Run `make grand-replace'.

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

diff --git a/flower/include/std-vector.hh b/flower/include/std-vector.hh
index 83e58d299ccbc180babe5a7f2aa34f2b1a5dbca7..76a11bb9252237189463c667290df2cd01ecc183 100644 (file)
--- a/flower/include/std-vector.hh
+++ b/flower/include/std-vector.hh
@@ -3,19 +3,30 @@
 
   source file of the GNU LilyPond music typesetter
 
-  (c) 2006 Jan Nieuwenhuizen <janneke@gnu.org>
+  (c) 2006--2008 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>
+#include <string>
 
 using namespace std;
 
-#if HAVE_BOOST_LAMBDA
+#if HAVE_BOOST_LAMBDA_LAMBDA_HPP
 #include <boost/lambda/lambda.hpp>
 #endif
 
@@ -132,146 +143,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
@@ -296,7 +227,7 @@ find (vector<T> const &v, T const &key)
   return find (v.begin (), v.end (), key);
 }
 
-#if HAVE_BOOST_LAMBDA
+#if HAVE_BOOST_LAMBDA_LAMBDA_HPP
 #include <boost/lambda/lambda.hpp>
 using namespace boost::lambda;
 template<typename T>
@@ -328,6 +259,7 @@ junk_pointers (vector<T> &v)
 #endif /* HAVE_BOOST_LAMBDA */
 
 vector<string> string_split (string str, char c);
+string string_join (vector<string> const &strs, string infix);
 
 #define iterof(i,s) typeof((s).begin()) i((s).begin())