stl_algobase.h (lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare)): Move...

2010-03-23  Paolo Carlini  <paolo.carlini@oracle.com>

	* include/bits/stl_algobase.h (lower_bound(_ForwardIterator,
	_ForwardIterator, const _Tp&, _Compare)): Move...
	* include/bits/stl_algo.h: ... here.

From-SVN: r157668

3 files changed, 61 insertions, 55 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 36e44c3..0fbab92 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,7 +1,13 @@
+2010-03-23  Paolo Carlini  <paolo.carlini@oracle.com>
+
+	* include/bits/stl_algobase.h (lower_bound(_ForwardIterator,
+	_ForwardIterator, const _Tp&, _Compare)): Move...
+	* include/bits/stl_algo.h: ... here.
+
 2010-03-22  Johannes Singler  <singler@kit.edu>
 
         * include/parallel/numeric (inner_product, partial_sum):
-        Precede subsequent call with _GLIBCXX_STD_P:: to avoid ambiguity 
+        Precede subsequent call with _GLIBCXX_STD_P:: to avoid ambiguity
         between __gnu_parallel:: and std::
         * include/parallel/algobase.h (equal): Likewise.
         * include/parallel/algo.h (find_first_of, search_n, merge, nth_element,
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 126305a..5b4991e 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2370,6 +2370,60 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
   // lower_bound moved to stl_algobase.h
 
   /**
+   *  @brief Finds the first position in which @a val could be inserted
+   *         without changing the ordering.
+   *  @ingroup binary_search_algorithms
+   *  @param  first   An iterator.
+   *  @param  last    Another iterator.
+   *  @param  val     The search term.
+   *  @param  comp    A functor to use for comparisons.
+   *  @return An iterator pointing to the first element <em>not less
+   *           than</em> @a val, or end() if every element is less
+   *           than @a val.
+   *  @ingroup binary_search_algorithms
+   *
+   *  The comparison function should have the same effects on ordering as
+   *  the function used for the initial sort.
+  */
+  template<typename _ForwardIterator, typename _Tp, typename _Compare>
+    _ForwardIterator
+    lower_bound(_ForwardIterator __first, _ForwardIterator __last,
+		const _Tp& __val, _Compare __comp)
+    {
+      typedef typename iterator_traits<_ForwardIterator>::value_type
+	_ValueType;
+      typedef typename iterator_traits<_ForwardIterator>::difference_type
+	_DistanceType;
+
+      // concept requirements
+      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
+      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
+				  _ValueType, _Tp>)
+      __glibcxx_requires_partitioned_lower_pred(__first, __last,
+						__val, __comp);
+
+      _DistanceType __len = std::distance(__first, __last);
+      _DistanceType __half;
+      _ForwardIterator __middle;
+
+      while (__len > 0)
+	{
+	  __half = __len >> 1;
+	  __middle = __first;
+	  std::advance(__middle, __half);
+	  if (__comp(*__middle, __val))
+	    {
+	      __first = __middle;
+	      ++__first;
+	      __len = __len - __half - 1;
+	    }
+	  else
+	    __len = __half;
+	}
+      return __first;
+    }
+
+  /**
    *  @brief Finds the last position in which @a val could be inserted
    *         without changing the ordering.
    *  @ingroup binary_search_algorithms
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 1756966..e925404 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -985,60 +985,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       return __first;
     }
 
-  /**
-   *  @brief Finds the first position in which @a val could be inserted
-   *         without changing the ordering.
-   *  @ingroup binary_search_algorithms
-   *  @param  first   An iterator.
-   *  @param  last    Another iterator.
-   *  @param  val     The search term.
-   *  @param  comp    A functor to use for comparisons.
-   *  @return An iterator pointing to the first element <em>not less
-   *           than</em> @a val, or end() if every element is less
-   *           than @a val.
-   *  @ingroup binary_search_algorithms
-   *
-   *  The comparison function should have the same effects on ordering as
-   *  the function used for the initial sort.
-  */
-  template<typename _ForwardIterator, typename _Tp, typename _Compare>
-    _ForwardIterator
-    lower_bound(_ForwardIterator __first, _ForwardIterator __last,
-		const _Tp& __val, _Compare __comp)
-    {
-      typedef typename iterator_traits<_ForwardIterator>::value_type
-	_ValueType;
-      typedef typename iterator_traits<_ForwardIterator>::difference_type
-	_DistanceType;
-
-      // concept requirements
-      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
-      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
-				  _ValueType, _Tp>)
-      __glibcxx_requires_partitioned_lower_pred(__first, __last,
-						__val, __comp);
-
-      _DistanceType __len = std::distance(__first, __last);
-      _DistanceType __half;
-      _ForwardIterator __middle;
-
-      while (__len > 0)
-	{
-	  __half = __len >> 1;
-	  __middle = __first;
-	  std::advance(__middle, __half);
-	  if (__comp(*__middle, __val))
-	    {
-	      __first = __middle;
-	      ++__first;
-	      __len = __len - __half - 1;
-	    }
-	  else
-	    __len = __half;
-	}
-      return __first;
-    }
-
   /// This is a helper function for the sort routines and for random.tcc.
   //  Precondition: __n > 0.
   template<typename _Size>