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