csutil/array.h
Go to the documentation of this file.00001 /* 00002 Crystal Space Generic Array Template 00003 Copyright (C) 2003 by Matze Braun 00004 Copyright (C) 2003 by Jorrit Tyberghein 00005 Copyright (C) 2003,2004 by Eric Sunshine 00006 00007 This library is free software; you can redistribute it and/or 00008 modify it under the terms of the GNU Library General Public 00009 License as published by the Free Software Foundation; either 00010 version 2 of the License, or (at your option) any later version. 00011 00012 This library is distributed in the hope that it will be useful, 00013 but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00015 Library General Public License for more details. 00016 00017 You should have received a copy of the GNU Library General Public 00018 License along with this library; if not, write to the Free 00019 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00020 */ 00021 #ifndef __CSUTIL_ARRAY_H__ 00022 #define __CSUTIL_ARRAY_H__ 00023 00028 #include "csutil/custom_new_disable.h" 00029 #include <algorithm> 00030 #include "csutil/custom_new_enable.h" 00031 00032 #include "csutil/allocator.h" 00033 #include "csutil/comparator.h" 00034 #include "csutil/customallocated.h" 00035 #include "csutil/util.h" 00036 00037 #include "csutil/custom_new_disable.h" 00038 00039 #if defined(CS_MEMORY_TRACKER) 00040 #include "csutil/memdebug.h" 00041 #include "csutil/snprintf.h" 00042 #include <typeinfo> 00043 #endif 00044 00057 template <class T, class K> 00058 class csArrayCmp 00059 { 00060 public: 00066 typedef int(*CF)(T const&, K const&); 00068 csArrayCmp(K const& k, CF c = DefaultCompare) : key(k), cmp(c) {} 00070 csArrayCmp(csArrayCmp const& o) : key(o.key), cmp(o.cmp) {} 00072 csArrayCmp& operator=(csArrayCmp const& o) 00073 { key = o.key; cmp = o.cmp; return *this; } 00082 int operator()(T const& r) const { return cmp(r, key); } 00084 operator CF() const { return cmp; } 00086 operator K const&() const { return key; } 00097 static int DefaultCompare(T const& r, K const& k) 00098 { return csComparator<T,K>::Compare(r,k); } 00099 private: 00100 K key; 00101 CF cmp; 00102 }; 00103 00107 template <class T> 00108 class csArrayElementHandler 00109 { 00110 public: 00112 static void Construct (T* address) 00113 { 00114 new (static_cast<void*> (address)) T(); 00115 } 00116 00118 static void Construct (T* address, T const& src) 00119 { 00120 new (static_cast<void*> (address)) T(src); 00121 } 00122 00124 static void Destroy (T* address) 00125 { 00126 address->~T(); 00127 } 00128 00130 static void InitRegion (T* address, size_t count) 00131 { 00132 for (size_t i = 0 ; i < count ; i++) 00133 Construct (address + i); 00134 } 00135 00137 template<typename Allocator> 00138 static T* ResizeRegion (Allocator& alloc, T* mem, size_t relevantcount, 00139 size_t oldcount, size_t newcount) 00140 { 00141 (void)relevantcount; 00142 T* newp = (T*)alloc.Realloc (mem, newcount * sizeof(T)); 00143 if (newp != 0) return newp; 00144 // Realloc() failed - allocate a new block 00145 newp = (T*)alloc.Alloc (newcount * sizeof(T)); 00146 if (newcount < oldcount) 00147 memcpy (newp, mem, newcount * sizeof(T)); 00148 else 00149 memcpy (newp, mem, oldcount * sizeof(T)); 00150 alloc.Free (mem); 00151 return newp; 00152 } 00153 00155 static void MoveElements (T* mem, size_t dest, size_t src, size_t count) 00156 { 00157 memmove (mem + dest, mem + src, count * sizeof(T)); 00158 } 00159 00164 static void MoveElementsNoOverlap (T* mem, size_t dest, size_t src, size_t count) 00165 { 00166 memcpy (mem + dest, mem + src, count * sizeof(T)); 00167 } 00168 }; 00169 00178 template <class T> 00179 class csArraySafeCopyElementHandler 00180 { 00181 public: 00182 static void Construct (T* address) 00183 { 00184 new (static_cast<void*> (address)) T(); 00185 } 00186 00187 static void Construct (T* address, T const& src) 00188 { 00189 new (static_cast<void*> (address)) T(src); 00190 } 00191 00192 static void Destroy (T* address) 00193 { 00194 address->~T(); 00195 } 00196 00197 static void InitRegion (T* address, size_t count) 00198 { 00199 for (size_t i = 0 ; i < count ; i++) 00200 Construct (address + i); 00201 } 00202 00208 template<typename Allocator> 00209 static T* ResizeRegion (Allocator& alloc, T* mem, size_t relevantcount, 00210 size_t oldcount, size_t newcount) 00211 { 00212 if (newcount <= oldcount) 00213 { 00214 // Realloc is safe. 00215 T* newmem = (T*)alloc.Realloc (mem, newcount * sizeof (T)); 00216 if (newmem != 0) 00217 { 00218 CS_ASSERT (newmem == mem); 00219 return newmem; 00220 } 00221 // else Realloc() failed (probably not supported) - allocate a new block 00222 } 00223 00224 T* newmem = (T*)alloc.Alloc (newcount * sizeof (T)); 00225 size_t i; 00226 for (i = 0 ; i < relevantcount ; i++) 00227 { 00228 Construct (newmem + i, mem[i]); 00229 Destroy (mem + i); 00230 } 00231 alloc.Free (mem); 00232 return newmem; 00233 } 00234 00240 static void MoveElements (T* mem, size_t dest, size_t src, size_t count) 00241 { 00242 size_t i; 00243 if (dest < src) 00244 { 00245 for (i = 0 ; i < count ; i++) 00246 { 00247 Construct (mem + dest + i, mem[src + i]); 00248 Destroy (mem + src + i); 00249 } 00250 } 00251 else 00252 { 00253 i = count; 00254 while (i > 0) 00255 { 00256 i--; 00257 Construct (mem + dest + i, mem[src + i]); 00258 Destroy (mem + src + i); 00259 } 00260 } 00261 } 00262 00264 static void MoveElementsNoOverlap (T* mem, size_t dest, size_t src, size_t count) 00265 { 00266 MoveElements (mem, dest, src, count); 00267 } 00268 }; 00269 00270 00275 class csArrayThresholdVariable 00276 { 00277 size_t threshold; 00278 public: 00280 csArrayThresholdVariable (size_t in_threshold = 0) 00281 { threshold = (in_threshold > 0 ? in_threshold : 16); } 00283 size_t GetThreshold() const { return threshold; } 00284 }; 00285 00290 template<int N> 00291 class csArrayThresholdFixed 00292 { 00293 public: 00295 csArrayThresholdFixed (size_t x = 0) 00296 { (void)x; } 00298 size_t GetThreshold() const { return N; } 00299 // Work around VC7 bug apparently incorrectly copying this empty class 00300 csArrayThresholdFixed& operator= (const csArrayThresholdFixed&) 00301 { return *this; } 00302 }; 00303 00311 template<typename Threshold = csArrayThresholdVariable> 00312 class csArrayCapacityLinear : public Threshold 00313 { 00314 public: 00316 00317 csArrayCapacityLinear () : Threshold () {} 00318 csArrayCapacityLinear (const Threshold& threshold) : Threshold (threshold) 00319 {} 00321 00327 csArrayCapacityLinear (const size_t x) : Threshold (x) 00328 {} 00329 00335 bool IsCapacityExcessive (size_t capacity, size_t count) const 00336 { 00337 return (capacity > this->GetThreshold() 00338 && count < capacity - this->GetThreshold()); 00339 } 00345 size_t GetCapacity (size_t count) const 00346 { 00347 return ((count + this->GetThreshold() - 1) / this->GetThreshold()) * 00348 this->GetThreshold(); 00349 } 00350 }; 00351 00352 // Alias for csArrayCapacityLinear<csArrayThresholdVariable> to keep 00353 // SWIG generated Java classes (and thus filenames) short enough for Windows. 00354 // Note that a typedef wont work because SWIG would expand it. 00355 struct csArrayCapacityVariableGrow : 00356 public csArrayCapacityLinear<csArrayThresholdVariable> 00357 { 00358 csArrayCapacityVariableGrow () : 00359 csArrayCapacityLinear<csArrayThresholdVariable> () {} 00360 csArrayCapacityVariableGrow (const csArrayThresholdVariable& threshold) : 00361 csArrayCapacityLinear<csArrayThresholdVariable> (threshold) {} 00362 csArrayCapacityVariableGrow (const size_t x) : 00363 csArrayCapacityLinear<csArrayThresholdVariable> (x) {} 00364 } ; 00365 // @@@ Deprecate? Name is non-descriptive/misleading 00366 typedef csArrayCapacityVariableGrow csArrayCapacityDefault; 00367 00372 template<int N> 00373 struct csArrayCapacityFixedGrow : 00374 public csArrayCapacityLinear<csArrayThresholdFixed<N> > 00375 { 00376 csArrayCapacityFixedGrow () : 00377 csArrayCapacityLinear<csArrayThresholdFixed<N> > () {} 00378 }; 00379 00380 namespace CS 00381 { 00382 namespace Container 00383 { 00384 typedef CS::Memory::AllocatorMalloc ArrayAllocDefault; 00385 typedef csArrayCapacityFixedGrow<16> ArrayCapacityDefault; 00386 00387 template<int MaxGrow = 1 << 20> 00388 struct ArrayCapacityExponential 00389 { 00390 bool IsCapacityExcessive (size_t capacity, size_t count) const 00391 { 00392 return size_t (csFindNearestPowerOf2 ((int)count)) < (capacity/2); 00393 } 00394 size_t GetCapacity (size_t count) const 00395 { 00396 size_t newCap = (size_t)csFindNearestPowerOf2 ((int)count); 00397 return newCap < MaxGrow ? newCap : MaxGrow; 00398 } 00399 }; 00400 } // namespace Container 00401 } // namespace CS 00402 00407 const size_t csArrayItemNotFound = (size_t)-1; 00408 00417 template <class T, 00418 class ElementHandler = csArrayElementHandler<T>, 00419 class MemoryAllocator = CS::Container::ArrayAllocDefault, 00420 class CapacityHandler = CS::Container::ArrayCapacityDefault> 00421 class csArray : public CS::Memory::CustomAllocated 00422 { 00423 public: 00424 typedef csArray<T, ElementHandler, MemoryAllocator, CapacityHandler> ThisType; 00425 typedef T ValueType; 00426 typedef ElementHandler ElementHandlerType; 00427 typedef MemoryAllocator AllocatorType; 00428 typedef CapacityHandler CapacityHandlerType; 00429 00430 private: 00431 size_t count; 00436 struct ArrayCapacity : public CapacityHandler 00437 { 00438 size_t c; 00439 ArrayCapacity (size_t in_capacity) 00440 { c = (in_capacity > 0 ? in_capacity : 0); } 00441 ArrayCapacity (size_t in_capacity, const CapacityHandler& ch) : 00442 CapacityHandler (ch) 00443 { c = (in_capacity > 0 ? in_capacity : 0); } 00444 void CopyFrom (const CapacityHandler& source) 00445 { 00446 CapacityHandler::operator= (source); 00447 } 00448 }; 00449 ArrayCapacity capacity; 00450 CS::Memory::AllocatorPointerWrapper<T, MemoryAllocator> root; 00451 00452 protected: 00457 void InitRegion (size_t start, size_t count) 00458 { 00459 ElementHandler::InitRegion (root.p+start, count); 00460 } 00461 00466 void SetDataVeryUnsafe (T* data) { root.p = data; } 00471 void SetSizeVeryUnsafe (size_t n) { count = n; } 00476 void SetCapacityVeryUnsafe (size_t n) { capacity.c = n; } 00477 private: 00479 void CopyFrom (const csArray& source) 00480 { 00481 capacity.CopyFrom (source.capacity); 00482 SetSizeUnsafe (source.GetSize ()); 00483 for (size_t i=0 ; i<source.GetSize () ; i++) 00484 ElementHandler::Construct (root.p + i, source[i]); 00485 } 00486 00488 void InternalSetCapacity (size_t n) 00489 { 00490 if (root.p == 0) 00491 { 00492 root.p = (T*)root.Alloc (n * sizeof (T)); 00493 } 00494 else 00495 { 00496 root.p = ElementHandler::ResizeRegion (root, root.p, count, capacity.c, n); 00497 } 00498 capacity.c = n; 00499 } 00500 00505 void AdjustCapacity (size_t n) 00506 { 00507 if (n > capacity.c || capacity.IsCapacityExcessive (capacity.c, n)) 00508 { 00509 InternalSetCapacity (capacity.GetCapacity (n)); 00510 } 00511 } 00512 00519 void SetSizeUnsafe (size_t n) 00520 { 00521 if (n > capacity.c) 00522 AdjustCapacity (n); 00523 count = n; 00524 } 00525 00526 public: 00538 static int DefaultCompare(T const& r1, T const& r2) 00539 { 00540 return csComparator<T,T>::Compare(r1,r2); 00541 } 00542 00549 csArray (size_t in_capacity = 0, 00550 const CapacityHandler& ch = CapacityHandler()) : count (0), 00551 capacity (in_capacity, ch) 00552 { 00553 #ifdef CS_MEMORY_TRACKER 00554 root.SetMemTrackerInfo (typeid(*this).name()); 00555 #endif 00556 if (capacity.c != 0) 00557 { 00558 root.p = (T*)root.Alloc (capacity.c * sizeof (T)); 00559 } 00560 else 00561 { 00562 root.p = 0; 00563 } 00564 } 00569 csArray (size_t in_capacity, 00570 const MemoryAllocator& alloc, 00571 const CapacityHandler& ch) : count (0), 00572 capacity (in_capacity, ch), root (alloc) 00573 { 00574 #ifdef CS_MEMORY_TRACKER 00575 root.SetMemTrackerInfo (typeid(*this).name()); 00576 #endif 00577 if (capacity.c != 0) 00578 { 00579 root.p = (T*)root.Alloc (capacity.c * sizeof (T)); 00580 } 00581 else 00582 { 00583 root.p = 0; 00584 } 00585 } 00586 00588 ~csArray () 00589 { 00590 DeleteAll (); 00591 } 00592 00594 csArray (const csArray& source) : count (0), capacity (0), root (0) 00595 { 00596 #ifdef CS_MEMORY_TRACKER 00597 root.SetMemTrackerInfo (typeid(*this).name()); 00598 #endif 00599 CopyFrom (source); 00600 } 00601 00603 csArray<T,ElementHandler,MemoryAllocator,CapacityHandler>& operator= ( 00604 const csArray& other) 00605 { 00606 if (&other != this) 00607 { 00608 DeleteAll (); 00609 CopyFrom (other); 00610 } 00611 return *this; 00612 } 00613 00615 size_t GetSize () const 00616 { 00617 return count; 00618 } 00619 00621 size_t Capacity () const 00622 { 00623 return capacity.c; 00624 } 00625 00632 // @@@ FIXME: What about custom allocators? 00633 void TransferTo (csArray& destination) 00634 { 00635 if (&destination != this) 00636 { 00637 destination.DeleteAll (); 00638 destination.root.p = root.p; 00639 destination.count = count; 00640 destination.capacity = capacity; 00641 root.p = 0; 00642 capacity.c = count = 0; 00643 } 00644 } 00645 00655 void SetSize (size_t n, T const& what) 00656 { 00657 if (n <= count) 00658 { 00659 Truncate (n); 00660 } 00661 else 00662 { 00663 size_t old_len = GetSize (); 00664 SetSizeUnsafe (n); 00665 for (size_t i = old_len ; i < n ; i++) 00666 ElementHandler::Construct (root.p + i, what); 00667 } 00668 } 00669 00677 void SetSize (size_t n) 00678 { 00679 if (n <= count) 00680 { 00681 Truncate (n); 00682 } 00683 else 00684 { 00685 size_t old_len = GetSize (); 00686 SetSizeUnsafe (n); 00687 ElementHandler::InitRegion (root.p + old_len, n-old_len); 00688 } 00689 } 00690 00691 00693 T& Get (size_t n) 00694 { 00695 CS_ASSERT (n < count); 00696 return root.p[n]; 00697 } 00698 00700 T const& Get (size_t n) const 00701 { 00702 CS_ASSERT (n < count); 00703 return root.p[n]; 00704 } 00705 00711 T& GetExtend (size_t n) 00712 { 00713 if (n >= count) 00714 SetSize (n+1); 00715 return root.p[n]; 00716 } 00717 00723 T& GetExtend (size_t n, T const& what) 00724 { 00725 if (n >= count) 00726 SetSize (n+1, what); 00727 return root.p[n]; 00728 } 00729 00731 T& operator [] (size_t n) 00732 { 00733 return Get(n); 00734 } 00735 00737 T const& operator [] (size_t n) const 00738 { 00739 return Get(n); 00740 } 00741 00746 void Put (size_t n, T const& what) 00747 { 00748 if (n >= count) 00749 SetSize (n+1); 00750 ElementHandler::Destroy (root.p + n); 00751 ElementHandler::Construct (root.p + n, what); 00752 } 00753 00761 template <class K> 00762 size_t FindKey (csArrayCmp<T,K> comparekey) const 00763 { 00764 for (size_t i = 0 ; i < GetSize () ; i++) 00765 if (comparekey (root.p[i]) == 0) 00766 return i; 00767 return csArrayItemNotFound; 00768 } 00769 00774 size_t Push (T const& what) 00775 { 00776 if (((&what >= root.p) && (&what < root.p + GetSize())) && 00777 (capacity.c < count + 1)) 00778 { 00779 /* 00780 Special case: An element from this very array is pushed, and a 00781 reallocation is needed. This could cause the passed ref to the 00782 element to be pushed to be read from deleted memory. Work 00783 around this. 00784 */ 00785 size_t whatIndex = &what - root.p; 00786 SetSizeUnsafe (count + 1); 00787 ElementHandler::Construct (root.p + count - 1, root.p[whatIndex]); 00788 } 00789 else 00790 { 00791 SetSizeUnsafe (count + 1); 00792 ElementHandler::Construct (root.p + count - 1, what); 00793 } 00794 return count - 1; 00795 } 00796 00801 size_t PushSmart (T const& what) 00802 { 00803 size_t const n = Find (what); 00804 return (n == csArrayItemNotFound) ? Push (what) : n; 00805 } 00806 00812 void Merge(const csArray& origin) 00813 { 00814 for(size_t i = 0; i < origin.GetSize(); i++) 00815 Push(origin.Get(i)); 00816 } 00817 00824 void MergeSmart(const csArray& origin) 00825 { 00826 for(size_t i = 0; i < origin.GetSize(); i++) 00827 PushSmart(origin.Get(i)); 00828 } 00829 00831 T Pop () 00832 { 00833 CS_ASSERT (count > 0); 00834 T ret(root.p [count - 1]); 00835 ElementHandler::Destroy (root.p + count - 1); 00836 SetSizeUnsafe (count - 1); 00837 return ret; 00838 } 00839 00841 T const& Top () const 00842 { 00843 CS_ASSERT (count > 0); 00844 return root.p [count - 1]; 00845 } 00846 00848 T& Top () 00849 { 00850 CS_ASSERT (count > 0); 00851 return root.p [count - 1]; 00852 } 00853 00855 bool Insert (size_t n, T const& item) 00856 { 00857 if (n <= count) 00858 { 00859 SetSizeUnsafe (count + 1); // Increments 'count' as a side-effect. 00860 size_t const nmove = (count - n - 1); 00861 if (nmove > 0) 00862 ElementHandler::MoveElements (root.p, n+1, n, nmove); 00863 ElementHandler::Construct (root.p + n, item); 00864 return true; 00865 } 00866 else 00867 return false; 00868 } 00869 00873 csArray<T> Section (size_t low, size_t high) const 00874 { 00875 CS_ASSERT (high < count && high >= low); 00876 csArray<T> sect (high - low + 1); 00877 for (size_t i = low; i <= high; i++) sect.Push (root.p[i]); 00878 return sect; 00879 } 00880 00886 template <class K> 00887 size_t FindSortedKey (csArrayCmp<T,K> comparekey, 00888 size_t* candidate = 0) const 00889 { 00890 size_t m = 0, l = 0, r = GetSize (); 00891 while (l < r) 00892 { 00893 m = (l + r) / 2; 00894 int cmp = comparekey (root.p[m]); 00895 if (cmp == 0) 00896 { 00897 if (candidate) *candidate = csArrayItemNotFound; 00898 return m; 00899 } 00900 else if (cmp < 0) 00901 l = m + 1; 00902 else 00903 r = m; 00904 } 00905 if ((m + 1) == r) 00906 m++; 00907 if (candidate) *candidate = m; 00908 return csArrayItemNotFound; 00909 } 00910 00921 size_t InsertSorted (const T& item, 00922 int (*compare)(T const&, T const&) = DefaultCompare, 00923 size_t* equal_index = 0) 00924 { 00925 size_t m = 0, l = 0, r = GetSize (); 00926 while (l < r) 00927 { 00928 m = (l + r) / 2; 00929 int cmp = compare (root.p [m], item); 00930 00931 if (cmp == 0) 00932 { 00933 if (equal_index) *equal_index = m; 00934 Insert (++m, item); 00935 return m; 00936 } 00937 else if (cmp < 0) 00938 l = m + 1; 00939 else 00940 r = m; 00941 } 00942 if ((m + 1) == r) 00943 m++; 00944 if (equal_index) *equal_index = csArrayItemNotFound; 00945 Insert (m, item); 00946 return m; 00947 } 00948 00955 size_t Find (T const& which) const 00956 { 00957 for (size_t i = 0 ; i < GetSize () ; i++) 00958 if (root.p[i] == which) 00959 return i; 00960 return csArrayItemNotFound; 00961 } 00962 00964 size_t Contains(T const& which) const 00965 { return Find(which); } 00966 00973 size_t GetIndex (const T* which) const 00974 { 00975 CS_ASSERT (which >= root.p); 00976 CS_ASSERT (which < (root.p + count)); 00977 return which-root.p; 00978 } 00979 00983 void Sort (int (*compare)(T const&, T const&) = DefaultCompare) 00984 { 00985 qsort (root.p, GetSize (), sizeof(T), 00986 (int (*)(void const*, void const*))compare); 00987 } 00988 00992 template<typename Pred> 00993 void Sort (Pred& pred) 00994 { 00995 std::sort (root.p, root.p + GetSize (), pred); 00996 } 00997 01001 template<typename Pred> 01002 void SortStable (Pred& pred) 01003 { 01004 std::stable_sort (root.p, root.p + GetSize (), pred); 01005 } 01006 01011 void DeleteAll () 01012 { 01013 if (root.p) 01014 { 01015 size_t i; 01016 for (i = 0 ; i < count ; i++) 01017 ElementHandler::Destroy (root.p + i); 01018 root.Free (root.p); 01019 root.p = 0; 01020 capacity.c = count = 0; 01021 } 01022 } 01023 01035 void Truncate (size_t n) 01036 { 01037 CS_ASSERT(n <= count); 01038 if (n < count) 01039 { 01040 for (size_t i = n; i < count; i++) 01041 ElementHandler::Destroy (root.p + i); 01042 SetSizeUnsafe(n); 01043 } 01044 } 01045 01051 void Empty () 01052 { 01053 Truncate (0); 01054 } 01055 01062 bool IsEmpty() const 01063 { 01064 return GetSize() == 0; 01065 } 01066 01073 void SetCapacity (size_t n) 01074 { 01075 if (n > GetSize ()) 01076 InternalSetCapacity (n); 01077 } 01078 01086 void SetMinimalCapacity (size_t n) 01087 { 01088 if (n < Capacity ()) return; 01089 if (n > GetSize ()) 01090 InternalSetCapacity (n); 01091 } 01092 01098 void ShrinkBestFit () 01099 { 01100 if (count == 0) 01101 { 01102 DeleteAll (); 01103 } 01104 else if (count != capacity.c) 01105 { 01106 root.p = ElementHandler::ResizeRegion (root, root.p, count, capacity.c, count); 01107 capacity.c = count; 01108 } 01109 } 01110 01119 bool DeleteIndex (size_t n) 01120 { 01121 if (n < count) 01122 { 01123 size_t const ncount = count - 1; 01124 size_t const nmove = ncount - n; 01125 ElementHandler::Destroy (root.p + n); 01126 if (nmove > 0) 01127 ElementHandler::MoveElements (root.p, n, n+1, nmove); 01128 SetSizeUnsafe (ncount); 01129 return true; 01130 } 01131 else 01132 return false; 01133 } 01134 01144 bool DeleteIndexFast (size_t n) 01145 { 01146 if (n < count) 01147 { 01148 size_t const ncount = count - 1; 01149 size_t const nmove = ncount - n; 01150 ElementHandler::Destroy (root.p + n); 01151 if (nmove > 0) 01152 ElementHandler::MoveElementsNoOverlap (root.p, n, ncount, 1); 01153 SetSizeUnsafe (ncount); 01154 return true; 01155 } 01156 else 01157 return false; 01158 } 01159 01166 bool DeleteRange (size_t start, size_t end) 01167 { 01168 if (start >= count) return false; 01169 // Treat 'csArrayItemNotFound' as invalid indices, do nothing. 01170 if (end == csArrayItemNotFound) return false; 01171 if (start == csArrayItemNotFound) return false;//start = 0; 01172 if (end >= count) end = count - 1; 01173 size_t i; 01174 for (i = start ; i <= end ; i++) 01175 ElementHandler::Destroy (root.p + i); 01176 01177 size_t const range_size = end - start + 1; 01178 size_t const ncount = count - range_size; 01179 size_t const nmove = count - end - 1; 01180 if (nmove > 0) 01181 ElementHandler::MoveElements (root.p, start, start + range_size, nmove); 01182 SetSizeUnsafe (ncount); 01183 return true; 01184 } 01185 01192 bool Delete (T const& item) 01193 { 01194 size_t const n = Find (item); 01195 if (n != csArrayItemNotFound) 01196 return DeleteIndex (n); 01197 return false; 01198 } 01199 01201 class Iterator 01202 { 01203 public: 01205 Iterator(Iterator const& r) : 01206 currentelem(r.currentelem), array(r.array) {} 01207 01209 Iterator& operator=(Iterator const& r) 01210 { currentelem = r.currentelem; array = r.array; return *this; } 01211 01213 bool HasNext() const 01214 { return currentelem < array.GetSize (); } 01215 01217 T& Next() 01218 { return array.Get(currentelem++); } 01219 01221 void Reset() 01222 { currentelem = 0; } 01223 01224 protected: 01225 Iterator(csArray<T, ElementHandler, MemoryAllocator, CapacityHandler>& newarray) 01226 : currentelem(0), array(newarray) {} 01227 friend class csArray<T, ElementHandler, MemoryAllocator, CapacityHandler>; 01228 01229 private: 01230 size_t currentelem; 01231 csArray<T, ElementHandler, MemoryAllocator, CapacityHandler>& array; 01232 }; 01233 01235 class ConstIterator 01236 { 01237 public: 01239 ConstIterator(ConstIterator const& r) : 01240 currentelem(r.currentelem), array(r.array) {} 01241 01243 ConstIterator& operator=(ConstIterator const& r) 01244 { currentelem = r.currentelem; array = r.array; return *this; } 01245 01247 bool HasNext() const 01248 { return currentelem < array.GetSize (); } 01249 01251 const T& Next() 01252 { return array.Get(currentelem++); } 01253 01255 void Reset() 01256 { currentelem = 0; } 01257 01258 protected: 01259 ConstIterator(const csArray<T, ElementHandler, MemoryAllocator, CapacityHandler>& newarray) 01260 : currentelem(0), array(newarray) {} 01261 friend class csArray<T, ElementHandler, MemoryAllocator, CapacityHandler>; 01262 01263 private: 01264 size_t currentelem; 01265 const csArray<T, ElementHandler, MemoryAllocator, CapacityHandler>& array; 01266 }; 01267 01269 class ReverseIterator 01270 { 01271 public: 01273 ReverseIterator(ReverseIterator const& r) : 01274 currentelem(r.currentelem), array(r.array) {} 01275 01277 ReverseIterator& operator=(ReverseIterator const& r) 01278 { currentelem = r.currentelem; array = r.array; return *this; } 01279 01281 bool HasNext() const 01282 { return currentelem > 0 && currentelem <= array.GetSize (); } 01283 01285 T& Next() 01286 { return array.Get(--currentelem); } 01287 01289 void Reset() 01290 { currentelem = array.GetSize (); } 01291 01292 protected: 01293 ReverseIterator(csArray<T, ElementHandler, MemoryAllocator, CapacityHandler>& newarray) 01294 : currentelem(newarray.GetSize ()), array(newarray) {} 01295 friend class csArray<T, ElementHandler, MemoryAllocator, CapacityHandler>; 01296 01297 private: 01298 size_t currentelem; 01299 csArray<T, ElementHandler, MemoryAllocator, CapacityHandler>& array; 01300 }; 01301 01303 class ReverseConstIterator 01304 { 01305 public: 01307 ReverseConstIterator(ReverseConstIterator const& r) : 01308 currentelem(r.currentelem), array(r.array) {} 01309 01311 ReverseConstIterator& operator=(ReverseConstIterator const& r) 01312 { currentelem = r.currentelem; array = r.array; return *this; } 01313 01315 bool HasNext() const 01316 { return currentelem > 0 && currentelem <= array.GetSize (); } 01317 01319 const T& Next() 01320 { return array.Get(--currentelem); } 01321 01323 void Reset() 01324 { currentelem = array.GetSize (); } 01325 01326 protected: 01327 ReverseConstIterator(const csArray<T, ElementHandler, MemoryAllocator, CapacityHandler>& newarray) 01328 : currentelem(newarray.GetSize ()), array(newarray) {} 01329 friend class csArray<T, ElementHandler, MemoryAllocator, CapacityHandler>; 01330 01331 private: 01332 size_t currentelem; 01333 const csArray<T, ElementHandler, MemoryAllocator, CapacityHandler>& array; 01334 }; 01335 01337 Iterator GetIterator() 01338 { return Iterator(*this); } 01339 01341 ConstIterator GetIterator() const 01342 { return ConstIterator(*this); } 01343 01345 ReverseIterator GetReverseIterator() 01346 { return ReverseIterator(*this); } 01347 01349 ReverseConstIterator GetReverseIterator() const 01350 { return ReverseConstIterator(*this); } 01351 01353 bool operator== (const csArray& other) const 01354 { 01355 if (other.GetSize() != GetSize()) return false; 01356 for (size_t i = 0; i < GetSize(); i++) 01357 if (!(Get (i) == other[i])) 01358 return false; 01359 return true; 01360 } 01361 01362 bool operator!= (const csArray& other) const { return !(*this==other); } 01363 01365 const MemoryAllocator& GetAllocator() const 01366 { 01367 return root; 01368 } 01369 }; 01370 01376 template <class T, 01377 class Allocator = CS::Memory::AllocatorMalloc, 01378 class CapacityHandler = CS::Container::ArrayCapacityDefault> 01379 class csSafeCopyArray 01380 : public csArray<T, 01381 csArraySafeCopyElementHandler<T>, 01382 Allocator, CapacityHandler> 01383 { 01384 public: 01389 csSafeCopyArray (size_t limit = 0, 01390 const CapacityHandler& ch = CapacityHandler()) 01391 : csArray<T, csArraySafeCopyElementHandler<T>, Allocator, 01392 CapacityHandler> (limit, ch) 01393 { 01394 } 01395 }; 01396 01397 #include "csutil/custom_new_enable.h" 01398 01401 #endif
Generated for Crystal Space 2.0 by doxygen 1.6.1