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