flower/include/parray.hh

   1 /*
   2   parray.hh -- declare Pointer_array
   3
   4   source file of the Flower Library
   5
   6   (c) 1997--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9 #ifndef PARRAY_HH
  10 #define PARRAY_HH
  11
  12 #include "array.hh"
  13
  14 /**
  15    an array of pointers.
  16
  17    TODO
  18    should init to 0.
  19 */
  20 template<class T>
  21 class Link_array : private Array<void *>
  22 {
  23
  24   Link_array (Array<void *> v)
  25     :Array<void *> (v)
  26   {
  27   }
  28 public:
  29   Link_array ()
  30   {}
  31
  32   static int default_compare (T *const &p1, T *const &p2)
  33   {
  34     /* can't do p1 -p2, since T might be an incomplete type */
  35     if (p1 < p2)
  36       return -1;
  37     if (p2 < p1)
  38       return 1;
  39     return 0;
  40   }
  41   Link_array (T *const *tp, int n)
  42     : Array<void *> ((void **)tp, n)
  43   {
  44   }
  45
  46   Link_array (Link_array<T> const &src)
  47     : Array<void *> (src)
  48   {
  49   }
  50   /// access element
  51   T *elem (int i) const
  52   {
  53     return elem_ref (i);
  54   }
  55   T *&elem_ref (int i) const
  56   {
  57     return (T *&) Array<void *>::elem_ref (i);
  58   }
  59
  60   /// access element
  61   T *&operator [] (int i)
  62   {
  63     return (T *&) Array<void *>::elem_ref (i);
  64   }
  65   /// access element
  66   T *const operator [] (int i) const
  67   {
  68     return (T *const) Array<void *>::elem (i);
  69   }
  70   T *pop ()
  71   {
  72     return (T *) Array<void *>::pop ();
  73   }
  74   void insert (T *t, int i)
  75   {
  76     Array<void *>::insert (t, i);
  77   }
  78   void push (T *t)
  79   {
  80     Array<void *>::push (t);
  81   }
  82   /// return last entry
  83   T *top (int j = 0) const
  84   {
  85     return (T *) Array<void *>::top (j);
  86   }
  87   T *& top (int i = 0)
  88   {
  89     return (T *&) Array<void *>::top (i);
  90   }
  91   void substitute (T *old, T *new_p)
  92   {
  93     int i;
  94     while ((i = find_index (old)) >= 0)
  95       if (new_p)
  96         elem_ref (i) = new_p;
  97       else
  98         del (i);
  99   }
 100   void unordered_substitute (T *old, T *new_p)
 101   {
 102     int i;
 103     while ((i = find_index (old)) >= 0)
 104       if (new_p)
 105         elem_ref (i) = new_p;
 106       else
 107         {
 108           unordered_del (i);
 109         }
 110   }
 111   void default_sort ()
 112   {
 113     sort (default_compare);
 114   }
 115   // quicksort.
 116   void sort (int (*compare) (T *const &, T *const &),
 117              int lower = -1, int upper = -1);
 118
 119   void uniq ()
 120   {
 121     Link_array<T> ls;
 122     for (int i = 0; i < size (); i++)
 123       if (!i || elem (i - 1) != elem (i))
 124         ls.push (elem (i));
 125     *this = ls;
 126   }
 127   Array<void *>::del;
 128   Array<void *>::unordered_del;
 129   Array<void *>::size;
 130   Array<void *>::clear;
 131   Array<void *>::set_size;
 132   Array<void *>::is_empty;
 133   Array<void *>::reverse;
 134   Array<void *>::tighten_maxsize;
 135
 136   T *& boundary (int d, int i)
 137   {
 138     assert (d);
 139     if (d == 1)
 140       return top (i);
 141     else
 142       return elem_ref (i);
 143   }
 144   T *boundary (int d, int i)const
 145   {
 146     assert (d);
 147     if (d == 1)
 148       return top (i);
 149     else
 150       return elem_ref (i);
 151   }
 152
 153   T ** accesses () const
 154   {
 155     return (T **) Array<void *>::accesses ();
 156   }
 157   T *get (int i)
 158   {
 159     return (T *) Array<void *>::get (i);
 160   }
 161   Link_array<T>
 162   slice (int l, int u) const
 163   {
 164     return Array<void *>::slice (l, u);
 165   }
 166   void concat (Link_array<T> const &a2)
 167   {
 168     Array<void *>::concat (a2);
 169   }
 170   int find_index (T const *t) const
 171   {
 172     for (int i = 0; i < size (); i++)
 173       if (elem (i) == t)
 174         return i;
 175     return -1;
 176   }
 177   T *find (T const *t) const
 178   {
 179     int i = find_index (t);
 180     if (i >= 0)
 181       return elem (i);
 182     else
 183       return 0;
 184   }
 185 };
 186
 187 template<class T, class V>
 188 Link_array<T>
 189 typecasts (Link_array<V> const &a, T * /* dummy */)
 190 {
 191   Link_array<T> ret;
 192   for (int i = a.size (); i--;)
 193     ret.push (dynamic_cast<T *> (a[i]));        // ugh?
 194   return ret;
 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_pointers (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   lookup with binsearch, return tokencode.
 230 */
 231 template<class T>
 232 int
 233 binsearch (Array<T> const &arr, T t, int (*compare) (T const &, T const &))
 234 {
 235   int lo;
 236   int hi;
 237   int cmp;
 238   int result;
 239   lo = 0;
 240   hi = Array<T>::maxkey;
 241
 242   /* binary search */
 243   do
 244     {
 245       cmp = (lo + hi) / 2;
 246
 247       result = compare (t, arr[cmp]);
 248
 249       if (result < 0)
 250         hi = cmp;
 251       else
 252         lo = cmp;
 253     }
 254   while (hi - lo > 1);
 255
 256   if (!compare (t, arr[lo]))
 257     return lo;
 258   else
 259     return -1;              /* not found */
 260 }
 261
 262 template<class T>
 263 int
 264 binsearch_links (Link_array<T> const &arr, T *t,
 265                  int (*compare) (T *const &, T *const &),
 266                  int lo = 0, int hi = -1)
 267 {
 268   int cmp;
 269   int result;
 270   if (hi < 0)
 271     hi = arr.size ();
 272
 273   if (hi == 0)
 274     return -1;
 275
 276   /* binary search */
 277   do
 278     {
 279       cmp = (lo + hi) / 2;
 280
 281       result = (*compare) (t, arr[cmp]);
 282
 283       if (result < 0)
 284         hi = cmp;
 285       else
 286         lo = cmp;
 287     }
 288   while (hi - lo > 1);
 289
 290   if (!compare (t, arr[lo]))
 291     return lo;
 292   else
 293     return -1;              /* not found */
 294 }
 295
 296 template<class T>
 297 void
 298 binary_search_bounds (Link_array<T> const &table,
 299                       T const *key, int (*compare) (T *const &, T *const &),
 300                       int *lo,
 301                       int *hi)
 302 {
 303   int cmp;
 304   int result;
 305
 306   /* binary search */
 307   do
 308     {
 309       cmp = (*lo + *hi) / 2;
 310
 311       result = (*compare) ((T *) key, table[cmp]);
 312
 313       if (result < 0)
 314         *hi = cmp;
 315       else
 316         *lo = cmp;
 317     }
 318   while (*hi - *lo > 1);
 319 }
 320
 321 #endif // PARRAY_HH
 322