v3/view/sample.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Casey Carter 2016
0005 //
0006 //  Use, modification and distribution is subject to the
0007 //  Boost Software License, Version 1.0. (See accompanying
0008 //  file LICENSE_1_0.txt or copy at
0009 //  http://www.boost.org/LICENSE_1_0.txt)
0010 //
0011 // Project home: https://github.com/ericniebler/range-v3
0012 //
0013
0014 #ifndef RANGES_V3_VIEW_SAMPLE_HPP
0015 #define RANGES_V3_VIEW_SAMPLE_HPP
0016
0017 #include <meta/meta.hpp>
0018
0019 #include <range/v3/algorithm/shuffle.hpp>
0020 #include <range/v3/functional/bind_back.hpp>
0021 #include <range/v3/functional/invoke.hpp>
0022 #include <range/v3/iterator/concepts.hpp>
0023 #include <range/v3/iterator/default_sentinel.hpp>
0024 #include <range/v3/iterator/operations.hpp>
0025 #include <range/v3/range/concepts.hpp>
0026 #include <range/v3/utility/static_const.hpp>
0027 #include <range/v3/view/all.hpp>
0028 #include <range/v3/view/facade.hpp>
0029 #include <range/v3/view/view.hpp>
0030
0031 #include <range/v3/detail/prologue.hpp>
0032
0033 namespace ranges
0034 {
0035     /// \cond
0036     namespace detail
0037     {
0038         template<typename Rng,
0039                  bool = (bool)sized_sentinel_for<sentinel_t<Rng>, iterator_t<Rng>>>
0040         class size_tracker
0041         {
0042             range_difference_t<Rng> size_;
0043
0044         public:
0045             CPP_assert(forward_range<Rng> || sized_range<Rng>);
0046             size_tracker() = default;
0047             size_tracker(Rng & rng)
0048               : size_(ranges::distance(rng))
0049             {}
0050             void decrement()
0051             {
0052                 --size_;
0053             }
0054             range_difference_t<Rng> get(Rng &, iterator_t<Rng> &) const
0055             {
0056                 return size_;
0057             }
0058         };
0059
0060         // Impl for sized_sentinel_for (no need to store anything)
0061         template<typename Rng>
0062         class size_tracker<Rng, true>
0063         {
0064         public:
0065             size_tracker() = default;
0066             size_tracker(Rng &)
0067             {}
0068             void decrement()
0069             {}
0070             range_difference_t<Rng> get(Rng & rng, iterator_t<Rng> const & it) const
0071             {
0072                 return ranges::end(rng) - it;
0073             }
0074         };
0075     } // namespace detail
0076     /// \endcond
0077
0078     /// \addtogroup group-views
0079     /// @{
0080
0081     // Take a random sampling from another view
0082     template<typename Rng, typename URNG>
0083     class sample_view : public view_facade<sample_view<Rng, URNG>, finite>
0084     {
0085         friend range_access;
0086         using D = range_difference_t<Rng>;
0087         Rng rng_;
0088         // Mutable is OK here because sample_view is an Input view.
0089         mutable range_difference_t<Rng> size_;
0090         URNG * engine_;
0091
0092         template<bool IsConst>
0093         class cursor
0094         {
0095             friend cursor<!IsConst>;
0096
0097             using Base = meta::const_if_c<IsConst, Rng>;
0098             meta::const_if_c<IsConst, sample_view> * parent_;
0099             iterator_t<Base> current_;
0100             RANGES_NO_UNIQUE_ADDRESS detail::size_tracker<Base> size_;
0101
0102             D pop_size()
0103             {
0104                 return size_.get(parent_->rng_, current_);
0105             }
0106             void advance()
0107             {
0108                 if(parent_->size_ > 0)
0109                 {
0110                     using Dist = std::uniform_int_distribution<D>;
0111                     Dist dist{};
0112                     URNG & engine = *parent_->engine_;
0113
0114                     for(;; ++current_, size_.decrement())
0115                     {
0116                         RANGES_ASSERT(current_ != ranges::end(parent_->rng_));
0117                         auto n = pop_size();
0118                         RANGES_EXPECT(n > 0);
0119                         typename Dist::param_type const interval{0, n - 1};
0120                         if(dist(engine, interval) < parent_->size_)
0121                             break;
0122                     }
0123                 }
0124             }
0125
0126         public:
0127             using value_type = range_value_t<Rng>;
0128             using difference_type = D;
0129
0130             cursor() = default;
0131             explicit cursor(meta::const_if_c<IsConst, sample_view> * rng)
0132               : parent_(rng)
0133               , current_(ranges::begin(rng->rng_))
0134               , size_{rng->rng_}
0135             {
0136                 auto n = pop_size();
0137                 if(rng->size_ > n)
0138                     rng->size_ = n;
0139                 advance();
0140             }
0141             template(bool Other)(
0142                 requires IsConst AND CPP_NOT(Other)) //
0143             cursor(cursor<Other> that)
0144               : parent_(that.parent_)
0145               , current_(std::move(that.current_))
0146               , size_(that.size_)
0147             {}
0148             range_reference_t<Rng> read() const
0149             {
0150                 return *current_;
0151             }
0152             bool equal(default_sentinel_t) const
0153             {
0154                 RANGES_EXPECT(parent_);
0155                 return parent_->size_ <= 0;
0156             }
0157             void next()
0158             {
0159                 RANGES_EXPECT(parent_);
0160                 RANGES_EXPECT(parent_->size_ > 0);
0161                 --parent_->size_;
0162                 RANGES_ASSERT(current_ != ranges::end(parent_->rng_));
0163                 ++current_;
0164                 size_.decrement();
0165                 advance();
0166             }
0167         };
0168
0169         cursor<false> begin_cursor()
0170         {
0171             return cursor<false>{this};
0172         }
0173         template(bool Const = true)(
0174             requires Const AND
0175             (sized_range<meta::const_if_c<Const, Rng>> ||
0176              sized_sentinel_for<sentinel_t<meta::const_if_c<Const, Rng>>,
0177                                 iterator_t<meta::const_if_c<Const, Rng>>> ||
0178              forward_range<meta::const_if_c<Const, Rng>>)) //
0179         cursor<Const> begin_cursor() const
0180         {
0181             return cursor<true>{this};
0182         }
0183
0184     public:
0185         sample_view() = default;
0186
0187         explicit sample_view(Rng rng, D sample_size, URNG & generator)
0188           : rng_(std::move(rng))
0189           , size_(sample_size)
0190           , engine_(std::addressof(generator))
0191         {
0192             RANGES_EXPECT(sample_size >= 0);
0193         }
0194
0195         Rng base() const
0196         {
0197             return rng_;
0198         }
0199     };
0200
0201 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
0202     template<typename Rng, typename URNG>
0203     sample_view(Rng &&, range_difference_t<Rng>, URNG &)
0204         ->sample_view<views::all_t<Rng>, URNG>;
0205 #endif
0206
0207     namespace views
0208     {
0209         /// Returns a random sample of a range of length `size(range)`.
0210         struct sample_base_fn
0211         {
0212             template(typename Rng, typename URNG = detail::default_random_engine)(
0213                 requires viewable_range<Rng> AND input_range<Rng> AND
0214                     uniform_random_bit_generator<URNG> AND
0215                     convertible_to<invoke_result_t<URNG &>, range_difference_t<Rng>> AND
0216                     (sized_range<Rng> ||
0217                      sized_sentinel_for<sentinel_t<Rng>, iterator_t<Rng>> ||
0218                      forward_range<Rng>)) //
0219             sample_view<all_t<Rng>, URNG> operator()(
0220                 Rng && rng,
0221                 range_difference_t<Rng> sample_size,
0222                 URNG & generator = detail::get_random_engine()) const
0223             {
0224                 return sample_view<all_t<Rng>, URNG>{
0225                     all(static_cast<Rng &&>(rng)), sample_size, generator};
0226             }
0227
0228             /// \cond
0229             template<typename Rng, typename URNG>
0230             invoke_result_t<sample_base_fn, Rng, range_difference_t<Rng>, URNG &> //
0231             operator()(
0232                 Rng && rng,
0233                 range_difference_t<Rng> sample_size,
0234                 detail::reference_wrapper_<URNG> r) const
0235             {
0236                 return (*this)(static_cast<Rng &&>(rng), sample_size, r.get());
0237             }
0238             /// \endcond
0239         };
0240
0241         struct sample_fn : sample_base_fn
0242         {
0243             using sample_base_fn::operator();
0244
0245             template(typename Size, typename URNG = detail::default_random_engine)(
0246                 requires integral<Size> AND uniform_random_bit_generator<URNG>)
0247             constexpr auto operator()(
0248                 Size n,
0249                 URNG & urng = detail::get_random_engine()) const //
0250             {
0251                 return make_view_closure(bind_back(
0252                     sample_base_fn{}, n, detail::reference_wrapper_<URNG>(urng)));
0253             }
0254         };
0255
0256         /// \relates sample_fn
0257         /// \ingroup group-views
0258         RANGES_INLINE_VARIABLE(sample_fn, sample)
0259     } // namespace views
0260     /// @}
0261 } // namespace ranges
0262
0263 #include <range/v3/detail/epilogue.hpp>
0264 #include <range/v3/detail/satisfy_boost_range.hpp>
0265 RANGES_SATISFY_BOOST_RANGE(::ranges::sample_view)
0266
0267 #endif