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