1 /// \file 2 // Range v3 library 3 // 4 // Copyright Eric Niebler 2013-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 // Copyright (c) 1994 14 // Hewlett-Packard Company 15 // 16 // Permission to use, copy, modify, distribute and sell this software 17 // and its documentation for any purpose is hereby granted without fee, 18 // provided that the above copyright notice appear in all copies and 19 // that both that copyright notice and this permission notice appear 20 // in supporting documentation. Hewlett-Packard Company makes no 21 // representations about the suitability of this software for any 22 // purpose. It is provided "as is" without express or implied warranty. 23 // 24 // Copyright (c) 1996 25 // Silicon Graphics Computer Systems, Inc. 26 // 27 // Permission to use, copy, modify, distribute and sell this software 28 // and its documentation for any purpose is hereby granted without fee, 29 // provided that the above copyright notice appear in all copies and 30 // that both that copyright notice and this permission notice appear 31 // in supporting documentation. Silicon Graphics makes no 32 // representations about the suitability of this software for any 33 // purpose. It is provided "as is" without express or implied warranty. 34 // 35 36 #ifndef RANGES_V3_ALGORITHM_SORT_HPP 37 #define RANGES_V3_ALGORITHM_SORT_HPP 38 39 #include <range/v3/range_fwd.hpp> 40 41 #include <range/v3/algorithm/heap_algorithm.hpp> 42 #include <range/v3/algorithm/move_backward.hpp> 43 #include <range/v3/algorithm/partial_sort.hpp> 44 #include <range/v3/functional/comparisons.hpp> 45 #include <range/v3/functional/identity.hpp> 46 #include <range/v3/functional/invoke.hpp> 47 #include <range/v3/iterator/concepts.hpp> 48 #include <range/v3/iterator/operations.hpp> 49 #include <range/v3/iterator/traits.hpp> 50 #include <range/v3/range/access.hpp> 51 #include <range/v3/range/concepts.hpp> 52 #include <range/v3/range/dangling.hpp> 53 #include <range/v3/range/traits.hpp> 54 #include <range/v3/utility/static_const.hpp> 55 56 #include <range/v3/detail/prologue.hpp> 57 58 namespace ranges 59 { 60 /// \cond 61 namespace detail 62 { 63 template<typename I, typename C, typename P> unguarded_partition(I first,I last,C & pred,P & proj)64 inline I unguarded_partition(I first, I last, C & pred, P & proj) 65 { 66 I mid = first + (last - first) / 2, penultimate = ranges::prev(last); 67 auto &&x = *first, &&y = *mid, &&z = *penultimate; 68 auto &&a = invoke(proj, (decltype(x) &&)x), 69 &&b = invoke(proj, (decltype(y) &&)y), 70 &&c = invoke(proj, (decltype(z) &&)z); 71 72 // Find the median: 73 I pivot_pnt = 74 invoke(pred, a, b) 75 ? (invoke(pred, b, c) ? mid 76 : (invoke(pred, a, c) ? penultimate : first)) 77 : (invoke(pred, a, c) ? first 78 : (invoke(pred, b, c) ? penultimate : mid)); 79 80 // Do the partition: 81 while(true) 82 { 83 auto && v = *pivot_pnt; 84 auto && pivot = invoke(proj, (decltype(v) &&)v); 85 while(invoke(pred, invoke(proj, *first), pivot)) 86 ++first; 87 --last; 88 while(invoke(pred, pivot, invoke(proj, *last))) 89 --last; 90 if(!(first < last)) 91 return first; 92 ranges::iter_swap(first, last); 93 pivot_pnt = 94 pivot_pnt == first ? last : (pivot_pnt == last ? first : pivot_pnt); 95 ++first; 96 } 97 } 98 99 template<typename I, typename C, typename P> unguarded_linear_insert(I last,iter_value_t<I> val,C & pred,P & proj)100 inline void unguarded_linear_insert(I last, iter_value_t<I> val, C & pred, 101 P & proj) 102 { 103 I next = prev(last); 104 while(invoke(pred, invoke(proj, val), invoke(proj, *next))) 105 { 106 *last = iter_move(next); 107 last = next; 108 --next; 109 } 110 *last = std::move(val); 111 } 112 113 template<typename I, typename C, typename P> linear_insert(I first,I last,C & pred,P & proj)114 inline void linear_insert(I first, I last, C & pred, P & proj) 115 { 116 iter_value_t<I> val = iter_move(last); 117 if(invoke(pred, invoke(proj, val), invoke(proj, *first))) 118 { 119 move_backward(first, last, last + 1); 120 *first = std::move(val); 121 } 122 else 123 detail::unguarded_linear_insert(last, std::move(val), pred, proj); 124 } 125 126 template<typename I, typename C, typename P> insertion_sort(I first,I last,C & pred,P & proj)127 inline void insertion_sort(I first, I last, C & pred, P & proj) 128 { 129 if(first == last) 130 return; 131 for(I i = next(first); i != last; ++i) 132 detail::linear_insert(first, i, pred, proj); 133 } 134 135 template<typename I, typename C, typename P> unguarded_insertion_sort(I first,I last,C & pred,P & proj)136 inline void unguarded_insertion_sort(I first, I last, C & pred, P & proj) 137 { 138 for(I i = first; i != last; ++i) 139 detail::unguarded_linear_insert(i, iter_move(i), pred, proj); 140 } 141 introsort_threshold()142 constexpr int introsort_threshold() 143 { 144 return 16; 145 } 146 147 template<typename I, typename C, typename P> final_insertion_sort(I first,I last,C & pred,P & proj)148 inline void final_insertion_sort(I first, I last, C & pred, P & proj) 149 { 150 if(last - first > detail::introsort_threshold()) 151 { 152 detail::insertion_sort( 153 first, first + detail::introsort_threshold(), pred, proj); 154 detail::unguarded_insertion_sort( 155 first + detail::introsort_threshold(), last, pred, proj); 156 } 157 else 158 detail::insertion_sort(first, last, pred, proj); 159 } 160 161 template<typename Size> log2(Size n)162 inline Size log2(Size n) 163 { 164 Size k = 0; 165 for(; n != 1; n >>= 1) 166 ++k; 167 return k; 168 } 169 170 template<typename I, typename Size, typename C, typename P> introsort_loop(I first,I last,Size depth_limit,C & pred,P & proj)171 inline void introsort_loop(I first, I last, Size depth_limit, C & pred, P & proj) 172 { 173 while(last - first > detail::introsort_threshold()) 174 { 175 if(depth_limit == 0) 176 return partial_sort( 177 first, last, last, std::ref(pred), std::ref(proj)), 178 void(); 179 I cut = detail::unguarded_partition(first, last, pred, proj); 180 detail::introsort_loop(cut, last, --depth_limit, pred, proj); 181 last = cut; 182 } 183 } 184 } // namespace detail 185 /// \endcond 186 187 /// \addtogroup group-algorithms 188 /// @{ 189 190 // Introsort: Quicksort to a certain depth, then Heapsort. Insertion 191 // sort below a certain threshold. 192 // TODO Forward iterators, like EoP? 193 194 RANGES_FUNC_BEGIN(sort) 195 196 /// \brief function template \c sort 197 template(typename I, typename S, typename C = less, typename P = identity)( 198 /// \pre 199 requires sortable<I, C, P> AND random_access_iterator<I> AND 200 sentinel_for<S, I>) 201 I RANGES_FUNC(sort)(I first, S end_, C pred = C{}, P proj = P{}) 202 { 203 I last = ranges::next(first, std::move(end_)); 204 if(first != last) 205 { 206 detail::introsort_loop( 207 first, last, detail::log2(last - first) * 2, pred, proj); 208 detail::final_insertion_sort(first, last, pred, proj); 209 } 210 return last; 211 } 212 213 /// \overload 214 template(typename Rng, typename C = less, typename P = identity)( 215 /// \pre 216 requires sortable<iterator_t<Rng>, C, P> AND random_access_range<Rng>) 217 borrowed_iterator_t<Rng> // 218 RANGES_FUNC(sort)(Rng && rng, C pred = C{}, P proj = P{}) // 219 { 220 return (*this)(begin(rng), end(rng), std::move(pred), std::move(proj)); 221 } 222 223 RANGES_FUNC_END(sort) 224 225 namespace cpp20 226 { 227 using ranges::sort; 228 } 229 /// @} 230 } // namespace ranges 231 232 #include <range/v3/detail/epilogue.hpp> 233 234 #endif 235