v3/view/sliding.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2013-present
0005 //  Copyright Tobias Mayer 2016
0006 //  Copyright Casey Carter 2016
0007 //
0008 //  Use, modification and distribution is subject to the
0009 //  Boost Software License, Version 1.0. (See accompanying
0010 //  file LICENSE_1_0.txt or copy at
0011 //  http://www.boost.org/LICENSE_1_0.txt)
0012 //
0013 // Project home: https://github.com/ericniebler/range-v3
0014 //
0015
0016 #ifndef RANGES_V3_VIEW_SLIDING_HPP
0017 #define RANGES_V3_VIEW_SLIDING_HPP
0018
0019 #include <utility>
0020
0021 #include <meta/meta.hpp>
0022
0023 #include <range/v3/range_fwd.hpp>
0024
0025 #include <range/v3/functional/bind_back.hpp>
0026 #include <range/v3/iterator/operations.hpp>
0027 #include <range/v3/range/access.hpp>
0028 #include <range/v3/range/concepts.hpp>
0029 #include <range/v3/range/traits.hpp>
0030 #include <range/v3/utility/optional.hpp>
0031 #include <range/v3/utility/static_const.hpp>
0032 #include <range/v3/view/adaptor.hpp>
0033 #include <range/v3/view/all.hpp>
0034 #include <range/v3/view/counted.hpp>
0035 #include <range/v3/view/view.hpp>
0036
0037 #include <range/v3/detail/prologue.hpp>
0038
0039 namespace ranges
0040 {
0041     /// \cond
0042     namespace sliding_view_detail
0043     {
0044         enum class cache
0045         {
0046             none,
0047             first,
0048             last
0049         };
0050
0051         template<typename Rng>
0052         using caching = std::integral_constant<
0053             cache, random_access_range<Rng> && sized_range<Rng>
0054                        ? cache::none
0055                        : bidirectional_range<Rng> && common_range<Rng> ? cache::last
0056                                                                        : cache::first>;
0057     } // namespace sliding_view_detail
0058     /// \endcond
0059
0060     template<typename Rng,
0061              sliding_view_detail::cache = sliding_view_detail::caching<Rng>::value>
0062     struct sliding_view;
0063
0064     /// \cond
0065     namespace sliding_view_detail
0066     {
0067         template<typename Rng>
0068         using uncounted_t =
0069             decltype(ranges::uncounted(std::declval<iterator_t<Rng> &>()));
0070
0071         template<typename Rng, bool = (bool)random_access_range<Rng>>
0072         struct trailing
0073         {
0074             trailing() = default;
0075             constexpr trailing(Rng & rng)
0076               : it_{uncounted(ranges::begin(rng))}
0077             {}
0078             constexpr uncounted_t<Rng> get(iterator_t<Rng> const &,
0079                                            range_difference_t<Rng>) const
0080             {
0081                 return it_;
0082             }
0083             void next()
0084             {
0085                 ++it_;
0086             }
0087             CPP_member
0088             auto prev() //
0089                 -> CPP_ret(void)(
0090                     requires bidirectional_range<Rng>)
0091             {
0092                 --it_;
0093             }
0094
0095         private:
0096             uncounted_t<Rng> it_;
0097         };
0098
0099         template<typename Rng>
0100         struct trailing<Rng, true>
0101         {
0102             trailing() = default;
0103             constexpr trailing(Rng &) noexcept
0104             {}
0105             constexpr uncounted_t<Rng> get(iterator_t<Rng> const & it,
0106                                            range_difference_t<Rng> n) const
0107             {
0108                 return uncounted(it - (n - 1));
0109             }
0110             void next()
0111             {}
0112             void prev()
0113             {}
0114         };
0115
0116         template<typename Rng>
0117         struct RANGES_EMPTY_BASES sv_base
0118           : view_adaptor<sliding_view<Rng>, Rng,
0119                          is_finite<Rng>::value ? finite : range_cardinality<Rng>::value>
0120           , private detail::non_propagating_cache<iterator_t<Rng>, sv_base<Rng>,
0121                                                   caching<Rng>::value != cache::none>
0122         {
0123             CPP_assert(forward_range<Rng>);
0124             sv_base() = default;
0125             sv_base(Rng rng, range_difference_t<Rng> n)
0126               : sv_base::view_adaptor(std::move(rng))
0127               , n_(n)
0128             {
0129                 RANGES_ASSERT(0 < n_);
0130             }
0131             CPP_auto_member
0132             auto CPP_fun(size)()(const //
0133                 requires sized_range<Rng const>)
0134             {
0135                 auto const count = ranges::size(this->base());
0136                 auto const n = static_cast<range_size_t<Rng const>>(n_);
0137                 return count < n ? 0 : count - n + 1;
0138             }
0139             CPP_auto_member
0140             auto CPP_fun(size)()(
0141                 requires sized_range<Rng>)
0142             {
0143                 auto const count = ranges::size(this->base());
0144                 auto const n = static_cast<range_size_t<Rng>>(n_);
0145                 return count < n ? 0 : count - n + 1;
0146             }
0147
0148         protected:
0149             range_difference_t<Rng> n_;
0150
0151             optional<iterator_t<Rng>> & cache() &
0152             {
0153                 return static_cast<cache_t &>(*this);
0154             }
0155             optional<iterator_t<Rng>> const & cache() const &
0156             {
0157                 return static_cast<cache_t const &>(*this);
0158             }
0159
0160         private:
0161             using cache_t = detail::non_propagating_cache<iterator_t<Rng>, sv_base<Rng>>;
0162         };
0163     } // namespace sliding_view_detail
0164     /// \endcond
0165
0166     /// \addtogroup group-views
0167     /// @{
0168     template<typename Rng>
0169     struct sliding_view<Rng, sliding_view_detail::cache::first>
0170       : sliding_view_detail::sv_base<Rng>
0171     {
0172     private:
0173         friend range_access;
0174
0175         iterator_t<Rng> get_first()
0176         {
0177             auto & first = this->cache();
0178             if(!first)
0179             {
0180                 first = ranges::next(
0181                     ranges::begin(this->base()), this->n_ - 1, ranges::end(this->base()));
0182             }
0183             return *first;
0184         }
0185
0186         struct RANGES_EMPTY_BASES adaptor
0187           : adaptor_base
0188           , sliding_view_detail::trailing<Rng>
0189         {
0190         private:
0191             using base_t = sliding_view_detail::trailing<Rng>;
0192             range_difference_t<Rng> n_ = {};
0193
0194         public:
0195             adaptor() = default;
0196             adaptor(sliding_view * v)
0197               : base_t{v->base()}
0198               , n_{v->n_}
0199             {}
0200             iterator_t<Rng> begin(sliding_view & v)
0201             {
0202                 return v.get_first();
0203             }
0204             auto read(iterator_t<Rng> const & it) const
0205                 -> decltype(views::counted(uncounted(it), n_))
0206             {
0207                 return views::counted(base_t::get(it, n_), n_);
0208             }
0209             void next(iterator_t<Rng> & it)
0210             {
0211                 ++it;
0212                 base_t::next();
0213             }
0214             CPP_member
0215             auto prev(iterator_t<Rng> & it) //
0216                 -> CPP_ret(void)(
0217                     requires bidirectional_range<Rng>)
0218             {
0219                 base_t::prev();
0220                 --it;
0221             }
0222             CPP_member
0223             auto advance(iterator_t<Rng> & it, range_difference_t<Rng> n)
0224                 -> CPP_ret(void)(
0225                     requires random_access_range<Rng>)
0226             {
0227                 it += n;
0228             }
0229         };
0230
0231         adaptor begin_adaptor()
0232         {
0233             return {this};
0234         }
0235         meta::if_c<common_range<Rng>, adaptor, adaptor_base> end_adaptor()
0236         {
0237             return {this};
0238         }
0239
0240     public:
0241         using sliding_view::sv_base::sv_base;
0242     };
0243
0244     template<typename Rng>
0245     struct sliding_view<Rng, sliding_view_detail::cache::last>
0246       : sliding_view_detail::sv_base<Rng>
0247     {
0248     private:
0249         friend range_access;
0250
0251         iterator_t<Rng> get_last()
0252         {
0253             auto & last = this->cache();
0254             if(!last)
0255             {
0256                 last = ranges::prev(
0257                     ranges::end(this->base()), this->n_ - 1, ranges::begin(this->base()));
0258             }
0259             return *last;
0260         }
0261
0262         struct adaptor : adaptor_base
0263         {
0264         private:
0265             range_difference_t<Rng> n_ = {};
0266
0267         public:
0268             adaptor() = default;
0269             adaptor(sliding_view * v)
0270               : n_{v->n_}
0271             {}
0272             iterator_t<Rng> end(sliding_view & v)
0273             {
0274                 return v.get_last();
0275             }
0276             auto read(iterator_t<Rng> const & it) const
0277                 -> decltype(views::counted(uncounted(it), n_))
0278             {
0279                 return views::counted(uncounted(it), n_);
0280             }
0281         };
0282
0283         adaptor begin_adaptor()
0284         {
0285             return {this};
0286         }
0287         adaptor end_adaptor()
0288         {
0289             return {this};
0290         }
0291
0292     public:
0293         using sliding_view::sv_base::sv_base;
0294     };
0295
0296     template<typename Rng>
0297     struct sliding_view<Rng, sliding_view_detail::cache::none>
0298       : sliding_view_detail::sv_base<Rng>
0299     {
0300     private:
0301         friend range_access;
0302
0303         template<bool Const>
0304         struct adaptor : adaptor_base
0305         {
0306         private:
0307             friend adaptor<!Const>;
0308             using CRng = meta::const_if_c<Const, Rng>;
0309             range_difference_t<Rng> n_ = 0;
0310
0311         public:
0312             adaptor() = default;
0313             adaptor(range_difference_t<Rng> n)
0314               : n_(n)
0315             {}
0316             template(bool Other)(
0317                 requires Const AND CPP_NOT(Other)) //
0318             adaptor(adaptor<Other> that)
0319               : n_(that.n_)
0320             {}
0321             iterator_t<CRng> end(meta::const_if_c<Const, sliding_view> & v) const
0322             {
0323                 auto const sz = ranges::distance(v.base());
0324                 auto const offset = n_ - 1 < sz ? n_ - 1 : sz;
0325                 return ranges::begin(v.base()) + (sz - offset);
0326             }
0327             auto read(iterator_t<CRng> const & it) const
0328                 -> decltype(views::counted(uncounted(it), n_))
0329             {
0330                 return views::counted(uncounted(it), n_);
0331             }
0332         };
0333
0334         adaptor<simple_view<Rng>()> begin_adaptor()
0335         {
0336             return {this->n_};
0337         }
0338         CPP_member
0339         auto begin_adaptor() const //
0340             -> CPP_ret(adaptor<true>)(
0341                 requires range<Rng const>)
0342         {
0343             return {this->n_};
0344         }
0345         adaptor<simple_view<Rng>()> end_adaptor()
0346         {
0347             return {this->n_};
0348         }
0349         CPP_member
0350         auto end_adaptor() const //
0351             -> CPP_ret(adaptor<true>)(
0352                 requires range<Rng const>)
0353         {
0354             return {this->n_};
0355         }
0356
0357     public:
0358         using sliding_view::sv_base::sv_base;
0359     };
0360
0361     template<typename Rng>
0362     RANGES_INLINE_VAR constexpr bool enable_borrowed_range<sliding_view<Rng>> = //
0363         enable_borrowed_range<Rng>;
0364
0365 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
0366     template<typename Rng>
0367     sliding_view(Rng &&, range_difference_t<Rng>)
0368         -> sliding_view<views::all_t<Rng>>;
0369 #endif
0370
0371     namespace views
0372     {
0373         // In:  range<T>
0374         // Out: range<range<T>>, where each inner range has $n$ elements.
0375         struct sliding_base_fn
0376         {
0377             template(typename Rng)(
0378                 requires viewable_range<Rng> AND forward_range<Rng>)
0379             constexpr sliding_view<all_t<Rng>> //
0380             operator()(Rng && rng, range_difference_t<Rng> n) const
0381             {
0382                 return {all(static_cast<Rng &&>(rng)), n};
0383             }
0384         };
0385
0386         struct sliding_fn : sliding_base_fn
0387         {
0388             using sliding_base_fn::operator();
0389
0390             template<typename Int>
0391             constexpr auto CPP_fun(operator())(Int n)(const //
0392                                                       requires detail::integer_like_<Int>)
0393             {
0394                 return make_view_closure(bind_back(sliding_base_fn{}, n));
0395             }
0396         };
0397
0398         /// \relates sliding_fn
0399         /// \ingroup group-views
0400         RANGES_INLINE_VARIABLE(sliding_fn, sliding)
0401     } // namespace views
0402     /// @}
0403 } // namespace ranges
0404
0405 #include <range/v3/detail/epilogue.hpp>
0406
0407 #endif