release: 1.2.15

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

diff --git a/flower/include/parray.hh b/flower/include/parray.hh
index 79ef5e6a7f6d258b32ec478f0fab8035b397cd53..a9baeab836c58c7f80c8f4c11c30e380906b24e1 100644 (file)
--- a/flower/include/parray.hh
+++ b/flower/include/parray.hh
@@ -3,7 +3,7 @@
 
   source file of the Flower Library
 
-  (c)  1997--1998 Han-Wen Nienhuys <hanwen@cs.uu.nl>
+  (c)  1997--1999 Han-Wen Nienhuys <hanwen@cs.uu.nl>
 */
 
 
@@ -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 ;
@@ -36,6 +36,12 @@ class Link_array : private Array<void *>
 public:
   Link_array()
     {}
+
+  Link_array(T * const *tp, int n)
+    : Array<void*> ((void **)tp, n)
+    {
+    }
+
   Link_array (Link_array<T> const &src)
     : Array<void*> (src)
     {
@@ -121,7 +127,31 @@ public:
   Array<void*>::clear;
   Array<void*>::set_size;
   Array<void*>::empty;
-  Array<void*>::reverse;  
+  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();
+    }
   T * get (int i)
     {
       return (T*) Array<void*>::get (i);
@@ -185,5 +215,87 @@ Link_array<T>::sort (int (*compare)(T *const&,T *const&),
   sort (compare, last+1, upper);
 }
 
+template<class T>
+void
+junk_pointer_array (Link_array<T> &a)
+{
+  for (int i=0; i < a.size ();  i++)
+    {
+      delete a[i];
+    }
+  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