flower/include/parray.hh

   1 /*
   2   parray.hh -- declare Pointer_array
   3
   4   source file of the Flower Library
   5
   6   (c)  1997--1998 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 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   Link_array (Link_array<T> const &src)
  40     : Array<void*> (src)
  41     {
  42     }
  43   /// access element
  44   T *elem (int i) const
  45     {
  46       return elem_ref (i);
  47     }
  48   T *&elem_ref  (int i) const
  49     {
  50       return (T*&) Array<void*>::elem_ref (i);
  51     }
  52
  53   /// access element
  54   T* &operator[] (int i)
  55     {
  56       return (T*&) Array<void*>::elem_ref (i);
  57     }
  58   /// access element
  59   T *const operator[] (int i) const
  60     {
  61       return (T *const) Array<void*>::elem (i);
  62     }
  63   T *pop ()
  64     {
  65       return (T*) Array<void*>::pop ();
  66     }
  67   void insert (T *t, int i)
  68     {
  69       Array<void*>::insert (t, i);
  70     }
  71   void push (T* t)
  72     {
  73       Array<void*>::push (t);
  74     }
  75   /// return last entry
  76   T* top (int j=0) const
  77     {
  78       return (T*) Array<void*>::top (j);
  79     }
  80   T *& top (int i=0)
  81     {
  82       return (T*&) Array<void*>::top (i);
  83     }
  84   void substitute (T *old, T*new_l)
  85     {
  86       int i;
  87       while ((i = find_i (old)) >=0)
  88         if (new_l)
  89           elem_ref (i) =new_l;
  90         else
  91           del (i);
  92     }
  93   void unordered_substitute (T* old, T * new_l)
  94     {
  95       int i;
  96       while ((i = find_i (old)) >=0)
  97         if (new_l)
  98           elem_ref (i) =new_l;
  99         else {
 100           unordered_del (i);
 101         }
 102
 103     }
 104   void default_sort() {
 105     sort (default_compare);
 106   }
 107   // quicksort.
 108   void sort (int (*compare)(T *const&,T *const&),
 109              int lower = -1, int upper = -1);
 110
 111   void uniq() {
 112     Link_array<T> l_arr;
 113     for (int i=0; i < size(); i++)
 114       if (!i || elem (i-1) != elem (i))
 115         l_arr.push (elem (i));
 116     *this = l_arr;
 117   }
 118   Array<void*>::del;
 119   Array<void*>::unordered_del;
 120   Array<void*>::size;
 121   Array<void*>::clear;
 122   Array<void*>::set_size;
 123   Array<void*>::empty;
 124   Array<void*>::reverse;
 125   T * get (int i)
 126     {
 127       return (T*) Array<void*>::get (i);
 128     }
 129   Link_array<T>
 130   slice(int l,int u)
 131     {
 132       return Array<void*>::slice (l,u);
 133     }
 134   void concat (Link_array<T> const &a2)
 135     {
 136       Array<void*>::concat (a2);
 137     }
 138   int find_i (T const * t) const {
 139     for (int i=0; i < size(); i++)
 140       if (elem (i) == t)
 141         return i;
 142     return -1;
 143   }
 144   T *find_l (T const *t) const
 145     {
 146       int i = find_i (t);
 147       if (i >= 0)
 148         return elem (i);
 149       else
 150         return 0;
 151     }
 152
 153 };
 154
 155 template<class T, class V>
 156 Link_array<T>
 157 typecast_array (Link_array<V> const &a, T * /* dummy */ )
 158 {
 159   Link_array<T> ret;
 160   for (int i=a.size (); i-- ; )
 161         ret.push (dynamic_cast<T*> (a[i]));     // ugh?
 162   return ret;
 163 }
 164
 165
 166
 167 template<class T> inline void
 168 Link_array<T>::sort (int (*compare)(T *const&,T *const&),
 169                 int lower = -1, int upper = -1)
 170 {
 171   if (lower < 0)
 172     {
 173       lower = 0 ;
 174       upper = size () - 1;
 175     }
 176   if (lower >= upper)
 177     return;
 178   swap (lower, (lower+upper)/2);
 179   int last = lower;
 180   for (int i= lower +1; i <= upper; i++)
 181     if (compare (elem (i), elem(lower)) < 0)
 182       swap (++last,i);
 183   swap (lower, last);
 184   sort (compare, lower, last-1);
 185   sort (compare, last+1, upper);
 186 }
 187
 188 #endif // PARRAY_HH
 189