v3/view/group_by.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2013-present
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_GROUP_BY_HPP
0015 #define RANGES_V3_VIEW_GROUP_BY_HPP
0016
0017 #include <type_traits>
0018 #include <utility>
0019
0020 #include <meta/meta.hpp>
0021
0022 #include <range/v3/range_fwd.hpp>
0023
0024 #include <range/v3/algorithm/find_if_not.hpp>
0025 #include <range/v3/functional/bind_back.hpp>
0026 #include <range/v3/functional/invoke.hpp>
0027 #include <range/v3/iterator/default_sentinel.hpp>
0028 #include <range/v3/range/access.hpp>
0029 #include <range/v3/range/concepts.hpp>
0030 #include <range/v3/range/traits.hpp>
0031 #include <range/v3/utility/optional.hpp>
0032 #include <range/v3/utility/semiregular_box.hpp>
0033 #include <range/v3/utility/static_const.hpp>
0034 #include <range/v3/view/facade.hpp>
0035 #include <range/v3/view/subrange.hpp>
0036 #include <range/v3/view/take_while.hpp>
0037 #include <range/v3/view/view.hpp>
0038
0039 #include <range/v3/detail/config.hpp>
0040 #include <range/v3/detail/prologue.hpp>
0041
0042 namespace ranges
0043 {
0044     // TODO group_by could support Input ranges by keeping mutable state in
0045     // the range itself. The group_by view would then be mutable-only and
0046     // Input.
0047
0048     /// \addtogroup group-views
0049     /// @{
0050     template<typename Rng, typename Fun>
0051     struct group_by_view
0052       : view_facade<group_by_view<Rng, Fun>,
0053                     is_finite<Rng>::value ? finite : range_cardinality<Rng>::value>
0054     {
0055     private:
0056         friend range_access;
0057         Rng rng_;
0058         // cached version of the end of the first subrange / start of the second subrange
0059         detail::non_propagating_cache<iterator_t<Rng>> second_;
0060         semiregular_box_t<Fun> fun_;
0061
0062         struct pred
0063         {
0064             iterator_t<Rng> first_;
0065             semiregular_box_ref_or_val_t<Fun, false> fun_;
0066             bool operator()(range_reference_t<Rng> r) const
0067             {
0068                 return invoke(fun_, *first_, r);
0069             }
0070         };
0071
0072         struct cursor
0073         {
0074         private:
0075             friend range_access;
0076             friend group_by_view;
0077             iterator_t<Rng> cur_;
0078             iterator_t<Rng> next_cur_;
0079             sentinel_t<Rng> last_;
0080             semiregular_box_ref_or_val_t<Fun, false> fun_;
0081
0082             struct mixin : basic_mixin<cursor>
0083             {
0084                 mixin() = default;
0085                 #ifndef _MSC_VER
0086                 using basic_mixin<cursor>::basic_mixin;
0087                 #else
0088                 constexpr explicit mixin(cursor && cur)
0089                   : basic_mixin<cursor>(static_cast<cursor &&>(cur))
0090                 {}
0091                 constexpr explicit mixin(cursor const & cur)
0092                   : basic_mixin<cursor>(cur)
0093                 {}
0094                 #endif
0095                 iterator_t<Rng> base() const
0096                 {
0097                     return this->get().cur_;
0098                 }
0099             };
0100
0101             #ifdef _MSC_VER
0102             template<typename I = iterator_t<Rng>>
0103             subrange<I> read() const
0104             {
0105                 return {cur_, next_cur_};
0106             }
0107             #else
0108             subrange<iterator_t<Rng>> read() const
0109             {
0110                 return {cur_, next_cur_};
0111             }
0112             #endif
0113             void next()
0114             {
0115                 cur_ = next_cur_;
0116                 next_cur_ = cur_ != last_
0117                                 ? find_if_not(ranges::next(cur_), last_, pred{cur_, fun_})
0118                                 : cur_;
0119             }
0120
0121             bool equal(default_sentinel_t) const
0122             {
0123                 return cur_ == last_;
0124             }
0125             bool equal(cursor const & that) const
0126             {
0127                 return cur_ == that.cur_;
0128             }
0129             cursor(semiregular_box_ref_or_val_t<Fun, false> fun, iterator_t<Rng> first,
0130                    iterator_t<Rng> next_cur, sentinel_t<Rng> last)
0131               : cur_(first)
0132               , next_cur_(next_cur)
0133               , last_(last)
0134               , fun_(fun)
0135             {}
0136
0137         public:
0138             cursor() = default;
0139         };
0140         cursor begin_cursor()
0141         {
0142             auto b = ranges::begin(rng_);
0143             auto e = ranges::end(rng_);
0144             if(!second_)
0145             {
0146                 second_ = b != e ? find_if_not(ranges::next(b), e, pred{b, fun_}) : b;
0147             }
0148             return {fun_, b, *second_, e};
0149         }
0150
0151     public:
0152         group_by_view() = default;
0153         constexpr group_by_view(Rng rng, Fun fun)
0154           : rng_(std::move(rng))
0155           , fun_(std::move(fun))
0156         {}
0157         Rng base() const
0158         {
0159             return rng_;
0160         }
0161     };
0162
0163 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
0164     template(typename Rng, typename Fun)(
0165         requires copy_constructible<Fun>)
0166         group_by_view(Rng &&, Fun)
0167             ->group_by_view<views::all_t<Rng>, Fun>;
0168 #endif
0169
0170     namespace views
0171     {
0172         struct group_by_base_fn
0173         {
0174             template(typename Rng, typename Fun)(
0175                 requires viewable_range<Rng> AND forward_range<Rng> AND
0176                     indirect_relation<Fun, iterator_t<Rng>>)
0177                 RANGES_DEPRECATED(
0178                     "views::group_by is deprecated. Please use views::chunk_by instead. "
0179                     "Note that views::chunk_by evaluates the predicate between adjacent "
0180                     "elements.")
0181             constexpr group_by_view<all_t<Rng>, Fun> operator()(Rng && rng, Fun fun) const
0182             {
0183                 return {all(static_cast<Rng &&>(rng)), std::move(fun)};
0184             }
0185         };
0186
0187         struct group_by_fn : group_by_base_fn
0188         {
0189             using group_by_base_fn::operator();
0190
0191             template<typename Fun>
0192             RANGES_DEPRECATED(
0193                 "views::group_by is deprecated. Please use views::chunk_by instead. "
0194                 "Note that views::chunk_by evaluates the predicate between adjacent "
0195                 "elements.")
0196             constexpr auto operator()(Fun fun) const
0197             {
0198                 return make_view_closure(bind_back(group_by_base_fn{}, std::move(fun)));
0199             }
0200         };
0201
0202         /// \relates group_by_fn
0203         /// \ingroup group-views
0204         RANGES_INLINE_VARIABLE(group_by_fn, group_by)
0205     } // namespace views
0206     /// @}
0207 } // namespace ranges
0208
0209 #include <range/v3/detail/epilogue.hpp>
0210 #include <range/v3/detail/satisfy_boost_range.hpp>
0211 RANGES_SATISFY_BOOST_RANGE(::ranges::group_by_view)
0212
0213 #endif