CrystalSpace

Public API Reference

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

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 
00035 template <class T>
00036 class csArray
00037 {
00038 private:
00039   int count;
00040   int capacity;
00041   int threshold;
00042   T* root;
00043 
00044   void ConstructElement (int n, T const& src)
00045   {
00046     new (static_cast<void*>(root + n)) T(src);
00047   }
00048 
00049   void DestroyElement (int n)
00050   {
00051     (root + n)->T::~T();
00052   }
00053  
00054   // Adjust internal capacity of this array.
00055   void AdjustCapacity (int n)
00056   {
00057     if (n > capacity || (capacity > threshold && n < capacity - threshold))
00058     {
00059       n = ((n + threshold - 1) / threshold ) * threshold;
00060       if (root == 0)
00061         root = (T*)malloc (n * sizeof(T));
00062       else
00063         root = (T*)realloc (root, n * sizeof(T));
00064       capacity = n;
00065     }
00066   }
00067 
00068   // Set array length.  NOTE: Do not make this public since it does not
00069   // properly construct/destroy elements.  To safely truncate the array, use
00070   // Truncate().  To safely set the capacity, use SetCapacity().
00071   void SetLengthUnsafe (int n)
00072   {
00073     if (n > capacity)
00074       AdjustCapacity (n);
00075     count = n;
00076   }
00077 
00078 public:
00083   csArray (int icapacity = 0, int ithreshold = 0)
00084   {
00085     count = 0;
00086     capacity = (icapacity > 0 ? icapacity : 0);
00087     threshold = (ithreshold > 0 ? ithreshold : 16);
00088     if (capacity != 0)
00089       root = (T*)malloc (capacity * sizeof(T));
00090     else
00091       root = 0;
00092   }
00093 
00095   csArray (const csArray& other)
00096   {
00097     count = 0;
00098     capacity = 0;
00099     threshold = other.threshold;
00100     root = 0;
00101     for (int i=0;i<other.Length();i++)
00102       Push (other[i]);
00103   }
00104 
00111   void TransferTo (csArray<T>& destination)
00112   {
00113     destination.DeleteAll ();
00114     destination.root = root;
00115     destination.count = count;
00116     destination.capacity = capacity;
00117     destination.threshold = threshold;
00118     root = NULL;
00119     capacity = count = 0;
00120   }
00121 
00122   csArray<T>& operator = (const csArray& other)
00123   {
00124     if (&other == this)
00125       return *this;
00126 
00127     // simple but not optimal solution here
00128     DeleteAll ();
00129 
00130     for (int i=0;i<other.Length();i++)
00131       Push(other[i]);
00132     return *this;
00133   }
00134 
00136   void DeleteAll ()
00137   {
00138     for (int i = 0; i < count; i++)
00139       DestroyElement (i);
00140     if (root != 0)
00141     {
00142       free (root);
00143       root = 0;
00144       capacity = 0;
00145       count = 0;
00146     }
00147   }
00148 
00154   void Truncate (int n)
00155   {
00156     CS_ASSERT(n >= 0);
00157     CS_ASSERT(n <= count);
00158     if (n < count)
00159     {
00160       for (int i = n; i < count; i++)
00161         DestroyElement(i);
00162       SetLengthUnsafe(n);
00163     }
00164   }
00165 
00173   void SetLength (int n, T const& what)
00174   {
00175     if (n <= count)
00176     {
00177       Truncate (n);
00178     }
00179     else
00180     {
00181       int old_len = Length ();
00182       SetLengthUnsafe (n);
00183       for (int i = old_len ; i < n ; i++)
00184         ConstructElement (i, what);
00185     }
00186   }
00187 
00193   void Empty()
00194   { Truncate(0); }
00195 
00196 
00198   ~csArray ()
00199   {
00200     DeleteAll ();
00201   }
00202 
00204   int Length () const
00205   {
00206     return count;
00207   }
00208 
00210   int Capacity () const
00211   {
00212     return capacity;
00213   }
00214 
00221   void SetCapacity (int n)
00222   {
00223     if (n > Length ())
00224       AdjustCapacity (n);
00225   }
00226 
00232   void ShrinkBestFit ()
00233   {
00234     if (count == 0)
00235     {
00236       DeleteAll ();
00237     }
00238     else if (count != capacity)
00239     {
00240       capacity = count;
00241       root = (T*)realloc (root, capacity * sizeof(T));
00242     }
00243   }
00244 
00246   T const& Get (int n) const
00247   {
00248     CS_ASSERT (n >= 0 && n < count);
00249     return root[n];
00250   }
00251 
00253   T& Get (int n)
00254   {
00255     CS_ASSERT (n >= 0 && n < count);
00256     return root[n];
00257   }
00258 
00260   T const& operator [] (int n) const
00261   {
00262     return Get(n);
00263   }
00264 
00266   T& operator [] (int n)
00267   {
00268     return Get(n);
00269   }
00270 
00272   int Find (T const& which) const
00273   {
00274     for (int i = 0, n = Length(); i < n; i++)
00275       if (root[i] == which)
00276         return i;
00277     return -1;
00278   }
00279 
00281   int Push (T const& what)
00282   {
00283     SetLengthUnsafe (count + 1);
00284     ConstructElement (count - 1, what);
00285     return (count - 1);
00286   }
00287 
00288   /*
00289    * Push a element onto the tail end of the array if not already present.
00290    * Returns index of newly pushed element or index of already present element.
00291    */
00292   int PushSmart (T const& what)
00293   {
00294     int const n = Find (what);
00295     return (n < 0) ? Push (what) : n;
00296   }
00297 
00299   T Pop ()
00300   {
00301     CS_ASSERT (count > 0);
00302     T ret(root [count - 1]);
00303     DestroyElement (count - 1);
00304     SetLengthUnsafe (count - 1);
00305     return ret;
00306   }
00307 
00309   T const& Top () const
00310   {
00311     CS_ASSERT (count > 0);
00312     return root [count - 1];
00313   }
00314 
00316   bool DeleteIndex (int n)
00317   {
00318     if (n >= 0 && n < count)
00319     {
00320       int const ncount = count - 1;
00321       int const nmove = ncount - n;
00322       DestroyElement (n);
00323       if (nmove > 0)
00324         memmove (root + n, root + n + 1, nmove * sizeof(T));
00325       SetLengthUnsafe (ncount);
00326       return true;
00327     }
00328     else
00329       return false;
00330   }
00331 
00336   void DeleteRange (int start, int end)
00337   {
00338     if (start >= count) return;
00339     if (end < 0) return;
00340     if (start < 0) start = 0;
00341     if (end >= count) end = count-1;
00342     int i;
00343     for (i = start ; i < end ; i++)
00344       DestroyElement (i);
00345 
00346     int const range_size = end-start+1;
00347     int const ncount = count - range_size;
00348     int const nmove = count - end - 1;
00349     if (nmove > 0)
00350       memmove (root + start, root + start + range_size, nmove * sizeof(T));
00351     SetLengthUnsafe (ncount);
00352   }
00353 
00355   bool Delete (T const& item)
00356   {
00357     int const n = Find (item);
00358     if (n >= 0)
00359       return DeleteIndex (n);
00360     return false;
00361   }
00362 
00364   bool Insert (int n, T const& item)
00365   {
00366     if (n <= count)
00367     {
00368       SetLengthUnsafe (count + 1); // Increments 'count' as a side-effect.
00369       int const nmove = (count - n - 1);
00370       if (nmove > 0)
00371         memmove (root + n + 1, root + n, nmove * sizeof(T));
00372       ConstructElement (n, item);
00373       return true;
00374     }
00375     else
00376       return false;
00377   }
00378 };
00379 
00380 #ifdef CS_EXTENSIVE_MEMDEBUG
00381 # define new CS_EXTENSIVE_MEMDEBUG_NEW
00382 #endif
00383 
00384 #endif

Generated for Crystal Space by doxygen 1.2.14