std_bitset.h revision 102782
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 { 22297403Sobrien if (__shift != 0) 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 { 24797403Sobrien if (__shift != 0) 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 57397403Sobrien /** 57497403Sobrien * @brief The %bitset class represents a @e fixed-size sequence of bits. 57597403Sobrien * 57697403Sobrien * @ingroup Containers 57797403Sobrien * 57897403Sobrien * (Note that %bitset does @e not meet the formal requirements of a 57997403Sobrien * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.) 58097403Sobrien * 58197403Sobrien * The template argument, @a _Nb, may be any nonzero number of type 58297403Sobrien * size_t. 58397403Sobrien * 58497403Sobrien * A %bitset of size N has N % (sizeof(unsigned long) * CHAR_BIT) unused 58597403Sobrien * bits. (They are the high-order bits in the highest word.) It is 58697403Sobrien * a class invariant that those unused bits are always zero. 58797403Sobrien * 58897403Sobrien * If you think of %bitset as "a simple array of bits," be aware that 58997403Sobrien * your mental picture is reversed: a %bitset behaves the same way as 59097403Sobrien * bits in integers do, with the bit at index 0 in the "least significant 59197403Sobrien * / right-hand" position, and the bit at index N-1 in the "most 59297403Sobrien * significant / left-hand" position. Thus, unlike other containers, a 59397403Sobrien * %bitset's index "counts from right to left," to put it very loosely. 59497403Sobrien * 59597403Sobrien * This behavior is preserved when translating to and from strings. For 59697403Sobrien * example, the first line of the following program probably prints 59797403Sobrien * "b('a') is 0001100001" on a modern ASCII system. 59897403Sobrien * 59997403Sobrien * @code 60097403Sobrien * #include <bitset> 60197403Sobrien * #include <iostream> 60297403Sobrien * #include <sstream> 60397403Sobrien * 60497403Sobrien * using namespace std; 60597403Sobrien * 60697403Sobrien * int main() 60797403Sobrien * { 60897403Sobrien * long a = 'a'; 60997403Sobrien * bitset<10> b(a); 61097403Sobrien * 61197403Sobrien * cout << "b('a') is " << b << endl; 61297403Sobrien * 61397403Sobrien * ostringstream s; 61497403Sobrien * s << b; 61597403Sobrien * string str = s.str(); 61697403Sobrien * cout << "index 3 in the string is " << str[3] << " but\n" 61797403Sobrien * << "index 3 in the bitset is " << b[3] << endl; 61897403Sobrien * } 61997403Sobrien * @endcode 62097403Sobrien * 62197403Sobrien * Also see http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23 62297403Sobrien * 62397403Sobrien * @if maint 62497403Sobrien * Most of the actual code isn't contained in %bitset<> itself, but in the 62597403Sobrien * base class _Base_bitset. The base class works with whole words, not with 62697403Sobrien * individual bits. This allows us to specialize _Base_bitset for the 62797403Sobrien * important special case where the %bitset is only a single word. 62897403Sobrien * 62997403Sobrien * Extra confusion can result due to the fact that the storage for 63097403Sobrien * _Base_bitset @e is a regular array, and is indexed as such. This is 63197403Sobrien * carefully encapsulated. 63297403Sobrien * @endif 63397403Sobrien */ 63497403Sobrien template<size_t _Nb> 63597403Sobrien class bitset : private _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> 63697403Sobrien { 63797403Sobrien private: 63897403Sobrien typedef _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> _Base; 63997403Sobrien typedef unsigned long _WordT; 64097403Sobrien 64197403Sobrien void 64297403Sobrien _M_do_sanitize() 64397403Sobrien { 64497403Sobrien _Sanitize<_Nb%_GLIBCPP_BITSET_BITS_PER_WORD>:: 64597403Sobrien _S_do_sanitize(this->_M_hiword()); 64697403Sobrien } 64797403Sobrien 64897403Sobrien public: 64997403Sobrien /** 65097403Sobrien * This encapsulates the concept of a single bit. An instance of this 65197403Sobrien * class is a proxy for an actual bit; this way the individual bit 65297403Sobrien * operations are done as faster word-size bitwise instructions. 65397403Sobrien * 65497403Sobrien * Most users will never need to use this class directly; conversions 65597403Sobrien * to and from bool are automatic and should be transparent. Overloaded 65697403Sobrien * operators help to preserve the illusion. 65797403Sobrien * 65897403Sobrien * (On a typical system, this "bit %reference" is 64 times the size of 65997403Sobrien * an actual bit. Ha.) 66097403Sobrien */ 66197403Sobrien class reference 66297403Sobrien { 66397403Sobrien friend class bitset; 66497403Sobrien 66597403Sobrien _WordT *_M_wp; 66697403Sobrien size_t _M_bpos; 66797403Sobrien 66897403Sobrien // left undefined 66997403Sobrien reference(); 67097403Sobrien 67197403Sobrien public: 67297403Sobrien reference(bitset& __b, size_t __pos) 67397403Sobrien { 67497403Sobrien _M_wp = &__b._M_getword(__pos); 67597403Sobrien _M_bpos = _Base::_S_whichbit(__pos); 67697403Sobrien } 67797403Sobrien 67897403Sobrien ~reference() { } 67997403Sobrien 68097403Sobrien // for b[i] = __x; 68197403Sobrien reference& 68297403Sobrien operator=(bool __x) 68397403Sobrien { 68497403Sobrien if ( __x ) 68597403Sobrien *_M_wp |= _Base::_S_maskbit(_M_bpos); 68697403Sobrien else 68797403Sobrien *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 68897403Sobrien return *this; 68997403Sobrien } 69097403Sobrien 69197403Sobrien // for b[i] = b[__j]; 69297403Sobrien reference& 69397403Sobrien operator=(const reference& __j) 69497403Sobrien { 69597403Sobrien if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) ) 69697403Sobrien *_M_wp |= _Base::_S_maskbit(_M_bpos); 69797403Sobrien else 69897403Sobrien *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 69997403Sobrien return *this; 70097403Sobrien } 70197403Sobrien 70297403Sobrien // flips the bit 70397403Sobrien bool 70497403Sobrien operator~() const 70597403Sobrien { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 70697403Sobrien 70797403Sobrien // for __x = b[i]; 70897403Sobrien operator bool() const 70997403Sobrien { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 71097403Sobrien 71197403Sobrien // for b[i].flip(); 71297403Sobrien reference& 71397403Sobrien flip() 71497403Sobrien { 71597403Sobrien *_M_wp ^= _Base::_S_maskbit(_M_bpos); 71697403Sobrien return *this; 71797403Sobrien } 71897403Sobrien }; 71997403Sobrien friend class reference; 72097403Sobrien 72197403Sobrien // 23.3.5.1 constructors: 72297403Sobrien /// All bits set to zero. 72397403Sobrien bitset() { } 72497403Sobrien 72597403Sobrien /// Initial bits bitwise-copied from a single word (others set to zero). 72697403Sobrien bitset(unsigned long __val) : _Base(__val) 72797403Sobrien { _M_do_sanitize(); } 72897403Sobrien 72997403Sobrien /** 73097403Sobrien * @brief Use a subset of a string. 73197403Sobrien * @param s A string of '0' and '1' characters. 73297403Sobrien * @param pos Index of the first character in @a s to use; defaults 73397403Sobrien * to zero. 73497403Sobrien * @throw std::out_of_range If @a pos is bigger the size of @a s. 73597403Sobrien * @throw std::invalid_argument If a character appears in the string 73697403Sobrien * which is neither '0' nor '1'. 73797403Sobrien */ 73897403Sobrien template<class _CharT, class _Traits, class _Alloc> 73997403Sobrien explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, 74097403Sobrien size_t __pos = 0) : _Base() 74197403Sobrien { 74297403Sobrien if (__pos > __s.size()) 74397403Sobrien __throw_out_of_range("bitset -- initial position is larger than " 74497403Sobrien "the string itself"); 74597403Sobrien _M_copy_from_string(__s, __pos, 74697403Sobrien basic_string<_CharT, _Traits, _Alloc>::npos); 74797403Sobrien } 74897403Sobrien 74997403Sobrien /** 75097403Sobrien * @brief Use a subset of a string. 75197403Sobrien * @param s A string of '0' and '1' characters. 75297403Sobrien * @param pos Index of the first character in @a s to use. 75397403Sobrien * @param n The number of characters to copy. 75497403Sobrien * @throw std::out_of_range If @a pos is bigger the size of @a s. 75597403Sobrien * @throw std::invalid_argument If a character appears in the string 75697403Sobrien * which is neither '0' nor '1'. 75797403Sobrien */ 75897403Sobrien template<class _CharT, class _Traits, class _Alloc> 75997403Sobrien bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, 76097403Sobrien size_t __pos, size_t __n) : _Base() 76197403Sobrien { 76297403Sobrien if (__pos > __s.size()) 76397403Sobrien __throw_out_of_range("bitset -- initial position is larger than " 76497403Sobrien "the string itself"); 76597403Sobrien _M_copy_from_string(__s, __pos, __n); 76697403Sobrien } 76797403Sobrien 76897403Sobrien // 23.3.5.2 bitset operations: 76997403Sobrien //@{ 77097403Sobrien /** 77197403Sobrien * @brief Operations on bitsets. 77297403Sobrien * @param rhs A same-sized bitset. 77397403Sobrien * 77497403Sobrien * These should be self-explanatory. 77597403Sobrien */ 77697403Sobrien bitset<_Nb>& 77797403Sobrien operator&=(const bitset<_Nb>& __rhs) 77897403Sobrien { 77997403Sobrien this->_M_do_and(__rhs); 78097403Sobrien return *this; 78197403Sobrien } 78297403Sobrien 78397403Sobrien bitset<_Nb>& 78497403Sobrien operator|=(const bitset<_Nb>& __rhs) 78597403Sobrien { 78697403Sobrien this->_M_do_or(__rhs); 78797403Sobrien return *this; 78897403Sobrien } 78997403Sobrien 79097403Sobrien bitset<_Nb>& 79197403Sobrien operator^=(const bitset<_Nb>& __rhs) 79297403Sobrien { 79397403Sobrien this->_M_do_xor(__rhs); 79497403Sobrien return *this; 79597403Sobrien } 79697403Sobrien //@} 79797403Sobrien 79897403Sobrien //@{ 79997403Sobrien /** 80097403Sobrien * @brief Operations on bitsets. 80197403Sobrien * @param pos The number of places to shift. 80297403Sobrien * 80397403Sobrien * These should be self-explanatory. 80497403Sobrien */ 80597403Sobrien bitset<_Nb>& 80697403Sobrien operator<<=(size_t __pos) 80797403Sobrien { 80897403Sobrien this->_M_do_left_shift(__pos); 80997403Sobrien this->_M_do_sanitize(); 81097403Sobrien return *this; 81197403Sobrien } 81297403Sobrien 81397403Sobrien bitset<_Nb>& 81497403Sobrien operator>>=(size_t __pos) 81597403Sobrien { 81697403Sobrien this->_M_do_right_shift(__pos); 81797403Sobrien this->_M_do_sanitize(); 81897403Sobrien return *this; 81997403Sobrien } 82097403Sobrien //@} 82197403Sobrien 82297403Sobrien //@{ 82397403Sobrien /** 82497403Sobrien * These versions of single-bit set, reset, flip, and test are 82597403Sobrien * extensions from the SGI version. They do no range checking. 82697403Sobrien * @ingroup SGIextensions 82797403Sobrien */ 82897403Sobrien bitset<_Nb>& 82997403Sobrien _Unchecked_set(size_t __pos) 83097403Sobrien { 83197403Sobrien this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 83297403Sobrien return *this; 83397403Sobrien } 83497403Sobrien 83597403Sobrien bitset<_Nb>& 83697403Sobrien _Unchecked_set(size_t __pos, int __val) 83797403Sobrien { 83897403Sobrien if (__val) 83997403Sobrien this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 84097403Sobrien else 84197403Sobrien this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 84297403Sobrien return *this; 84397403Sobrien } 84497403Sobrien 84597403Sobrien bitset<_Nb>& 84697403Sobrien _Unchecked_reset(size_t __pos) 84797403Sobrien { 84897403Sobrien this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 84997403Sobrien return *this; 85097403Sobrien } 85197403Sobrien 85297403Sobrien bitset<_Nb>& 85397403Sobrien _Unchecked_flip(size_t __pos) 85497403Sobrien { 85597403Sobrien this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 85697403Sobrien return *this; 85797403Sobrien } 85897403Sobrien 85997403Sobrien bool 86097403Sobrien _Unchecked_test(size_t __pos) const 86197403Sobrien { 86297403Sobrien return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 86397403Sobrien != static_cast<_WordT>(0); 86497403Sobrien } 86597403Sobrien //@} 86697403Sobrien 86797403Sobrien // Set, reset, and flip. 86897403Sobrien /** 86997403Sobrien * @brief Sets every bit to true. 87097403Sobrien */ 87197403Sobrien bitset<_Nb>& 87297403Sobrien set() 87397403Sobrien { 87497403Sobrien this->_M_do_set(); 87597403Sobrien this->_M_do_sanitize(); 87697403Sobrien return *this; 87797403Sobrien } 87897403Sobrien 87997403Sobrien /** 88097403Sobrien * @brief Sets a given bit to a particular value. 88197403Sobrien * @param pos The index of the bit. 88297403Sobrien * @param val Either true or false, defaults to true. 88397403Sobrien * @throw std::out_of_range If @a pos is bigger the size of the %set. 88497403Sobrien */ 88597403Sobrien bitset<_Nb>& 88697403Sobrien set(size_t __pos, bool __val = true) 88797403Sobrien { 88897403Sobrien if (__pos >= _Nb) 88997403Sobrien __throw_out_of_range("bitset -- set() argument too large"); 89097403Sobrien return _Unchecked_set(__pos, __val); 89197403Sobrien } 89297403Sobrien 89397403Sobrien /** 89497403Sobrien * @brief Sets every bit to false. 89597403Sobrien */ 89697403Sobrien bitset<_Nb>& 89797403Sobrien reset() 89897403Sobrien { 89997403Sobrien this->_M_do_reset(); 90097403Sobrien return *this; 90197403Sobrien } 90297403Sobrien 90397403Sobrien /** 90497403Sobrien * @brief Sets a given bit to false. 90597403Sobrien * @param pos The index of the bit. 90697403Sobrien * @throw std::out_of_range If @a pos is bigger the size of the %set. 90797403Sobrien * 90897403Sobrien * Same as writing @c set(pos,false). 90997403Sobrien */ 91097403Sobrien bitset<_Nb>& 91197403Sobrien reset(size_t __pos) 91297403Sobrien { 91397403Sobrien if (__pos >= _Nb) 91497403Sobrien __throw_out_of_range("bitset -- reset() argument too large"); 91597403Sobrien return _Unchecked_reset(__pos); 91697403Sobrien } 91797403Sobrien 91897403Sobrien /** 91997403Sobrien * @brief Toggles every bit to its opposite value. 92097403Sobrien */ 92197403Sobrien bitset<_Nb>& 92297403Sobrien flip() 92397403Sobrien { 92497403Sobrien this->_M_do_flip(); 92597403Sobrien this->_M_do_sanitize(); 92697403Sobrien return *this; 92797403Sobrien } 92897403Sobrien 92997403Sobrien /** 93097403Sobrien * @brief Toggles a given bit to its opposite value. 93197403Sobrien * @param pos The index of the bit. 93297403Sobrien * @throw std::out_of_range If @a pos is bigger the size of the %set. 93397403Sobrien */ 93497403Sobrien bitset<_Nb>& 93597403Sobrien flip(size_t __pos) 93697403Sobrien { 93797403Sobrien if (__pos >= _Nb) 93897403Sobrien __throw_out_of_range("bitset -- flip() argument too large"); 93997403Sobrien return _Unchecked_flip(__pos); 94097403Sobrien } 94197403Sobrien 94297403Sobrien /// See the no-argument flip(). 94397403Sobrien bitset<_Nb> 94497403Sobrien operator~() const { return bitset<_Nb>(*this).flip(); } 94597403Sobrien 94697403Sobrien //@{ 94797403Sobrien /** 94897403Sobrien * @brief Array-indexing support. 94997403Sobrien * @param pos Index into the %bitset. 95097403Sobrien * @return A bool for a 'const %bitset'. For non-const bitsets, an 95197403Sobrien * instance of the reference proxy class. 95297403Sobrien * @note These operators do no range checking and throw no exceptions, 95397403Sobrien * as required by DR 11 to the standard. 95497403Sobrien * 95597403Sobrien * @if maint 95697403Sobrien * _GLIBCPP_RESOLVE_LIB_DEFECTS Note that this implementation already 95797403Sobrien * resolves DR 11 (items 1 and 2), but does not do the range-checking 95897403Sobrien * required by that DR's resolution. -pme 95997403Sobrien * The DR has since been changed: range-checking is a precondition 96097403Sobrien * (users' responsibility), and these functions must not throw. -pme 96197403Sobrien * @endif 96297403Sobrien */ 96397403Sobrien reference 96497403Sobrien operator[](size_t __pos) { return reference(*this,__pos); } 96597403Sobrien 96697403Sobrien bool 96797403Sobrien operator[](size_t __pos) const { return _Unchecked_test(__pos); } 96897403Sobrien //@} 96997403Sobrien 97097403Sobrien /** 97197403Sobrien * @brief Retuns a numerical interpretation of the %bitset. 97297403Sobrien * @return The integral equivalent of the bits. 97397403Sobrien * @throw std::overflow_error If there are too many bits to be 97497403Sobrien * represented in an @c unsigned @c long. 97597403Sobrien */ 97697403Sobrien unsigned long 97797403Sobrien to_ulong() const { return this->_M_do_to_ulong(); } 97897403Sobrien 97997403Sobrien /** 98097403Sobrien * @brief Retuns a character interpretation of the %bitset. 98197403Sobrien * @return The string equivalent of the bits. 98297403Sobrien * 98397403Sobrien * Note the ordering of the bits: decreasing character positions 98497403Sobrien * correspond to increasing bit positions (see the main class notes for 98597403Sobrien * an example). 98697403Sobrien * 98797403Sobrien * Also note that you must specify the string's template parameters 98897403Sobrien * explicitly. Given a bitset @c bs and a string @s: 98997403Sobrien * @code 99097403Sobrien * s = bs.to_string<char,char_traits<char>,allocator<char> >(); 99197403Sobrien * @endcode 99297403Sobrien */ 99397403Sobrien template<class _CharT, class _Traits, class _Alloc> 99497403Sobrien basic_string<_CharT, _Traits, _Alloc> 99597403Sobrien to_string() const 99697403Sobrien { 99797403Sobrien basic_string<_CharT, _Traits, _Alloc> __result; 99897403Sobrien _M_copy_to_string(__result); 99997403Sobrien return __result; 100097403Sobrien } 100197403Sobrien 100297403Sobrien // Helper functions for string operations. 100397403Sobrien template<class _CharT, class _Traits, class _Alloc> 100497403Sobrien void 100597403Sobrien _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, 100697403Sobrien size_t, size_t); 100797403Sobrien 100897403Sobrien template<class _CharT, class _Traits, class _Alloc> 100997403Sobrien void 101097403Sobrien _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const; 101197403Sobrien 101297403Sobrien /// Returns the number of bits which are set. 101397403Sobrien size_t 101497403Sobrien count() const { return this->_M_do_count(); } 101597403Sobrien 101697403Sobrien /// Returns the total number of bits. 101797403Sobrien size_t 101897403Sobrien size() const { return _Nb; } 101997403Sobrien 102097403Sobrien //@{ 102197403Sobrien /// These comparisons for equality/inequality are, well, @e bitwise. 102297403Sobrien bool 102397403Sobrien operator==(const bitset<_Nb>& __rhs) const 102497403Sobrien { return this->_M_is_equal(__rhs); } 102597403Sobrien 102697403Sobrien bool 102797403Sobrien operator!=(const bitset<_Nb>& __rhs) const 102897403Sobrien { return !this->_M_is_equal(__rhs); } 102997403Sobrien //@} 103097403Sobrien 103197403Sobrien /** 103297403Sobrien * @brief Tests the value of a bit. 103397403Sobrien * @param pos The index of a bit. 103497403Sobrien * @return The value at @a pos. 103597403Sobrien * @throw std::out_of_range If @a pos is bigger the size of the %set. 103697403Sobrien */ 103797403Sobrien bool 103897403Sobrien test(size_t __pos) const 103997403Sobrien { 104097403Sobrien if (__pos >= _Nb) 104197403Sobrien __throw_out_of_range("bitset -- test() argument too large"); 104297403Sobrien return _Unchecked_test(__pos); 104397403Sobrien } 104497403Sobrien 104597403Sobrien /** 104697403Sobrien * @brief Tests whether any of the bits are on. 104797403Sobrien * @return True if at least one bit is set. 104897403Sobrien */ 104997403Sobrien bool 105097403Sobrien any() const { return this->_M_is_any(); } 105197403Sobrien 105297403Sobrien /** 105397403Sobrien * @brief Tests whether any of the bits are on. 105497403Sobrien * @return True if none of the bits are set. 105597403Sobrien */ 105697403Sobrien bool 105797403Sobrien none() const { return !this->_M_is_any(); } 105897403Sobrien 105997403Sobrien //@{ 106097403Sobrien /// Self-explanatory. 106197403Sobrien bitset<_Nb> 106297403Sobrien operator<<(size_t __pos) const 106397403Sobrien { return bitset<_Nb>(*this) <<= __pos; } 106497403Sobrien 106597403Sobrien bitset<_Nb> 106697403Sobrien operator>>(size_t __pos) const 106797403Sobrien { return bitset<_Nb>(*this) >>= __pos; } 106897403Sobrien //@} 106997403Sobrien 107097403Sobrien /** 107197403Sobrien * @brief Finds the index of the first "on" bit. 107297403Sobrien * @return The index of the first bit set, or size() if not found. 107397403Sobrien * @ingroup SGIextensions 107497403Sobrien * @sa _Find_next 107597403Sobrien */ 107697403Sobrien size_t 107797403Sobrien _Find_first() const 107897403Sobrien { return this->_M_do_find_first(_Nb); } 107997403Sobrien 108097403Sobrien /** 108197403Sobrien * @brief Finds the index of the next "on" bit after prev. 108297403Sobrien * @return The index of the next bit set, or size() if not found. 108397403Sobrien * @param prev Where to start searching. 108497403Sobrien * @ingroup SGIextensions 108597403Sobrien * @sa _Find_first 108697403Sobrien */ 108797403Sobrien size_t 108897403Sobrien _Find_next(size_t __prev ) const 108997403Sobrien { return this->_M_do_find_next(__prev, _Nb); } 109097403Sobrien }; 109197403Sobrien 109297403Sobrien // Definitions of non-inline member functions. 109397403Sobrien template<size_t _Nb> 109497403Sobrien template<class _CharT, class _Traits, class _Alloc> 109597403Sobrien void 109697403Sobrien bitset<_Nb>::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, size_t __pos, size_t __n) 109797403Sobrien { 109897403Sobrien reset(); 109997403Sobrien const size_t __nbits = min(_Nb, min(__n, __s.size() - __pos)); 110097403Sobrien for (size_t __i = 0; __i < __nbits; ++__i) 110197403Sobrien { 110297403Sobrien switch(__s[__pos + __nbits - __i - 1]) 110397403Sobrien { 110497403Sobrien case '0': 110597403Sobrien break; 110697403Sobrien case '1': 110797403Sobrien set(__i); 110897403Sobrien break; 110997403Sobrien default: 111097403Sobrien __throw_invalid_argument("bitset -- string contains characters " 111197403Sobrien "which are neither 0 nor 1"); 111297403Sobrien } 111397403Sobrien } 111497403Sobrien } 111597403Sobrien 111697403Sobrien template<size_t _Nb> 111797403Sobrien template<class _CharT, class _Traits, class _Alloc> 111897403Sobrien void 111997403Sobrien bitset<_Nb>::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const 112097403Sobrien { 112197403Sobrien __s.assign(_Nb, '0'); 112297403Sobrien for (size_t __i = 0; __i < _Nb; ++__i) 112397403Sobrien if (_Unchecked_test(__i)) 112497403Sobrien __s[_Nb - 1 - __i] = '1'; 112597403Sobrien } 112697403Sobrien 112797403Sobrien // 23.3.5.3 bitset operations: 112897403Sobrien //@{ 112997403Sobrien /** 113097403Sobrien * @brief Global bitwise operations on bitsets. 113197403Sobrien * @param x A bitset. 113297403Sobrien * @param y A bitset of the same size as @a x. 113397403Sobrien * @return A new bitset. 113497403Sobrien * 113597403Sobrien * These should be self-explanatory. 113697403Sobrien */ 113797403Sobrien template<size_t _Nb> 113897403Sobrien inline bitset<_Nb> 113997403Sobrien operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 114097403Sobrien { 114197403Sobrien bitset<_Nb> __result(__x); 114297403Sobrien __result &= __y; 114397403Sobrien return __result; 114497403Sobrien } 114597403Sobrien 114697403Sobrien template<size_t _Nb> 114797403Sobrien inline bitset<_Nb> 114897403Sobrien operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 114997403Sobrien { 115097403Sobrien bitset<_Nb> __result(__x); 115197403Sobrien __result |= __y; 115297403Sobrien return __result; 115397403Sobrien } 115497403Sobrien 115597403Sobrien template <size_t _Nb> 115697403Sobrien inline bitset<_Nb> 115797403Sobrien operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 115897403Sobrien { 115997403Sobrien bitset<_Nb> __result(__x); 116097403Sobrien __result ^= __y; 116197403Sobrien return __result; 116297403Sobrien } 116397403Sobrien //@} 116497403Sobrien 116597403Sobrien //@{ 116697403Sobrien /** 116797403Sobrien * @brief Global I/O operators for bitsets. 116897403Sobrien * 116997403Sobrien * Direct I/O between streams and bitsets is supported. Output is 117097403Sobrien * straightforward. Input will skip whitespace, only accept '0' and '1' 117197403Sobrien * characters, and will only extract as many digits as the %bitset will 117297403Sobrien * hold. 117397403Sobrien */ 117497403Sobrien template<class _CharT, class _Traits, size_t _Nb> 117597403Sobrien basic_istream<_CharT, _Traits>& 117697403Sobrien operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 117797403Sobrien { 117897403Sobrien typedef typename _Traits::char_type char_type; 117997403Sobrien basic_string<_CharT, _Traits> __tmp; 118097403Sobrien __tmp.reserve(_Nb); 118197403Sobrien 118297403Sobrien // Skip whitespace 118397403Sobrien typename basic_istream<_CharT, _Traits>::sentry __sentry(__is); 118497403Sobrien if (__sentry) 118597403Sobrien { 118697403Sobrien basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf(); 118797403Sobrien for (size_t __i = 0; __i < _Nb; ++__i) 118897403Sobrien { 118997403Sobrien static typename _Traits::int_type __eof = _Traits::eof(); 119097403Sobrien 119197403Sobrien typename _Traits::int_type __c1 = __buf->sbumpc(); 119297403Sobrien if (_Traits::eq_int_type(__c1, __eof)) 119397403Sobrien { 119497403Sobrien __is.setstate(ios_base::eofbit); 119597403Sobrien break; 119697403Sobrien } 119797403Sobrien else 119897403Sobrien { 119997403Sobrien char_type __c2 = _Traits::to_char_type(__c1); 120097403Sobrien char_type __c = __is.narrow(__c2, '*'); 120197403Sobrien 120297403Sobrien if (__c == '0' || __c == '1') 120397403Sobrien __tmp.push_back(__c); 120497403Sobrien else if (_Traits::eq_int_type(__buf->sputbackc(__c2), 120597403Sobrien __eof)) 120697403Sobrien { 120797403Sobrien __is.setstate(ios_base::failbit); 120897403Sobrien break; 120997403Sobrien } 121097403Sobrien } 121197403Sobrien } 121297403Sobrien 1213102782Skan if (__tmp.empty() && !_Nb) 121497403Sobrien __is.setstate(ios_base::failbit); 121597403Sobrien else 121697403Sobrien __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb); 121797403Sobrien } 121897403Sobrien 121997403Sobrien return __is; 122097403Sobrien } 122197403Sobrien 122297403Sobrien template <class _CharT, class _Traits, size_t _Nb> 122397403Sobrien basic_ostream<_CharT, _Traits>& 122497403Sobrien operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x) 122597403Sobrien { 122697403Sobrien basic_string<_CharT, _Traits> __tmp; 122797403Sobrien __x._M_copy_to_string(__tmp); 122897403Sobrien return __os << __tmp; 122997403Sobrien } 123097403Sobrien //@} 123197403Sobrien} // namespace std 123297403Sobrien 123397403Sobrien#undef _GLIBCPP_BITSET_WORDS 123497403Sobrien 123597403Sobrien#endif /* _GLIBCPP_BITSET_H */ 1236