2010-09-01 Christopher Yeleighton <giecrilj@stegny.2a.pl>

[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 126305a..456c536 100644 (file)
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2370,6 +2370,58 @@ _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);
+
+      while (__len > 0)
+       {
+         _DistanceType __half = __len >> 1;
+         _ForwardIterator __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
@@ -2396,13 +2448,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       __glibcxx_requires_partitioned_upper(__first, __last, __val);
 
       _DistanceType __len = std::distance(__first, __last);
-      _DistanceType __half;
-      _ForwardIterator __middle;
 
       while (__len > 0)
        {
-         __half = __len >> 1;
-         __middle = __first;
+         _DistanceType __half = __len >> 1;
+         _ForwardIterator __middle = __first;
          std::advance(__middle, __half);
          if (__val < *__middle)
            __len = __half;
@@ -2449,13 +2499,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
                                                __val, __comp);
 
       _DistanceType __len = std::distance(__first, __last);
-      _DistanceType __half;
-      _ForwardIterator __middle;
 
       while (__len > 0)
        {
-         __half = __len >> 1;
-         __middle = __first;
+         _DistanceType __half = __len >> 1;
+         _ForwardIterator __middle = __first;
          std::advance(__middle, __half);
          if (__comp(__val, *__middle))
            __len = __half;
@@ -2504,13 +2552,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       __glibcxx_requires_partitioned_upper(__first, __last, __val);      
 
       _DistanceType __len = std::distance(__first, __last);
-      _DistanceType __half;
-      _ForwardIterator __middle, __left, __right;
-
+ 
       while (__len > 0)
        {
-         __half = __len >> 1;
-         __middle = __first;
+         _DistanceType __half = __len >> 1;
+         _ForwardIterator __middle = __first;
          std::advance(__middle, __half);
          if (*__middle < __val)
            {
@@ -2522,9 +2568,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
            __len = __half;
          else
            {
-             __left = std::lower_bound(__first, __middle, __val);
+             _ForwardIterator __left = std::lower_bound(__first, __middle,
+                                                        __val);
              std::advance(__first, __len);
-             __right = std::upper_bound(++__middle, __first, __val);
+             _ForwardIterator __right = std::upper_bound(++__middle, __first,
+                                                         __val);
              return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
            }
        }
@@ -2551,8 +2599,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
   template<typename _ForwardIterator, typename _Tp, typename _Compare>
     pair<_ForwardIterator, _ForwardIterator>
     equal_range(_ForwardIterator __first, _ForwardIterator __last,
-               const _Tp& __val,
-               _Compare __comp)
+               const _Tp& __val, _Compare __comp)
     {
       typedef typename iterator_traits<_ForwardIterator>::value_type
        _ValueType;
@@ -2571,13 +2618,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
                                                __val, __comp);
 
       _DistanceType __len = std::distance(__first, __last);
-      _DistanceType __half;
-      _ForwardIterator __middle, __left, __right;
 
       while (__len > 0)
        {
-         __half = __len >> 1;
-         __middle = __first;
+         _DistanceType __half = __len >> 1;
+         _ForwardIterator __middle = __first;
          std::advance(__middle, __half);
          if (__comp(*__middle, __val))
            {
@@ -2589,9 +2634,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
            __len = __half;
          else
            {
-             __left = std::lower_bound(__first, __middle, __val, __comp);
+             _ForwardIterator __left = std::lower_bound(__first, __middle,
+                                                        __val, __comp);
              std::advance(__first, __len);
-             __right = std::upper_bound(++__middle, __first, __val, __comp);
+             _ForwardIterator __right = std::upper_bound(++__middle, __first,
+                                                         __val, __comp);
              return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
            }
        }
@@ -4079,7 +4126,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
           typename _UniformRandomNumberGenerator>
     void
     shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
-           _UniformRandomNumberGenerator& __g)
+           _UniformRandomNumberGenerator&& __g)
     {
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
@@ -4790,7 +4837,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
             // "the type returned by a _Generator"
             __typeof__(__gen())>)
 
-      for (; __n > 0; --__n, ++__first)
+      for (__decltype(__n + 0) __niter = __n;
+          __niter > 0; --__niter, ++__first)
        *__first = __gen();
       return __first;
     }