Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-12-16 10:27:55 

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2014-present
0005 //  Copyright Casey Carter 2016
0006 //
0007 //  Use, modification and distribution is subject to the
0008 //  Boost Software License, Version 1.0. (See accompanying
0009 //  file LICENSE_1_0.txt or copy at
0010 //  http://www.boost.org/LICENSE_1_0.txt)
0011 //
0012 // Project home: https://github.com/ericniebler/range-v3
0013 //
0014 #ifndef RANGES_V3_ALGORITHM_SAMPLE_HPP
0015 #define RANGES_V3_ALGORITHM_SAMPLE_HPP
0016 
0017 #include <utility>
0018 
0019 #include <range/v3/range_fwd.hpp>
0020 
0021 #include <range/v3/algorithm/copy_n.hpp>
0022 #include <range/v3/iterator/concepts.hpp>
0023 #include <range/v3/iterator/operations.hpp>
0024 #include <range/v3/iterator/traits.hpp>
0025 #include <range/v3/range/access.hpp>
0026 #include <range/v3/range/concepts.hpp>
0027 #include <range/v3/range/dangling.hpp>
0028 #include <range/v3/range/traits.hpp>
0029 #include <range/v3/utility/random.hpp>
0030 #include <range/v3/utility/static_const.hpp>
0031 
0032 #include <range/v3/detail/prologue.hpp>
0033 
0034 namespace ranges
0035 {
0036     /// \addtogroup group-algorithms
0037     /// @{
0038     template<typename I, typename O>
0039     using sample_result = detail::in_out_result<I, O>;
0040 
0041     /// \cond
0042     namespace detail
0043     {
0044         template<typename I, typename S, typename O, typename Gen>
0045         sample_result<I, O> sample_sized_impl(I first,
0046                                               S last,
0047                                               iter_difference_t<I> pop_size,
0048                                               O out,
0049                                               iter_difference_t<O> sample_size,
0050                                               Gen && gen)
0051         {
0052             if(pop_size > 0 && sample_size > 0)
0053             {
0054                 std::uniform_int_distribution<iter_difference_t<I>> dist;
0055                 using param_t = typename decltype(dist)::param_type;
0056                 for(; first != last; ++first)
0057                 {
0058                     if(sample_size >= pop_size)
0059                         return copy_n(std::move(first), pop_size, std::move(out));
0060 
0061                     if(dist(gen, param_t{0, --pop_size}) < sample_size)
0062                     {
0063                         *out = *first;
0064                         ++out;
0065                         if(--sample_size == 0)
0066                             break;
0067                     }
0068                 }
0069             }
0070 
0071             return {std::move(first), std::move(out)};
0072         }
0073     } // namespace detail
0074     /// \endcond
0075 
0076     RANGES_FUNC_BEGIN(sample)
0077 
0078         /// \brief function template \c sample
0079         template(typename I,
0080                  typename S,
0081                  typename O,
0082                  typename Gen = detail::default_random_engine &)(
0083             requires input_iterator<I> AND sentinel_for<S, I> AND
0084                 weakly_incrementable<O> AND indirectly_copyable<I, O> AND
0085                 uniform_random_bit_generator<std::remove_reference_t<Gen>> AND
0086                 (random_access_iterator<O> || forward_iterator<I> ||
0087                  sized_sentinel_for<S, I>))
0088         sample_result<I, O> RANGES_FUNC(sample)(I first,
0089                                                 S last,
0090                                                 O out,
0091                                                 iter_difference_t<O> const n,
0092                                                 Gen && gen = detail::get_random_engine())
0093         {
0094             if(RANGES_CONSTEXPR_IF(forward_iterator<I> || sized_sentinel_for<S, I>)) //
0095             {
0096                 auto const k = distance(first, last);
0097                 return detail::sample_sized_impl(std::move(first),
0098                                                  std::move(last),
0099                                                  k,
0100                                                  std::move(out),
0101                                                  n,
0102                                                  static_cast<Gen &&>(gen));
0103             }
0104             else
0105             {
0106                 // out is random-access here; calls to advance(out,n) and
0107                 // next(out,n) are O(1).
0108                 if(n > 0)
0109                 {
0110                     for(iter_difference_t<O> i = 0; i < n; (void)++i, ++first)
0111                     {
0112                         if(first == last)
0113                         {
0114                             advance(out, i);
0115                             goto done;
0116                         }
0117                         *next(out, i) = *first;
0118                     }
0119 
0120                     std::uniform_int_distribution<iter_difference_t<O>> dist;
0121                     using param_t = typename decltype(dist)::param_type;
0122                     for(auto pop_size = n; first != last; (void)++first, ++pop_size)
0123                     {
0124                         auto const i = dist(gen, param_t{0, pop_size});
0125                         if(i < n)
0126                             *next(out, i) = *first;
0127                     }
0128 
0129                     advance(out, n);
0130                 }
0131             done:
0132                 return {std::move(first), std::move(out)};
0133             }
0134         }
0135 
0136         /// \overload
0137         template(typename I,
0138                  typename S,
0139                  typename ORng,
0140                  typename Gen = detail::default_random_engine &)(
0141             requires input_iterator<I> AND sentinel_for<S, I> AND
0142                 weakly_incrementable<iterator_t<ORng>> AND
0143                 indirectly_copyable<I, iterator_t<ORng>> AND
0144                 uniform_random_bit_generator<std::remove_reference_t<Gen>> AND
0145                 (forward_range<ORng> || sized_range<ORng>) AND
0146                 (random_access_iterator<iterator_t<ORng>> || forward_iterator<I> ||
0147                     sized_sentinel_for<S, I>))
0148         sample_result<I, borrowed_iterator_t<ORng>> RANGES_FUNC(sample)(
0149             I first,
0150             S last,
0151             ORng && out,
0152             Gen && gen = detail::get_random_engine()) //
0153         {
0154             if(RANGES_CONSTEXPR_IF(forward_iterator<I> || sized_sentinel_for<S, I>)) //
0155             {
0156                 auto k = distance(first, last);
0157                 return detail::sample_sized_impl(std::move(first),
0158                                                  std::move(last),
0159                                                  k,
0160                                                  begin(out),
0161                                                  distance(out),
0162                                                  static_cast<Gen &&>(gen));
0163             }
0164             else
0165             {
0166                 return (*this)(std::move(first),
0167                                std::move(last),
0168                                begin(out),
0169                                distance(out),
0170                                static_cast<Gen &&>(gen));
0171             }
0172         }
0173 
0174         /// \overload
0175         template(typename Rng,
0176                  typename O,
0177                  typename Gen = detail::default_random_engine &)(
0178             requires input_range<Rng> AND weakly_incrementable<O> AND
0179                 indirectly_copyable<iterator_t<Rng>, O> AND
0180                 uniform_random_bit_generator<std::remove_reference_t<Gen>> AND
0181                 (random_access_iterator<O> || forward_range<Rng> || sized_range<Rng>))
0182         sample_result<borrowed_iterator_t<Rng>, O> RANGES_FUNC(sample)(
0183             Rng && rng,
0184             O out,
0185             iter_difference_t<O> const n,
0186             Gen && gen = detail::get_random_engine()) //
0187         {
0188             if(RANGES_CONSTEXPR_IF(forward_range<Rng> || sized_range<Rng>)) //
0189             {
0190                 return detail::sample_sized_impl(begin(rng),
0191                                                  end(rng),
0192                                                  distance(rng),
0193                                                  std::move(out),
0194                                                  n,
0195                                                  static_cast<Gen &&>(gen));
0196             }
0197             else
0198             {
0199                 return (*this)(
0200                     begin(rng), end(rng), std::move(out), n, static_cast<Gen &&>(gen));
0201             }
0202         }
0203 
0204         /// \overload
0205         template(typename IRng,
0206                  typename ORng,
0207                  typename Gen = detail::default_random_engine &)(
0208             requires input_range<IRng> AND range<ORng> AND
0209                 indirectly_copyable<iterator_t<IRng>, iterator_t<ORng>> AND
0210                 uniform_random_bit_generator<std::remove_reference_t<Gen>> AND
0211                 (random_access_iterator<iterator_t<ORng>> || forward_range<IRng> ||
0212                     sized_range<IRng>) AND
0213                 (forward_range<ORng> || sized_range<ORng>))
0214         sample_result<borrowed_iterator_t<IRng>, borrowed_iterator_t<ORng>> //
0215         RANGES_FUNC(sample)(IRng && rng,
0216                             ORng && out,
0217                             Gen && gen = detail::get_random_engine())
0218         {
0219             if(RANGES_CONSTEXPR_IF(forward_range<IRng> || sized_range<IRng>)) //
0220             {
0221                 return detail::sample_sized_impl(begin(rng),
0222                                                  end(rng),
0223                                                  distance(rng),
0224                                                  begin(out),
0225                                                  distance(out),
0226                                                  static_cast<Gen &&>(gen));
0227             }
0228             else
0229             {
0230                 return (*this)(begin(rng),
0231                                end(rng),
0232                                begin(out),
0233                                distance(out),
0234                                static_cast<Gen &&>(gen));
0235             }
0236         }
0237 
0238     RANGES_FUNC_END(sample)
0239 
0240     namespace cpp20
0241     {
0242         using ranges::sample_result;
0243         using ranges::sample;
0244     }
0245     /// @}
0246 } // namespace ranges
0247 
0248 #include <range/v3/detail/epilogue.hpp>
0249 
0250 #endif
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!