flower/include/parray.hh

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