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