std_bitset.h revision 117397
197403Sobrien// <bitset> -*- C++ -*- 297403Sobrien 397403Sobrien// Copyright (C) 2001, 2002 Free Software Foundation, Inc. 497403Sobrien// 597403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 697403Sobrien// software; you can redistribute it and/or modify it under the 797403Sobrien// terms of the GNU General Public License as published by the 897403Sobrien// Free Software Foundation; either version 2, or (at your option) 997403Sobrien// any later version. 1097403Sobrien 1197403Sobrien// This library is distributed in the hope that it will be useful, 1297403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1397403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1497403Sobrien// GNU General Public License for more details. 1597403Sobrien 1697403Sobrien// You should have received a copy of the GNU General Public License along 1797403Sobrien// with this library; see the file COPYING. If not, write to the Free 1897403Sobrien// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 1997403Sobrien// USA. 2097403Sobrien 2197403Sobrien// As a special exception, you may use this file as part of a free software 2297403Sobrien// library without restriction. Specifically, if other files instantiate 2397403Sobrien// templates or use macros or inline functions from this file, or you compile 2497403Sobrien// this file and link it with other files to produce an executable, this 2597403Sobrien// file does not by itself cause the resulting executable to be covered by 2697403Sobrien// the GNU General Public License. This exception does not however 2797403Sobrien// invalidate any other reasons why the executable file might be covered by 2897403Sobrien// the GNU General Public License. 2997403Sobrien 3097403Sobrien/* 3197403Sobrien * Copyright (c) 1998 3297403Sobrien * Silicon Graphics Computer Systems, Inc. 3397403Sobrien * 3497403Sobrien * Permission to use, copy, modify, distribute and sell this software 3597403Sobrien * and its documentation for any purpose is hereby granted without fee, 3697403Sobrien * provided that the above copyright notice appear in all copies and 3797403Sobrien * that both that copyright notice and this permission notice appear 3897403Sobrien * in supporting documentation. Silicon Graphics makes no 3997403Sobrien * representations about the suitability of this software for any 4097403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4197403Sobrien */ 4297403Sobrien 4397403Sobrien/** @file bitset 4497403Sobrien * This is a Standard C++ Library header. You should @c #include this header 4597403Sobrien * in your programs, rather than any of the "st[dl]_*.h" implementation files. 4697403Sobrien */ 4797403Sobrien 4897403Sobrien#ifndef _GLIBCPP_BITSET_H 4997403Sobrien#define _GLIBCPP_BITSET_H 5097403Sobrien 5197403Sobrien#pragma GCC system_header 5297403Sobrien 5397403Sobrien#include <cstddef> // for size_t 5497403Sobrien#include <cstring> // for memset 5597403Sobrien#include <string> 5697403Sobrien#include <bits/functexcept.h> // for invalid_argument, out_of_range, 5797403Sobrien // overflow_error 5897403Sobrien#include <ostream> // for ostream (operator<<) 5997403Sobrien#include <istream> // for istream (operator>>) 6097403Sobrien 6197403Sobrien 6297403Sobrien#define _GLIBCPP_BITSET_BITS_PER_WORD (CHAR_BIT*sizeof(unsigned long)) 6397403Sobrien#define _GLIBCPP_BITSET_WORDS(__n) \ 64102782Skan ((__n) < 1 ? 0 : ((__n) + _GLIBCPP_BITSET_BITS_PER_WORD - 1)/_GLIBCPP_BITSET_BITS_PER_WORD) 6597403Sobrien 6697403Sobriennamespace std 6797403Sobrien{ 6897403Sobrien extern unsigned char _S_bit_count[256]; 6997403Sobrien extern unsigned char _S_first_one[256]; 7097403Sobrien 7197403Sobrien /** 7297403Sobrien * @if maint 7397403Sobrien * Base class, general case. It is a class inveriant that _Nw will be 7497403Sobrien * nonnegative. 7597403Sobrien * 7697403Sobrien * See documentation for bitset. 7797403Sobrien * @endif 7897403Sobrien */ 7997403Sobrien template<size_t _Nw> 8097403Sobrien struct _Base_bitset 8197403Sobrien { 8297403Sobrien typedef unsigned long _WordT; 8397403Sobrien 8497403Sobrien /// 0 is the least significant word. 8597403Sobrien _WordT _M_w[_Nw]; 8697403Sobrien 8797403Sobrien _Base_bitset() { _M_do_reset(); } 8897403Sobrien _Base_bitset(unsigned long __val) 8997403Sobrien { 9097403Sobrien _M_do_reset(); 9197403Sobrien _M_w[0] = __val; 9297403Sobrien } 9397403Sobrien 9497403Sobrien static size_t 9597403Sobrien _S_whichword(size_t __pos ) 9697403Sobrien { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; } 9797403Sobrien 9897403Sobrien static size_t 9997403Sobrien _S_whichbyte(size_t __pos ) 10097403Sobrien { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; } 10197403Sobrien 10297403Sobrien static size_t 10397403Sobrien _S_whichbit(size_t __pos ) 10497403Sobrien { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; } 10597403Sobrien 10697403Sobrien static _WordT 10797403Sobrien _S_maskbit(size_t __pos ) 10897403Sobrien { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 10997403Sobrien 11097403Sobrien _WordT& 11197403Sobrien _M_getword(size_t __pos) 11297403Sobrien { return _M_w[_S_whichword(__pos)]; } 11397403Sobrien 11497403Sobrien _WordT 11597403Sobrien _M_getword(size_t __pos) const 11697403Sobrien { return _M_w[_S_whichword(__pos)]; } 11797403Sobrien 11897403Sobrien _WordT& 11997403Sobrien _M_hiword() { return _M_w[_Nw - 1]; } 12097403Sobrien 12197403Sobrien _WordT 12297403Sobrien _M_hiword() const { return _M_w[_Nw - 1]; } 12397403Sobrien 12497403Sobrien void 12597403Sobrien _M_do_and(const _Base_bitset<_Nw>& __x) 12697403Sobrien { 12797403Sobrien for (size_t __i = 0; __i < _Nw; __i++) 12897403Sobrien _M_w[__i] &= __x._M_w[__i]; 12997403Sobrien } 13097403Sobrien 13197403Sobrien void 13297403Sobrien _M_do_or(const _Base_bitset<_Nw>& __x) 13397403Sobrien { 13497403Sobrien for (size_t __i = 0; __i < _Nw; __i++) 13597403Sobrien _M_w[__i] |= __x._M_w[__i]; 13697403Sobrien } 13797403Sobrien 13897403Sobrien void 13997403Sobrien _M_do_xor(const _Base_bitset<_Nw>& __x) 14097403Sobrien { 14197403Sobrien for (size_t __i = 0; __i < _Nw; __i++) 14297403Sobrien _M_w[__i] ^= __x._M_w[__i]; 14397403Sobrien } 14497403Sobrien 14597403Sobrien void 14697403Sobrien _M_do_left_shift(size_t __shift); 14797403Sobrien 14897403Sobrien void 14997403Sobrien _M_do_right_shift(size_t __shift); 15097403Sobrien 15197403Sobrien void 15297403Sobrien _M_do_flip() 15397403Sobrien { 15497403Sobrien for (size_t __i = 0; __i < _Nw; __i++) 15597403Sobrien _M_w[__i] = ~_M_w[__i]; 15697403Sobrien } 15797403Sobrien 15897403Sobrien void 15997403Sobrien _M_do_set() 16097403Sobrien { 16197403Sobrien for (size_t __i = 0; __i < _Nw; __i++) 16297403Sobrien _M_w[__i] = ~static_cast<_WordT>(0); 16397403Sobrien } 16497403Sobrien 16597403Sobrien void 16697403Sobrien _M_do_reset() { memset(_M_w, 0, _Nw * sizeof(_WordT)); } 16797403Sobrien 16897403Sobrien bool 16997403Sobrien _M_is_equal(const _Base_bitset<_Nw>& __x) const 17097403Sobrien { 17197403Sobrien for (size_t __i = 0; __i < _Nw; ++__i) 17297403Sobrien { 17397403Sobrien if (_M_w[__i] != __x._M_w[__i]) 17497403Sobrien return false; 17597403Sobrien } 17697403Sobrien return true; 17797403Sobrien } 17897403Sobrien 17997403Sobrien bool 18097403Sobrien _M_is_any() const 18197403Sobrien { 18297403Sobrien for (size_t __i = 0; __i < _Nw; __i++) 18397403Sobrien { 18497403Sobrien if (_M_w[__i] != static_cast<_WordT>(0)) 18597403Sobrien return true; 18697403Sobrien } 18797403Sobrien return false; 18897403Sobrien } 18997403Sobrien 19097403Sobrien size_t 19197403Sobrien _M_do_count() const 19297403Sobrien { 19397403Sobrien size_t __result = 0; 19497403Sobrien const unsigned char* __byte_ptr = (const unsigned char*)_M_w; 19597403Sobrien const unsigned char* __end_ptr = (const unsigned char*)(_M_w + _Nw); 19697403Sobrien 19797403Sobrien while ( __byte_ptr < __end_ptr ) 19897403Sobrien { 19997403Sobrien __result += _S_bit_count[*__byte_ptr]; 20097403Sobrien __byte_ptr++; 20197403Sobrien } 20297403Sobrien return __result; 20397403Sobrien } 20497403Sobrien 20597403Sobrien unsigned long 20697403Sobrien _M_do_to_ulong() const; 20797403Sobrien 20897403Sobrien // find first "on" bit 20997403Sobrien size_t 21097403Sobrien _M_do_find_first(size_t __not_found) const; 21197403Sobrien 21297403Sobrien // find the next "on" bit that follows "prev" 21397403Sobrien size_t 21497403Sobrien _M_do_find_next(size_t __prev, size_t __not_found) const; 21597403Sobrien }; 21697403Sobrien 21797403Sobrien // Definitions of non-inline functions from _Base_bitset. 21897403Sobrien template<size_t _Nw> 21997403Sobrien void 22097403Sobrien _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) 22197403Sobrien { 222117397Skan if (__builtin_expect(__shift != 0, 1)) 22397403Sobrien { 22497403Sobrien const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD; 22597403Sobrien const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD; 22697403Sobrien 22797403Sobrien if (__offset == 0) 22897403Sobrien for (size_t __n = _Nw - 1; __n >= __wshift; --__n) 22997403Sobrien _M_w[__n] = _M_w[__n - __wshift]; 23097403Sobrien else 23197403Sobrien { 23297403Sobrien const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset; 23397403Sobrien for (size_t __n = _Nw - 1; __n > __wshift; --__n) 23497403Sobrien _M_w[__n] = (_M_w[__n - __wshift] << __offset) | 23597403Sobrien (_M_w[__n - __wshift - 1] >> __sub_offset); 23697403Sobrien _M_w[__wshift] = _M_w[0] << __offset; 23797403Sobrien } 23897403Sobrien 23997403Sobrien fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0)); 24097403Sobrien } 24197403Sobrien } 24297403Sobrien 24397403Sobrien template<size_t _Nw> 24497403Sobrien void 24597403Sobrien _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) 24697403Sobrien { 247117397Skan if (__builtin_expect(__shift != 0, 1)) 24897403Sobrien { 24997403Sobrien const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD; 25097403Sobrien const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD; 25197403Sobrien const size_t __limit = _Nw - __wshift - 1; 25297403Sobrien 25397403Sobrien if (__offset == 0) 25497403Sobrien for (size_t __n = 0; __n <= __limit; ++__n) 25597403Sobrien _M_w[__n] = _M_w[__n + __wshift]; 25697403Sobrien else 25797403Sobrien { 25897403Sobrien const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset; 25997403Sobrien for (size_t __n = 0; __n < __limit; ++__n) 26097403Sobrien _M_w[__n] = (_M_w[__n + __wshift] >> __offset) | 26197403Sobrien (_M_w[__n + __wshift + 1] << __sub_offset); 26297403Sobrien _M_w[__limit] = _M_w[_Nw-1] >> __offset; 26397403Sobrien } 26497403Sobrien 26597403Sobrien fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0)); 26697403Sobrien } 26797403Sobrien } 26897403Sobrien 26997403Sobrien template<size_t _Nw> 27097403Sobrien unsigned long 27197403Sobrien _Base_bitset<_Nw>::_M_do_to_ulong() const 27297403Sobrien { 27397403Sobrien for (size_t __i = 1; __i < _Nw; ++__i) 27497403Sobrien if (_M_w[__i]) 27597403Sobrien __throw_overflow_error("bitset -- too large to fit in unsigned long"); 27697403Sobrien return _M_w[0]; 27797403Sobrien } 27897403Sobrien 27997403Sobrien template<size_t _Nw> 28097403Sobrien size_t 28197403Sobrien _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const 28297403Sobrien { 28397403Sobrien for (size_t __i = 0; __i < _Nw; __i++ ) 28497403Sobrien { 28597403Sobrien _WordT __thisword = _M_w[__i]; 28697403Sobrien if ( __thisword != static_cast<_WordT>(0) ) 28797403Sobrien { 28897403Sobrien // find byte within word 28997403Sobrien for (size_t __j = 0; __j < sizeof(_WordT); __j++ ) 29097403Sobrien { 29197403Sobrien unsigned char __this_byte 29297403Sobrien = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); 29397403Sobrien if (__this_byte) 29497403Sobrien return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT + 29597403Sobrien _S_first_one[__this_byte]; 29697403Sobrien 29797403Sobrien __thisword >>= CHAR_BIT; 29897403Sobrien } 29997403Sobrien } 30097403Sobrien } 30197403Sobrien // not found, so return an indication of failure. 30297403Sobrien return __not_found; 30397403Sobrien } 30497403Sobrien 30597403Sobrien template<size_t _Nw> 30697403Sobrien size_t 30797403Sobrien _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const 30897403Sobrien { 30997403Sobrien // make bound inclusive 31097403Sobrien ++__prev; 31197403Sobrien 31297403Sobrien // check out of bounds 31397403Sobrien if ( __prev >= _Nw * _GLIBCPP_BITSET_BITS_PER_WORD ) 31497403Sobrien return __not_found; 31597403Sobrien 31697403Sobrien // search first word 31797403Sobrien size_t __i = _S_whichword(__prev); 31897403Sobrien _WordT __thisword = _M_w[__i]; 31997403Sobrien 32097403Sobrien // mask off bits below bound 32197403Sobrien __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 32297403Sobrien 32397403Sobrien if ( __thisword != static_cast<_WordT>(0) ) 32497403Sobrien { 32597403Sobrien // find byte within word 32697403Sobrien // get first byte into place 32797403Sobrien __thisword >>= _S_whichbyte(__prev) * CHAR_BIT; 32897403Sobrien for (size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++) 32997403Sobrien { 33097403Sobrien unsigned char __this_byte 33197403Sobrien = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); 33297403Sobrien if ( __this_byte ) 33397403Sobrien return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT + 33497403Sobrien _S_first_one[__this_byte]; 33597403Sobrien 33697403Sobrien __thisword >>= CHAR_BIT; 33797403Sobrien } 33897403Sobrien } 33997403Sobrien 34097403Sobrien // check subsequent words 34197403Sobrien __i++; 34297403Sobrien for ( ; __i < _Nw; __i++ ) 34397403Sobrien { 34497403Sobrien __thisword = _M_w[__i]; 34597403Sobrien if ( __thisword != static_cast<_WordT>(0) ) 34697403Sobrien { 34797403Sobrien // find byte within word 34897403Sobrien for (size_t __j = 0; __j < sizeof(_WordT); __j++ ) 34997403Sobrien { 35097403Sobrien unsigned char __this_byte 35197403Sobrien = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); 35297403Sobrien if ( __this_byte ) 35397403Sobrien return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT + 35497403Sobrien _S_first_one[__this_byte]; 35597403Sobrien 35697403Sobrien __thisword >>= CHAR_BIT; 35797403Sobrien } 35897403Sobrien } 35997403Sobrien } 36097403Sobrien // not found, so return an indication of failure. 36197403Sobrien return __not_found; 36297403Sobrien } // end _M_do_find_next 36397403Sobrien 36497403Sobrien 36597403Sobrien /** 36697403Sobrien * @if maint 36797403Sobrien * Base class, specialization for a single word. 36897403Sobrien * 36997403Sobrien * See documentation for bitset. 37097403Sobrien * @endif 37197403Sobrien */ 37297403Sobrien template<> 37397403Sobrien struct _Base_bitset<1> 37497403Sobrien { 37597403Sobrien typedef unsigned long _WordT; 37697403Sobrien _WordT _M_w; 37797403Sobrien 37897403Sobrien _Base_bitset( void ) : _M_w(0) {} 37997403Sobrien _Base_bitset(unsigned long __val) : _M_w(__val) {} 38097403Sobrien 38197403Sobrien static size_t 38297403Sobrien _S_whichword(size_t __pos ) 38397403Sobrien { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; } 38497403Sobrien 38597403Sobrien static size_t 38697403Sobrien _S_whichbyte(size_t __pos ) 38797403Sobrien { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; } 38897403Sobrien 38997403Sobrien static size_t 39097403Sobrien _S_whichbit(size_t __pos ) 39197403Sobrien { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; } 39297403Sobrien 39397403Sobrien static _WordT 39497403Sobrien _S_maskbit(size_t __pos ) 39597403Sobrien { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 39697403Sobrien 39797403Sobrien _WordT& 39897403Sobrien _M_getword(size_t) { return _M_w; } 39997403Sobrien 40097403Sobrien _WordT 40197403Sobrien _M_getword(size_t) const { return _M_w; } 40297403Sobrien 40397403Sobrien _WordT& 40497403Sobrien _M_hiword() { return _M_w; } 40597403Sobrien 40697403Sobrien _WordT 40797403Sobrien _M_hiword() const { return _M_w; } 40897403Sobrien 40997403Sobrien void 41097403Sobrien _M_do_and(const _Base_bitset<1>& __x) { _M_w &= __x._M_w; } 41197403Sobrien 41297403Sobrien void 41397403Sobrien _M_do_or(const _Base_bitset<1>& __x) { _M_w |= __x._M_w; } 41497403Sobrien 41597403Sobrien void 41697403Sobrien _M_do_xor(const _Base_bitset<1>& __x) { _M_w ^= __x._M_w; } 41797403Sobrien 41897403Sobrien void 41997403Sobrien _M_do_left_shift(size_t __shift) { _M_w <<= __shift; } 42097403Sobrien 42197403Sobrien void 42297403Sobrien _M_do_right_shift(size_t __shift) { _M_w >>= __shift; } 42397403Sobrien 42497403Sobrien void 42597403Sobrien _M_do_flip() { _M_w = ~_M_w; } 42697403Sobrien 42797403Sobrien void 42897403Sobrien _M_do_set() { _M_w = ~static_cast<_WordT>(0); } 42997403Sobrien 43097403Sobrien void 43197403Sobrien _M_do_reset() { _M_w = 0; } 43297403Sobrien 43397403Sobrien bool 43497403Sobrien _M_is_equal(const _Base_bitset<1>& __x) const 43597403Sobrien { return _M_w == __x._M_w; } 43697403Sobrien 43797403Sobrien bool 43897403Sobrien _M_is_any() const { return _M_w != 0; } 43997403Sobrien 44097403Sobrien size_t 44197403Sobrien _M_do_count() const 44297403Sobrien { 44397403Sobrien size_t __result = 0; 44497403Sobrien const unsigned char* __byte_ptr = (const unsigned char*)&_M_w; 44597403Sobrien const unsigned char* __end_ptr 44697403Sobrien = ((const unsigned char*)&_M_w)+sizeof(_M_w); 44797403Sobrien while ( __byte_ptr < __end_ptr ) 44897403Sobrien { 44997403Sobrien __result += _S_bit_count[*__byte_ptr]; 45097403Sobrien __byte_ptr++; 45197403Sobrien } 45297403Sobrien return __result; 45397403Sobrien } 45497403Sobrien 45597403Sobrien unsigned long 45697403Sobrien _M_do_to_ulong() const { return _M_w; } 45797403Sobrien 45897403Sobrien size_t 45997403Sobrien _M_do_find_first(size_t __not_found) const; 46097403Sobrien 46197403Sobrien // find the next "on" bit that follows "prev" 46297403Sobrien size_t 46397403Sobrien _M_do_find_next(size_t __prev, size_t __not_found) const; 46497403Sobrien }; 46597403Sobrien 466102782Skan 467102782Skan /** 468102782Skan * @if maint 469102782Skan * Base class, specialization for no storage (zero-length %bitset). 470102782Skan * 471102782Skan * See documentation for bitset. 472102782Skan * @endif 473102782Skan */ 474102782Skan template<> 475102782Skan struct _Base_bitset<0> 476102782Skan { 477102782Skan typedef unsigned long _WordT; 478102782Skan 479102782Skan _Base_bitset() {} 480102782Skan _Base_bitset(unsigned long) {} 481102782Skan 482102782Skan static size_t 483102782Skan _S_whichword(size_t __pos ) 484102782Skan { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; } 485102782Skan 486102782Skan static size_t 487102782Skan _S_whichbyte(size_t __pos ) 488102782Skan { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; } 489102782Skan 490102782Skan static size_t 491102782Skan _S_whichbit(size_t __pos ) 492102782Skan { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; } 493102782Skan 494102782Skan static _WordT 495102782Skan _S_maskbit(size_t __pos ) 496102782Skan { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 497102782Skan 498102782Skan // This would normally give access to the data. The bounds-checking 499102782Skan // in the bitset class will prevent the user from getting this far, 500102782Skan // but (1) it must still return an lvalue to compile, and (2) the 501102782Skan // user might call _Unchecked_set directly, in which case this /needs/ 502102782Skan // to fail. Let's not penalize zero-length users unless they actually 503102782Skan // make an unchecked call; all the memory ugliness is therefore 504102782Skan // localized to this single should-never-get-this-far function. 505102782Skan _WordT& 506102782Skan _M_getword(size_t) const 507102782Skan { __throw_out_of_range("bitset -- zero-length"); return *new _WordT; } 508102782Skan 509102782Skan _WordT 510102782Skan _M_hiword() const { return 0; } 511102782Skan 512102782Skan void 513102782Skan _M_do_and(const _Base_bitset<0>&) { } 514102782Skan 515102782Skan void 516102782Skan _M_do_or(const _Base_bitset<0>&) { } 517102782Skan 518102782Skan void 519102782Skan _M_do_xor(const _Base_bitset<0>&) { } 520102782Skan 521102782Skan void 522102782Skan _M_do_left_shift(size_t) { } 523102782Skan 524102782Skan void 525102782Skan _M_do_right_shift(size_t) { } 526102782Skan 527102782Skan void 528102782Skan _M_do_flip() { } 529102782Skan 530102782Skan void 531102782Skan _M_do_set() { } 532102782Skan 533102782Skan void 534102782Skan _M_do_reset() { } 535102782Skan 536102782Skan // Are all empty bitsets equal to each other? Are they equal to 537102782Skan // themselves? How to compare a thing which has no state? What is 538102782Skan // the sound of one zero-length bitset clapping? 539102782Skan bool 540102782Skan _M_is_equal(const _Base_bitset<0>&) const { return true; } 541102782Skan 542102782Skan bool 543102782Skan _M_is_any() const { return false; } 544102782Skan 545102782Skan size_t 546102782Skan _M_do_count() const { return 0; } 547102782Skan 548102782Skan unsigned long 549102782Skan _M_do_to_ulong() const { return 0; } 550102782Skan 551102782Skan // Normally "not found" is the size, but that could also be 552102782Skan // misinterpreted as an index in this corner case. Oh well. 553102782Skan size_t 554102782Skan _M_do_find_first(size_t) const { return 0; } 555102782Skan 556102782Skan size_t 557102782Skan _M_do_find_next(size_t, size_t) const { return 0; } 558102782Skan }; 559102782Skan 560102782Skan 56197403Sobrien // Helper class to zero out the unused high-order bits in the highest word. 56297403Sobrien template<size_t _Extrabits> 56397403Sobrien struct _Sanitize 56497403Sobrien { 56597403Sobrien static void _S_do_sanitize(unsigned long& __val) 56697403Sobrien { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); } 56797403Sobrien }; 56897403Sobrien 56997403Sobrien template<> 57097403Sobrien struct _Sanitize<0> 57197403Sobrien { static void _S_do_sanitize(unsigned long) { } }; 57297403Sobrien 573117397Skan 57497403Sobrien /** 57597403Sobrien * @brief The %bitset class represents a @e fixed-size sequence of bits. 57697403Sobrien * 57797403Sobrien * @ingroup Containers 57897403Sobrien * 57997403Sobrien * (Note that %bitset does @e not meet the formal requirements of a 58097403Sobrien * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.) 58197403Sobrien * 582117397Skan * The template argument, @a Nb, may be any non-negative number, 583117397Skan * specifying the number of bits (e.g., "0", "12", "1024*1024"). 58497403Sobrien * 585117397Skan * In the general unoptimized case, storage is allocated in word-sized 586117397Skan * blocks. Let B be the number of bits in a word, then (Nb+(B-1))/B 587117397Skan * words will be used for storage. B - Nb%B bits are unused. (They are 588117397Skan * the high-order bits in the highest word.) It is a class invariant 589117397Skan * that those unused bits are always zero. 59097403Sobrien * 59197403Sobrien * If you think of %bitset as "a simple array of bits," be aware that 59297403Sobrien * your mental picture is reversed: a %bitset behaves the same way as 59397403Sobrien * bits in integers do, with the bit at index 0 in the "least significant 594117397Skan * / right-hand" position, and the bit at index Nb-1 in the "most 59597403Sobrien * significant / left-hand" position. Thus, unlike other containers, a 59697403Sobrien * %bitset's index "counts from right to left," to put it very loosely. 59797403Sobrien * 59897403Sobrien * This behavior is preserved when translating to and from strings. For 59997403Sobrien * example, the first line of the following program probably prints 60097403Sobrien * "b('a') is 0001100001" on a modern ASCII system. 60197403Sobrien * 60297403Sobrien * @code 60397403Sobrien * #include <bitset> 60497403Sobrien * #include <iostream> 60597403Sobrien * #include <sstream> 60697403Sobrien * 60797403Sobrien * using namespace std; 60897403Sobrien * 60997403Sobrien * int main() 61097403Sobrien * { 61197403Sobrien * long a = 'a'; 61297403Sobrien * bitset<10> b(a); 61397403Sobrien * 61497403Sobrien * cout << "b('a') is " << b << endl; 61597403Sobrien * 61697403Sobrien * ostringstream s; 61797403Sobrien * s << b; 61897403Sobrien * string str = s.str(); 61997403Sobrien * cout << "index 3 in the string is " << str[3] << " but\n" 62097403Sobrien * << "index 3 in the bitset is " << b[3] << endl; 62197403Sobrien * } 62297403Sobrien * @endcode 62397403Sobrien * 62497403Sobrien * Also see http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23 625117397Skan * for a description of extensions. 62697403Sobrien * 62797403Sobrien * @if maint 62897403Sobrien * Most of the actual code isn't contained in %bitset<> itself, but in the 62997403Sobrien * base class _Base_bitset. The base class works with whole words, not with 63097403Sobrien * individual bits. This allows us to specialize _Base_bitset for the 63197403Sobrien * important special case where the %bitset is only a single word. 63297403Sobrien * 63397403Sobrien * Extra confusion can result due to the fact that the storage for 63497403Sobrien * _Base_bitset @e is a regular array, and is indexed as such. This is 63597403Sobrien * carefully encapsulated. 63697403Sobrien * @endif 63797403Sobrien */ 63897403Sobrien template<size_t _Nb> 63997403Sobrien class bitset : private _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> 64097403Sobrien { 64197403Sobrien private: 64297403Sobrien typedef _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> _Base; 64397403Sobrien typedef unsigned long _WordT; 64497403Sobrien 64597403Sobrien void 64697403Sobrien _M_do_sanitize() 64797403Sobrien { 64897403Sobrien _Sanitize<_Nb%_GLIBCPP_BITSET_BITS_PER_WORD>:: 64997403Sobrien _S_do_sanitize(this->_M_hiword()); 65097403Sobrien } 65197403Sobrien 65297403Sobrien public: 65397403Sobrien /** 65497403Sobrien * This encapsulates the concept of a single bit. An instance of this 65597403Sobrien * class is a proxy for an actual bit; this way the individual bit 65697403Sobrien * operations are done as faster word-size bitwise instructions. 65797403Sobrien * 65897403Sobrien * Most users will never need to use this class directly; conversions 65997403Sobrien * to and from bool are automatic and should be transparent. Overloaded 66097403Sobrien * operators help to preserve the illusion. 66197403Sobrien * 66297403Sobrien * (On a typical system, this "bit %reference" is 64 times the size of 66397403Sobrien * an actual bit. Ha.) 66497403Sobrien */ 66597403Sobrien class reference 66697403Sobrien { 66797403Sobrien friend class bitset; 66897403Sobrien 66997403Sobrien _WordT *_M_wp; 67097403Sobrien size_t _M_bpos; 67197403Sobrien 67297403Sobrien // left undefined 67397403Sobrien reference(); 67497403Sobrien 67597403Sobrien public: 67697403Sobrien reference(bitset& __b, size_t __pos) 67797403Sobrien { 67897403Sobrien _M_wp = &__b._M_getword(__pos); 67997403Sobrien _M_bpos = _Base::_S_whichbit(__pos); 68097403Sobrien } 68197403Sobrien 68297403Sobrien ~reference() { } 68397403Sobrien 68497403Sobrien // for b[i] = __x; 68597403Sobrien reference& 68697403Sobrien operator=(bool __x) 68797403Sobrien { 68897403Sobrien if ( __x ) 68997403Sobrien *_M_wp |= _Base::_S_maskbit(_M_bpos); 69097403Sobrien else 69197403Sobrien *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 69297403Sobrien return *this; 69397403Sobrien } 69497403Sobrien 69597403Sobrien // for b[i] = b[__j]; 69697403Sobrien reference& 69797403Sobrien operator=(const reference& __j) 69897403Sobrien { 69997403Sobrien if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) ) 70097403Sobrien *_M_wp |= _Base::_S_maskbit(_M_bpos); 70197403Sobrien else 70297403Sobrien *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 70397403Sobrien return *this; 70497403Sobrien } 70597403Sobrien 70697403Sobrien // flips the bit 70797403Sobrien bool 70897403Sobrien operator~() const 70997403Sobrien { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 71097403Sobrien 71197403Sobrien // for __x = b[i]; 71297403Sobrien operator bool() const 71397403Sobrien { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 71497403Sobrien 71597403Sobrien // for b[i].flip(); 71697403Sobrien reference& 71797403Sobrien flip() 71897403Sobrien { 71997403Sobrien *_M_wp ^= _Base::_S_maskbit(_M_bpos); 72097403Sobrien return *this; 72197403Sobrien } 72297403Sobrien }; 72397403Sobrien friend class reference; 72497403Sobrien 72597403Sobrien // 23.3.5.1 constructors: 72697403Sobrien /// All bits set to zero. 72797403Sobrien bitset() { } 72897403Sobrien 72997403Sobrien /// Initial bits bitwise-copied from a single word (others set to zero). 73097403Sobrien bitset(unsigned long __val) : _Base(__val) 73197403Sobrien { _M_do_sanitize(); } 73297403Sobrien 73397403Sobrien /** 73497403Sobrien * @brief Use a subset of a string. 73597403Sobrien * @param s A string of '0' and '1' characters. 73697403Sobrien * @param pos Index of the first character in @a s to use; defaults 73797403Sobrien * to zero. 73897403Sobrien * @throw std::out_of_range If @a pos is bigger the size of @a s. 73997403Sobrien * @throw std::invalid_argument If a character appears in the string 74097403Sobrien * which is neither '0' nor '1'. 74197403Sobrien */ 74297403Sobrien template<class _CharT, class _Traits, class _Alloc> 74397403Sobrien explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, 74497403Sobrien size_t __pos = 0) : _Base() 74597403Sobrien { 74697403Sobrien if (__pos > __s.size()) 74797403Sobrien __throw_out_of_range("bitset -- initial position is larger than " 74897403Sobrien "the string itself"); 74997403Sobrien _M_copy_from_string(__s, __pos, 75097403Sobrien basic_string<_CharT, _Traits, _Alloc>::npos); 75197403Sobrien } 75297403Sobrien 75397403Sobrien /** 75497403Sobrien * @brief Use a subset of a string. 75597403Sobrien * @param s A string of '0' and '1' characters. 75697403Sobrien * @param pos Index of the first character in @a s to use. 75797403Sobrien * @param n The number of characters to copy. 75897403Sobrien * @throw std::out_of_range If @a pos is bigger the size of @a s. 75997403Sobrien * @throw std::invalid_argument If a character appears in the string 76097403Sobrien * which is neither '0' nor '1'. 76197403Sobrien */ 76297403Sobrien template<class _CharT, class _Traits, class _Alloc> 76397403Sobrien bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, 76497403Sobrien size_t __pos, size_t __n) : _Base() 76597403Sobrien { 76697403Sobrien if (__pos > __s.size()) 76797403Sobrien __throw_out_of_range("bitset -- initial position is larger than " 76897403Sobrien "the string itself"); 76997403Sobrien _M_copy_from_string(__s, __pos, __n); 77097403Sobrien } 77197403Sobrien 77297403Sobrien // 23.3.5.2 bitset operations: 77397403Sobrien //@{ 77497403Sobrien /** 77597403Sobrien * @brief Operations on bitsets. 77697403Sobrien * @param rhs A same-sized bitset. 77797403Sobrien * 77897403Sobrien * These should be self-explanatory. 77997403Sobrien */ 78097403Sobrien bitset<_Nb>& 78197403Sobrien operator&=(const bitset<_Nb>& __rhs) 78297403Sobrien { 78397403Sobrien this->_M_do_and(__rhs); 78497403Sobrien return *this; 78597403Sobrien } 78697403Sobrien 78797403Sobrien bitset<_Nb>& 78897403Sobrien operator|=(const bitset<_Nb>& __rhs) 78997403Sobrien { 79097403Sobrien this->_M_do_or(__rhs); 79197403Sobrien return *this; 79297403Sobrien } 79397403Sobrien 79497403Sobrien bitset<_Nb>& 79597403Sobrien operator^=(const bitset<_Nb>& __rhs) 79697403Sobrien { 79797403Sobrien this->_M_do_xor(__rhs); 79897403Sobrien return *this; 79997403Sobrien } 80097403Sobrien //@} 80197403Sobrien 80297403Sobrien //@{ 80397403Sobrien /** 80497403Sobrien * @brief Operations on bitsets. 80597403Sobrien * @param pos The number of places to shift. 80697403Sobrien * 80797403Sobrien * These should be self-explanatory. 80897403Sobrien */ 80997403Sobrien bitset<_Nb>& 81097403Sobrien operator<<=(size_t __pos) 81197403Sobrien { 812117397Skan if (__builtin_expect(__pos < _Nb, 1)) 813117397Skan { 814117397Skan this->_M_do_left_shift(__pos); 815117397Skan this->_M_do_sanitize(); 816117397Skan } 817117397Skan else 818117397Skan this->_M_do_reset(); 81997403Sobrien return *this; 82097403Sobrien } 82197403Sobrien 82297403Sobrien bitset<_Nb>& 82397403Sobrien operator>>=(size_t __pos) 82497403Sobrien { 825117397Skan if (__builtin_expect(__pos < _Nb, 1)) 826117397Skan { 827117397Skan this->_M_do_right_shift(__pos); 828117397Skan this->_M_do_sanitize(); 829117397Skan } 830117397Skan else 831117397Skan this->_M_do_reset(); 83297403Sobrien return *this; 83397403Sobrien } 83497403Sobrien //@} 83597403Sobrien 83697403Sobrien //@{ 83797403Sobrien /** 83897403Sobrien * These versions of single-bit set, reset, flip, and test are 83997403Sobrien * extensions from the SGI version. They do no range checking. 84097403Sobrien * @ingroup SGIextensions 84197403Sobrien */ 84297403Sobrien bitset<_Nb>& 84397403Sobrien _Unchecked_set(size_t __pos) 84497403Sobrien { 84597403Sobrien this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 84697403Sobrien return *this; 84797403Sobrien } 84897403Sobrien 84997403Sobrien bitset<_Nb>& 85097403Sobrien _Unchecked_set(size_t __pos, int __val) 85197403Sobrien { 85297403Sobrien if (__val) 85397403Sobrien this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 85497403Sobrien else 85597403Sobrien this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 85697403Sobrien return *this; 85797403Sobrien } 85897403Sobrien 85997403Sobrien bitset<_Nb>& 86097403Sobrien _Unchecked_reset(size_t __pos) 86197403Sobrien { 86297403Sobrien this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 86397403Sobrien return *this; 86497403Sobrien } 86597403Sobrien 86697403Sobrien bitset<_Nb>& 86797403Sobrien _Unchecked_flip(size_t __pos) 86897403Sobrien { 86997403Sobrien this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 87097403Sobrien return *this; 87197403Sobrien } 87297403Sobrien 87397403Sobrien bool 87497403Sobrien _Unchecked_test(size_t __pos) const 87597403Sobrien { 87697403Sobrien return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 87797403Sobrien != static_cast<_WordT>(0); 87897403Sobrien } 87997403Sobrien //@} 88097403Sobrien 88197403Sobrien // Set, reset, and flip. 88297403Sobrien /** 88397403Sobrien * @brief Sets every bit to true. 88497403Sobrien */ 88597403Sobrien bitset<_Nb>& 88697403Sobrien set() 88797403Sobrien { 88897403Sobrien this->_M_do_set(); 88997403Sobrien this->_M_do_sanitize(); 89097403Sobrien return *this; 89197403Sobrien } 89297403Sobrien 89397403Sobrien /** 89497403Sobrien * @brief Sets a given bit to a particular value. 89597403Sobrien * @param pos The index of the bit. 89697403Sobrien * @param val Either true or false, defaults to true. 89797403Sobrien * @throw std::out_of_range If @a pos is bigger the size of the %set. 89897403Sobrien */ 89997403Sobrien bitset<_Nb>& 90097403Sobrien set(size_t __pos, bool __val = true) 90197403Sobrien { 90297403Sobrien if (__pos >= _Nb) 90397403Sobrien __throw_out_of_range("bitset -- set() argument too large"); 90497403Sobrien return _Unchecked_set(__pos, __val); 90597403Sobrien } 90697403Sobrien 90797403Sobrien /** 90897403Sobrien * @brief Sets every bit to false. 90997403Sobrien */ 91097403Sobrien bitset<_Nb>& 91197403Sobrien reset() 91297403Sobrien { 91397403Sobrien this->_M_do_reset(); 91497403Sobrien return *this; 91597403Sobrien } 91697403Sobrien 91797403Sobrien /** 91897403Sobrien * @brief Sets a given bit to false. 91997403Sobrien * @param pos The index of the bit. 92097403Sobrien * @throw std::out_of_range If @a pos is bigger the size of the %set. 92197403Sobrien * 92297403Sobrien * Same as writing @c set(pos,false). 92397403Sobrien */ 92497403Sobrien bitset<_Nb>& 92597403Sobrien reset(size_t __pos) 92697403Sobrien { 92797403Sobrien if (__pos >= _Nb) 92897403Sobrien __throw_out_of_range("bitset -- reset() argument too large"); 92997403Sobrien return _Unchecked_reset(__pos); 93097403Sobrien } 93197403Sobrien 93297403Sobrien /** 93397403Sobrien * @brief Toggles every bit to its opposite value. 93497403Sobrien */ 93597403Sobrien bitset<_Nb>& 93697403Sobrien flip() 93797403Sobrien { 93897403Sobrien this->_M_do_flip(); 93997403Sobrien this->_M_do_sanitize(); 94097403Sobrien return *this; 94197403Sobrien } 94297403Sobrien 94397403Sobrien /** 94497403Sobrien * @brief Toggles a given bit to its opposite value. 94597403Sobrien * @param pos The index of the bit. 94697403Sobrien * @throw std::out_of_range If @a pos is bigger the size of the %set. 94797403Sobrien */ 94897403Sobrien bitset<_Nb>& 94997403Sobrien flip(size_t __pos) 95097403Sobrien { 95197403Sobrien if (__pos >= _Nb) 95297403Sobrien __throw_out_of_range("bitset -- flip() argument too large"); 95397403Sobrien return _Unchecked_flip(__pos); 95497403Sobrien } 95597403Sobrien 95697403Sobrien /// See the no-argument flip(). 95797403Sobrien bitset<_Nb> 95897403Sobrien operator~() const { return bitset<_Nb>(*this).flip(); } 95997403Sobrien 96097403Sobrien //@{ 96197403Sobrien /** 96297403Sobrien * @brief Array-indexing support. 96397403Sobrien * @param pos Index into the %bitset. 96497403Sobrien * @return A bool for a 'const %bitset'. For non-const bitsets, an 96597403Sobrien * instance of the reference proxy class. 96697403Sobrien * @note These operators do no range checking and throw no exceptions, 96797403Sobrien * as required by DR 11 to the standard. 96897403Sobrien * 96997403Sobrien * @if maint 97097403Sobrien * _GLIBCPP_RESOLVE_LIB_DEFECTS Note that this implementation already 97197403Sobrien * resolves DR 11 (items 1 and 2), but does not do the range-checking 97297403Sobrien * required by that DR's resolution. -pme 97397403Sobrien * The DR has since been changed: range-checking is a precondition 97497403Sobrien * (users' responsibility), and these functions must not throw. -pme 97597403Sobrien * @endif 97697403Sobrien */ 97797403Sobrien reference 97897403Sobrien operator[](size_t __pos) { return reference(*this,__pos); } 97997403Sobrien 98097403Sobrien bool 98197403Sobrien operator[](size_t __pos) const { return _Unchecked_test(__pos); } 98297403Sobrien //@} 98397403Sobrien 98497403Sobrien /** 98597403Sobrien * @brief Retuns a numerical interpretation of the %bitset. 98697403Sobrien * @return The integral equivalent of the bits. 98797403Sobrien * @throw std::overflow_error If there are too many bits to be 98897403Sobrien * represented in an @c unsigned @c long. 98997403Sobrien */ 99097403Sobrien unsigned long 99197403Sobrien to_ulong() const { return this->_M_do_to_ulong(); } 99297403Sobrien 99397403Sobrien /** 99497403Sobrien * @brief Retuns a character interpretation of the %bitset. 99597403Sobrien * @return The string equivalent of the bits. 99697403Sobrien * 99797403Sobrien * Note the ordering of the bits: decreasing character positions 99897403Sobrien * correspond to increasing bit positions (see the main class notes for 99997403Sobrien * an example). 100097403Sobrien * 100197403Sobrien * Also note that you must specify the string's template parameters 100297403Sobrien * explicitly. Given a bitset @c bs and a string @s: 100397403Sobrien * @code 100497403Sobrien * s = bs.to_string<char,char_traits<char>,allocator<char> >(); 100597403Sobrien * @endcode 100697403Sobrien */ 100797403Sobrien template<class _CharT, class _Traits, class _Alloc> 100897403Sobrien basic_string<_CharT, _Traits, _Alloc> 100997403Sobrien to_string() const 101097403Sobrien { 101197403Sobrien basic_string<_CharT, _Traits, _Alloc> __result; 101297403Sobrien _M_copy_to_string(__result); 101397403Sobrien return __result; 101497403Sobrien } 101597403Sobrien 101697403Sobrien // Helper functions for string operations. 101797403Sobrien template<class _CharT, class _Traits, class _Alloc> 101897403Sobrien void 101997403Sobrien _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, 102097403Sobrien size_t, size_t); 102197403Sobrien 102297403Sobrien template<class _CharT, class _Traits, class _Alloc> 102397403Sobrien void 102497403Sobrien _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const; 102597403Sobrien 102697403Sobrien /// Returns the number of bits which are set. 102797403Sobrien size_t 102897403Sobrien count() const { return this->_M_do_count(); } 102997403Sobrien 103097403Sobrien /// Returns the total number of bits. 103197403Sobrien size_t 103297403Sobrien size() const { return _Nb; } 103397403Sobrien 103497403Sobrien //@{ 103597403Sobrien /// These comparisons for equality/inequality are, well, @e bitwise. 103697403Sobrien bool 103797403Sobrien operator==(const bitset<_Nb>& __rhs) const 103897403Sobrien { return this->_M_is_equal(__rhs); } 103997403Sobrien 104097403Sobrien bool 104197403Sobrien operator!=(const bitset<_Nb>& __rhs) const 104297403Sobrien { return !this->_M_is_equal(__rhs); } 104397403Sobrien //@} 104497403Sobrien 104597403Sobrien /** 104697403Sobrien * @brief Tests the value of a bit. 104797403Sobrien * @param pos The index of a bit. 104897403Sobrien * @return The value at @a pos. 104997403Sobrien * @throw std::out_of_range If @a pos is bigger the size of the %set. 105097403Sobrien */ 105197403Sobrien bool 105297403Sobrien test(size_t __pos) const 105397403Sobrien { 105497403Sobrien if (__pos >= _Nb) 105597403Sobrien __throw_out_of_range("bitset -- test() argument too large"); 105697403Sobrien return _Unchecked_test(__pos); 105797403Sobrien } 105897403Sobrien 105997403Sobrien /** 106097403Sobrien * @brief Tests whether any of the bits are on. 106197403Sobrien * @return True if at least one bit is set. 106297403Sobrien */ 106397403Sobrien bool 106497403Sobrien any() const { return this->_M_is_any(); } 106597403Sobrien 106697403Sobrien /** 106797403Sobrien * @brief Tests whether any of the bits are on. 106897403Sobrien * @return True if none of the bits are set. 106997403Sobrien */ 107097403Sobrien bool 107197403Sobrien none() const { return !this->_M_is_any(); } 107297403Sobrien 107397403Sobrien //@{ 107497403Sobrien /// Self-explanatory. 107597403Sobrien bitset<_Nb> 107697403Sobrien operator<<(size_t __pos) const 107797403Sobrien { return bitset<_Nb>(*this) <<= __pos; } 107897403Sobrien 107997403Sobrien bitset<_Nb> 108097403Sobrien operator>>(size_t __pos) const 108197403Sobrien { return bitset<_Nb>(*this) >>= __pos; } 108297403Sobrien //@} 108397403Sobrien 108497403Sobrien /** 108597403Sobrien * @brief Finds the index of the first "on" bit. 108697403Sobrien * @return The index of the first bit set, or size() if not found. 108797403Sobrien * @ingroup SGIextensions 108897403Sobrien * @sa _Find_next 108997403Sobrien */ 109097403Sobrien size_t 109197403Sobrien _Find_first() const 109297403Sobrien { return this->_M_do_find_first(_Nb); } 109397403Sobrien 109497403Sobrien /** 109597403Sobrien * @brief Finds the index of the next "on" bit after prev. 109697403Sobrien * @return The index of the next bit set, or size() if not found. 109797403Sobrien * @param prev Where to start searching. 109897403Sobrien * @ingroup SGIextensions 109997403Sobrien * @sa _Find_first 110097403Sobrien */ 110197403Sobrien size_t 110297403Sobrien _Find_next(size_t __prev ) const 110397403Sobrien { return this->_M_do_find_next(__prev, _Nb); } 110497403Sobrien }; 110597403Sobrien 110697403Sobrien // Definitions of non-inline member functions. 110797403Sobrien template<size_t _Nb> 110897403Sobrien template<class _CharT, class _Traits, class _Alloc> 110997403Sobrien void 111097403Sobrien bitset<_Nb>::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, size_t __pos, size_t __n) 111197403Sobrien { 111297403Sobrien reset(); 111397403Sobrien const size_t __nbits = min(_Nb, min(__n, __s.size() - __pos)); 111497403Sobrien for (size_t __i = 0; __i < __nbits; ++__i) 111597403Sobrien { 111697403Sobrien switch(__s[__pos + __nbits - __i - 1]) 111797403Sobrien { 111897403Sobrien case '0': 111997403Sobrien break; 112097403Sobrien case '1': 112197403Sobrien set(__i); 112297403Sobrien break; 112397403Sobrien default: 112497403Sobrien __throw_invalid_argument("bitset -- string contains characters " 112597403Sobrien "which are neither 0 nor 1"); 112697403Sobrien } 112797403Sobrien } 112897403Sobrien } 112997403Sobrien 113097403Sobrien template<size_t _Nb> 113197403Sobrien template<class _CharT, class _Traits, class _Alloc> 113297403Sobrien void 113397403Sobrien bitset<_Nb>::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const 113497403Sobrien { 113597403Sobrien __s.assign(_Nb, '0'); 113697403Sobrien for (size_t __i = 0; __i < _Nb; ++__i) 113797403Sobrien if (_Unchecked_test(__i)) 113897403Sobrien __s[_Nb - 1 - __i] = '1'; 113997403Sobrien } 114097403Sobrien 114197403Sobrien // 23.3.5.3 bitset operations: 114297403Sobrien //@{ 114397403Sobrien /** 114497403Sobrien * @brief Global bitwise operations on bitsets. 114597403Sobrien * @param x A bitset. 114697403Sobrien * @param y A bitset of the same size as @a x. 114797403Sobrien * @return A new bitset. 114897403Sobrien * 114997403Sobrien * These should be self-explanatory. 115097403Sobrien */ 115197403Sobrien template<size_t _Nb> 115297403Sobrien inline bitset<_Nb> 115397403Sobrien operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 115497403Sobrien { 115597403Sobrien bitset<_Nb> __result(__x); 115697403Sobrien __result &= __y; 115797403Sobrien return __result; 115897403Sobrien } 115997403Sobrien 116097403Sobrien template<size_t _Nb> 116197403Sobrien inline bitset<_Nb> 116297403Sobrien operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 116397403Sobrien { 116497403Sobrien bitset<_Nb> __result(__x); 116597403Sobrien __result |= __y; 116697403Sobrien return __result; 116797403Sobrien } 116897403Sobrien 116997403Sobrien template <size_t _Nb> 117097403Sobrien inline bitset<_Nb> 117197403Sobrien operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 117297403Sobrien { 117397403Sobrien bitset<_Nb> __result(__x); 117497403Sobrien __result ^= __y; 117597403Sobrien return __result; 117697403Sobrien } 117797403Sobrien //@} 117897403Sobrien 117997403Sobrien //@{ 118097403Sobrien /** 118197403Sobrien * @brief Global I/O operators for bitsets. 118297403Sobrien * 118397403Sobrien * Direct I/O between streams and bitsets is supported. Output is 118497403Sobrien * straightforward. Input will skip whitespace, only accept '0' and '1' 118597403Sobrien * characters, and will only extract as many digits as the %bitset will 118697403Sobrien * hold. 118797403Sobrien */ 118897403Sobrien template<class _CharT, class _Traits, size_t _Nb> 118997403Sobrien basic_istream<_CharT, _Traits>& 119097403Sobrien operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 119197403Sobrien { 119297403Sobrien typedef typename _Traits::char_type char_type; 119397403Sobrien basic_string<_CharT, _Traits> __tmp; 119497403Sobrien __tmp.reserve(_Nb); 119597403Sobrien 119697403Sobrien // Skip whitespace 119797403Sobrien typename basic_istream<_CharT, _Traits>::sentry __sentry(__is); 119897403Sobrien if (__sentry) 119997403Sobrien { 1200117397Skan ios_base::iostate __state = ios_base::goodbit; 120197403Sobrien basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf(); 120297403Sobrien for (size_t __i = 0; __i < _Nb; ++__i) 120397403Sobrien { 120497403Sobrien static typename _Traits::int_type __eof = _Traits::eof(); 120597403Sobrien 120697403Sobrien typename _Traits::int_type __c1 = __buf->sbumpc(); 120797403Sobrien if (_Traits::eq_int_type(__c1, __eof)) 120897403Sobrien { 1209117397Skan __state |= ios_base::eofbit; 121097403Sobrien break; 121197403Sobrien } 121297403Sobrien else 121397403Sobrien { 121497403Sobrien char_type __c2 = _Traits::to_char_type(__c1); 121597403Sobrien char_type __c = __is.narrow(__c2, '*'); 121697403Sobrien 121797403Sobrien if (__c == '0' || __c == '1') 121897403Sobrien __tmp.push_back(__c); 1219117397Skan else if (_Traits::eq_int_type(__buf->sputbackc(__c2), __eof)) 122097403Sobrien { 1221117397Skan __state |= ios_base::failbit; 122297403Sobrien break; 122397403Sobrien } 122497403Sobrien } 122597403Sobrien } 122697403Sobrien 1227102782Skan if (__tmp.empty() && !_Nb) 1228117397Skan __state |= ios_base::failbit; 122997403Sobrien else 123097403Sobrien __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb); 1231117397Skan 1232117397Skan if (__state != ios_base::goodbit) 1233117397Skan __is.setstate(__state); // may throw an exception 123497403Sobrien } 123597403Sobrien 123697403Sobrien return __is; 123797403Sobrien } 123897403Sobrien 123997403Sobrien template <class _CharT, class _Traits, size_t _Nb> 124097403Sobrien basic_ostream<_CharT, _Traits>& 124197403Sobrien operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x) 124297403Sobrien { 124397403Sobrien basic_string<_CharT, _Traits> __tmp; 124497403Sobrien __x._M_copy_to_string(__tmp); 124597403Sobrien return __os << __tmp; 124697403Sobrien } 124797403Sobrien //@} 124897403Sobrien} // namespace std 124997403Sobrien 125097403Sobrien#undef _GLIBCPP_BITSET_WORDS 125197403Sobrien 125297403Sobrien#endif /* _GLIBCPP_BITSET_H */ 1253