Horizon
equal_range_n.hpp
Go to the documentation of this file.
1
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_AUX_EQUAL_RANGE_N_HPP
14#define RANGES_V3_ALGORITHM_AUX_EQUAL_RANGE_N_HPP
15
16#include <functional>
17
19
30#include <range/v3/utility/static_const.hpp>
32
33#include <range/v3/detail/prologue.hpp>
34
35namespace 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
The forward_iterator concept.
The indirect_strict_weak_order concept.
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