1// <experimental/algorithm> -*- C++ -*- 2 3// Copyright (C) 2014-2015 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 3, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25/** @file experimental/algorithm 26 * This is a TS C++ Library header. 27 */ 28 29#ifndef _GLIBCXX_EXPERIMENTAL_ALGORITHM 30#define _GLIBCXX_EXPERIMENTAL_ALGORITHM 1 31 32#pragma GCC system_header 33 34#if __cplusplus <= 201103L 35# include <bits/c++14_warning.h> 36#else 37 38#include <algorithm> 39#include <random> 40 41namespace std _GLIBCXX_VISIBILITY(default) 42{ 43namespace experimental 44{ 45inline namespace fundamentals_v1 46{ 47_GLIBCXX_BEGIN_NAMESPACE_VERSION 48 49 template<typename _ForwardIterator, typename _Searcher> 50 inline _ForwardIterator 51 search(_ForwardIterator __first, _ForwardIterator __last, 52 const _Searcher& __searcher) 53 { return __searcher(__first, __last); } 54 55#define __cpp_lib_experimental_sample 201402 56 57 /// Reservoir sampling algorithm. 58 template<typename _InputIterator, typename _RandomAccessIterator, 59 typename _Size, typename _UniformRandomNumberGenerator> 60 _RandomAccessIterator 61 __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, 62 _RandomAccessIterator __out, random_access_iterator_tag, 63 _Size __n, _UniformRandomNumberGenerator&& __g) 64 { 65 using __distrib_type = std::uniform_int_distribution<_Size>; 66 using __param_type = typename __distrib_type::param_type; 67 __distrib_type __d{}; 68 _Size __sample_sz = 0; 69 while (__first != __last && __sample_sz != __n) 70 __out[__sample_sz++] = *__first++; 71 for (auto __pop_sz = __sample_sz; __first != __last; 72 ++__first, ++__pop_sz) 73 { 74 const auto __k = __d(__g, __param_type{0, __pop_sz}); 75 if (__k < __n) 76 __out[__k] = *__first; 77 } 78 return __out + __sample_sz; 79 } 80 81 /// Selection sampling algorithm. 82 template<typename _ForwardIterator, typename _OutputIterator, typename _Cat, 83 typename _Size, typename _UniformRandomNumberGenerator> 84 _OutputIterator 85 __sample(_ForwardIterator __first, _ForwardIterator __last, 86 forward_iterator_tag, 87 _OutputIterator __out, _Cat, 88 _Size __n, _UniformRandomNumberGenerator&& __g) 89 { 90 using __distrib_type = std::uniform_int_distribution<_Size>; 91 using __param_type = typename __distrib_type::param_type; 92 __distrib_type __d{}; 93 _Size __unsampled_sz = std::distance(__first, __last); 94 for (__n = std::min(__n, __unsampled_sz); __n != 0; ++__first) 95 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n) 96 { 97 *__out++ = *__first; 98 --__n; 99 } 100 return __out; 101 } 102 103 /// Take a random sample from a population. 104 template<typename _PopulationIterator, typename _SampleIterator, 105 typename _Distance, typename _UniformRandomNumberGenerator> 106 _SampleIterator 107 sample(_PopulationIterator __first, _PopulationIterator __last, 108 _SampleIterator __out, _Distance __n, 109 _UniformRandomNumberGenerator&& __g) 110 { 111 using __pop_cat = typename 112 std::iterator_traits<_PopulationIterator>::iterator_category; 113 using __samp_cat = typename 114 std::iterator_traits<_SampleIterator>::iterator_category; 115 116 static_assert( 117 __or_<is_convertible<__pop_cat, forward_iterator_tag>, 118 is_convertible<__samp_cat, random_access_iterator_tag>>::value, 119 "output range must use a RandomAccessIterator when input range" 120 " does not meet the ForwardIterator requirements"); 121 122 static_assert(is_integral<_Distance>::value, 123 "sample size must be an integer type"); 124 125 return std::experimental::__sample( 126 __first, __last, __pop_cat{}, __out, __samp_cat{}, 127 __n, std::forward<_UniformRandomNumberGenerator>(__g)); 128 } 129 130_GLIBCXX_END_NAMESPACE_VERSION 131} // namespace fundamentals_v1 132} // namespace experimental 133} // namespace std 134 135#endif // C++14 136 137#endif // _GLIBCXX_EXPERIMENTAL_ALGORITHM 138