2 parray.hh -- declare Pointer_array
4 source file of the Flower Library
6 (c) 1997--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
13 #error array.hh is obsolete, use std-vector.hh
26 class Link_array : private Array<void *>
29 Link_array (Array<void *> const &v)
39 T *const &back() const
41 return (T * const &) Array<void *>::back();
46 return (T *&) Array<void *>::back ();
54 Array<void *>::resize;
57 Array<void *>::pop_back;
61 Array<void *>::unordered_del;
62 Array<void *>::tighten_maxsize;
64 static int default_compare (T *const &p1, T *const &p2)
66 /* can't do p1 -p2, since T might be an incomplete type */
73 Link_array (T *const *tp, int n)
74 : Array<void *> ((void **)tp, n)
78 Link_array (Link_array<T> const &src)
83 /* std::vector interface */
84 //typedef T** iterator;
85 //typedef T* const* iterator_const;
87 Link_array (const_iterator begin, const_iterator end)
88 : Array<void *> (begin, end)
94 return (T *) Array<void *>::at (i);
96 T const *at (int i) const
98 return (T const *) Array<void *>::at (i);
102 T *&operator [] (int i)
104 return (T *&) Array<void *>::at (i);
107 T *const operator [] (int i) const
109 return (T *const) Array<void *>::at (i);
113 T* t = (T *) Array<void *>::back ();
117 void insert (iterator b, T *t)
119 Array<void *>::insert (b, t);
121 void insert (iterator pos, const_iterator b, const_iterator e)
123 Array<void *>::insert (pos, b, e);
125 void push_back (T *t)
127 Array<void *>::push_back (t);
132 return (*this)[size_ - j - 1];
134 T *& top (vsize j) const
136 return (*this)[size_ - j - 1];
139 void substitute (T *old, T *new_p)
142 while ((i = find_index (old)) >= 0)
146 erase (begin () + i);
148 void unordered_substitute (T *old, T *new_p)
151 while ((i = find_index (old)) >= 0)
159 sort (default_compare);
163 void sort (int (*compare) (T *const &, T *const &),
164 int lower = -1, int upper = -1);
169 for (vsize i = 0; i < size (); i++)
170 if (!i || at (i - 1) != at (i))
171 ls.push_back (at (i));
175 T *& boundary (int d, int i)
183 T *boundary (int d, int i)const
195 return (T**) Array<void *>::data ();
201 return (T**) Array<void *>::data ();
205 remove i-th element, and return it.
210 Array<void*>::erase (Array<void*>::begin () + i);
214 slice (int l, int u) const
216 return Array<void *>::Array (begin () + l, begin () + u);
218 void concat (Link_array<T> const &a2)
220 Array<void *>::insert (end (), a2.begin (), a2.end ());
222 int find_index (T const *t) const
224 for (vsize i = 0; i < size (); i++)
229 T const *find (T const *t) const
231 int i = find_index (t);
238 void swap (vsize i, vsize j)
241 (*this)[i] = (*this)[j];
247 vsize h = size () / 2;
248 for (vsize i = 0, j = size () - 1; i < h; i++, j--)
253 template<class T, class V>
255 typecasts (Link_array<V> const &a, T * /* dummy */)
258 for (vsize i = a.size (); i--;)
259 ret.push_back (dynamic_cast<T *> (a[i])); // ugh?
263 template<class T> inline void
264 Link_array<T>::sort (int (*compare) (T *const &, T *const &), int lower, int upper)
273 swap (lower, (lower + upper) / 2);
275 for (int i = lower +1; i <= upper; i++)
276 if (compare (at (i), at (lower)) < 0)
279 sort (compare, lower, last - 1);
280 sort (compare, last + 1, upper);
285 junk_pointers (Link_array<T> &a)
287 for (vsize i = 0; i < a.size (); i++)
294 binary_search (Link_array<T> const &arr, T *t,
295 int (*compare) (T *const &, T *const &))
300 int hi = arr.size ();
310 result = (*compare) (t, arr[cmp]);
319 if (!compare (t, arr[lo]))
327 binary_search_bounds (Link_array<T> const &table,
328 T const *key, int (*compare) (T *const &, T *const &),
338 cmp = (*lo + *hi) / 2;
340 result = (*compare) ((T *) key, table[cmp]);
347 while (*hi - *lo > 1);
352 reverse (Link_array<T> &v)
354 vsize h = v.size () / 2;
355 for (vsize i = 0, j = v.size () - 1; i < h; i++, j--)
361 concat (Link_array<T> &v, Link_array<T> const& w)
363 v.insert (v.end (), w.begin (), w.end ());
368 vector_sort (Link_array<T> &v, int (*compare) (T *const &, T * const &),
369 vsize lower=-1, vsize upper=-1)
374 upper = v.size () - 1;
378 swap (v[lower], v[(lower + upper) / 2]);
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);
390 uniq (Link_array<T> &v)
396 typename Array<void *>::const_iterator
397 find (Link_array<T> const &v, T * const& key)
399 return v.begin () + v.find_index (key);