flower/include/parray.hh

   1 /*
   2   parray.hh -- declare Pointer_array
   3
   4   source file of the Flower Library
   5
   6   (c)  1997--1999 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9
  10 #ifndef PARRAY_HH
  11 #define PARRAY_HH
  12
  13 #include "array.hh"
  14
  15 /**
  16   an array of pointers.
  17
  18   TODO
  19   should init to 0.
  20  */
  21 template<class T>
  22 class Link_array : private Array<void *>
  23 {
  24   static default_compare (T *const& p1, T  *const&p2) {
  25     /* can't do p1 -p2, since T might be an incomplete type */
  26     if (p1 < p2)
  27       return -1 ;
  28     if (p2 < p1)
  29       return 1;
  30     return 0;
  31   }
  32   Link_array (Array<void*> v)
  33     :Array<void*> (v)
  34     {
  35     }
  36 public:
  37   Link_array()
  38     {}
  39
  40   Link_array(T * const *tp, int n)
  41     : Array<void*> ((void **)tp, n)
  42     {
  43     }
  44
  45   Link_array (Link_array<T> const &src)
  46     : Array<void*> (src)
  47     {
  48     }
  49   /// access element
  50   T *elem (int i) const
  51     {
  52       return elem_ref (i);
  53     }
  54   T *&elem_ref  (int i) const
  55     {
  56       return (T*&) Array<void*>::elem_ref (i);
  57     }
  58
  59   /// access element
  60   T* &operator[] (int i)
  61     {
  62       return (T*&) Array<void*>::elem_ref (i);
  63     }
  64   /// access element
  65   T *const operator[] (int i) const
  66     {
  67       return (T *const) Array<void*>::elem (i);
  68     }
  69   T *pop ()
  70     {
  71       return (T*) Array<void*>::pop ();
  72     }
  73   void insert (T *t, int i)
  74     {
  75       Array<void*>::insert (t, i);
  76     }
  77   void push (T* t)
  78     {
  79       Array<void*>::push (t);
  80     }
  81   /// return last entry
  82   T* top (int j=0) const
  83     {
  84       return (T*) Array<void*>::top (j);
  85     }
  86   T *& top (int i=0)
  87     {
  88       return (T*&) Array<void*>::top (i);
  89     }
  90   void substitute (T *old, T*new_l)
  91     {
  92       int i;
  93       while ((i = find_i (old)) >=0)
  94         if (new_l)
  95           elem_ref (i) =new_l;
  96         else
  97           del (i);
  98     }
  99   void unordered_substitute (T* old, T * new_l)
 100     {
 101       int i;
 102       while ((i = find_i (old)) >=0)
 103         if (new_l)
 104           elem_ref (i) =new_l;
 105         else {
 106           unordered_del (i);
 107         }
 108
 109     }
 110   void default_sort() {
 111     sort (default_compare);
 112   }
 113   // quicksort.
 114   void sort (int (*compare)(T *const&,T *const&),
 115              int lower = -1, int upper = -1);
 116
 117   void uniq() {
 118     Link_array<T> l_arr;
 119     for (int i=0; i < size(); i++)
 120       if (!i || elem (i-1) != elem (i))
 121         l_arr.push (elem (i));
 122     *this = l_arr;
 123   }
 124   Array<void*>::del;
 125   Array<void*>::unordered_del;
 126   Array<void*>::size;
 127   Array<void*>::clear;
 128   Array<void*>::set_size;
 129   Array<void*>::empty;
 130   Array<void*>::reverse;
 131   Array<void*>::tighten_maxsize;
 132   T ** access_array () const
 133     {
 134       return (T**) Array<void*>::access_array();
 135     }
 136   T * get (int i)
 137     {
 138       return (T*) Array<void*>::get (i);
 139     }
 140   Link_array<T>
 141   slice(int l,int u)
 142     {
 143       return Array<void*>::slice (l,u);
 144     }
 145   void concat (Link_array<T> const &a2)
 146     {
 147       Array<void*>::concat (a2);
 148     }
 149   int find_i (T const * t) const {
 150     for (int i=0; i < size(); i++)
 151       if (elem (i) == t)
 152         return i;
 153     return -1;
 154   }
 155   T *find_l (T const *t) const
 156     {
 157       int i = find_i (t);
 158       if (i >= 0)
 159         return elem (i);
 160       else
 161         return 0;
 162     }
 163
 164 };
 165
 166 template<class T, class V>
 167 Link_array<T>
 168 typecast_array (Link_array<V> const &a, T * /* dummy */ )
 169 {
 170   Link_array<T> ret;
 171   for (int i=a.size (); i-- ; )
 172         ret.push (dynamic_cast<T*> (a[i]));     // ugh?
 173   return ret;
 174 }
 175
 176
 177
 178 template<class T> inline void
 179 Link_array<T>::sort (int (*compare)(T *const&,T *const&),
 180                 int lower = -1, int upper = -1)
 181 {
 182   if (lower < 0)
 183     {
 184       lower = 0 ;
 185       upper = size () - 1;
 186     }
 187   if (lower >= upper)
 188     return;
 189   swap (lower, (lower+upper)/2);
 190   int last = lower;
 191   for (int i= lower +1; i <= upper; i++)
 192     if (compare (elem (i), elem(lower)) < 0)
 193       swap (++last,i);
 194   swap (lower, last);
 195   sort (compare, lower, last-1);
 196   sort (compare, last+1, upper);
 197 }
 198
 199 template<class T>
 200 void
 201 junk_pointer_array (Link_array<T> &a)
 202 {
 203   for (int i=0; i < a.size ();  i++)
 204     {
 205       delete a[i];
 206     }
 207   a.clear ();
 208 }
 209
 210 #endif // PARRAY_HH
 211