]>
Commit | Line | Data |
---|---|---|
54c1bf78 | 1 | // <bitset> -*- C++ -*- |
de96ac46 | 2 | |
348b0c31 | 3 | // Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc. |
de96ac46 BK |
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 2, 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 | // You should have received a copy of the GNU General Public License along | |
17 | // with this library; see the file COPYING. If not, write to the Free | |
18 | // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, | |
19 | // USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free software | |
22 | // library without restriction. Specifically, if other files instantiate | |
23 | // templates or use macros or inline functions from this file, or you compile | |
24 | // this file and link it with other files to produce an executable, this | |
25 | // file does not by itself cause the resulting executable to be covered by | |
26 | // the GNU General Public License. This exception does not however | |
27 | // invalidate any other reasons why the executable file might be covered by | |
28 | // the GNU General Public License. | |
29 | ||
54c1bf78 BK |
30 | /* |
31 | * Copyright (c) 1998 | |
32 | * Silicon Graphics Computer Systems, Inc. | |
33 | * | |
34 | * Permission to use, copy, modify, distribute and sell this software | |
35 | * and its documentation for any purpose is hereby granted without fee, | |
36 | * provided that the above copyright notice appear in all copies and | |
37 | * that both that copyright notice and this permission notice appear | |
38 | * in supporting documentation. Silicon Graphics makes no | |
39 | * representations about the suitability of this software for any | |
40 | * purpose. It is provided "as is" without express or implied warranty. | |
b963aad8 | 41 | */ |
54c1bf78 | 42 | |
ffe94f83 PE |
43 | /** @file bitset |
44 | * This is a Standard C++ Library header. You should @c #include this header | |
45 | * in your programs, rather than any of the "st[dl]_*.h" implementation files. | |
2f9d51b8 PE |
46 | */ |
47 | ||
1143680e SE |
48 | #ifndef _GLIBCXX_BITSET |
49 | #define _GLIBCXX_BITSET 1 | |
54c1bf78 BK |
50 | |
51 | #pragma GCC system_header | |
52 | ||
285b36d6 BK |
53 | #include <cstddef> // For size_t |
54 | #include <cstring> // For memset | |
55 | #include <limits> // For numeric_limits | |
54c1bf78 | 56 | #include <string> |
285b36d6 | 57 | #include <bits/functexcept.h> // For invalid_argument, out_of_range, |
b963aad8 | 58 | // overflow_error |
285b36d6 BK |
59 | #include <ostream> // For ostream (operator<<) |
60 | #include <istream> // For istream (operator>>) | |
54c1bf78 | 61 | |
3d7c150e BK |
62 | #define _GLIBCXX_BITSET_BITS_PER_WORD numeric_limits<unsigned long>::digits |
63 | #define _GLIBCXX_BITSET_WORDS(__n) \ | |
64 | ((__n) < 1 ? 0 : ((__n) + _GLIBCXX_BITSET_BITS_PER_WORD - 1)/_GLIBCXX_BITSET_BITS_PER_WORD) | |
54c1bf78 | 65 | |
390e4c0d | 66 | namespace _GLIBCXX_STD |
54c1bf78 | 67 | { |
b963aad8 PE |
68 | /** |
69 | * @if maint | |
70 | * Base class, general case. It is a class inveriant that _Nw will be | |
71 | * nonnegative. | |
72 | * | |
73 | * See documentation for bitset. | |
74 | * @endif | |
75 | */ | |
1cb7f91f | 76 | template<size_t _Nw> |
b963aad8 | 77 | struct _Base_bitset |
1cb7f91f BK |
78 | { |
79 | typedef unsigned long _WordT; | |
80 | ||
b963aad8 PE |
81 | /// 0 is the least significant word. |
82 | _WordT _M_w[_Nw]; | |
83 | ||
1cb7f91f | 84 | _Base_bitset() { _M_do_reset(); } |
b963aad8 | 85 | _Base_bitset(unsigned long __val) |
1cb7f91f BK |
86 | { |
87 | _M_do_reset(); | |
88 | _M_w[0] = __val; | |
89 | } | |
54c1bf78 | 90 | |
b963aad8 | 91 | static size_t |
1cb7f91f | 92 | _S_whichword(size_t __pos ) |
3d7c150e | 93 | { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } |
54c1bf78 | 94 | |
b963aad8 | 95 | static size_t |
1cb7f91f | 96 | _S_whichbyte(size_t __pos ) |
3d7c150e | 97 | { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } |
54c1bf78 | 98 | |
b963aad8 | 99 | static size_t |
1cb7f91f | 100 | _S_whichbit(size_t __pos ) |
3d7c150e | 101 | { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } |
54c1bf78 | 102 | |
b963aad8 | 103 | static _WordT |
1cb7f91f BK |
104 | _S_maskbit(size_t __pos ) |
105 | { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } | |
54c1bf78 | 106 | |
b963aad8 PE |
107 | _WordT& |
108 | _M_getword(size_t __pos) | |
1cb7f91f | 109 | { return _M_w[_S_whichword(__pos)]; } |
54c1bf78 | 110 | |
b963aad8 PE |
111 | _WordT |
112 | _M_getword(size_t __pos) const | |
1cb7f91f | 113 | { return _M_w[_S_whichword(__pos)]; } |
54c1bf78 | 114 | |
b963aad8 | 115 | _WordT& |
1cb7f91f | 116 | _M_hiword() { return _M_w[_Nw - 1]; } |
54c1bf78 | 117 | |
b963aad8 | 118 | _WordT |
1cb7f91f | 119 | _M_hiword() const { return _M_w[_Nw - 1]; } |
54c1bf78 | 120 | |
b963aad8 PE |
121 | void |
122 | _M_do_and(const _Base_bitset<_Nw>& __x) | |
1cb7f91f | 123 | { |
b963aad8 | 124 | for (size_t __i = 0; __i < _Nw; __i++) |
1cb7f91f BK |
125 | _M_w[__i] &= __x._M_w[__i]; |
126 | } | |
54c1bf78 | 127 | |
b963aad8 PE |
128 | void |
129 | _M_do_or(const _Base_bitset<_Nw>& __x) | |
1cb7f91f | 130 | { |
b963aad8 | 131 | for (size_t __i = 0; __i < _Nw; __i++) |
1cb7f91f BK |
132 | _M_w[__i] |= __x._M_w[__i]; |
133 | } | |
54c1bf78 | 134 | |
b963aad8 PE |
135 | void |
136 | _M_do_xor(const _Base_bitset<_Nw>& __x) | |
1cb7f91f BK |
137 | { |
138 | for (size_t __i = 0; __i < _Nw; __i++) | |
139 | _M_w[__i] ^= __x._M_w[__i]; | |
140 | } | |
54c1bf78 | 141 | |
b963aad8 | 142 | void |
1cb7f91f BK |
143 | _M_do_left_shift(size_t __shift); |
144 | ||
b963aad8 | 145 | void |
1cb7f91f | 146 | _M_do_right_shift(size_t __shift); |
b963aad8 PE |
147 | |
148 | void | |
149 | _M_do_flip() | |
1cb7f91f | 150 | { |
b963aad8 | 151 | for (size_t __i = 0; __i < _Nw; __i++) |
1cb7f91f BK |
152 | _M_w[__i] = ~_M_w[__i]; |
153 | } | |
54c1bf78 | 154 | |
b963aad8 PE |
155 | void |
156 | _M_do_set() | |
1cb7f91f BK |
157 | { |
158 | for (size_t __i = 0; __i < _Nw; __i++) | |
159 | _M_w[__i] = ~static_cast<_WordT>(0); | |
160 | } | |
54c1bf78 | 161 | |
b963aad8 | 162 | void |
1cb7f91f BK |
163 | _M_do_reset() { memset(_M_w, 0, _Nw * sizeof(_WordT)); } |
164 | ||
b963aad8 PE |
165 | bool |
166 | _M_is_equal(const _Base_bitset<_Nw>& __x) const | |
1cb7f91f | 167 | { |
b963aad8 | 168 | for (size_t __i = 0; __i < _Nw; ++__i) |
1cb7f91f BK |
169 | { |
170 | if (_M_w[__i] != __x._M_w[__i]) | |
171 | return false; | |
172 | } | |
173 | return true; | |
174 | } | |
54c1bf78 | 175 | |
b963aad8 PE |
176 | bool |
177 | _M_is_any() const | |
1cb7f91f | 178 | { |
b963aad8 | 179 | for (size_t __i = 0; __i < _Nw; __i++) |
1cb7f91f BK |
180 | { |
181 | if (_M_w[__i] != static_cast<_WordT>(0)) | |
182 | return true; | |
183 | } | |
184 | return false; | |
185 | } | |
54c1bf78 | 186 | |
b963aad8 PE |
187 | size_t |
188 | _M_do_count() const | |
1cb7f91f BK |
189 | { |
190 | size_t __result = 0; | |
348b0c31 FH |
191 | for (size_t __i = 0; __i < _Nw; __i++) |
192 | __result += __builtin_popcountl(_M_w[__i]); | |
1cb7f91f BK |
193 | return __result; |
194 | } | |
54c1bf78 | 195 | |
b963aad8 PE |
196 | unsigned long |
197 | _M_do_to_ulong() const; | |
1cb7f91f BK |
198 | |
199 | // find first "on" bit | |
b963aad8 | 200 | size_t |
1cb7f91f BK |
201 | _M_do_find_first(size_t __not_found) const; |
202 | ||
203 | // find the next "on" bit that follows "prev" | |
b963aad8 | 204 | size_t |
1cb7f91f BK |
205 | _M_do_find_next(size_t __prev, size_t __not_found) const; |
206 | }; | |
207 | ||
208 | // Definitions of non-inline functions from _Base_bitset. | |
209 | template<size_t _Nw> | |
b963aad8 PE |
210 | void |
211 | _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) | |
1cb7f91f | 212 | { |
3bbfb3d9 | 213 | if (__builtin_expect(__shift != 0, 1)) |
1cb7f91f | 214 | { |
3d7c150e BK |
215 | const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; |
216 | const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; | |
b963aad8 | 217 | |
1cb7f91f BK |
218 | if (__offset == 0) |
219 | for (size_t __n = _Nw - 1; __n >= __wshift; --__n) | |
220 | _M_w[__n] = _M_w[__n - __wshift]; | |
b963aad8 | 221 | else |
1cb7f91f | 222 | { |
3d7c150e | 223 | const size_t __sub_offset = _GLIBCXX_BITSET_BITS_PER_WORD - __offset; |
1cb7f91f | 224 | for (size_t __n = _Nw - 1; __n > __wshift; --__n) |
b963aad8 | 225 | _M_w[__n] = (_M_w[__n - __wshift] << __offset) | |
1cb7f91f BK |
226 | (_M_w[__n - __wshift - 1] >> __sub_offset); |
227 | _M_w[__wshift] = _M_w[0] << __offset; | |
228 | } | |
b963aad8 | 229 | |
a8cad3e1 | 230 | std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0)); |
1cb7f91f | 231 | } |
54c1bf78 | 232 | } |
b963aad8 | 233 | |
1cb7f91f | 234 | template<size_t _Nw> |
b963aad8 PE |
235 | void |
236 | _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) | |
1cb7f91f | 237 | { |
3bbfb3d9 | 238 | if (__builtin_expect(__shift != 0, 1)) |
1cb7f91f | 239 | { |
3d7c150e BK |
240 | const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; |
241 | const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; | |
1cb7f91f | 242 | const size_t __limit = _Nw - __wshift - 1; |
b963aad8 | 243 | |
1cb7f91f BK |
244 | if (__offset == 0) |
245 | for (size_t __n = 0; __n <= __limit; ++__n) | |
246 | _M_w[__n] = _M_w[__n + __wshift]; | |
b963aad8 | 247 | else |
1cb7f91f | 248 | { |
3d7c150e | 249 | const size_t __sub_offset = _GLIBCXX_BITSET_BITS_PER_WORD - __offset; |
1cb7f91f BK |
250 | for (size_t __n = 0; __n < __limit; ++__n) |
251 | _M_w[__n] = (_M_w[__n + __wshift] >> __offset) | | |
252 | (_M_w[__n + __wshift + 1] << __sub_offset); | |
253 | _M_w[__limit] = _M_w[_Nw-1] >> __offset; | |
254 | } | |
a8cad3e1 PC |
255 | |
256 | std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0)); | |
1cb7f91f | 257 | } |
54c1bf78 | 258 | } |
54c1bf78 | 259 | |
1cb7f91f | 260 | template<size_t _Nw> |
b963aad8 | 261 | unsigned long |
1cb7f91f BK |
262 | _Base_bitset<_Nw>::_M_do_to_ulong() const |
263 | { | |
b963aad8 PE |
264 | for (size_t __i = 1; __i < _Nw; ++__i) |
265 | if (_M_w[__i]) | |
988ad90d | 266 | __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong")); |
1cb7f91f | 267 | return _M_w[0]; |
54c1bf78 | 268 | } |
54c1bf78 | 269 | |
1cb7f91f | 270 | template<size_t _Nw> |
b963aad8 PE |
271 | size_t |
272 | _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const | |
1cb7f91f | 273 | { |
348b0c31 | 274 | for (size_t __i = 0; __i < _Nw; __i++) |
1cb7f91f BK |
275 | { |
276 | _WordT __thisword = _M_w[__i]; | |
348b0c31 | 277 | if (__thisword != static_cast<_WordT>(0)) |
3d7c150e | 278 | return __i * _GLIBCXX_BITSET_BITS_PER_WORD |
348b0c31 | 279 | + __builtin_ctzl(__thisword); |
1cb7f91f BK |
280 | } |
281 | // not found, so return an indication of failure. | |
282 | return __not_found; | |
54c1bf78 BK |
283 | } |
284 | ||
1cb7f91f BK |
285 | template<size_t _Nw> |
286 | size_t | |
287 | _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const | |
b963aad8 | 288 | { |
1cb7f91f BK |
289 | // make bound inclusive |
290 | ++__prev; | |
b963aad8 | 291 | |
1cb7f91f | 292 | // check out of bounds |
3d7c150e | 293 | if ( __prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD ) |
1cb7f91f | 294 | return __not_found; |
b963aad8 | 295 | |
1cb7f91f BK |
296 | // search first word |
297 | size_t __i = _S_whichword(__prev); | |
298 | _WordT __thisword = _M_w[__i]; | |
b963aad8 | 299 | |
1cb7f91f | 300 | // mask off bits below bound |
348b0c31 | 301 | __thisword >>= __prev + 1; |
b963aad8 | 302 | |
348b0c31 | 303 | if (__thisword != static_cast<_WordT>(0)) |
3d7c150e | 304 | return __i * _GLIBCXX_BITSET_BITS_PER_WORD |
348b0c31 | 305 | + __builtin_ctzl(__thisword); |
b963aad8 | 306 | |
1cb7f91f BK |
307 | // check subsequent words |
308 | __i++; | |
b963aad8 | 309 | for ( ; __i < _Nw; __i++ ) |
1cb7f91f BK |
310 | { |
311 | __thisword = _M_w[__i]; | |
348b0c31 | 312 | if (__thisword != static_cast<_WordT>(0)) |
3d7c150e | 313 | return __i * _GLIBCXX_BITSET_BITS_PER_WORD |
348b0c31 | 314 | + __builtin_ctzl(__thisword); |
1cb7f91f BK |
315 | } |
316 | // not found, so return an indication of failure. | |
317 | return __not_found; | |
318 | } // end _M_do_find_next | |
54c1bf78 | 319 | |
b963aad8 PE |
320 | |
321 | /** | |
322 | * @if maint | |
323 | * Base class, specialization for a single word. | |
324 | * | |
325 | * See documentation for bitset. | |
326 | * @endif | |
327 | */ | |
328 | template<> | |
329 | struct _Base_bitset<1> | |
1cb7f91f BK |
330 | { |
331 | typedef unsigned long _WordT; | |
332 | _WordT _M_w; | |
54c1bf78 | 333 | |
1cb7f91f BK |
334 | _Base_bitset( void ) : _M_w(0) {} |
335 | _Base_bitset(unsigned long __val) : _M_w(__val) {} | |
54c1bf78 | 336 | |
b963aad8 | 337 | static size_t |
1cb7f91f | 338 | _S_whichword(size_t __pos ) |
3d7c150e | 339 | { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } |
54c1bf78 | 340 | |
b963aad8 | 341 | static size_t |
1cb7f91f | 342 | _S_whichbyte(size_t __pos ) |
3d7c150e | 343 | { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } |
54c1bf78 | 344 | |
b963aad8 | 345 | static size_t |
1cb7f91f | 346 | _S_whichbit(size_t __pos ) |
3d7c150e | 347 | { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } |
54c1bf78 | 348 | |
b963aad8 | 349 | static _WordT |
1cb7f91f BK |
350 | _S_maskbit(size_t __pos ) |
351 | { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } | |
54c1bf78 | 352 | |
b963aad8 | 353 | _WordT& |
1cb7f91f | 354 | _M_getword(size_t) { return _M_w; } |
54c1bf78 | 355 | |
b963aad8 | 356 | _WordT |
1cb7f91f | 357 | _M_getword(size_t) const { return _M_w; } |
54c1bf78 | 358 | |
b963aad8 | 359 | _WordT& |
1cb7f91f | 360 | _M_hiword() { return _M_w; } |
54c1bf78 | 361 | |
b963aad8 | 362 | _WordT |
1cb7f91f | 363 | _M_hiword() const { return _M_w; } |
54c1bf78 | 364 | |
b963aad8 | 365 | void |
1cb7f91f | 366 | _M_do_and(const _Base_bitset<1>& __x) { _M_w &= __x._M_w; } |
54c1bf78 | 367 | |
b963aad8 | 368 | void |
1cb7f91f | 369 | _M_do_or(const _Base_bitset<1>& __x) { _M_w |= __x._M_w; } |
54c1bf78 | 370 | |
b963aad8 | 371 | void |
1cb7f91f | 372 | _M_do_xor(const _Base_bitset<1>& __x) { _M_w ^= __x._M_w; } |
54c1bf78 | 373 | |
b963aad8 | 374 | void |
1cb7f91f | 375 | _M_do_left_shift(size_t __shift) { _M_w <<= __shift; } |
54c1bf78 | 376 | |
b963aad8 | 377 | void |
1cb7f91f | 378 | _M_do_right_shift(size_t __shift) { _M_w >>= __shift; } |
54c1bf78 | 379 | |
b963aad8 | 380 | void |
1cb7f91f | 381 | _M_do_flip() { _M_w = ~_M_w; } |
54c1bf78 | 382 | |
b963aad8 | 383 | void |
1cb7f91f | 384 | _M_do_set() { _M_w = ~static_cast<_WordT>(0); } |
54c1bf78 | 385 | |
b963aad8 | 386 | void |
1cb7f91f | 387 | _M_do_reset() { _M_w = 0; } |
54c1bf78 | 388 | |
b963aad8 | 389 | bool |
1cb7f91f BK |
390 | _M_is_equal(const _Base_bitset<1>& __x) const |
391 | { return _M_w == __x._M_w; } | |
54c1bf78 | 392 | |
b963aad8 | 393 | bool |
1cb7f91f | 394 | _M_is_any() const { return _M_w != 0; } |
54c1bf78 | 395 | |
b963aad8 | 396 | size_t |
348b0c31 | 397 | _M_do_count() const { return __builtin_popcountl(_M_w); } |
54c1bf78 | 398 | |
b963aad8 | 399 | unsigned long |
1cb7f91f BK |
400 | _M_do_to_ulong() const { return _M_w; } |
401 | ||
b963aad8 | 402 | size_t |
348b0c31 FH |
403 | _M_do_find_first(size_t __not_found) const |
404 | { | |
405 | if (_M_w != 0) | |
406 | return __builtin_ctzl(_M_w); | |
407 | else | |
408 | return __not_found; | |
409 | } | |
1cb7f91f BK |
410 | |
411 | // find the next "on" bit that follows "prev" | |
412 | size_t | |
348b0c31 FH |
413 | _M_do_find_next(size_t __prev, size_t __not_found) const |
414 | { | |
415 | ++__prev; | |
3d7c150e | 416 | if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD)) |
348b0c31 FH |
417 | return __not_found; |
418 | ||
419 | _WordT __x = _M_w >> __prev; | |
420 | if (__x != 0) | |
421 | return __builtin_ctzl(__x) + __prev; | |
422 | else | |
423 | return __not_found; | |
424 | } | |
1cb7f91f BK |
425 | }; |
426 | ||
bb12c809 PE |
427 | |
428 | /** | |
429 | * @if maint | |
430 | * Base class, specialization for no storage (zero-length %bitset). | |
431 | * | |
432 | * See documentation for bitset. | |
433 | * @endif | |
434 | */ | |
435 | template<> | |
436 | struct _Base_bitset<0> | |
437 | { | |
438 | typedef unsigned long _WordT; | |
439 | ||
440 | _Base_bitset() {} | |
441 | _Base_bitset(unsigned long) {} | |
442 | ||
443 | static size_t | |
444 | _S_whichword(size_t __pos ) | |
3d7c150e | 445 | { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } |
bb12c809 PE |
446 | |
447 | static size_t | |
448 | _S_whichbyte(size_t __pos ) | |
3d7c150e | 449 | { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } |
bb12c809 PE |
450 | |
451 | static size_t | |
452 | _S_whichbit(size_t __pos ) | |
3d7c150e | 453 | { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } |
bb12c809 PE |
454 | |
455 | static _WordT | |
456 | _S_maskbit(size_t __pos ) | |
457 | { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } | |
458 | ||
459 | // This would normally give access to the data. The bounds-checking | |
460 | // in the bitset class will prevent the user from getting this far, | |
461 | // but (1) it must still return an lvalue to compile, and (2) the | |
462 | // user might call _Unchecked_set directly, in which case this /needs/ | |
463 | // to fail. Let's not penalize zero-length users unless they actually | |
464 | // make an unchecked call; all the memory ugliness is therefore | |
465 | // localized to this single should-never-get-this-far function. | |
466 | _WordT& | |
467 | _M_getword(size_t) const | |
988ad90d BK |
468 | { |
469 | __throw_out_of_range(__N("_Base_bitset::_M_getword")); | |
470 | return *new _WordT; | |
471 | } | |
bb12c809 PE |
472 | |
473 | _WordT | |
474 | _M_hiword() const { return 0; } | |
475 | ||
476 | void | |
477 | _M_do_and(const _Base_bitset<0>&) { } | |
478 | ||
479 | void | |
480 | _M_do_or(const _Base_bitset<0>&) { } | |
481 | ||
482 | void | |
483 | _M_do_xor(const _Base_bitset<0>&) { } | |
484 | ||
485 | void | |
486 | _M_do_left_shift(size_t) { } | |
487 | ||
488 | void | |
489 | _M_do_right_shift(size_t) { } | |
490 | ||
491 | void | |
492 | _M_do_flip() { } | |
493 | ||
494 | void | |
495 | _M_do_set() { } | |
496 | ||
497 | void | |
498 | _M_do_reset() { } | |
499 | ||
500 | // Are all empty bitsets equal to each other? Are they equal to | |
501 | // themselves? How to compare a thing which has no state? What is | |
502 | // the sound of one zero-length bitset clapping? | |
503 | bool | |
504 | _M_is_equal(const _Base_bitset<0>&) const { return true; } | |
505 | ||
506 | bool | |
507 | _M_is_any() const { return false; } | |
508 | ||
509 | size_t | |
510 | _M_do_count() const { return 0; } | |
511 | ||
512 | unsigned long | |
513 | _M_do_to_ulong() const { return 0; } | |
514 | ||
515 | // Normally "not found" is the size, but that could also be | |
516 | // misinterpreted as an index in this corner case. Oh well. | |
517 | size_t | |
518 | _M_do_find_first(size_t) const { return 0; } | |
519 | ||
520 | size_t | |
521 | _M_do_find_next(size_t, size_t) const { return 0; } | |
522 | }; | |
523 | ||
524 | ||
1cb7f91f | 525 | // Helper class to zero out the unused high-order bits in the highest word. |
b963aad8 PE |
526 | template<size_t _Extrabits> |
527 | struct _Sanitize | |
1cb7f91f BK |
528 | { |
529 | static void _S_do_sanitize(unsigned long& __val) | |
530 | { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); } | |
531 | }; | |
532 | ||
b963aad8 PE |
533 | template<> |
534 | struct _Sanitize<0> | |
1cb7f91f BK |
535 | { static void _S_do_sanitize(unsigned long) { } }; |
536 | ||
70e12fb9 | 537 | |
b963aad8 PE |
538 | /** |
539 | * @brief The %bitset class represents a @e fixed-size sequence of bits. | |
540 | * | |
541 | * @ingroup Containers | |
542 | * | |
e92a4045 PE |
543 | * (Note that %bitset does @e not meet the formal requirements of a |
544 | * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.) | |
b963aad8 | 545 | * |
70e12fb9 PE |
546 | * The template argument, @a Nb, may be any non-negative number, |
547 | * specifying the number of bits (e.g., "0", "12", "1024*1024"). | |
b963aad8 | 548 | * |
70e12fb9 PE |
549 | * In the general unoptimized case, storage is allocated in word-sized |
550 | * blocks. Let B be the number of bits in a word, then (Nb+(B-1))/B | |
551 | * words will be used for storage. B - Nb%B bits are unused. (They are | |
552 | * the high-order bits in the highest word.) It is a class invariant | |
553 | * that those unused bits are always zero. | |
b963aad8 PE |
554 | * |
555 | * If you think of %bitset as "a simple array of bits," be aware that | |
556 | * your mental picture is reversed: a %bitset behaves the same way as | |
557 | * bits in integers do, with the bit at index 0 in the "least significant | |
70e12fb9 | 558 | * / right-hand" position, and the bit at index Nb-1 in the "most |
b963aad8 PE |
559 | * significant / left-hand" position. Thus, unlike other containers, a |
560 | * %bitset's index "counts from right to left," to put it very loosely. | |
561 | * | |
562 | * This behavior is preserved when translating to and from strings. For | |
563 | * example, the first line of the following program probably prints | |
564 | * "b('a') is 0001100001" on a modern ASCII system. | |
565 | * | |
566 | * @code | |
567 | * #include <bitset> | |
568 | * #include <iostream> | |
569 | * #include <sstream> | |
570 | * | |
571 | * using namespace std; | |
572 | * | |
573 | * int main() | |
574 | * { | |
575 | * long a = 'a'; | |
576 | * bitset<10> b(a); | |
577 | * | |
578 | * cout << "b('a') is " << b << endl; | |
579 | * | |
580 | * ostringstream s; | |
581 | * s << b; | |
582 | * string str = s.str(); | |
583 | * cout << "index 3 in the string is " << str[3] << " but\n" | |
584 | * << "index 3 in the bitset is " << b[3] << endl; | |
585 | * } | |
586 | * @endcode | |
587 | * | |
588 | * Also see http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23 | |
70e12fb9 | 589 | * for a description of extensions. |
b963aad8 PE |
590 | * |
591 | * @if maint | |
592 | * Most of the actual code isn't contained in %bitset<> itself, but in the | |
593 | * base class _Base_bitset. The base class works with whole words, not with | |
594 | * individual bits. This allows us to specialize _Base_bitset for the | |
595 | * important special case where the %bitset is only a single word. | |
596 | * | |
597 | * Extra confusion can result due to the fact that the storage for | |
598 | * _Base_bitset @e is a regular array, and is indexed as such. This is | |
599 | * carefully encapsulated. | |
600 | * @endif | |
601 | */ | |
1cb7f91f | 602 | template<size_t _Nb> |
3d7c150e | 603 | class bitset : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> |
1cb7f91f BK |
604 | { |
605 | private: | |
3d7c150e | 606 | typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base; |
1cb7f91f | 607 | typedef unsigned long _WordT; |
b963aad8 PE |
608 | |
609 | void | |
610 | _M_do_sanitize() | |
1cb7f91f | 611 | { |
3d7c150e | 612 | _Sanitize<_Nb%_GLIBCXX_BITSET_BITS_PER_WORD>:: |
b963aad8 | 613 | _S_do_sanitize(this->_M_hiword()); |
1cb7f91f | 614 | } |
54c1bf78 | 615 | |
1cb7f91f | 616 | public: |
b963aad8 PE |
617 | /** |
618 | * This encapsulates the concept of a single bit. An instance of this | |
619 | * class is a proxy for an actual bit; this way the individual bit | |
620 | * operations are done as faster word-size bitwise instructions. | |
621 | * | |
622 | * Most users will never need to use this class directly; conversions | |
623 | * to and from bool are automatic and should be transparent. Overloaded | |
624 | * operators help to preserve the illusion. | |
625 | * | |
626 | * (On a typical system, this "bit %reference" is 64 times the size of | |
627 | * an actual bit. Ha.) | |
628 | */ | |
629 | class reference | |
1cb7f91f BK |
630 | { |
631 | friend class bitset; | |
b963aad8 | 632 | |
1cb7f91f BK |
633 | _WordT *_M_wp; |
634 | size_t _M_bpos; | |
b963aad8 | 635 | |
1cb7f91f BK |
636 | // left undefined |
637 | reference(); | |
b963aad8 | 638 | |
1cb7f91f | 639 | public: |
b963aad8 | 640 | reference(bitset& __b, size_t __pos) |
1cb7f91f BK |
641 | { |
642 | _M_wp = &__b._M_getword(__pos); | |
643 | _M_bpos = _Base::_S_whichbit(__pos); | |
644 | } | |
54c1bf78 | 645 | |
1cb7f91f BK |
646 | ~reference() { } |
647 | ||
285b36d6 | 648 | // For b[i] = __x; |
b963aad8 PE |
649 | reference& |
650 | operator=(bool __x) | |
1cb7f91f BK |
651 | { |
652 | if ( __x ) | |
653 | *_M_wp |= _Base::_S_maskbit(_M_bpos); | |
654 | else | |
655 | *_M_wp &= ~_Base::_S_maskbit(_M_bpos); | |
656 | return *this; | |
657 | } | |
b963aad8 | 658 | |
285b36d6 | 659 | // For b[i] = b[__j]; |
b963aad8 PE |
660 | reference& |
661 | operator=(const reference& __j) | |
1cb7f91f BK |
662 | { |
663 | if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) ) | |
664 | *_M_wp |= _Base::_S_maskbit(_M_bpos); | |
665 | else | |
666 | *_M_wp &= ~_Base::_S_maskbit(_M_bpos); | |
667 | return *this; | |
668 | } | |
54c1bf78 | 669 | |
285b36d6 | 670 | // Flips the bit |
b963aad8 | 671 | bool |
1cb7f91f BK |
672 | operator~() const |
673 | { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } | |
54c1bf78 | 674 | |
285b36d6 | 675 | // For __x = b[i]; |
1cb7f91f BK |
676 | operator bool() const |
677 | { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } | |
54c1bf78 | 678 | |
285b36d6 | 679 | // For b[i].flip(); |
b963aad8 PE |
680 | reference& |
681 | flip() | |
1cb7f91f BK |
682 | { |
683 | *_M_wp ^= _Base::_S_maskbit(_M_bpos); | |
684 | return *this; | |
685 | } | |
686 | }; | |
b963aad8 PE |
687 | friend class reference; |
688 | ||
1cb7f91f | 689 | // 23.3.5.1 constructors: |
b963aad8 | 690 | /// All bits set to zero. |
1cb7f91f | 691 | bitset() { } |
54c1bf78 | 692 | |
b963aad8 PE |
693 | /// Initial bits bitwise-copied from a single word (others set to zero). |
694 | bitset(unsigned long __val) : _Base(__val) | |
1cb7f91f | 695 | { _M_do_sanitize(); } |
54c1bf78 | 696 | |
b963aad8 PE |
697 | /** |
698 | * @brief Use a subset of a string. | |
699 | * @param s A string of '0' and '1' characters. | |
08addde6 | 700 | * @param position Index of the first character in @a s to use; defaults |
b963aad8 PE |
701 | * to zero. |
702 | * @throw std::out_of_range If @a pos is bigger the size of @a s. | |
703 | * @throw std::invalid_argument If a character appears in the string | |
704 | * which is neither '0' nor '1'. | |
705 | */ | |
1cb7f91f BK |
706 | template<class _CharT, class _Traits, class _Alloc> |
707 | explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, | |
08addde6 | 708 | size_t __position = 0) : _Base() |
1cb7f91f | 709 | { |
08addde6 | 710 | if (__position > __s.size()) |
ba9119ec PC |
711 | __throw_out_of_range(__N("bitset::bitset initial position " |
712 | "not valid")); | |
08addde6 | 713 | _M_copy_from_string(__s, __position, |
1cb7f91f BK |
714 | basic_string<_CharT, _Traits, _Alloc>::npos); |
715 | } | |
54c1bf78 | 716 | |
b963aad8 PE |
717 | /** |
718 | * @brief Use a subset of a string. | |
719 | * @param s A string of '0' and '1' characters. | |
08addde6 | 720 | * @param position Index of the first character in @a s to use. |
b963aad8 PE |
721 | * @param n The number of characters to copy. |
722 | * @throw std::out_of_range If @a pos is bigger the size of @a s. | |
723 | * @throw std::invalid_argument If a character appears in the string | |
724 | * which is neither '0' nor '1'. | |
725 | */ | |
1cb7f91f BK |
726 | template<class _CharT, class _Traits, class _Alloc> |
727 | bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, | |
08addde6 | 728 | size_t __position, size_t __n) : _Base() |
1cb7f91f | 729 | { |
08addde6 | 730 | if (__position > __s.size()) |
ba9119ec PC |
731 | __throw_out_of_range(__N("bitset::bitset initial position " |
732 | "not valid")); | |
08addde6 | 733 | _M_copy_from_string(__s, __position, __n); |
1cb7f91f | 734 | } |
54c1bf78 | 735 | |
1cb7f91f | 736 | // 23.3.5.2 bitset operations: |
b963aad8 PE |
737 | //@{ |
738 | /** | |
739 | * @brief Operations on bitsets. | |
740 | * @param rhs A same-sized bitset. | |
741 | * | |
742 | * These should be self-explanatory. | |
743 | */ | |
744 | bitset<_Nb>& | |
745 | operator&=(const bitset<_Nb>& __rhs) | |
1cb7f91f BK |
746 | { |
747 | this->_M_do_and(__rhs); | |
54c1bf78 BK |
748 | return *this; |
749 | } | |
750 | ||
b963aad8 PE |
751 | bitset<_Nb>& |
752 | operator|=(const bitset<_Nb>& __rhs) | |
1cb7f91f BK |
753 | { |
754 | this->_M_do_or(__rhs); | |
54c1bf78 BK |
755 | return *this; |
756 | } | |
757 | ||
b963aad8 PE |
758 | bitset<_Nb>& |
759 | operator^=(const bitset<_Nb>& __rhs) | |
1cb7f91f BK |
760 | { |
761 | this->_M_do_xor(__rhs); | |
762 | return *this; | |
763 | } | |
b963aad8 PE |
764 | //@} |
765 | ||
766 | //@{ | |
767 | /** | |
768 | * @brief Operations on bitsets. | |
08addde6 | 769 | * @param position The number of places to shift. |
b963aad8 PE |
770 | * |
771 | * These should be self-explanatory. | |
772 | */ | |
773 | bitset<_Nb>& | |
08addde6 | 774 | operator<<=(size_t __position) |
1cb7f91f | 775 | { |
08addde6 | 776 | if (__builtin_expect(__position < _Nb, 1)) |
3bbfb3d9 | 777 | { |
08addde6 | 778 | this->_M_do_left_shift(__position); |
3bbfb3d9 PE |
779 | this->_M_do_sanitize(); |
780 | } | |
781 | else | |
782 | this->_M_do_reset(); | |
54c1bf78 BK |
783 | return *this; |
784 | } | |
54c1bf78 | 785 | |
b963aad8 | 786 | bitset<_Nb>& |
08addde6 | 787 | operator>>=(size_t __position) |
1cb7f91f | 788 | { |
08addde6 | 789 | if (__builtin_expect(__position < _Nb, 1)) |
3bbfb3d9 | 790 | { |
08addde6 | 791 | this->_M_do_right_shift(__position); |
3bbfb3d9 PE |
792 | this->_M_do_sanitize(); |
793 | } | |
794 | else | |
795 | this->_M_do_reset(); | |
1cb7f91f BK |
796 | return *this; |
797 | } | |
b963aad8 PE |
798 | //@} |
799 | ||
800 | //@{ | |
801 | /** | |
802 | * These versions of single-bit set, reset, flip, and test are | |
803 | * extensions from the SGI version. They do no range checking. | |
804 | * @ingroup SGIextensions | |
805 | */ | |
806 | bitset<_Nb>& | |
807 | _Unchecked_set(size_t __pos) | |
1cb7f91f | 808 | { |
54c1bf78 | 809 | this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); |
1cb7f91f BK |
810 | return *this; |
811 | } | |
54c1bf78 | 812 | |
b963aad8 PE |
813 | bitset<_Nb>& |
814 | _Unchecked_set(size_t __pos, int __val) | |
1cb7f91f BK |
815 | { |
816 | if (__val) | |
817 | this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); | |
818 | else | |
819 | this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); | |
820 | return *this; | |
821 | } | |
54c1bf78 | 822 | |
b963aad8 PE |
823 | bitset<_Nb>& |
824 | _Unchecked_reset(size_t __pos) | |
1cb7f91f BK |
825 | { |
826 | this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); | |
827 | return *this; | |
828 | } | |
54c1bf78 | 829 | |
b963aad8 PE |
830 | bitset<_Nb>& |
831 | _Unchecked_flip(size_t __pos) | |
1cb7f91f BK |
832 | { |
833 | this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); | |
834 | return *this; | |
835 | } | |
54c1bf78 | 836 | |
b963aad8 PE |
837 | bool |
838 | _Unchecked_test(size_t __pos) const | |
1cb7f91f | 839 | { |
b963aad8 | 840 | return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) |
1cb7f91f BK |
841 | != static_cast<_WordT>(0); |
842 | } | |
b963aad8 | 843 | //@} |
54c1bf78 | 844 | |
1cb7f91f | 845 | // Set, reset, and flip. |
b963aad8 PE |
846 | /** |
847 | * @brief Sets every bit to true. | |
848 | */ | |
849 | bitset<_Nb>& | |
850 | set() | |
1cb7f91f BK |
851 | { |
852 | this->_M_do_set(); | |
853 | this->_M_do_sanitize(); | |
854 | return *this; | |
855 | } | |
54c1bf78 | 856 | |
b963aad8 PE |
857 | /** |
858 | * @brief Sets a given bit to a particular value. | |
08addde6 | 859 | * @param position The index of the bit. |
b963aad8 PE |
860 | * @param val Either true or false, defaults to true. |
861 | * @throw std::out_of_range If @a pos is bigger the size of the %set. | |
862 | */ | |
863 | bitset<_Nb>& | |
08addde6 | 864 | set(size_t __position, bool __val = true) |
1cb7f91f | 865 | { |
08addde6 | 866 | if (__position >= _Nb) |
988ad90d | 867 | __throw_out_of_range(__N("bitset::set")); |
08addde6 | 868 | return _Unchecked_set(__position, __val); |
1cb7f91f | 869 | } |
54c1bf78 | 870 | |
b963aad8 PE |
871 | /** |
872 | * @brief Sets every bit to false. | |
873 | */ | |
874 | bitset<_Nb>& | |
875 | reset() | |
1cb7f91f BK |
876 | { |
877 | this->_M_do_reset(); | |
878 | return *this; | |
879 | } | |
54c1bf78 | 880 | |
b963aad8 PE |
881 | /** |
882 | * @brief Sets a given bit to false. | |
08addde6 | 883 | * @param position The index of the bit. |
b963aad8 PE |
884 | * @throw std::out_of_range If @a pos is bigger the size of the %set. |
885 | * | |
886 | * Same as writing @c set(pos,false). | |
887 | */ | |
888 | bitset<_Nb>& | |
08addde6 | 889 | reset(size_t __position) |
1cb7f91f | 890 | { |
08addde6 | 891 | if (__position >= _Nb) |
988ad90d | 892 | __throw_out_of_range(__N("bitset::reset")); |
08addde6 | 893 | return _Unchecked_reset(__position); |
1cb7f91f | 894 | } |
54c1bf78 | 895 | |
b963aad8 PE |
896 | /** |
897 | * @brief Toggles every bit to its opposite value. | |
898 | */ | |
899 | bitset<_Nb>& | |
900 | flip() | |
1cb7f91f BK |
901 | { |
902 | this->_M_do_flip(); | |
903 | this->_M_do_sanitize(); | |
904 | return *this; | |
905 | } | |
54c1bf78 | 906 | |
b963aad8 PE |
907 | /** |
908 | * @brief Toggles a given bit to its opposite value. | |
08addde6 | 909 | * @param position The index of the bit. |
b963aad8 PE |
910 | * @throw std::out_of_range If @a pos is bigger the size of the %set. |
911 | */ | |
912 | bitset<_Nb>& | |
08addde6 | 913 | flip(size_t __position) |
1cb7f91f | 914 | { |
08addde6 | 915 | if (__position >= _Nb) |
988ad90d | 916 | __throw_out_of_range(__N("bitset::flip")); |
08addde6 | 917 | return _Unchecked_flip(__position); |
1cb7f91f | 918 | } |
54c1bf78 | 919 | |
b963aad8 PE |
920 | /// See the no-argument flip(). |
921 | bitset<_Nb> | |
1cb7f91f BK |
922 | operator~() const { return bitset<_Nb>(*this).flip(); } |
923 | ||
b963aad8 PE |
924 | //@{ |
925 | /** | |
926 | * @brief Array-indexing support. | |
08addde6 | 927 | * @param position Index into the %bitset. |
b963aad8 PE |
928 | * @return A bool for a 'const %bitset'. For non-const bitsets, an |
929 | * instance of the reference proxy class. | |
930 | * @note These operators do no range checking and throw no exceptions, | |
931 | * as required by DR 11 to the standard. | |
932 | * | |
933 | * @if maint | |
3d7c150e | 934 | * _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already |
b963aad8 PE |
935 | * resolves DR 11 (items 1 and 2), but does not do the range-checking |
936 | * required by that DR's resolution. -pme | |
937 | * The DR has since been changed: range-checking is a precondition | |
938 | * (users' responsibility), and these functions must not throw. -pme | |
939 | * @endif | |
940 | */ | |
941 | reference | |
08addde6 | 942 | operator[](size_t __position) { return reference(*this,__position); } |
1cb7f91f | 943 | |
b963aad8 | 944 | bool |
08addde6 | 945 | operator[](size_t __position) const { return _Unchecked_test(__position); } |
b963aad8 PE |
946 | //@} |
947 | ||
948 | /** | |
949 | * @brief Retuns a numerical interpretation of the %bitset. | |
950 | * @return The integral equivalent of the bits. | |
951 | * @throw std::overflow_error If there are too many bits to be | |
952 | * represented in an @c unsigned @c long. | |
953 | */ | |
954 | unsigned long | |
1cb7f91f BK |
955 | to_ulong() const { return this->_M_do_to_ulong(); } |
956 | ||
b963aad8 PE |
957 | /** |
958 | * @brief Retuns a character interpretation of the %bitset. | |
959 | * @return The string equivalent of the bits. | |
960 | * | |
961 | * Note the ordering of the bits: decreasing character positions | |
962 | * correspond to increasing bit positions (see the main class notes for | |
963 | * an example). | |
964 | * | |
965 | * Also note that you must specify the string's template parameters | |
966 | * explicitly. Given a bitset @c bs and a string @s: | |
967 | * @code | |
968 | * s = bs.to_string<char,char_traits<char>,allocator<char> >(); | |
969 | * @endcode | |
970 | */ | |
1cb7f91f | 971 | template<class _CharT, class _Traits, class _Alloc> |
b963aad8 PE |
972 | basic_string<_CharT, _Traits, _Alloc> |
973 | to_string() const | |
1cb7f91f BK |
974 | { |
975 | basic_string<_CharT, _Traits, _Alloc> __result; | |
976 | _M_copy_to_string(__result); | |
977 | return __result; | |
978 | } | |
54c1bf78 | 979 | |
1cb7f91f BK |
980 | // Helper functions for string operations. |
981 | template<class _CharT, class _Traits, class _Alloc> | |
b963aad8 | 982 | void |
1cb7f91f BK |
983 | _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, |
984 | size_t, size_t); | |
54c1bf78 | 985 | |
1cb7f91f | 986 | template<class _CharT, class _Traits, class _Alloc> |
b963aad8 | 987 | void |
1cb7f91f | 988 | _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const; |
54c1bf78 | 989 | |
b963aad8 PE |
990 | /// Returns the number of bits which are set. |
991 | size_t | |
1cb7f91f | 992 | count() const { return this->_M_do_count(); } |
54c1bf78 | 993 | |
b963aad8 PE |
994 | /// Returns the total number of bits. |
995 | size_t | |
1cb7f91f | 996 | size() const { return _Nb; } |
54c1bf78 | 997 | |
b963aad8 PE |
998 | //@{ |
999 | /// These comparisons for equality/inequality are, well, @e bitwise. | |
1000 | bool | |
1001 | operator==(const bitset<_Nb>& __rhs) const | |
1cb7f91f | 1002 | { return this->_M_is_equal(__rhs); } |
54c1bf78 | 1003 | |
b963aad8 PE |
1004 | bool |
1005 | operator!=(const bitset<_Nb>& __rhs) const | |
1cb7f91f | 1006 | { return !this->_M_is_equal(__rhs); } |
b963aad8 PE |
1007 | //@} |
1008 | ||
1009 | /** | |
1010 | * @brief Tests the value of a bit. | |
08addde6 | 1011 | * @param position The index of a bit. |
b963aad8 PE |
1012 | * @return The value at @a pos. |
1013 | * @throw std::out_of_range If @a pos is bigger the size of the %set. | |
1014 | */ | |
1015 | bool | |
08addde6 | 1016 | test(size_t __position) const |
1cb7f91f | 1017 | { |
08addde6 | 1018 | if (__position >= _Nb) |
988ad90d | 1019 | __throw_out_of_range(__N("bitset::test")); |
08addde6 | 1020 | return _Unchecked_test(__position); |
1cb7f91f | 1021 | } |
54c1bf78 | 1022 | |
b963aad8 PE |
1023 | /** |
1024 | * @brief Tests whether any of the bits are on. | |
1025 | * @return True if at least one bit is set. | |
1026 | */ | |
1027 | bool | |
1cb7f91f | 1028 | any() const { return this->_M_is_any(); } |
54c1bf78 | 1029 | |
b963aad8 PE |
1030 | /** |
1031 | * @brief Tests whether any of the bits are on. | |
1032 | * @return True if none of the bits are set. | |
1033 | */ | |
1034 | bool | |
1cb7f91f | 1035 | none() const { return !this->_M_is_any(); } |
54c1bf78 | 1036 | |
b963aad8 PE |
1037 | //@{ |
1038 | /// Self-explanatory. | |
1039 | bitset<_Nb> | |
08addde6 PE |
1040 | operator<<(size_t __position) const |
1041 | { return bitset<_Nb>(*this) <<= __position; } | |
1cb7f91f | 1042 | |
b963aad8 | 1043 | bitset<_Nb> |
08addde6 PE |
1044 | operator>>(size_t __position) const |
1045 | { return bitset<_Nb>(*this) >>= __position; } | |
b963aad8 | 1046 | //@} |
54c1bf78 | 1047 | |
b963aad8 PE |
1048 | /** |
1049 | * @brief Finds the index of the first "on" bit. | |
e92a4045 | 1050 | * @return The index of the first bit set, or size() if not found. |
b963aad8 PE |
1051 | * @ingroup SGIextensions |
1052 | * @sa _Find_next | |
1053 | */ | |
1054 | size_t | |
1055 | _Find_first() const | |
54c1bf78 BK |
1056 | { return this->_M_do_find_first(_Nb); } |
1057 | ||
b963aad8 PE |
1058 | /** |
1059 | * @brief Finds the index of the next "on" bit after prev. | |
e92a4045 | 1060 | * @return The index of the next bit set, or size() if not found. |
b963aad8 PE |
1061 | * @param prev Where to start searching. |
1062 | * @ingroup SGIextensions | |
1063 | * @sa _Find_first | |
1064 | */ | |
1065 | size_t | |
1066 | _Find_next(size_t __prev ) const | |
54c1bf78 | 1067 | { return this->_M_do_find_next(__prev, _Nb); } |
1cb7f91f | 1068 | }; |
54c1bf78 | 1069 | |
1cb7f91f BK |
1070 | // Definitions of non-inline member functions. |
1071 | template<size_t _Nb> | |
1072 | template<class _CharT, class _Traits, class _Alloc> | |
b963aad8 | 1073 | void |
ba9119ec PC |
1074 | bitset<_Nb>::_M_copy_from_string(const basic_string<_CharT, _Traits, |
1075 | _Alloc>& __s, size_t __pos, size_t __n) | |
b963aad8 | 1076 | { |
1cb7f91f | 1077 | reset(); |
4977bab6 | 1078 | const size_t __nbits = std::min(_Nb, std::min(__n, __s.size() - __pos)); |
b963aad8 | 1079 | for (size_t __i = 0; __i < __nbits; ++__i) |
1cb7f91f | 1080 | { |
b963aad8 | 1081 | switch(__s[__pos + __nbits - __i - 1]) |
1cb7f91f BK |
1082 | { |
1083 | case '0': | |
1084 | break; | |
1085 | case '1': | |
1086 | set(__i); | |
1087 | break; | |
1088 | default: | |
ba9119ec | 1089 | __throw_invalid_argument(__N("bitset::_M_copy_from_string")); |
1cb7f91f BK |
1090 | } |
1091 | } | |
54c1bf78 | 1092 | } |
54c1bf78 | 1093 | |
1cb7f91f BK |
1094 | template<size_t _Nb> |
1095 | template<class _CharT, class _Traits, class _Alloc> | |
b963aad8 | 1096 | void |
ba9119ec PC |
1097 | bitset<_Nb>::_M_copy_to_string(basic_string<_CharT, _Traits, |
1098 | _Alloc>& __s) const | |
1cb7f91f BK |
1099 | { |
1100 | __s.assign(_Nb, '0'); | |
b963aad8 | 1101 | for (size_t __i = 0; __i < _Nb; ++__i) |
1cb7f91f BK |
1102 | if (_Unchecked_test(__i)) |
1103 | __s[_Nb - 1 - __i] = '1'; | |
1104 | } | |
54c1bf78 | 1105 | |
1cb7f91f | 1106 | // 23.3.5.3 bitset operations: |
b963aad8 PE |
1107 | //@{ |
1108 | /** | |
1109 | * @brief Global bitwise operations on bitsets. | |
1110 | * @param x A bitset. | |
1111 | * @param y A bitset of the same size as @a x. | |
1112 | * @return A new bitset. | |
1113 | * | |
1114 | * These should be self-explanatory. | |
1115 | */ | |
1cb7f91f | 1116 | template<size_t _Nb> |
b963aad8 PE |
1117 | inline bitset<_Nb> |
1118 | operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) | |
1cb7f91f BK |
1119 | { |
1120 | bitset<_Nb> __result(__x); | |
1121 | __result &= __y; | |
1122 | return __result; | |
54c1bf78 BK |
1123 | } |
1124 | ||
1cb7f91f | 1125 | template<size_t _Nb> |
b963aad8 PE |
1126 | inline bitset<_Nb> |
1127 | operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) | |
1cb7f91f BK |
1128 | { |
1129 | bitset<_Nb> __result(__x); | |
1130 | __result |= __y; | |
1131 | return __result; | |
1132 | } | |
54c1bf78 | 1133 | |
1cb7f91f | 1134 | template <size_t _Nb> |
b963aad8 PE |
1135 | inline bitset<_Nb> |
1136 | operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) | |
1cb7f91f BK |
1137 | { |
1138 | bitset<_Nb> __result(__x); | |
1139 | __result ^= __y; | |
1140 | return __result; | |
1141 | } | |
b963aad8 PE |
1142 | //@} |
1143 | ||
1144 | //@{ | |
1145 | /** | |
1146 | * @brief Global I/O operators for bitsets. | |
1147 | * | |
1148 | * Direct I/O between streams and bitsets is supported. Output is | |
1149 | * straightforward. Input will skip whitespace, only accept '0' and '1' | |
1150 | * characters, and will only extract as many digits as the %bitset will | |
1151 | * hold. | |
1152 | */ | |
1cb7f91f BK |
1153 | template<class _CharT, class _Traits, size_t _Nb> |
1154 | basic_istream<_CharT, _Traits>& | |
1155 | operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) | |
1156 | { | |
1157 | typedef typename _Traits::char_type char_type; | |
1158 | basic_string<_CharT, _Traits> __tmp; | |
1159 | __tmp.reserve(_Nb); | |
b963aad8 | 1160 | |
7f1156ed | 1161 | ios_base::iostate __state = ios_base::goodbit; |
1cb7f91f | 1162 | typename basic_istream<_CharT, _Traits>::sentry __sentry(__is); |
b963aad8 | 1163 | if (__sentry) |
1cb7f91f | 1164 | { |
7f1156ed | 1165 | try |
1cb7f91f | 1166 | { |
7f1156ed PC |
1167 | basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf(); |
1168 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
1169 | // 303. Bitset input operator underspecified | |
1170 | const char_type __zero = __is.widen('0'); | |
1171 | const char_type __one = __is.widen('1'); | |
1172 | for (size_t __i = 0; __i < _Nb; ++__i) | |
1cb7f91f | 1173 | { |
7f1156ed PC |
1174 | static typename _Traits::int_type __eof = _Traits::eof(); |
1175 | ||
1176 | typename _Traits::int_type __c1 = __buf->sbumpc(); | |
1177 | if (_Traits::eq_int_type(__c1, __eof)) | |
1cb7f91f | 1178 | { |
7f1156ed | 1179 | __state |= ios_base::eofbit; |
1cb7f91f BK |
1180 | break; |
1181 | } | |
7f1156ed PC |
1182 | else |
1183 | { | |
1184 | char_type __c2 = _Traits::to_char_type(__c1); | |
1185 | if (__c2 == __zero) | |
1186 | __tmp.push_back('0'); | |
1187 | else if (__c2 == __one) | |
1188 | __tmp.push_back('1'); | |
1189 | else if (_Traits::eq_int_type(__buf->sputbackc(__c2), | |
1190 | __eof)) | |
1191 | { | |
1192 | __state |= ios_base::failbit; | |
1193 | break; | |
1194 | } | |
1195 | } | |
1cb7f91f BK |
1196 | } |
1197 | } | |
7f1156ed PC |
1198 | catch(...) |
1199 | { __is._M_setstate(ios_base::badbit); } | |
1cb7f91f BK |
1200 | } |
1201 | ||
7f1156ed PC |
1202 | if (__tmp.empty() && _Nb) |
1203 | __state |= ios_base::failbit; | |
1204 | else | |
1205 | __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb); | |
1206 | if (__state) | |
1207 | __is.setstate(__state); | |
1cb7f91f BK |
1208 | return __is; |
1209 | } | |
54c1bf78 | 1210 | |
1cb7f91f BK |
1211 | template <class _CharT, class _Traits, size_t _Nb> |
1212 | basic_ostream<_CharT, _Traits>& | |
1213 | operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x) | |
1214 | { | |
1215 | basic_string<_CharT, _Traits> __tmp; | |
1216 | __x._M_copy_to_string(__tmp); | |
1217 | return __os << __tmp; | |
1218 | } | |
b963aad8 | 1219 | //@} |
390e4c0d | 1220 | } // namespace std |
54c1bf78 | 1221 | |
3d7c150e BK |
1222 | #undef _GLIBCXX_BITSET_WORDS |
1223 | #undef _GLIBCXX_BITSET_BITS_PER_WORD | |
54c1bf78 | 1224 | |
285b36d6 BK |
1225 | #ifdef _GLIBCXX_DEBUG |
1226 | # include <debug/bitset> | |
1227 | #endif | |
1228 | ||
1143680e | 1229 | #endif /* _GLIBCXX_BITSET */ |