]>
Commit | Line | Data |
---|---|---|
54c1bf78 | 1 | // <bitset> -*- C++ -*- |
de96ac46 | 2 | |
ffe94f83 | 3 | // Copyright (C) 2001, 2002 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. | |
41 | */ | |
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 | ||
54c1bf78 BK |
48 | #ifndef __GLIBCPP_BITSET |
49 | #define __GLIBCPP_BITSET | |
50 | ||
51 | #pragma GCC system_header | |
52 | ||
53 | // A bitset of size N has N % (sizeof(unsigned long) * CHAR_BIT) unused | |
54 | // bits. (They are the high- order bits in the highest word.) It is | |
55 | // a class invariant of class bitset<> that those unused bits are | |
56 | // always zero. | |
57 | ||
58 | // Most of the actual code isn't contained in bitset<> itself, but in the | |
59 | // base class _Base_bitset. The base class works with whole words, not with | |
60 | // individual bits. This allows us to specialize _Base_bitset for the | |
61 | // important special case where the bitset is only a single word. | |
62 | ||
54c1bf78 BK |
63 | #include <cstddef> // for size_t |
64 | #include <cstring> // for memset | |
65 | #include <string> | |
54c1bf78 BK |
66 | #include <bits/functexcept.h> // for invalid_argument, out_of_range, |
67 | // overflow_error | |
68 | #include <ostream> // for ostream (operator<<) | |
69 | #include <istream> // for istream (operator>>) | |
70 | ||
71 | #define _GLIBCPP_BITSET_BITS_PER_WORD (CHAR_BIT*sizeof(unsigned long)) | |
72 | #define __BITSET_WORDS(__n) \ | |
73 | ((__n) < 1 ? 1 : ((__n) + _GLIBCPP_BITSET_BITS_PER_WORD - 1)/_GLIBCPP_BITSET_BITS_PER_WORD) | |
74 | ||
75 | namespace std | |
76 | { | |
1cb7f91f BK |
77 | extern unsigned char _S_bit_count[256]; |
78 | extern unsigned char _S_first_one[256]; | |
79 | ||
80 | // Base class: general case. | |
81 | template<size_t _Nw> | |
82 | struct _Base_bitset | |
83 | { | |
84 | typedef unsigned long _WordT; | |
85 | ||
86 | // 0 is the least significant word. | |
87 | _WordT _M_w[_Nw]; | |
88 | ||
89 | _Base_bitset() { _M_do_reset(); } | |
90 | _Base_bitset(unsigned long __val) | |
91 | { | |
92 | _M_do_reset(); | |
93 | _M_w[0] = __val; | |
94 | } | |
54c1bf78 | 95 | |
1cb7f91f BK |
96 | static size_t |
97 | _S_whichword(size_t __pos ) | |
98 | { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; } | |
54c1bf78 | 99 | |
1cb7f91f BK |
100 | static size_t |
101 | _S_whichbyte(size_t __pos ) | |
102 | { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; } | |
54c1bf78 | 103 | |
1cb7f91f BK |
104 | static size_t |
105 | _S_whichbit(size_t __pos ) | |
106 | { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; } | |
54c1bf78 | 107 | |
1cb7f91f BK |
108 | static _WordT |
109 | _S_maskbit(size_t __pos ) | |
110 | { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } | |
54c1bf78 | 111 | |
1cb7f91f BK |
112 | _WordT& |
113 | _M_getword(size_t __pos) | |
114 | { return _M_w[_S_whichword(__pos)]; } | |
54c1bf78 | 115 | |
1cb7f91f BK |
116 | _WordT |
117 | _M_getword(size_t __pos) const | |
118 | { return _M_w[_S_whichword(__pos)]; } | |
54c1bf78 | 119 | |
1cb7f91f BK |
120 | _WordT& |
121 | _M_hiword() { return _M_w[_Nw - 1]; } | |
54c1bf78 | 122 | |
1cb7f91f BK |
123 | _WordT |
124 | _M_hiword() const { return _M_w[_Nw - 1]; } | |
54c1bf78 | 125 | |
1cb7f91f BK |
126 | void |
127 | _M_do_and(const _Base_bitset<_Nw>& __x) | |
128 | { | |
129 | for (size_t __i = 0; __i < _Nw; __i++) | |
130 | _M_w[__i] &= __x._M_w[__i]; | |
131 | } | |
54c1bf78 | 132 | |
1cb7f91f BK |
133 | void |
134 | _M_do_or(const _Base_bitset<_Nw>& __x) | |
135 | { | |
136 | for (size_t __i = 0; __i < _Nw; __i++) | |
137 | _M_w[__i] |= __x._M_w[__i]; | |
138 | } | |
54c1bf78 | 139 | |
1cb7f91f BK |
140 | void |
141 | _M_do_xor(const _Base_bitset<_Nw>& __x) | |
142 | { | |
143 | for (size_t __i = 0; __i < _Nw; __i++) | |
144 | _M_w[__i] ^= __x._M_w[__i]; | |
145 | } | |
54c1bf78 | 146 | |
1cb7f91f BK |
147 | void |
148 | _M_do_left_shift(size_t __shift); | |
149 | ||
150 | void | |
151 | _M_do_right_shift(size_t __shift); | |
152 | ||
153 | void | |
154 | _M_do_flip() | |
155 | { | |
156 | for (size_t __i = 0; __i < _Nw; __i++) | |
157 | _M_w[__i] = ~_M_w[__i]; | |
158 | } | |
54c1bf78 | 159 | |
1cb7f91f BK |
160 | void |
161 | _M_do_set() | |
162 | { | |
163 | for (size_t __i = 0; __i < _Nw; __i++) | |
164 | _M_w[__i] = ~static_cast<_WordT>(0); | |
165 | } | |
54c1bf78 | 166 | |
1cb7f91f BK |
167 | void |
168 | _M_do_reset() { memset(_M_w, 0, _Nw * sizeof(_WordT)); } | |
169 | ||
170 | bool | |
171 | _M_is_equal(const _Base_bitset<_Nw>& __x) const | |
172 | { | |
173 | for (size_t __i = 0; __i < _Nw; ++__i) | |
174 | { | |
175 | if (_M_w[__i] != __x._M_w[__i]) | |
176 | return false; | |
177 | } | |
178 | return true; | |
179 | } | |
54c1bf78 | 180 | |
1cb7f91f BK |
181 | bool |
182 | _M_is_any() const | |
183 | { | |
184 | for (size_t __i = 0; __i < _Nw; __i++) | |
185 | { | |
186 | if (_M_w[__i] != static_cast<_WordT>(0)) | |
187 | return true; | |
188 | } | |
189 | return false; | |
190 | } | |
54c1bf78 | 191 | |
1cb7f91f BK |
192 | size_t |
193 | _M_do_count() const | |
194 | { | |
195 | size_t __result = 0; | |
196 | const unsigned char* __byte_ptr = (const unsigned char*)_M_w; | |
197 | const unsigned char* __end_ptr = (const unsigned char*)(_M_w + _Nw); | |
198 | ||
199 | while ( __byte_ptr < __end_ptr ) | |
200 | { | |
201 | __result += _S_bit_count[*__byte_ptr]; | |
202 | __byte_ptr++; | |
203 | } | |
204 | return __result; | |
205 | } | |
54c1bf78 | 206 | |
1cb7f91f BK |
207 | unsigned long |
208 | _M_do_to_ulong() const; | |
209 | ||
210 | // find first "on" bit | |
211 | size_t | |
212 | _M_do_find_first(size_t __not_found) const; | |
213 | ||
214 | // find the next "on" bit that follows "prev" | |
215 | size_t | |
216 | _M_do_find_next(size_t __prev, size_t __not_found) const; | |
217 | }; | |
218 | ||
219 | // Definitions of non-inline functions from _Base_bitset. | |
220 | template<size_t _Nw> | |
221 | void | |
222 | _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) | |
223 | { | |
224 | if (__shift != 0) | |
225 | { | |
226 | const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD; | |
227 | const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD; | |
228 | ||
229 | if (__offset == 0) | |
230 | for (size_t __n = _Nw - 1; __n >= __wshift; --__n) | |
231 | _M_w[__n] = _M_w[__n - __wshift]; | |
232 | else | |
233 | { | |
234 | const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset; | |
235 | for (size_t __n = _Nw - 1; __n > __wshift; --__n) | |
236 | _M_w[__n] = (_M_w[__n - __wshift] << __offset) | | |
237 | (_M_w[__n - __wshift - 1] >> __sub_offset); | |
238 | _M_w[__wshift] = _M_w[0] << __offset; | |
239 | } | |
240 | ||
241 | fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0)); | |
242 | } | |
54c1bf78 | 243 | } |
1cb7f91f BK |
244 | |
245 | template<size_t _Nw> | |
246 | void | |
247 | _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) | |
248 | { | |
249 | if (__shift != 0) | |
250 | { | |
251 | const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD; | |
252 | const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD; | |
253 | const size_t __limit = _Nw - __wshift - 1; | |
254 | ||
255 | if (__offset == 0) | |
256 | for (size_t __n = 0; __n <= __limit; ++__n) | |
257 | _M_w[__n] = _M_w[__n + __wshift]; | |
258 | else | |
259 | { | |
260 | const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset; | |
261 | for (size_t __n = 0; __n < __limit; ++__n) | |
262 | _M_w[__n] = (_M_w[__n + __wshift] >> __offset) | | |
263 | (_M_w[__n + __wshift + 1] << __sub_offset); | |
264 | _M_w[__limit] = _M_w[_Nw-1] >> __offset; | |
265 | } | |
266 | ||
267 | fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0)); | |
268 | } | |
54c1bf78 | 269 | } |
54c1bf78 | 270 | |
1cb7f91f BK |
271 | template<size_t _Nw> |
272 | unsigned long | |
273 | _Base_bitset<_Nw>::_M_do_to_ulong() const | |
274 | { | |
275 | for (size_t __i = 1; __i < _Nw; ++__i) | |
276 | if (_M_w[__i]) | |
277 | __throw_overflow_error("bitset"); | |
278 | return _M_w[0]; | |
54c1bf78 | 279 | } |
54c1bf78 | 280 | |
1cb7f91f BK |
281 | template<size_t _Nw> |
282 | size_t | |
283 | _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const | |
284 | { | |
285 | for (size_t __i = 0; __i < _Nw; __i++ ) | |
286 | { | |
287 | _WordT __thisword = _M_w[__i]; | |
288 | if ( __thisword != static_cast<_WordT>(0) ) | |
289 | { | |
290 | // find byte within word | |
291 | for (size_t __j = 0; __j < sizeof(_WordT); __j++ ) | |
292 | { | |
293 | unsigned char __this_byte | |
294 | = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); | |
295 | if (__this_byte) | |
296 | return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT + | |
297 | _S_first_one[__this_byte]; | |
298 | ||
299 | __thisword >>= CHAR_BIT; | |
300 | } | |
301 | } | |
302 | } | |
303 | // not found, so return an indication of failure. | |
304 | return __not_found; | |
54c1bf78 BK |
305 | } |
306 | ||
1cb7f91f BK |
307 | template<size_t _Nw> |
308 | size_t | |
309 | _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const | |
310 | { | |
311 | // make bound inclusive | |
312 | ++__prev; | |
313 | ||
314 | // check out of bounds | |
315 | if ( __prev >= _Nw * _GLIBCPP_BITSET_BITS_PER_WORD ) | |
316 | return __not_found; | |
317 | ||
318 | // search first word | |
319 | size_t __i = _S_whichword(__prev); | |
320 | _WordT __thisword = _M_w[__i]; | |
321 | ||
322 | // mask off bits below bound | |
323 | __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); | |
324 | ||
325 | if ( __thisword != static_cast<_WordT>(0) ) | |
326 | { | |
327 | // find byte within word | |
328 | // get first byte into place | |
329 | __thisword >>= _S_whichbyte(__prev) * CHAR_BIT; | |
330 | for (size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++) | |
331 | { | |
332 | unsigned char __this_byte | |
333 | = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); | |
334 | if ( __this_byte ) | |
335 | return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT + | |
336 | _S_first_one[__this_byte]; | |
337 | ||
338 | __thisword >>= CHAR_BIT; | |
339 | } | |
340 | } | |
341 | ||
342 | // check subsequent words | |
343 | __i++; | |
344 | for ( ; __i < _Nw; __i++ ) | |
345 | { | |
346 | __thisword = _M_w[__i]; | |
347 | if ( __thisword != static_cast<_WordT>(0) ) | |
348 | { | |
349 | // find byte within word | |
350 | for (size_t __j = 0; __j < sizeof(_WordT); __j++ ) | |
351 | { | |
352 | unsigned char __this_byte | |
353 | = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); | |
354 | if ( __this_byte ) | |
355 | return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT + | |
356 | _S_first_one[__this_byte]; | |
357 | ||
358 | __thisword >>= CHAR_BIT; | |
359 | } | |
360 | } | |
361 | } | |
362 | // not found, so return an indication of failure. | |
363 | return __not_found; | |
364 | } // end _M_do_find_next | |
365 | ||
54c1bf78 | 366 | |
1cb7f91f BK |
367 | // Base class: specialization for a single word. |
368 | template<> | |
369 | struct _Base_bitset<1> | |
370 | { | |
371 | typedef unsigned long _WordT; | |
372 | _WordT _M_w; | |
54c1bf78 | 373 | |
1cb7f91f BK |
374 | _Base_bitset( void ) : _M_w(0) {} |
375 | _Base_bitset(unsigned long __val) : _M_w(__val) {} | |
54c1bf78 | 376 | |
1cb7f91f BK |
377 | static size_t |
378 | _S_whichword(size_t __pos ) | |
379 | { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; } | |
54c1bf78 | 380 | |
1cb7f91f BK |
381 | static size_t |
382 | _S_whichbyte(size_t __pos ) | |
383 | { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; } | |
54c1bf78 | 384 | |
1cb7f91f BK |
385 | static size_t |
386 | _S_whichbit(size_t __pos ) | |
387 | { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; } | |
54c1bf78 | 388 | |
1cb7f91f BK |
389 | static _WordT |
390 | _S_maskbit(size_t __pos ) | |
391 | { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } | |
54c1bf78 | 392 | |
1cb7f91f BK |
393 | _WordT& |
394 | _M_getword(size_t) { return _M_w; } | |
54c1bf78 | 395 | |
1cb7f91f BK |
396 | _WordT |
397 | _M_getword(size_t) const { return _M_w; } | |
54c1bf78 | 398 | |
1cb7f91f BK |
399 | _WordT& |
400 | _M_hiword() { return _M_w; } | |
54c1bf78 | 401 | |
1cb7f91f BK |
402 | _WordT |
403 | _M_hiword() const { return _M_w; } | |
54c1bf78 | 404 | |
1cb7f91f BK |
405 | void |
406 | _M_do_and(const _Base_bitset<1>& __x) { _M_w &= __x._M_w; } | |
54c1bf78 | 407 | |
1cb7f91f BK |
408 | void |
409 | _M_do_or(const _Base_bitset<1>& __x) { _M_w |= __x._M_w; } | |
54c1bf78 | 410 | |
1cb7f91f BK |
411 | void |
412 | _M_do_xor(const _Base_bitset<1>& __x) { _M_w ^= __x._M_w; } | |
54c1bf78 | 413 | |
1cb7f91f BK |
414 | void |
415 | _M_do_left_shift(size_t __shift) { _M_w <<= __shift; } | |
54c1bf78 | 416 | |
1cb7f91f BK |
417 | void |
418 | _M_do_right_shift(size_t __shift) { _M_w >>= __shift; } | |
54c1bf78 | 419 | |
1cb7f91f BK |
420 | void |
421 | _M_do_flip() { _M_w = ~_M_w; } | |
54c1bf78 | 422 | |
1cb7f91f BK |
423 | void |
424 | _M_do_set() { _M_w = ~static_cast<_WordT>(0); } | |
54c1bf78 | 425 | |
1cb7f91f BK |
426 | void |
427 | _M_do_reset() { _M_w = 0; } | |
54c1bf78 | 428 | |
1cb7f91f BK |
429 | bool |
430 | _M_is_equal(const _Base_bitset<1>& __x) const | |
431 | { return _M_w == __x._M_w; } | |
54c1bf78 | 432 | |
1cb7f91f BK |
433 | bool |
434 | _M_is_any() const { return _M_w != 0; } | |
54c1bf78 | 435 | |
1cb7f91f BK |
436 | size_t |
437 | _M_do_count() const | |
438 | { | |
439 | size_t __result = 0; | |
440 | const unsigned char* __byte_ptr = (const unsigned char*)&_M_w; | |
441 | const unsigned char* __end_ptr | |
442 | = ((const unsigned char*)&_M_w)+sizeof(_M_w); | |
443 | while ( __byte_ptr < __end_ptr ) | |
444 | { | |
445 | __result += _S_bit_count[*__byte_ptr]; | |
446 | __byte_ptr++; | |
447 | } | |
448 | return __result; | |
449 | } | |
54c1bf78 | 450 | |
1cb7f91f BK |
451 | unsigned long |
452 | _M_do_to_ulong() const { return _M_w; } | |
453 | ||
454 | size_t | |
455 | _M_do_find_first(size_t __not_found) const; | |
456 | ||
457 | // find the next "on" bit that follows "prev" | |
458 | size_t | |
459 | _M_do_find_next(size_t __prev, size_t __not_found) const; | |
460 | }; | |
461 | ||
462 | // Helper class to zero out the unused high-order bits in the highest word. | |
463 | template<size_t _Extrabits> | |
464 | struct _Sanitize | |
465 | { | |
466 | static void _S_do_sanitize(unsigned long& __val) | |
467 | { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); } | |
468 | }; | |
469 | ||
470 | template<> | |
471 | struct _Sanitize<0> | |
472 | { static void _S_do_sanitize(unsigned long) { } }; | |
473 | ||
474 | // Class bitset. | |
475 | // _Nb may be any nonzero number of type size_t. | |
476 | template<size_t _Nb> | |
477 | class bitset : private _Base_bitset<__BITSET_WORDS(_Nb)> | |
478 | { | |
479 | private: | |
480 | typedef _Base_bitset<__BITSET_WORDS(_Nb)> _Base; | |
481 | typedef unsigned long _WordT; | |
482 | ||
483 | void | |
484 | _M_do_sanitize() | |
485 | { | |
486 | _Sanitize<_Nb%_GLIBCPP_BITSET_BITS_PER_WORD>::_S_do_sanitize(this->_M_hiword()); | |
487 | } | |
54c1bf78 | 488 | |
1cb7f91f BK |
489 | public: |
490 | // bit reference: | |
491 | class reference; | |
492 | friend class reference; | |
493 | ||
494 | class reference | |
495 | { | |
496 | friend class bitset; | |
497 | ||
498 | _WordT *_M_wp; | |
499 | size_t _M_bpos; | |
500 | ||
501 | // left undefined | |
502 | reference(); | |
503 | ||
504 | public: | |
505 | reference( bitset& __b, size_t __pos ) | |
506 | { | |
507 | _M_wp = &__b._M_getword(__pos); | |
508 | _M_bpos = _Base::_S_whichbit(__pos); | |
509 | } | |
54c1bf78 | 510 | |
1cb7f91f BK |
511 | ~reference() { } |
512 | ||
513 | // for b[i] = __x; | |
514 | reference& | |
515 | operator=(bool __x) | |
516 | { | |
517 | if ( __x ) | |
518 | *_M_wp |= _Base::_S_maskbit(_M_bpos); | |
519 | else | |
520 | *_M_wp &= ~_Base::_S_maskbit(_M_bpos); | |
521 | return *this; | |
522 | } | |
523 | ||
524 | // for b[i] = b[__j]; | |
525 | reference& | |
526 | operator=(const reference& __j) | |
527 | { | |
528 | if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) ) | |
529 | *_M_wp |= _Base::_S_maskbit(_M_bpos); | |
530 | else | |
531 | *_M_wp &= ~_Base::_S_maskbit(_M_bpos); | |
532 | return *this; | |
533 | } | |
54c1bf78 | 534 | |
1cb7f91f BK |
535 | // flips the bit |
536 | bool | |
537 | operator~() const | |
538 | { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } | |
54c1bf78 | 539 | |
1cb7f91f BK |
540 | // for __x = b[i]; |
541 | operator bool() const | |
542 | { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } | |
54c1bf78 | 543 | |
1cb7f91f BK |
544 | // for b[i].flip(); |
545 | reference& | |
546 | flip() | |
547 | { | |
548 | *_M_wp ^= _Base::_S_maskbit(_M_bpos); | |
549 | return *this; | |
550 | } | |
551 | }; | |
552 | ||
553 | // 23.3.5.1 constructors: | |
554 | bitset() { } | |
54c1bf78 | 555 | |
1cb7f91f BK |
556 | bitset(unsigned long __val) : _Base_bitset<__BITSET_WORDS(_Nb)>(__val) |
557 | { _M_do_sanitize(); } | |
54c1bf78 | 558 | |
1cb7f91f BK |
559 | template<class _CharT, class _Traits, class _Alloc> |
560 | explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, | |
561 | size_t __pos = 0) : _Base() | |
562 | { | |
563 | if (__pos > __s.size()) | |
564 | __throw_out_of_range("bitset"); | |
565 | _M_copy_from_string(__s, __pos, | |
566 | basic_string<_CharT, _Traits, _Alloc>::npos); | |
567 | } | |
54c1bf78 | 568 | |
1cb7f91f BK |
569 | template<class _CharT, class _Traits, class _Alloc> |
570 | bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, | |
571 | size_t __pos, size_t __n) : _Base() | |
572 | { | |
573 | if (__pos > __s.size()) | |
574 | __throw_out_of_range("bitset"); | |
575 | _M_copy_from_string(__s, __pos, __n); | |
576 | } | |
54c1bf78 | 577 | |
1cb7f91f BK |
578 | // 23.3.5.2 bitset operations: |
579 | bitset<_Nb>& | |
580 | operator&=(const bitset<_Nb>& __rhs) | |
581 | { | |
582 | this->_M_do_and(__rhs); | |
54c1bf78 BK |
583 | return *this; |
584 | } | |
585 | ||
1cb7f91f BK |
586 | bitset<_Nb>& |
587 | operator|=(const bitset<_Nb>& __rhs) | |
588 | { | |
589 | this->_M_do_or(__rhs); | |
54c1bf78 BK |
590 | return *this; |
591 | } | |
592 | ||
1cb7f91f BK |
593 | bitset<_Nb>& |
594 | operator^=(const bitset<_Nb>& __rhs) | |
595 | { | |
596 | this->_M_do_xor(__rhs); | |
597 | return *this; | |
598 | } | |
54c1bf78 | 599 | |
1cb7f91f BK |
600 | bitset<_Nb>& |
601 | operator<<=(size_t __pos) | |
602 | { | |
603 | this->_M_do_left_shift(__pos); | |
604 | this->_M_do_sanitize(); | |
54c1bf78 BK |
605 | return *this; |
606 | } | |
54c1bf78 | 607 | |
1cb7f91f BK |
608 | bitset<_Nb>& |
609 | operator>>=(size_t __pos) | |
610 | { | |
611 | this->_M_do_right_shift(__pos); | |
612 | this->_M_do_sanitize(); | |
613 | return *this; | |
614 | } | |
54c1bf78 | 615 | |
1cb7f91f BK |
616 | // Extension: |
617 | // Versions of single-bit set, reset, flip, test with no range checking. | |
618 | bitset<_Nb>& | |
619 | _Unchecked_set(size_t __pos) | |
620 | { | |
54c1bf78 | 621 | this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); |
1cb7f91f BK |
622 | return *this; |
623 | } | |
54c1bf78 | 624 | |
1cb7f91f BK |
625 | bitset<_Nb>& |
626 | _Unchecked_set(size_t __pos, int __val) | |
627 | { | |
628 | if (__val) | |
629 | this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); | |
630 | else | |
631 | this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); | |
632 | return *this; | |
633 | } | |
54c1bf78 | 634 | |
1cb7f91f BK |
635 | bitset<_Nb>& |
636 | _Unchecked_reset(size_t __pos) | |
637 | { | |
638 | this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); | |
639 | return *this; | |
640 | } | |
54c1bf78 | 641 | |
1cb7f91f BK |
642 | bitset<_Nb>& |
643 | _Unchecked_flip(size_t __pos) | |
644 | { | |
645 | this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); | |
646 | return *this; | |
647 | } | |
54c1bf78 | 648 | |
1cb7f91f BK |
649 | bool |
650 | _Unchecked_test(size_t __pos) const | |
651 | { | |
652 | return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) | |
653 | != static_cast<_WordT>(0); | |
654 | } | |
54c1bf78 | 655 | |
1cb7f91f BK |
656 | // Set, reset, and flip. |
657 | bitset<_Nb>& | |
658 | set() | |
659 | { | |
660 | this->_M_do_set(); | |
661 | this->_M_do_sanitize(); | |
662 | return *this; | |
663 | } | |
54c1bf78 | 664 | |
1cb7f91f BK |
665 | bitset<_Nb>& |
666 | set(size_t __pos, bool __val = true) | |
667 | { | |
668 | if (__pos >= _Nb) | |
669 | __throw_out_of_range("bitset"); | |
670 | return _Unchecked_set(__pos, __val); | |
671 | } | |
54c1bf78 | 672 | |
1cb7f91f BK |
673 | bitset<_Nb>& |
674 | reset() | |
675 | { | |
676 | this->_M_do_reset(); | |
677 | return *this; | |
678 | } | |
54c1bf78 | 679 | |
1cb7f91f BK |
680 | bitset<_Nb>& |
681 | reset(size_t __pos) | |
682 | { | |
683 | if (__pos >= _Nb) | |
684 | __throw_out_of_range("bitset"); | |
685 | return _Unchecked_reset(__pos); | |
686 | } | |
54c1bf78 | 687 | |
1cb7f91f BK |
688 | bitset<_Nb>& |
689 | flip() | |
690 | { | |
691 | this->_M_do_flip(); | |
692 | this->_M_do_sanitize(); | |
693 | return *this; | |
694 | } | |
54c1bf78 | 695 | |
1cb7f91f BK |
696 | bitset<_Nb>& |
697 | flip(size_t __pos) | |
698 | { | |
699 | if (__pos >= _Nb) | |
700 | __throw_out_of_range("bitset"); | |
701 | return _Unchecked_flip(__pos); | |
702 | } | |
54c1bf78 | 703 | |
1cb7f91f BK |
704 | bitset<_Nb> |
705 | operator~() const { return bitset<_Nb>(*this).flip(); } | |
706 | ||
707 | // element access: | |
708 | //for b[i]; | |
709 | // _GLIBCPP_RESOLVE_LIB_DEFECTS Note that this implementation already | |
710 | // resolves DR 11 (items 1 and 2), but does not do the range-checking | |
711 | // required by that DR's resolution. -pme | |
712 | reference | |
713 | operator[](size_t __pos) { return reference(*this,__pos); } | |
714 | ||
715 | bool | |
716 | operator[](size_t __pos) const { return _Unchecked_test(__pos); } | |
717 | ||
718 | unsigned long | |
719 | to_ulong() const { return this->_M_do_to_ulong(); } | |
720 | ||
721 | template<class _CharT, class _Traits, class _Alloc> | |
722 | basic_string<_CharT, _Traits, _Alloc> | |
723 | to_string() const | |
724 | { | |
725 | basic_string<_CharT, _Traits, _Alloc> __result; | |
726 | _M_copy_to_string(__result); | |
727 | return __result; | |
728 | } | |
54c1bf78 | 729 | |
1cb7f91f BK |
730 | // Helper functions for string operations. |
731 | template<class _CharT, class _Traits, class _Alloc> | |
732 | void | |
733 | _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, | |
734 | size_t, size_t); | |
54c1bf78 | 735 | |
1cb7f91f BK |
736 | template<class _CharT, class _Traits, class _Alloc> |
737 | void | |
738 | _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const; | |
54c1bf78 | 739 | |
1cb7f91f BK |
740 | size_t |
741 | count() const { return this->_M_do_count(); } | |
54c1bf78 | 742 | |
1cb7f91f BK |
743 | size_t |
744 | size() const { return _Nb; } | |
54c1bf78 | 745 | |
1cb7f91f BK |
746 | bool |
747 | operator==(const bitset<_Nb>& __rhs) const | |
748 | { return this->_M_is_equal(__rhs); } | |
54c1bf78 | 749 | |
1cb7f91f BK |
750 | bool |
751 | operator!=(const bitset<_Nb>& __rhs) const | |
752 | { return !this->_M_is_equal(__rhs); } | |
54c1bf78 | 753 | |
1cb7f91f BK |
754 | bool |
755 | test(size_t __pos) const | |
756 | { | |
757 | if (__pos >= _Nb) | |
758 | __throw_out_of_range("bitset"); | |
759 | return _Unchecked_test(__pos); | |
760 | } | |
54c1bf78 | 761 | |
1cb7f91f BK |
762 | bool |
763 | any() const { return this->_M_is_any(); } | |
54c1bf78 | 764 | |
1cb7f91f BK |
765 | bool |
766 | none() const { return !this->_M_is_any(); } | |
54c1bf78 | 767 | |
1cb7f91f BK |
768 | bitset<_Nb> |
769 | operator<<(size_t __pos) const | |
54c1bf78 | 770 | { return bitset<_Nb>(*this) <<= __pos; } |
1cb7f91f BK |
771 | |
772 | bitset<_Nb> | |
773 | operator>>(size_t __pos) const | |
54c1bf78 BK |
774 | { return bitset<_Nb>(*this) >>= __pos; } |
775 | ||
1cb7f91f BK |
776 | // EXTENSIONS: bit-find operations. These operations are |
777 | // experimental, and are subject to change or removal in future | |
778 | // versions. | |
54c1bf78 | 779 | |
1cb7f91f BK |
780 | // find the index of the first "on" bit |
781 | size_t | |
782 | _Find_first() const | |
54c1bf78 BK |
783 | { return this->_M_do_find_first(_Nb); } |
784 | ||
1cb7f91f BK |
785 | // find the index of the next "on" bit after prev |
786 | size_t | |
787 | _Find_next(size_t __prev ) const | |
54c1bf78 | 788 | { return this->_M_do_find_next(__prev, _Nb); } |
1cb7f91f | 789 | }; |
54c1bf78 | 790 | |
1cb7f91f BK |
791 | // Definitions of non-inline member functions. |
792 | template<size_t _Nb> | |
793 | template<class _CharT, class _Traits, class _Alloc> | |
794 | void | |
795 | bitset<_Nb>::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, size_t __pos, size_t __n) | |
796 | { | |
797 | reset(); | |
798 | const size_t __nbits = min(_Nb, min(__n, __s.size() - __pos)); | |
799 | for (size_t __i = 0; __i < __nbits; ++__i) | |
800 | { | |
801 | switch(__s[__pos + __nbits - __i - 1]) | |
802 | { | |
803 | case '0': | |
804 | break; | |
805 | case '1': | |
806 | set(__i); | |
807 | break; | |
808 | default: | |
809 | __throw_invalid_argument("bitset"); | |
810 | } | |
811 | } | |
54c1bf78 | 812 | } |
54c1bf78 | 813 | |
1cb7f91f BK |
814 | template<size_t _Nb> |
815 | template<class _CharT, class _Traits, class _Alloc> | |
816 | void | |
817 | bitset<_Nb>::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const | |
818 | { | |
819 | __s.assign(_Nb, '0'); | |
820 | for (size_t __i = 0; __i < _Nb; ++__i) | |
821 | if (_Unchecked_test(__i)) | |
822 | __s[_Nb - 1 - __i] = '1'; | |
823 | } | |
54c1bf78 | 824 | |
1cb7f91f BK |
825 | // 23.3.5.3 bitset operations: |
826 | template<size_t _Nb> | |
827 | inline bitset<_Nb> | |
828 | operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) | |
829 | { | |
830 | bitset<_Nb> __result(__x); | |
831 | __result &= __y; | |
832 | return __result; | |
54c1bf78 BK |
833 | } |
834 | ||
1cb7f91f BK |
835 | template<size_t _Nb> |
836 | inline bitset<_Nb> | |
837 | operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) | |
838 | { | |
839 | bitset<_Nb> __result(__x); | |
840 | __result |= __y; | |
841 | return __result; | |
842 | } | |
54c1bf78 | 843 | |
1cb7f91f BK |
844 | template <size_t _Nb> |
845 | inline bitset<_Nb> | |
846 | operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) | |
847 | { | |
848 | bitset<_Nb> __result(__x); | |
849 | __result ^= __y; | |
850 | return __result; | |
851 | } | |
54c1bf78 | 852 | |
1cb7f91f BK |
853 | template<class _CharT, class _Traits, size_t _Nb> |
854 | basic_istream<_CharT, _Traits>& | |
855 | operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) | |
856 | { | |
857 | typedef typename _Traits::char_type char_type; | |
858 | basic_string<_CharT, _Traits> __tmp; | |
859 | __tmp.reserve(_Nb); | |
860 | ||
861 | // Skip whitespace | |
862 | typename basic_istream<_CharT, _Traits>::sentry __sentry(__is); | |
863 | if (__sentry) | |
864 | { | |
865 | basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf(); | |
866 | for (size_t __i = 0; __i < _Nb; ++__i) | |
867 | { | |
868 | static typename _Traits::int_type __eof = _Traits::eof(); | |
869 | ||
870 | typename _Traits::int_type __c1 = __buf->sbumpc(); | |
871 | if (_Traits::eq_int_type(__c1, __eof)) | |
872 | { | |
873 | __is.setstate(ios_base::eofbit); | |
874 | break; | |
875 | } | |
876 | else | |
877 | { | |
878 | char_type __c2 = _Traits::to_char_type(__c1); | |
879 | char_type __c = __is.narrow(__c2, '*'); | |
880 | ||
881 | if (__c == '0' || __c == '1') | |
882 | __tmp.push_back(__c); | |
883 | else if (_Traits::eq_int_type(__buf->sputbackc(__c2), | |
884 | __eof)) | |
885 | { | |
886 | __is.setstate(ios_base::failbit); | |
887 | break; | |
888 | } | |
889 | } | |
890 | } | |
891 | ||
892 | if (__tmp.empty()) | |
893 | __is.setstate(ios_base::failbit); | |
894 | else | |
895 | __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb); | |
896 | } | |
897 | ||
898 | return __is; | |
899 | } | |
54c1bf78 | 900 | |
1cb7f91f BK |
901 | template <class _CharT, class _Traits, size_t _Nb> |
902 | basic_ostream<_CharT, _Traits>& | |
903 | operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x) | |
904 | { | |
905 | basic_string<_CharT, _Traits> __tmp; | |
906 | __x._M_copy_to_string(__tmp); | |
907 | return __os << __tmp; | |
908 | } | |
54c1bf78 BK |
909 | } // namespace std |
910 | ||
911 | #undef __BITSET_WORDS | |
912 | ||
1cb7f91f | 913 | #endif |