00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
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
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
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
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
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
00353
00354
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
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 }
00401 }
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
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
00781
00782
00783
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);
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
01170 if (end == csArrayItemNotFound) return false;
01171 if (start == csArrayItemNotFound) return false;
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