contrib/libc++/include/experimental/algorithm

   1 // -*- C++ -*-
   2 //===-------------------------- algorithm ---------------------------------===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is dual licensed under the MIT and the University of Illinois Open
   7 // Source Licenses. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _LIBCPP_EXPERIMENTAL_ALGORITHM
  12 #define _LIBCPP_EXPERIMENTAL_ALGORITHM
  13
  14 /*
  15    experimental/algorithm synopsis
  16
  17 #include <algorithm>
  18
  19 namespace std {
  20 namespace experimental {
  21 inline namespace fundamentals_v1 {
  22
  23 template <class ForwardIterator, class Searcher>
  24 ForwardIterator search(ForwardIterator first, ForwardIterator last,
  25                        const Searcher &searcher);
  26 template <class PopulationIterator, class SampleIterator, class Distance,
  27           class UniformRandomNumberGenerator>
  28 SampleIterator sample(PopulationIterator first, PopulationIterator last,
  29                       SampleIterator out, Distance n,
  30                       UniformRandomNumberGenerator &&g);
  31
  32 } // namespace fundamentals_v1
  33 } // namespace experimental
  34 } // namespace std
  35
  36 */
  37
  38 #include <experimental/__config>
  39 #include <algorithm>
  40 #include <type_traits>
  41
  42 #include <__undef_min_max>
  43
  44 #include <__debug>
  45
  46 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  47 #pragma GCC system_header
  48 #endif
  49
  50 _LIBCPP_BEGIN_NAMESPACE_LFTS
  51
  52
  53 template <class _PopulationIterator, class _SampleIterator, class _Distance,
  54           class _UniformRandomNumberGenerator>
  55 _LIBCPP_INLINE_VISIBILITY
  56 _SampleIterator __sample(_PopulationIterator __first,
  57                          _PopulationIterator __last, _SampleIterator __out,
  58                          _Distance __n,
  59                          _UniformRandomNumberGenerator &&__g,
  60                          input_iterator_tag) {
  61
  62   _Distance __k = 0;
  63   for (; __first != __last && __k < __n; ++__first, (void)++__k)
  64     __out[__k] = *__first;
  65   _Distance __sz = __k;
  66   for (; __first != __last; ++__first, (void)++__k) {
  67     _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g);
  68     if (__r < __sz)
  69       __out[__r] = *__first;
  70   }
  71   return __out + _VSTD::min(__n, __k);
  72 }
  73
  74 template <class _PopulationIterator, class _SampleIterator, class _Distance,
  75           class _UniformRandomNumberGenerator>
  76 _LIBCPP_INLINE_VISIBILITY
  77 _SampleIterator __sample(_PopulationIterator __first,
  78                          _PopulationIterator __last, _SampleIterator __out,
  79                          _Distance __n,
  80                          _UniformRandomNumberGenerator &&__g,
  81                          forward_iterator_tag) {
  82   _Distance __unsampled_sz = _VSTD::distance(__first, __last);
  83   for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
  84     _Distance __r =
  85         _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g);
  86     if (__r < __n) {
  87       *__out++ = *__first;
  88       --__n;
  89     }
  90   }
  91   return __out;
  92 }
  93
  94 template <class _PopulationIterator, class _SampleIterator, class _Distance,
  95           class _UniformRandomNumberGenerator>
  96 _LIBCPP_INLINE_VISIBILITY
  97 _SampleIterator sample(_PopulationIterator __first,
  98                          _PopulationIterator __last, _SampleIterator __out,
  99                          _Distance __n, _UniformRandomNumberGenerator &&__g) {
 100   typedef typename iterator_traits<_PopulationIterator>::iterator_category
 101         _PopCategory;
 102   typedef typename iterator_traits<_PopulationIterator>::difference_type
 103         _Difference;
 104   typedef typename common_type<_Distance, _Difference>::type _CommonType;
 105   _LIBCPP_ASSERT(__n >= 0, "N must be a positive number.");
 106   return _VSTD_LFTS::__sample(
 107       __first, __last, __out, _CommonType(__n),
 108       _VSTD::forward<_UniformRandomNumberGenerator>(__g),
 109       _PopCategory());
 110 }
 111
 112 _LIBCPP_END_NAMESPACE_LFTS
 113
 114 #endif /* _LIBCPP_EXPERIMENTAL_ALGORITHM */