flower/include/parray.hh

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