CrystalSpace

Public API Reference

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

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 
00032 template <class T>
00033 class csArrayElementHandler
00034 {
00035 public:
00036   static void Construct (T* address, T const& src)
00037   {
00038     new (static_cast<void*>(address)) T(src);
00039   }
00040 
00041   static void Destroy (T* address)
00042   {
00043     address->T::~T();
00044   }
00045 
00046   static void InitRegion (T* address, int count)
00047   {
00048     for (int i = 0 ; i < count ; i++)
00049       Construct (address + i, T ());
00050   }
00051 };
00052 
00060 template <class T, class ElementHandler = csArrayElementHandler<T> >
00061 class csArray
00062 {
00063 private:
00064   int count;
00065   int capacity;
00066   int threshold;
00067   T* root;
00068 
00069 protected:
00074   void InitRegion (int start, int count)
00075   {
00076     ElementHandler::InitRegion (root+start, count);
00077   }
00078 
00079 private:
00081   void CopyFrom (const csArray& source)
00082   {
00083     if (&source != this)
00084     {
00085       DeleteAll ();
00086       threshold = source.threshold;
00087       SetLengthUnsafe (source.Length ());
00088       for (int i=0 ; i<source.Length() ; i++)
00089         ElementHandler::Construct (root + i, source[i]);
00090     }
00091   }
00092 
00093   // Adjust internal capacity of this array.
00094   void AdjustCapacity (int n)
00095   {
00096     if (n > capacity || (capacity > threshold && n < capacity - threshold))
00097     {
00098       n = ((n + threshold - 1) / threshold ) * threshold;
00099       capacity = n;
00100       if (root == 0)
00101         root = (T*)malloc (capacity * sizeof(T));
00102       else
00103         root = (T*)realloc (root, capacity * sizeof(T));
00104     }
00105   }
00106 
00107   // Set array length.  NOTE: Do not make this public since it does not
00108   // properly construct/destroy elements.  To safely truncate the array, use
00109   // Truncate().  To safely set the capacity, use SetCapacity().
00110   void SetLengthUnsafe (int n)
00111   {
00112     if (n > capacity)
00113       AdjustCapacity (n);
00114     count = n;
00115   }
00116 
00117 public:
00119   typedef int ArrayCompareFunction (T const& item1, T const& item2);
00121   typedef int ArrayCompareKeyFunction (T const& item1, void* item2);
00122 
00127   csArray (int icapacity = 0, int ithreshold = 0)
00128   {
00129     count = 0;
00130     capacity = (icapacity > 0 ? icapacity : 0);
00131     threshold = (ithreshold > 0 ? ithreshold : 16);
00132     if (capacity != 0)
00133       root = (T*)malloc (capacity * sizeof(T));
00134     else
00135       root = 0;
00136   }
00137 
00138   ~csArray ()
00139   {
00140     DeleteAll ();
00141   }
00142 
00144   csArray (const csArray& source)
00145   {
00146     root = 0;
00147     capacity = 0;
00148     count = 0;
00149     CopyFrom (source);
00150   }
00151   
00153   csArray<T>& operator= (const csArray& other)
00154   {
00155     CopyFrom (other);
00156     return *this;
00157   }
00158 
00160   int Length () const
00161   {
00162     return count;
00163   }
00164 
00166   int Capacity () const
00167   {
00168     return capacity;
00169   }
00170 
00177   void TransferTo (csArray& destination)
00178   {
00179     if (&destination != this)
00180     {
00181       destination.DeleteAll ();
00182       destination.root = root;
00183       destination.count = count;
00184       destination.capacity = capacity;
00185       destination.threshold = threshold;
00186       root = 0;
00187       capacity = count = 0;
00188     }
00189   }
00190 
00198   void SetLength (int n, T const& what)
00199   {
00200     if (n <= count)
00201     {
00202       Truncate (n);
00203     }
00204     else
00205     {
00206       int old_len = Length ();
00207       SetLengthUnsafe (n);
00208       for (int i = old_len ; i < n ; i++)
00209         ElementHandler::Construct (root + i, what);
00210     }
00211   }
00212 
00214   void SetLength (int n)
00215   {
00216     if (n <= count)
00217     {
00218       Truncate (n);
00219     }
00220     else
00221     {
00222       int old_len = Length ();
00223       SetLengthUnsafe (n);
00224       ElementHandler::InitRegion (root + old_len, n-old_len);
00225     }
00226   }
00227 
00229   T& Get (int n)
00230   {
00231     CS_ASSERT (n >= 0 && n < count);
00232     return root[n];
00233   }
00234 
00239   T& GetExtend (int n)
00240   {
00241     CS_ASSERT (n >= 0);
00242     if (n >= count)
00243       SetLength (n+1);
00244     return root[n];
00245   }
00246 
00248   T& operator [] (int n)
00249   {
00250     return Get(n);
00251   }
00252 
00254   void Put (int n, T const& what)
00255   {
00256     CS_ASSERT (n >= 0);
00257     if (n >= count)
00258       SetLength (n+1);
00259     ElementHandler::Destroy (root + n);
00260     ElementHandler::Construct (root + n, what);
00261   }
00262 
00266   int FindKey (void* key, ArrayCompareKeyFunction* comparekey) const
00267   {
00268     for (int i = 0 ; i < Length () ; i++)
00269       if (comparekey (root[i], key) == 0)
00270         return i;
00271     return -1;
00272   }
00273 
00274 
00276   int Push (T const& what)
00277   {
00278     SetLengthUnsafe (count + 1);
00279     ElementHandler::Construct (root + count - 1, what);
00280     return count - 1;
00281   }
00282 
00283   /*
00284    * Push a element onto the tail end of the array if not already present.
00285    * Returns index of newly pushed element or index of already present element.
00286    */
00287   int PushSmart (T const& what)
00288   {
00289     int const n = Find (what);
00290     return (n < 0) ? Push (what) : n;
00291   }
00292 
00294   T Pop ()
00295   {
00296     CS_ASSERT (count > 0);
00297     T ret(root [count - 1]);
00298     ElementHandler::Destroy (root + count - 1);
00299     SetLengthUnsafe (count - 1);
00300     return ret;
00301   }
00302 
00304   T const& Top () const
00305   {
00306     CS_ASSERT (count > 0);
00307     return root [count - 1];
00308   }
00309 
00311   bool Insert (int n, T const& item)
00312   {
00313     if (n <= count)
00314     {
00315       SetLengthUnsafe (count + 1); // Increments 'count' as a side-effect.
00316       int const nmove = (count - n - 1);
00317       if (nmove > 0)
00318         memmove (root + n + 1, root + n, nmove * sizeof(T));
00319       ElementHandler::Construct (root + n, item);
00320       return true;
00321     }
00322     else
00323       return false;
00324   }
00325 
00329   csArray<T> Section (int low, int high) const
00330   {
00331     CS_ASSERT (low >= 0 && high < count && high >= low);
00332     csArray<T> sect (high - low + 1);
00333     for (int i = low; i <= high; i++) sect.Push (root[i]);
00334     return sect;
00335   }
00336 
00338   static int DefaultCompare (T const &item1, T const &item2)
00339   {
00340     if (item1 < item2) return -1;
00341     else if (item1 > item2) return 1;
00342     else return 0;
00343   }
00344 
00346   static int DefaultCompareKey (T const &item1, void* p)
00347   {
00348     T const& item2 = *(T const*)p;
00349     if (item1 < item2) return -1;
00350     else if (item1 > item2) return 1;
00351     else return 0;
00352   }
00353 
00358   int FindSortedKey (void* key, ArrayCompareKeyFunction* comparekey
00359     = DefaultCompareKey, int* candidate = 0) const
00360   {
00361     int m = 0, l = 0, r = Length () - 1;
00362     while (l <= r)
00363     {
00364       m = (l + r) / 2;
00365       int cmp = comparekey (root [m], key);
00366 
00367       if (cmp == 0)
00368       {
00369         if (candidate) *candidate = -1;
00370         return m;
00371       }
00372       else if (cmp < 0)
00373         l = m + 1;
00374       else
00375         r = m - 1;
00376     }
00377     if (candidate) *candidate = m;
00378     return -1;
00379   }
00380 
00385   int InsertSorted (const T &item, ArrayCompareFunction* compare
00386     = DefaultCompare, int* equal_index = 0)
00387   {
00388     int m = 0, l = 0, r = Length () - 1;
00389     while (l <= r)
00390     {
00391       m = (l + r) / 2;
00392       int cmp = compare (root [m], item);
00393 
00394       if (cmp == 0)
00395       {
00396         if (equal_index) *equal_index = m;
00397         Insert (++m, item);
00398         return m;
00399       }
00400       else if (cmp < 0)
00401         l = m + 1;
00402       else
00403         r = m - 1;
00404     }
00405     if (r == m)
00406       m++;
00407     if (equal_index) *equal_index = -1;
00408     Insert (m, item);
00409     return m;
00410   }
00411 
00413   int Find (T const& which) const
00414   {
00415     for (int i = 0 ; i < Length () ; i++)
00416       if (root[i] == which)
00417         return i;
00418     return -1;
00419   }
00420 
00424   void Sort (ArraySortCompareFunction* compare)
00425   {
00426     qsort (root, Length (), sizeof (T), compare);
00427   }
00428 
00430   T const& Get (int n) const
00431   {
00432     CS_ASSERT (n >= 0 && n < count);
00433     return root[n];
00434   }
00435 
00437   T const& operator [] (int n) const
00438   {
00439     CS_ASSERT (n >= 0 && n < count);
00440     return root[n];
00441   }
00442 
00446   void DeleteAll ()
00447   {
00448     if (root)
00449     {
00450       int i;
00451       for (i = 0 ; i < count ; i++)
00452         ElementHandler::Destroy (root + i);
00453       free (root);
00454       root = 0;
00455       capacity = count = 0;
00456     }
00457   }
00458 
00464   void Truncate (int n)
00465   {
00466     CS_ASSERT(n >= 0);
00467     CS_ASSERT(n <= count);
00468     if (n < count)
00469     {
00470       for (int i = n; i < count; i++)
00471         ElementHandler::Destroy (root + i);
00472       SetLengthUnsafe(n);
00473     }
00474   }
00475 
00481   void Empty ()
00482   {
00483     Truncate (0);
00484   }
00485 
00492   void SetCapacity (int n)
00493   {
00494     if (n > Length ())
00495       AdjustCapacity (n);
00496   }
00497 
00503   void ShrinkBestFit ()
00504   {
00505     if (count == 0)
00506     {
00507       DeleteAll ();
00508     }
00509     else if (count != capacity)
00510     {
00511       capacity = count;
00512       root = (T*)realloc (root, capacity * sizeof(T));
00513     }
00514   }
00515 
00517   bool DeleteIndex (int n)
00518   {
00519     if (n >= 0 && n < count)
00520     {
00521       int const ncount = count - 1;
00522       int const nmove = ncount - n;
00523       ElementHandler::Destroy (root + n);
00524       if (nmove > 0)
00525         memmove (root + n, root + n + 1, nmove * sizeof(T));
00526       SetLengthUnsafe (ncount);
00527       return true;
00528     }
00529     else
00530       return false;
00531   }
00532 
00537   void DeleteRange (int start, int end)
00538   {
00539     if (start >= count) return;
00540     if (end < 0) return;
00541     if (start < 0) start = 0;
00542     if (end >= count) end = count-1;
00543     int i;
00544     for (i = start ; i < end ; i++)
00545       ElementHandler::Destroy (root + i);
00546 
00547     int const range_size = end-start+1;
00548     int const ncount = count - range_size;
00549     int const nmove = count - end - 1;
00550     if (nmove > 0)
00551       memmove (root + start, root + start + range_size, nmove * sizeof(T));
00552     SetLengthUnsafe (ncount);
00553   }
00554 
00556   bool Delete (T const& item)
00557   {
00558     int const n = Find (item);
00559     if (n >= 0)
00560       return DeleteIndex (n);
00561     return false;
00562   }
00563 
00565   class Iterator
00566   {
00567   public:
00569     bool HasNext()
00570     { return currentelem < array.Length(); }
00571 
00573     const T& Next()
00574     { return array.Get(currentelem++); }
00575 
00577     void Reset()
00578     { currentelem = 0; }
00579   protected:
00580     Iterator(const csArray<T, ElementHandler>& newarray)
00581         : currentelem(0), array(newarray)
00582     { }
00583     friend class csArray<T, ElementHandler>;
00584     
00585   private:
00586     int currentelem;
00587     const csArray<T, ElementHandler>& array;
00588   };
00589 
00591   Iterator GetIterator() const
00592   { return Iterator(*this); }
00593 };
00594 
00595 #ifdef CS_EXTENSIVE_MEMDEBUG
00596 # define new CS_EXTENSIVE_MEMDEBUG_NEW
00597 #endif
00598 
00599 #endif

Generated for Crystal Space by doxygen 1.2.14