X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=flower%2Finclude%2Farray.icc;h=a84fe937e4a7834d808069792e4734e502bc7ecc;hb=91e7cbaa6e54e004365d28e0f10c9362a7f13320;hp=8b876ce85d2bca4e43ef1841ecec755f28f4d68e;hpb=78ed9c22a8cbf56ff5390553e0a2854aa42cbbc5;p=lilypond.git

diff --git a/flower/include/array.icc b/flower/include/array.icc
index 8b876ce85d..a84fe937e4 100644
--- a/flower/include/array.icc
+++ b/flower/include/array.icc
@@ -1,5 +1,5 @@
 /*
-  (c) Han-Wen Nienhuys 1995,96,97,98
+  (c) 1995--2005  Han-Wen Nienhuys  <hanwen@cs.uu.nl>
 
   Distributed under GNU GPL
 */
@@ -19,7 +19,7 @@
  */
 
 template<class T> INLINE void 
-arrcpy (T*dest, T*src, int count)
+arrcpy (T*dest, T const* src, int count)
 {
   for (int i_shadows_local=0; i_shadows_local < count ; i_shadows_local++)
 #ifdef __powerpc__
@@ -44,13 +44,12 @@ 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;
+    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) 
     {
@@ -62,7 +61,7 @@ Array<T>::sort (int (*compare)(T const&,T const&),
   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)
+    if (compare (array_[i], array_[lower]) < 0)
       swap (++last,i);
   swap (lower, last);
   sort (compare, lower, last-1);
@@ -79,32 +78,82 @@ Array<T>::reverse ()
 
 template<class T> INLINE
 void
-Array<T>::OK() const
+Array<T>::OK () const
 {
   assert (max_ >= size_ && size_ >=0);
-  if (max_) assert (array_p_);
+  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;
 }
 
 template<class T> INLINE
 Array<T>
-Array<T>::slice (int lower, int upper)
+Array<T>::slice (int lower, int upper) const
 {
   assert (lower >= 0 && lower <=upper&& upper <= size_);
   Array<T> r;
   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 */
+}