v3/algorithm/find_end.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 #ifndef RANGES_V3_ALGORITHM_FIND_END_HPP
0014 #define RANGES_V3_ALGORITHM_FIND_END_HPP
0015
0016 #include <utility>
0017
0018 #include <meta/meta.hpp>
0019
0020 #include <range/v3/range_fwd.hpp>
0021
0022 #include <range/v3/functional/comparisons.hpp>
0023 #include <range/v3/functional/identity.hpp>
0024 #include <range/v3/functional/invoke.hpp>
0025 #include <range/v3/iterator/concepts.hpp>
0026 #include <range/v3/iterator/operations.hpp>
0027 #include <range/v3/iterator/traits.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/static_const.hpp>
0032 #include <range/v3/view/subrange.hpp>
0033
0034 #include <range/v3/detail/prologue.hpp>
0035
0036 namespace ranges
0037 {
0038     /// \cond
0039     namespace detail
0040     {
0041         template(typename I, typename S)(
0042             requires input_iterator<I> AND sentinel_for<S, I>)
0043         constexpr I next_to_if(I i, S s, std::true_type)
0044         {
0045             return ranges::next(i, s);
0046         }
0047
0048         template(typename I, typename S)(
0049             requires input_iterator<I> AND sentinel_for<S, I>)
0050         constexpr S next_to_if(I, S s, std::false_type)
0051         {
0052             return s;
0053         }
0054
0055         template(bool B, typename I, typename S)(
0056             requires input_iterator<I> AND sentinel_for<S, I>)
0057         constexpr meta::if_c<B, I, S> next_to_if(I i, S s)
0058         {
0059             return detail::next_to_if(std::move(i), std::move(s), meta::bool_<B>{});
0060         }
0061
0062         template<typename I1, typename S1, typename I2, typename S2, typename R,
0063                  typename P>
0064         constexpr subrange<I1> find_end_impl(I1 begin1, S1 end1, I2 begin2, S2 end2, R pred, P proj,
0065                                    std::forward_iterator_tag, std::forward_iterator_tag)
0066         {
0067             bool found = false;
0068             I1 res_begin, res_end;
0069             if(begin2 == end2)
0070             {
0071                 auto e1 = ranges::next(begin1, end1);
0072                 return {e1, e1};
0073             }
0074             while(true)
0075             {
0076                 while(true)
0077                 {
0078                     if(begin1 == end1)
0079                         return {(found ? res_begin : begin1), (found ? res_end : begin1)};
0080                     if(invoke(pred, invoke(proj, *begin1), *begin2))
0081                         break;
0082                     ++begin1;
0083                 }
0084                 auto tmp1 = begin1;
0085                 auto tmp2 = begin2;
0086                 while(true)
0087                 {
0088                     if(++tmp2 == end2)
0089                     {
0090                         res_begin = begin1++;
0091                         res_end = ++tmp1;
0092                         found = true;
0093                         break;
0094                     }
0095                     if(++tmp1 == end1)
0096                         return {(found ? res_begin : tmp1), (found ? res_end : tmp1)};
0097                     if(!invoke(pred, invoke(proj, *tmp1), *tmp2))
0098                     {
0099                         ++begin1;
0100                         break;
0101                     }
0102                 }
0103             }
0104         }
0105
0106         template<typename I1, typename I2, typename R, typename P>
0107         constexpr subrange<I1> find_end_impl(I1 begin1, I1 end1, I2 begin2, I2 end2, R pred, P proj,
0108                                    std::bidirectional_iterator_tag,
0109                                    std::bidirectional_iterator_tag)
0110         {
0111             // modeled after search algorithm (in reverse)
0112             if(begin2 == end2)
0113                 return {end1, end1}; // Everything matches an empty sequence
0114             I1 l1 = end1;
0115             I2 l2 = end2;
0116             --l2;
0117             while(true)
0118             {
0119                 // Find end element in sequence 1 that matches *(end2-1), with a mininum
0120                 // of loop checks
0121                 do
0122                     // return {end1,end1} if no element matches *begin2
0123                     if(begin1 == l1)
0124                         return {end1, end1};
0125                 while(!invoke(pred, invoke(proj, *--l1), *l2));
0126                 // *l1 matches *l2, now match elements before here
0127                 I1 m1 = l1;
0128                 I2 m2 = l2;
0129                 do
0130                     // If pattern exhausted, {m1,++l1} is the answer
0131                     // (works for 1 element pattern)
0132                     if(m2 == begin2)
0133                         return {m1, ++l1};
0134                     // Otherwise if source exhausted, pattern not found
0135                     else if(m1 == begin1)
0136                         return {end1, end1};
0137                 // if there is a mismatch, restart with a new l1
0138                 // else there is a match, check next elements
0139                 while(invoke(pred, invoke(proj, *--m1), *--m2));
0140             }
0141         }
0142
0143         template<typename I1, typename I2, typename R, typename P>
0144         constexpr subrange<I1> find_end_impl(I1 begin1, I1 end1, I2 begin2, I2 end2, R pred, P proj,
0145                                    std::random_access_iterator_tag,
0146                                    std::random_access_iterator_tag)
0147         {
0148             // Take advantage of knowing source and pattern lengths.  Stop short when
0149             // source is smaller than pattern
0150             auto len2 = end2 - begin2;
0151             if(len2 == 0)
0152                 return {end1, end1};
0153             auto len1 = end1 - begin1;
0154             if(len1 < len2)
0155                 return {end1, end1};
0156             I1 const start =
0157                 begin1 + (len2 - 1); // End of pattern match can't go before here
0158             I1 l1 = end1;
0159             I2 l2 = end2;
0160             --l2;
0161             while(true)
0162             {
0163                 do
0164                     if(start == l1)
0165                         return {end1, end1};
0166                 while(!invoke(pred, invoke(proj, *--l1), *l2));
0167                 I1 m1 = l1;
0168                 I2 m2 = l2;
0169                 do
0170                     if(m2 == begin2)
0171                         return {m1, ++l1};
0172                 // no need to check range on m1 because s guarantees we have enough source
0173                 while(invoke(pred, invoke(proj, *--m1), *--m2));
0174             }
0175         }
0176     } // namespace detail
0177     /// \endcond
0178
0179     /// \addtogroup group-algorithms
0180     /// @{
0181     RANGES_FUNC_BEGIN(find_end)
0182
0183         /// \brief function template \c find_end
0184         template(typename I1,
0185                  typename S1,
0186                  typename I2,
0187                  typename S2,
0188                  typename R = equal_to,
0189                  typename P = identity)(
0190             requires forward_iterator<I1> AND sentinel_for<S1, I1> AND
0191                 forward_iterator<I2> AND sentinel_for<S2, I2> AND
0192                 indirect_relation<R, projected<I1, P>, I2>)
0193         constexpr subrange<I1> RANGES_FUNC(find_end)(
0194             I1 begin1, S1 end1, I2 begin2, S2 end2, R pred = R{}, P proj = P{}) //
0195         {
0196             constexpr bool Bidi =
0197                 bidirectional_iterator<I1> && bidirectional_iterator<I2>;
0198             return detail::find_end_impl(begin1,
0199                                          detail::next_to_if<Bidi>(begin1, end1),
0200                                          begin2,
0201                                          detail::next_to_if<Bidi>(begin2, end2),
0202                                          std::move(pred),
0203                                          std::move(proj),
0204                                          iterator_tag_of<I1>(),
0205                                          iterator_tag_of<I2>());
0206         }
0207
0208         /// \overload
0209         template(typename Rng1,
0210                  typename Rng2,
0211                  typename R = equal_to,
0212                  typename P = identity)(
0213             requires forward_range<Rng1> AND forward_range<Rng2> AND
0214                 indirect_relation<R, projected<iterator_t<Rng1>, P>, iterator_t<Rng2>>)
0215         constexpr borrowed_subrange_t<Rng1> RANGES_FUNC(find_end)(
0216             Rng1 && rng1, Rng2 && rng2, R pred = R{}, P proj = P{}) //
0217         {
0218             return (*this)(begin(rng1),
0219                            end(rng1),
0220                            begin(rng2),
0221                            end(rng2),
0222                            std::move(pred),
0223                            std::move(proj));
0224         }
0225
0226     RANGES_FUNC_END(find_end)
0227
0228     namespace cpp20
0229     {
0230         using ranges::find_end;
0231     }
0232     /// @}
0233 } // namespace ranges
0234
0235 #include <range/v3/detail/epilogue.hpp>
0236
0237 #endif