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 60caa43..5b4991e 100644 (file)
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -62,6 +62,10 @@
 #include <bits/stl_heap.h>
 #include <bits/stl_tempbuf.h>  // for _Temporary_buffer
 
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#include <random> // for std::uniform_int_distribution
+#endif
+
 // See concept_check.h for the __glibcxx_*_requires macros.
 
 _GLIBCXX_BEGIN_NAMESPACE(std)
@@ -2301,29 +2305,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
        }
     }
 
-  /// This is a helper function for the sort routines.  Precondition: __n > 0.
-  template<typename _Size>
-    inline _Size
-    __lg(_Size __n)
-    {
-      _Size __k;
-      for (__k = 0; __n != 0; __n >>= 1)
-       ++__k;
-      return __k - 1;
-    }
-
-  inline int
-  __lg(int __n)
-  { return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }
-
-  inline long
-  __lg(long __n)
-  { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
-
-  inline long long
-  __lg(long long __n)
-  { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
-
   // sort
 
   template<typename _RandomAccessIterator, typename _Size>
@@ -2386,52 +2367,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 
   // nth_element
 
-  /**
-   *  @brief Finds the first position in which @a val could be inserted
-   *         without changing the ordering.
-   *  @param  first   An iterator.
-   *  @param  last    Another iterator.
-   *  @param  val     The search term.
-   *  @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
-  */
-  template<typename _ForwardIterator, typename _Tp>
-    _ForwardIterator
-    lower_bound(_ForwardIterator __first, _ForwardIterator __last,
-               const _Tp& __val)
-    {
-      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(_LessThanOpConcept<_ValueType, _Tp>)
-      __glibcxx_requires_partitioned_lower(__first, __last, __val);
-
-      _DistanceType __len = std::distance(__first, __last);
-      _DistanceType __half;
-      _ForwardIterator __middle;
-
-      while (__len > 0)
-       {
-         __half = __len >> 1;
-         __middle = __first;
-         std::advance(__middle, __half);
-         if (*__middle < __val)
-           {
-             __first = __middle;
-             ++__first;
-             __len = __len - __half - 1;
-           }
-         else
-           __len = __half;
-       }
-      return __first;
-    }
+  // lower_bound moved to stl_algobase.h
 
   /**
    *  @brief Finds the first position in which @a val could be inserted
@@ -4141,7 +4077,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       return std::make_pair(__min, __max);
     }
 
-  // N2722 + fixes.
+  // N2722 + DR 915.
   template<typename _Tp>
     inline _Tp
     min(initializer_list<_Tp> __l)
@@ -4179,6 +4115,47 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
        std::minmax_element(__l.begin(), __l.end(), __comp);
       return std::make_pair(*__p.first, *__p.second);
     }
+
+#ifdef _GLIBCXX_USE_C99_STDINT_TR1
+  /**
+   *  @brief Shuffle the elements of a sequence using a uniform random
+   *         number generator.
+   *  @ingroup mutating_algorithms
+   *  @param  first   A forward iterator.
+   *  @param  last    A forward iterator.
+   *  @param  g       A UniformRandomNumberGenerator (26.5.1.3).
+   *  @return  Nothing.
+   *
+   *  Reorders the elements in the range @p [first,last) using @p g to
+   *  provide random numbers.
+  */
+  template<typename _RandomAccessIterator,
+          typename _UniformRandomNumberGenerator>
+    void
+    shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
+           _UniformRandomNumberGenerator& __g)
+    {
+      // concept requirements
+      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
+           _RandomAccessIterator>)
+      __glibcxx_requires_valid_range(__first, __last);
+
+      if (__first == __last)
+       return;
+
+      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+       _DistanceType;
+
+      typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
+      typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
+      typedef typename __distr_type::param_type __p_type;
+      __distr_type __d;
+
+      for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+       std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
+    }
+#endif
+
 #endif // __GXX_EXPERIMENTAL_CXX0X__
 
 _GLIBCXX_END_NAMESPACE
@@ -4996,7 +4973,11 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
   template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
     void
     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+                  _RandomNumberGenerator&& __rand)
+#else
                   _RandomNumberGenerator& __rand)
+#endif
     {
       // concept requirements
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<