2 parray.hh -- declare Pointer_array
4 source file of the Flower Library
6 (c) 1997--2005 Han-Wen Nienhuys <hanwen@xs4all.nl>
21 class Link_array : private Array<void *>
24 Link_array (Array<void *> v)
32 static int default_compare (T *const &p1, T *const &p2)
34 /* can't do p1 -p2, since T might be an incomplete type */
41 Link_array (T *const *tp, int n)
42 : Array<void *> ((void **)tp, n)
46 Link_array (Link_array<T> const &src)
55 T *&elem_ref (int i) const
57 return (T *&) Array<void *>::elem_ref (i);
61 T *&operator [] (int i)
63 return (T *&) Array<void *>::elem_ref (i);
66 T *const operator [] (int i) const
68 return (T *const) Array<void *>::elem (i);
72 return (T *) Array<void *>::pop ();
74 void insert (T *t, int i)
76 Array<void *>::insert (t, i);
80 Array<void *>::push (t);
83 T *top (int j = 0) const
85 return (T *) Array<void *>::top (j);
89 return (T *&) Array<void *>::top (i);
91 void substitute (T *old, T *new_p)
94 while ((i = find_index (old)) >= 0)
100 void unordered_substitute (T *old, T *new_p)
103 while ((i = find_index (old)) >= 0)
105 elem_ref (i) = new_p;
111 sort (default_compare);
114 void sort (int (*compare) (T *const &, T *const &),
115 int lower = -1, int upper = -1);
120 for (int i = 0; i < size (); i++)
121 if (!i || elem (i - 1) != elem (i))
126 Array<void *>::unordered_del;
128 Array<void *>::clear;
129 Array<void *>::set_size;
130 Array<void *>::is_empty;
131 Array<void *>::reverse;
132 Array<void *>::tighten_maxsize;
134 T *& boundary (int d, int i)
142 T *boundary (int d, int i)const
151 T ** accesses () const
153 return (T **) Array<void *>::accesses ();
157 return (T *) Array<void *>::get (i);
160 slice (int l, int u) const
162 return Array<void *>::slice (l, u);
164 void concat (Link_array<T> const &a2)
166 Array<void *>::concat (a2);
168 int find_index (T const *t) const
170 for (int i = 0; i < size (); i++)
175 T *find (T const *t) const
177 int i = find_index (t);
185 template<class T, class V>
187 typecasts (Link_array<V> const &a, T * /* dummy */)
190 for (int i = a.size (); i--;)
191 ret.push (dynamic_cast<T *> (a[i])); // ugh?
195 template<class T> inline void
196 Link_array<T>::sort (int (*compare) (T *const &, T *const &), int lower, int upper)
205 swap (lower, (lower + upper) / 2);
207 for (int i = lower +1; i <= upper; i++)
208 if (compare (elem (i), elem (lower)) < 0)
211 sort (compare, lower, last - 1);
212 sort (compare, last + 1, upper);
217 junk_pointers (Link_array<T> &a)
219 for (int i = 0; i < a.size (); i++)
225 lookup with binsearch, return tokencode.
229 binsearch (Array<T> const &arr, T t, int (*compare) (T const &, T const &))
234 int hi = arr.size ();
241 result = compare (t, arr[cmp]);
250 if (!compare (t, arr[lo]))
253 return -1; /* not found */
258 binsearch_links (Link_array<T> const &arr, T *t,
259 int (*compare) (T *const &, T *const &))
264 int hi = arr.size ();
274 result = (*compare) (t, arr[cmp]);
283 if (!compare (t, arr[lo]))
286 return -1; /* not found */
291 binary_search_bounds (Link_array<T> const &table,
292 T const *key, int (*compare) (T *const &, T *const &),
302 cmp = (*lo + *hi) / 2;
304 result = (*compare) ((T *) key, table[cmp]);
311 while (*hi - *lo > 1);