Horizon
equal_range_n.hpp
Go to the documentation of this file.
1 // 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_AUX_EQUAL_RANGE_N_HPP
14 #define RANGES_V3_ALGORITHM_AUX_EQUAL_RANGE_N_HPP
15 
16 #include <functional>
17 
18 #include <range/v3/range_fwd.hpp>
19 
30 #include <range/v3/utility/static_const.hpp>
32 
33 #include <range/v3/detail/prologue.hpp>
34 
35 namespace ranges
36 {
37  namespace aux
38  {
40  {
41  template(typename I, typename V, typename R = less, typename P = identity)(
42  requires forward_iterator<I> AND
43  indirect_strict_weak_order<R, V const *, projected<I, P>>)
44  constexpr subrange<I> operator()(I first,
45  iter_difference_t<I> dist,
46  V const & val,
47  R pred = R{},
48  P proj = P{}) const
49  {
50  if(0 < dist)
51  {
52  do
53  {
54  auto half = dist / 2;
55  auto middle = ranges::next(first, half);
56  auto && v = *middle;
57  auto && pv = invoke(proj, (decltype(v) &&)v);
58  if(invoke(pred, pv, val))
59  {
60  first = std::move(++middle);
61  dist -= half + 1;
62  }
63  else if(invoke(pred, val, pv))
64  {
65  dist = half;
66  }
67  else
68  {
69  return {lower_bound_n(std::move(first),
70  half,
71  val,
72  ranges::ref(pred),
73  ranges::ref(proj)),
74  upper_bound_n(ranges::next(middle),
75  dist - (half + 1),
76  val,
77  ranges::ref(pred),
78  ranges::ref(proj))};
79  }
80  } while(0 != dist);
81  }
82  return {first, first};
83  }
84  };
85 
87  } // namespace aux
88 } // namespace ranges
89 
90 #include <range/v3/detail/epilogue.hpp>
91 
92 #endif
CPP_concept indirect_strict_weak_order
\concept indirect_strict_weak_order
Definition: concepts.hpp:689
RANGES_INLINE_VARIABLE(detail::to_container_fn< detail::from_range< std::vector >>, to_vector) template< template< typename... > class ContT > auto to(RANGES_HIDDEN_DETAIL(detail
For initializing a container of the specified type with the elements of an Range.
Definition: conversion.hpp:399
typename Fn::template invoke< Args... > invoke
Evaluate the invocable Fn with the arguments Args.
Definition: meta.hpp:541
front< Pair > first
Retrieve the first element of the pair Pair.
Definition: meta.hpp:2251
bool_<(T::type::value< U::type::value)> less
A Boolean integral constant wrapper around true if T::type::value is less than U::type::value; false,...
Definition: meta.hpp:255
Definition: equal_range_n.hpp:40
Definition: identity.hpp:25
Definition: subrange.hpp:196