]>
Commit | Line | Data |
---|---|---|
768a887c JM |
1 | /* |
2 | * Copyright (c) 1998 | |
3 | * Silicon Graphics Computer Systems, Inc. | |
4 | * | |
5 | * Permission to use, copy, modify, distribute and sell this software | |
6 | * and its documentation for any purpose is hereby granted without fee, | |
7 | * provided that the above copyright notice appear in all copies and | |
8 | * that both that copyright notice and this permission notice appear | |
9 | * in supporting documentation. Silicon Graphics makes no | |
10 | * representations about the suitability of this software for any | |
11 | * purpose. It is provided "as is" without express or implied warranty. | |
554241c3 | 12 | */ |
768a887c JM |
13 | |
14 | #ifndef __SGI_STL_BITSET | |
15 | #define __SGI_STL_BITSET | |
16 | ||
17 | // This implementation of bitset<> has a second template parameter, | |
18 | // _WordT, which defaults to unsigned long. *YOU SHOULD NOT USE | |
19 | // THIS FEATURE*. It is experimental, and it may be removed in | |
20 | // future releases. | |
21 | ||
554241c3 | 22 | // A bitset of size N, using words of type _WordT, will have |
768a887c JM |
23 | // N % (sizeof(_WordT) * CHAR_BIT) unused bits. (They are the high- |
24 | // order bits in the highest word.) It is a class invariant | |
25 | // of class bitset<> that those unused bits are always zero. | |
26 | ||
554241c3 | 27 | // Most of the actual code isn't contained in bitset<> itself, but in the |
768a887c JM |
28 | // base class _Base_bitset. The base class works with whole words, not with |
29 | // individual bits. This allows us to specialize _Base_bitset for the | |
30 | // important special case where the bitset is only a single word. | |
31 | ||
32 | // The C++ standard does not define the precise semantics of operator[]. | |
33 | // In this implementation the const version of operator[] is equivalent | |
34 | // to test(), except that it does no range checking. The non-const version | |
35 | // returns a reference to a bit, again without doing any range checking. | |
36 | ||
37 | ||
38 | #include <stddef.h> // for size_t | |
39 | #include <string> | |
40 | #include <stdexcept> // for invalid_argument, out_of_range, overflow_error | |
41 | #include <iostream.h> // for istream, ostream | |
42 | ||
43 | #define __BITS_PER_WORDT(__wt) (CHAR_BIT*sizeof(__wt)) | |
44 | #define __BITSET_WORDS(__n,__wt) \ | |
45 | ((__n) < 1 ? 1 : ((__n) + __BITS_PER_WORDT(__wt) - 1)/__BITS_PER_WORDT(__wt)) | |
46 | ||
47 | __STL_BEGIN_NAMESPACE | |
48 | ||
49 | #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) | |
50 | #pragma set woff 1209 | |
51 | #endif | |
52 | ||
53 | // structure to aid in counting bits | |
554241c3 | 54 | template<bool __dummy> |
768a887c JM |
55 | struct _Bit_count { |
56 | static unsigned char _S_bit_count[256]; | |
57 | }; | |
58 | ||
59 | // Mapping from 8 bit unsigned integers to the index of the first one | |
60 | // bit: | |
554241c3 | 61 | template<bool __dummy> |
768a887c JM |
62 | struct _First_one { |
63 | static unsigned char _S_first_one[256]; | |
64 | }; | |
65 | ||
66 | // | |
67 | // Base class: general case. | |
68 | // | |
69 | ||
70 | template<size_t _Nw, class _WordT> | |
71 | struct _Base_bitset { | |
72 | _WordT _M_w[_Nw]; // 0 is the least significant word. | |
73 | ||
74 | _Base_bitset( void ) { _M_do_reset(); } | |
75 | ||
76 | _Base_bitset(unsigned long __val); | |
77 | ||
78 | static size_t _S_whichword( size_t __pos ) { | |
79 | return __pos / __BITS_PER_WORDT(_WordT); | |
80 | } | |
81 | static size_t _S_whichbyte( size_t __pos ) { | |
82 | return (__pos % __BITS_PER_WORDT(_WordT)) / CHAR_BIT; | |
83 | } | |
84 | static size_t _S_whichbit( size_t __pos ) { | |
85 | return __pos % __BITS_PER_WORDT(_WordT); | |
86 | } | |
87 | static _WordT _S_maskbit( size_t __pos ) { | |
88 | return (static_cast<_WordT>(1)) << _S_whichbit(__pos); | |
89 | } | |
90 | ||
91 | _WordT& _M_getword(size_t __pos) { return _M_w[_S_whichword(__pos)]; } | |
92 | _WordT _M_getword(size_t __pos) const { return _M_w[_S_whichword(__pos)]; } | |
93 | ||
94 | _WordT& _M_hiword() { return _M_w[_Nw - 1]; } | |
95 | _WordT _M_hiword() const { return _M_w[_Nw - 1]; } | |
96 | ||
97 | void _M_do_and(const _Base_bitset<_Nw,_WordT>& __x) { | |
98 | for ( size_t __i = 0; __i < _Nw; __i++ ) { | |
99 | _M_w[__i] &= __x._M_w[__i]; | |
100 | } | |
101 | } | |
102 | ||
103 | void _M_do_or(const _Base_bitset<_Nw,_WordT>& __x) { | |
104 | for ( size_t __i = 0; __i < _Nw; __i++ ) { | |
105 | _M_w[__i] |= __x._M_w[__i]; | |
106 | } | |
107 | } | |
108 | ||
109 | void _M_do_xor(const _Base_bitset<_Nw,_WordT>& __x) { | |
110 | for ( size_t __i = 0; __i < _Nw; __i++ ) { | |
111 | _M_w[__i] ^= __x._M_w[__i]; | |
112 | } | |
113 | } | |
114 | ||
115 | void _M_do_left_shift(size_t __shift); | |
116 | ||
117 | void _M_do_right_shift(size_t __shift); | |
118 | ||
119 | void _M_do_flip() { | |
120 | for ( size_t __i = 0; __i < _Nw; __i++ ) { | |
121 | _M_w[__i] = ~_M_w[__i]; | |
122 | } | |
123 | } | |
124 | ||
125 | void _M_do_set() { | |
126 | for ( size_t __i = 0; __i < _Nw; __i++ ) { | |
127 | _M_w[__i] = ~static_cast<_WordT>(0); | |
128 | } | |
129 | } | |
130 | ||
131 | void _M_do_reset() { | |
132 | for ( size_t __i = 0; __i < _Nw; __i++ ) { | |
133 | _M_w[__i] = 0; | |
134 | } | |
135 | } | |
136 | ||
137 | bool _M_is_equal(const _Base_bitset<_Nw,_WordT>& __x) const { | |
138 | for (size_t __i = 0; __i < _Nw; ++__i) { | |
139 | if (_M_w[__i] != __x._M_w[__i]) | |
140 | return false; | |
141 | } | |
142 | return true; | |
143 | } | |
144 | ||
145 | bool _M_is_any() const { | |
146 | for ( size_t __i = 0; __i < __BITSET_WORDS(_Nw,_WordT); __i++ ) { | |
147 | if ( _M_w[__i] != static_cast<_WordT>(0) ) | |
148 | return true; | |
149 | } | |
150 | return false; | |
151 | } | |
152 | ||
153 | size_t _M_do_count() const { | |
154 | size_t __result = 0; | |
155 | const unsigned char* __byte_ptr = (const unsigned char*)_M_w; | |
156 | const unsigned char* __end_ptr = (const unsigned char*)(_M_w+_Nw); | |
157 | ||
158 | while ( __byte_ptr < __end_ptr ) { | |
159 | __result += _Bit_count<true>::_S_bit_count[*__byte_ptr]; | |
160 | __byte_ptr++; | |
161 | } | |
162 | return __result; | |
163 | } | |
164 | ||
554241c3 | 165 | unsigned long _M_do_to_ulong() const; |
768a887c JM |
166 | |
167 | // find first "on" bit | |
168 | size_t _M_do_find_first(size_t __not_found) const; | |
169 | ||
170 | // find the next "on" bit that follows "prev" | |
171 | size_t _M_do_find_next(size_t __prev, size_t __not_found) const; | |
172 | }; | |
173 | ||
174 | // | |
175 | // Definitions of non-inline functions from _Base_bitset. | |
554241c3 | 176 | // |
768a887c JM |
177 | |
178 | template<size_t _Nw, class _WordT> | |
179 | _Base_bitset<_Nw, _WordT>::_Base_bitset(unsigned long __val) | |
180 | { | |
181 | _M_do_reset(); | |
182 | const size_t __n = min(sizeof(unsigned long)*CHAR_BIT, | |
183 | __BITS_PER_WORDT(_WordT)*_Nw); | |
184 | for(size_t __i = 0; __i < __n; ++__i, __val >>= 1) | |
185 | if ( __val & 0x1 ) | |
186 | _M_getword(__i) |= _S_maskbit(__i); | |
187 | } | |
188 | ||
189 | template<size_t _Nw, class _WordT> | |
554241c3 | 190 | void _Base_bitset<_Nw, _WordT>::_M_do_left_shift(size_t __shift) |
768a887c JM |
191 | { |
192 | if (__shift != 0) { | |
193 | const size_t __wshift = __shift / __BITS_PER_WORDT(_WordT); | |
194 | const size_t __offset = __shift % __BITS_PER_WORDT(_WordT); | |
195 | const size_t __sub_offset = __BITS_PER_WORDT(_WordT) - __offset; | |
196 | size_t __n = _Nw - 1; | |
197 | for ( ; __n > __wshift; --__n) | |
554241c3 | 198 | _M_w[__n] = (_M_w[__n - __wshift] << __offset) | |
768a887c JM |
199 | (_M_w[__n - __wshift - 1] >> __sub_offset); |
200 | if (__n == __wshift) | |
201 | _M_w[__n] = _M_w[0] << __offset; | |
202 | for (size_t __n1 = 0; __n1 < __n; ++__n1) | |
203 | _M_w[__n1] = static_cast<_WordT>(0); | |
204 | } | |
205 | } | |
206 | ||
207 | template<size_t _Nw, class _WordT> | |
554241c3 | 208 | void _Base_bitset<_Nw, _WordT>::_M_do_right_shift(size_t __shift) |
768a887c JM |
209 | { |
210 | if (__shift != 0) { | |
211 | const size_t __wshift = __shift / __BITS_PER_WORDT(_WordT); | |
212 | const size_t __offset = __shift % __BITS_PER_WORDT(_WordT); | |
213 | const size_t __sub_offset = __BITS_PER_WORDT(_WordT) - __offset; | |
214 | const size_t __limit = _Nw - __wshift - 1; | |
215 | size_t __n = 0; | |
216 | for ( ; __n < __limit; ++__n) | |
554241c3 | 217 | _M_w[__n] = (_M_w[__n + __wshift] >> __offset) | |
768a887c JM |
218 | (_M_w[__n + __wshift + 1] << __sub_offset); |
219 | _M_w[__limit] = _M_w[_Nw-1] >> __offset; | |
220 | for (size_t __n1 = __limit + 1; __n1 < _Nw; ++__n1) | |
221 | _M_w[__n1] = static_cast<_WordT>(0); | |
222 | } | |
223 | } | |
224 | ||
225 | template<size_t _Nw, class _WordT> | |
226 | unsigned long _Base_bitset<_Nw, _WordT>::_M_do_to_ulong() const | |
227 | { | |
228 | const overflow_error __overflow("bitset"); | |
229 | ||
230 | if (sizeof(_WordT) >= sizeof(unsigned long)) { | |
554241c3 UD |
231 | for (size_t __i = 1; __i < _Nw; ++__i) |
232 | if (_M_w[__i]) | |
768a887c JM |
233 | __STL_THROW(__overflow); |
234 | ||
235 | const _WordT __mask = static_cast<_WordT>(static_cast<unsigned long>(-1)); | |
554241c3 | 236 | if (_M_w[0] & ~__mask) |
768a887c JM |
237 | __STL_THROW(__overflow); |
238 | ||
239 | return static_cast<unsigned long>(_M_w[0] & __mask); | |
240 | } | |
241 | else { // sizeof(_WordT) < sizeof(unsigned long). | |
242 | const size_t __nwords = | |
243 | (sizeof(unsigned long) + sizeof(_WordT) - 1) / sizeof(_WordT); | |
244 | ||
245 | size_t __min_nwords = __nwords; | |
246 | if (_Nw > __nwords) { | |
554241c3 UD |
247 | for (size_t __i = __nwords; __i < _Nw; ++__i) |
248 | if (_M_w[__i]) | |
768a887c JM |
249 | __STL_THROW(__overflow); |
250 | } | |
554241c3 | 251 | else |
768a887c | 252 | __min_nwords = _Nw; |
554241c3 | 253 | |
768a887c JM |
254 | // If unsigned long is 8 bytes and _WordT is 6 bytes, then an unsigned |
255 | // long consists of all of one word plus 2 bytes from another word. | |
256 | const size_t __part = sizeof(unsigned long) % sizeof(_WordT); | |
257 | ||
554241c3 | 258 | if (__part != 0 && __nwords <= _Nw && |
768a887c JM |
259 | (_M_w[__min_nwords - 1] >> ((sizeof(_WordT) - __part) * CHAR_BIT)) != 0) |
260 | __STL_THROW(__overflow); | |
261 | ||
262 | unsigned long __result = 0; | |
263 | for (size_t __i = 0; __i < __min_nwords; ++__i) { | |
264 | __result |= static_cast<unsigned long>( | |
265 | _M_w[__i]) << (__i * sizeof(_WordT) * CHAR_BIT); | |
266 | } | |
267 | return __result; | |
268 | } | |
269 | } // End _M_do_to_ulong | |
270 | ||
271 | template<size_t _Nw, class _WordT> | |
554241c3 | 272 | size_t _Base_bitset<_Nw, _WordT>::_M_do_find_first(size_t __not_found) const |
768a887c JM |
273 | { |
274 | for ( size_t __i = 0; __i < _Nw; __i++ ) { | |
275 | _WordT __thisword = _M_w[__i]; | |
276 | if ( __thisword != static_cast<_WordT>(0) ) { | |
277 | // find byte within word | |
278 | for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) { | |
279 | unsigned char __this_byte | |
280 | = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); | |
281 | if ( __this_byte ) | |
282 | return __i*__BITS_PER_WORDT(_WordT) + __j*CHAR_BIT + | |
283 | _First_one<true>::_S_first_one[__this_byte]; | |
284 | ||
285 | __thisword >>= CHAR_BIT; | |
286 | } | |
287 | } | |
288 | } | |
289 | // not found, so return an indication of failure. | |
290 | return __not_found; | |
291 | } | |
292 | ||
293 | template<size_t _Nw, class _WordT> | |
294 | size_t | |
554241c3 | 295 | _Base_bitset<_Nw, _WordT>::_M_do_find_next(size_t __prev, |
768a887c JM |
296 | size_t __not_found) const |
297 | { | |
298 | // make bound inclusive | |
299 | ++__prev; | |
300 | ||
301 | // check out of bounds | |
302 | if ( __prev >= _Nw * __BITS_PER_WORDT(_WordT) ) | |
303 | return __not_found; | |
304 | ||
305 | // search first word | |
306 | size_t __i = _S_whichword(__prev); | |
307 | _WordT __thisword = _M_w[__i]; | |
308 | ||
309 | // mask off bits below bound | |
310 | __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); | |
311 | ||
312 | if ( __thisword != static_cast<_WordT>(0) ) { | |
313 | // find byte within word | |
314 | // get first byte into place | |
315 | __thisword >>= _S_whichbyte(__prev) * CHAR_BIT; | |
316 | for ( size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++ ) { | |
317 | unsigned char __this_byte | |
318 | = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); | |
319 | if ( __this_byte ) | |
320 | return __i*__BITS_PER_WORDT(_WordT) + __j*CHAR_BIT + | |
321 | _First_one<true>::_S_first_one[__this_byte]; | |
322 | ||
323 | __thisword >>= CHAR_BIT; | |
324 | } | |
325 | } | |
326 | ||
327 | // check subsequent words | |
328 | __i++; | |
329 | for ( ; __i < _Nw; __i++ ) { | |
330 | _WordT __thisword = _M_w[__i]; | |
331 | if ( __thisword != static_cast<_WordT>(0) ) { | |
332 | // find byte within word | |
333 | for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) { | |
334 | unsigned char __this_byte | |
335 | = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); | |
336 | if ( __this_byte ) | |
337 | return __i*__BITS_PER_WORDT(_WordT) + __j*CHAR_BIT + | |
338 | _First_one<true>::_S_first_one[__this_byte]; | |
339 | ||
340 | __thisword >>= CHAR_BIT; | |
341 | } | |
342 | } | |
343 | } | |
344 | ||
345 | // not found, so return an indication of failure. | |
346 | return __not_found; | |
347 | } // end _M_do_find_next | |
348 | ||
349 | ||
350 | // ------------------------------------------------------------ | |
351 | ||
352 | // | |
353 | // Base class: specialization for a single word. | |
354 | // | |
355 | ||
356 | template<class _WordT> | |
357 | struct _Base_bitset<1, _WordT> { | |
358 | _WordT _M_w; | |
359 | ||
360 | _Base_bitset( void ) { _M_do_reset(); } | |
361 | ||
554241c3 | 362 | _Base_bitset(unsigned long __val); |
768a887c JM |
363 | |
364 | static size_t _S_whichword( size_t __pos ) { | |
365 | return __pos / __BITS_PER_WORDT(_WordT); | |
366 | } | |
367 | static size_t _S_whichbyte( size_t __pos ) { | |
368 | return (__pos % __BITS_PER_WORDT(_WordT)) / CHAR_BIT; | |
369 | } | |
370 | static size_t _S_whichbit( size_t __pos ) { | |
371 | return __pos % __BITS_PER_WORDT(_WordT); | |
372 | } | |
373 | static _WordT _S_maskbit( size_t __pos ) { | |
374 | return (static_cast<_WordT>(1)) << _S_whichbit(__pos); | |
375 | } | |
376 | ||
377 | _WordT& _M_getword(size_t) { return _M_w; } | |
378 | _WordT _M_getword(size_t) const { return _M_w; } | |
379 | ||
380 | _WordT& _M_hiword() { return _M_w; } | |
381 | _WordT _M_hiword() const { return _M_w; } | |
382 | ||
383 | void _M_do_and(const _Base_bitset<1,_WordT>& __x) { _M_w &= __x._M_w; } | |
384 | void _M_do_or(const _Base_bitset<1,_WordT>& __x) { _M_w |= __x._M_w; } | |
385 | void _M_do_xor(const _Base_bitset<1,_WordT>& __x) { _M_w ^= __x._M_w; } | |
386 | void _M_do_left_shift(size_t __shift) { _M_w <<= __shift; } | |
387 | void _M_do_right_shift(size_t __shift) { _M_w >>= __shift; } | |
388 | void _M_do_flip() { _M_w = ~_M_w; } | |
389 | void _M_do_set() { _M_w = ~static_cast<_WordT>(0); } | |
390 | void _M_do_reset() { _M_w = 0; } | |
391 | ||
392 | bool _M_is_equal(const _Base_bitset<1,_WordT>& __x) const { | |
393 | return _M_w == __x._M_w; | |
394 | } | |
395 | bool _M_is_any() const { | |
396 | return _M_w != 0; | |
397 | } | |
398 | ||
399 | size_t _M_do_count() const { | |
400 | size_t __result = 0; | |
401 | const unsigned char* __byte_ptr = (const unsigned char*)&_M_w; | |
402 | const unsigned char* __end_ptr = ((const unsigned char*)&_M_w)+sizeof(_M_w); | |
403 | while ( __byte_ptr < __end_ptr ) { | |
404 | __result += _Bit_count<true>::_S_bit_count[*__byte_ptr]; | |
405 | __byte_ptr++; | |
406 | } | |
407 | return __result; | |
408 | } | |
409 | ||
410 | unsigned long _M_do_to_ulong() const { | |
411 | if (sizeof(_WordT) <= sizeof(unsigned long)) | |
412 | return static_cast<unsigned long>(_M_w); | |
413 | else { | |
414 | const _WordT __mask = static_cast<_WordT>(static_cast<unsigned long>(-1)); | |
554241c3 | 415 | if (_M_w & ~__mask) |
768a887c JM |
416 | __STL_THROW(overflow_error("bitset")); |
417 | return static_cast<unsigned long>(_M_w); | |
418 | } | |
419 | } | |
420 | ||
421 | size_t _M_do_find_first(size_t __not_found) const; | |
422 | ||
423 | // find the next "on" bit that follows "prev" | |
554241c3 | 424 | size_t _M_do_find_next(size_t __prev, size_t __not_found) const; |
768a887c JM |
425 | |
426 | }; | |
427 | ||
428 | // | |
429 | // Definitions of non-inline functions from the single-word version of | |
430 | // _Base_bitset. | |
431 | // | |
432 | ||
433 | template <class _WordT> | |
554241c3 | 434 | _Base_bitset<1, _WordT>::_Base_bitset(unsigned long __val) |
768a887c JM |
435 | { |
436 | _M_do_reset(); | |
437 | const size_t __n = min(sizeof(unsigned long)*CHAR_BIT, | |
438 | __BITS_PER_WORDT(_WordT)*_Nw); | |
439 | for(size_t __i = 0; __i < __n; ++__i, __val >>= 1) | |
440 | if ( __val & 0x1 ) | |
441 | _M_w |= _S_maskbit(__i); | |
442 | } | |
443 | ||
444 | template <class _WordT> | |
445 | size_t _Base_bitset<1, _WordT>::_M_do_find_first(size_t __not_found) const | |
446 | { | |
447 | _WordT __thisword = _M_w; | |
448 | ||
449 | if ( __thisword != static_cast<_WordT>(0) ) { | |
450 | // find byte within word | |
451 | for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) { | |
452 | unsigned char __this_byte | |
453 | = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); | |
454 | if ( __this_byte ) | |
455 | return __j*CHAR_BIT + _First_one<true>::_S_first_one[__this_byte]; | |
456 | ||
457 | __thisword >>= CHAR_BIT; | |
458 | } | |
459 | } | |
460 | // not found, so return a value that indicates failure. | |
461 | return __not_found; | |
462 | } | |
463 | ||
464 | template <class _WordT> | |
554241c3 UD |
465 | size_t |
466 | _Base_bitset<1, _WordT>::_M_do_find_next(size_t __prev, | |
768a887c JM |
467 | size_t __not_found ) const |
468 | { | |
469 | // make bound inclusive | |
470 | ++__prev; | |
471 | ||
472 | // check out of bounds | |
473 | if ( __prev >= __BITS_PER_WORDT(_WordT) ) | |
474 | return __not_found; | |
475 | ||
476 | // search first (and only) word | |
477 | _WordT __thisword = _M_w; | |
478 | ||
479 | // mask off bits below bound | |
480 | __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); | |
481 | ||
482 | if ( __thisword != static_cast<_WordT>(0) ) { | |
483 | // find byte within word | |
484 | // get first byte into place | |
485 | __thisword >>= _S_whichbyte(__prev) * CHAR_BIT; | |
486 | for ( size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++ ) { | |
487 | unsigned char __this_byte | |
488 | = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); | |
489 | if ( __this_byte ) | |
490 | return __j*CHAR_BIT + _First_one<true>::_S_first_one[__this_byte]; | |
491 | ||
492 | __thisword >>= CHAR_BIT; | |
493 | } | |
494 | } | |
495 | ||
496 | // not found, so return a value that indicates failure. | |
497 | return __not_found; | |
498 | } // end _M_do_find_next | |
499 | ||
500 | // | |
501 | // One last specialization: _M_do_to_ulong() and the constructor from | |
554241c3 | 502 | // unsigned long are very simple if the bitset consists of a single |
768a887c JM |
503 | // word of type unsigned long. |
504 | // | |
505 | ||
506 | template<> | |
554241c3 | 507 | inline unsigned long |
768a887c JM |
508 | _Base_bitset<1, unsigned long>::_M_do_to_ulong() const { return _M_w; } |
509 | ||
510 | template<> | |
511 | inline _Base_bitset<1, unsigned long>::_Base_bitset(unsigned long __val) { | |
512 | _M_w = __val; | |
513 | } | |
514 | ||
515 | ||
516 | // ------------------------------------------------------------ | |
517 | // Helper class to zero out the unused high-order bits in the highest word. | |
518 | ||
519 | template <class _WordT, size_t _Extrabits> struct _Sanitize { | |
520 | static void _M_do_sanitize(_WordT& __val) | |
521 | { __val &= ~((~static_cast<_WordT>(0)) << _Extrabits); } | |
522 | }; | |
523 | ||
524 | template <class _WordT> struct _Sanitize<_WordT, 0> { | |
525 | static void _M_do_sanitize(_WordT) {} | |
526 | }; | |
527 | ||
528 | // ------------------------------------------------------------ | |
529 | // Class bitset. | |
530 | // _Nb may be any nonzero number of type size_t. | |
531 | // Type _WordT may be any unsigned integral type. | |
532 | ||
533 | template<size_t _Nb, class _WordT = unsigned long> | |
554241c3 | 534 | class bitset : private _Base_bitset<__BITSET_WORDS(_Nb,_WordT), _WordT> |
768a887c JM |
535 | { |
536 | private: | |
537 | typedef _Base_bitset<__BITSET_WORDS(_Nb,_WordT), _WordT> _Base; | |
538 | ||
539 | // Import base's protected interface. Necessary because of new template | |
540 | // name resolution rules. | |
541 | using _Base::_S_whichword; | |
542 | using _Base::_S_whichbyte; | |
543 | using _Base::_S_whichbit; | |
544 | using _Base::_S_maskbit; | |
545 | using _Base::_M_getword; | |
546 | using _Base::_M_hiword; | |
547 | using _Base::_M_do_and; | |
548 | using _Base::_M_do_or; | |
549 | using _Base::_M_do_xor; | |
550 | using _Base::_M_do_left_shift; | |
551 | using _Base::_M_do_right_shift; | |
552 | using _Base::_M_do_flip; | |
553 | using _Base::_M_do_set; | |
554 | using _Base::_M_do_reset; | |
555 | using _Base::_M_is_equal; | |
556 | using _Base::_M_is_any; | |
557 | using _Base::_M_do_count; | |
558 | using _Base::_M_do_to_ulong; | |
559 | using _Base::_M_do_find_first; | |
560 | using _Base::_M_do_find_next; | |
561 | ||
562 | private: | |
563 | void _M_do_sanitize() { | |
564 | _Sanitize<_WordT,_Nb%__BITS_PER_WORDT(_WordT) > | |
565 | ::_M_do_sanitize(_M_hiword()); | |
566 | } | |
567 | ||
568 | public: | |
569 | ||
570 | // bit reference: | |
571 | class reference { | |
572 | friend class bitset; | |
573 | ||
574 | _WordT *_M_wp; | |
575 | size_t _M_bpos; | |
576 | ||
577 | // left undefined | |
578 | reference(); | |
579 | ||
580 | reference( bitset& __b, size_t __pos ) { | |
581 | _M_wp = &__b._M_getword(__pos); | |
582 | _M_bpos = _S_whichbit(__pos); | |
583 | } | |
584 | ||
585 | public: | |
586 | ~reference() {} | |
587 | ||
588 | // for b[i] = __x; | |
589 | reference& operator=(bool __x) { | |
590 | if ( __x ) | |
591 | *_M_wp |= _S_maskbit(_M_bpos); | |
592 | else | |
593 | *_M_wp &= ~_S_maskbit(_M_bpos); | |
594 | ||
595 | return *this; | |
596 | } | |
597 | ||
598 | // for b[i] = b[__j]; | |
599 | reference& operator=(const reference& __j) { | |
600 | if ( (*(__j._M_wp) & _S_maskbit(__j._M_bpos)) ) | |
601 | *_M_wp |= _S_maskbit(_M_bpos); | |
602 | else | |
603 | *_M_wp &= ~_S_maskbit(_M_bpos); | |
604 | ||
605 | return *this; | |
606 | } | |
607 | ||
608 | // flips the bit | |
609 | bool operator~() const { return (*(_M_wp) & _S_maskbit(_M_bpos)) == 0; } | |
610 | ||
611 | // for __x = b[i]; | |
612 | operator bool() const { return (*(_M_wp) & _S_maskbit(_M_bpos)) != 0; } | |
613 | ||
614 | // for b[i].flip(); | |
615 | reference& flip() { | |
616 | *_M_wp ^= _S_maskbit(_M_bpos); | |
617 | return *this; | |
618 | } | |
619 | }; | |
620 | ||
621 | // 23.3.5.1 constructors: | |
622 | bitset() {} | |
554241c3 | 623 | bitset(unsigned long __val) : |
768a887c JM |
624 | _Base_bitset<__BITSET_WORDS(_Nb,_WordT), _WordT>(__val) {} |
625 | ||
626 | template<class _CharT, class _Traits, class _Alloc> | |
627 | explicit bitset(const basic_string<_CharT,_Traits,_Alloc>& __s, | |
628 | size_t __pos = 0, | |
1bd0b556 | 629 | size_t __n = size_t(basic_string<_CharT,_Traits,_Alloc>::npos)) |
554241c3 | 630 | : _Base() |
768a887c | 631 | { |
554241c3 | 632 | if (__pos > __s.size()) |
768a887c JM |
633 | __STL_THROW(out_of_range("bitset")); |
634 | _M_copy_from_string(__s, __pos, __n); | |
635 | } | |
636 | ||
637 | // 23.3.5.2 bitset operations: | |
638 | bitset<_Nb,_WordT>& operator&=(const bitset<_Nb,_WordT>& __rhs) { | |
639 | _M_do_and(__rhs); | |
640 | return *this; | |
641 | } | |
642 | ||
643 | bitset<_Nb,_WordT>& operator|=(const bitset<_Nb,_WordT>& __rhs) { | |
644 | _M_do_or(__rhs); | |
645 | return *this; | |
646 | } | |
647 | ||
648 | bitset<_Nb,_WordT>& operator^=(const bitset<_Nb,_WordT>& __rhs) { | |
649 | _M_do_xor(__rhs); | |
650 | return *this; | |
651 | } | |
652 | ||
653 | bitset<_Nb,_WordT>& operator<<=(size_t __pos) { | |
654 | _M_do_left_shift(__pos); | |
655 | _M_do_sanitize(); | |
656 | return *this; | |
657 | } | |
658 | ||
659 | bitset<_Nb,_WordT>& operator>>=(size_t __pos) { | |
660 | _M_do_right_shift(__pos); | |
661 | _M_do_sanitize(); | |
662 | return *this; | |
663 | } | |
664 | ||
665 | // | |
666 | // Extension: | |
667 | // Versions of single-bit set, reset, flip, test with no range checking. | |
668 | // | |
669 | ||
670 | bitset<_Nb,_WordT>& _Unchecked_set(size_t __pos) { | |
671 | _M_getword(__pos) |= _S_maskbit(__pos); | |
672 | return *this; | |
673 | } | |
674 | ||
675 | bitset<_Nb,_WordT>& _Unchecked_set(size_t __pos, int __val) { | |
676 | if (__val) | |
677 | _M_getword(__pos) |= _S_maskbit(__pos); | |
678 | else | |
679 | _M_getword(__pos) &= ~_S_maskbit(__pos); | |
680 | ||
681 | return *this; | |
682 | } | |
683 | ||
684 | bitset<_Nb,_WordT>& _Unchecked_reset(size_t __pos) { | |
685 | _M_getword(__pos) &= ~_S_maskbit(__pos); | |
686 | return *this; | |
687 | } | |
688 | ||
689 | bitset<_Nb,_WordT>& _Unchecked_flip(size_t __pos) { | |
690 | _M_getword(__pos) ^= _S_maskbit(__pos); | |
691 | return *this; | |
692 | } | |
693 | ||
694 | bool _Unchecked_test(size_t __pos) const { | |
695 | return (_M_getword(__pos) & _S_maskbit(__pos)) != static_cast<_WordT>(0); | |
696 | } | |
697 | ||
698 | // Set, reset, and flip. | |
699 | ||
700 | bitset<_Nb,_WordT>& set() { | |
701 | _M_do_set(); | |
702 | _M_do_sanitize(); | |
703 | return *this; | |
704 | } | |
705 | ||
706 | bitset<_Nb,_WordT>& set(size_t __pos) { | |
707 | if (__pos >= _Nb) | |
708 | __STL_THROW(out_of_range("bitset")); | |
709 | ||
710 | return _Unchecked_set(__pos); | |
711 | } | |
712 | ||
713 | bitset<_Nb,_WordT>& set(size_t __pos, int __val) { | |
714 | if (__pos >= _Nb) | |
715 | __STL_THROW(out_of_range("bitset")); | |
716 | ||
717 | return _Unchecked_set(__pos, __val); | |
718 | } | |
719 | ||
720 | bitset<_Nb,_WordT>& reset() { | |
721 | _M_do_reset(); | |
722 | return *this; | |
723 | } | |
724 | ||
725 | bitset<_Nb,_WordT>& reset(size_t __pos) { | |
726 | if (__pos >= _Nb) | |
727 | __STL_THROW(out_of_range("bitset")); | |
728 | ||
729 | return _Unchecked_reset(__pos); | |
730 | } | |
731 | ||
732 | bitset<_Nb,_WordT>& flip() { | |
733 | _M_do_flip(); | |
734 | _M_do_sanitize(); | |
735 | return *this; | |
736 | } | |
737 | ||
738 | bitset<_Nb,_WordT>& flip(size_t __pos) { | |
739 | if (__pos >= _Nb) | |
740 | __STL_THROW(out_of_range("bitset")); | |
741 | ||
742 | return _Unchecked_flip(__pos); | |
743 | } | |
744 | ||
554241c3 | 745 | bitset<_Nb,_WordT> operator~() const { |
768a887c JM |
746 | return bitset<_Nb,_WordT>(*this).flip(); |
747 | } | |
748 | ||
749 | // element access: | |
750 | //for b[i]; | |
751 | reference operator[](size_t __pos) { return reference(*this,__pos); } | |
752 | bool operator[](size_t __pos) const { return _Unchecked_test(__pos); } | |
753 | ||
754 | unsigned long to_ulong() const { return _M_do_to_ulong(); } | |
755 | ||
1bd0b556 | 756 | #ifdef __STL_EXPLICIT_FUNCTION_TMPL_ARGS |
768a887c JM |
757 | template <class _CharT, class _Traits, class _Alloc> |
758 | basic_string<_CharT, _Traits, _Alloc> to_string() const { | |
759 | basic_string<_CharT, _Traits, _Alloc> __result; | |
760 | _M_copy_to_string(__result); | |
761 | return __result; | |
762 | } | |
763 | #endif /* __STL_EXPLICIT_FUNCTION_TMPL_ARGS */ | |
764 | ||
765 | // Helper functions for string operations. | |
766 | template<class _CharT, class _Traits, class _Alloc> | |
767 | void _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, | |
768 | size_t, | |
769 | size_t); | |
770 | ||
771 | // Helper functions for string operations. | |
772 | template<class _CharT, class _Traits, class _Alloc> | |
773 | void _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const; | |
774 | ||
775 | size_t count() const { return _M_do_count(); } | |
776 | ||
777 | size_t size() const { return _Nb; } | |
778 | ||
779 | bool operator==(const bitset<_Nb,_WordT>& __rhs) const { | |
780 | return _M_is_equal(__rhs); | |
781 | } | |
782 | bool operator!=(const bitset<_Nb,_WordT>& __rhs) const { | |
783 | return !_M_is_equal(__rhs); | |
784 | } | |
785 | ||
786 | bool test(size_t __pos) const { | |
787 | if (__pos > _Nb) | |
788 | __STL_THROW(out_of_range("bitset")); | |
789 | ||
790 | return _Unchecked_test(__pos); | |
791 | } | |
792 | ||
793 | bool any() const { return _M_is_any(); } | |
794 | bool none() const { return !_M_is_any(); } | |
795 | ||
796 | bitset<_Nb,_WordT> operator<<(size_t __pos) const | |
797 | { return bitset<_Nb,_WordT>(*this) <<= __pos; } | |
798 | bitset<_Nb,_WordT> operator>>(size_t __pos) const | |
799 | { return bitset<_Nb,_WordT>(*this) >>= __pos; } | |
800 | ||
801 | // | |
802 | // EXTENSIONS: bit-find operations. These operations are | |
803 | // experimental, and are subject to change or removal in future | |
804 | // versions. | |
554241c3 | 805 | // |
768a887c JM |
806 | |
807 | // find the index of the first "on" bit | |
554241c3 | 808 | size_t _Find_first() const |
768a887c JM |
809 | { return _M_do_find_first(_Nb); } |
810 | ||
811 | // find the index of the next "on" bit after prev | |
554241c3 | 812 | size_t _Find_next( size_t __prev ) const |
768a887c JM |
813 | { return _M_do_find_next(__prev, _Nb); } |
814 | ||
815 | }; | |
816 | ||
817 | // | |
818 | // Definitions of non-inline member functions. | |
819 | // | |
820 | ||
821 | template <size_t _Nb, class _WordT> | |
822 | template<class _CharT, class _Traits, class _Alloc> | |
823 | void bitset<_Nb, _WordT> | |
824 | ::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, | |
825 | size_t __pos, | |
826 | size_t __n) | |
827 | { | |
828 | reset(); | |
829 | const size_t __nbits = min(_Nb, min(__n, __s.size() - __pos)); | |
830 | for (size_t __i = 0; __i < __nbits; ++__i) { | |
831 | switch(__s[__pos + __nbits - __i - 1]) { | |
832 | case '0': | |
833 | break; | |
834 | case '1': | |
835 | set(__i); | |
836 | break; | |
837 | default: | |
838 | __STL_THROW(invalid_argument("bitset")); | |
839 | } | |
840 | } | |
841 | } | |
842 | ||
843 | template <size_t _Nb, class _WordT> | |
844 | template <class _CharT, class _Traits, class _Alloc> | |
845 | void bitset<_Nb, _WordT> | |
846 | ::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const | |
847 | { | |
848 | __s.assign(_Nb, '0'); | |
554241c3 UD |
849 | |
850 | for (size_t __i = 0; __i < _Nb; ++__i) | |
768a887c JM |
851 | if (_Unchecked_test(__i)) |
852 | __s[_Nb - 1 - __i] = '1'; | |
853 | } | |
854 | ||
855 | // ------------------------------------------------------------ | |
856 | ||
857 | // | |
858 | // 23.3.5.3 bitset operations: | |
859 | // | |
860 | ||
861 | template <size_t _Nb, class _WordT> | |
862 | inline bitset<_Nb,_WordT> operator&(const bitset<_Nb,_WordT>& __x, | |
863 | const bitset<_Nb,_WordT>& __y) { | |
864 | bitset<_Nb,_WordT> __result(__x); | |
865 | __result &= __y; | |
866 | return __result; | |
867 | } | |
868 | ||
869 | ||
870 | template <size_t _Nb, class _WordT> | |
871 | inline bitset<_Nb,_WordT> operator|(const bitset<_Nb,_WordT>& __x, | |
872 | const bitset<_Nb,_WordT>& __y) { | |
873 | bitset<_Nb,_WordT> __result(__x); | |
874 | __result |= __y; | |
875 | return __result; | |
876 | } | |
877 | ||
878 | template <size_t _Nb, class _WordT> | |
879 | inline bitset<_Nb,_WordT> operator^(const bitset<_Nb,_WordT>& __x, | |
880 | const bitset<_Nb,_WordT>& __y) { | |
881 | bitset<_Nb,_WordT> __result(__x); | |
882 | __result ^= __y; | |
883 | return __result; | |
884 | } | |
885 | ||
886 | // NOTE: these must be rewritten once we have templatized iostreams. | |
887 | ||
888 | template <size_t _Nb, class _WordT> | |
889 | istream& | |
890 | operator>>(istream& __is, bitset<_Nb,_WordT>& __x) { | |
891 | string __tmp; | |
892 | __tmp.reserve(_Nb); | |
893 | ||
894 | // In new templatized iostreams, use istream::sentry | |
895 | if (__is.flags() & ios::skipws) { | |
896 | char __c; | |
554241c3 | 897 | do |
768a887c JM |
898 | __is.get(__c); |
899 | while (__is && isspace(__c)); | |
900 | if (__is) | |
901 | __is.putback(__c); | |
902 | } | |
903 | ||
904 | for (size_t __i = 0; __i < _Nb; ++__i) { | |
905 | char __c; | |
906 | __is.get(__c); | |
907 | ||
908 | if (!__is) | |
909 | break; | |
910 | else if (__c != '0' && __c != '1') { | |
911 | __is.putback(__c); | |
912 | break; | |
913 | } | |
914 | else | |
915 | __tmp.push_back(__c); | |
916 | } | |
917 | ||
554241c3 | 918 | if (__tmp.empty()) |
768a887c JM |
919 | __is.clear(__is.rdstate() | ios::failbit); |
920 | else | |
921 | __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb); | |
922 | ||
923 | return __is; | |
924 | } | |
925 | ||
926 | template <size_t _Nb, class _WordT> | |
927 | ostream& operator<<(ostream& __os, const bitset<_Nb,_WordT>& __x) { | |
928 | string __tmp; | |
929 | __x._M_copy_to_string(__tmp); | |
930 | return __os << __tmp; | |
931 | } | |
932 | ||
933 | // ------------------------------------------------------------ | |
934 | // Lookup tables for find and count operations. | |
935 | ||
936 | template<bool __dummy> | |
937 | unsigned char _Bit_count<__dummy>::_S_bit_count[] = { | |
938 | 0, /* 0 */ 1, /* 1 */ 1, /* 2 */ 2, /* 3 */ 1, /* 4 */ | |
939 | 2, /* 5 */ 2, /* 6 */ 3, /* 7 */ 1, /* 8 */ 2, /* 9 */ | |
940 | 2, /* 10 */ 3, /* 11 */ 2, /* 12 */ 3, /* 13 */ 3, /* 14 */ | |
941 | 4, /* 15 */ 1, /* 16 */ 2, /* 17 */ 2, /* 18 */ 3, /* 19 */ | |
942 | 2, /* 20 */ 3, /* 21 */ 3, /* 22 */ 4, /* 23 */ 2, /* 24 */ | |
943 | 3, /* 25 */ 3, /* 26 */ 4, /* 27 */ 3, /* 28 */ 4, /* 29 */ | |
944 | 4, /* 30 */ 5, /* 31 */ 1, /* 32 */ 2, /* 33 */ 2, /* 34 */ | |
945 | 3, /* 35 */ 2, /* 36 */ 3, /* 37 */ 3, /* 38 */ 4, /* 39 */ | |
946 | 2, /* 40 */ 3, /* 41 */ 3, /* 42 */ 4, /* 43 */ 3, /* 44 */ | |
947 | 4, /* 45 */ 4, /* 46 */ 5, /* 47 */ 2, /* 48 */ 3, /* 49 */ | |
948 | 3, /* 50 */ 4, /* 51 */ 3, /* 52 */ 4, /* 53 */ 4, /* 54 */ | |
949 | 5, /* 55 */ 3, /* 56 */ 4, /* 57 */ 4, /* 58 */ 5, /* 59 */ | |
950 | 4, /* 60 */ 5, /* 61 */ 5, /* 62 */ 6, /* 63 */ 1, /* 64 */ | |
951 | 2, /* 65 */ 2, /* 66 */ 3, /* 67 */ 2, /* 68 */ 3, /* 69 */ | |
952 | 3, /* 70 */ 4, /* 71 */ 2, /* 72 */ 3, /* 73 */ 3, /* 74 */ | |
953 | 4, /* 75 */ 3, /* 76 */ 4, /* 77 */ 4, /* 78 */ 5, /* 79 */ | |
954 | 2, /* 80 */ 3, /* 81 */ 3, /* 82 */ 4, /* 83 */ 3, /* 84 */ | |
955 | 4, /* 85 */ 4, /* 86 */ 5, /* 87 */ 3, /* 88 */ 4, /* 89 */ | |
956 | 4, /* 90 */ 5, /* 91 */ 4, /* 92 */ 5, /* 93 */ 5, /* 94 */ | |
957 | 6, /* 95 */ 2, /* 96 */ 3, /* 97 */ 3, /* 98 */ 4, /* 99 */ | |
958 | 3, /* 100 */ 4, /* 101 */ 4, /* 102 */ 5, /* 103 */ 3, /* 104 */ | |
959 | 4, /* 105 */ 4, /* 106 */ 5, /* 107 */ 4, /* 108 */ 5, /* 109 */ | |
960 | 5, /* 110 */ 6, /* 111 */ 3, /* 112 */ 4, /* 113 */ 4, /* 114 */ | |
961 | 5, /* 115 */ 4, /* 116 */ 5, /* 117 */ 5, /* 118 */ 6, /* 119 */ | |
962 | 4, /* 120 */ 5, /* 121 */ 5, /* 122 */ 6, /* 123 */ 5, /* 124 */ | |
963 | 6, /* 125 */ 6, /* 126 */ 7, /* 127 */ 1, /* 128 */ 2, /* 129 */ | |
964 | 2, /* 130 */ 3, /* 131 */ 2, /* 132 */ 3, /* 133 */ 3, /* 134 */ | |
965 | 4, /* 135 */ 2, /* 136 */ 3, /* 137 */ 3, /* 138 */ 4, /* 139 */ | |
966 | 3, /* 140 */ 4, /* 141 */ 4, /* 142 */ 5, /* 143 */ 2, /* 144 */ | |
967 | 3, /* 145 */ 3, /* 146 */ 4, /* 147 */ 3, /* 148 */ 4, /* 149 */ | |
968 | 4, /* 150 */ 5, /* 151 */ 3, /* 152 */ 4, /* 153 */ 4, /* 154 */ | |
969 | 5, /* 155 */ 4, /* 156 */ 5, /* 157 */ 5, /* 158 */ 6, /* 159 */ | |
970 | 2, /* 160 */ 3, /* 161 */ 3, /* 162 */ 4, /* 163 */ 3, /* 164 */ | |
971 | 4, /* 165 */ 4, /* 166 */ 5, /* 167 */ 3, /* 168 */ 4, /* 169 */ | |
972 | 4, /* 170 */ 5, /* 171 */ 4, /* 172 */ 5, /* 173 */ 5, /* 174 */ | |
973 | 6, /* 175 */ 3, /* 176 */ 4, /* 177 */ 4, /* 178 */ 5, /* 179 */ | |
974 | 4, /* 180 */ 5, /* 181 */ 5, /* 182 */ 6, /* 183 */ 4, /* 184 */ | |
975 | 5, /* 185 */ 5, /* 186 */ 6, /* 187 */ 5, /* 188 */ 6, /* 189 */ | |
976 | 6, /* 190 */ 7, /* 191 */ 2, /* 192 */ 3, /* 193 */ 3, /* 194 */ | |
977 | 4, /* 195 */ 3, /* 196 */ 4, /* 197 */ 4, /* 198 */ 5, /* 199 */ | |
978 | 3, /* 200 */ 4, /* 201 */ 4, /* 202 */ 5, /* 203 */ 4, /* 204 */ | |
979 | 5, /* 205 */ 5, /* 206 */ 6, /* 207 */ 3, /* 208 */ 4, /* 209 */ | |
980 | 4, /* 210 */ 5, /* 211 */ 4, /* 212 */ 5, /* 213 */ 5, /* 214 */ | |
981 | 6, /* 215 */ 4, /* 216 */ 5, /* 217 */ 5, /* 218 */ 6, /* 219 */ | |
982 | 5, /* 220 */ 6, /* 221 */ 6, /* 222 */ 7, /* 223 */ 3, /* 224 */ | |
983 | 4, /* 225 */ 4, /* 226 */ 5, /* 227 */ 4, /* 228 */ 5, /* 229 */ | |
984 | 5, /* 230 */ 6, /* 231 */ 4, /* 232 */ 5, /* 233 */ 5, /* 234 */ | |
985 | 6, /* 235 */ 5, /* 236 */ 6, /* 237 */ 6, /* 238 */ 7, /* 239 */ | |
986 | 4, /* 240 */ 5, /* 241 */ 5, /* 242 */ 6, /* 243 */ 5, /* 244 */ | |
987 | 6, /* 245 */ 6, /* 246 */ 7, /* 247 */ 5, /* 248 */ 6, /* 249 */ | |
988 | 6, /* 250 */ 7, /* 251 */ 6, /* 252 */ 7, /* 253 */ 7, /* 254 */ | |
989 | 8 /* 255 */ | |
990 | }; // end _Bit_count | |
991 | ||
992 | template<bool __dummy> | |
993 | unsigned char _First_one<__dummy>::_S_first_one[] = { | |
994 | 0, /* 0 */ 0, /* 1 */ 1, /* 2 */ 0, /* 3 */ 2, /* 4 */ | |
995 | 0, /* 5 */ 1, /* 6 */ 0, /* 7 */ 3, /* 8 */ 0, /* 9 */ | |
996 | 1, /* 10 */ 0, /* 11 */ 2, /* 12 */ 0, /* 13 */ 1, /* 14 */ | |
997 | 0, /* 15 */ 4, /* 16 */ 0, /* 17 */ 1, /* 18 */ 0, /* 19 */ | |
998 | 2, /* 20 */ 0, /* 21 */ 1, /* 22 */ 0, /* 23 */ 3, /* 24 */ | |
999 | 0, /* 25 */ 1, /* 26 */ 0, /* 27 */ 2, /* 28 */ 0, /* 29 */ | |
1000 | 1, /* 30 */ 0, /* 31 */ 5, /* 32 */ 0, /* 33 */ 1, /* 34 */ | |
1001 | 0, /* 35 */ 2, /* 36 */ 0, /* 37 */ 1, /* 38 */ 0, /* 39 */ | |
1002 | 3, /* 40 */ 0, /* 41 */ 1, /* 42 */ 0, /* 43 */ 2, /* 44 */ | |
1003 | 0, /* 45 */ 1, /* 46 */ 0, /* 47 */ 4, /* 48 */ 0, /* 49 */ | |
1004 | 1, /* 50 */ 0, /* 51 */ 2, /* 52 */ 0, /* 53 */ 1, /* 54 */ | |
1005 | 0, /* 55 */ 3, /* 56 */ 0, /* 57 */ 1, /* 58 */ 0, /* 59 */ | |
1006 | 2, /* 60 */ 0, /* 61 */ 1, /* 62 */ 0, /* 63 */ 6, /* 64 */ | |
1007 | 0, /* 65 */ 1, /* 66 */ 0, /* 67 */ 2, /* 68 */ 0, /* 69 */ | |
1008 | 1, /* 70 */ 0, /* 71 */ 3, /* 72 */ 0, /* 73 */ 1, /* 74 */ | |
1009 | 0, /* 75 */ 2, /* 76 */ 0, /* 77 */ 1, /* 78 */ 0, /* 79 */ | |
1010 | 4, /* 80 */ 0, /* 81 */ 1, /* 82 */ 0, /* 83 */ 2, /* 84 */ | |
1011 | 0, /* 85 */ 1, /* 86 */ 0, /* 87 */ 3, /* 88 */ 0, /* 89 */ | |
1012 | 1, /* 90 */ 0, /* 91 */ 2, /* 92 */ 0, /* 93 */ 1, /* 94 */ | |
1013 | 0, /* 95 */ 5, /* 96 */ 0, /* 97 */ 1, /* 98 */ 0, /* 99 */ | |
1014 | 2, /* 100 */ 0, /* 101 */ 1, /* 102 */ 0, /* 103 */ 3, /* 104 */ | |
1015 | 0, /* 105 */ 1, /* 106 */ 0, /* 107 */ 2, /* 108 */ 0, /* 109 */ | |
1016 | 1, /* 110 */ 0, /* 111 */ 4, /* 112 */ 0, /* 113 */ 1, /* 114 */ | |
1017 | 0, /* 115 */ 2, /* 116 */ 0, /* 117 */ 1, /* 118 */ 0, /* 119 */ | |
1018 | 3, /* 120 */ 0, /* 121 */ 1, /* 122 */ 0, /* 123 */ 2, /* 124 */ | |
1019 | 0, /* 125 */ 1, /* 126 */ 0, /* 127 */ 7, /* 128 */ 0, /* 129 */ | |
1020 | 1, /* 130 */ 0, /* 131 */ 2, /* 132 */ 0, /* 133 */ 1, /* 134 */ | |
1021 | 0, /* 135 */ 3, /* 136 */ 0, /* 137 */ 1, /* 138 */ 0, /* 139 */ | |
1022 | 2, /* 140 */ 0, /* 141 */ 1, /* 142 */ 0, /* 143 */ 4, /* 144 */ | |
1023 | 0, /* 145 */ 1, /* 146 */ 0, /* 147 */ 2, /* 148 */ 0, /* 149 */ | |
1024 | 1, /* 150 */ 0, /* 151 */ 3, /* 152 */ 0, /* 153 */ 1, /* 154 */ | |
1025 | 0, /* 155 */ 2, /* 156 */ 0, /* 157 */ 1, /* 158 */ 0, /* 159 */ | |
1026 | 5, /* 160 */ 0, /* 161 */ 1, /* 162 */ 0, /* 163 */ 2, /* 164 */ | |
1027 | 0, /* 165 */ 1, /* 166 */ 0, /* 167 */ 3, /* 168 */ 0, /* 169 */ | |
1028 | 1, /* 170 */ 0, /* 171 */ 2, /* 172 */ 0, /* 173 */ 1, /* 174 */ | |
1029 | 0, /* 175 */ 4, /* 176 */ 0, /* 177 */ 1, /* 178 */ 0, /* 179 */ | |
1030 | 2, /* 180 */ 0, /* 181 */ 1, /* 182 */ 0, /* 183 */ 3, /* 184 */ | |
1031 | 0, /* 185 */ 1, /* 186 */ 0, /* 187 */ 2, /* 188 */ 0, /* 189 */ | |
1032 | 1, /* 190 */ 0, /* 191 */ 6, /* 192 */ 0, /* 193 */ 1, /* 194 */ | |
1033 | 0, /* 195 */ 2, /* 196 */ 0, /* 197 */ 1, /* 198 */ 0, /* 199 */ | |
1034 | 3, /* 200 */ 0, /* 201 */ 1, /* 202 */ 0, /* 203 */ 2, /* 204 */ | |
1035 | 0, /* 205 */ 1, /* 206 */ 0, /* 207 */ 4, /* 208 */ 0, /* 209 */ | |
1036 | 1, /* 210 */ 0, /* 211 */ 2, /* 212 */ 0, /* 213 */ 1, /* 214 */ | |
1037 | 0, /* 215 */ 3, /* 216 */ 0, /* 217 */ 1, /* 218 */ 0, /* 219 */ | |
1038 | 2, /* 220 */ 0, /* 221 */ 1, /* 222 */ 0, /* 223 */ 5, /* 224 */ | |
1039 | 0, /* 225 */ 1, /* 226 */ 0, /* 227 */ 2, /* 228 */ 0, /* 229 */ | |
1040 | 1, /* 230 */ 0, /* 231 */ 3, /* 232 */ 0, /* 233 */ 1, /* 234 */ | |
1041 | 0, /* 235 */ 2, /* 236 */ 0, /* 237 */ 1, /* 238 */ 0, /* 239 */ | |
1042 | 4, /* 240 */ 0, /* 241 */ 1, /* 242 */ 0, /* 243 */ 2, /* 244 */ | |
1043 | 0, /* 245 */ 1, /* 246 */ 0, /* 247 */ 3, /* 248 */ 0, /* 249 */ | |
1044 | 1, /* 250 */ 0, /* 251 */ 2, /* 252 */ 0, /* 253 */ 1, /* 254 */ | |
1045 | 0, /* 255 */ | |
1046 | }; // end _First_one | |
1047 | ||
1048 | #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) | |
1049 | #pragma reset woff 1209 | |
1050 | #endif | |
1051 | ||
1052 | __STL_END_NAMESPACE | |
1053 | ||
1054 | ||
1055 | #undef __BITS_PER_WORDT | |
1056 | #undef __BITSET_WORDS | |
1057 | ||
1058 | #endif /* __SGI_STL_BITSET */ | |
1059 | ||
1060 | ||
1061 | // Local Variables: | |
1062 | // mode:C++ | |
1063 | // End: |