Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  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.  
  41. namespace std _GLIBCXX_VISIBILITY(default)
  42. {
  43. namespace experimental
  44. {
  45. inline 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.