2 parray.hh -- declare Pointer_array
4 source file of the Flower Library
6 (c) 1997--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
24 class Link_array : private Array<void *>
27 Link_array (Array<void*> v)
35 static int default_compare (T *const& p1, T *const&p2)
37 /* can't do p1 -p2, since T might be an incomplete type */
44 Link_array (T * const *tp, int n)
45 : Array<void*> ((void **)tp, n)
49 Link_array (Link_array<T> const &src)
58 T *&elem_ref (int i) const
60 return (T*&) Array<void*>::elem_ref (i);
64 T* &operator[] (int i)
66 return (T*&) Array<void*>::elem_ref (i);
69 T *const operator[] (int i) const
71 return (T *const) Array<void*>::elem (i);
75 return (T*) Array<void*>::pop ();
77 void insert (T *t, int i)
79 Array<void*>::insert (t, i);
83 Array<void*>::push (t);
86 T* top (int j=0) const
88 return (T*) Array<void*>::top (j);
92 return (T*&) Array<void*>::top (i);
94 void substitute (T *old, T*new_p)
97 while ((i = find_index (old)) >=0)
103 void unordered_substitute (T* old, T * new_p)
106 while ((i = find_index (old)) >=0)
114 void default_sort () {
115 sort (default_compare);
118 void sort (int (*compare) (T *const&,T *const&),
119 int lower = -1, int upper = -1);
123 for (int i=0; i < size (); i++)
124 if (!i || elem (i-1) != elem (i))
129 Array<void*>::unordered_del;
132 Array<void*>::set_size;
133 Array<void*>::is_empty;
134 Array<void*>::reverse;
135 Array<void*>::tighten_maxsize;
137 T *& boundary (int d, int i)
145 T * boundary (int d, int i)const
155 T ** accesses () const
157 return (T**) Array<void*>::accesses ();
161 return (T*) Array<void*>::get (i);
166 return Array<void*>::slice (l,u);
168 void concat (Link_array<T> const &a2)
170 Array<void*>::concat (a2);
172 int find_index (T const * t) const {
173 for (int i=0; i < size (); i++)
178 T *find (T const *t) const
180 int i = find_index (t);
188 template<class T, class V>
190 typecasts (Link_array<V> const &a, T * /* dummy */ )
193 for (int i=a.size (); i-- ; )
194 ret.push (dynamic_cast<T*> (a[i])); // ugh?
200 template<class T> inline void
201 Link_array<T>::sort (int (*compare)(T *const&,T *const&), int lower, int upper)
210 swap (lower, (lower+upper)/2);
212 for (int i= lower +1; i <= upper; i++)
213 if (compare (elem (i), elem (lower)) < 0)
216 sort (compare, lower, last-1);
217 sort (compare, last+1, upper);
222 junk_pointers (Link_array<T> &a)
224 for (int i=0; i < a.size (); i++)
234 lookup with binsearch, return tokencode.
238 binsearch (Array<T> const &arr, T t, int (*compare) (T const&,T const&))
245 hi = Array<T>::maxkey;
252 result = compare (t, arr[cmp]);
260 if (!compare (t, arr[lo]))
263 return -1; /* not found */
269 binsearch_links (Link_array<T> const &arr, T *t,
270 int (*compare) (T *const&,T *const&),
271 int lo = 0, int hi = -1 )
286 result = (*compare) (t, arr[cmp]);
294 if (!compare (t, arr[lo]))
297 return -1; /* not found */
303 binary_search_bounds (Link_array<T> const &table,
304 T const *key, int (*compare) (T * const& , T *const &),
314 cmp = (*lo + *hi) / 2;
316 result = (*compare) ((T*) key, table[cmp]);
323 while (*hi - *lo > 1);