X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=flower%2Finclude%2Fstd-vector.hh;h=4c3dcc0e0e8f61ae506d8672cf81073b0799759b;hb=dc3017bfda1b00bc3853ce46b846ff0bba2b8a2c;hp=83e58d299ccbc180babe5a7f2aa34f2b1a5dbca7;hpb=9f3572d98bb948c9689cd1f75401a029451fa001;p=lilypond.git

diff --git a/flower/include/std-vector.hh b/flower/include/std-vector.hh
index 83e58d299c..4c3dcc0e0e 100644
--- a/flower/include/std-vector.hh
+++ b/flower/include/std-vector.hh
@@ -3,12 +3,22 @@
 
   source file of the GNU LilyPond music typesetter
 
-  (c) 2006 Jan Nieuwenhuizen <janneke@gnu.org>
+  (c) 2006--2007 Jan Nieuwenhuizen <janneke@gnu.org>
 */
 
 #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>
@@ -132,146 +142,66 @@ concat (vector<T> &v, vector<T> const& w)
   v.insert (v.end (), w.begin (), w.end ());
 }
 
-template<class T>
-void
-binary_search_bounds (vector<T> const &table,
-		      T const &key, int (*compare) (T const &, T const &),
-		      vsize *lo,
-		      vsize *hi)
+template<typename T, typename Compare>
+vsize
+lower_bound (vector<T> const &v,
+	     T const &key,
+	     Compare less,
+	     vsize b=0, vsize e=VPOS)
 {
-  if (*lo >= *hi)
-    return;
-
-  int cmp;
-  int result;
-
-  /* binary search */
-  do
-    {
-      cmp = (*lo + *hi) / 2;
-
-      result = (*compare) (key, table[cmp]);
+  if (e == VPOS)
+    e = v.size ();
+  typename vector<T>::const_iterator i = lower_bound (v.begin () + b,
+						      v.begin () + e,
+						      key,
+						      less);
 
-      if (result < 0)
-	*hi = cmp;
-      else
-	*lo = cmp;
-    }
-  while (*hi - *lo > 1);
+  return i - v.begin ();
 }
 
-template<typename T>
-void
-binary_search_bounds (vector<T*> const &table,
-		      T const *key, int (*compare) (T *const &, T *const &),
-		      vsize *lo,
-		      vsize *hi)
+template<typename T, typename Compare>
+vsize
+upper_bound (vector<T> const &v,
+	     T const &key,
+	     Compare less,
+	     vsize b=0, vsize e=VPOS)
 {
-  vsize cmp;
-  int result;
-
-  /* binary search */
-  do
-    {
-      cmp = (*lo + *hi) / 2;
+  if (e == VPOS)
+    e = v.size ();
 
-      result = (*compare) ((T *) key, table[cmp]);
+  typename vector<T>::const_iterator i = upper_bound (v.begin () + b,
+						      v.begin () + e,
+						      key,
+						      less);
 
-      if (result < 0)
-	*hi = cmp;
-      else
-	*lo = cmp;
-    }
-  while (*hi - *lo > 1);
+  return i - v.begin ();
 }
 
-#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>
+template<typename T, typename Compare>
 vsize
 binary_search (vector<T> const &v,
-	       T const &key, int (*compare) (T const &, T const &),
-	       vsize b=0, vsize e=VPOS)
-{
-  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)
+	       Compare less=less<T> (),
+	       vsize b=0, vsize e=VPOS)
 {
-  if (hi == VPOS)
-    hi = table.size ();
+  vsize lb = lower_bound (v, key, less, b, e);
 
-  if (lo >= hi)
+  if (lb == v.size () || less (key, v[lb]))
     return VPOS;
-
-  binary_search_bounds (table, key, compare, &lo, &hi);
-
-  if (! (*compare) (key, table[lo]))
-    return lo;
-
-  /* not found */
-  return VPOS;
+  return lb;
 }
 
-
-#endif
-
-
-#if 0
-/* FIXME: the COMPARE functionality is broken?  */
-template<typename T>
+template<typename T, typename Compare>
 void
-vector_sort (vector<T> &v, int (*compare) (T const &, T const &),
-	     vsize lower=VPOS, vsize upper=VPOS)
+vector_sort (vector<T> &v,
+	     Compare less,
+	     vsize b=0, vsize e=VPOS)
 {
-  typename vector<T>::iterator b = v.begin ();
-  typename vector<T>::iterator e = v.begin ();
-  if (lower == VPOS)
-    {
-      lower = 0;
-      upper = v.size ();
-    }
-  sort (b + lower, e + upper, compare);
-}
-#else
+  if (e == VPOS)
+    e = v.size ();
 
-// ugh, c&p
-template<typename T> void
-vector_sort (vector<T> &v, int (*compare) (T const &, T const &),
-	     vsize lower=VPOS, vsize upper=VPOS)
-{
-  if (lower == VPOS)
-    {
-      lower = 0;
-      upper = v.size () - 1;
-    }
-  if (upper == VPOS || lower >= upper)
-    return;
-  swap (v[lower], v[(lower + upper) / 2]);
-  vsize last = lower;
-  for (vsize i = lower +1; i <= upper; i++)
-    if (compare (v[i], v[lower]) < 0)
-      swap (v[++last], v[i]);
-  swap (v[lower], v[last]);
-  vector_sort (v, compare, lower, last - 1);
-  vector_sort (v, compare, last + 1, upper);
+  sort (v.begin () + b, v.begin () + e, less);
 }
-#endif
 
 template<typename T>
 void