v3/algorithm/partial_sort_copy.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_PARTIAL_SORT_COPY_HPP
0014 #define RANGES_V3_ALGORITHM_PARTIAL_SORT_COPY_HPP
0015
0016 #include <meta/meta.hpp>
0017
0018 #include <range/v3/range_fwd.hpp>
0019
0020 #include <range/v3/algorithm/heap_algorithm.hpp>
0021 #include <range/v3/functional/comparisons.hpp>
0022 #include <range/v3/functional/identity.hpp>
0023 #include <range/v3/functional/invoke.hpp>
0024 #include <range/v3/iterator/concepts.hpp>
0025 #include <range/v3/iterator/traits.hpp>
0026 #include <range/v3/range/access.hpp>
0027 #include <range/v3/range/concepts.hpp>
0028 #include <range/v3/range/dangling.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(partial_sort_copy)
0039
0040         /// \brief function template \c partial_sort_copy
0041         template(typename I,
0042                  typename SI,
0043                  typename O,
0044                  typename SO,
0045                  typename C = less,
0046                  typename PI = identity,
0047                  typename PO = identity)(
0048             requires input_iterator<I> AND sentinel_for<SI, I> AND
0049                 random_access_iterator<O> AND sentinel_for<SO, O> AND
0050                 indirectly_copyable<I, O> AND sortable<O, C, PO> AND
0051                 indirect_strict_weak_order<C, projected<I, PI>, projected<O, PO>>)
0052         constexpr O RANGES_FUNC(partial_sort_copy)(I first,
0053                                                    SI last,
0054                                                    O out_begin,
0055                                                    SO out_end,
0056                                                    C pred = C{},
0057                                                    PI in_proj = PI{},
0058                                                    PO out_proj = PO{}) //
0059         {
0060             O r = out_begin;
0061             if(r != out_end)
0062             {
0063                 for(; first != last && r != out_end; ++first, ++r)
0064                     *r = *first;
0065                 make_heap(out_begin, r, ranges::ref(pred), ranges::ref(out_proj));
0066                 auto len = r - out_begin;
0067                 for(; first != last; ++first)
0068                 {
0069                     auto && x = *first;
0070                     if(invoke(pred, invoke(in_proj, x), invoke(out_proj, *out_begin)))
0071                     {
0072                         *out_begin = (decltype(x) &&)x;
0073                         detail::sift_down_n(out_begin,
0074                                             len,
0075                                             out_begin,
0076                                             ranges::ref(pred),
0077                                             ranges::ref(out_proj));
0078                     }
0079                 }
0080                 sort_heap(out_begin, r, ranges::ref(pred), ranges::ref(out_proj));
0081             }
0082             return r;
0083         }
0084
0085         /// \overload
0086         template(typename InRng,
0087                  typename OutRng,
0088                  typename C = less,
0089                  typename PI = identity,
0090                  typename PO = identity)(
0091             requires input_range<InRng> AND random_access_range<OutRng> AND
0092                 indirectly_copyable<iterator_t<InRng>, iterator_t<OutRng>> AND
0093                 sortable<iterator_t<OutRng>, C, PO> AND
0094                 indirect_strict_weak_order<C,
0095                                            projected<iterator_t<InRng>, PI>,
0096                                            projected<iterator_t<OutRng>, PO>>)
0097         constexpr borrowed_iterator_t<OutRng> RANGES_FUNC(partial_sort_copy)(InRng && in_rng,
0098                                                                              OutRng && out_rng,
0099                                                                              C pred = C{},
0100                                                                              PI in_proj = PI{},
0101                                                                              PO out_proj = PO{}) //
0102         {
0103             return (*this)(begin(in_rng),
0104                            end(in_rng),
0105                            begin(out_rng),
0106                            end(out_rng),
0107                            std::move(pred),
0108                            std::move(in_proj),
0109                            std::move(out_proj));
0110         }
0111
0112     RANGES_FUNC_END(partial_sort_copy)
0113
0114     namespace cpp20
0115     {
0116         using ranges::partial_sort_copy;
0117     }
0118     /// @}
0119 } // namespace ranges
0120
0121 #include <range/v3/detail/epilogue.hpp>
0122
0123 #endif