v3/algorithm/binary_search.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2013-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_BINARY_SEARCH_HPP
0014 #define RANGES_V3_ALGORITHM_BINARY_SEARCH_HPP
0015
0016 #include <functional>
0017 #include <utility>
0018
0019 #include <range/v3/range_fwd.hpp>
0020
0021 #include <range/v3/algorithm/lower_bound.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/iterator/concepts.hpp>
0026 #include <range/v3/iterator/traits.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
0032 #include <range/v3/detail/prologue.hpp>
0033
0034 namespace ranges
0035 {
0036     /// \addtogroup group-algorithms
0037     /// @{
0038     RANGES_FUNC_BEGIN(binary_search)
0039         /// \brief function template \c binary_search
0040         ///
0041         /// range-based version of the \c binary_search std algorithm
0042         ///
0043         /// \pre `Rng` is a model of the `range` concept
0044         template(typename I,
0045                  typename S,
0046                  typename V,
0047                  typename C = less,
0048                  typename P = identity)(
0049             requires forward_iterator<I> AND sentinel_for<S, I> AND
0050                 indirect_strict_weak_order<C, V const *, projected<I, P>>)
0051         constexpr bool RANGES_FUNC(binary_search)(
0052             I first, S last, V const & val, C pred = C{}, P proj = P{})
0053         {
0054             first =
0055                 lower_bound(std::move(first), last, val, ranges::ref(pred), ranges::ref(proj));
0056             return first != last && !invoke(pred, val, invoke(proj, *first));
0057         }
0058
0059         /// \overload
0060         template(typename Rng, typename V, typename C = less, typename P = identity)(
0061             requires forward_range<Rng> AND
0062                 indirect_strict_weak_order<C, V const *, projected<iterator_t<Rng>, P>>)
0063         constexpr bool RANGES_FUNC(binary_search)(
0064             Rng && rng, V const & val, C pred = C{}, P proj = P{}) //
0065         {
0066             static_assert(!is_infinite<Rng>::value,
0067                           "Trying to binary search an infinite range");
0068             return (*this)(begin(rng), end(rng), val, std::move(pred), std::move(proj));
0069         }
0070     RANGES_FUNC_END(binary_search)
0071
0072     namespace cpp20
0073     {
0074         using ranges::binary_search;
0075     }
0076     /// @}
0077 } // namespace ranges
0078
0079 #include <range/v3/detail/epilogue.hpp>
0080
0081 #endif