CrystalSpace

Public API Reference

Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

csutil/array.h

00001 /*
00002   Crystal Space Generic Array Template
00003   Copyright (C) 2003 by Matze Braun
00004 
00005   This library is free software; you can redistribute it and/or
00006   modify it under the terms of the GNU Library General Public
00007   License as published by the Free Software Foundation; either
00008   version 2 of the License, or (at your option) any later version.
00009 
00010   This library is distributed in the hope that it will be useful,
00011   but WITHOUT ANY WARRANTY; without even the implied warranty of
00012   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013   Library General Public License for more details.
00014 
00015   You should have received a copy of the GNU Library General Public
00016   License along with this library; if not, write to the Free
00017   Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00018 */
00019 #ifndef __CSUTIL_ARRAY_H__
00020 #define __CSUTIL_ARRAY_H__
00021 
00022 // hack: work around problems caused by #defining 'new'
00023 #ifdef CS_EXTENSIVE_MEMDEBUG
00024 # undef new
00025 #endif
00026 #include <new>
00027 
00029 typedef int ArraySortCompareFunction (void const* item1,
00030         void const* item2);
00031 
00035 template <class T>
00036 class csArrayElementHandler
00037 {
00038 public:
00039   static void Construct (T* address, T const& src)
00040   {
00041     new (static_cast<void*>(address)) T(src);
00042   }
00043 
00044   static void Destroy (T* address)
00045   {
00046     address->~T();
00047   }
00048 
00049   static void InitRegion (T* address, int count)
00050   {
00051     for (int i = 0 ; i < count ; i++)
00052       Construct (address + i, T ());
00053   }
00054 };
00055 
00059 template <class T>
00060 class csArrayMemoryAllocator
00061 {
00062 public:
00063   static T* Alloc (int count)
00064   {
00065     return (T*)malloc (count * sizeof(T));
00066   }
00067 
00068   static void Free (T* mem)
00069   {
00070     free (mem);
00071   }
00072 
00073   // The 'relevantcount' parameter should be the number of items
00074   // in the old array that are initialized.
00075   static T* Realloc (T* mem, int relevantcount, int oldcount, int newcount)
00076   {
00077     (void)relevantcount; (void)oldcount;
00078     return (T*)realloc (mem, newcount * sizeof(T));
00079   }
00080 };
00081 
00090 template <class T, class ElementHandler = csArrayElementHandler<T> >
00091 class csSafeCopyArrayMemoryAllocator
00092 {
00093 public:
00094   static T* Alloc (int count)
00095   {
00096     return (T*)malloc (count * sizeof(T));
00097   }
00098 
00099   static void Free (T* mem)
00100   {
00101     free (mem);
00102   }
00103 
00104   static T* Realloc (T* mem, int relevantcount, int oldcount, int newcount)
00105   {
00106     if (newcount <= oldcount)
00107     {
00108       // Realloc is safe.
00109       T* newmem = (T*)realloc (mem, newcount * sizeof (T));
00110       CS_ASSERT (newmem == mem);
00111       return newmem;
00112     }
00113 
00114     T* newmem = Alloc (newcount);
00115     int i;
00116     for (i = 0 ; i < relevantcount ; i++)
00117     {
00118       ElementHandler::Construct (newmem + i, mem[i]);
00119       ElementHandler::Destroy (mem + i);
00120     }
00121     Free (mem);
00122     return newmem;
00123   }
00124 };
00125 
00126 
00134 template <class T,
00135         class ElementHandler = csArrayElementHandler<T>,
00136         class MemoryAllocator = csArrayMemoryAllocator<T> >
00137 class csArray
00138 {
00139 private:
00140   int count;
00141   int capacity;
00142   int threshold;
00143   T* root;
00144 
00145 protected:
00150   void InitRegion (int start, int count)
00151   {
00152     ElementHandler::InitRegion (root+start, count);
00153   }
00154 
00155 private:
00157   void CopyFrom (const csArray& source)
00158   {
00159     if (&source != this)
00160     {
00161       DeleteAll ();
00162       threshold = source.threshold;
00163       SetLengthUnsafe (source.Length ());
00164       for (int i=0 ; i<source.Length() ; i++)
00165         ElementHandler::Construct (root + i, source[i]);
00166     }
00167   }
00168 
00169   // Adjust internal capacity of this array.
00170   void AdjustCapacity (int n)
00171   {
00172     if (n > capacity || (capacity > threshold && n < capacity - threshold))
00173     {
00174       n = ((n + threshold - 1) / threshold ) * threshold;
00175       if (root == 0)
00176         root = MemoryAllocator::Alloc (n);
00177       else
00178         root = MemoryAllocator::Realloc (root, count, capacity, n);
00179       capacity = n;
00180     }
00181   }
00182 
00183   // Set array length.  NOTE: Do not make this public since it does not
00184   // properly construct/destroy elements.  To safely truncate the array, use
00185   // Truncate().  To safely set the capacity, use SetCapacity().
00186   void SetLengthUnsafe (int n)
00187   {
00188     if (n > capacity)
00189       AdjustCapacity (n);
00190     count = n;
00191   }
00192 
00193 public:
00195   typedef int ArrayCompareFunction (T const& item1, T const& item2);
00197   typedef int ArrayCompareKeyFunction (T const& item1, void* item2);
00198 
00203   csArray (int icapacity = 0, int ithreshold = 0)
00204   {
00205     count = 0;
00206     capacity = (icapacity > 0 ? icapacity : 0);
00207     threshold = (ithreshold > 0 ? ithreshold : 16);
00208     if (capacity != 0)
00209       root = MemoryAllocator::Alloc (capacity);
00210     else
00211       root = 0;
00212   }
00213 
00214   ~csArray ()
00215   {
00216     DeleteAll ();
00217   }
00218 
00220   csArray (const csArray& source)
00221   {
00222     root = 0;
00223     capacity = 0;
00224     count = 0;
00225     CopyFrom (source);
00226   }
00227   
00229   csArray<T>& operator= (const csArray& other)
00230   {
00231     CopyFrom (other);
00232     return *this;
00233   }
00234 
00236   int Length () const
00237   {
00238     return count;
00239   }
00240 
00242   int Capacity () const
00243   {
00244     return capacity;
00245   }
00246 
00253   void TransferTo (csArray& destination)
00254   {
00255     if (&destination != this)
00256     {
00257       destination.DeleteAll ();
00258       destination.root = root;
00259       destination.count = count;
00260       destination.capacity = capacity;
00261       destination.threshold = threshold;
00262       root = 0;
00263       capacity = count = 0;
00264     }
00265   }
00266 
00274   void SetLength (int n, T const& what)
00275   {
00276     if (n <= count)
00277     {
00278       Truncate (n);
00279     }
00280     else
00281     {
00282       int old_len = Length ();
00283       SetLengthUnsafe (n);
00284       for (int i = old_len ; i < n ; i++)
00285         ElementHandler::Construct (root + i, what);
00286     }
00287   }
00288 
00290   void SetLength (int n)
00291   {
00292     if (n <= count)
00293     {
00294       Truncate (n);
00295     }
00296     else
00297     {
00298       int old_len = Length ();
00299       SetLengthUnsafe (n);
00300       ElementHandler::InitRegion (root + old_len, n-old_len);
00301     }
00302   }
00303 
00305   T& Get (int n)
00306   {
00307     CS_ASSERT (n >= 0 && n < count);
00308     return root[n];
00309   }
00310 
00312   T const& Get (int n) const
00313   {
00314     CS_ASSERT (n >= 0 && n < count);
00315     return root[n];
00316   }
00317 
00322   T& GetExtend (int n)
00323   {
00324     CS_ASSERT (n >= 0);
00325     if (n >= count)
00326       SetLength (n+1);
00327     return root[n];
00328   }
00329 
00331   T& operator [] (int n)
00332   {
00333     return Get(n);
00334   }
00335 
00337   T const& operator [] (int n) const
00338   {
00339     return Get(n);
00340   }
00341 
00343   void Put (int n, T const& what)
00344   {
00345     CS_ASSERT (n >= 0);
00346     if (n >= count)
00347       SetLength (n+1);
00348     ElementHandler::Destroy (root + n);
00349     ElementHandler::Construct (root + n, what);
00350   }
00351 
00355   int FindKey (void* key, ArrayCompareKeyFunction* comparekey) const
00356   {
00357     for (int i = 0 ; i < Length () ; i++)
00358       if (comparekey (root[i], key) == 0)
00359         return i;
00360     return -1;
00361   }
00362 
00363 
00365   int Push (T const& what)
00366   {
00367     SetLengthUnsafe (count + 1);
00368     ElementHandler::Construct (root + count - 1, what);
00369     return count - 1;
00370   }
00371 
00372   /*
00373    * Push a element onto the tail end of the array if not already present.
00374    * Returns index of newly pushed element or index of already present element.
00375    */
00376   int PushSmart (T const& what)
00377   {
00378     int const n = Find (what);
00379     return (n < 0) ? Push (what) : n;
00380   }
00381 
00383   T Pop ()
00384   {
00385     CS_ASSERT (count > 0);
00386     T ret(root [count - 1]);
00387     ElementHandler::Destroy (root + count - 1);
00388     SetLengthUnsafe (count - 1);
00389     return ret;
00390   }
00391 
00393   T const& Top () const
00394   {
00395     CS_ASSERT (count > 0);
00396     return root [count - 1];
00397   }
00398 
00400   T& Top ()
00401   {
00402     CS_ASSERT (count > 0);
00403     return root [count - 1];
00404   }
00405 
00407   bool Insert (int n, T const& item)
00408   {
00409     if (n <= count)
00410     {
00411       SetLengthUnsafe (count + 1); // Increments 'count' as a side-effect.
00412       int const nmove = (count - n - 1);
00413       if (nmove > 0)
00414         memmove (root + n + 1, root + n, nmove * sizeof(T));
00415       ElementHandler::Construct (root + n, item);
00416       return true;
00417     }
00418     else
00419       return false;
00420   }
00421 
00425   csArray<T> Section (int low, int high) const
00426   {
00427     CS_ASSERT (low >= 0 && high < count && high >= low);
00428     csArray<T> sect (high - low + 1);
00429     for (int i = low; i <= high; i++) sect.Push (root[i]);
00430     return sect;
00431   }
00432 
00434   static int DefaultCompare (T const &item1, T const &item2)
00435   {
00436     if (item1 < item2) return -1;
00437     else if (item1 > item2) return 1;
00438     else return 0;
00439   }
00440 
00442   static int DefaultCompareKey (T const &item1, void* p)
00443   {
00444     T const& item2 = *(T const*)p;
00445     if (item1 < item2) return -1;
00446     else if (item1 > item2) return 1;
00447     else return 0;
00448   }
00449 
00454   int FindSortedKey (void* key, ArrayCompareKeyFunction* comparekey
00455     = DefaultCompareKey, int* candidate = 0) const
00456   {
00457     int m = 0, l = 0, r = Length () - 1;
00458     while (l <= r)
00459     {
00460       m = (l + r) / 2;
00461       int cmp = comparekey (root [m], key);
00462 
00463       if (cmp == 0)
00464       {
00465         if (candidate) *candidate = -1;
00466         return m;
00467       }
00468       else if (cmp < 0)
00469         l = m + 1;
00470       else
00471         r = m - 1;
00472     }
00473     if (candidate) *candidate = m;
00474     return -1;
00475   }
00476 
00481   int InsertSorted (const T &item, ArrayCompareFunction* compare
00482     = DefaultCompare, int* equal_index = 0)
00483   {
00484     int m = 0, l = 0, r = Length () - 1;
00485     while (l <= r)
00486     {
00487       m = (l + r) / 2;
00488       int cmp = compare (root [m], item);
00489 
00490       if (cmp == 0)
00491       {
00492         if (equal_index) *equal_index = m;
00493         Insert (++m, item);
00494         return m;
00495       }
00496       else if (cmp < 0)
00497         l = m + 1;
00498       else
00499         r = m - 1;
00500     }
00501     if (r == m)
00502       m++;
00503     if (equal_index) *equal_index = -1;
00504     Insert (m, item);
00505     return m;
00506   }
00507 
00509   int Find (T const& which) const
00510   {
00511     for (int i = 0 ; i < Length () ; i++)
00512       if (root[i] == which)
00513         return i;
00514     return -1;
00515   }
00516 
00520   void Sort (ArraySortCompareFunction* compare)
00521   {
00522     qsort (root, Length (), sizeof (T), compare);
00523   }
00524 
00528   void DeleteAll ()
00529   {
00530     if (root)
00531     {
00532       int i;
00533       for (i = 0 ; i < count ; i++)
00534         ElementHandler::Destroy (root + i);
00535       MemoryAllocator::Free (root);
00536       root = 0;
00537       capacity = count = 0;
00538     }
00539   }
00540 
00546   void Truncate (int n)
00547   {
00548     CS_ASSERT(n >= 0);
00549     CS_ASSERT(n <= count);
00550     if (n < count)
00551     {
00552       for (int i = n; i < count; i++)
00553         ElementHandler::Destroy (root + i);
00554       SetLengthUnsafe(n);
00555     }
00556   }
00557 
00563   void Empty ()
00564   {
00565     Truncate (0);
00566   }
00567 
00574   void SetCapacity (int n)
00575   {
00576     if (n > Length ())
00577       AdjustCapacity (n);
00578   }
00579 
00585   void ShrinkBestFit ()
00586   {
00587     if (count == 0)
00588     {
00589       DeleteAll ();
00590     }
00591     else if (count != capacity)
00592     {
00593       root = MemoryAllocator::Realloc (root, count, capacity, count);
00594       capacity = count;
00595     }
00596   }
00597 
00599   bool DeleteIndex (int n)
00600   {
00601     if (n >= 0 && n < count)
00602     {
00603       int const ncount = count - 1;
00604       int const nmove = ncount - n;
00605       ElementHandler::Destroy (root + n);
00606       if (nmove > 0)
00607         memmove (root + n, root + n + 1, nmove * sizeof(T));
00608       SetLengthUnsafe (ncount);
00609       return true;
00610     }
00611     else
00612       return false;
00613   }
00614 
00619   void DeleteRange (int start, int end)
00620   {
00621     if (start >= count) return;
00622     if (end < 0) return;
00623     if (start < 0) start = 0;
00624     if (end >= count) end = count-1;
00625     int i;
00626     for (i = start ; i < end ; i++)
00627       ElementHandler::Destroy (root + i);
00628 
00629     int const range_size = end-start+1;
00630     int const ncount = count - range_size;
00631     int const nmove = count - end - 1;
00632     if (nmove > 0)
00633       memmove (root + start, root + start + range_size, nmove * sizeof(T));
00634     SetLengthUnsafe (ncount);
00635   }
00636 
00638   bool Delete (T const& item)
00639   {
00640     int const n = Find (item);
00641     if (n >= 0)
00642       return DeleteIndex (n);
00643     return false;
00644   }
00645 
00647   class Iterator
00648   {
00649   public:
00651     Iterator(Iterator const& r) :
00652       currentelem(r.currentelem), array(r.array) {}
00653 
00655     Iterator& operator=(Iterator const& r)
00656     { currentelem = r.currentelem; array = r.array; return *this; }
00657 
00659     bool HasNext()
00660     { return currentelem < array.Length(); }
00661 
00663     const T& Next()
00664     { return array.Get(currentelem++); }
00665 
00667     void Reset()
00668     { currentelem = 0; }
00669   protected:
00670     Iterator(const csArray<T, ElementHandler>& newarray)
00671         : currentelem(0), array(newarray)
00672     { }
00673     friend class csArray<T, ElementHandler>;
00674     
00675   private:
00676     int currentelem;
00677     const csArray<T, ElementHandler>& array;
00678   };
00679 
00681   Iterator GetIterator() const
00682   { return Iterator(*this); }
00683 };
00684 
00690 template <class T>
00691 class csSafeCopyArray
00692         : public csArray<T,
00693                 csArrayElementHandler<T>,
00694                 csSafeCopyArrayMemoryAllocator<T> >
00695 {
00696 public:
00701   csSafeCopyArray (int ilimit = 0, int ithreshold = 0)
00702         : csArray<T, csArrayElementHandler<T>,
00703                      csSafeCopyArrayMemoryAllocator<T> > (ilimit, ithreshold)
00704   {
00705   }
00706 };
00707 
00708 #ifdef CS_EXTENSIVE_MEMDEBUG
00709 # define new CS_EXTENSIVE_MEMDEBUG_NEW
00710 #endif
00711 
00712 #endif

Generated for Crystal Space by doxygen 1.2.18