Branch data Line data Source code
1 : : #pragma once
2 : :
3 : : #include <algorithm>
4 : : #include <climits>
5 : : #include <cstdint>
6 : : #include <iostream>
7 : : #include <limits>
8 : : #include <memory>
9 : : #include <mutable/util/exception.hpp>
10 : : #include <mutable/util/fn.hpp>
11 : : #include <mutable/util/macro.hpp>
12 : : #include <mutable/util/malloc_allocator.hpp>
13 : : #include <sstream>
14 : : #include <string>
15 : : #include <type_traits>
16 : : #include <utility>
17 : : #ifdef __BMI2__
18 : : #include <x86intrin.h>
19 : : #endif
20 : :
21 : :
22 : : namespace m {
23 : :
24 : : /** Implements a small and efficient set over integers in the range of `0` to `63` (including). */
25 : : struct SmallBitset
26 : : {
27 : : static constexpr std::size_t CAPACITY = 64; ///< the maximum capacity of a `SmallBitset`
28 : :
29 : : /** A proxy to access single elements in `SmallBitset`. */
30 : : template<bool C>
31 : : struct Proxy
32 : : {
33 : : static constexpr bool Is_Const = C;
34 : :
35 : : private:
36 : : using reference_type = std::conditional_t<Is_Const, const SmallBitset&, SmallBitset&>;
37 : :
38 : : reference_type S_;
39 : : std::size_t offset_;
40 : :
41 : : public:
42 : 79025 : Proxy(reference_type S, std::size_t offset) : S_(S), offset_(offset) { M_insist(offset_ < CAPACITY); }
43 : :
44 : 36373 : operator bool() const { return (S_.bits_ >> offset_) & 0b1; }
45 : :
46 : : template <bool C_ = Is_Const>
47 : : requires (not C_)
48 : 42654 : Proxy& operator=(bool val) { setbit(&S_.bits_, val, offset_); return *this; }
49 : :
50 : 2 : Proxy & operator=(const Proxy &other) {
51 : : static_assert(not Is_Const, "can only assign to proxy of non-const SmallBitset");
52 : 2 : return operator=(bool(other));
53 : : }
54 : : };
55 : :
56 : : private:
57 : : uint64_t bits_; ///< the bit vector representing the set
58 : :
59 : : struct iterator
60 : : {
61 : : private:
62 : : uint64_t bits_;
63 : :
64 : : public:
65 : 29418 : iterator(uint64_t bits) : bits_(bits) { }
66 : :
67 : 25617 : bool operator==(iterator other) const { return this->bits_ == other.bits_; }
68 : 25615 : bool operator!=(iterator other) const { return not operator==(other); }
69 : :
70 : 14118 : iterator & operator++() {
71 : : #ifdef __BMI__
72 : 14118 : bits_ = _blsr_u64(bits_); // BMI1: reset lowest set bit
73 : : #else
74 : : bits_ = bits_ & (bits_ - 1UL); // reset lowest set bit
75 : : #endif
76 : 14118 : return *this;
77 : : }
78 : 7 : iterator operator++(int) { auto clone = *this; operator++(); return clone; }
79 : :
80 : 13814 : std::size_t operator*() const { M_insist(bits_ != 0); return std::countr_zero(bits_); }
81 : 3524 : SmallBitset as_set() const {
82 : : #ifdef __BMI__
83 : 3524 : return SmallBitset(_blsi_u64(bits_)); // BMI1: extract lowest set isolated bit
84 : : #else
85 : : return SmallBitset(bits_ & -bits_); // extract lowest set isolated bit
86 : : #endif
87 : : }
88 : : };
89 : :
90 : : struct reverse_iterator
91 : : {
92 : : private:
93 : : uint64_t bits_;
94 : :
95 : : public:
96 : 14 : reverse_iterator(uint64_t bits) : bits_(bits) { }
97 : :
98 : 10 : bool operator==(reverse_iterator other) const { return this->bits_ == other.bits_; }
99 : 8 : bool operator!=(reverse_iterator other) const { return not operator==(other); }
100 : :
101 : 10 : reverse_iterator & operator++() { bits_ = bits_ & ~(1UL << operator*()); return *this; }
102 : 7 : reverse_iterator operator++(int) { auto clone = *this; operator++(); return clone; }
103 : :
104 : 32 : std::size_t operator*() const {
105 : 32 : M_insist(bits_ != 0);
106 : 32 : const unsigned lz = std::countl_zero(bits_);
107 : 32 : return CHAR_BIT * sizeof(bits_) - 1UL - lz;
108 : : }
109 : 6 : SmallBitset as_set() const { return SmallBitset::Singleton(operator*()); }
110 : : };
111 : :
112 : : public:
113 : 57391 : SmallBitset() : bits_(0) { };
114 : 89578 : explicit SmallBitset(uint64_t bits) : bits_(bits) { };
115 : :
116 : : /** Factory method for creating a SmallBitset with first n bits set */
117 : 1085 : static SmallBitset All(std::size_t n) {
118 : 1085 : M_insist(n <= CAPACITY);
119 [ + + ]: 1085 : if (n == CAPACITY) [[unlikely]]
120 : 1 : return ~SmallBitset(0);
121 : 1084 : return SmallBitset((uint64_t(1) << n) - uint64_t(1));
122 : 1085 : }
123 : :
124 : : /** Factory method for creating a Singleton Smallbitset with \p n -th bit set */
125 : 1081 : static SmallBitset Singleton(std::size_t n) {
126 : 1081 : M_insist(n < CAPACITY);
127 : 1081 : return SmallBitset(uint64_t(1) << n);
128 : : }
129 : :
130 : : /** Returns the `offset`-th bit. Requires that `offset` is in range `[0; CAPACITY)`. */
131 : 35209 : Proxy<true> operator()(std::size_t offset) const { return Proxy<true>(*this, offset); }
132 : :
133 : : /** Returns the `offset`-th bit. Requires that `offset` is in range `[0; CAPACITY)`. */
134 : 43816 : Proxy<false> operator()(std::size_t offset) { return Proxy<false>(*this, offset); }
135 : :
136 : : /** Returns the `offset`-th bit. Requires that `offset` is in range `[0; CAPACITY)`. */
137 : 73 : Proxy<true> operator[](std::size_t offset) const { return operator()(offset); }
138 : :
139 : : /** Returns the `offset`-th bit. Requires that `offset` is in range `[0; CAPACITY)`. */
140 : 3950 : Proxy<false> operator[](std::size_t offset) { return operator()(offset); }
141 : :
142 : : /** Returns a proxy to the bit at offset `offset`. Throws `m::out_of_range` if `offset` is not in range
143 : : * `[0; CAPACITY)`. */
144 : 7 : Proxy<true> at(std::size_t offset) const {
145 [ + + ]: 7 : if (offset >= CAPACITY)
146 [ + - + - : 1 : throw m::out_of_range("offset is out of bounds");
- + + - ]
147 : 6 : return operator()(offset);
148 : 1 : }
149 : :
150 : : /** Returns a proxy to the bit at offset `offset`. Throws `m::out_of_range` if `offset` is not in range
151 : : * `[0; CAPACITY)`. */
152 : 7 : Proxy<false> at(std::size_t offset) {
153 [ + + ]: 7 : if (offset >= CAPACITY)
154 [ + - + - : 1 : throw m::out_of_range("offset is out of bounds");
- + + - ]
155 : 6 : return operator()(offset);
156 : 1 : }
157 : :
158 : : /** Returns the maximum capacity. */
159 : 20 : constexpr std::size_t capacity() { return CAPACITY; }
160 : : /** Returns the number of elements in this `SmallBitset`. */
161 : 5230 : std::size_t size() const { return std::popcount(bits_); }
162 : : /** Returns `true` if there are no elements in this `SmallBitset`. */
163 : 14848 : bool empty() const { return bits_ == 0; }
164 : : /* Returns `true` if this set is a singleton set, i.e. the set contains exactly one element. */
165 : 1871 : bool is_singleton() const { return size() == 1; }
166 : :
167 : : /** Returns the highest set bit as a `SmallBitset`. */
168 : 58 : SmallBitset hi() const {
169 : 58 : unsigned lz = std::countl_zero(bits_);
170 : 58 : return SmallBitset::Singleton(CHAR_BIT * sizeof(bits_) - lz - 1U);
171 : : }
172 : :
173 : 15171 : auto begin() const { return iterator(bits_); }
174 : 1 : auto cbegin() const { return begin(); }
175 : 14247 : auto end() const { return iterator(0); }
176 : 7 : auto cend() const { return end(); }
177 : :
178 : 6 : auto rbegin() const { return reverse_iterator(bits_); }
179 : 1 : auto crbegin() const { return rbegin(); }
180 : 8 : auto rend() const { return reverse_iterator(0); }
181 : 7 : auto crend() const { return rend(); }
182 : :
183 : : /** Convert the `SmallBitset` type to `uint64_t`. */
184 : 33931 : explicit operator uint64_t() const { return bits_; }
185 : 2417 : explicit operator bool() const { return not empty(); }
186 : :
187 : 6001 : bool operator==(SmallBitset other) const { return this->bits_ == other.bits_; }
188 : 857 : bool operator!=(SmallBitset other) const { return not operator==(other); }
189 : :
190 : : /** Inverts all bits in the bitset. */
191 : 131 : SmallBitset operator~() const { return SmallBitset(~bits_); }
192 : :
193 : : /** Returns `true` if the set represented by `this` is a subset of `other`, i.e.\ `this` ⊆ `other`. */
194 : 1740 : bool is_subset(SmallBitset other) const { return this->bits_ == (other.bits_ & this->bits_); }
195 : :
196 : : /** Returns a mask up to and including the lowest set bit. */
197 : 187 : SmallBitset mask_to_lo() const {
198 : 187 : M_insist(not empty());
199 : : #ifdef __BMI__
200 : 187 : return SmallBitset(_blsmsk_u64(bits_)); // BMI1: get mask up to lowest set bit
201 : : #else
202 : : return SmallBitset(bits_ ^ (bits_ - 1UL)); // get mask up to lowest set bit
203 : : #endif
204 : : }
205 : :
206 : : /** Converts a singleton set to a mask up to -- but not including -- the single, set bit. */
207 : 4 : SmallBitset singleton_to_lo_mask() const {
208 : 4 : M_insist(is_singleton(), "not a singleton set");
209 : 4 : return SmallBitset(bits_ - 1UL);
210 : : }
211 : :
212 : : /** Returns the union of `left` and `right`, i.e.\ `left` ∪ `right`. */
213 : 12021 : friend SmallBitset unify(SmallBitset left, SmallBitset right) { return SmallBitset(left.bits_ | right.bits_); }
214 : : /** Returns the intersection of `left` and `right`, i.e.\ `left` ∩ `right`. */
215 : 8907 : friend SmallBitset intersect(SmallBitset left, SmallBitset right) { return SmallBitset(left.bits_ & right.bits_); }
216 : : /** Returns the set where the elements of `right` have been subtracted from `left`, i.e.\ `left` - `right`. */
217 : 10353 : friend SmallBitset subtract(SmallBitset left, SmallBitset right) { return SmallBitset(left.bits_ & ~right.bits_); }
218 : : /** Returns the union of `left` and `right`, i.e.\ `left` ∪ `right`. */
219 : 12021 : friend SmallBitset operator|(SmallBitset left, SmallBitset right) { return unify(left, right); }
220 : : /** Returns the intersection of `left` and `right`, i.e.\ `left` ∩ `right`. */
221 : 8907 : friend SmallBitset operator&(SmallBitset left, SmallBitset right) { return intersect(left, right); }
222 : : /** Returns the set where the elements of `right` have been subtracted from `left`, i.e.\ `left` - `right`. */
223 : 10353 : friend SmallBitset operator-(SmallBitset left, SmallBitset right) { return subtract(left, right); }
224 : :
225 : 5422 : SmallBitset & operator|=(SmallBitset other) { return *this = *this | other; }
226 : 1 : SmallBitset & operator&=(SmallBitset other) { return *this = *this & other; }
227 : 432 : SmallBitset & operator-=(SmallBitset other) { return *this = *this - other; }
228 : :
229 : : /** Treat this `SmallBitset` as an element of the power set of *2^n* bits, where *n* is the number of bits that fit
230 : : * into `SmallBitset`. Then this method advances to the next set in the power set. The behavior is undefined if
231 : : * all bits are already set. */
232 : 2 : SmallBitset & operator++() { M_insist(~bits_ != 0UL, "must not have all bits set"); bits_ += 1UL; return *this; }
233 : : /** Treat this `SmallBitset` as an element of the power set of *2^n* bits, where *n* is the number of bits that fit
234 : : * into `SmallBitset`. Then this method advances to the next set in the power set. The behavior is undefined if
235 : : * all bits are already set. */
236 : 1 : SmallBitset operator++(int) { SmallBitset clone(*this); operator++(); return clone; }
237 : :
238 : : /** Treat this `SmallBitset` as an element of the power set of *2^n* bits, where *n* is the number of bits that fit
239 : : * into `SmallBitset`. Then this method advances to the previous set in the power set. The behavior is undefined
240 : : * if no bits are set. */
241 : 2 : SmallBitset & operator--() { M_insist(bits_, "at least one bit must be set"); bits_ -= 1UL; return *this; }
242 : : /** Treat this `SmallBitset` as an element of the power set of *2^n* bits, where *n* is the number of bits that fit
243 : : * into `SmallBitset`. Then this method advances to the previous set in the power set. The behavior is undefined
244 : : * if no bits are set. */
245 : 1 : SmallBitset operator--(int) { SmallBitset clone(*this); operator--(); return clone; }
246 : :
247 : : M_LCOV_EXCL_START
248 : : /** Write a textual representation of `s` to `out`. */
249 : : friend std::ostream & operator<<(std::ostream &out, SmallBitset s) {
250 : : for (uint64_t i = CAPACITY; i --> 0;)
251 : : out << s(i);
252 : : return out;
253 : : }
254 : :
255 : : /** Print a textual representation of `this` with `size` bits to `out`. */
256 : : void print_fixed_length(std::ostream &out, std::size_t size) const {
257 : : for (uint64_t i = size; i --> 0;)
258 : : out << (*this)(i);
259 : : }
260 : :
261 : : void dump(std::ostream &out) const;
262 : : void dump() const;
263 : : M_LCOV_EXCL_STOP
264 : : };
265 : :
266 : : /** Returns the least subset of a given `set`, i.e.\ the set represented by the lowest 1 bit. */
267 : 349 : inline SmallBitset least_subset(SmallBitset S) { return SmallBitset(uint64_t(S) & -uint64_t(S)); }
268 : :
269 : : /** Returns the next subset of a given `subset` and `set. */
270 : 251 : inline SmallBitset next_subset(SmallBitset subset, SmallBitset set)
271 : : {
272 : 251 : return SmallBitset(uint64_t(subset) - uint64_t(set)) & set;
273 : : }
274 : :
275 : : /** Implements an array of dynamic but fixed size. */
276 : : template<typename T>
277 : : struct dyn_array
278 : : {
279 : : using value_type = T;
280 : : using size_type = std::size_t;
281 : : using iterator = value_type*;
282 : : using const_iterator = const value_type*;
283 : :
284 : : private:
285 : : std::unique_ptr<value_type[]> arr_;
286 : : std::size_t size_;
287 : :
288 : : public:
289 : : /** Constructs an array of size 0. */
290 : : dyn_array() : size_(0) { }
291 : :
292 : : /** Constructs an array of size `size`. */
293 : : explicit dyn_array(std::size_t size)
294 : : : arr_(std::make_unique<value_type[]>(size))
295 : : , size_(size)
296 : : { }
297 : :
298 : : /** Constructs an array with the elements in range `[begin, end)`. The size of the array will be
299 : : * `std::distance(begin, end)`. */
300 : : template<typename InputIt>
301 : : dyn_array(InputIt begin, InputIt end)
302 : : : dyn_array(std::distance(begin, end))
303 : : {
304 : : auto ptr = data();
305 : : for (auto it = begin; it != end; ++it)
306 : : new (ptr++) value_type(*it);
307 : : }
308 : :
309 : : /** Copy-constructs an array. */
310 : : explicit dyn_array(const dyn_array &other)
311 : : : dyn_array(other.size())
312 : : {
313 : : for (std::size_t i = 0; i != other.size(); ++i)
314 : : new (&data()[i]) value_type(other[i]);
315 : : }
316 : :
317 : : dyn_array(dyn_array&&) = default;
318 : : dyn_array & operator=(dyn_array&&) = default;
319 : :
320 : : /** Returns the size of this array, i.e. the number of elements. */
321 : : size_type size() const { return size_; }
322 : :
323 : : /** Returns a pointer to the beginning of the array. */
324 : : const value_type * data() const { return arr_.get(); }
325 : : /** Returns a pointer to the beginning of the array. */
326 : : value_type * data() { return arr_.get(); }
327 : :
328 : : /** Returns a reference to the element at position `pos`. Requires that `pos` is in bounds. */
329 : : const value_type & operator[](std::size_t pos) const {
330 : : M_insist(pos < size(), "index out of bounds");
331 : : return data()[pos];
332 : : }
333 : :
334 : : /** Returns a reference to the element at position `pos`. Requires that `pos` is in bounds. */
335 : : value_type & operator[](std::size_t pos) {
336 : : M_insist(pos < size(), "index out of bounds");
337 : : return data()[pos];
338 : : }
339 : :
340 : : /** Returns a reference to the element at position `pos`. Throws `m::out_of_range` if `pos` is out of bounds. */
341 : : const value_type & at(std::size_t pos) const {
342 : : if (pos >= size())
343 : : throw m::out_of_range("index out of bounds");
344 : : return (*this)[pos];
345 : : }
346 : :
347 : : /** Returns a reference to the element at position `pos`. Throws `m::out_of_range` if `pos` is out of bounds. */
348 : : value_type & at(std::size_t pos) {
349 : : if (pos >= size())
350 : : throw m::out_of_range("index out of bounds");
351 : : return (*this)[pos];
352 : : }
353 : :
354 : : iterator begin() { return data(); }
355 : : iterator end() { return data() + size(); }
356 : : const_iterator begin() const { return data(); }
357 : : const_iterator end() const { return data() + size(); }
358 : : const_iterator cbegin() const { return begin(); }
359 : : const_iterator cend() const { return end(); }
360 : :
361 : : /** Returns `true` iff the contents of `this` and `other` are equal, that is, they have the same number of elements
362 : : * and each element in `this` compares equal with the element in `other` at the same position. */
363 : : bool operator==(const dyn_array &other) const {
364 : : if (this->size() != other.size())
365 : : return false;
366 : :
367 : : for (std::size_t i = 0; i != size(); ++i) {
368 : : if ((*this)[i] != other[i])
369 : : return false;
370 : : }
371 : :
372 : : return true;
373 : : }
374 : : /** Returns `false` iff the contents of `this` and `other` are equal, that is, they have the same number of elements
375 : : * and each element in `this` compares equal with the element in `other` at the same position. */
376 : : bool operator!=(const dyn_array &other) const { return not operator==(other); }
377 : : };
378 : :
379 : : /** Implements a doubly-linked list with an overhead of just a single pointer per element. */
380 : : template<
381 : : typename T,
382 : : is_allocator Allocator = malloc_allocator
383 : : >
384 : : struct doubly_linked_list
385 : : {
386 : : using value_type = T;
387 : : using size_type = std::size_t;
388 : : using allocator_type = Allocator;
389 : :
390 : : using reference_type = T&;
391 : : using const_reference_type = const T&;
392 : :
393 : : struct node_type
394 : : {
395 : : std::uintptr_t ptrxor_;
396 : : T value_;
397 : : };
398 : :
399 : : private:
400 : : ///> the memory allocator
401 : : mutable allocator_type allocator_;
402 : :
403 : : ///> points to the first node
404 : 54 : node_type *head_ = nullptr;
405 : : ///> points to the last node
406 : 54 : node_type *tail_ = nullptr;
407 : : ///> the number of elements/nodes in the list
408 : 54 : size_type size_ = 0;
409 : :
410 : : template<bool C>
411 : : struct the_iterator
412 : : {
413 : : friend struct doubly_linked_list;
414 : :
415 : : static constexpr bool Is_Const = C;
416 : :
417 : : using iterator_category = std::bidirectional_iterator_tag;
418 : : using value_type = T;
419 : : using difference_type = std::ptrdiff_t;
420 : : using pointer = std::conditional_t<Is_Const, const T*, T*>;
421 : : using reference = std::conditional_t<Is_Const, const T&, T&>;
422 : :
423 : : private:
424 : : node_type *node_;
425 : : std::uintptr_t prev_;
426 : :
427 : : public:
428 : 1710 : the_iterator(node_type *node, std::uintptr_t prev) : node_(node), prev_(prev) { }
429 : :
430 : 298 : the_iterator & operator++() {
431 : 298 : M_insist(node_, "cannot advance a past-the-end iterator");
432 : 298 : node_type *curr = node_;
433 : 298 : node_ = reinterpret_cast<node_type*>(prev_ ^ node_->ptrxor_);
434 : 298 : prev_ = reinterpret_cast<std::uintptr_t>(curr);
435 : 298 : return *this;
436 : : }
437 : :
438 : 83 : the_iterator operator++(int) { the_iterator clone = *this; operator++(); return clone; }
439 : :
440 : 50 : the_iterator & operator--() {
441 : 50 : node_type *prev = reinterpret_cast<node_type*>(prev_);
442 : 50 : M_insist(prev, "cannot retreat past the beginning");
443 : 50 : prev_ = prev->ptrxor_ ^ reinterpret_cast<std::uintptr_t>(node_);
444 : 50 : node_ = prev;
445 : 50 : return *this;
446 : : }
447 : :
448 : 1 : the_iterator operator--(int) { the_iterator clone = *this; operator--(); return clone; }
449 : :
450 : 940 : reference operator*() const { return node_->value_; }
451 : 1 : pointer operator->() const { return &node_->value_; }
452 : :
453 : 740 : bool operator==(const the_iterator &other) const {
454 [ + + + + ]: 740 : return this->node_ == other.node_ and this->prev_ == other.prev_;
455 : : }
456 : 519 : bool operator!=(const the_iterator &other) const { return not operator==(other); }
457 : :
458 : 186 : operator the_iterator<true>() const { return the_iterator<true>(node_, prev_); }
459 : : };
460 : :
461 : : public:
462 : : using iterator = the_iterator<false>;
463 : : using const_iterator = the_iterator<true>;
464 : :
465 : 6 : friend void swap(doubly_linked_list &first, doubly_linked_list &second) {
466 : : using std::swap;
467 : 6 : swap(first.head_, second.head_);
468 : 6 : swap(first.tail_, second.tail_);
469 : 6 : swap(first.size_, second.size_);
470 : 6 : swap(first.allocator_, second.allocator_);
471 : 6 : }
472 : :
473 : : /*----- Constructors & Destructor --------------------------------------------------------------------------------*/
474 : 33 : doubly_linked_list() : doubly_linked_list(allocator_type()) { }
475 : :
476 : : template<is_allocator A = allocator_type>
477 : 49 : explicit doubly_linked_list(A &&allocator)
478 : 49 : : allocator_(std::forward<A>(allocator))
479 : 49 : { }
480 : :
481 : : template<typename InputIt>
482 : 5 : doubly_linked_list(InputIt begin, InputIt end, allocator_type &&allocator = allocator_type())
483 : 5 : : allocator_(std::forward<allocator_type>(allocator))
484 : : {
485 [ + + ]: 20 : for (auto it = begin; it != end; ++it)
486 : 15 : push_back(*it);
487 : 5 : }
488 : :
489 [ + - ]: 54 : ~doubly_linked_list() { clear(); }
490 : :
491 : 3 : explicit doubly_linked_list(const doubly_linked_list &other) : doubly_linked_list() {
492 [ + - + - : 3 : insert(begin(), other.cbegin(), other.cend());
+ - + - +
- ]
493 : 3 : }
494 : :
495 [ + - ]: 3 : doubly_linked_list(doubly_linked_list &&other) : doubly_linked_list() { swap(*this, other); }
496 : :
497 : 2 : doubly_linked_list & operator=(doubly_linked_list other) { swap(*this, other); return *this; }
498 : :
499 : 4 : allocator_type & get_allocator() const noexcept { return allocator_; }
500 : :
501 : : /*----- Element access -------------------------------------------------------------------------------------------*/
502 : 5 : reference_type front() { M_insist(head_); return head_->value_; }
503 : 1 : const_reference_type front() const { M_insist(head_); return head_->value_; }
504 : 5 : reference_type back() { M_insist(tail_); return tail_->value_; }
505 : 1 : const_reference_type back() const { M_insist(tail_); return tail_->value_; }
506 : :
507 : : /*----- Iterators ------------------------------------------------------------------------------------------------*/
508 : 293 : iterator begin() { return iterator(head_, 0); }
509 : 478 : iterator end() { return iterator(nullptr, reinterpret_cast<std::uintptr_t>(tail_)); }
510 : 60 : const_iterator begin() const { return const_iterator(head_, 0); }
511 : 134 : const_iterator end() const { return const_iterator(nullptr, reinterpret_cast<std::uintptr_t>(tail_)); }
512 : 60 : const_iterator cbegin() const { return begin(); }
513 : 134 : const_iterator cend() const { return end(); }
514 : :
515 : 1 : iterator rbegin() { return iterator(tail_, 0); }
516 : 1 : iterator rend() { return iterator(nullptr, reinterpret_cast<std::uintptr_t>(head_)); }
517 : 57 : const_iterator rbegin() const { return const_iterator(tail_, 0); }
518 : 131 : const_iterator rend() const { return const_iterator(nullptr, reinterpret_cast<std::uintptr_t>(head_)); }
519 : 57 : const_iterator crbegin() const { return rbegin(); }
520 : 131 : const_iterator crend() const { return rend(); }
521 : :
522 : : /*----- Capacity -------------------------------------------------------------------------------------------------*/
523 : 77 : bool empty() const { return size_ == 0; }
524 : 145 : size_type size() const { return size_; }
525 : : size_type max_size() const { return std::numeric_limits<size_type>::max(); }
526 : :
527 : : /*----- Modifiers ------------------------------------------------------------------------------------------------*/
528 : : template<typename... Args>
529 : 184 : iterator emplace(const_iterator pos, Args&&... args) {
530 : 184 : node_type *node = allocate_node();
531 : 184 : new (&node->value_) value_type(std::forward<Args>(args)...);
532 : 184 : node->ptrxor_ = pos.prev_ ^ reinterpret_cast<std::uintptr_t>(pos.node_);
533 : :
534 : 184 : node_type *prev = reinterpret_cast<node_type*>(pos.prev_);
535 [ + + + + ]: 184 : if (prev)
536 : 96 : prev->ptrxor_ ^= reinterpret_cast<std::uintptr_t>(pos.node_) ^ reinterpret_cast<std::uintptr_t>(node);
537 : : else // insert at front
538 : 88 : head_ = node;
539 [ + + + + ]: 184 : if (pos.node_)
540 : 51 : pos.node_->ptrxor_ ^= pos.prev_ ^ reinterpret_cast<std::uintptr_t>(node);
541 : : else // insert at end
542 : 133 : tail_ = node;
543 : :
544 : 184 : ++size_;
545 : 184 : return iterator(node, pos.prev_);
546 : : }
547 : :
548 : : template<typename... Args>
549 : 59 : reference_type emplace_back(Args&&... args) {
550 : 59 : auto it = emplace(end(), std::forward<Args>(args)...);
551 : 59 : return *it;
552 : : }
553 : :
554 : : template<typename... Args>
555 : 6 : reference_type emplace_front(Args&&... args) {
556 : 6 : auto it = emplace(begin(), std::forward<Args>(args)...);
557 : 6 : return *it;
558 : : }
559 : :
560 : 15 : void push_back(const value_type &value) { emplace_back(value); }
561 : 41 : void push_back(value_type &&value) { emplace_back(std::move(value)); }
562 : : void push_front(const value_type &value) { emplace_front(value); }
563 : 3 : void push_front(value_type &&value) { emplace_front(std::move(value)); }
564 : :
565 : 115 : iterator insert(const_iterator pos, const value_type &value) { return emplace(pos, value); }
566 : : iterator insert(const_iterator pos, value_type &&value) { return emplace(pos, std::move(value)); }
567 : 1 : iterator insert(const_iterator pos, size_type count, const value_type &value) {
568 : 1 : iterator it(pos.node_, pos.prev_);
569 [ + + ]: 4 : while (count--) it = insert(it, value);
570 : 1 : return it;
571 : : }
572 : :
573 : : template<typename InputIt,
574 : : typename = decltype(*std::declval<InputIt&>(), std::declval<InputIt&>()++, void())>
575 : 5 : iterator insert(const_iterator pos, InputIt first, InputIt last) {
576 [ - + - + : 5 : if (first == last) return iterator(pos.node_, pos.prev_);
- + ]
577 : :
578 : 5 : iterator begin = insert(pos, *first++);
579 : 5 : M_insist(begin != end());
580 : 5 : M_insist(begin.node_);
581 : 5 : iterator it = begin;
582 [ + + + + : 15 : while (first != last) it = insert(++it, *first++);
+ + ]
583 : :
584 : 5 : return begin;
585 : 5 : }
586 : :
587 : 1 : iterator insert(const_iterator pos, std::initializer_list<value_type> ilist) {
588 : 1 : return insert(pos, ilist.begin(), ilist.end());
589 : : }
590 : :
591 : 184 : iterator erase(iterator pos) {
592 : 184 : M_insist(pos.node_);
593 : 184 : M_insist(size_);
594 : 184 : node_type *prev = reinterpret_cast<node_type*>(pos.prev_);
595 : 184 : node_type *next = reinterpret_cast<node_type*>(pos.node_->ptrxor_ ^ pos.prev_);
596 [ + + ]: 184 : if (prev)
597 : 42 : prev->ptrxor_ ^= reinterpret_cast<std::uintptr_t>(pos.node_) ^ reinterpret_cast<std::uintptr_t>(next);
598 : : else // erased first node
599 : 142 : head_ = next;
600 [ + + ]: 184 : if (next)
601 : 101 : next->ptrxor_ ^= reinterpret_cast<std::uintptr_t>(pos.node_) ^ reinterpret_cast<std::uintptr_t>(prev);
602 : : else // erased last node
603 : 83 : tail_ = prev;
604 : 184 : deallocate_node(pos.node_);
605 : 184 : --size_;
606 : 184 : return iterator(next, pos.prev_);
607 : : }
608 : :
609 : : iterator erase(const_iterator pos) { return erase(iterator(pos.node_, pos.prev_)); }
610 : :
611 : 2 : value_type pop_back() {
612 : 2 : reverse();
613 : 2 : value_type value = pop_front();
614 : 2 : reverse();
615 : 2 : return value;
616 : : }
617 : :
618 : 83 : value_type pop_front() {
619 : 83 : M_insist(head_);
620 : 83 : M_insist(tail_);
621 : 83 : M_insist(size_);
622 : 83 : value_type value = std::move(head_->value_);
623 : 83 : erase(begin());
624 : 83 : return value;
625 : : }
626 : :
627 [ + + ]: 136 : void clear() { while (head_) pop_front(); M_insist(size_ == 0); }
628 : :
629 : : /*----- Operations -----------------------------------------------------------------------------------------------*/
630 : 5 : void reverse() { std::swap(head_, tail_); }
631 : :
632 : : /*----- Text -----------------------------------------------------------------------------------------------------*/
633 : : M_LCOV_EXCL_START
634 : : friend std::ostream & operator<<(std::ostream &out, const doubly_linked_list &L) {
635 : : if (L.empty())
636 : : return out << "+-+";
637 : :
638 : : out << "+-> ";
639 : : for (auto it = L.cbegin(); it != L.cend(); ++it) {
640 : : if (it != L.cbegin()) out << " <-> ";
641 : : if constexpr (is_streamable<std::ostream&, decltype(*it)>::value)
642 : : out << *it;
643 : : else
644 : : out << 'o';
645 : : }
646 : : return out << " <-+";
647 : : }
648 : :
649 : : friend std::string to_string(const doubly_linked_list &L) {
650 : : std::ostringstream oss;
651 : : oss << L;
652 : : return oss.str();
653 : : }
654 : :
655 : : void dump(std::ostream &out) const { out << *this << std::endl; }
656 : : void dump() const { dump(std::cerr); }
657 : : M_LCOV_EXCL_STOP
658 : :
659 : : private:
660 : 184 : node_type * allocate_node() { return allocator_.template allocate<node_type>(); }
661 : 184 : void deallocate_node(node_type *ptr) { allocator_.template deallocate<node_type>(ptr); }
662 : : };
663 : :
664 : : template<typename It>
665 : : struct range
666 : : {
667 : : using iterator_type = It;
668 : :
669 : : ///> whether the iterator supports reversing
670 : : static constexpr bool reversible = requires { typename std::reverse_iterator<It>; } and
671 : : requires (It it) { std::make_reverse_iterator(it); };
672 : :
673 : : private:
674 : : It begin_, end_;
675 : :
676 : : public:
677 : : range() { }
678 : 377 : range(It begin, It end) : begin_(begin), end_(end) { }
679 : :
680 : : bool empty() const { return begin() == end(); }
681 : : std::size_t size() const { return std::distance(begin(), end()); }
682 : :
683 : 364 : It begin() const { return begin_; }
684 : 398 : It end() const { return end_; }
685 : : It cbegin() const { return begin_; }
686 : : It cend() const { return end_; }
687 : :
688 : 13 : std::reverse_iterator<It> rbegin() const requires reversible { return std::make_reverse_iterator(end_); }
689 : 13 : std::reverse_iterator<It> rend() const requires reversible { return std::make_reverse_iterator(begin_); }
690 : : std::reverse_iterator<It> crbegin() const requires reversible { return std::make_reverse_iterator(end_); }
691 : : std::reverse_iterator<It> crend() const requires reversible { return std::make_reverse_iterator(begin_); }
692 : :
693 : : /** Returns this `range` reversed. */
694 : 13 : range<std::reverse_iterator<It>> reverse() const requires reversible {
695 : 13 : return range<std::reverse_iterator<It>>(rbegin(), rend());
696 : : }
697 : : };
698 : :
699 : : template<typename It, typename Fn, bool OwnsProjection = true>
700 : : struct projecting_iterator;
701 : :
702 : : template<typename It, typename ReturnType, bool OwnsProjection>
703 : : struct projecting_iterator<It, ReturnType&(It), OwnsProjection>
704 : : {
705 : : using difference_type = typename It::difference_type;
706 : : using value_type = ReturnType;
707 : : using pointer = value_type*;
708 : : using reference = value_type&;
709 : : using iterator_category = std::random_access_iterator_tag;
710 : : using projection_type = std::function<ReturnType&(It)>;
711 : :
712 : : private:
713 : : It it_;
714 : : std::conditional_t<OwnsProjection, projection_type, const projection_type&> project_;
715 : :
716 : : public:
717 : : projecting_iterator(It it, projection_type project) requires OwnsProjection : it_(it), project_(std::move(project)) { }
718 : 676 : projecting_iterator(It it, const projection_type &project) requires (not OwnsProjection) : it_(it), project_(project) { }
719 : :
720 : : bool operator==(projecting_iterator other) const requires requires (It it) { { it == it } -> std::same_as<bool>; } {
721 : : return this->it_ == other.it_;
722 : : }
723 : : bool operator!=(projecting_iterator other) const requires requires (It it) { { it != it } -> std::same_as<bool>; } {
724 : : return this->it_ != other.it_;
725 : : }
726 : :
727 : 906 : projecting_iterator & operator++() requires requires (It it) { ++it; } { ++it_; return *this; }
728 : : projecting_iterator operator++(int) requires requires (It it) { it++; } { return it_++; }
729 : :
730 : : projecting_iterator & operator--() requires requires (It it) { --it; } { --it_; return *this; }
731 : : projecting_iterator operator--(int) requires requires (It it) { it--; } { return it_--; }
732 : :
733 : : projecting_iterator & operator+=(int offset) requires requires (It it) { it += offset; } { it_ += offset; return *this; }
734 : : projecting_iterator & operator-=(int offset) requires requires (It it) { it -= offset; } { it_ -= offset; return *this; }
735 : :
736 : 676 : difference_type operator-(projecting_iterator other) const
737 : : requires requires (It it) { { it - it } -> std::convertible_to<difference_type>; } {
738 : 676 : return this->it_ - other.it_;
739 : : }
740 : :
741 : 906 : reference operator*() const requires requires (projection_type p, It it) { p(it); } { return project_(it_); }
742 : : pointer operator->() const requires requires (projection_type p, It it) { p(it); } { return &project_(it_); }
743 : : };
744 : :
745 : : // class template argument deduction guides
746 : : template<typename It, typename Fn>
747 : : projecting_iterator(It, Fn&&) -> projecting_iterator<It, std::invoke_result_t<Fn&&, It>(It)>;
748 : :
749 : : template<typename It, typename Fn>
750 : : struct view;
751 : :
752 : : template<typename It, typename ReturnType>
753 : : struct view<It, ReturnType&(It)>
754 : : {
755 : : using iterator_type = It;
756 : : using projection_type = std::function<ReturnType&(It)>;
757 : : using projecting_iterator_type = projecting_iterator<It, ReturnType&(It), false>; // share projection by reference
758 : :
759 : : private:
760 : : range<It> range_;
761 : : projection_type project_;
762 : :
763 : : public:
764 : : view(range<It> range, projection_type project) : range_(range), project_(std::move(project)) { }
765 : : view(It begin, It end, projection_type project) : range_(begin, end), project_(std::move(project)) { }
766 : : template<typename Fn>
767 : : view(range<It> range, Fn &&fn) : range_(range), project_(std::forward<Fn>(fn)) { }
768 : : template<typename Fn>
769 : 338 : view(It begin, It end, Fn &&fn) : range_(begin, end), project_(std::forward<Fn>(fn)) { }
770 : :
771 : 338 : projecting_iterator_type begin() const { return projecting_iterator_type(range_.begin(), project_); }
772 : 338 : projecting_iterator_type end() const { return projecting_iterator_type(range_.end(), project_); }
773 : : };
774 : :
775 : : // class template argument deduction guides
776 : : template<typename It, typename Fn>
777 : : view(range<It>, Fn&&) -> view<It, std::invoke_result_t<Fn&&, It>(It)>;
778 : : template<typename It, typename Fn>
779 : : view(It, It, Fn&&) -> view<It, std::invoke_result_t<Fn&&, It>(It)>;
780 : :
781 : : /** A sorted list of elements. Allows duplicates. */
782 : : template<typename T, typename Compare = std::less<T>>
783 : : struct sorted_vector
784 : : {
785 : : using vector_type = std::vector<T>; ///< the type of the internal container of elements
786 : : using value_type = T;
787 : : using size_type = typename vector_type::size_type;
788 : :
789 : : private:
790 : : Compare comp_;
791 : : vector_type v_; ///< the internal container of elements
792 : :
793 : : public:
794 : : sorted_vector(Compare comp = Compare()) : comp_(comp) { }
795 : :
796 : : auto begin() { return v_.begin(); }
797 : : auto end() { return v_.end(); }
798 : : auto begin() const { return v_.begin(); }
799 : : auto end() const { return v_.end(); }
800 : : auto cbegin() const { return v_.cbegin(); }
801 : : auto cend() const { return v_.cend(); }
802 : :
803 : : /** Returns `true` iff the `sorted_vector` has no elements. */
804 : : auto empty() const { return v_.empty(); }
805 : : /** Returns the number of elements in this `sorted_vector`. */
806 : : auto size() const { return v_.size(); }
807 : : /** Reserves space for `new_cap` elements in this `sorted_vector`. */
808 : : auto reserve(size_type new_cap) { return v_.reserve(new_cap); }
809 : :
810 : : /** Returns `true` iff this `sorted_vector` contains an element that is equal to `value`. */
811 : : bool contains(const T &value) const {
812 : : auto pos = std::lower_bound(begin(), end(), value, comp_);
813 : : return pos != end() and *pos == value;
814 : : }
815 : :
816 : : /** Inserts `value` into this `sorted_vector`. Returns an `iterator` pointing to the inserted element. */
817 : : auto insert(T value) { return v_.insert(std::lower_bound(begin(), end(), value), value, comp_); }
818 : :
819 : : /** Inserts elements in the range from `first` (including) to `last` (excluding) into this `sorted_vector. */
820 : : template<typename InsertIt>
821 : : void insert(InsertIt first, InsertIt last) {
822 : : while (first != last)
823 : : insert(*first++);
824 : : }
825 : : };
826 : :
827 : : /** Enumerate all subsets of size `k` based on superset of size `n`.
828 : : * See http://programmingforinsomniacs.blogspot.com/2018/03/gospers-hack-explained.html. */
829 : : struct GospersHack
830 : : {
831 : : private:
832 : : SmallBitset set_;
833 : : uint64_t limit_;
834 : :
835 : 58 : GospersHack() { }
836 : :
837 : : public:
838 : : /** Create an instance of `GospersHack` that enumerates all subsets of size `k` of a set of `n` elements. */
839 : 49 : static GospersHack enumerate_all(uint64_t k, uint64_t n) {
840 : 49 : M_insist(k <= n, "invalid enumeration");
841 : 49 : M_insist(n < 64, "n exceeds range");
842 : 49 : GospersHack GH;
843 : 49 : GH.set_ = SmallBitset::All(k);
844 : 49 : GH.limit_ = 1UL << n;
845 : 49 : return GH;
846 : : }
847 : : /** Create an instance of `GospersHack` that enumerates all remaining subsets of a set of `n` elements, starting at
848 : : * subset `set`. */
849 : 9 : static GospersHack enumerate_from(SmallBitset set, uint64_t n) {
850 : 9 : M_insist(n < 64, "n exceeds range");
851 : 9 : GospersHack GH;
852 : 9 : GH.set_ = set;
853 : 9 : GH.limit_ = 1UL << n;
854 : 9 : M_insist(uint64_t(set) <= GH.limit_, "set exceeds the limit");
855 : 9 : return GH;
856 : : }
857 : :
858 : : /** Advance to the next subset. */
859 : 237 : GospersHack & operator++() {
860 : 237 : const uint64_t s(set_);
861 : : #ifdef __BMI__
862 : 237 : const uint64_t c = _blsi_u64(s); // BMI1: extract lowest set isolated bit -> c is a power of 2
863 : : #else
864 : : const uint64_t c = s & -s; // extract lowest set isolated bit -> c is a power of 2
865 : : #endif
866 : 237 : const uint64_t r = s + c; // flip lowest block of 1-bits and following 0-bit
867 : 237 : const uint64_t m = r ^ s; // mask flipped bits, i.e. lowest block of 1-bits and following 0-bit
868 : : #ifdef __BMI2__
869 : 237 : const uint64_t l = _pext_u64(m, m); // BMI2: deposit all set bits in the low bits
870 : : #else
871 : : const uint64_t l = (1UL << __builtin_popcount(m)) - 1UL; // deposit all set bits in the low bits
872 : : #endif
873 : 237 : set_ = SmallBitset((l >> 2U) | r); // instead of divide by c, rshift by log2(c)
874 : 237 : return *this;
875 : : }
876 : :
877 : : /** Returns `false` iff all subsets have been enumerated. */
878 : 283 : operator bool() const { return uint64_t(set_) < limit_; }
879 : :
880 : : /** Returns the current subset. */
881 : 829 : SmallBitset operator*() const { return SmallBitset(set_); }
882 : : };
883 : :
884 : : /** This class efficiently enumerates all subsets of a given size. */
885 : : struct SubsetEnumerator
886 : : {
887 : : private:
888 : : ///> the set to compute the power set of
889 : : SmallBitset set_;
890 : : ///> used to enumerate the power set of numbers 0 to n-1
891 : : GospersHack GH_;
892 : :
893 : : public:
894 : 3 : SubsetEnumerator(SmallBitset set, uint64_t size)
895 : 3 : : set_(set)
896 : 3 : , GH_(GospersHack::enumerate_all(size, set.size()))
897 : : {
898 : 3 : M_insist(size <= set.size());
899 : 3 : }
900 : :
901 : 7 : SubsetEnumerator & operator++() { ++GH_; return *this; }
902 : 10 : operator bool() const { return bool(GH_); }
903 : 7 : SmallBitset operator*() const {
904 : 7 : auto gh_set = *GH_;
905 : 7 : return SmallBitset(_pdep_u64(uint64_t(gh_set), uint64_t(set_)));
906 : : }
907 : : };
908 : :
909 : : }
|
