v3/algorithm/nth_element.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2014-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
0014 //===----------------------------------------------------------------------===//
0015 //
0016 //                     The LLVM Compiler Infrastructure
0017 //
0018 // This file is dual licensed under the MIT and the University of Illinois Open
0019 // Source Licenses. See LICENSE.TXT for details.
0020 //
0021 //===----------------------------------------------------------------------===//
0022
0023 #ifndef RANGES_V3_ALGORITHM_NTH_ELEMENT_HPP
0024 #define RANGES_V3_ALGORITHM_NTH_ELEMENT_HPP
0025
0026 #include <utility>
0027
0028 #include <range/v3/range_fwd.hpp>
0029
0030 #include <range/v3/algorithm/min_element.hpp>
0031 #include <range/v3/functional/comparisons.hpp>
0032 #include <range/v3/functional/identity.hpp>
0033 #include <range/v3/functional/invoke.hpp>
0034 #include <range/v3/iterator/concepts.hpp>
0035 #include <range/v3/iterator/operations.hpp>
0036 #include <range/v3/iterator/traits.hpp>
0037 #include <range/v3/range/access.hpp>
0038 #include <range/v3/range/concepts.hpp>
0039 #include <range/v3/range/dangling.hpp>
0040 #include <range/v3/range/traits.hpp>
0041 #include <range/v3/utility/optional.hpp>
0042 #include <range/v3/utility/static_const.hpp>
0043 #include <range/v3/utility/swap.hpp>
0044
0045 #include <range/v3/detail/prologue.hpp>
0046
0047 namespace ranges
0048 {
0049     /// \cond
0050     namespace detail
0051     {
0052         // stable, 2-3 compares, 0-2 swaps
0053
0054         template(typename I, typename C, typename P)(
0055             requires forward_iterator<I> AND indirect_relation<C, projected<I, P>>)
0056         unsigned sort3(I x, I y, I z, C & pred, P & proj)
0057         {
0058             unsigned r = 0;
0059             if(!invoke(pred, invoke(proj, *y), invoke(proj, *x))) // if x <= y
0060             {
0061                 if(!invoke(pred, invoke(proj, *z), invoke(proj, *y))) // if y <= z
0062                     return r;                                         // x <= y && y <= z
0063                                                                       // x <= y && y > z
0064                 ranges::iter_swap(y, z);                              // x <= z && y < z
0065                 r = 1;
0066                 if(invoke(pred, invoke(proj, *y), invoke(proj, *x))) // if x > y
0067                 {
0068                     ranges::iter_swap(x, y); // x < y && y <= z
0069                     r = 2;
0070                 }
0071                 return r; // x <= y && y < z
0072             }
0073             if(invoke(pred, invoke(proj, *z), invoke(proj, *y))) // x > y, if y > z
0074             {
0075                 ranges::iter_swap(x, z); // x < y && y < z
0076                 r = 1;
0077                 return r;
0078             }
0079             ranges::iter_swap(x, y);                             // x > y && y <= z
0080             r = 1;                                               // x < y && x <= z
0081             if(invoke(pred, invoke(proj, *z), invoke(proj, *y))) // if y > z
0082             {
0083                 ranges::iter_swap(y, z); // x <= y && y < z
0084                 r = 2;
0085             }
0086             return r;
0087         } // x <= y && y <= z
0088
0089         template(typename I, typename C, typename P)(
0090             requires bidirectional_iterator<I> AND indirect_relation<C, projected<I, P>>)
0091         void selection_sort(I first, I last, C & pred, P & proj)
0092         {
0093             RANGES_EXPECT(first != last);
0094             for(I lm1 = ranges::prev(last); first != lm1; ++first)
0095             {
0096                 I i = ranges::min_element(first, last, std::ref(pred), std::ref(proj));
0097                 if(i != first)
0098                     ranges::iter_swap(first, i);
0099             }
0100         }
0101     } // namespace detail
0102     /// \endcond
0103
0104     /// \addtogroup group-algorithms
0105     /// @{
0106     RANGES_FUNC_BEGIN(nth_element)
0107
0108         /// \brief function template \c nth_element
0109         template(typename I, typename S, typename C = less, typename P = identity)(
0110             requires random_access_iterator<I> AND sortable<I, C, P>)
0111         constexpr I RANGES_FUNC(nth_element)(
0112             I first, I nth, S end_, C pred = C{}, P proj = P{}) //
0113         {
0114             I last = ranges::next(nth, end_), end_orig = last;
0115             // C is known to be a reference type
0116             using difference_type = iter_difference_t<I>;
0117             difference_type const limit = 7;
0118             while(true)
0119             {
0120                 if(nth == last)
0121                     return end_orig;
0122                 difference_type len = last - first;
0123                 switch(len)
0124                 {
0125                 case 0:
0126                 case 1:
0127                     return end_orig;
0128                 case 2:
0129                     if(invoke(pred, invoke(proj, *--last), invoke(proj, *first)))
0130                         ranges::iter_swap(first, last);
0131                     return end_orig;
0132                 case 3:
0133                 {
0134                     I m = first;
0135                     detail::sort3(first, ++m, --last, pred, proj);
0136                     return end_orig;
0137                 }
0138                 }
0139                 if(len <= limit)
0140                 {
0141                     detail::selection_sort(first, last, pred, proj);
0142                     return end_orig;
0143                 }
0144                 // len > limit >= 3
0145                 I m = first + len / 2;
0146                 I lm1 = last;
0147                 unsigned n_swaps = detail::sort3(first, m, --lm1, pred, proj);
0148                 // *m is median
0149                 // partition [first, m) < *m and *m <= [m, last)
0150                 //(this inhibits tossing elements equivalent to m around unnecessarily)
0151                 I i = first;
0152                 I j = lm1;
0153                 // j points beyond range to be tested, *lm1 is known to be <= *m
0154                 // The search going up is known to be guarded but the search coming down
0155                 // isn't. Prime the downward search with a guard.
0156                 if(!invoke(pred, invoke(proj, *i), invoke(proj, *m))) // if *first == *m
0157                 {
0158                     // *first == *m, *first doesn't go in first part
0159                     // manually guard downward moving j against i
0160                     while(true)
0161                     {
0162                         if(i == --j)
0163                         {
0164                             // *first == *m, *m <= all other elements
0165                             // Parition instead into [first, i) == *first and *first < [i,
0166                             // last)
0167                             ++i; // first + 1
0168                             j = last;
0169                             if(!invoke(
0170                                    pred,
0171                                    invoke(proj, *first),
0172                                    invoke(
0173                                        proj,
0174                                        *--j))) // we need a guard if *first == *(last-1)
0175                             {
0176                                 while(true)
0177                                 {
0178                                     if(i == j)
0179                                         return end_orig; // [first, last) all equivalent
0180                                                          // elements
0181                                     if(invoke(
0182                                            pred, invoke(proj, *first), invoke(proj, *i)))
0183                                     {
0184                                         ranges::iter_swap(i, j);
0185                                         ++n_swaps;
0186                                         ++i;
0187                                         break;
0188                                     }
0189                                     ++i;
0190                                 }
0191                             }
0192                             // [first, i) == *first and *first < [j, last) and j == last -
0193                             // 1
0194                             if(i == j)
0195                                 return end_orig;
0196                             while(true)
0197                             {
0198                                 while(
0199                                     !invoke(pred, invoke(proj, *first), invoke(proj, *i)))
0200                                     ++i;
0201                                 while(invoke(
0202                                     pred, invoke(proj, *first), invoke(proj, *--j)))
0203                                     ;
0204                                 if(i >= j)
0205                                     break;
0206                                 ranges::iter_swap(i, j);
0207                                 ++n_swaps;
0208                                 ++i;
0209                             }
0210                             // [first, i) == *first and *first < [i, last)
0211                             // The first part is sorted,
0212                             if(nth < i)
0213                                 return end_orig;
0214                             // nth_element the second part
0215                             // nth_element<C>(i, nth, last, pred);
0216                             first = i;
0217                             continue;
0218                         }
0219                         if(invoke(pred, invoke(proj, *j), invoke(proj, *m)))
0220                         {
0221                             ranges::iter_swap(i, j);
0222                             ++n_swaps;
0223                             break; // found guard for downward moving j, now use unguarded
0224                                    // partition
0225                         }
0226                     }
0227                 }
0228                 ++i;
0229                 // j points beyond range to be tested, *lm1 is known to be <= *m
0230                 // if not yet partitioned...
0231                 if(i < j)
0232                 {
0233                     // known that *(i - 1) < *m
0234                     while(true)
0235                     {
0236                         // m still guards upward moving i
0237                         while(invoke(pred, invoke(proj, *i), invoke(proj, *m)))
0238                             ++i;
0239                         // It is now known that a guard exists for downward moving j
0240                         while(!invoke(pred, invoke(proj, *--j), invoke(proj, *m)))
0241                             ;
0242                         if(i >= j)
0243                             break;
0244                         ranges::iter_swap(i, j);
0245                         ++n_swaps;
0246                         // It is known that m != j
0247                         // If m just moved, follow it
0248                         if(m == i)
0249                             m = j;
0250                         ++i;
0251                     }
0252                 }
0253                 // [first, i) < *m and *m <= [i, last)
0254                 if(i != m && invoke(pred, invoke(proj, *m), invoke(proj, *i)))
0255                 {
0256                     ranges::iter_swap(i, m);
0257                     ++n_swaps;
0258                 }
0259                 // [first, i) < *i and *i <= [i+1, last)
0260                 if(nth == i)
0261                     return end_orig;
0262                 const auto optional_return = [&]() -> ranges::optional<I> {
0263                     if(n_swaps == 0)
0264                     {
0265                         // We were given a perfectly partitioned sequence.  Coincidence?
0266                         if(nth < i)
0267                         {
0268                             // Check for [first, i) already sorted
0269                             j = m = first;
0270                             while(++j != i)
0271                             {
0272                                 if(invoke(pred, invoke(proj, *j), invoke(proj, *m)))
0273                                     // not yet sorted, so sort
0274                                     return ranges::nullopt;
0275                                 m = j;
0276                             }
0277                             // [first, i) sorted
0278                             return end_orig;
0279                         }
0280                         else
0281                         {
0282                             // Check for [i, last) already sorted
0283                             j = m = i;
0284                             while(++j != last)
0285                             {
0286                                 if(invoke(pred, invoke(proj, *j), invoke(proj, *m)))
0287                                     // not yet sorted, so sort
0288                                     return ranges::nullopt;
0289                                 m = j;
0290                             }
0291                             // [i, last) sorted
0292                             return end_orig;
0293                         }
0294                     }
0295                     return ranges::nullopt;
0296                 }();
0297                 if(optional_return)
0298                 {
0299                     return *optional_return;
0300                 }
0301                 // nth_element on range containing nth
0302                 if(nth < i)
0303                 {
0304                     // nth_element<C>(first, nth, i, pred);
0305                     last = i;
0306                 }
0307                 else
0308                 {
0309                     // nth_element<C>(i+1, nth, last, pred);
0310                     first = ++i;
0311                 }
0312             }
0313             return end_orig;
0314         }
0315
0316         /// \overload
0317         template(typename Rng, typename C = less, typename P = identity)(
0318             requires random_access_range<Rng> AND sortable<iterator_t<Rng>, C, P>)
0319         constexpr borrowed_iterator_t<Rng> RANGES_FUNC(nth_element)(
0320             Rng && rng, iterator_t<Rng> nth, C pred = C{}, P proj = P{}) //
0321         {
0322             return (*this)(
0323                 begin(rng), std::move(nth), end(rng), std::move(pred), std::move(proj));
0324         }
0325
0326     RANGES_FUNC_END(nth_element)
0327
0328     namespace cpp20
0329     {
0330         using ranges::nth_element;
0331     }
0332     /// @}
0333 } // namespace ranges
0334
0335 #include <range/v3/detail/epilogue.hpp>
0336
0337 #endif