CrystalSpace

Public API Reference

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

refarr.h

00001 /*
00002   Crystal Space Smart Pointers
00003   Copyright (C) 2002 by Jorrit Tyberghein and Matthias 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 
00020 #ifndef __CS_REFARR_H__
00021 #define __CS_REFARR_H__
00022 
00023 #include "csutil/ref.h"
00024 
00028 template <class T>
00029 class csRefArray
00030 {
00031 private:
00032   int count, limit, threshold;
00033   csRef<T>* root;
00034 
00035 public:
00036   typedef int ArrayCompareFunction (T* item1, T* item2);
00037   typedef int ArrayCompareKeyFunction (T* item, void* key);
00038   
00043   csRefArray (int ilimit = 0, int ithreshold = 0)
00044   {
00045     count = 0;
00046     limit = (ilimit > 0 ? ilimit : 0);
00047     threshold = (ithreshold > 0 ? ithreshold : 16);
00048     if (limit != 0)
00049       root = (csRef<T>*)calloc (limit, sizeof(csRef<T>));
00050     else
00051       root = NULL;
00052   }
00053 
00060   void TransferTo (csRefArray<T>& destination)
00061   {
00062     destination.DeleteAll ();
00063     destination.root = root;
00064     destination.count = count;
00065     destination.limit = limit;
00066     destination.threshold = threshold;
00067     root = NULL;
00068     limit = count = 0;
00069   }
00070 
00074   void DeleteAll ()
00075   {
00076     if (root)
00077     {
00078       int i;
00079       for (i = 0 ; i < limit ; i++)
00080         root[i] = NULL; // Clear ref.
00081       free (root);
00082       root = NULL;
00083       limit = count = 0;
00084     }
00085   }
00086 
00090   ~csRefArray ()
00091   {
00092     DeleteAll ();
00093   }
00094 
00096   void SetLength (int n)
00097   {
00098     // Free all items between new count and old count.
00099     int i;
00100     for (i = n ; i < count ; i++) root[i] = NULL;
00101 
00102     int old_count = count;
00103     count = n;
00104 
00105     if (n > limit || (limit > threshold && n < limit - threshold))
00106     {
00107       n = ((n + threshold - 1) / threshold ) * threshold;
00108       if (!n)
00109       {
00110         DeleteAll ();
00111       }
00112       else if (root == NULL)
00113         root = (csRef<T>*)calloc (n, sizeof(csRef<T>));
00114       else
00115       {
00116         csRef<T>* newroot = (csRef<T>*)calloc (n, sizeof(csRef<T>));
00117         memcpy (newroot, root, old_count * sizeof (csRef<T>));
00118         free (root);
00119         root = newroot;
00120       }
00121       limit = n;
00122     }
00123   }
00124 
00126   int Length () const
00127   {
00128     return count;
00129   }
00130 
00132   int Limit () const
00133   {
00134     return limit;
00135   }
00136 
00138   const csRef<T>& Get (int n) const
00139   {
00140     CS_ASSERT (n >= 0 && n < count);
00141     return root[n];
00142   }
00143 
00145   const csRef<T>& operator [] (int n) const
00146   {
00147     CS_ASSERT (n >= 0 && n < count);
00148     return root[n];
00149   }
00150 
00152   csRef<T>& operator [] (int n)
00153   {
00154     CS_ASSERT (n >= 0);
00155     if (n >= count)
00156       SetLength (n + 1);
00157     return root[n];
00158   }
00159 
00161   int Find (T* which) const
00162   {
00163     int i;
00164     for (i = 0 ; i < Length () ; i++)
00165       if (root[i] == which)
00166         return i;
00167     return -1;
00168   }
00169 
00171   int Push (T* what)
00172   {
00173     SetLength (count + 1);
00174     root [count - 1] = what;
00175     return (count - 1);
00176   }
00177 
00179   int PushSmart (T* what)
00180   {
00181     int n = Find (what);
00182     return (n == -1) ? Push (what) : n;
00183   }
00184 
00186   csPtr<T> Pop ()
00187   {
00188     csRef<T> ret = root [count - 1];
00189     SetLength (count - 1);
00190     return csPtr<T> (ret);
00191   }
00192 
00194   T* Top () const
00195   {
00196     return root [count - 1];
00197   }
00198 
00200   bool Delete (int n)
00201   {
00202     if (n >= 0 && n < count)
00203     {
00204       root[n] = NULL;   // Clear element.
00205       const int ncount = count - 1;
00206       const int nmove = ncount - n;
00207       if (nmove > 0)
00208       {
00209         memmove (&root [n], &root [n + 1], nmove * sizeof (csRef<T>));
00210         // The following manual IncRef() is to make sure that
00211         // the element will not get deleted by the SetLength() below.
00212         if (root[ncount])
00213           root[ncount]->IncRef ();
00214       }
00215       SetLength (ncount);
00216       return true;
00217     }
00218     else
00219       return false;
00220   }
00221 
00223   bool Delete (T* item)
00224   {
00225     int n = Find (item);
00226     if (n == -1) return false;
00227     else return Delete (n);
00228   }
00229 
00231   bool Insert (int n, T* item)
00232   {
00233     if (n <= count)
00234     {
00235       SetLength (count + 1); // Increments 'count' as a side-effect.
00236       const int nmove = (count - n - 1);
00237       if (nmove > 0)
00238       {
00239         memmove (&root [n + 1], &root [n], nmove * sizeof (csRef<T>));
00240         // The following manual IncRef() is to make sure that
00241         // the element will not get deleted later. This element is
00242         // currently (temporarily) duplicated in the root array so
00243         // that's why it needs an additional ref.
00244         if (root[n])
00245           root[n]->IncRef ();
00246       }
00247       root [n] = item;
00248       return true;
00249     }
00250     else
00251      return false;
00252   }
00253 
00257   int FindSortedKey (void* key, ArrayCompareKeyFunction* comparekey) const
00258   {
00259     int l = 0, r = Length () - 1;
00260     while (l <= r)
00261     {
00262       int m = (l + r) / 2;
00263       int cmp = comparekey (root [m], key);
00264 
00265       if (cmp == 0)
00266         return m;
00267       else if (cmp < 0)
00268         l = m + 1;
00269       else
00270         r = m - 1;
00271     }
00272     return -1;
00273   }
00274 
00279   int InsertSorted (T* item, ArrayCompareFunction* compare)
00280   {
00281     int m = 0, l = 0, r = Length () - 1;
00282     while (l <= r)
00283     {
00284       m = (l + r) / 2;
00285       int cmp = compare (root [m], item);
00286 
00287       if (cmp == 0)
00288       {
00289         Insert (++m, item);
00290         return m;
00291       }
00292       else if (cmp < 0)
00293         l = m + 1;
00294       else
00295         r = m - 1;
00296     }
00297     if (r == m)
00298       m++;
00299     Insert (m, item);
00300     return m;
00301   }
00302 
00304   void QuickSort (ArrayCompareFunction* compare)
00305   {
00306     if (count > 0)
00307       QuickSort (0, count - 1, compare);
00308   }
00309   
00311   void QuickSort (int Left, int Right, ArrayCompareFunction* compare)
00312   {
00313   recurse:
00314     int i = Left, j = Right;
00315     int x = (Left + Right) / 2;
00316     do
00317     {
00318       while ((i != x) && (compare (root[i], root[x]) < 0))
00319         i++;
00320       while ((j != x) && (compare (root[j], root[x]) > 0))
00321         j--;
00322       if (i < j)
00323       {
00324         csRef<T> swap;
00325         swap = root[i];
00326         root[i] = root[j];
00327         root[j] = swap;
00328         if (x == i)
00329           x = j;
00330         else if (x == j)
00331           x = i;
00332       }
00333       if (i <= j)
00334       {
00335         i++;
00336         if (j > Left)
00337           j--;
00338       }
00339     } while (i <= j);
00340 
00341     if (j - Left < Right - i)
00342     {
00343       if (Left < j)
00344         QuickSort (Left, j, compare);
00345       if (i < Right)
00346       {
00347         Left = i;
00348         goto recurse;
00349       }
00350     }
00351     else
00352     {
00353       if (i < Right)
00354         QuickSort (i, Right, compare);
00355       if (Left < j)
00356       {
00357         Right = j;
00358         goto recurse;
00359       }
00360     }
00361   }
00362   
00363 };
00364 
00365 #endif // __CS_REFARR_H__
00366 

Generated for Crystal Space by doxygen 1.2.14