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