CrystalSpace

Public API Reference

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.7.6.1