algorithm/aux_/partition_point_n.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2014-present
0005 //  Copyright Casey Carter 2016
0006 //
0007 //  Use, modification and distribution is subject to the
0008 //  Boost Software License, Version 1.0. (See accompanying
0009 //  file LICENSE_1_0.txt or copy at
0010 //  http://www.boost.org/LICENSE_1_0.txt)
0011 //
0012 // Project home: https://github.com/ericniebler/range-v3
0013 //
0014 #ifndef RANGES_V3_ALGORITHM_AUX_PARTITION_POINT_N_HPP
0015 #define RANGES_V3_ALGORITHM_AUX_PARTITION_POINT_N_HPP
0016
0017 #include <range/v3/range_fwd.hpp>
0018
0019 #include <range/v3/functional/identity.hpp>
0020 #include <range/v3/functional/invoke.hpp>
0021 #include <range/v3/iterator/operations.hpp>
0022 #include <range/v3/utility/static_const.hpp>
0023
0024 #include <range/v3/detail/prologue.hpp>
0025
0026 namespace ranges
0027 {
0028     namespace aux
0029     {
0030         struct partition_point_n_fn
0031         {
0032             template(typename I, typename C, typename P = identity)(
0033                 requires forward_iterator<I> AND
0034                         indirect_unary_predicate<C, projected<I, P>>)
0035             constexpr I operator()(I first,
0036                                    iter_difference_t<I> d,
0037                                    C pred,
0038                                    P proj = P{}) const //
0039             {
0040                 if(0 < d)
0041                 {
0042                     do
0043                     {
0044                         auto half = d / 2;
0045                         auto middle = next(uncounted(first), half);
0046                         if(invoke(pred, invoke(proj, *middle)))
0047                         {
0048                             first = recounted(first, std::move(++middle), half + 1);
0049                             d -= half + 1;
0050                         }
0051                         else
0052                             d = half;
0053                     } while(0 != d);
0054                 }
0055                 return first;
0056             }
0057         };
0058
0059         RANGES_INLINE_VARIABLE(partition_point_n_fn, partition_point_n)
0060     } // namespace aux
0061 } // namespace ranges
0062
0063 #include <range/v3/detail/epilogue.hpp>
0064
0065 #endif