random

// n3925: A sample Proposal, v4

// Additions to <algorithm>

// Code from paper.  These are from SGI code and we might have them in ext.
// Check this: gcc/libstdc++-v3/include/ext/algorithm
// <experimental/tuple> -*- C++ -*-

// Copyright (C) 2014 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file experimental/random
 *  This is a TS C++ Library header.
 */

#ifndef _GLIBCXX_EXPERIMENTAL_RANDOM
#define _GLIBCXX_EXPERIMENTAL_RANDOM 1

#pragma GCC system_header

#if __cplusplus <= 201103L
# include <bits/c++14_warning.h>
#else

#define __cpp_lib_sample 201402L

namespace std _GLIBCXX_VISIBILITY(default)
{
namespace experimental
{
inline namespace fundamentals_v1
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

namespace __detail
{
  template<typename _PopIter, typename _SampleIter, typename _Size,
	   typename _URNG>
    _SampleIter
    __sample(_PopIter __first, _PopIter __last, std::input_iterator_tag,
	     _SampleIter __out, std::random_access_iterator_tag,
	     _Size __n, _URNG&& __urng);

  template<typename _PopIter, typename _SampleIter, typename _Size,
	   typename _URNG>
    _SampleIter
    __sample(_PopIter __first, _PopIter __last, std::forward_iterator_tag,
	     _SampleIter __out, std::output_iterator_tag,
	     _Size __n, _URNG&& __urng);
}

  ///
  ///  Select __n samples from a population of range [__first, __last)
  ///  and store them in the sample range beginning at __out.
  ///  Return the end of the sample range.
  ///
  template<typename _PopIter, typename _SampleIter, typename _Size,
	   typename _URNG>
    inline _SampleIter
    sample(_PopIter __first, _PopIter __last, _SampleIter __out, _Size __n,
	   _URNG&& __urng)
    {
      using __pop_t = typename std::iterator_traits<_PopIter>
			::iterator_category;
      using __samp_t = typename std::iterator_traits<_SampleIter>
			::iterator_category;

      return __detail::__sample(__first, __last, __pop_t{}, __out, __samp_t{},
				__n, std::forward<_URNG>(__urng));
    }

namespace __detail
{
  //  Reservoir sampling.
  template<typename _PopIter, typename _SampleIter, typename _Size,
	   typename _URNG>
    _SampleIter
    __sample(_PopIter __first, _PopIter __last, std::input_iterator_tag,
	     _SampleIter __out, std::random_access_iterator_tag,
	     _Size __n, _URNG&& __urng)
    {
      using __dist_t = std::uniform_int_distribution<_Size>;
      using __param_t = typename __dist_t::param_type;

      __dist_t __dist{};
      _Size __sample_sz{};
      while (__first != __last && __sample_sz != __n)
	__out[__sample_sz++] = *__first++;
      for (_Size __pop_sz{__sample_sz}; __first != __last;
	   ++__first, ++__pop_sz )
	{
	  __param_t const __param{0, __pop_sz};
	  _Size __k{__dist(__urng, __param)};
	  if (__k < __n)
	    __out[__k] = *__first;
	}
      return __out + __sample_sz;
    }

  //  Selection sampling.
  template<typename _PopIter, typename _SampleIter, typename _Size,
	   typename _URNG>
    _SampleIter
    __sample(_PopIter __first, _PopIter __last, std::forward_iterator_tag,
	     _SampleIter __out, std::output_iterator_tag,
	     _Size __n, _URNG&& __urng)
    {
      using __dist_t = std::uniform_int_distribution<_Size>;
      using __param_t = typename __dist_t::param_type;

      __dist_t __dist{};
      _Size __unsampled_sz = std::distance(__first, __last);
      for (__n = std::min(__n, __unsampled_sz); __n != 0; ++__first)
	{
	  const __param_t __param{0, --__unsampled_sz};
	  if (__dist(__urng, __param) < __n )
	    {
	      *__out++ = *__first;
	      --__n;
	    }
	}
      return __out;
    }
}

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace fundamentals_v1
} // namespace experimental
} // namespace std

#endif // C++14

#endif // _GLIBCXX_EXPERIMENTAL_RANDOM










/*

// Additions to <random>:

// Could the function static variables be thread_local?  Is there an advantage?
// Yes! Good call! These are in a later version.

  namespace __detail
  {
    inline auto&
    global_urng()
    {
      static thread_local std::default_random_engine __urng{};

      return __urng;
    }
  }


  // 26.5.7.3, function template randint
  template<typename _IntType>
    IntType randint(_IntType __a, _IntType __b)
    {
      static std::uniform_int_distribution<_IntType> __uid{};

      using __parm_t = decltype(__uid)::param_type;

      return __uid(__detail::global_urng(), __parm_t{__from, __thru});
    }

  // 26.5.7.4, seeding the per-thread engine
  void reseed()
  { __detail::global_urng().seed(); }

  void reseed(default_random_engine::result_type __value)
  { __detail::global_urng().seed(__value); }


//  There is more in algorithms I think...

  // Replace the C++11 shuffle declaration with this declaration (adds defaults).
  template<class RandomAccessIterator,
           class UniformRandomNumberGenerator = decltype(global_urng())>
    void shuffle(RandomAccessIterator first, RandomAccessIterator last,
                 UniformRandomNumberGenerator&& g = global_urng());

*/