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 #ifndef STD_VECTOR_HH
  13 #error array.hh is obsolete, use std-vector.hh
  14 #endif
  15
  16 using namespace std;
  17
  18 namespace std {
  19 /**
  20    an array of pointers.
  21
  22    TODO
  23    should init to 0.
  24 */
  25 template<class T>
  26 class Link_array : private Array<void *>
  27 {
  28
  29   Link_array (Array<void *> const &v)
  30     :Array<void *> (v)
  31   {
  32   }
  33
  34 public:
  35   Link_array ()
  36   {
  37   }
  38
  39   T *const &back() const
  40   {
  41     return (T * const &) Array<void *>::back();
  42   }
  43
  44   T *&back ()
  45   {
  46     return (T *&) Array<void *>::back ();
  47   }
  48
  49   Array<void *>::begin;
  50   Array<void *>::data;
  51   Array<void *>::end;
  52   Array<void *>::clear;
  53   Array<void *>::erase;
  54   Array<void *>::resize;
  55   Array<void *>::size;
  56   Array<void *>::empty;
  57   Array<void *>::pop_back;
  58
  59
  60   /* Flower compat */
  61   Array<void *>::unordered_del;
  62   Array<void *>::tighten_maxsize;
  63
  64   static int default_compare (T *const &p1, T *const &p2)
  65   {
  66     /* can't do p1 -p2, since T might be an incomplete type */
  67     if (p1 < p2)
  68       return -1;
  69     if (p2 < p1)
  70       return 1;
  71     return 0;
  72   }
  73   Link_array (T *const *tp, int n)
  74     : Array<void *> ((void **)tp, n)
  75   {
  76   }
  77
  78   Link_array (Link_array<T> const &src)
  79     : Array<void *> (src)
  80   {
  81   }
  82
  83   /* std::vector interface */
  84   //typedef T** iterator;
  85   //typedef T* const* iterator_const;
  86
  87   Link_array (const_iterator begin, const_iterator end)
  88     : Array<void *> (begin, end)
  89   {
  90   }
  91
  92   T *at (int i)
  93   {
  94     return (T *) Array<void *>::at (i);
  95   }
  96   T const *at (int i) const
  97   {
  98     return (T const *) Array<void *>::at (i);
  99   }
 100
 101   /// access element
 102   T *&operator [] (int i)
 103   {
 104     return (T *&) Array<void *>::at (i);
 105   }
 106   /// access element
 107   T *const operator [] (int i) const
 108   {
 109     return (T *const) Array<void *>::at (i);
 110   }
 111   T *pop ()
 112   {
 113     T* t = (T *) Array<void *>::back ();
 114     pop_back ();
 115     return t;
 116   }
 117   void insert (iterator b, T *t)
 118   {
 119     Array<void *>::insert (b, t);
 120   }
 121   void insert (iterator pos, const_iterator b, const_iterator e)
 122   {
 123     Array<void *>::insert (pos, b, e);
 124   }
 125   void push_back (T *t)
 126   {
 127     Array<void *>::push_back (t);
 128   }
 129
 130   T *top (vsize j)
 131   {
 132     return (*this)[size_ - j - 1];
 133   }
 134   T *& top (vsize j) const
 135   {
 136     return (*this)[size_ - j - 1];
 137   }
 138
 139   void substitute (T *old, T *new_p)
 140   {
 141     int i;
 142     while ((i = find_index (old)) >= 0)
 143       if (new_p)
 144         at (i) = new_p;
 145       else
 146         erase (begin () + i);
 147   }
 148   void unordered_substitute (T *old, T *new_p)
 149   {
 150     int i;
 151     while ((i = find_index (old)) >= 0)
 152       if (new_p)
 153         at (i) = new_p;
 154       else
 155         unordered_del (i);
 156   }
 157   void default_sort ()
 158   {
 159     sort (default_compare);
 160   }
 161
 162   // quicksort.
 163   void sort (int (*compare) (T *const &, T *const &),
 164              int lower = -1, int upper = -1);
 165
 166   void uniq ()
 167   {
 168     Link_array<T> ls;
 169     for (vsize i = 0; i < size (); i++)
 170       if (!i || at (i - 1) != at (i))
 171         ls.push_back (at (i));
 172     *this = ls;
 173   }
 174
 175   T *& boundary (int d, int i)
 176   {
 177     assert (d);
 178     if (d == 1)
 179       return top (i);
 180     else
 181       return at (i);
 182   }
 183   T *boundary (int d, int i)const
 184   {
 185     assert (d);
 186     if (d == 1)
 187       return top (i);
 188     else
 189       return at (i);
 190   }
 191
 192   T **
 193   data ()
 194   {
 195     return (T**) Array<void *>::data ();
 196   }
 197
 198   T * const*
 199   data () const
 200   {
 201     return (T**) Array<void *>::data ();
 202   }
 203
 204   /**
 205      remove  i-th element, and return it.
 206   */
 207   T *get (vsize i)
 208   {
 209     T *t = at (i);
 210     Array<void*>::erase (Array<void*>::begin () + i);
 211     return t;
 212   }
 213   Link_array<T>
 214   slice (int l, int u) const
 215   {
 216     return Array<void *>::Array (begin () + l, begin () + u);
 217   }
 218   void concat (Link_array<T> const &a2)
 219   {
 220     Array<void *>::insert (end (), a2.begin (), a2.end ());
 221   }
 222   int find_index (T const *t) const
 223   {
 224     for (vsize i = 0; i < size (); i++)
 225       if (at (i) == t)
 226         return i;
 227     return -1;
 228   }
 229   T const *find (T const *t) const
 230   {
 231     int i = find_index (t);
 232     if (i >= 0)
 233       return at (i);
 234     else
 235       return 0;
 236   }
 237
 238   void swap (vsize i, vsize j)
 239   {
 240     T *t ((*this)[i]);
 241     (*this)[i] = (*this)[j];
 242     (*this)[j] = t;
 243   }
 244   void
 245   reverse ()
 246   {
 247     vsize h = size () / 2;
 248     for (vsize i = 0, j = size () - 1; i < h; i++, j--)
 249       swap (i, j);
 250   }
 251 };
 252
 253 template<class T, class V>
 254 Link_array<T>
 255 typecasts (Link_array<V> const &a, T * /* dummy */)
 256 {
 257   Link_array<T> ret;
 258   for (vsize i = a.size (); i--;)
 259     ret.push_back (dynamic_cast<T *> (a[i]));   // ugh?
 260   return ret;
 261 }
 262
 263 template<class T> inline void
 264 Link_array<T>::sort (int (*compare) (T *const &, T *const &), int lower, int upper)
 265 {
 266   if (lower < 0)
 267     {
 268       lower = 0;
 269       upper = size () - 1;
 270     }
 271   if (lower >= upper)
 272     return;
 273   swap (lower, (lower + upper) / 2);
 274   int last = lower;
 275   for (int i = lower +1; i <= upper; i++)
 276     if (compare (at (i), at (lower)) < 0)
 277       swap (++last, i);
 278   swap (lower, last);
 279   sort (compare, lower, last - 1);
 280   sort (compare, last + 1, upper);
 281 }
 282
 283 template<class T>
 284 void
 285 junk_pointers (Link_array<T> &a)
 286 {
 287   for (vsize i = 0; i < a.size (); i++)
 288     delete a[i];
 289   a.clear ();
 290 }
 291
 292 template<class T>
 293 int
 294 binary_search (Link_array<T> const &arr, T *t,
 295                int (*compare) (T *const &, T *const &))
 296 {
 297   int cmp;
 298   int result;
 299   int lo = 0;
 300   int hi = arr.size ();
 301
 302   if (hi == 0)
 303     return -1;
 304
 305   /* binary search */
 306   do
 307     {
 308       cmp = (lo + hi) / 2;
 309
 310       result = (*compare) (t, arr[cmp]);
 311
 312       if (result < 0)
 313         hi = cmp;
 314       else
 315         lo = cmp;
 316     }
 317   while (hi - lo > 1);
 318
 319   if (!compare (t, arr[lo]))
 320     return lo;
 321   /* not found */
 322   return -1;
 323 }
 324
 325 template<class T>
 326 void
 327 binary_search_bounds (Link_array<T> const &table,
 328                       T const *key, int (*compare) (T *const &, T *const &),
 329                       int *lo,
 330                       int *hi)
 331 {
 332   int cmp;
 333   int result;
 334
 335   /* binary search */
 336   do
 337     {
 338       cmp = (*lo + *hi) / 2;
 339
 340       result = (*compare) ((T *) key, table[cmp]);
 341
 342       if (result < 0)
 343         *hi = cmp;
 344       else
 345         *lo = cmp;
 346     }
 347   while (*hi - *lo > 1);
 348 }
 349
 350 template<class T>
 351 void
 352 reverse (Link_array<T> &v)
 353 {
 354   vsize h = v.size () / 2;
 355   for (vsize i = 0, j = v.size () - 1; i < h; i++, j--)
 356     swap (v[i], v[j]);
 357 }
 358
 359 template<typename T>
 360 void
 361 concat (Link_array<T> &v, Link_array<T> const& w)
 362 {
 363   v.insert (v.end (), w.begin (), w.end ());
 364 }
 365
 366 template<typename T>
 367 void
 368 vector_sort (Link_array<T> &v, int (*compare) (T *const &, T * const &),
 369              vsize lower=-1, vsize upper=-1)
 370 {
 371   if (lower < 0)
 372     {
 373       lower = 0;
 374       upper = v.size () - 1;
 375     }
 376   if (lower >= upper)
 377     return;
 378   swap (v[lower], v[(lower + upper) / 2]);
 379   vsize last = lower;
 380   for (vsize i = lower +1; i <= upper; i++)
 381     if (compare (v[i], v[lower]) < 0)
 382       swap (v[++last], v[i]);
 383   swap (v[lower], v[last]);
 384   vector_sort (v, compare, lower, last - 1);
 385   vector_sort (v, compare, last + 1, upper);
 386 }
 387
 388 template<typename T>
 389 void
 390 uniq (Link_array<T> &v)
 391 {
 392   v.uniq ();
 393 }
 394
 395 template<typename T>
 396 typename Array<void *>::const_iterator
 397 find (Link_array<T> const &v, T * const& key)
 398 {
 399   return v.begin () + v.find_index (key);
 400 }
 401
 402 }
 403
 404 #endif // PARRAY_HH
 405