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