flower/include/parray.hh

   1 /*
   2   parray.hh -- declare Pointer_array
   3
   4   source file of the Flower Library
   5
   6   (c)  1997--2000 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   an array of pointers.
  17
  18   TODO
  19   should init to 0.
  20  */
  21 template<class T>
  22 class Link_array : private Array<void *>
  23 {
  24   static int default_compare (T *const& p1, T  *const&p2) {
  25     /* can't do p1 -p2, since T might be an incomplete type */
  26     if (p1 < p2)
  27       return -1 ;
  28     if (p2 < p1)
  29       return 1;
  30     return 0;
  31   }
  32   Link_array (Array<void*> v)
  33     :Array<void*> (v)
  34     {
  35     }
  36 public:
  37   Link_array ()
  38     {}
  39
  40   Link_array (T * const *tp, int n)
  41     : Array<void*> ((void **)tp, n)
  42     {
  43     }
  44
  45   Link_array (Link_array<T> const &src)
  46     : Array<void*> (src)
  47     {
  48     }
  49   /// access element
  50   T *elem (int i) const
  51     {
  52       return elem_ref (i);
  53     }
  54   T *&elem_ref (int i) const
  55     {
  56       return (T*&) Array<void*>::elem_ref (i);
  57     }
  58
  59   /// access element
  60   T* &operator[] (int i)
  61     {
  62       return (T*&) Array<void*>::elem_ref (i);
  63     }
  64   /// access element
  65   T *const operator[] (int i) const
  66     {
  67       return (T *const) Array<void*>::elem (i);
  68     }
  69   T *pop ()
  70     {
  71       return (T*) Array<void*>::pop ();
  72     }
  73   void insert (T *t, int i)
  74     {
  75       Array<void*>::insert (t, i);
  76     }
  77   void push (T* t)
  78     {
  79       Array<void*>::push (t);
  80     }
  81   /// return last entry
  82   T* top (int j=0) const
  83     {
  84       return (T*) Array<void*>::top (j);
  85     }
  86   T *& top (int i=0)
  87     {
  88       return (T*&) Array<void*>::top (i);
  89     }
  90   void substitute (T *old, T*new_l)
  91     {
  92       int i;
  93       while ((i = find_i (old)) >=0)
  94         if (new_l)
  95           elem_ref (i) =new_l;
  96         else
  97           del (i);
  98     }
  99   void unordered_substitute (T* old, T * new_l)
 100     {
 101       int i;
 102       while ((i = find_i (old)) >=0)
 103         if (new_l)
 104           elem_ref (i) =new_l;
 105         else {
 106           unordered_del (i);
 107         }
 108
 109     }
 110   void default_sort () {
 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     Link_array<T> l_arr;
 119     for (int i=0; i < size (); i++)
 120       if (!i || elem (i-1) != elem (i))
 121         l_arr.push (elem (i));
 122     *this = l_arr;
 123   }
 124   Array<void*>::del;
 125   Array<void*>::unordered_del;
 126   Array<void*>::size;
 127   Array<void*>::clear;
 128   Array<void*>::set_size;
 129   Array<void*>::empty;
 130   Array<void*>::reverse;
 131   Array<void*>::tighten_maxsize;
 132
 133   T *& boundary (int d, int i)
 134   {
 135     assert (d);
 136     if (d == 1)
 137       return top (i);
 138     else
 139       return elem_ref (i);
 140   }
 141   T * boundary (int d, int i)const
 142   {
 143     assert (d);
 144     if (d == 1)
 145       return top (i);
 146     else
 147       return elem_ref (i);
 148   }
 149
 150
 151   T ** access_array () const
 152     {
 153       return (T**) Array<void*>::access_array ();
 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)
 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_i (T const * t) const {
 169     for (int i=0; i < size (); i++)
 170       if (elem (i) == t)
 171         return i;
 172     return -1;
 173   }
 174   T *find_l (T const *t) const
 175     {
 176       int i = find_i (t);
 177       if (i >= 0)
 178         return elem (i);
 179       else
 180         return 0;
 181     }
 182
 183 };
 184
 185 template<class T, class V>
 186 Link_array<T>
 187 typecast_array (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
 196
 197 template<class T> inline void
 198 Link_array<T>::sort (int (*compare) (T *const&,T *const&),
 199                 int lower = -1, int upper = -1)
 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_pointer_array (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
 231 /*
 232   lookup with binsearch, return tokencode.
 233 */
 234 template<class T>
 235 int
 236 binsearch_array (Array<T> const &arr, T t, int (*compare) (T const&,T const&))
 237 {
 238   int lo;
 239   int hi;
 240   int cmp;
 241   int result;
 242   lo = 0;
 243   hi = maxkey;
 244
 245   /* binary search */
 246   do
 247   {
 248       cmp = (lo + hi) / 2;
 249
 250       result = compare (t, arr[cmp]);
 251
 252       if (result < 0)
 253           hi = cmp;
 254       else
 255           lo = cmp;
 256     }
 257   while (hi - lo > 1);
 258   if (!compare (t, arr[lo]))
 259     return lo;
 260   else
 261     return -1;              /* not found */
 262 }
 263
 264
 265 template<class T>
 266 int
 267 binsearch_link_array (Link_array<T> const &arr, T *t,
 268                       int (*compare) (T *const&,T *const&),
 269                       int lo = 0, int hi = -1 )
 270 {
 271   int cmp;
 272   int result;
 273   if (hi< 0)
 274     hi = arr.size ();
 275
 276   if (hi == 0)
 277     return -1;
 278
 279   /* binary search */
 280   do
 281   {
 282       cmp = (lo + hi) / 2;
 283
 284       result = compare (t, arr[cmp]);
 285
 286       if (result < 0)
 287           hi = cmp;
 288       else
 289           lo = cmp;
 290     }
 291   while (hi - lo > 1);
 292   if (!compare (t, arr[lo]))
 293     return lo;
 294   else
 295     return -1;              /* not found */
 296 }
 297
 298
 299 #endif // PARRAY_HH
 300