flower/include/parray.hh

   1 /*
   2   parray.hh -- declare Pointer_array
   3
   4   source file of the Flower Library
   5
   6   (c)  1997--2000 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 int 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
 133   T *& boundary (int d, int i)
 134   {
 135     assert (d);
 136     if (d == 1)
 137       return top (i);
 138     else
 139       return elem_ref (i);
 140   }
 141   T * boundary (int d, int i)const
 142   {
 143     assert (d);
 144     if (d == 1)
 145       return top (i);
 146     else
 147       return elem_ref (i);
 148   }
 149
 150
 151   T ** access_array () const
 152     {
 153       return (T**) Array<void*>::access_array ();
 154     }
 155   T * get (int i)
 156     {
 157       return (T*) Array<void*>::get (i);
 158     }
 159   Link_array<T>
 160   slice (int l,int u)
 161     {
 162       return Array<void*>::slice (l,u);
 163     }
 164   void concat (Link_array<T> const &a2)
 165     {
 166       Array<void*>::concat (a2);
 167     }
 168   int find_i (T const * t) const {
 169     for (int i=0; i < size (); i++)
 170       if (elem (i) == t)
 171         return i;
 172     return -1;
 173   }
 174   T *find_l (T const *t) const
 175     {
 176       int i = find_i (t);
 177       if (i >= 0)
 178         return elem (i);
 179       else
 180         return 0;
 181     }
 182
 183 };
 184
 185 template<class T, class V>
 186 Link_array<T>
 187 typecast_array (Link_array<V> const &a, T * /* dummy */ )
 188 {
 189   Link_array<T> ret;
 190   for (int i=a.size (); i-- ; )
 191         ret.push (dynamic_cast<T*> (a[i]));     // ugh?
 192   return ret;
 193 }
 194
 195
 196
 197 template<class T> inline void
 198 Link_array<T>::sort (int (*compare)(T *const&,T *const&), int lower, int upper)
 199 {
 200   if (lower < 0)
 201     {
 202       lower = 0 ;
 203       upper = size () - 1;
 204     }
 205   if (lower >= upper)
 206     return;
 207   swap (lower, (lower+upper)/2);
 208   int last = lower;
 209   for (int i= lower +1; i <= upper; i++)
 210     if (compare (elem (i), elem (lower)) < 0)
 211       swap (++last,i);
 212   swap (lower, last);
 213   sort (compare, lower, last-1);
 214   sort (compare, last+1, upper);
 215 }
 216
 217 template<class T>
 218 void
 219 junk_pointer_array (Link_array<T> &a)
 220 {
 221   for (int i=0; i < a.size ();  i++)
 222     {
 223       delete a[i];
 224     }
 225   a.clear ();
 226 }
 227
 228
 229
 230 /*
 231   lookup with binsearch, return tokencode.
 232 */
 233 template<class T>
 234 int
 235 binsearch_array (Array<T> const &arr, T t, int (*compare) (T const&,T const&))
 236 {
 237   int lo;
 238   int hi;
 239   int cmp;
 240   int result;
 241   lo = 0;
 242   hi = maxkey;
 243
 244   /* binary search */
 245   do
 246   {
 247       cmp = (lo + hi) / 2;
 248
 249       result = compare (t, arr[cmp]);
 250
 251       if (result < 0)
 252           hi = cmp;
 253       else
 254           lo = cmp;
 255     }
 256   while (hi - lo > 1);
 257   if (!compare (t, arr[lo]))
 258     return lo;
 259   else
 260     return -1;              /* not found */
 261 }
 262
 263
 264 template<class T>
 265 int
 266 binsearch_link_array (Link_array<T> const &arr, T *t,
 267                       int (*compare) (T *const&,T *const&),
 268                       int lo = 0, int hi = -1 )
 269 {
 270   int cmp;
 271   int result;
 272   if (hi< 0)
 273     hi = arr.size ();
 274
 275   if (hi == 0)
 276     return -1;
 277
 278   /* binary search */
 279   do
 280   {
 281       cmp = (lo + hi) / 2;
 282
 283       result = compare (t, arr[cmp]);
 284
 285       if (result < 0)
 286           hi = cmp;
 287       else
 288           lo = cmp;
 289     }
 290   while (hi - lo > 1);
 291   if (!compare (t, arr[lo]))
 292     return lo;
 293   else
 294     return -1;              /* not found */
 295 }
 296
 297
 298 #endif // PARRAY_HH
 299