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#include <experimental/lfts_config.h> 41 42namespace std _GLIBCXX_VISIBILITY(default) 43{ 44namespace experimental 45{ 46inline namespace fundamentals_v1 47{ 48_GLIBCXX_BEGIN_NAMESPACE_VERSION 49 50 template<typename _ForwardIterator, typename _Searcher> 51 inline _ForwardIterator 52 search(_ForwardIterator __first, _ForwardIterator __last, 53 const _Searcher& __searcher) 54 { return __searcher(__first, __last); } 55 56#define __cpp_lib_experimental_sample 201402 57 58 /// Reservoir sampling algorithm. 59 template<typename _InputIterator, typename _RandomAccessIterator, 60 typename _Size, typename _UniformRandomNumberGenerator> 61 _RandomAccessIterator 62 __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, 63 _RandomAccessIterator __out, random_access_iterator_tag, 64 _Size __n, _UniformRandomNumberGenerator&& __g) 65 { 66 using __distrib_type = std::uniform_int_distribution<_Size>; 67 using __param_type = typename __distrib_type::param_type; 68 __distrib_type __d{}; 69 _Size __sample_sz = 0; 70 while (__first != __last && __sample_sz != __n) 71 { 72 __out[__sample_sz++] = *__first; 73 ++__first; 74 } 75 for (auto __pop_sz = __sample_sz; __first != __last; 76 ++__first, (void)++__pop_sz) 77 { 78 const auto __k = __d(__g, __param_type{0, __pop_sz}); 79 if (__k < __n) 80 __out[__k] = *__first; 81 } 82 return __out + __sample_sz; 83 } 84 85 /// Selection sampling algorithm. 86 template<typename _ForwardIterator, typename _OutputIterator, typename _Cat, 87 typename _Size, typename _UniformRandomNumberGenerator> 88 _OutputIterator 89 __sample(_ForwardIterator __first, _ForwardIterator __last, 90 forward_iterator_tag, 91 _OutputIterator __out, _Cat, 92 _Size __n, _UniformRandomNumberGenerator&& __g) 93 { 94 using __distrib_type = std::uniform_int_distribution<_Size>; 95 using __param_type = typename __distrib_type::param_type; 96 __distrib_type __d{}; 97 _Size __unsampled_sz = std::distance(__first, __last); 98 for (__n = std::min(__n, __unsampled_sz); __n != 0; ++__first) 99 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n) 100 { 101 *__out++ = *__first; 102 --__n; 103 } 104 return __out; 105 } 106 107 /// Take a random sample from a population. 108 template<typename _PopulationIterator, typename _SampleIterator, 109 typename _Distance, typename _UniformRandomNumberGenerator> 110 _SampleIterator 111 sample(_PopulationIterator __first, _PopulationIterator __last, 112 _SampleIterator __out, _Distance __n, 113 _UniformRandomNumberGenerator&& __g) 114 { 115 using __pop_cat = typename 116 std::iterator_traits<_PopulationIterator>::iterator_category; 117 using __samp_cat = typename 118 std::iterator_traits<_SampleIterator>::iterator_category; 119 120 static_assert( 121 __or_<is_convertible<__pop_cat, forward_iterator_tag>, 122 is_convertible<__samp_cat, random_access_iterator_tag>>::value, 123 "output range must use a RandomAccessIterator when input range" 124 " does not meet the ForwardIterator requirements"); 125 126 static_assert(is_integral<_Distance>::value, 127 "sample size must be an integer type"); 128 129 typename iterator_traits<_PopulationIterator>::difference_type __d = __n; 130 return std::experimental::__sample( 131 __first, __last, __pop_cat{}, __out, __samp_cat{}, 132 __d, std::forward<_UniformRandomNumberGenerator>(__g)); 133 } 134 135_GLIBCXX_END_NAMESPACE_VERSION 136} // namespace fundamentals_v1 137} // namespace experimental 138} // namespace std 139 140#endif // C++14 141 142#endif // _GLIBCXX_EXPERIMENTAL_ALGORITHM 143