Branch data Line data Source code
1 : : // Copyright 2019 Silexica GmbH, Lichtstr. 25, Cologne, Germany. All rights reserved.
2 : : //
3 : : // Licensed under the Apache License, Version 2.0 (the "License");
4 : : // you may not use this file except in compliance with the License.
5 : : // You may obtain a copy of the License at
6 : : //
7 : : // http://www.apache.org/licenses/LICENSE-2.0
8 : : //
9 : : // Unless required by applicable law or agreed to in writing, software
10 : : // distributed under the License is distributed on an "AS IS" BASIS,
11 : : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : : // See the License for the specific language governing permissions and
13 : : // limitations under the License.
14 : : /// \file
15 : : /// \brief This file provides an iterative quick sort implementation.
16 : : #ifndef AUTOWARE_AUTO_ALGORITHM__QUICK_SORT_HPP_
17 : : #define AUTOWARE_AUTO_ALGORITHM__QUICK_SORT_HPP_
18 : :
19 : : #include <algorithm>
20 : : #include <functional>
21 : : #include <utility>
22 : : #include <vector>
23 : :
24 : : namespace autoware
25 : : {
26 : :
27 : : namespace common
28 : : {
29 : :
30 : : namespace algorithm
31 : : {
32 : :
33 : : /// \brief Iterative quick sort implementation based on a stack.
34 : : template<typename Container, typename RandomIt = typename Container::iterator>
35 [ + - - - : 9 : class QuickSorter
+ - - - +
- - - + -
- - + - -
- + - - -
+ - - - +
- - - - +
- - ]
36 : : {
37 : : public:
38 : : QuickSorter(QuickSorter const &) = delete;
39 : : QuickSorter & operator=(QuickSorter const &) = delete;
40 : : QuickSorter(QuickSorter &&) = default;
41 : : /// \brief Move equals operator
42 : : QuickSorter & operator=(QuickSorter &&) = default;
43 : :
44 : : /// \brief Default constructor, do not reserve capacity for stack
45 : : QuickSorter() = default;
46 : :
47 : : /// \brief Construct and reserve capacity for stack
48 : : /// \param[in] capacity - The maximum capacity of the container to be sorted
49 : 8 : explicit QuickSorter(::std::size_t capacity)
50 [ + - ]: 8 : {
51 : : reserve(capacity);
52 : 8 : }
53 : :
54 : : /// \brief Iterative quick sort implementation using a stack, sorts
55 : : /// range [first, last) using the given comparison function
56 : : /// \param[in] first Start of the range to sort
57 : : /// \param[in] last End of the range to sort (not included)
58 : : /// \param[in] comp The comparison function to base the sorting on
59 : : template<typename Compare>
60 [ + + ]: 9 : void sort(RandomIt first, RandomIt last, Compare comp) const
61 : : {
62 [ + + ]: 9 : if (::std::distance(first, last) < 2) {
63 : : return;
64 : : }
65 : :
66 : : // Make sure we do not accidently have an already partially filled stack,
67 : : // capacity does not change
68 [ - + ]: 7 : m_stack.clear();
69 : :
70 : : // Add first interval to the stack for sorting, from here on last is really
71 : : // the last element and not the element after, i.e. not end
72 : 7 : m_stack.push_back(first);
73 : 7 : m_stack.push_back(last - 1);
74 : :
75 [ + + ]: 27 : while (!m_stack.empty()) {
76 : 20 : last = m_stack.back();
77 : : m_stack.pop_back();
78 : 20 : first = m_stack.back();
79 : : m_stack.pop_back();
80 : :
81 : : auto part = QuickSorter::partition(first, last, comp);
82 : :
83 [ + + ]: 20 : if (part > first + 1) {
84 : 8 : m_stack.push_back(first);
85 : 8 : m_stack.push_back(part - 1);
86 : : }
87 : :
88 [ + + ]: 20 : if (part < last - 1) {
89 : 5 : m_stack.push_back(part + 1);
90 : 5 : m_stack.push_back(last);
91 : : }
92 : : }
93 : : }
94 : :
95 : : /// \brief Iterative quick sort implementation using a stack, sorts
96 : : /// range [first, last) using the default less operation
97 : : /// \param[in] first Start of the range to sort
98 : : /// \param[in] last End of the range to sort (not included)
99 : : void sort(RandomIt first, RandomIt last) const
100 : : {
101 [ + - + - : 9 : sort(first, last, ::std::less<const decltype(*first)>());
+ - + - +
- + - + -
+ - + - ]
102 : 9 : }
103 : :
104 : : /// \brief Reserves helper stack capacity for the iterative quick sort
105 : : /// algorithm based on the capacity of the container to be sorted such that
106 : : /// no heap allocation is done during the algorithm.
107 : : /// \param[in] capacity - The maximum capacity of the container to be sorted
108 : : void reserve(::std::size_t capacity)
109 : : {
110 : : // The maximum partition depth is n/2 + 1, which means we need a maximum
111 : : // capacity of n + 2 to hold store the iterators in the stack.
112 [ + - ]: 8 : m_stack.reserve(capacity + 2);
113 : 8 : }
114 : :
115 : : /// \brief Returns the maximum capacity that is allowed for a container to be
116 : : /// sorted.
117 : : /// \return The maximum capacity that a container may have if it is to be sorted
118 : : /// using this sorter.
119 : : ::std::size_t capacity() const
120 : : {
121 [ + - + - : 17 : if (m_stack.capacity() < 2) {
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - -
+ ]
122 : : return 0;
123 : : }
124 : 16 : return m_stack.capacity() - 2;
125 : : }
126 : :
127 : : private:
128 : : /// \brief Partition range [first, last], based on pivot element last. After
129 : : /// execution all elements smaller than the pivot element are left of it and
130 : : /// all bigger elements right of it.
131 : : /// \param[in] first Start of the range to partition
132 : : /// \param[in] last End (included) of the range to partition, used as pivot
133 : : /// \param[in] comp Element comparison function
134 : : /// \return Iterator to the pivot element in the range
135 : : template<typename Compare>
136 : : static RandomIt partition(RandomIt first, RandomIt last, Compare comp)
137 : : {
138 : : auto prev = first;
139 : :
140 : : // Iterate over range and swap whenever element is smaller than the pivot
141 : : // element.
142 [ + + ]: 71 : for (auto it = first; it < last; it++) {
143 [ + + ]: 51 : if (comp(*it, *last)) {
144 : : ::std::iter_swap(it, prev);
145 : : prev++;
146 : : }
147 : : }
148 : :
149 : : // Swap the pivot element into place
150 : : ::std::iter_swap(prev, last);
151 : : return prev;
152 : : }
153 : :
154 : : private:
155 : : /// Helper stack used for sorting, needs to have capacity (last-first)+2
156 : : mutable ::std::vector<RandomIt> m_stack;
157 : : };
158 : :
159 : : } // namespace algorithm
160 : :
161 : : } // namespace common
162 : :
163 : : } // namespace autoware
164 : :
165 : : #endif // AUTOWARE_AUTO_ALGORITHM__QUICK_SORT_HPP_
|