2003 -> 2004

[lilypond.git] / flower / include / parray.hh

diff --git a/flower/include/parray.hh b/flower/include/parray.hh
index eb259ede4b7e306bac75884ec50e49e89b0c1ace..decf7b6681e16326d538333afce12a3b9c260cea 100644 (file)
--- a/flower/include/parray.hh
+++ b/flower/include/parray.hh
@@ -3,7 +3,7 @@
 
   source file of the Flower Library
 
-  (c)  1997--2000 Han-Wen Nienhuys <hanwen@cs.uu.nl>
+  (c) 1997--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
 */
 
 
@@ -12,6 +12,8 @@
 
 #include "array.hh"
 
+
+
 /**
   an array of pointers.
 
@@ -21,14 +23,7 @@
 template<class T>
 class Link_array : private Array<void *>
 {
-  static int default_compare (T *const& p1, T  *const&p2) {
-    /* can't do p1 -p2, since T might be an incomplete type */
-    if (p1 < p2)
-      return -1 ;
-    if (p2 < p1)
-      return 1;
-    return 0;
-  }
+
   Link_array (Array<void*> v)
     :Array<void*> (v)
     {
@@ -37,6 +32,15 @@ public:
   Link_array ()
     {}
 
+  static int default_compare (T *const& p1, T  *const&p2)
+  {
+    /* can't do p1 -p2, since T might be an incomplete type */
+    if (p1 < p2)
+      return -1 ;
+    if (p2 < p1)
+      return 1;
+    return 0;
+  }
   Link_array (T * const *tp, int n)
     : Array<void*> ((void **)tp, n)
     {
@@ -87,21 +91,21 @@ public:
     {
       return (T*&) Array<void*>::top (i);
     }
-  void substitute (T *old, T*new_l)
+  void substitute (T *old, T*new_p)
     {
       int i;
-      while ((i = find_i (old)) >=0) 
-       if (new_l)
-         elem_ref (i) =new_l;
+      while ((i = find_index (old)) >=0) 
+       if (new_p)
+         elem_ref (i) =new_p;
        else
          del (i);
     }
-  void unordered_substitute (T* old, T * new_l)
+  void unordered_substitute (T* old, T * new_p)
     {
       int i;
-      while ((i = find_i (old)) >=0) 
-       if (new_l)
-         elem_ref (i) =new_l;
+      while ((i = find_index (old)) >=0) 
+       if (new_p)
+         elem_ref (i) =new_p;
        else {
          unordered_del (i);
        }
@@ -115,11 +119,11 @@ public:
             int lower = -1, int upper = -1);
   
   void uniq () {
-    Link_array<T> l_arr;
+    Link_array<T> ls;
     for (int i=0; i < size (); i++) 
       if (!i || elem (i-1) != elem (i))
-       l_arr.push (elem (i)); 
-    *this = l_arr;
+       ls.push (elem (i)); 
+    *this = ls;
   }
   Array<void*>::del;
   Array<void*>::unordered_del;  
@@ -148,9 +152,9 @@ public:
   }
 
   
-  T ** access_array () const
+  T ** accesses () const
     {
-      return (T**) Array<void*>::access_array ();
+      return (T**) Array<void*>::accesses ();
     }
   T * get (int i)
     {
@@ -165,26 +169,25 @@ public:
     {
       Array<void*>::concat (a2);
     }
-  int find_i (T const * t) const {
+  int find_index (T const * t) const {
     for (int i=0; i < size (); i++)
       if (elem (i) == t)
        return i;
     return -1;
   }
-  T *find_l (T const *t) const
+  T *find (T const *t) const
     {
-      int i = find_i (t);
+      int i = find_index (t);
       if (i >= 0)
        return elem (i);
       else
        return 0;
     }
-  
 };
 
 template<class T, class V>
 Link_array<T>
-typecast_array (Link_array<V> const &a, T * /* dummy */ )
+typecasts (Link_array<V> const &a, T * /* dummy */ )
 {
   Link_array<T> ret;
   for (int i=a.size (); i-- ; )
@@ -216,7 +219,7 @@ Link_array<T>::sort (int (*compare)(T *const&,T *const&), int lower, int upper)
 
 template<class T>
 void
-junk_pointer_array (Link_array<T> &a)
+junk_pointers (Link_array<T> &a)
 {
   for (int i=0; i < a.size ();  i++)
     {
@@ -232,7 +235,7 @@ junk_pointer_array (Link_array<T> &a)
 */
 template<class T>
 int
-binsearch_array (Array<T> const &arr, T t, int (*compare) (T const&,T const&))
+binsearchs (Array<T> const &arr, T t, int (*compare) (T const&,T const&))
 {
   int lo;
   int hi;
@@ -263,7 +266,7 @@ binsearch_array (Array<T> const &arr, T t, int (*compare) (T const&,T const&))
 
 template<class T>
 int
-binsearch_link_array (Link_array<T> const &arr, T *t,
+binsearch_links (Link_array<T> const &arr, T *t,
                      int (*compare) (T *const&,T *const&),
                      int lo = 0, int hi = -1 )
 {
@@ -295,5 +298,30 @@ binsearch_link_array (Link_array<T> const &arr, T *t,
 }
 
 
+template<class T>
+void
+binary_search_bounds (Link_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)  ((T*) key, table[cmp]);
+
+      if (result < 0)
+          *hi = cmp;
+      else
+          *lo = cmp;
+    }
+  while (*hi - *lo > 1);
+}
+
 #endif // PARRAY_HH