1 /// \file 2 // Range v3 library 3 // 4 // Copyright Eric Niebler 2014-present 5 // 6 // Use, modification and distribution is subject to the 7 // Boost Software License, Version 1.0. (See accompanying 8 // file LICENSE_1_0.txt or copy at 9 // http://www.boost.org/LICENSE_1_0.txt) 10 // 11 // Project home: https://github.com/ericniebler/range-v3 12 // 13 #ifndef RANGES_V3_ALGORITHM_FIND_END_HPP 14 #define RANGES_V3_ALGORITHM_FIND_END_HPP 15 16 #include <utility> 17 18 #include <meta/meta.hpp> 19 20 #include <range/v3/range_fwd.hpp> 21 22 #include <range/v3/functional/comparisons.hpp> 23 #include <range/v3/functional/identity.hpp> 24 #include <range/v3/functional/invoke.hpp> 25 #include <range/v3/iterator/concepts.hpp> 26 #include <range/v3/iterator/operations.hpp> 27 #include <range/v3/iterator/traits.hpp> 28 #include <range/v3/range/access.hpp> 29 #include <range/v3/range/concepts.hpp> 30 #include <range/v3/range/traits.hpp> 31 #include <range/v3/utility/static_const.hpp> 32 #include <range/v3/view/subrange.hpp> 33 34 #include <range/v3/detail/prologue.hpp> 35 36 namespace ranges 37 { 38 /// \cond 39 namespace detail 40 { 41 template(typename I, typename S)( 42 /// \pre 43 requires input_iterator<I> AND sentinel_for<S, I>) 44 I next_to_if(I i, S s, std::true_type) 45 { 46 return ranges::next(i, s); 47 } 48 49 template(typename I, typename S)( 50 /// \pre 51 requires input_iterator<I> AND sentinel_for<S, I>) 52 S next_to_if(I, S s, std::false_type) 53 { 54 return s; 55 } 56 57 template(bool B, typename I, typename S)( 58 /// \pre 59 requires input_iterator<I> AND sentinel_for<S, I>) 60 meta::if_c<B, I, S> next_to_if(I i, S s) 61 { 62 return detail::next_to_if(std::move(i), std::move(s), meta::bool_<B>{}); 63 } 64 65 template<typename I1, typename S1, typename I2, typename S2, typename R, 66 typename P> find_end_impl(I1 begin1,S1 end1,I2 begin2,S2 end2,R pred,P proj,std::forward_iterator_tag,std::forward_iterator_tag)67 subrange<I1> find_end_impl(I1 begin1, S1 end1, I2 begin2, S2 end2, R pred, P proj, 68 std::forward_iterator_tag, std::forward_iterator_tag) 69 { 70 bool found = false; 71 I1 res_begin, res_end; 72 if(begin2 == end2) 73 { 74 auto e1 = ranges::next(begin1, end1); 75 return {e1, e1}; 76 } 77 while(true) 78 { 79 while(true) 80 { 81 if(begin1 == end1) 82 return {(found ? res_begin : begin1), (found ? res_end : begin1)}; 83 if(invoke(pred, invoke(proj, *begin1), *begin2)) 84 break; 85 ++begin1; 86 } 87 auto tmp1 = begin1; 88 auto tmp2 = begin2; 89 while(true) 90 { 91 if(++tmp2 == end2) 92 { 93 res_begin = begin1++; 94 res_end = ++tmp1; 95 found = true; 96 break; 97 } 98 if(++tmp1 == end1) 99 return {(found ? res_begin : tmp1), (found ? res_end : tmp1)}; 100 if(!invoke(pred, invoke(proj, *tmp1), *tmp2)) 101 { 102 ++begin1; 103 break; 104 } 105 } 106 } 107 } 108 109 template<typename I1, typename I2, typename R, typename P> find_end_impl(I1 begin1,I1 end1,I2 begin2,I2 end2,R pred,P proj,std::bidirectional_iterator_tag,std::bidirectional_iterator_tag)110 subrange<I1> find_end_impl(I1 begin1, I1 end1, I2 begin2, I2 end2, R pred, P proj, 111 std::bidirectional_iterator_tag, 112 std::bidirectional_iterator_tag) 113 { 114 // modeled after search algorithm (in reverse) 115 if(begin2 == end2) 116 return {end1, end1}; // Everything matches an empty sequence 117 I1 l1 = end1; 118 I2 l2 = end2; 119 --l2; 120 while(true) 121 { 122 // Find end element in sequence 1 that matches *(end2-1), with a mininum 123 // of loop checks 124 do 125 // return {end1,end1} if no element matches *begin2 126 if(begin1 == l1) 127 return {end1, end1}; 128 while(!invoke(pred, invoke(proj, *--l1), *l2)); 129 // *l1 matches *l2, now match elements before here 130 I1 m1 = l1; 131 I2 m2 = l2; 132 do 133 // If pattern exhausted, {m1,++l1} is the answer 134 // (works for 1 element pattern) 135 if(m2 == begin2) 136 return {m1, ++l1}; 137 // Otherwise if source exhausted, pattern not found 138 else if(m1 == begin1) 139 return {end1, end1}; 140 // if there is a mismatch, restart with a new l1 141 // else there is a match, check next elements 142 while(invoke(pred, invoke(proj, *--m1), *--m2)); 143 } 144 } 145 146 template<typename I1, typename I2, typename R, typename P> find_end_impl(I1 begin1,I1 end1,I2 begin2,I2 end2,R pred,P proj,std::random_access_iterator_tag,std::random_access_iterator_tag)147 subrange<I1> find_end_impl(I1 begin1, I1 end1, I2 begin2, I2 end2, R pred, P proj, 148 std::random_access_iterator_tag, 149 std::random_access_iterator_tag) 150 { 151 // Take advantage of knowing source and pattern lengths. Stop short when 152 // source is smaller than pattern 153 auto len2 = end2 - begin2; 154 if(len2 == 0) 155 return {end1, end1}; 156 auto len1 = end1 - begin1; 157 if(len1 < len2) 158 return {end1, end1}; 159 I1 const start = 160 begin1 + (len2 - 1); // End of pattern match can't go before here 161 I1 l1 = end1; 162 I2 l2 = end2; 163 --l2; 164 while(true) 165 { 166 do 167 if(start == l1) 168 return {end1, end1}; 169 while(!invoke(pred, invoke(proj, *--l1), *l2)); 170 I1 m1 = l1; 171 I2 m2 = l2; 172 do 173 if(m2 == begin2) 174 return {m1, ++l1}; 175 // no need to check range on m1 because s guarantees we have enough source 176 while(invoke(pred, invoke(proj, *--m1), *--m2)); 177 } 178 } 179 } // namespace detail 180 /// \endcond 181 182 /// \addtogroup group-algorithms 183 /// @{ RANGES_FUNC_BEGIN(find_end)184 RANGES_FUNC_BEGIN(find_end) 185 186 /// \brief function template \c find_end 187 template(typename I1, 188 typename S1, 189 typename I2, 190 typename S2, 191 typename R = equal_to, 192 typename P = identity)( 193 /// \pre 194 requires forward_iterator<I1> AND sentinel_for<S1, I1> AND 195 forward_iterator<I2> AND sentinel_for<S2, I2> AND 196 indirect_relation<R, projected<I1, P>, I2>) 197 subrange<I1> RANGES_FUNC(find_end)( 198 I1 begin1, S1 end1, I2 begin2, S2 end2, R pred = R{}, P proj = P{}) // 199 { 200 constexpr bool Bidi = 201 bidirectional_iterator<I1> && bidirectional_iterator<I2>; 202 return detail::find_end_impl(begin1, 203 detail::next_to_if<Bidi>(begin1, end1), 204 begin2, 205 detail::next_to_if<Bidi>(begin2, end2), 206 std::move(pred), 207 std::move(proj), 208 iterator_tag_of<I1>(), 209 iterator_tag_of<I2>()); 210 } 211 212 /// \overload 213 template(typename Rng1, 214 typename Rng2, 215 typename R = equal_to, 216 typename P = identity)( 217 /// \pre 218 requires forward_range<Rng1> AND forward_range<Rng2> AND 219 indirect_relation<R, projected<iterator_t<Rng1>, P>, iterator_t<Rng2>>) RANGES_FUNC(find_end)220 borrowed_subrange_t<Rng1> RANGES_FUNC(find_end)( 221 Rng1 && rng1, Rng2 && rng2, R pred = R{}, P proj = P{}) // 222 { 223 return (*this)(begin(rng1), 224 end(rng1), 225 begin(rng2), 226 end(rng2), 227 std::move(pred), 228 std::move(proj)); 229 } 230 231 RANGES_FUNC_END(find_end) 232 233 namespace cpp20 234 { 235 using ranges::find_end; 236 } 237 /// @} 238 } // namespace ranges 239 240 #include <range/v3/detail/epilogue.hpp> 241 242 #endif 243