algorithm/aux_/equal_range_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 #ifndef RANGES_V3_ALGORITHM_AUX_EQUAL_RANGE_N_HPP
0014 #define RANGES_V3_ALGORITHM_AUX_EQUAL_RANGE_N_HPP
0015
0016 #include <functional>
0017
0018 #include <range/v3/range_fwd.hpp>
0019
0020 #include <range/v3/algorithm/aux_/lower_bound_n.hpp>
0021 #include <range/v3/algorithm/aux_/upper_bound_n.hpp>
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/functional/reference_wrapper.hpp>
0026 #include <range/v3/iterator/operations.hpp>
0027 #include <range/v3/range/access.hpp>
0028 #include <range/v3/range/concepts.hpp>
0029 #include <range/v3/range/traits.hpp>
0030 #include <range/v3/utility/static_const.hpp>
0031 #include <range/v3/view/subrange.hpp>
0032
0033 #include <range/v3/detail/prologue.hpp>
0034
0035 namespace ranges
0036 {
0037     namespace aux
0038     {
0039         struct equal_range_n_fn
0040         {
0041             template(typename I, typename V, typename R = less, typename P = identity)(
0042                 requires forward_iterator<I> AND
0043                     indirect_strict_weak_order<R, V const *, projected<I, P>>)
0044             constexpr subrange<I> operator()(I first,
0045                                              iter_difference_t<I> dist,
0046                                              V const & val,
0047                                              R pred = R{},
0048                                              P proj = P{}) const
0049             {
0050                 if(0 < dist)
0051                 {
0052                     do
0053                     {
0054                         auto half = dist / 2;
0055                         auto middle = ranges::next(first, half);
0056                         auto && v = *middle;
0057                         auto && pv = invoke(proj, (decltype(v) &&)v);
0058                         if(invoke(pred, pv, val))
0059                         {
0060                             first = std::move(++middle);
0061                             dist -= half + 1;
0062                         }
0063                         else if(invoke(pred, val, pv))
0064                         {
0065                             dist = half;
0066                         }
0067                         else
0068                         {
0069                             return {lower_bound_n(std::move(first),
0070                                                   half,
0071                                                   val,
0072                                                   ranges::ref(pred),
0073                                                   ranges::ref(proj)),
0074                                     upper_bound_n(ranges::next(middle),
0075                                                   dist - (half + 1),
0076                                                   val,
0077                                                   ranges::ref(pred),
0078                                                   ranges::ref(proj))};
0079                         }
0080                     } while(0 != dist);
0081                 }
0082                 return {first, first};
0083             }
0084         };
0085
0086         RANGES_INLINE_VARIABLE(equal_range_n_fn, equal_range_n)
0087     } // namespace aux
0088 } // namespace ranges
0089
0090 #include <range/v3/detail/epilogue.hpp>
0091
0092 #endif