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