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