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

[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / stl_algo.h

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 2f96d06..5b4991e 100644 (file)
--- 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
@@ -4079,7 +4133,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
           typename _UniformRandomNumberGenerator>
     void
     shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
-           _UniformRandomNumberGenerator&& __g)
+           _UniformRandomNumberGenerator& __g)
     {
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<