/*
- (c) Han-Wen Nienhuys 1995,96,97,98
+ (c) 1995--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
Distributed under GNU GPL
*/
-
#if 0
#include "array.hh"
#ifdef INLINE
#endif
/*
- functions with loops don't inline
- */
+ functions with loops don't inline
+*/
-template<class T> INLINE void
-arrcpy (T*dest, T const* src, int count)
+template<class T> INLINE void
+arrcpy (T *dest, T const *src, int count)
{
- for (int i_shadows_local=0; i_shadows_local < count ; i_shadows_local++)
+ for (int i_shadows_local = 0; i_shadows_local < count; i_shadows_local++)
#ifdef __powerpc__
{
/*
urg: wierd egcs-1.1.2-12c (stock LinuxPPC R5) bug on ppc
bug report filed
fixed in egcs-1.1.2-12f
- ftp://dev.linuxppc.org/users/fsirl/R5/RPMS/ppc/
+ ftp://dev.linuxppc.org/users/fsirl/R5/RPMS/ppc/
*/
*dest = *src;
dest++, src++;
}
#else
- *dest++ = *src++;
+ *dest++ = *src++;
#endif
}
template<class T> INLINE void
-Array<T>::insert (T k, int j)
+Array<T>::insert (T k, int j)
{
- assert (j >=0 && j<= size_);
- set_size (size_+1);
- for (int i=size_-1; i > j; i--)
- array_p_[i] = array_p_[i-1];
- array_p_[j] = k;
+ assert (j >= 0 && j <= size_);
+ set_size (size_ + 1);
+ for (int i = size_ - 1; i > j; i--)
+ array_[i] = array_[i - 1];
+ array_[j] = k;
}
template<class T> INLINE void
-Array<T>::sort (int (*compare) (T const&,T const&),
- int lower = -1, int upper = -1)
+Array<T>::sort (int (*compare) (T const &, T const &), int lower, int upper)
{
- if (lower < 0)
+ if (lower < 0)
{
- lower = 0 ;
+ lower = 0;
upper = size () - 1;
}
if (lower >= upper)
return;
- swap (lower, (lower+upper)/2);
+ swap (lower, (lower + upper) / 2);
int last = lower;
- for (int i= lower +1; i <= upper; i++)
- if (compare (array_p_[i], array_p_[lower]) < 0)
- swap (++last,i);
+ for (int i = lower +1; i <= upper; i++)
+ if (compare (array_[i], array_[lower]) < 0)
+ swap (++last, i);
swap (lower, last);
- sort (compare, lower, last-1);
- sort (compare, last+1, upper);
+ sort (compare, lower, last - 1);
+ sort (compare, last + 1, upper);
}
template<class T> INLINE void
-Array<T>::reverse ()
+Array<T>::reverse ()
{
- int h = size_/2;
- for (int i =0,j = size_-1; i < h; i++,j--)
- swap (i,j);
+ int h = size_ / 2;
+ for (int i = 0, j = size_ - 1; i < h; i++, j--)
+ swap (i, j);
}
template<class T> INLINE
void
Array<T>::OK () const
{
- assert (max_ >= size_ && size_ >=0);
- if (max_) assert (array_p_);
+ assert (max_ >= size_ && size_ >= 0);
+ if (max_)
+ assert (array_);
}
template<class T> INLINE
T *
-Array<T>::remove_array_p ()
+Array<T>::remove_array ()
{
- T * p = array_p_;
+ T *p = array_;
size_ = 0;
max_ = 0;
- array_p_ =0;
+ array_ = 0;
return p;
}
Array<T>
Array<T>::slice (int lower, int upper) const
{
- assert (lower >= 0 && lower <=upper&& upper <= size_);
+ assert (lower >= 0 && lower <= upper && upper <= size_);
Array<T> r;
- int s =upper-lower;
+ int s = upper - lower;
r.set_size (s);
- arrcpy (r.array_p_, array_p_ + lower, s);
+ arrcpy (r.array_, array_ + lower, s);
return r;
}
+template<class T>
+void
+binary_search_bounds (Array<T> const &table,
+ T const &key, int (*compare) (T const &, T const &),
+ int *lo,
+ int *hi)
+{
+ int cmp;
+ int result;
+
+ /* binary search */
+ do
+ {
+ cmp = (*lo + *hi) / 2;
+
+ result = (*compare) (key, table[cmp]);
+
+ if (result < 0)
+ *hi = cmp;
+ else
+ *lo = cmp;
+ }
+ while (*hi - *lo > 1);
+}
+
+/*
+ lookup with binsearch, return array index.
+*/
+template<class T>
+int
+binary_search (Array<T> const &table,
+ T const &key, int (*compare) (T const &, T const &),
+ int lo = 0,
+ int hi = -1)
+{
+ if (hi < 0)
+ hi = table.size ();
+
+ binary_search_bounds (table, key, compare, &lo, &hi);
+
+ if (! (*compare) (key, table[lo]))
+ return lo;
+ else
+ return -1; /* not found */
+}