bitdeque.h raw
1 // Copyright (c) 2022 The Limenka developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5 #ifndef LIMENKA_UTIL_BITDEQUE_H
6 #define LIMENKA_UTIL_BITDEQUE_H
7
8 #include <bitset>
9 #include <cstddef>
10 #include <deque>
11 #include <limits>
12 #include <stdexcept>
13 #include <tuple>
14
15 /** Class that mimics std::deque<bool>, but with std::vector<bool>'s bit packing.
16 *
17 * BITS_PER_WORD selects the (minimum) number of bits that are allocated at once.
18 * Larger values reduce the asymptotic memory usage overhead, at the cost of
19 * needing larger up-front allocations. The default is 4096 bytes.
20 */
21 template<int BITS_PER_WORD = 4096 * 8>
22 class bitdeque
23 {
24 // Internal definitions
25 using word_type = std::bitset<BITS_PER_WORD>;
26 using deque_type = std::deque<word_type>;
27 static_assert(BITS_PER_WORD > 0);
28
29 // Forward and friend declarations of iterator types.
30 template<bool Const> class Iterator;
31 template<bool Const> friend class Iterator;
32
33 /** Iterator to a bitdeque element, const or not. */
34 template<bool Const>
35 class Iterator
36 {
37 using deque_iterator = std::conditional_t<Const, typename deque_type::const_iterator, typename deque_type::iterator>;
38
39 deque_iterator m_it;
40 int m_bitpos{0};
41 Iterator(const deque_iterator& it, int bitpos) : m_it(it), m_bitpos(bitpos) {}
42 friend class bitdeque;
43
44 public:
45 using iterator_category = std::random_access_iterator_tag;
46 using value_type = bool;
47 using pointer = void;
48 using const_pointer = void;
49 using reference = std::conditional_t<Const, bool, typename word_type::reference>;
50 using const_reference = bool;
51 using difference_type = std::ptrdiff_t;
52
53 /** Default constructor. */
54 Iterator() = default;
55
56 /** Default copy constructor. */
57 Iterator(const Iterator&) = default;
58
59 /** Conversion from non-const to const iterator. */
60 template<bool ConstArg = Const, typename = std::enable_if_t<Const && ConstArg>>
61 Iterator(const Iterator<false>& x) : m_it(x.m_it), m_bitpos(x.m_bitpos) {}
62
63 Iterator& operator+=(difference_type dist)
64 {
65 if (dist > 0) {
66 if (dist + m_bitpos >= BITS_PER_WORD) {
67 ++m_it;
68 dist -= BITS_PER_WORD - m_bitpos;
69 m_bitpos = 0;
70 }
71 auto jump = dist / BITS_PER_WORD;
72 m_it += jump;
73 m_bitpos += dist - jump * BITS_PER_WORD;
74 } else if (dist < 0) {
75 dist = -dist;
76 if (dist > m_bitpos) {
77 --m_it;
78 dist -= m_bitpos + 1;
79 m_bitpos = BITS_PER_WORD - 1;
80 }
81 auto jump = dist / BITS_PER_WORD;
82 m_it -= jump;
83 m_bitpos -= dist - jump * BITS_PER_WORD;
84 }
85 return *this;
86 }
87
88 friend difference_type operator-(const Iterator& x, const Iterator& y)
89 {
90 return BITS_PER_WORD * (x.m_it - y.m_it) + x.m_bitpos - y.m_bitpos;
91 }
92
93 Iterator& operator=(const Iterator&) = default;
94 Iterator& operator-=(difference_type dist) { return operator+=(-dist); }
95 Iterator& operator++() { ++m_bitpos; if (m_bitpos == BITS_PER_WORD) { m_bitpos = 0; ++m_it; }; return *this; }
96 Iterator operator++(int) { auto ret{*this}; operator++(); return ret; }
97 Iterator& operator--() { if (m_bitpos == 0) { m_bitpos = BITS_PER_WORD; --m_it; }; --m_bitpos; return *this; }
98 Iterator operator--(int) { auto ret{*this}; operator--(); return ret; }
99 friend Iterator operator+(Iterator x, difference_type dist) { x += dist; return x; }
100 friend Iterator operator+(difference_type dist, Iterator x) { x += dist; return x; }
101 friend Iterator operator-(Iterator x, difference_type dist) { x -= dist; return x; }
102 friend bool operator<(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) < std::tie(y.m_it, y.m_bitpos); }
103 friend bool operator>(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) > std::tie(y.m_it, y.m_bitpos); }
104 friend bool operator<=(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) <= std::tie(y.m_it, y.m_bitpos); }
105 friend bool operator>=(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) >= std::tie(y.m_it, y.m_bitpos); }
106 friend bool operator==(const Iterator& x, const Iterator& y) { return x.m_it == y.m_it && x.m_bitpos == y.m_bitpos; }
107 friend bool operator!=(const Iterator& x, const Iterator& y) { return x.m_it != y.m_it || x.m_bitpos != y.m_bitpos; }
108 reference operator*() const { return (*m_it)[m_bitpos]; }
109 reference operator[](difference_type pos) const { return *(*this + pos); }
110 };
111
112 public:
113 using value_type = bool;
114 using size_type = std::size_t;
115 using difference_type = typename deque_type::difference_type;
116 using reference = typename word_type::reference;
117 using const_reference = bool;
118 using iterator = Iterator<false>;
119 using const_iterator = Iterator<true>;
120 using pointer = void;
121 using const_pointer = void;
122 using reverse_iterator = std::reverse_iterator<iterator>;
123 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
124
125 private:
126 /** Deque of bitsets storing the actual bit data. */
127 deque_type m_deque;
128
129 /** Number of unused bits at the front of m_deque.front(). */
130 int m_pad_begin;
131
132 /** Number of unused bits at the back of m_deque.back(). */
133 int m_pad_end;
134
135 /** Shrink the container by n bits, removing from the end. */
136 void erase_back(size_type n)
137 {
138 if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_end)) {
139 n -= BITS_PER_WORD - m_pad_end;
140 m_pad_end = 0;
141 m_deque.erase(m_deque.end() - 1 - (n / BITS_PER_WORD), m_deque.end());
142 n %= BITS_PER_WORD;
143 }
144 if (n) {
145 auto& last = m_deque.back();
146 while (n) {
147 last.reset(BITS_PER_WORD - 1 - m_pad_end);
148 ++m_pad_end;
149 --n;
150 }
151 }
152 }
153
154 /** Extend the container by n bits, adding at the end. */
155 void extend_back(size_type n)
156 {
157 if (n > static_cast<size_type>(m_pad_end)) {
158 n -= m_pad_end + 1;
159 m_pad_end = BITS_PER_WORD - 1;
160 m_deque.insert(m_deque.end(), 1 + (n / BITS_PER_WORD), {});
161 n %= BITS_PER_WORD;
162 }
163 m_pad_end -= n;
164 }
165
166 /** Shrink the container by n bits, removing from the beginning. */
167 void erase_front(size_type n)
168 {
169 if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_begin)) {
170 n -= BITS_PER_WORD - m_pad_begin;
171 m_pad_begin = 0;
172 m_deque.erase(m_deque.begin(), m_deque.begin() + 1 + (n / BITS_PER_WORD));
173 n %= BITS_PER_WORD;
174 }
175 if (n) {
176 auto& first = m_deque.front();
177 while (n) {
178 first.reset(m_pad_begin);
179 ++m_pad_begin;
180 --n;
181 }
182 }
183 }
184
185 /** Extend the container by n bits, adding at the beginning. */
186 void extend_front(size_type n)
187 {
188 if (n > static_cast<size_type>(m_pad_begin)) {
189 n -= m_pad_begin + 1;
190 m_pad_begin = BITS_PER_WORD - 1;
191 m_deque.insert(m_deque.begin(), 1 + (n / BITS_PER_WORD), {});
192 n %= BITS_PER_WORD;
193 }
194 m_pad_begin -= n;
195 }
196
197 /** Insert a sequence of falses anywhere in the container. */
198 void insert_zeroes(size_type before, size_type count)
199 {
200 size_type after = size() - before;
201 if (before < after) {
202 extend_front(count);
203 std::move(begin() + count, begin() + count + before, begin());
204 } else {
205 extend_back(count);
206 std::move_backward(begin() + before, begin() + before + after, end());
207 }
208 }
209
210 public:
211 /** Construct an empty container. */
212 explicit bitdeque() : m_pad_begin{0}, m_pad_end{0} {}
213
214 /** Set the container equal to count times the value of val. */
215 void assign(size_type count, bool val)
216 {
217 m_deque.clear();
218 m_deque.resize((count + BITS_PER_WORD - 1) / BITS_PER_WORD);
219 m_pad_begin = 0;
220 m_pad_end = 0;
221 if (val) {
222 for (auto& elem : m_deque) elem.flip();
223 }
224 if (count % BITS_PER_WORD) {
225 erase_back(BITS_PER_WORD - (count % BITS_PER_WORD));
226 }
227 }
228
229 /** Construct a container containing count times the value of val. */
230 bitdeque(size_type count, bool val) { assign(count, val); }
231
232 /** Construct a container containing count false values. */
233 explicit bitdeque(size_t count) { assign(count, false); }
234
235 /** Copy constructor. */
236 bitdeque(const bitdeque&) = default;
237
238 /** Move constructor. */
239 bitdeque(bitdeque&&) noexcept = default;
240
241 /** Copy assignment operator. */
242 bitdeque& operator=(const bitdeque& other) = default;
243
244 /** Move assignment operator. */
245 bitdeque& operator=(bitdeque&& other) noexcept = default;
246
247 // Iterator functions.
248 iterator begin() noexcept { return {m_deque.begin(), m_pad_begin}; }
249 iterator end() noexcept { return iterator{m_deque.end(), 0} - m_pad_end; }
250 const_iterator begin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; }
251 const_iterator cbegin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; }
252 const_iterator end() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; }
253 const_iterator cend() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; }
254 reverse_iterator rbegin() noexcept { return reverse_iterator{end()}; }
255 reverse_iterator rend() noexcept { return reverse_iterator{begin()}; }
256 const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator{cend()}; }
257 const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{cend()}; }
258 const_reverse_iterator rend() const noexcept { return const_reverse_iterator{cbegin()}; }
259 const_reverse_iterator crend() const noexcept { return const_reverse_iterator{cbegin()}; }
260
261 /** Count the number of bits in the container. */
262 size_type size() const noexcept { return m_deque.size() * BITS_PER_WORD - m_pad_begin - m_pad_end; }
263
264 /** Determine whether the container is empty. */
265 bool empty() const noexcept
266 {
267 return m_deque.size() == 0 || (m_deque.size() == 1 && (m_pad_begin + m_pad_end == BITS_PER_WORD));
268 }
269
270 /** Return the maximum size of the container. */
271 size_type max_size() const noexcept
272 {
273 if (m_deque.max_size() < std::numeric_limits<difference_type>::max() / BITS_PER_WORD) {
274 return m_deque.max_size() * BITS_PER_WORD;
275 } else {
276 return std::numeric_limits<difference_type>::max();
277 }
278 }
279
280 /** Set the container equal to the bits in [first,last). */
281 template<typename It>
282 void assign(It first, It last)
283 {
284 size_type count = std::distance(first, last);
285 assign(count, false);
286 auto it = begin();
287 while (first != last) {
288 *(it++) = *(first++);
289 }
290 }
291
292 /** Set the container equal to the bits in ilist. */
293 void assign(std::initializer_list<bool> ilist)
294 {
295 assign(ilist.size(), false);
296 auto it = begin();
297 auto init = ilist.begin();
298 while (init != ilist.end()) {
299 *(it++) = *(init++);
300 }
301 }
302
303 /** Set the container equal to the bits in ilist. */
304 bitdeque& operator=(std::initializer_list<bool> ilist)
305 {
306 assign(ilist);
307 return *this;
308 }
309
310 /** Construct a container containing the bits in [first,last). */
311 template<typename It>
312 bitdeque(It first, It last) { assign(first, last); }
313
314 /** Construct a container containing the bits in ilist. */
315 bitdeque(std::initializer_list<bool> ilist) { assign(ilist); }
316
317 // Access an element of the container, with bounds checking.
318 reference at(size_type position)
319 {
320 if (position >= size()) throw std::out_of_range("bitdeque::at() out of range");
321 return begin()[position];
322 }
323 const_reference at(size_type position) const
324 {
325 if (position >= size()) throw std::out_of_range("bitdeque::at() out of range");
326 return cbegin()[position];
327 }
328
329 // Access elements of the container without bounds checking.
330 reference operator[](size_type position) { return begin()[position]; }
331 const_reference operator[](size_type position) const { return cbegin()[position]; }
332 reference front() { return *begin(); }
333 const_reference front() const { return *cbegin(); }
334 reference back() { return end()[-1]; }
335 const_reference back() const { return cend()[-1]; }
336
337 /** Release unused memory. */
338 void shrink_to_fit()
339 {
340 m_deque.shrink_to_fit();
341 }
342
343 /** Empty the container. */
344 void clear() noexcept
345 {
346 m_deque.clear();
347 m_pad_begin = m_pad_end = 0;
348 }
349
350 // Append an element to the container.
351 void push_back(bool val)
352 {
353 extend_back(1);
354 back() = val;
355 }
356 reference emplace_back(bool val)
357 {
358 extend_back(1);
359 auto ref = back();
360 ref = val;
361 return ref;
362 }
363
364 // Prepend an element to the container.
365 void push_front(bool val)
366 {
367 extend_front(1);
368 front() = val;
369 }
370 reference emplace_front(bool val)
371 {
372 extend_front(1);
373 auto ref = front();
374 ref = val;
375 return ref;
376 }
377
378 // Remove the last element from the container.
379 void pop_back()
380 {
381 erase_back(1);
382 }
383
384 // Remove the first element from the container.
385 void pop_front()
386 {
387 erase_front(1);
388 }
389
390 /** Resize the container. */
391 void resize(size_type n)
392 {
393 if (n < size()) {
394 erase_back(size() - n);
395 } else {
396 extend_back(n - size());
397 }
398 }
399
400 // Swap two containers.
401 void swap(bitdeque& other) noexcept
402 {
403 std::swap(m_deque, other.m_deque);
404 std::swap(m_pad_begin, other.m_pad_begin);
405 std::swap(m_pad_end, other.m_pad_end);
406 }
407 friend void swap(bitdeque& b1, bitdeque& b2) noexcept { b1.swap(b2); }
408
409 // Erase elements from the container.
410 iterator erase(const_iterator first, const_iterator last)
411 {
412 size_type before = std::distance(cbegin(), first);
413 size_type dist = std::distance(first, last);
414 size_type after = std::distance(last, cend());
415 if (before < after) {
416 std::move_backward(begin(), begin() + before, end() - after);
417 erase_front(dist);
418 return begin() + before;
419 } else {
420 std::move(end() - after, end(), begin() + before);
421 erase_back(dist);
422 return end() - after;
423 }
424 }
425
426 iterator erase(iterator first, iterator last) { return erase(const_iterator{first}, const_iterator{last}); }
427 iterator erase(const_iterator pos) { return erase(pos, pos + 1); }
428 iterator erase(iterator pos) { return erase(const_iterator{pos}, const_iterator{pos} + 1); }
429
430 // Insert elements into the container.
431 iterator insert(const_iterator pos, bool val)
432 {
433 size_type before = pos - cbegin();
434 insert_zeroes(before, 1);
435 auto it = begin() + before;
436 *it = val;
437 return it;
438 }
439
440 iterator emplace(const_iterator pos, bool val) { return insert(pos, val); }
441
442 iterator insert(const_iterator pos, size_type count, bool val)
443 {
444 size_type before = pos - cbegin();
445 insert_zeroes(before, count);
446 auto it_begin = begin() + before;
447 auto it = it_begin;
448 auto it_end = it + count;
449 while (it != it_end) *(it++) = val;
450 return it_begin;
451 }
452
453 template<typename It>
454 iterator insert(const_iterator pos, It first, It last)
455 {
456 size_type before = pos - cbegin();
457 size_type count = std::distance(first, last);
458 insert_zeroes(before, count);
459 auto it_begin = begin() + before;
460 auto it = it_begin;
461 while (first != last) {
462 *(it++) = *(first++);
463 }
464 return it_begin;
465 }
466 };
467
468 #endif // LIMENKA_UTIL_BITDEQUE_H
469