Fix some bugs in the dynamic engraver and PostScript backend

[lilypond.git] / flower / include / std-vector.hh

diff --git a/flower/include/std-vector.hh b/flower/include/std-vector.hh
index da3686a07c813eb7ab036d3e151c7c6af762d4ee..83e58d299ccbc180babe5a7f2aa34f2b1a5dbca7 100644 (file)
--- a/flower/include/std-vector.hh
+++ b/flower/include/std-vector.hh
@@ -9,16 +9,6 @@
 #ifndef STD_VECTOR_HH
 #define STD_VECTOR_HH
 
-#if 0
-
-/*
-  leads to dubious crashes - libstdc++  bug?
-*/
-#ifndef NDEBUG
-#define _GLIBCXX_DEBUG 1
-#endif
-#endif
-
 #include <algorithm>   /* find, reverse, sort */
 #include <functional>  /* unary_function */
 #include <cassert>
@@ -142,55 +132,106 @@ concat (vector<T> &v, vector<T> const& w)
   v.insert (v.end (), w.begin (), w.end ());
 }
 
-template<typename T, typename Compare>
-vsize
-lower_bound (vector<T> const &v,
-            T const &key,
-            Compare less,
-            vsize b=0, vsize e=VPOS)
+template<class T>
+void
+binary_search_bounds (vector<T> const &table,
+                     T const &key, int (*compare) (T const &, T const &),
+                     vsize *lo,
+                     vsize *hi)
 {
-  if (e == VPOS)
-    e = v.size ();
-  typename vector<T>::const_iterator i = lower_bound (v.begin () + b,
-                                                     v.begin () + e,
-                                                     key,
-                                                     less);
+  if (*lo >= *hi)
+    return;
+
+  int cmp;
+  int result;
+
+  /* binary search */
+  do
+    {
+      cmp = (*lo + *hi) / 2;
+
+      result = (*compare) (key, table[cmp]);
 
-  return i - v.begin ();
+      if (result < 0)
+       *hi = cmp;
+      else
+       *lo = cmp;
+    }
+  while (*hi - *lo > 1);
 }
 
-template<typename T, typename Compare>
-vsize
-upper_bound (vector<T> const &v,
-            T const &key,
-            Compare less,
-            vsize b=0, vsize e=VPOS)
+template<typename T>
+void
+binary_search_bounds (vector<T*> const &table,
+                     T const *key, int (*compare) (T *const &, T *const &),
+                     vsize *lo,
+                     vsize *hi)
 {
-  if (e == VPOS)
-    e = v.size ();
+  vsize cmp;
+  int result;
+
+  /* binary search */
+  do
+    {
+      cmp = (*lo + *hi) / 2;
 
-  typename vector<T>::const_iterator i = upper_bound (v.begin () + b,
-                                                     v.begin () + e,
-                                                     key,
-                                                     less);
+      result = (*compare) ((T *) key, table[cmp]);
 
-  return i - v.begin ();
+      if (result < 0)
+       *hi = cmp;
+      else
+       *lo = cmp;
+    }
+  while (*hi - *lo > 1);
 }
 
-template<typename T, typename Compare>
+#if 0
+/* FIXME: what if COMPARE is named: int operator == (T const&, T const&),
+   wouldn't that work for most uses of BINARY_SEARCH?
+*/
+template<typename T>
 vsize
 binary_search (vector<T> const &v,
-              T const &key,
-              Compare less=less<T> (),
+              T const &key, int (*compare) (T const &, T const &),
               vsize b=0, vsize e=VPOS)
 {
-  vsize lb = lower_bound (v, key, less, b, e);
+  if (e == VPOS)
+    e = v.size ();
+  typename vector<T>::const_iterator i = find (v.begin () + b,
+                                              v.begin () + e,
+                                              key);
+  if (i != v.end ())
+    return i - v.begin ();
+  return VPOS;
+}
+#else // c&p from array.icc; cannot easily use stl_algo:find b.o. compare func.
+template<class T>
+vsize
+binary_search (vector<T> const &table,
+              T const &key,
+              int (*compare) (T const &, T const &),
+              vsize lo=0,
+              vsize hi=VPOS)
+{
+  if (hi == VPOS)
+    hi = table.size ();
 
-  if (lb == v.size () || less (key, v[lb]))
+  if (lo >= hi)
     return VPOS;
-  return lb;
+
+  binary_search_bounds (table, key, compare, &lo, &hi);
+
+  if (! (*compare) (key, table[lo]))
+    return lo;
+
+  /* not found */
+  return VPOS;
 }
 
+
+#endif
+
+
 #if 0
 /* FIXME: the COMPARE functionality is broken?  */
 template<typename T>