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@xs4all.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         unordered_del (i);
 108   }
 109   void default_sort ()
 110   {
 111     sort (default_compare);
 112   }
 113   // quicksort.
 114   void sort (int (*compare) (T *const &, T *const &),
 115              int lower = -1, int upper = -1);
 116
 117   void uniq ()
 118   {
 119     Link_array<T> ls;
 120     for (int i = 0; i < size (); i++)
 121       if (!i || elem (i - 1) != elem (i))
 122         ls.push (elem (i));
 123     *this = ls;
 124   }
 125   Array<void *>::del;
 126   Array<void *>::unordered_del;
 127   Array<void *>::size;
 128   Array<void *>::clear;
 129   Array<void *>::set_size;
 130   Array<void *>::is_empty;
 131   Array<void *>::reverse;
 132   Array<void *>::tighten_maxsize;
 133
 134   T *& boundary (int d, int i)
 135   {
 136     assert (d);
 137     if (d == 1)
 138       return top (i);
 139     else
 140       return elem_ref (i);
 141   }
 142   T *boundary (int d, int i)const
 143   {
 144     assert (d);
 145     if (d == 1)
 146       return top (i);
 147     else
 148       return elem_ref (i);
 149   }
 150
 151   T ** accesses () const
 152   {
 153     return (T **) Array<void *>::accesses ();
 154   }
 155   T *get (int i)
 156   {
 157     return (T *) Array<void *>::get (i);
 158   }
 159   Link_array<T>
 160   slice (int l, int u) const
 161   {
 162     return Array<void *>::slice (l, u);
 163   }
 164   void concat (Link_array<T> const &a2)
 165   {
 166     Array<void *>::concat (a2);
 167   }
 168   int find_index (T const *t) const
 169   {
 170     for (int i = 0; i < size (); i++)
 171       if (elem (i) == t)
 172         return i;
 173     return -1;
 174   }
 175   T *find (T const *t) const
 176   {
 177     int i = find_index (t);
 178     if (i >= 0)
 179       return elem (i);
 180     else
 181       return 0;
 182   }
 183 };
 184
 185 template<class T, class V>
 186 Link_array<T>
 187 typecasts (Link_array<V> const &a, T * /* dummy */)
 188 {
 189   Link_array<T> ret;
 190   for (int i = a.size (); i--;)
 191     ret.push (dynamic_cast<T *> (a[i]));        // ugh?
 192   return ret;
 193 }
 194
 195 template<class T> inline void
 196 Link_array<T>::sort (int (*compare) (T *const &, T *const &), int lower, int upper)
 197 {
 198   if (lower < 0)
 199     {
 200       lower = 0;
 201       upper = size () - 1;
 202     }
 203   if (lower >= upper)
 204     return;
 205   swap (lower, (lower + upper) / 2);
 206   int last = lower;
 207   for (int i = lower +1; i <= upper; i++)
 208     if (compare (elem (i), elem (lower)) < 0)
 209       swap (++last, i);
 210   swap (lower, last);
 211   sort (compare, lower, last - 1);
 212   sort (compare, last + 1, upper);
 213 }
 214
 215 template<class T>
 216 void
 217 junk_pointers (Link_array<T> &a)
 218 {
 219   for (int i = 0; i < a.size (); i++)
 220     delete a[i];
 221   a.clear ();
 222 }
 223
 224 /*
 225   lookup with binsearch, return tokencode.
 226 */
 227 template<class T>
 228 int
 229 binsearch (Array<T> const &arr, T t, int (*compare) (T const &, T const &))
 230 {
 231   int cmp;
 232   int result;
 233   int lo = 0;
 234   int hi = arr.size ();
 235
 236   /* binary search */
 237   do
 238     {
 239       cmp = (lo + hi) / 2;
 240
 241       result = compare (t, arr[cmp]);
 242
 243       if (result < 0)
 244         hi = cmp;
 245       else
 246         lo = cmp;
 247     }
 248   while (hi - lo > 1);
 249
 250   if (!compare (t, arr[lo]))
 251     return lo;
 252   else
 253     return -1;              /* not found */
 254 }
 255
 256 template<class T>
 257 int
 258 binsearch_links (Link_array<T> const &arr, T *t,
 259                  int (*compare) (T *const &, T *const &))
 260 {
 261   int cmp;
 262   int result;
 263   int lo = 0;
 264   int hi = arr.size ();
 265
 266   if (hi == 0)
 267     return -1;
 268
 269   /* binary search */
 270   do
 271     {
 272       cmp = (lo + hi) / 2;
 273
 274       result = (*compare) (t, arr[cmp]);
 275
 276       if (result < 0)
 277         hi = cmp;
 278       else
 279         lo = cmp;
 280     }
 281   while (hi - lo > 1);
 282
 283   if (!compare (t, arr[lo]))
 284     return lo;
 285   else
 286     return -1;              /* not found */
 287 }
 288
 289 template<class T>
 290 void
 291 binary_search_bounds (Link_array<T> const &table,
 292                       T const *key, int (*compare) (T *const &, T *const &),
 293                       int *lo,
 294                       int *hi)
 295 {
 296   int cmp;
 297   int result;
 298
 299   /* binary search */
 300   do
 301     {
 302       cmp = (*lo + *hi) / 2;
 303
 304       result = (*compare) ((T *) key, table[cmp]);
 305
 306       if (result < 0)
 307         *hi = cmp;
 308       else
 309         *lo = cmp;
 310     }
 311   while (*hi - *lo > 1);
 312 }
 313
 314 #endif // PARRAY_HH
 315