]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /* |
2 | Copyright (c) Marshall Clow 2008-2012. | |
3 | ||
4 | Distributed under the Boost Software License, Version 1.0. (See accompanying | |
5 | file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | Revision history: | |
8 | 28 Sep 2015 mtc First version | |
9 | ||
10 | */ | |
11 | ||
12 | /// \file sort_subrange.hpp | |
13 | /// \brief Sort a subrange | |
14 | /// \author Marshall Clow | |
15 | /// | |
16 | /// Suggested by Sean Parent in his CppCon 2015 keynote | |
17 | ||
18 | #ifndef BOOST_ALGORITHM_SORT_SUBRANGE_HPP | |
19 | #define BOOST_ALGORITHM_SORT_SUBRANGE_HPP | |
20 | ||
21 | #include <functional> // For std::less | |
22 | #include <iterator> // For std::iterator_traits | |
23 | #include <algorithm> // For nth_element and partial_sort | |
24 | ||
92f5a8d4 | 25 | #include <boost/config.hpp> |
7c673cae FG |
26 | #include <boost/range/begin.hpp> |
27 | #include <boost/range/end.hpp> | |
28 | ||
29 | namespace boost { namespace algorithm { | |
30 | ||
31 | /// \fn sort_subrange ( T const& val, | |
32 | /// Iterator first, Iterator last, | |
33 | /// Iterator sub_first, Iterator sub_last, | |
34 | /// Pred p ) | |
35 | /// \brief Sort the subrange [sub_first, sub_last) that is inside | |
36 | /// the range [first, last) as if you had sorted the entire range. | |
37 | /// | |
38 | /// \param first The start of the larger range | |
39 | /// \param last The end of the larger range | |
40 | /// \param sub_first The start of the sub range | |
41 | /// \param sub_last The end of the sub range | |
42 | /// \param p A predicate to use to compare the values. | |
43 | /// p ( a, b ) returns a boolean. | |
44 | /// | |
45 | template<typename Iterator, typename Pred> | |
46 | void sort_subrange ( | |
47 | Iterator first, Iterator last, | |
48 | Iterator sub_first, Iterator sub_last, | |
49 | Pred p) | |
50 | { | |
51 | if (sub_first == sub_last) return; // the empty sub-range is already sorted. | |
52 | ||
53 | if (sub_first != first) { // sub-range is at the start, don't need to partition | |
54 | (void) std::nth_element(first, sub_first, last, p); | |
55 | ++sub_first; | |
56 | } | |
57 | std::partial_sort(sub_first, sub_last, last, p); | |
58 | } | |
59 | ||
60 | ||
61 | ||
62 | template<typename Iterator> | |
63 | void sort_subrange (Iterator first, Iterator last, Iterator sub_first, Iterator sub_last) | |
64 | { | |
65 | typedef typename std::iterator_traits<Iterator>::value_type value_type; | |
66 | return sort_subrange(first, last, sub_first, sub_last, std::less<value_type>()); | |
67 | } | |
68 | ||
69 | /// range versions? | |
70 | ||
71 | ||
72 | /// \fn partition_subrange ( T const& val, | |
73 | /// Iterator first, Iterator last, | |
74 | /// Iterator sub_first, Iterator sub_last, | |
75 | /// Pred p ) | |
76 | /// \brief Gather the elements of the subrange [sub_first, sub_last) that is | |
77 | /// inside the range [first, last) as if you had sorted the entire range. | |
78 | /// | |
79 | /// \param first The start of the larger range | |
80 | /// \param last The end of the larger range | |
81 | /// \param sub_first The start of the sub range | |
82 | /// \param sub_last The end of the sub range | |
83 | /// \param p A predicate to use to compare the values. | |
84 | /// p ( a, b ) returns a boolean. | |
85 | /// | |
86 | template<typename Iterator, typename Pred> | |
87 | void partition_subrange ( | |
88 | Iterator first, Iterator last, | |
89 | Iterator sub_first, Iterator sub_last, | |
90 | Pred p) | |
91 | { | |
92 | if (sub_first != first) { | |
93 | (void) std::nth_element(first, sub_first, last, p); | |
94 | ++sub_first; | |
95 | } | |
96 | ||
97 | if (sub_last != last) | |
98 | (void) std::nth_element(sub_first, sub_last, last, p); | |
99 | } | |
100 | ||
101 | template<typename Iterator> | |
102 | void partition_subrange (Iterator first, Iterator last, Iterator sub_first, Iterator sub_last) | |
103 | { | |
104 | typedef typename std::iterator_traits<Iterator>::value_type value_type; | |
105 | return partition_subrange(first, last, sub_first, sub_last, std::less<value_type>()); | |
106 | } | |
107 | ||
108 | }} | |
109 | ||
110 | #endif // BOOST_ALGORITHM_SORT_SUBRANGE_HPP |