2 parray.hh -- declare Pointer_array
4 source file of the Flower Library
6 (c) 1997--2000 Han-Wen Nienhuys <hanwen@cs.uu.nl>
22 class Link_array : private Array<void *>
24 static int default_compare (T *const& p1, T *const&p2) {
25 /* can't do p1 -p2, since T might be an incomplete type */
32 Link_array (Array<void*> v)
40 Link_array(T * const *tp, int n)
41 : Array<void*> ((void **)tp, n)
45 Link_array (Link_array<T> const &src)
54 T *&elem_ref (int i) const
56 return (T*&) Array<void*>::elem_ref (i);
60 T* &operator[] (int i)
62 return (T*&) Array<void*>::elem_ref (i);
65 T *const operator[] (int i) const
67 return (T *const) Array<void*>::elem (i);
71 return (T*) Array<void*>::pop ();
73 void insert (T *t, int i)
75 Array<void*>::insert (t, i);
79 Array<void*>::push (t);
82 T* top (int j=0) const
84 return (T*) Array<void*>::top (j);
88 return (T*&) Array<void*>::top (i);
90 void substitute (T *old, T*new_l)
93 while ((i = find_i (old)) >=0)
99 void unordered_substitute (T* old, T * new_l)
102 while ((i = find_i (old)) >=0)
110 void default_sort() {
111 sort (default_compare);
114 void sort (int (*compare)(T *const&,T *const&),
115 int lower = -1, int upper = -1);
119 for (int i=0; i < size(); i++)
120 if (!i || elem (i-1) != elem (i))
121 l_arr.push (elem (i));
125 Array<void*>::unordered_del;
128 Array<void*>::set_size;
130 Array<void*>::reverse;
131 Array<void*>::tighten_maxsize;
133 T *& boundary (int d, int i)
141 T * boundary (int d, int i)const
151 T ** access_array () const
153 return (T**) Array<void*>::access_array();
157 return (T*) Array<void*>::get (i);
162 return Array<void*>::slice (l,u);
164 void concat (Link_array<T> const &a2)
166 Array<void*>::concat (a2);
168 int find_i (T const * t) const {
169 for (int i=0; i < size(); i++)
174 T *find_l (T const *t) const
185 template<class T, class V>
187 typecast_array (Link_array<V> const &a, T * /* dummy */ )
190 for (int i=a.size (); i-- ; )
191 ret.push (dynamic_cast<T*> (a[i])); // ugh?
197 template<class T> inline void
198 Link_array<T>::sort (int (*compare)(T *const&,T *const&),
199 int lower = -1, int upper = -1)
208 swap (lower, (lower+upper)/2);
210 for (int i= lower +1; i <= upper; i++)
211 if (compare (elem (i), elem(lower)) < 0)
214 sort (compare, lower, last-1);
215 sort (compare, last+1, upper);
220 junk_pointer_array (Link_array<T> &a)
222 for (int i=0; i < a.size (); i++)
232 lookup with binsearch, return tokencode.
236 binsearch_array (Array<T> const &arr, T t, int (*compare)(T const&,T const&))
250 result = compare (t, arr[cmp]);
258 if (!compare (t, arr[lo]))
261 return -1; /* not found */
267 binsearch_link_array (Link_array<T> const &arr, T *t,
268 int (*compare)(T *const&,T *const&))
285 result = compare (t, arr[cmp]);
293 if (!compare (t, arr[lo]))
296 return -1; /* not found */