v3/algorithm/search_n.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2014-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 //
0015 //                     The LLVM Compiler Infrastructure
0016 //
0017 // This file is dual licensed under the MIT and the University of Illinois Open
0018 // Source Licenses. See LICENSE.TXT for details.
0019 //
0020 //===----------------------------------------------------------------------===//
0021 #ifndef RANGES_V3_ALGORITHM_SEARCH_N_HPP
0022 #define RANGES_V3_ALGORITHM_SEARCH_N_HPP
0023
0024 #include <meta/meta.hpp>
0025
0026 #include <range/v3/range_fwd.hpp>
0027
0028 #include <range/v3/functional/comparisons.hpp>
0029 #include <range/v3/functional/identity.hpp>
0030 #include <range/v3/functional/invoke.hpp>
0031 #include <range/v3/iterator/concepts.hpp>
0032 #include <range/v3/iterator/operations.hpp>
0033 #include <range/v3/iterator/traits.hpp>
0034 #include <range/v3/range/access.hpp>
0035 #include <range/v3/range/concepts.hpp>
0036 #include <range/v3/range/primitives.hpp>
0037 #include <range/v3/range/traits.hpp>
0038 #include <range/v3/utility/static_const.hpp>
0039 #include <range/v3/view/subrange.hpp>
0040
0041 #include <range/v3/detail/prologue.hpp>
0042
0043 namespace ranges
0044 {
0045     /// \addtogroup group-algorithms
0046     /// @{
0047
0048     /// \cond
0049     namespace detail
0050     {
0051         template<typename I, typename S, typename D, typename V, typename C, typename P>
0052         constexpr subrange<I> search_n_sized_impl(I const begin_,
0053                                                   S last,
0054                                                   D const d_,
0055                                                   D cnt,
0056                                                   V const & val,
0057                                                   C & pred,
0058                                                   P & proj)
0059         {
0060             D d = d_; // always the distance from first to end
0061             auto first = uncounted(begin_);
0062             while(true)
0063             {
0064                 // Find first element in sequence 1 that matches val, with a mininum of
0065                 // loop checks
0066                 while(true)
0067                 {
0068                     if(d < cnt) // return the last if we've run out of room
0069                     {
0070                         auto e = ranges::next(recounted(begin_, std::move(first), d_ - d),
0071                                               std::move(last));
0072                         return {e, e};
0073                     }
0074                     if(invoke(pred, invoke(proj, *first), val))
0075                         break;
0076                     ++first;
0077                     --d;
0078                 }
0079                 // *first matches val, now match elements after here
0080                 auto m = first;
0081                 D c = 0;
0082                 while(true)
0083                 {
0084                     if(++c == cnt) // If pattern exhausted, first is the answer (works
0085                                    // for 1 element pattern)
0086                         return {recounted(begin_, std::move(first), d_ - d),
0087                                 recounted(begin_, std::move(++m), d_ - d)};
0088                     ++m; // No need to check, we know we have room to match successfully
0089                     if(!invoke(pred,
0090                                invoke(proj, *m),
0091                                val)) // if there is a mismatch, restart with a new begin
0092                     {
0093                         first = next(std::move(m));
0094                         d -= (c + 1);
0095                         break;
0096                     } // else there is a match, check next elements
0097                 }
0098             }
0099         }
0100
0101         template<typename I, typename S, typename D, typename V, typename C, typename P>
0102         constexpr subrange<I> search_n_impl(I first,
0103                                             S last,
0104                                             D cnt,
0105                                             V const & val,
0106                                             C & pred,
0107                                             P & proj)
0108         {
0109             while(true)
0110             {
0111                 // Find first element in sequence 1 that matches val, with a mininum of
0112                 // loop checks
0113                 while(true)
0114                 {
0115                     if(first == last) // return last if no element matches val
0116                         return {first, first};
0117                     if(invoke(pred, invoke(proj, *first), val))
0118                         break;
0119                     ++first;
0120                 }
0121                 // *first matches val, now match elements after here
0122                 I m = first;
0123                 D c = 0;
0124                 while(true)
0125                 {
0126                     if(++c == cnt) // If pattern exhausted, first is the answer (works
0127                                    // for 1 element pattern)
0128                         return {first, ++m};
0129                     if(++m == last) // Otherwise if source exhausted, pattern not found
0130                         return {m, m};
0131                     if(!invoke(pred,
0132                                invoke(proj, *m),
0133                                val)) // if there is a mismatch, restart with a new begin
0134                     {
0135                         first = next(std::move(m));
0136                         break;
0137                     } // else there is a match, check next elements
0138                 }
0139             }
0140         }
0141     } // namespace detail
0142     /// \endcond
0143
0144     RANGES_FUNC_BEGIN(search_n)
0145
0146         /// \brief function template \c search_n
0147         template(typename I,
0148                  typename S,
0149                  typename V,
0150                  typename C = equal_to,
0151                  typename P = identity)(
0152             requires forward_iterator<I> AND sentinel_for<S, I> AND
0153                 indirectly_comparable<I, V const *, C, P>)
0154         constexpr subrange<I> RANGES_FUNC(search_n)(I first,
0155                                                     S last,
0156                                                     iter_difference_t<I> cnt,
0157                                                     V const & val,
0158                                                     C pred = C{},
0159                                                     P proj = P{}) //
0160         {
0161             if(cnt <= 0)
0162                 return {first, first};
0163             if(RANGES_CONSTEXPR_IF(sized_sentinel_for<S, I>))
0164                 return detail::search_n_sized_impl(std::move(first),
0165                                                    std::move(last),
0166                                                    distance(first, last),
0167                                                    cnt,
0168                                                    val,
0169                                                    pred,
0170                                                    proj);
0171             else
0172                 return detail::search_n_impl(
0173                     std::move(first), std::move(last), cnt, val, pred, proj);
0174         }
0175
0176         /// \overload
0177         template(typename Rng, typename V, typename C = equal_to, typename P = identity)(
0178             requires forward_range<Rng> AND
0179                 indirectly_comparable<iterator_t<Rng>, V const *, C, P>)
0180         constexpr borrowed_subrange_t<Rng> RANGES_FUNC(search_n)(Rng && rng,
0181                                                                  iter_difference_t<iterator_t<Rng>> cnt,
0182                                                                  V const & val,
0183                                                                  C pred = C{},
0184                                                                  P proj = P{}) //
0185         {
0186             if(cnt <= 0)
0187                 return subrange<iterator_t<Rng>>{begin(rng), begin(rng)};
0188             if(RANGES_CONSTEXPR_IF(sized_range<Rng>))
0189                 return detail::search_n_sized_impl(
0190                     begin(rng), end(rng), distance(rng), cnt, val, pred, proj);
0191             else
0192                 return detail::search_n_impl(begin(rng), end(rng), cnt, val, pred, proj);
0193         }
0194
0195     RANGES_FUNC_END(search_n)
0196
0197     namespace cpp20
0198     {
0199         using ranges::search_n;
0200     }
0201     /// @}
0202 } // namespace ranges
0203
0204 #include <range/v3/detail/epilogue.hpp>
0205
0206 #endif