v3/algorithm/search.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_HPP
0022 #define RANGES_V3_ALGORITHM_SEARCH_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 I1, typename S1, typename D1, typename I2, typename S2,
0052                  typename D2, typename C, typename P1, typename P2>
0053         constexpr subrange<I1> search_sized_impl(I1 const begin1_,
0054                                                  S1 end1,
0055                                                  D1 const d1_,
0056                                                  I2 begin2,
0057                                                  S2 end2,
0058                                                  D2 d2,
0059                                                  C & pred,
0060                                                  P1 & proj1,
0061                                                  P2 & proj2)
0062         {
0063             D1 d1 = d1_;
0064             auto begin1 = uncounted(begin1_);
0065             while(true)
0066             {
0067                 // Find first element in sequence 1 that matches *begin2, with a mininum
0068                 // of loop checks
0069                 while(true)
0070                 {
0071                     if(d1 < d2) // return the last if we've run out of room
0072                     {
0073                         auto e =
0074                             ranges::next(recounted(begin1_, std::move(begin1), d1_ - d1),
0075                                          std::move(end1));
0076                         return {e, e};
0077                     }
0078                     if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
0079                         break;
0080                     ++begin1;
0081                     --d1;
0082                 }
0083                 // *begin1 matches *begin2, now match elements after here
0084                 auto m1 = begin1;
0085                 I2 m2 = begin2;
0086                 while(true)
0087                 {
0088                     if(++m2 == end2) // If pattern exhausted, begin1 is the answer (works
0089                                      // for 1 element pattern)
0090                     {
0091                         return {recounted(begin1_, std::move(begin1), d1_ - d1),
0092                                 recounted(begin1_, std::move(++m1), d1_ - d1)};
0093                     }
0094                     ++m1; // No need to check, we know we have room to match successfully
0095                     if(!invoke(
0096                            pred,
0097                            invoke(proj1, *m1),
0098                            invoke(
0099                                proj2,
0100                                *m2))) // if there is a mismatch, restart with a new begin1
0101                     {
0102                         ++begin1;
0103                         --d1;
0104                         break;
0105                     } // else there is a match, check next elements
0106                 }
0107             }
0108         }
0109
0110         template<typename I1, typename S1, typename I2, typename S2, typename C,
0111                  typename P1, typename P2>
0112         constexpr subrange<I1> search_impl(I1 begin1,
0113                                            S1 end1,
0114                                            I2 begin2,
0115                                            S2 end2,
0116                                            C & pred,
0117                                            P1 & proj1,
0118                                            P2 & proj2)
0119         {
0120             while(true)
0121             {
0122                 // Find first element in sequence 1 that matches *begin2, with a mininum
0123                 // of loop checks
0124                 while(true)
0125                 {
0126                     if(begin1 == end1) // return end1 if no element matches *begin2
0127                         return {begin1, begin1};
0128                     if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
0129                         break;
0130                     ++begin1;
0131                 }
0132                 // *begin1 matches *begin2, now match elements after here
0133                 I1 m1 = begin1;
0134                 I2 m2 = begin2;
0135                 while(true)
0136                 {
0137                     if(++m2 == end2) // If pattern exhausted, begin1 is the answer (works
0138                                      // for 1 element pattern)
0139                         return {begin1, ++m1};
0140                     if(++m1 == end1) // Otherwise if source exhausted, pattern not found
0141                         return {m1, m1};
0142                     if(!invoke(
0143                            pred,
0144                            invoke(proj1, *m1),
0145                            invoke(
0146                                proj2,
0147                                *m2))) // if there is a mismatch, restart with a new begin1
0148                     {
0149                         ++begin1;
0150                         break;
0151                     } // else there is a match, check next elements
0152                 }
0153             }
0154         }
0155     } // namespace detail
0156     /// \endcond
0157
0158     RANGES_FUNC_BEGIN(search)
0159
0160         /// \brief function template \c search
0161         template(typename I1,
0162                  typename S1,
0163                  typename I2,
0164                  typename S2,
0165                  typename C = equal_to,
0166                  typename P1 = identity,
0167                  typename P2 = identity)(
0168             requires forward_iterator<I1> AND sentinel_for<S1, I1> AND
0169                 forward_iterator<I2> AND sentinel_for<S2, I2> AND
0170                 indirectly_comparable<I1, I2, C, P1, P2>)
0171         constexpr subrange<I1> RANGES_FUNC(search)(I1 begin1,
0172                                                    S1 end1,
0173                                                    I2 begin2,
0174                                                    S2 end2,
0175                                                    C pred = C{},
0176                                                    P1 proj1 = P1{},
0177                                                    P2 proj2 = P2{}) //
0178         {
0179             if(begin2 == end2)
0180                 return {begin1, begin1};
0181             if(RANGES_CONSTEXPR_IF(sized_sentinel_for<S1, I1> &&
0182                                    sized_sentinel_for<S2, I2>))
0183                 return detail::search_sized_impl(std::move(begin1),
0184                                                  std::move(end1),
0185                                                  distance(begin1, end1),
0186                                                  std::move(begin2),
0187                                                  std::move(end2),
0188                                                  distance(begin2, end2),
0189                                                  pred,
0190                                                  proj1,
0191                                                  proj2);
0192             else
0193                 return detail::search_impl(std::move(begin1),
0194                                            std::move(end1),
0195                                            std::move(begin2),
0196                                            std::move(end2),
0197                                            pred,
0198                                            proj1,
0199                                            proj2);
0200         }
0201
0202         /// \overload
0203         template(typename Rng1,
0204                  typename Rng2,
0205                  typename C = equal_to,
0206                  typename P1 = identity,
0207                  typename P2 = identity)(
0208             requires forward_range<Rng1> AND forward_range<Rng2> AND
0209                 indirectly_comparable<iterator_t<Rng1>, iterator_t<Rng2>, C, P1, P2>)
0210         constexpr borrowed_subrange_t<Rng1> RANGES_FUNC(search)(
0211             Rng1 && rng1, Rng2 && rng2, C pred = C{}, P1 proj1 = P1{}, P2 proj2 = P2{}) //
0212         {
0213             if(empty(rng2))
0214                 return subrange<iterator_t<Rng1>>{begin(rng1), begin(rng1)};
0215             if(RANGES_CONSTEXPR_IF(sized_range<Rng1> && sized_range<Rng2>))
0216                 return detail::search_sized_impl(begin(rng1),
0217                                                  end(rng1),
0218                                                  distance(rng1),
0219                                                  begin(rng2),
0220                                                  end(rng2),
0221                                                  distance(rng2),
0222                                                  pred,
0223                                                  proj1,
0224                                                  proj2);
0225             else
0226                 return detail::search_impl(
0227                     begin(rng1), end(rng1), begin(rng2), end(rng2), pred, proj1, proj2);
0228         }
0229
0230     RANGES_FUNC_END(search)
0231
0232     namespace cpp20
0233     {
0234         using ranges::search;
0235     }
0236     /// @}
0237 } // namespace ranges
0238
0239 #include <range/v3/detail/epilogue.hpp>
0240
0241 #endif