Anklang-0.3.0.dev502+ga23511a1 anklang-0.3.0.dev502+ga23511a1
ASE — Anklang Sound Engine (C++)
« « « Anklang Documentation
Loading...
Searching...
No Matches
sortnet.hh
Go to the documentation of this file.
1 // This Source Code Form is licensed MPL-2.0: http://mozilla.org/MPL/2.0
2#ifndef __ASE_SORTNET_HH__
3#define __ASE_SORTNET_HH__
4
5#include <functional>
6#include <algorithm>
7
8namespace Ase {
9
10namespace SortingNetworks {
11
12template<class RandomIt, class Compare> inline __attribute__ ((always_inline)) void
13srt (RandomIt &v1, RandomIt &v2, Compare lesser)
14{
15 // optimize for *not* needing to swap
16 if (__builtin_expect (lesser (v2, v1), 0))
17 std::swap (v2, v1);
18}
19
20template<class RandomIt, class Compare> void
21sort_3 (RandomIt v, Compare c)
22{
23 srt (v[0], v[1], c); srt (v[0], v[2], c); srt (v[1], v[2], c);
24}
25
26template<class RandomIt, class Compare> void __attribute__ ((noinline))
27sort_4 (RandomIt v, Compare c)
28{
29 // oddevenmerge 4
30 srt (v[0], v[1], c); srt (v[2], v[3], c); srt (v[0], v[2], c);
31 srt (v[1], v[3], c); srt (v[1], v[2], c);
32}
33
34template<class RandomIt, class Compare> void __attribute__ ((noinline))
35sort_5 (RandomIt v, Compare c)
36{
37 // bitonic 5
38 srt (v[0], v[1], c); srt (v[3], v[4], c); srt (v[2], v[4], c); srt (v[2], v[3], c); srt (v[1], v[4], c);
39 srt (v[1], v[2], c); srt (v[0], v[3], c); srt (v[0], v[1], c); srt (v[2], v[3], c);
40}
41
42template<class RandomIt, class Compare> void __attribute__ ((noinline))
43sort_6 (RandomIt v, Compare c)
44{
45 // oddevenmerge 6
46 srt (v[0], v[1], c); srt (v[2], v[3], c); srt (v[4], v[5], c); srt (v[0], v[2], c);
47 srt (v[1], v[3], c); srt (v[1], v[2], c); srt (v[0], v[4], c); srt (v[2], v[4], c);
48 srt (v[1], v[5], c); srt (v[3], v[5], c); srt (v[1], v[2], c); srt (v[3], v[4], c);
49}
50
51template<class RandomIt, class Compare> void __attribute__ ((noinline))
52sort_7 (RandomIt v, Compare c)
53{
54 // oddevenmerge 7
55 srt (v[0], v[1], c); srt (v[2], v[3], c); srt (v[4], v[5], c); srt (v[0], v[2], c);
56 srt (v[1], v[3], c); srt (v[4], v[6], c); srt (v[1], v[2], c); srt (v[5], v[6], c);
57 srt (v[0], v[4], c); srt (v[2], v[6], c); srt (v[1], v[5], c); srt (v[2], v[4], c);
58 srt (v[3], v[5], c); srt (v[1], v[2], c); srt (v[3], v[4], c); srt (v[5], v[6], c);
59}
60
61template<class RandomIt, class Compare> void __attribute__ ((noinline))
62sort_8 (RandomIt v, Compare c)
63{
64 // oddevenmerge 8
65 srt (v[0], v[1], c); srt (v[2], v[3], c); srt (v[4], v[5], c); srt (v[6], v[7], c); srt (v[0], v[2], c);
66 srt (v[1], v[3], c); srt (v[4], v[6], c); srt (v[5], v[7], c); srt (v[1], v[2], c); srt (v[5], v[6], c);
67 srt (v[0], v[4], c); srt (v[3], v[7], c); srt (v[2], v[6], c); srt (v[1], v[5], c); srt (v[2], v[4], c);
68 srt (v[3], v[5], c); srt (v[1], v[2], c); srt (v[3], v[4], c); srt (v[5], v[6], c);
69}
70
71template<class RandomIt, class Compare> void __attribute__ ((noinline))
72sort_9 (RandomIt v, Compare c)
73{
74 // https://imada.sdu.dk/~petersk/sn/
75 srt (v[0], v[1], c); srt (v[2], v[3], c); srt (v[4], v[5], c); srt (v[6], v[7], c); srt (v[1], v[3], c);
76 srt (v[5], v[7], c); srt (v[0], v[2], c); srt (v[4], v[6], c); srt (v[1], v[5], c); srt (v[3], v[7], c);
77 srt (v[0], v[4], c); srt (v[2], v[6], c); srt (v[1], v[8], c); srt (v[2], v[4], c); srt (v[3], v[5], c);
78 srt (v[1], v[2], c); srt (v[4], v[8], c); srt (v[2], v[4], c); srt (v[6], v[8], c); srt (v[0], v[1], c);
79 srt (v[5], v[8], c); srt (v[3], v[6], c); srt (v[3], v[4], c); srt (v[5], v[6], c); srt (v[7], v[8], c);
80}
81
82template<class RandomIt, class Compare> void __attribute__ ((noinline))
83sort_10 (RandomIt v, Compare c)
84{
85 // D. E. Knuth. The art of computer programming, vol. 3: Sorting and Searching, 2nd edition. Addison-Wesley, 1998
86 srt (v[0], v[8], c); srt (v[1], v[9], c); srt (v[2], v[7], c); srt (v[3], v[5], c); srt (v[4], v[6], c);
87 srt (v[0], v[2], c); srt (v[1], v[4], c); srt (v[5], v[8], c); srt (v[7], v[9], c); srt (v[0], v[3], c);
88 srt (v[2], v[4], c); srt (v[5], v[7], c); srt (v[6], v[9], c); srt (v[0], v[1], c); srt (v[3], v[6], c);
89 srt (v[8], v[9], c); srt (v[1], v[5], c); srt (v[2], v[3], c); srt (v[4], v[8], c); srt (v[6], v[7], c);
90 srt (v[1], v[2], c); srt (v[3], v[5], c); srt (v[4], v[6], c); srt (v[7], v[8], c); srt (v[2], v[3], c);
91 srt (v[4], v[5], c); srt (v[6], v[7], c); srt (v[3], v[4], c); srt (v[5], v[6], c);
92}
93
94template<class RandomIt, class Compare> void __attribute__ ((noinline))
95sort_11 (RandomIt v, Compare c)
96{
97 // Harder, Jannis; https://github.com/jix/sortnetopt
98 srt (v[0], v[9], c); srt (v[1], v[6], c); srt (v[2], v[4], c); srt (v[3], v[7], c); srt (v[5], v[8], c);
99 srt (v[0], v[1], c); srt (v[3], v[5], c); srt (v[4], v[10], c); srt (v[6], v[9], c); srt (v[7], v[8], c);
100 srt (v[1], v[3], c); srt (v[2], v[5], c); srt (v[4], v[7], c); srt (v[8], v[10], c); srt (v[0], v[4], c);
101 srt (v[1], v[2], c); srt (v[3], v[7], c); srt (v[5], v[9], c); srt (v[6], v[8], c); srt (v[0], v[1], c);
102 srt (v[2], v[6], c); srt (v[4], v[5], c); srt (v[7], v[8], c); srt (v[9], v[10], c); srt (v[2], v[4], c);
103 srt (v[3], v[6], c); srt (v[5], v[7], c); srt (v[8], v[9], c); srt (v[1], v[2], c); srt (v[3], v[4], c);
104 srt (v[5], v[6], c); srt (v[7], v[8], c); srt (v[2], v[3], c); srt (v[4], v[5], c); srt (v[6], v[7], c);
105}
106
107template<class RandomIt, class Compare> void __attribute__ ((noinline))
108sort_12 (RandomIt v, Compare c)
109{
110 // Harder, Jannis; https://github.com/jix/sortnetopt
111 srt (v[0], v[8], c); srt (v[1], v[7], c); srt (v[2], v[6], c); srt (v[3], v[11], c); srt (v[4], v[10], c);
112 srt (v[5], v[9], c); srt (v[0], v[1], c); srt (v[2], v[5], c); srt (v[3], v[4], c); srt (v[6], v[9], c);
113 srt (v[7], v[8], c); srt (v[10], v[11], c); srt (v[0], v[2], c); srt (v[1], v[6], c); srt (v[5], v[10], c);
114 srt (v[9], v[11], c); srt (v[0], v[3], c); srt (v[1], v[2], c); srt (v[4], v[6], c); srt (v[5], v[7], c);
115 srt (v[8], v[11], c); srt (v[9], v[10], c); srt (v[1], v[4], c); srt (v[3], v[5], c); srt (v[6], v[8], c);
116 srt (v[7], v[10], c); srt (v[1], v[3], c); srt (v[2], v[5], c); srt (v[6], v[9], c); srt (v[8], v[10], c);
117 srt (v[2], v[3], c); srt (v[4], v[5], c); srt (v[6], v[7], c); srt (v[8], v[9], c); srt (v[4], v[6], c);
118 srt (v[5], v[7], c); srt (v[3], v[4], c); srt (v[5], v[6], c); srt (v[7], v[8], c);
119}
120
121template<class RandomIt, class Compare> void __attribute__ ((noinline))
122sort_13 (RandomIt v, Compare c)
123{
124 // http://bertdobbelaere.github.io/sorting_networks.html
125 srt (v[0], v[12], c); srt (v[1], v[10], c); srt (v[2], v[9], c); srt (v[3], v[7], c); srt (v[5], v[11], c);
126 srt (v[6], v[8], c); srt (v[1], v[6], c); srt (v[2], v[3], c); srt (v[4], v[11], c); srt (v[7], v[9], c);
127 srt (v[8], v[10], c); srt (v[0], v[4], c); srt (v[1], v[2], c); srt (v[3], v[6], c); srt (v[7], v[8], c);
128 srt (v[9], v[10], c); srt (v[11], v[12], c); srt (v[4], v[6], c); srt (v[5], v[9], c); srt (v[8], v[11], c);
129 srt (v[10], v[12], c); srt (v[0], v[5], c); srt (v[3], v[8], c); srt (v[4], v[7], c); srt (v[6], v[11], c);
130 srt (v[9], v[10], c); srt (v[0], v[1], c); srt (v[2], v[5], c); srt (v[6], v[9], c); srt (v[7], v[8], c);
131 srt (v[10], v[11], c); srt (v[1], v[3], c); srt (v[2], v[4], c); srt (v[5], v[6], c); srt (v[9], v[10], c);
132 srt (v[1], v[2], c); srt (v[3], v[4], c); srt (v[5], v[7], c); srt (v[6], v[8], c); srt (v[2], v[3], c);
133 srt (v[4], v[5], c); srt (v[6], v[7], c); srt (v[8], v[9], c); srt (v[3], v[4], c); srt (v[5], v[6], c);
134}
135
136template<class RandomIt, class Compare> void __attribute__ ((noinline))
137sort_14 (RandomIt v, Compare c)
138{
139 // http://bertdobbelaere.github.io/sorting_networks.html
140 srt (v[0], v[6], c); srt (v[1], v[11], c); srt (v[2], v[12], c); srt (v[3], v[10], c); srt (v[4], v[5], c);
141 srt (v[7], v[13], c); srt (v[8], v[9], c); srt (v[1], v[2], c); srt (v[3], v[7], c); srt (v[4], v[8], c);
142 srt (v[5], v[9], c); srt (v[6], v[10], c); srt (v[11], v[12], c); srt (v[0], v[4], c); srt (v[1], v[3], c);
143 srt (v[5], v[6], c); srt (v[7], v[8], c); srt (v[9], v[13], c); srt (v[10], v[12], c); srt (v[0], v[1], c);
144 srt (v[2], v[9], c); srt (v[3], v[7], c); srt (v[4], v[11], c); srt (v[6], v[10], c); srt (v[12], v[13], c);
145 srt (v[2], v[5], c); srt (v[4], v[7], c); srt (v[6], v[9], c); srt (v[8], v[11], c); srt (v[1], v[2], c);
146 srt (v[3], v[4], c); srt (v[6], v[7], c); srt (v[9], v[10], c); srt (v[11], v[12], c); srt (v[1], v[3], c);
147 srt (v[2], v[4], c); srt (v[5], v[6], c); srt (v[7], v[8], c); srt (v[9], v[11], c); srt (v[10], v[12], c);
148 srt (v[2], v[3], c); srt (v[4], v[7], c); srt (v[6], v[9], c); srt (v[10], v[11], c); srt (v[4], v[5], c);
149 srt (v[6], v[7], c); srt (v[8], v[9], c); srt (v[3], v[4], c); srt (v[5], v[6], c); srt (v[7], v[8], c);
150 srt (v[9], v[10], c);
151}
152
153template<class RandomIt, class Compare> void __attribute__ ((noinline))
154sort_15 (RandomIt v, Compare c)
155{
156 // http://bertdobbelaere.github.io/sorting_networks.html
157 srt (v[1], v[2], c); srt (v[3], v[10], c); srt (v[4], v[14], c); srt (v[5], v[8], c); srt (v[6], v[13], c);
158 srt (v[7], v[12], c); srt (v[9], v[11], c); srt (v[0], v[14], c); srt (v[1], v[5], c); srt (v[2], v[8], c);
159 srt (v[3], v[7], c); srt (v[6], v[9], c); srt (v[10], v[12], c); srt (v[11], v[13], c); srt (v[0], v[7], c);
160 srt (v[1], v[6], c); srt (v[2], v[9], c); srt (v[4], v[10], c); srt (v[5], v[11], c); srt (v[8], v[13], c);
161 srt (v[12], v[14], c); srt (v[0], v[6], c); srt (v[2], v[4], c); srt (v[3], v[5], c); srt (v[7], v[11], c);
162 srt (v[8], v[10], c); srt (v[9], v[12], c); srt (v[13], v[14], c); srt (v[0], v[3], c); srt (v[1], v[2], c);
163 srt (v[4], v[7], c); srt (v[5], v[9], c); srt (v[6], v[8], c); srt (v[10], v[11], c); srt (v[12], v[13], c);
164 srt (v[0], v[1], c); srt (v[2], v[3], c); srt (v[4], v[6], c); srt (v[7], v[9], c); srt (v[10], v[12], c);
165 srt (v[11], v[13], c); srt (v[1], v[2], c); srt (v[3], v[5], c); srt (v[8], v[10], c); srt (v[11], v[12], c);
166 srt (v[3], v[4], c); srt (v[5], v[6], c); srt (v[7], v[8], c); srt (v[9], v[10], c); srt (v[2], v[3], c);
167 srt (v[4], v[5], c); srt (v[6], v[7], c); srt (v[8], v[9], c); srt (v[10], v[11], c); srt (v[5], v[6], c);
168 srt (v[7], v[8], c);
169}
170
171template<class RandomIt, class Compare> void __attribute__ ((noinline))
172sort_16 (RandomIt v, Compare c)
173{
174 // http://bertdobbelaere.github.io/sorting_networks.html
175 srt (v[0], v[13], c); srt (v[1], v[12], c); srt (v[2], v[15], c); srt (v[3], v[14], c); srt (v[4], v[8], c);
176 srt (v[5], v[6], c); srt (v[7], v[11], c); srt (v[9], v[10], c); srt (v[0], v[5], c); srt (v[1], v[7], c);
177 srt (v[2], v[9], c); srt (v[3], v[4], c); srt (v[6], v[13], c); srt (v[8], v[14], c); srt (v[10], v[15], c);
178 srt (v[11], v[12], c); srt (v[0], v[1], c); srt (v[2], v[3], c); srt (v[4], v[5], c); srt (v[6], v[8], c);
179 srt (v[7], v[9], c); srt (v[10], v[11], c); srt (v[12], v[13], c); srt (v[14], v[15], c); srt (v[0], v[2], c);
180 srt (v[1], v[3], c); srt (v[4], v[10], c); srt (v[5], v[11], c); srt (v[6], v[7], c); srt (v[8], v[9], c);
181 srt (v[12], v[14], c); srt (v[13], v[15], c); srt (v[1], v[2], c); srt (v[3], v[12], c); srt (v[4], v[6], c);
182 srt (v[5], v[7], c); srt (v[8], v[10], c); srt (v[9], v[11], c); srt (v[13], v[14], c); srt (v[1], v[4], c);
183 srt (v[2], v[6], c); srt (v[5], v[8], c); srt (v[7], v[10], c); srt (v[9], v[13], c); srt (v[11], v[14], c);
184 srt (v[2], v[4], c); srt (v[3], v[6], c); srt (v[9], v[12], c); srt (v[11], v[13], c); srt (v[3], v[5], c);
185 srt (v[6], v[8], c); srt (v[7], v[9], c); srt (v[10], v[12], c); srt (v[3], v[4], c); srt (v[5], v[6], c);
186 srt (v[7], v[8], c); srt (v[9], v[10], c); srt (v[11], v[12], c); srt (v[6], v[7], c); srt (v[8], v[9], c);
187}
188
189} // SortingNetworks
190
192template<class RandomIt, class Compare> inline void
193fixed_sort (RandomIt first, RandomIt last,
194 Compare comp = std::less<typename std::iterator_traits<RandomIt>::value_type>())
195{
196 using namespace SortingNetworks;
197 const size_t n = last - first;
198 switch (n)
199 {
200 case 0: break;
201 case 1: break;
202 case 2: return srt (first[0], first[1], comp);
203 case 3: return sort_3 (first, comp);
204 case 4: return sort_4 (first, comp);
205 case 5: return sort_5 (first, comp);
206 case 6: return sort_6 (first, comp);
207 case 7: return sort_7 (first, comp);
208 case 8: return sort_8 (first, comp);
209 case 9: return sort_9 (first, comp);
210 case 10: return sort_10 (first, comp);
211 case 11: return sort_11 (first, comp);
212 case 12: return sort_12 (first, comp);
213 case 13: return sort_13 (first, comp);
214 case 14: return sort_14 (first, comp);
215 case 15: return sort_15 (first, comp);
216 case 16: return sort_16 (first, comp);
217 default: return std::sort (first, last, comp);
218 }
219}
220
222template<class T, class Less = std::less<T>>
223class SortedVector : private Less {
224 std::vector<T> v_;
225public:
226 using size_type = typename std::vector<T>::size_type;
227 using value_type = typename std::vector<T>::value_type;
228 using iterator = typename std::vector<T>::iterator;
229 using const_iterator = typename std::vector<T>::const_iterator;
230 using reverse_iterator = typename std::vector<T>::reverse_iterator;
231 using const_reverse_iterator = typename std::vector<T>::const_reverse_iterator;
232 using const_reference = typename std::vector<T>::const_reference;
233 constexpr void reserve (size_type n) { v_.reserve (n); }
234 constexpr size_type capacity () const noexcept { return v_.capacity(); }
235 constexpr const_iterator begin () const noexcept { return v_.begin(); }
236 constexpr const_iterator end () const noexcept { return v_.end(); }
237 constexpr const_reverse_iterator crbegin () const noexcept { return v_.crbegin(); }
238 constexpr const_reverse_iterator crend () const noexcept { return v_.crend(); }
239 constexpr const_reverse_iterator rbegin () const noexcept { return v_.rbegin(); }
240 constexpr const_reverse_iterator rend () const noexcept { return v_.rend(); }
241 constexpr void clear () noexcept { v_.clear(); }
242 constexpr bool empty () const noexcept { return v_.empty(); }
243 constexpr iterator erase (const_iterator first, const_iterator last) { return v_.erase (first, last); }
244 constexpr iterator erase (const_iterator position) { return v_.erase (position); }
245 constexpr iterator replace (const value_type &val) { return insert (val, true); }
246 constexpr size_type size () const noexcept { return v_.size(); }
247 constexpr void shrink_to_fit () { v_.shrink_to_fit(); }
248 constexpr bool sorted (const bool allow_multiple = false) const { return sorted (*this, allow_multiple); }
249 constexpr bool contains (const value_type &val) const { return end() != find (val); }
250 constexpr const_iterator find (const value_type &val) const { return const_cast<SortedVector&> (*this).find (val); }
251 constexpr const_reference front () const noexcept { return v_.front(); }
252 constexpr const_reference back () const noexcept { return v_.back(); }
253 constexpr const T* data () const noexcept { return v_.data(); }
254 constexpr T* data () noexcept { return v_.data(); }
255 constexpr void swap (std::vector<T> &other) noexcept { v_.swap (other); sort(); }
256 constexpr void swap (SortedVector &other) noexcept { v_.swap (other); }
257 constexpr const_reference at (size_type n) const { return v_.at (n); }
258 constexpr const_reference operator[] (size_type n) const noexcept { return v_[n]; }
259 constexpr SortedVector& operator= (const SortedVector &other) { v_ = other.v_; return *this; }
260 constexpr SortedVector&
261 operator= (const std::vector<T> &other)
262 {
263 v_ = other;
264 sort();
265 return *this;
266 }
267 constexpr SortedVector&
268 operator= (std::initializer_list<value_type> l)
269 {
270 v_.assign (l);
271 sort();
272 return *this;
273 }
274 constexpr SortedVector&
275 operator= (SortedVector &&other)
276 {
277 v_.clear();
278 v_.swap (other);
279 return *this;
280 }
281 constexpr SortedVector&
282 operator= (std::vector<T> &&other)
283 {
284 v_.clear();
285 v_.swap (other);
286 sort();
287 return *this;
288 }
289 constexpr void
290 resize (size_type n, const value_type &el)
291 {
292 const size_type o = v_.size();
293 v_.resize (n, el);
294 if (v_.size() > o)
295 sort();
296 }
297 constexpr void
298 assign (std::initializer_list<value_type> l)
299 {
300 v_.assign (l);
301 sort();
302 }
303 constexpr void
304 sort ()
305 {
306 const Less &lesser = *this;
307 fixed_sort (v_.begin(), v_.end(), lesser);
308 }
309 constexpr iterator
310 find (const value_type &val)
311 {
312 const Less &lesser = *this;
313 iterator it = std::lower_bound (v_.begin(), v_.end(), val, lesser);
314 if (it == v_.end() || lesser (val, *it))
315 return v_.end(); // not found
316 return it; // found
317 }
318 constexpr iterator
319 insert (const value_type &val, bool replace = false)
320 {
321 const Less &lesser = *this;
322 iterator it = std::lower_bound (v_.begin(), v_.end(), val, lesser);
323 if (it != end() && !lesser (val, *it)) // val == *it
324 {
325 if (!replace)
326 return v_.end(); // insertion failed, duplicate
327 *it = val;
328 return it; // duplicate replaced
329 }
330 return v_.insert (it, val); // insert or append
331 }
332 constexpr bool
333 sorted (const Less &lesser, const bool allow_multiple = false) const
334 {
335 const size_type l = size();
336 for (size_type i = 1; i < l; i++)
337 if (lesser (v_[i-1], v_[i]) == false)
338 {
339 if (allow_multiple && lesser (v_[i], v_[i-1]) == false)
340 continue; // v_[i-1] == v_[i]
341 return false;
342 }
343 return true;
344 }
345 constexpr size_type
346 collapse (bool delete_first = true)
347 {
348 const Less &lesser = *this;
349 const size_type l = size();
350 for (size_type i = 1; i < size(); i++)
351 if (lesser (v_[i-1], v_[i]) == false)
352 {
353 erase (begin() + i - delete_first);
354 i--;
355 }
356 return l - size();
357 }
358 template<class Pred> constexpr size_type
359 erase_if (Pred pred)
360 {
361 const size_type l = size();
362 for (iterator it = v_.begin(); it != v_.end(); )
363 if (pred (*it))
364 it = v_.erase (it);
365 else
366 ++it;
367 return l - size();
368 }
369 template<class InputIterator> constexpr
370 SortedVector (InputIterator first, InputIterator last) :
371 v_ (first, last)
372 {
373 sort();
374 }
375 constexpr
376 SortedVector (std::initializer_list<value_type> l = {})
377 {
378 *this = l;
379 }
380 operator const std::vector<T> () const { return v_; }
381 template<class Pred> friend constexpr size_type erase_if (SortedVector &self, Pred pred) { return self.erase_if (pred); }
382};
383
384} // Ase
385
386#endif // __ASE_SORTNET_HH__
Ase::SortedVector
Vector that keeps its elements sorted.
Definition sortnet.hh:223
std::lower_bound
T lower_bound(T... args)
Ase
The Anklang C++ API namespace.
Definition api.hh:9
Ase::fixed_sort
void fixed_sort(RandomIt first, RandomIt last, Compare comp=std::less< typename std::iterator_traits< RandomIt >::value_type >())
Use sorting networks to sort containers <= 16 elements without allocations.
Definition sortnet.hh:193
std::sort
T sort(T... args)
std::swap
T swap(T... args)
« « « Anklang Documentation