2 (c) 1995--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
4 Distributed under GNU GPL
17 functions with loops don't inline
20 template<class T> INLINE void
21 arrcpy (T *dest, T const *src, int count)
23 for (int i_shadows_local = 0; i_shadows_local < count; i_shadows_local++)
27 urg: wierd egcs-1.1.2-12c (stock LinuxPPC R5) bug on ppc
29 fixed in egcs-1.1.2-12f
30 ftp://dev.linuxppc.org/users/fsirl/R5/RPMS/ppc/
40 template<class T> INLINE void
41 Array<T>::insert (T k, int j)
43 assert (j >= 0 && j <= size_);
45 for (int i = size_ - 1; i > j; i--)
46 array_[i] = array_[i - 1];
50 template<class T> INLINE void
51 Array<T>::sort (int (*compare) (T const &, T const &), int lower, int upper)
60 swap (lower, (lower + upper) / 2);
62 for (int i = lower +1; i <= upper; i++)
63 if (compare (array_[i], array_[lower]) < 0)
66 sort (compare, lower, last - 1);
67 sort (compare, last + 1, upper);
70 template<class T> INLINE void
74 for (int i = 0, j = size_ - 1; i < h; i++, j--)
78 template<class T> INLINE
82 assert (max_ >= size_ && size_ >= 0);
83 if (max_) assert (array_);
86 template<class T> INLINE
88 Array<T>::remove_array ()
97 template<class T> INLINE
99 Array<T>::slice (int lower, int upper) const
101 assert (lower >= 0 && lower <= upper && upper <= size_);
103 int s = upper - lower;
105 arrcpy (r.array_, array_ + lower, s);
111 binary_search_bounds (Array<T> const &table,
112 T const &key, int (*compare) (T const &, T const &),
122 cmp = (*lo + *hi) / 2;
124 result = (*compare) (key, table[cmp]);
131 while (*hi - *lo > 1);
135 lookup with binsearch, return array index.
139 binary_search (Array<T> const &table,
140 T const &key, int (*compare) (T const &, T const &),
147 binary_search_bounds (table, key, compare, &lo, &hi);
149 if (! (*compare) (key, table[lo]))
154 return -1; /* not found */