flower/include/parray.hh

   1 /*
   2   parray.hh -- declare Pointer_array
   3
   4   source file of the Flower Library
   5
   6   (c) 1997--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9
  10 #ifndef PARRAY_HH
  11 #define PARRAY_HH
  12
  13 #include "array.hh"
  14
  15
  16
  17 /**
  18   an array of pointers.
  19
  20   TODO
  21   should init to 0.
  22  */
  23 template<class T>
  24 class Link_array : private Array<void *>
  25 {
  26
  27   Link_array (Array<void*> v)
  28     :Array<void*> (v)
  29     {
  30     }
  31 public:
  32   Link_array ()
  33     {}
  34
  35   static int default_compare (T *const& p1, T  *const&p2)
  36   {
  37     /* can't do p1 -p2, since T might be an incomplete type */
  38     if (p1 < p2)
  39       return -1 ;
  40     if (p2 < p1)
  41       return 1;
  42     return 0;
  43   }
  44   Link_array (T * const *tp, int n)
  45     : Array<void*> ((void **)tp, n)
  46     {
  47     }
  48
  49   Link_array (Link_array<T> const &src)
  50     : Array<void*> (src)
  51     {
  52     }
  53   /// access element
  54   T *elem (int i) const
  55     {
  56       return elem_ref (i);
  57     }
  58   T *&elem_ref (int i) const
  59     {
  60       return (T*&) Array<void*>::elem_ref (i);
  61     }
  62
  63   /// access element
  64   T* &operator[] (int i)
  65     {
  66       return (T*&) Array<void*>::elem_ref (i);
  67     }
  68   /// access element
  69   T *const operator[] (int i) const
  70     {
  71       return (T *const) Array<void*>::elem (i);
  72     }
  73   T *pop ()
  74     {
  75       return (T*) Array<void*>::pop ();
  76     }
  77   void insert (T *t, int i)
  78     {
  79       Array<void*>::insert (t, i);
  80     }
  81   void push (T* t)
  82     {
  83       Array<void*>::push (t);
  84     }
  85   /// return last entry
  86   T* top (int j=0) const
  87     {
  88       return (T*) Array<void*>::top (j);
  89     }
  90   T *& top (int i=0)
  91     {
  92       return (T*&) Array<void*>::top (i);
  93     }
  94   void substitute (T *old, T*new_p)
  95     {
  96       int i;
  97       while ((i = find_index (old)) >=0)
  98         if (new_p)
  99           elem_ref (i) =new_p;
 100         else
 101           del (i);
 102     }
 103   void unordered_substitute (T* old, T * new_p)
 104     {
 105       int i;
 106       while ((i = find_index (old)) >=0)
 107         if (new_p)
 108           elem_ref (i) =new_p;
 109         else {
 110           unordered_del (i);
 111         }
 112
 113     }
 114   void default_sort () {
 115     sort (default_compare);
 116   }
 117   // quicksort.
 118   void sort (int (*compare) (T *const&,T *const&),
 119              int lower = -1, int upper = -1);
 120
 121   void uniq () {
 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
 155   T ** accesses () const
 156     {
 157       return (T**) Array<void*>::accesses ();
 158     }
 159   T * get (int i)
 160     {
 161       return (T*) Array<void*>::get (i);
 162     }
 163   Link_array<T>
 164   slice (int l,int u)
 165     {
 166       return Array<void*>::slice (l,u);
 167     }
 168   void concat (Link_array<T> const &a2)
 169     {
 170       Array<void*>::concat (a2);
 171     }
 172   int find_index (T const * t) const {
 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
 199
 200 template<class T> inline void
 201 Link_array<T>::sort (int (*compare)(T *const&,T *const&), int lower, int upper)
 202 {
 203   if (lower < 0)
 204     {
 205       lower = 0 ;
 206       upper = size () - 1;
 207     }
 208   if (lower >= upper)
 209     return;
 210   swap (lower, (lower+upper)/2);
 211   int last = lower;
 212   for (int i= lower +1; i <= upper; i++)
 213     if (compare (elem (i), elem (lower)) < 0)
 214       swap (++last,i);
 215   swap (lower, last);
 216   sort (compare, lower, last-1);
 217   sort (compare, last+1, upper);
 218 }
 219
 220 template<class T>
 221 void
 222 junk_pointers (Link_array<T> &a)
 223 {
 224   for (int i=0; i < a.size ();  i++)
 225     {
 226       delete a[i];
 227     }
 228   a.clear ();
 229 }
 230
 231
 232
 233 /*
 234   lookup with binsearch, return tokencode.
 235 */
 236 template<class T>
 237 int
 238 binsearch (Array<T> const &arr, T t, int (*compare) (T const&,T const&))
 239 {
 240   int lo;
 241   int hi;
 242   int cmp;
 243   int result;
 244   lo = 0;
 245   hi = Array<T>::maxkey;
 246
 247   /* binary search */
 248   do
 249   {
 250       cmp = (lo + hi) / 2;
 251
 252       result = compare (t, arr[cmp]);
 253
 254       if (result < 0)
 255           hi = cmp;
 256       else
 257           lo = cmp;
 258     }
 259   while (hi - lo > 1);
 260   if (!compare (t, arr[lo]))
 261     return lo;
 262   else
 263     return -1;              /* not found */
 264 }
 265
 266
 267 template<class T>
 268 int
 269 binsearch_links (Link_array<T> const &arr, T *t,
 270                       int (*compare) (T *const&,T *const&),
 271                       int lo = 0, int hi = -1 )
 272 {
 273   int cmp;
 274   int result;
 275   if (hi< 0)
 276     hi = arr.size ();
 277
 278   if (hi == 0)
 279     return -1;
 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   if (!compare (t, arr[lo]))
 295     return lo;
 296   else
 297     return -1;              /* not found */
 298 }
 299
 300
 301 template<class T>
 302 void
 303 binary_search_bounds (Link_array<T> const &table,
 304                       T const *key, int (*compare) (T * const& , T *const &),
 305                       int *lo,
 306                       int *hi)
 307 {
 308   int cmp;
 309   int result;
 310
 311   /* binary search */
 312   do
 313   {
 314       cmp = (*lo + *hi) / 2;
 315
 316       result = (*compare)  ((T*) key, table[cmp]);
 317
 318       if (result < 0)
 319           *hi = cmp;
 320       else
 321           *lo = cmp;
 322     }
 323   while (*hi - *lo > 1);
 324 }
 325
 326 #endif // PARRAY_HH
 327