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