release: 1.2.15

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

diff --git a/flower/include/parray.hh b/flower/include/parray.hh
index 77a69b519a1d87bd4725cb745e813b718c848042..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>
 */
 
 
@@ -16,12 +16,12 @@
   an array of pointers.
 
   TODO
-  should init to 0. Derive from Array<void*>? 
+  should init to 0.
  */
 template<class T>
-class Link_array : public Array<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 ;
@@ -29,13 +29,70 @@ class Link_array : public Array<T*>
       return 1;
     return 0;
   }
+  Link_array (Array<void*> v)
+    :Array<void*> (v)
+    {
+    }
 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)
+    {
+    }
+  /// access element
+  T *elem (int i) const 
+    {
+      return elem_ref (i);
+    }
+  T *&elem_ref  (int i) const
+    {
+      return (T*&) Array<void*>::elem_ref (i);
+    }
+
+  /// access element
+  T* &operator[] (int i)  
+    {
+      return (T*&) Array<void*>::elem_ref (i);
+    }
+  /// access element
+  T *const operator[] (int i) const 
+    {
+      return (T *const) Array<void*>::elem (i);
+    }
+  T *pop ()
+    {
+      return (T*) Array<void*>::pop ();
+    }
+  void insert (T *t, int i)
+    {
+      Array<void*>::insert (t, i);
+    }
+  void push (T* t)
+    {
+      Array<void*>::push (t);
+    }
+  /// return last entry
+  T* top (int j=0) const 
+    {
+      return (T*) Array<void*>::top (j);
+    }
+  T *& top (int i=0)
+    {
+      return (T*&) Array<void*>::top (i);
+    }
   void substitute (T *old, T*new_l)
     {
       int i;
       while ((i = find_i (old)) >=0) 
        if (new_l)
-         elem (i) =new_l;
+         elem_ref (i) =new_l;
        else
          del (i);
     }
@@ -44,7 +101,7 @@ public:
       int i;
       while ((i = find_i (old)) >=0) 
        if (new_l)
-         elem (i) =new_l;
+         elem_ref (i) =new_l;
        else {
          unordered_del (i);
        }
@@ -53,6 +110,10 @@ public:
   void default_sort() {
     sort (default_compare);
   }
+  // quicksort.
+  void sort (int (*compare)(T *const&,T *const&),
+            int lower = -1, int upper = -1);
+  
   void uniq() {
     Link_array<T> l_arr;
     for (int i=0; i < size(); i++) 
@@ -60,7 +121,50 @@ public:
        l_arr.push (elem (i)); 
     *this = l_arr;
   }
+  Array<void*>::del;
+  Array<void*>::unordered_del;  
+  Array<void*>::size;
+  Array<void*>::clear;
+  Array<void*>::set_size;
+  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();
+    }
+  T * get (int i)
+    {
+      return (T*) Array<void*>::get (i);
+    }
+  Link_array<T>
+  slice(int l,int u)
+    {
+      return Array<void*>::slice (l,u);
+    }
+  void concat (Link_array<T> const &a2)
+    {
+      Array<void*>::concat (a2);
+    }
   int find_i (T const * t) const {
     for (int i=0; i < size(); i++)
       if (elem (i) == t)
@@ -75,6 +179,7 @@ public:
       else
        return 0;
     }
+  
 };
 
 template<class T, class V>
@@ -88,5 +193,109 @@ typecast_array (Link_array<V> const &a, T * /* dummy */ )
 }
 
 
+
+template<class T> inline void
+Link_array<T>::sort (int (*compare)(T *const&,T *const&),
+               int lower = -1, int upper = -1) 
+{
+  if (lower < 0) 
+    {
+      lower = 0 ;
+      upper = size () - 1;
+    }
+  if (lower >= upper)
+    return;
+  swap (lower, (lower+upper)/2);
+  int last = lower;
+  for (int i= lower +1; i <= upper; i++)
+    if (compare (elem (i), elem(lower)) < 0)
+      swap (++last,i);
+  swap (lower, last);
+  sort (compare, lower, last-1);
+  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