release: 1.2.15

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

diff --git a/flower/include/parray.hh b/flower/include/parray.hh
index 94d2e319e32e4a9d6ab9d5274b28a4f204da21f5..a9baeab836c58c7f80c8f4c11c30e380906b24e1 100644 (file)
--- a/flower/include/parray.hh
+++ b/flower/include/parray.hh
@@ -21,7 +21,7 @@
 template<class T>
 class Link_array : private Array<void *>
 {
-  static default_compare (T *const& p1, T  *const&p2) {
+  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 ;
@@ -129,6 +129,25 @@ public:
   Array<void*>::empty;
   Array<void*>::reverse;
   Array<void*>::tighten_maxsize;
+
+  T *& boundary (int d, int i)
+  {
+    assert (d);
+    if (d == 1)
+      return top (i);
+    else
+      return elem_ref (i);
+  }
+  T * boundary (int d, int i)const
+  {
+    assert (d);
+    if (d == 1)
+      return top (i);
+    else
+      return elem_ref (i);
+  }
+
+  
   T ** access_array () const
     {
       return (T**) Array<void*>::access_array();
@@ -207,5 +226,76 @@ junk_pointer_array (Link_array<T> &a)
   a.clear ();
 }
 
+
+
+/*
+  lookup with binsearch, return tokencode.
+*/
+template<class T>
+int
+binsearch_array (Array<T> const &arr, T t, int (*compare)(T const&,T const&))
+{
+  int lo;
+  int hi;
+  int cmp;
+  int result;
+  lo = 0;
+  hi = maxkey;
+
+  /* binary search */
+  do
+  {
+      cmp = (lo + hi) / 2;
+
+      result = compare (t, arr[cmp]);
+
+      if (result < 0)
+          hi = cmp;
+      else
+          lo = cmp;
+    }
+  while (hi - lo > 1);
+  if (!compare (t, arr[lo]))
+    return lo;
+  else
+    return -1;              /* not found */
+}
+
+
+template<class T>
+int
+binsearch_link_array (Link_array<T> const &arr, T *t,
+                     int (*compare)(T *const&,T *const&))
+{
+  int lo;
+  int hi;
+  int cmp;
+  int result;
+  lo = 0;
+  hi = arr.size();
+
+  if (hi == 0)
+    return -1;
+  
+  /* binary search */
+  do
+  {
+      cmp = (lo + hi) / 2;
+
+      result = compare (t, arr[cmp]);
+
+      if (result < 0)
+          hi = cmp;
+      else
+          lo = cmp;
+    }
+  while (hi - lo > 1);
+  if (!compare (t, arr[lo]))
+    return lo;
+  else
+    return -1;              /* not found */
+}
+
+
 #endif // PARRAY_HH