source: Daodan/MSYS2/mingw32/include/c++/11.2.0/tr2/dynamic_bitset

Last change on this file was 1166, checked in by rossy, 3 years ago

Daodan: Replace MinGW build env with an up-to-date MSYS2 env
File size: 33.5 KB
Line 
1// TR2 <dynamic_bitset> -*- C++ -*-
2
3// Copyright (C) 2009-2021 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file tr2/dynamic_bitset
26 * This is a TR2 C++ Library header.
27 */
28
29#ifndef _GLIBCXX_TR2_DYNAMIC_BITSET
30#define _GLIBCXX_TR2_DYNAMIC_BITSET 1
31
32#pragma GCC system_header
33
34#include <limits>
35#include <vector>
36#include <string>
37#include <istream>
38#include <bits/functexcept.h>
39#include <bits/stl_algo.h> // For fill
40#include <bits/cxxabi_forced.h>
41
42namespace std _GLIBCXX_VISIBILITY(default)
43{
44_GLIBCXX_BEGIN_NAMESPACE_VERSION
45
46namespace tr2
47{
48 /**
49 * @defgroup dynamic_bitset Dynamic Bitset.
50 * @ingroup extensions
51 *
52 * @{
53 */
54
55 /**
56 * Base class, general case.
57 *
58 * See documentation for dynamic_bitset.
59 */
60 template<typename _WordT = unsigned long long,
61 typename _Alloc = std::allocator<_WordT>>
62 struct __dynamic_bitset_base
63 {
64 static_assert(std::is_unsigned<_WordT>::value, "template argument "
65 "_WordT not an unsigned integral type");
66
67 typedef _WordT block_type;
68 typedef _Alloc allocator_type;
69 typedef size_t size_type;
70
71 static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type);
72 static const size_type npos = static_cast<size_type>(-1);
73
74 /// 0 is the least significant word.
75 std::vector<block_type, allocator_type> _M_w;
76
77 explicit
78 __dynamic_bitset_base(const allocator_type& __alloc)
79 : _M_w(__alloc)
80 { }
81
82 __dynamic_bitset_base() = default;
83 __dynamic_bitset_base(const __dynamic_bitset_base&) = default;
84 __dynamic_bitset_base(__dynamic_bitset_base&& __b) = default;
85 __dynamic_bitset_base& operator=(const __dynamic_bitset_base&) = default;
86 __dynamic_bitset_base& operator=(__dynamic_bitset_base&&) = default;
87 ~__dynamic_bitset_base() = default;
88
89 explicit
90 __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL,
91 const allocator_type& __alloc = allocator_type())
92 : _M_w(__nbits / _S_bits_per_block + (__nbits % _S_bits_per_block > 0),
93 block_type(0), __alloc)
94 {
95 if (__nbits < std::numeric_limits<decltype(__val)>::digits)
96 __val &= ~(-1ULL << __nbits);
97 if (__val == 0)
98 return;
99
100 if _GLIBCXX17_CONSTEXPR (sizeof(__val) == sizeof(block_type))
101 _M_w[0] = __val;
102 else
103 {
104 const size_t __n
105 = std::min(_M_w.size(), sizeof(__val) / sizeof(block_type));
106 for (size_t __i = 0; __val && __i < __n; ++__i)
107 {
108 _M_w[__i] = static_cast<block_type>(__val);
109 __val >>= _S_bits_per_block;
110 }
111 }
112 }
113
114 void
115 _M_swap(__dynamic_bitset_base& __b) noexcept
116 { this->_M_w.swap(__b._M_w); }
117
118 void
119 _M_clear() noexcept
120 { this->_M_w.clear(); }
121
122 void
123 _M_resize(size_t __nbits, bool __value)
124 {
125 size_t __sz = __nbits / _S_bits_per_block;
126 if (__nbits % _S_bits_per_block > 0)
127 ++__sz;
128 if (__sz != this->_M_w.size())
129 {
130 block_type __val = 0;
131 if (__value)
132 __val = std::numeric_limits<block_type>::max();
133 this->_M_w.resize(__sz, __val);
134 }
135 }
136
137 allocator_type
138 _M_get_allocator() const noexcept
139 { return this->_M_w.get_allocator(); }
140
141 static size_type
142 _S_whichword(size_type __pos) noexcept
143 { return __pos / _S_bits_per_block; }
144
145 static size_type
146 _S_whichbyte(size_type __pos) noexcept
147 { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
148
149 static size_type
150 _S_whichbit(size_type __pos) noexcept
151 { return __pos % _S_bits_per_block; }
152
153 static block_type
154 _S_maskbit(size_type __pos) noexcept
155 { return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
156
157 block_type&
158 _M_getword(size_type __pos) noexcept
159 { return this->_M_w[_S_whichword(__pos)]; }
160
161 block_type
162 _M_getword(size_type __pos) const noexcept
163 { return this->_M_w[_S_whichword(__pos)]; }
164
165 block_type&
166 _M_hiword() noexcept
167 { return this->_M_w[_M_w.size() - 1]; }
168
169 block_type
170 _M_hiword() const noexcept
171 { return this->_M_w[_M_w.size() - 1]; }
172
173 void
174 _M_do_and(const __dynamic_bitset_base& __x) noexcept
175 {
176 if (__x._M_w.size() == this->_M_w.size())
177 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
178 this->_M_w[__i] &= __x._M_w[__i];
179 else
180 return;
181 }
182
183 void
184 _M_do_or(const __dynamic_bitset_base& __x) noexcept
185 {
186 if (__x._M_w.size() == this->_M_w.size())
187 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
188 this->_M_w[__i] |= __x._M_w[__i];
189 else
190 return;
191 }
192
193 void
194 _M_do_xor(const __dynamic_bitset_base& __x) noexcept
195 {
196 if (__x._M_w.size() == this->_M_w.size())
197 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
198 this->_M_w[__i] ^= __x._M_w[__i];
199 else
200 return;
201 }
202
203 void
204 _M_do_dif(const __dynamic_bitset_base& __x) noexcept
205 {
206 if (__x._M_w.size() == this->_M_w.size())
207 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
208 this->_M_w[__i] &= ~__x._M_w[__i];
209 else
210 return;
211 }
212
213 void
214 _M_do_left_shift(size_t __shift);
215
216 void
217 _M_do_right_shift(size_t __shift);
218
219 void
220 _M_do_flip() noexcept
221 {
222 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
223 this->_M_w[__i] = ~this->_M_w[__i];
224 }
225
226 void
227 _M_do_set() noexcept
228 {
229 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
230 this->_M_w[__i] = static_cast<block_type>(-1);
231 }
232
233 void
234 _M_do_reset() noexcept
235 {
236 std::fill(_M_w.begin(), _M_w.end(), static_cast<block_type>(0));
237 }
238
239 bool
240 _M_is_equal(const __dynamic_bitset_base& __x) const noexcept
241 {
242 if (__x._M_w.size() == this->_M_w.size())
243 {
244 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
245 if (this->_M_w[__i] != __x._M_w[__i])
246 return false;
247 return true;
248 }
249 else
250 return false;
251 }
252
253 bool
254 _M_is_less(const __dynamic_bitset_base& __x) const noexcept
255 {
256 if (__x._M_w.size() == this->_M_w.size())
257 {
258 for (size_t __i = this->_M_w.size(); __i > 0; --__i)
259 {
260 if (this->_M_w[__i-1] < __x._M_w[__i-1])
261 return true;
262 else if (this->_M_w[__i-1] > __x._M_w[__i-1])
263 return false;
264 }
265 return false;
266 }
267 else
268 return false;
269 }
270
271 size_t
272 _M_are_all_aux() const noexcept
273 {
274 for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i)
275 if (_M_w[__i] != static_cast<block_type>(-1))
276 return 0;
277 return ((this->_M_w.size() - 1) * _S_bits_per_block
278 + __builtin_popcountll(this->_M_hiword()));
279 }
280
281 bool
282 _M_is_any() const noexcept
283 {
284 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
285 if (this->_M_w[__i] != static_cast<block_type>(0))
286 return true;
287 return false;
288 }
289
290 bool
291 _M_is_subset_of(const __dynamic_bitset_base& __b) noexcept
292 {
293 if (__b._M_w.size() == this->_M_w.size())
294 {
295 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
296 if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i]))
297 return false;
298 return true;
299 }
300 else
301 return false;
302 }
303
304 bool
305 _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const noexcept
306 {
307 if (this->is_subset_of(__b))
308 {
309 if (*this == __b)
310 return false;
311 else
312 return true;
313 }
314 else
315 return false;
316 }
317
318 size_t
319 _M_do_count() const noexcept
320 {
321 size_t __result = 0;
322 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
323 __result += __builtin_popcountll(this->_M_w[__i]);
324 return __result;
325 }
326
327 size_type
328 _M_size() const noexcept
329 { return this->_M_w.size(); }
330
331 unsigned long
332 _M_do_to_ulong() const;
333
334 unsigned long long
335 _M_do_to_ullong() const;
336
337 // find first "on" bit
338 size_type
339 _M_do_find_first(size_t __not_found) const;
340
341 // find the next "on" bit that follows "prev"
342 size_type
343 _M_do_find_next(size_t __prev, size_t __not_found) const;
344
345 // do append of block
346 void
347 _M_do_append_block(block_type __block, size_type __pos)
348 {
349 size_t __offset = __pos % _S_bits_per_block;
350 if (__offset == 0)
351 this->_M_w.push_back(__block);
352 else
353 {
354 this->_M_hiword() |= (__block << __offset);
355 this->_M_w.push_back(__block >> (_S_bits_per_block - __offset));
356 }
357 }
358 };
359
360 /**
361 * @brief The %dynamic_bitset class represents a sequence of bits.
362 *
363 * See N2050,
364 * Proposal to Add a Dynamically Sizeable Bitset to the Standard Library.
365 * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2050.pdf
366 *
367 * In the general unoptimized case, storage is allocated in
368 * word-sized blocks. Let B be the number of bits in a word, then
369 * (Nb+(B-1))/B words will be used for storage. B - Nb%B bits are
370 * unused. (They are the high-order bits in the highest word.) It
371 * is a class invariant that those unused bits are always zero.
372 *
373 * If you think of %dynamic_bitset as "a simple array of bits," be
374 * aware that your mental picture is reversed: a %dynamic_bitset
375 * behaves the same way as bits in integers do, with the bit at
376 * index 0 in the "least significant / right-hand" position, and
377 * the bit at index Nb-1 in the "most significant / left-hand"
378 * position. Thus, unlike other containers, a %dynamic_bitset's
379 * index "counts from right to left," to put it very loosely.
380 *
381 * This behavior is preserved when translating to and from strings.
382 * For example, the first line of the following program probably
383 * prints "b('a') is 0001100001" on a modern ASCII system.
384 *
385 * @code
386 * #include <dynamic_bitset>
387 * #include <iostream>
388 * #include <sstream>
389 *
390 * using namespace std;
391 *
392 * int main()
393 * {
394 * long a = 'a';
395 * dynamic_bitset<> b(a);
396 *
397 * cout << "b('a') is " << b << endl;
398 *
399 * ostringstream s;
400 * s << b;
401 * string str = s.str();
402 * cout << "index 3 in the string is " << str[3] << " but\n"
403 * << "index 3 in the bitset is " << b[3] << endl;
404 * }
405 * @endcode
406 *
407 * Most of the actual code isn't contained in %dynamic_bitset<>
408 * itself, but in the base class __dynamic_bitset_base. The base
409 * class works with whole words, not with individual bits. This
410 * allows us to specialize __dynamic_bitset_base for the important
411 * special case where the %dynamic_bitset is only a single word.
412 *
413 * Extra confusion can result due to the fact that the storage for
414 * __dynamic_bitset_base @e is a vector, and is indexed as such. This is
415 * carefully encapsulated.
416 */
417 template<typename _WordT = unsigned long long,
418 typename _Alloc = std::allocator<_WordT>>
419 class dynamic_bitset
420 : private __dynamic_bitset_base<_WordT, _Alloc>
421 {
422 static_assert(std::is_unsigned<_WordT>::value, "template argument "
423 "_WordT not an unsigned integral type");
424
425 public:
426
427 typedef __dynamic_bitset_base<_WordT, _Alloc> _Base;
428 typedef _WordT block_type;
429 typedef _Alloc allocator_type;
430 typedef size_t size_type;
431
432 static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type);
433 // Use this: constexpr size_type std::numeric_limits<size_type>::max().
434 static const size_type npos = static_cast<size_type>(-1);
435
436 private:
437
438 // Clear the unused bits in the uppermost word.
439 void
440 _M_do_sanitize()
441 {
442 size_type __shift = this->_M_Nb % bits_per_block;
443 if (__shift > 0)
444 this->_M_hiword() &= block_type(~(block_type(-1) << __shift));
445 }
446
447 // Set the unused bits in the uppermost word.
448 void
449 _M_do_fill()
450 {
451 size_type __shift = this->_M_Nb % bits_per_block;
452 if (__shift > 0)
453 this->_M_hiword() |= block_type(block_type(-1) << __shift);
454 }
455
456 /**
457 * These versions of single-bit set, reset, flip, and test
458 * do no range checking.
459 */
460 dynamic_bitset&
461 _M_unchecked_set(size_type __pos) noexcept
462 {
463 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
464 return *this;
465 }
466
467 dynamic_bitset&
468 _M_unchecked_set(size_type __pos, int __val) noexcept
469 {
470 if (__val)
471 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
472 else
473 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
474 return *this;
475 }
476
477 dynamic_bitset&
478 _M_unchecked_reset(size_type __pos) noexcept
479 {
480 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
481 return *this;
482 }
483
484 dynamic_bitset&
485 _M_unchecked_flip(size_type __pos) noexcept
486 {
487 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
488 return *this;
489 }
490
491 bool
492 _M_unchecked_test(size_type __pos) const noexcept
493 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
494 != static_cast<_WordT>(0)); }
495
496 size_type _M_Nb = 0;
497
498 public:
499 /**
500 * This encapsulates the concept of a single bit. An instance
501 * of this class is a proxy for an actual bit; this way the
502 * individual bit operations are done as faster word-size
503 * bitwise instructions.
504 *
505 * Most users will never need to use this class directly;
506 * conversions to and from bool are automatic and should be
507 * transparent. Overloaded operators help to preserve the
508 * illusion.
509 *
510 * (On a typical system, this "bit %reference" is 64 times the
511 * size of an actual bit. Ha.)
512 */
513 class reference
514 {
515 friend class dynamic_bitset;
516
517 block_type *_M_wp;
518 size_type _M_bpos;
519
520 public:
521 reference(dynamic_bitset& __b, size_type __pos) noexcept
522 {
523 this->_M_wp = &__b._M_getword(__pos);
524 this->_M_bpos = _Base::_S_whichbit(__pos);
525 }
526
527 // For b[i] = __x;
528 reference&
529 operator=(bool __x) noexcept
530 {
531 if (__x)
532 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
533 else
534 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
535 return *this;
536 }
537
538 // For b[i] = b[__j];
539 reference&
540 operator=(const reference& __j) noexcept
541 {
542 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
543 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
544 else
545 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
546 return *this;
547 }
548
549 // Flips the bit
550 bool
551 operator~() const noexcept
552 { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
553
554 // For __x = b[i];
555 operator bool() const noexcept
556 { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
557
558 // For b[i].flip();
559 reference&
560 flip() noexcept
561 {
562 *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
563 return *this;
564 }
565 };
566
567 friend class reference;
568
569 typedef bool const_reference;
570
571 // 23.3.5.1 constructors:
572
573 /// All bits set to zero.
574 dynamic_bitset() = default;
575
576 /// All bits set to zero.
577 explicit
578 dynamic_bitset(const allocator_type& __alloc)
579 : _Base(__alloc)
580 { }
581
582 /// Initial bits bitwise-copied from a single word (others set to zero).
583 explicit
584 dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,
585 const allocator_type& __alloc = allocator_type())
586 : _Base(__nbits, __val, __alloc),
587 _M_Nb(__nbits)
588 { }
589
590 dynamic_bitset(initializer_list<block_type> __il,
591 const allocator_type& __alloc = allocator_type())
592 : _Base(__alloc)
593 { this->append(__il); }
594
595 /**
596 * @brief Use a subset of a string.
597 * @param __str A string of '0' and '1' characters.
598 * @param __pos Index of the first character in @p __str to use.
599 * @param __n The number of characters to copy.
600 * @param __zero The character to use for unset bits.
601 * @param __one The character to use for set bits.
602 * @param __alloc An allocator.
603 * @throw std::out_of_range If @p __pos is bigger the size of @p __str.
604 * @throw std::invalid_argument If a character appears in the string
605 * which is neither '0' nor '1'.
606 */
607 template<typename _CharT, typename _Traits, typename _Alloc1>
608 explicit
609 dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,
610 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
611 __pos = 0,
612 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
613 __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos,
614 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
615 const allocator_type& __alloc = allocator_type())
616 : _Base(__alloc)
617 {
618 if (__pos > __str.size())
619 __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
620 "not valid"));
621
622 // Watch for npos.
623 this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);
624 this->resize(this->_M_Nb);
625 this->_M_copy_from_string(__str, __pos, __n);
626 }
627
628 /**
629 * @brief Construct from a string.
630 * @param __str A string of '0' and '1' characters.
631 * @param __alloc An allocator.
632 * @throw std::invalid_argument If a character appears in the string
633 * which is neither '0' nor '1'.
634 */
635 explicit
636 dynamic_bitset(const char* __str,
637 const allocator_type& __alloc = allocator_type())
638 : _Base(__builtin_strlen(__str), 0ULL, __alloc),
639 _M_Nb(__builtin_strlen(__str))
640 {
641 this->_M_copy_from_ptr(__str, _M_Nb, 0, _M_Nb);
642 }
643
644 /// Copy constructor.
645 dynamic_bitset(const dynamic_bitset&) = default;
646
647 /// Move constructor.
648 dynamic_bitset(dynamic_bitset&& __b) noexcept
649 : _Base(std::move(__b)), _M_Nb(__b._M_Nb)
650 { __b.clear(); }
651
652 /// Swap with another bitset.
653 void
654 swap(dynamic_bitset& __b) noexcept
655 {
656 this->_M_swap(__b);
657 std::swap(this->_M_Nb, __b._M_Nb);
658 }
659
660 /// Copy assignment operator.
661 dynamic_bitset& operator=(const dynamic_bitset&) = default;
662
663 /// Move assignment operator.
664 dynamic_bitset&
665 operator=(dynamic_bitset&& __b)
666 noexcept(std::is_nothrow_move_assignable<_Base>::value)
667 {
668 static_cast<_Base&>(*this) = static_cast<_Base&&>(__b);
669 _M_Nb = __b._M_Nb;
670 if _GLIBCXX17_CONSTEXPR (std::is_nothrow_move_assignable<_Base>::value)
671 __b._M_Nb = 0;
672 else if (get_allocator() == __b.get_allocator())
673 __b._M_Nb = 0;
674 return *this;
675 }
676
677 /**
678 * @brief Return the allocator for the bitset.
679 */
680 allocator_type
681 get_allocator() const noexcept
682 { return this->_M_get_allocator(); }
683
684 /**
685 * @brief Resize the bitset.
686 */
687 void
688 resize(size_type __nbits, bool __value = false)
689 {
690 if (__value)
691 this->_M_do_fill();
692 this->_M_resize(__nbits, __value);
693 this->_M_Nb = __nbits;
694 this->_M_do_sanitize();
695 }
696
697 /**
698 * @brief Clear the bitset.
699 */
700 void
701 clear()
702 {
703 this->_M_clear();
704 this->_M_Nb = 0;
705 }
706
707 /**
708 * @brief Push a bit onto the high end of the bitset.
709 */
710 void
711 push_back(bool __bit)
712 {
713 if (this->size() % bits_per_block == 0)
714 this->_M_do_append_block(block_type(__bit), this->_M_Nb);
715 else
716 this->_M_unchecked_set(this->_M_Nb, __bit);
717 ++this->_M_Nb;
718 }
719
720 // XXX why is there no pop_back() member in the proposal?
721
722 /**
723 * @brief Append a block.
724 */
725 void
726 append(block_type __block)
727 {
728 this->_M_do_append_block(__block, this->_M_Nb);
729 this->_M_Nb += bits_per_block;
730 }
731
732 /**
733 * @brief
734 */
735 void
736 append(initializer_list<block_type> __il)
737 { this->append(__il.begin(), __il.end()); }
738
739 /**
740 * @brief Append an iterator range of blocks.
741 */
742 template <typename _BlockInputIterator>
743 void
744 append(_BlockInputIterator __first, _BlockInputIterator __last)
745 {
746 for (; __first != __last; ++__first)
747 this->append(*__first);
748 }
749
750 // 23.3.5.2 dynamic_bitset operations:
751 ///@{
752 /**
753 * @brief Operations on dynamic_bitsets.
754 * @param __rhs A same-sized dynamic_bitset.
755 *
756 * These should be self-explanatory.
757 */
758 dynamic_bitset&
759 operator&=(const dynamic_bitset& __rhs)
760 {
761 this->_M_do_and(__rhs);
762 return *this;
763 }
764
765 dynamic_bitset&
766 operator&=(dynamic_bitset&& __rhs)
767 {
768 this->_M_do_and(std::move(__rhs));
769 return *this;
770 }
771
772 dynamic_bitset&
773 operator|=(const dynamic_bitset& __rhs)
774 {
775 this->_M_do_or(__rhs);
776 return *this;
777 }
778
779 dynamic_bitset&
780 operator^=(const dynamic_bitset& __rhs)
781 {
782 this->_M_do_xor(__rhs);
783 return *this;
784 }
785
786 dynamic_bitset&
787 operator-=(const dynamic_bitset& __rhs)
788 {
789 this->_M_do_dif(__rhs);
790 return *this;
791 }
792 ///@}
793
794 ///@{
795 /**
796 * @brief Operations on dynamic_bitsets.
797 * @param __pos The number of places to shift.
798 *
799 * These should be self-explanatory.
800 */
801 dynamic_bitset&
802 operator<<=(size_type __pos)
803 {
804 if (__builtin_expect(__pos < this->_M_Nb, 1))
805 {
806 this->_M_do_left_shift(__pos);
807 this->_M_do_sanitize();
808 }
809 else
810 this->_M_do_reset();
811 return *this;
812 }
813
814 dynamic_bitset&
815 operator>>=(size_type __pos)
816 {
817 if (__builtin_expect(__pos < this->_M_Nb, 1))
818 {
819 this->_M_do_right_shift(__pos);
820 this->_M_do_sanitize();
821 }
822 else
823 this->_M_do_reset();
824 return *this;
825 }
826 ///@}
827
828 // Set, reset, and flip.
829 /**
830 * @brief Sets every bit to true.
831 */
832 dynamic_bitset&
833 set()
834 {
835 this->_M_do_set();
836 this->_M_do_sanitize();
837 return *this;
838 }
839
840 /**
841 * @brief Sets a given bit to a particular value.
842 * @param __pos The index of the bit.
843 * @param __val Either true or false, defaults to true.
844 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
845 */
846 dynamic_bitset&
847 set(size_type __pos, bool __val = true)
848 {
849 if (__pos >= _M_Nb)
850 __throw_out_of_range(__N("dynamic_bitset::set"));
851 return this->_M_unchecked_set(__pos, __val);
852 }
853
854 /**
855 * @brief Sets every bit to false.
856 */
857 dynamic_bitset&
858 reset()
859 {
860 this->_M_do_reset();
861 return *this;
862 }
863
864 /**
865 * @brief Sets a given bit to false.
866 * @param __pos The index of the bit.
867 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
868 *
869 * Same as writing @c set(__pos, false).
870 */
871 dynamic_bitset&
872 reset(size_type __pos)
873 {
874 if (__pos >= _M_Nb)
875 __throw_out_of_range(__N("dynamic_bitset::reset"));
876 return this->_M_unchecked_reset(__pos);
877 }
878
879 /**
880 * @brief Toggles every bit to its opposite value.
881 */
882 dynamic_bitset&
883 flip()
884 {
885 this->_M_do_flip();
886 this->_M_do_sanitize();
887 return *this;
888 }
889
890 /**
891 * @brief Toggles a given bit to its opposite value.
892 * @param __pos The index of the bit.
893 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
894 */
895 dynamic_bitset&
896 flip(size_type __pos)
897 {
898 if (__pos >= _M_Nb)
899 __throw_out_of_range(__N("dynamic_bitset::flip"));
900 return this->_M_unchecked_flip(__pos);
901 }
902
903 /// See the no-argument flip().
904 dynamic_bitset
905 operator~() const
906 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
907
908 ///@{
909 /**
910 * @brief Array-indexing support.
911 * @param __pos Index into the %dynamic_bitset.
912 * @return A bool for a 'const %dynamic_bitset'. For non-const
913 * bitsets, an instance of the reference proxy class.
914 * @note These operators do no range checking and throw no
915 * exceptions, as required by DR 11 to the standard.
916 */
917 reference
918 operator[](size_type __pos)
919 { return reference(*this,__pos); }
920
921 const_reference
922 operator[](size_type __pos) const
923 { return _M_unchecked_test(__pos); }
924 ///@}
925
926 /**
927 * @brief Returns a numerical interpretation of the %dynamic_bitset.
928 * @return The integral equivalent of the bits.
929 * @throw std::overflow_error If there are too many bits to be
930 * represented in an @c unsigned @c long.
931 */
932 unsigned long
933 to_ulong() const
934 { return this->_M_do_to_ulong(); }
935
936 /**
937 * @brief Returns a numerical interpretation of the %dynamic_bitset.
938 * @return The integral equivalent of the bits.
939 * @throw std::overflow_error If there are too many bits to be
940 * represented in an @c unsigned @c long.
941 */
942 unsigned long long
943 to_ullong() const
944 { return this->_M_do_to_ullong(); }
945
946 /**
947 * @brief Returns a character interpretation of the %dynamic_bitset.
948 * @return The string equivalent of the bits.
949 *
950 * Note the ordering of the bits: decreasing character positions
951 * correspond to increasing bit positions (see the main class notes for
952 * an example).
953 */
954 template<typename _CharT = char,
955 typename _Traits = std::char_traits<_CharT>,
956 typename _Alloc1 = std::allocator<_CharT>>
957 std::basic_string<_CharT, _Traits, _Alloc1>
958 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
959 {
960 std::basic_string<_CharT, _Traits, _Alloc1> __result;
961 _M_copy_to_string(__result, __zero, __one);
962 return __result;
963 }
964
965 // Helper functions for string operations.
966 template<typename _Traits = std::char_traits<char>,
967 typename _CharT = typename _Traits::char_type>
968 void
969 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
970 _CharT __zero = _CharT('0'),
971 _CharT __one = _CharT('1'));
972
973 template<typename _CharT, typename _Traits, typename _Alloc1>
974 void
975 _M_copy_from_string(const basic_string<_CharT, _Traits, _Alloc1>& __str,
976 size_t __pos, size_t __n,
977 _CharT __zero = _CharT('0'),
978 _CharT __one = _CharT('1'))
979 {
980 _M_copy_from_ptr<_Traits>(__str.data(), __str.size(), __pos, __n,
981 __zero, __one);
982 }
983
984 template<typename _CharT, typename _Traits, typename _Alloc1>
985 void
986 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
987 _CharT __zero = _CharT('0'),
988 _CharT __one = _CharT('1')) const;
989
990 /// Returns the number of bits which are set.
991 size_type
992 count() const noexcept
993 { return this->_M_do_count(); }
994
995 /// Returns the total number of bits.
996 size_type
997 size() const noexcept
998 { return this->_M_Nb; }
999
1000 /// Returns the total number of blocks.
1001 size_type
1002 num_blocks() const noexcept
1003 { return this->_M_size(); }
1004
1005 /// Returns true if the dynamic_bitset is empty.
1006 _GLIBCXX_NODISCARD bool
1007 empty() const noexcept
1008 { return (this->_M_Nb == 0); }
1009
1010 /// Returns the maximum size of a dynamic_bitset object having the same
1011 /// type as *this.
1012 /// The real answer is max() * bits_per_block but is likely to overflow.
1013 constexpr size_type
1014 max_size() noexcept
1015 { return std::numeric_limits<block_type>::max(); }
1016
1017 /**
1018 * @brief Tests the value of a bit.
1019 * @param __pos The index of a bit.
1020 * @return The value at @a __pos.
1021 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
1022 */
1023 bool
1024 test(size_type __pos) const
1025 {
1026 if (__pos >= _M_Nb)
1027 __throw_out_of_range(__N("dynamic_bitset::test"));
1028 return _M_unchecked_test(__pos);
1029 }
1030
1031 /**
1032 * @brief Tests whether all the bits are on.
1033 * @return True if all the bits are set.
1034 */
1035 bool
1036 all() const
1037 { return this->_M_are_all_aux() == _M_Nb; }
1038
1039 /**
1040 * @brief Tests whether any of the bits are on.
1041 * @return True if at least one bit is set.
1042 */
1043 bool
1044 any() const
1045 { return this->_M_is_any(); }
1046
1047 /**
1048 * @brief Tests whether any of the bits are on.
1049 * @return True if none of the bits are set.
1050 */
1051 bool
1052 none() const
1053 { return !this->_M_is_any(); }
1054
1055 ///@{
1056 /// Self-explanatory.
1057 dynamic_bitset
1058 operator<<(size_type __pos) const
1059 { return dynamic_bitset(*this) <<= __pos; }
1060
1061 dynamic_bitset
1062 operator>>(size_type __pos) const
1063 { return dynamic_bitset(*this) >>= __pos; }
1064 ///@}
1065
1066 /**
1067 * @brief Finds the index of the first "on" bit.
1068 * @return The index of the first bit set, or size() if not found.
1069 * @sa find_next
1070 */
1071 size_type
1072 find_first() const
1073 { return this->_M_do_find_first(this->_M_Nb); }
1074
1075 /**
1076 * @brief Finds the index of the next "on" bit after prev.
1077 * @return The index of the next bit set, or size() if not found.
1078 * @param __prev Where to start searching.
1079 * @sa find_first
1080 */
1081 size_type
1082 find_next(size_t __prev) const
1083 { return this->_M_do_find_next(__prev, this->_M_Nb); }
1084
1085 bool
1086 is_subset_of(const dynamic_bitset& __b) const
1087 { return this->_M_is_subset_of(__b); }
1088
1089 bool
1090 is_proper_subset_of(const dynamic_bitset& __b) const
1091 { return this->_M_is_proper_subset_of(__b); }
1092
1093 friend bool
1094 operator==(const dynamic_bitset& __lhs,
1095 const dynamic_bitset& __rhs) noexcept
1096 { return __lhs._M_Nb == __rhs._M_Nb && __lhs._M_is_equal(__rhs); }
1097
1098 friend bool
1099 operator<(const dynamic_bitset& __lhs,
1100 const dynamic_bitset& __rhs) noexcept
1101 { return __lhs._M_is_less(__rhs) || __lhs._M_Nb < __rhs._M_Nb; }
1102 };
1103
1104 template<typename _WordT, typename _Alloc>
1105 template<typename _CharT, typename _Traits, typename _Alloc1>
1106 inline void
1107 dynamic_bitset<_WordT, _Alloc>::
1108 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1109 _CharT __zero, _CharT __one) const
1110 {
1111 __str.assign(_M_Nb, __zero);
1112 for (size_t __i = _M_Nb; __i > 0; --__i)
1113 if (_M_unchecked_test(__i - 1))
1114 _Traits::assign(__str[_M_Nb - __i], __one);
1115 }
1116
1117
1118 ///@{
1119 /// These comparisons for equality/inequality are, well, @e bitwise.
1120
1121 template<typename _WordT, typename _Alloc>
1122 inline bool
1123 operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1124 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1125 { return !(__lhs == __rhs); }
1126
1127 template<typename _WordT, typename _Alloc>
1128 inline bool
1129 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1130 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1131 { return !(__lhs > __rhs); }
1132
1133 template<typename _WordT, typename _Alloc>
1134 inline bool
1135 operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1136 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1137 { return __rhs < __lhs; }
1138
1139 template<typename _WordT, typename _Alloc>
1140 inline bool
1141 operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1142 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1143 { return !(__lhs < __rhs); }
1144 ///@}
1145
1146 // 23.3.5.3 bitset operations:
1147 ///@{
1148 /**
1149 * @brief Global bitwise operations on bitsets.
1150 * @param __x A bitset.
1151 * @param __y A bitset of the same size as @a __x.
1152 * @return A new bitset.
1153 *
1154 * These should be self-explanatory.
1155 */
1156 template<typename _WordT, typename _Alloc>
1157 inline dynamic_bitset<_WordT, _Alloc>
1158 operator&(const dynamic_bitset<_WordT, _Alloc>& __x,
1159 const dynamic_bitset<_WordT, _Alloc>& __y)
1160 {
1161 dynamic_bitset<_WordT, _Alloc> __result(__x);
1162 __result &= __y;
1163 return __result;
1164 }
1165
1166 template<typename _WordT, typename _Alloc>
1167 inline dynamic_bitset<_WordT, _Alloc>
1168 operator|(const dynamic_bitset<_WordT, _Alloc>& __x,
1169 const dynamic_bitset<_WordT, _Alloc>& __y)
1170 {
1171 dynamic_bitset<_WordT, _Alloc> __result(__x);
1172 __result |= __y;
1173 return __result;
1174 }
1175
1176 template <typename _WordT, typename _Alloc>
1177 inline dynamic_bitset<_WordT, _Alloc>
1178 operator^(const dynamic_bitset<_WordT, _Alloc>& __x,
1179 const dynamic_bitset<_WordT, _Alloc>& __y)
1180 {
1181 dynamic_bitset<_WordT, _Alloc> __result(__x);
1182 __result ^= __y;
1183 return __result;
1184 }
1185
1186 template <typename _WordT, typename _Alloc>
1187 inline dynamic_bitset<_WordT, _Alloc>
1188 operator-(const dynamic_bitset<_WordT, _Alloc>& __x,
1189 const dynamic_bitset<_WordT, _Alloc>& __y)
1190 {
1191 dynamic_bitset<_WordT, _Alloc> __result(__x);
1192 __result -= __y;
1193 return __result;
1194 }
1195 ///@}
1196
1197 /// Stream output operator for dynamic_bitset.
1198 template <typename _CharT, typename _Traits,
1199 typename _WordT, typename _Alloc>
1200 inline std::basic_ostream<_CharT, _Traits>&
1201 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1202 const dynamic_bitset<_WordT, _Alloc>& __x)
1203 {
1204 std::basic_string<_CharT, _Traits> __tmp;
1205
1206 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
1207 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1208 return __os << __tmp;
1209 }
1210 /**
1211 * @}
1212 */
1213} // tr2
1214
1215_GLIBCXX_END_NAMESPACE_VERSION
1216} // std
1217
1218#include <tr2/dynamic_bitset.tcc>
1219
1220#endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */
Note: See TracBrowser for help on using the repository browser.