bitset

Go to the documentation of this file.
00001 // <bitset> -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  * Copyright (c) 1998
00032  * Silicon Graphics Computer Systems, Inc.
00033  *
00034  * Permission to use, copy, modify, distribute and sell this software
00035  * and its documentation for any purpose is hereby granted without fee,
00036  * provided that the above copyright notice appear in all copies and
00037  * that both that copyright notice and this permission notice appear
00038  * in supporting documentation.  Silicon Graphics makes no
00039  * representations about the suitability of this software for any
00040  * purpose.  It is provided "as is" without express or implied warranty.
00041  */
00042 
00048 #ifndef _GLIBCPP_BITSET_H
00049 #define _GLIBCPP_BITSET_H
00050 
00051 #pragma GCC system_header
00052 
00053 #include <cstddef>     // for size_t
00054 #include <cstring>     // for memset
00055 #include <string>
00056 #include <bits/functexcept.h>   // for invalid_argument, out_of_range,
00057                                 // overflow_error
00058 #include <ostream>     // for ostream (operator<<)
00059 #include <istream>     // for istream (operator>>)
00060 
00061 
00062 #define _GLIBCPP_BITSET_BITS_PER_WORD (CHAR_BIT*sizeof(unsigned long))
00063 #define _GLIBCPP_BITSET_WORDS(__n) \
00064  ((__n) < 1 ? 0 : ((__n) + _GLIBCPP_BITSET_BITS_PER_WORD - 1)/_GLIBCPP_BITSET_BITS_PER_WORD)
00065 
00066 namespace std
00067 {
00068   extern unsigned char  _S_bit_count[256];
00069   extern unsigned char  _S_first_one[256];
00070 
00079   template<size_t _Nw>
00080     struct _Base_bitset
00081     {
00082       typedef unsigned long _WordT;
00083 
00085       _WordT        _M_w[_Nw];
00086 
00087       _Base_bitset() { _M_do_reset(); }
00088       _Base_bitset(unsigned long __val)
00089       {
00090     _M_do_reset();
00091     _M_w[0] = __val;
00092       }
00093 
00094       static size_t
00095       _S_whichword(size_t __pos )
00096       { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; }
00097 
00098       static size_t
00099       _S_whichbyte(size_t __pos )
00100       { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; }
00101 
00102       static size_t
00103       _S_whichbit(size_t __pos )
00104       { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; }
00105 
00106       static _WordT
00107       _S_maskbit(size_t __pos )
00108       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
00109 
00110       _WordT&
00111       _M_getword(size_t __pos)
00112       { return _M_w[_S_whichword(__pos)]; }
00113 
00114       _WordT
00115       _M_getword(size_t __pos) const
00116       { return _M_w[_S_whichword(__pos)]; }
00117 
00118       _WordT&
00119       _M_hiword() { return _M_w[_Nw - 1]; }
00120 
00121       _WordT
00122       _M_hiword() const { return _M_w[_Nw - 1]; }
00123 
00124       void
00125       _M_do_and(const _Base_bitset<_Nw>& __x)
00126       {
00127     for (size_t __i = 0; __i < _Nw; __i++)
00128       _M_w[__i] &= __x._M_w[__i];
00129       }
00130 
00131       void
00132       _M_do_or(const _Base_bitset<_Nw>& __x)
00133       {
00134     for (size_t __i = 0; __i < _Nw; __i++)
00135       _M_w[__i] |= __x._M_w[__i];
00136       }
00137 
00138       void
00139       _M_do_xor(const _Base_bitset<_Nw>& __x)
00140       {
00141     for (size_t __i = 0; __i < _Nw; __i++)
00142       _M_w[__i] ^= __x._M_w[__i];
00143       }
00144 
00145       void
00146       _M_do_left_shift(size_t __shift);
00147 
00148       void
00149       _M_do_right_shift(size_t __shift);
00150 
00151       void
00152       _M_do_flip()
00153       {
00154     for (size_t __i = 0; __i < _Nw; __i++)
00155       _M_w[__i] = ~_M_w[__i];
00156       }
00157 
00158       void
00159       _M_do_set()
00160       {
00161     for (size_t __i = 0; __i < _Nw; __i++)
00162       _M_w[__i] = ~static_cast<_WordT>(0);
00163       }
00164 
00165       void
00166       _M_do_reset() { memset(_M_w, 0, _Nw * sizeof(_WordT)); }
00167 
00168       bool
00169       _M_is_equal(const _Base_bitset<_Nw>& __x) const
00170       {
00171     for (size_t __i = 0; __i < _Nw; ++__i)
00172       {
00173         if (_M_w[__i] != __x._M_w[__i])
00174           return false;
00175       }
00176     return true;
00177       }
00178 
00179       bool
00180       _M_is_any() const
00181       {
00182     for (size_t __i = 0; __i < _Nw; __i++)
00183       {
00184         if (_M_w[__i] != static_cast<_WordT>(0))
00185           return true;
00186       }
00187     return false;
00188       }
00189 
00190       size_t
00191       _M_do_count() const
00192       {
00193     size_t __result = 0;
00194     const unsigned char* __byte_ptr = (const unsigned char*)_M_w;
00195     const unsigned char* __end_ptr = (const unsigned char*)(_M_w + _Nw);
00196 
00197     while ( __byte_ptr < __end_ptr )
00198       {
00199         __result += _S_bit_count[*__byte_ptr];
00200         __byte_ptr++;
00201       }
00202     return __result;
00203       }
00204 
00205       unsigned long
00206       _M_do_to_ulong() const;
00207 
00208       // find first "on" bit
00209       size_t
00210       _M_do_find_first(size_t __not_found) const;
00211 
00212       // find the next "on" bit that follows "prev"
00213       size_t
00214       _M_do_find_next(size_t __prev, size_t __not_found) const;
00215     };
00216 
00217   // Definitions of non-inline functions from _Base_bitset.
00218   template<size_t _Nw>
00219     void
00220     _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift)
00221     {
00222       if (__shift != 0)
00223     {
00224       const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD;
00225       const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD;
00226 
00227       if (__offset == 0)
00228         for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
00229           _M_w[__n] = _M_w[__n - __wshift];
00230       else
00231         {
00232           const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset;
00233           for (size_t __n = _Nw - 1; __n > __wshift; --__n)
00234         _M_w[__n] = (_M_w[__n - __wshift] << __offset) |
00235           (_M_w[__n - __wshift - 1] >> __sub_offset);
00236           _M_w[__wshift] = _M_w[0] << __offset;
00237         }
00238 
00239       fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
00240     }
00241     }
00242 
00243   template<size_t _Nw>
00244     void
00245     _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift)
00246     {
00247       if (__shift != 0)
00248     {
00249       const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD;
00250       const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD;
00251       const size_t __limit = _Nw - __wshift - 1;
00252 
00253       if (__offset == 0)
00254         for (size_t __n = 0; __n <= __limit; ++__n)
00255           _M_w[__n] = _M_w[__n + __wshift];
00256       else
00257         {
00258           const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset;
00259           for (size_t __n = 0; __n < __limit; ++__n)
00260         _M_w[__n] = (_M_w[__n + __wshift] >> __offset) |
00261           (_M_w[__n + __wshift + 1] << __sub_offset);
00262           _M_w[__limit] = _M_w[_Nw-1] >> __offset;
00263         }
00264 
00265       fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
00266     }
00267     }
00268 
00269   template<size_t _Nw>
00270     unsigned long
00271     _Base_bitset<_Nw>::_M_do_to_ulong() const
00272     {
00273       for (size_t __i = 1; __i < _Nw; ++__i)
00274     if (_M_w[__i])
00275       __throw_overflow_error("bitset -- too large to fit in unsigned long");
00276       return _M_w[0];
00277     }
00278 
00279   template<size_t _Nw>
00280     size_t
00281     _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const
00282     {
00283       for (size_t __i = 0; __i < _Nw; __i++ )
00284     {
00285       _WordT __thisword = _M_w[__i];
00286       if ( __thisword != static_cast<_WordT>(0) )
00287         {
00288           // find byte within word
00289           for (size_t __j = 0; __j < sizeof(_WordT); __j++ )
00290         {
00291           unsigned char __this_byte
00292             = static_cast<unsigned char>(__thisword & (~(unsigned char)0));
00293           if (__this_byte)
00294             return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT +
00295               _S_first_one[__this_byte];
00296 
00297           __thisword >>= CHAR_BIT;
00298         }
00299         }
00300     }
00301       // not found, so return an indication of failure.
00302       return __not_found;
00303     }
00304 
00305   template<size_t _Nw>
00306     size_t
00307     _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const
00308     {
00309       // make bound inclusive
00310       ++__prev;
00311 
00312       // check out of bounds
00313       if ( __prev >= _Nw * _GLIBCPP_BITSET_BITS_PER_WORD )
00314     return __not_found;
00315 
00316       // search first word
00317       size_t __i = _S_whichword(__prev);
00318       _WordT __thisword = _M_w[__i];
00319 
00320       // mask off bits below bound
00321       __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
00322 
00323       if ( __thisword != static_cast<_WordT>(0) )
00324     {
00325       // find byte within word
00326       // get first byte into place
00327       __thisword >>= _S_whichbyte(__prev) * CHAR_BIT;
00328       for (size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++)
00329         {
00330           unsigned char __this_byte
00331         = static_cast<unsigned char>(__thisword & (~(unsigned char)0));
00332           if ( __this_byte )
00333         return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT +
00334           _S_first_one[__this_byte];
00335 
00336           __thisword >>= CHAR_BIT;
00337         }
00338     }
00339 
00340       // check subsequent words
00341       __i++;
00342       for ( ; __i < _Nw; __i++ )
00343     {
00344       __thisword = _M_w[__i];
00345       if ( __thisword != static_cast<_WordT>(0) )
00346         {
00347           // find byte within word
00348           for (size_t __j = 0; __j < sizeof(_WordT); __j++ )
00349         {
00350           unsigned char __this_byte
00351             = static_cast<unsigned char>(__thisword & (~(unsigned char)0));
00352           if ( __this_byte )
00353             return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT +
00354               _S_first_one[__this_byte];
00355 
00356           __thisword >>= CHAR_BIT;
00357         }
00358         }
00359     }
00360       // not found, so return an indication of failure.
00361       return __not_found;
00362     } // end _M_do_find_next
00363 
00364 
00372   template<>
00373     struct _Base_bitset<1>
00374     {
00375       typedef unsigned long _WordT;
00376       _WordT _M_w;
00377 
00378       _Base_bitset( void ) : _M_w(0) {}
00379       _Base_bitset(unsigned long __val) : _M_w(__val) {}
00380 
00381       static size_t
00382       _S_whichword(size_t __pos )
00383       { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; }
00384 
00385       static size_t
00386       _S_whichbyte(size_t __pos )
00387       { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; }
00388 
00389       static size_t
00390       _S_whichbit(size_t __pos )
00391       {  return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; }
00392 
00393       static _WordT
00394       _S_maskbit(size_t __pos )
00395       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
00396 
00397       _WordT&
00398       _M_getword(size_t) { return _M_w; }
00399 
00400       _WordT
00401       _M_getword(size_t) const { return _M_w; }
00402 
00403       _WordT&
00404       _M_hiword() { return _M_w; }
00405 
00406       _WordT
00407       _M_hiword() const { return _M_w; }
00408 
00409       void
00410       _M_do_and(const _Base_bitset<1>& __x) { _M_w &= __x._M_w; }
00411 
00412       void
00413       _M_do_or(const _Base_bitset<1>& __x)  { _M_w |= __x._M_w; }
00414 
00415       void
00416       _M_do_xor(const _Base_bitset<1>& __x) { _M_w ^= __x._M_w; }
00417 
00418       void
00419       _M_do_left_shift(size_t __shift) { _M_w <<= __shift; }
00420 
00421       void
00422       _M_do_right_shift(size_t __shift) { _M_w >>= __shift; }
00423 
00424       void
00425       _M_do_flip() { _M_w = ~_M_w; }
00426 
00427       void
00428       _M_do_set() { _M_w = ~static_cast<_WordT>(0); }
00429 
00430       void
00431       _M_do_reset() { _M_w = 0; }
00432 
00433       bool
00434       _M_is_equal(const _Base_bitset<1>& __x) const
00435       { return _M_w == __x._M_w; }
00436 
00437       bool
00438       _M_is_any() const { return _M_w != 0; }
00439 
00440       size_t
00441       _M_do_count() const
00442       {
00443     size_t __result = 0;
00444     const unsigned char* __byte_ptr = (const unsigned char*)&_M_w;
00445     const unsigned char* __end_ptr
00446       = ((const unsigned char*)&_M_w)+sizeof(_M_w);
00447     while ( __byte_ptr < __end_ptr )
00448       {
00449         __result += _S_bit_count[*__byte_ptr];
00450         __byte_ptr++;
00451       }
00452     return __result;
00453       }
00454 
00455       unsigned long
00456       _M_do_to_ulong() const { return _M_w; }
00457 
00458       size_t
00459       _M_do_find_first(size_t __not_found) const;
00460 
00461       // find the next "on" bit that follows "prev"
00462       size_t
00463       _M_do_find_next(size_t __prev, size_t __not_found) const;
00464     };
00465 
00466 
00474   template<>
00475     struct _Base_bitset<0>
00476     {
00477       typedef unsigned long _WordT;
00478 
00479       _Base_bitset() {}
00480       _Base_bitset(unsigned long) {}
00481 
00482       static size_t
00483       _S_whichword(size_t __pos )
00484       { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; }
00485 
00486       static size_t
00487       _S_whichbyte(size_t __pos )
00488       { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; }
00489 
00490       static size_t
00491       _S_whichbit(size_t __pos )
00492       {  return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; }
00493 
00494       static _WordT
00495       _S_maskbit(size_t __pos )
00496       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
00497 
00498       // This would normally give access to the data.  The bounds-checking
00499       // in the bitset class will prevent the user from getting this far,
00500       // but (1) it must still return an lvalue to compile, and (2) the
00501       // user might call _Unchecked_set directly, in which case this /needs/
00502       // to fail.  Let's not penalize zero-length users unless they actually
00503       // make an unchecked call; all the memory ugliness is therefore
00504       // localized to this single should-never-get-this-far function.
00505       _WordT&
00506       _M_getword(size_t) const
00507       { __throw_out_of_range("bitset -- zero-length"); return *new _WordT; }
00508 
00509       _WordT
00510       _M_hiword() const { return 0; }
00511 
00512       void
00513       _M_do_and(const _Base_bitset<0>&) { }
00514 
00515       void
00516       _M_do_or(const _Base_bitset<0>&)  { }
00517 
00518       void
00519       _M_do_xor(const _Base_bitset<0>&) { }
00520 
00521       void
00522       _M_do_left_shift(size_t) { }
00523 
00524       void
00525       _M_do_right_shift(size_t) { }
00526 
00527       void
00528       _M_do_flip() { }
00529 
00530       void
00531       _M_do_set() { }
00532 
00533       void
00534       _M_do_reset() { }
00535 
00536       // Are all empty bitsets equal to each other?  Are they equal to
00537       // themselves?  How to compare a thing which has no state?  What is
00538       // the sound of one zero-length bitset clapping?
00539       bool
00540       _M_is_equal(const _Base_bitset<0>&) const { return true; }
00541 
00542       bool
00543       _M_is_any() const { return false; }
00544 
00545       size_t
00546       _M_do_count() const { return 0; }
00547 
00548       unsigned long
00549       _M_do_to_ulong() const { return 0; }
00550 
00551       // Normally "not found" is the size, but that could also be
00552       // misinterpreted as an index in this corner case.  Oh well.
00553       size_t
00554       _M_do_find_first(size_t) const { return 0; }
00555 
00556       size_t
00557       _M_do_find_next(size_t, size_t) const { return 0; }
00558     };
00559 
00560 
00561   // Helper class to zero out the unused high-order bits in the highest word.
00562   template<size_t _Extrabits>
00563     struct _Sanitize
00564     {
00565       static void _S_do_sanitize(unsigned long& __val)
00566       { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); }
00567     };
00568 
00569   template<>
00570     struct _Sanitize<0>
00571     { static void _S_do_sanitize(unsigned long) { } };
00572 
00634   template<size_t _Nb>
00635     class bitset : private _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)>
00636   {
00637   private:
00638     typedef _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> _Base;
00639     typedef unsigned long _WordT;
00640 
00641     void
00642     _M_do_sanitize()
00643     {
00644       _Sanitize<_Nb%_GLIBCPP_BITSET_BITS_PER_WORD>::
00645           _S_do_sanitize(this->_M_hiword());
00646     }
00647 
00648   public:
00661     class reference
00662     {
00663       friend class bitset;
00664 
00665       _WordT *_M_wp;
00666       size_t _M_bpos;
00667 
00668       // left undefined
00669       reference();
00670 
00671     public:
00672       reference(bitset& __b, size_t __pos)
00673       {
00674     _M_wp = &__b._M_getword(__pos);
00675     _M_bpos = _Base::_S_whichbit(__pos);
00676       }
00677 
00678       ~reference() { }
00679 
00680       // for b[i] = __x;
00681       reference&
00682       operator=(bool __x)
00683       {
00684     if ( __x )
00685       *_M_wp |= _Base::_S_maskbit(_M_bpos);
00686     else
00687       *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
00688     return *this;
00689       }
00690 
00691       // for b[i] = b[__j];
00692       reference&
00693       operator=(const reference& __j)
00694       {
00695     if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) )
00696       *_M_wp |= _Base::_S_maskbit(_M_bpos);
00697     else
00698       *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
00699     return *this;
00700       }
00701 
00702       // flips the bit
00703       bool
00704       operator~() const
00705       { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
00706 
00707       // for __x = b[i];
00708       operator bool() const
00709       { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
00710 
00711       // for b[i].flip();
00712       reference&
00713       flip()
00714       {
00715     *_M_wp ^= _Base::_S_maskbit(_M_bpos);
00716     return *this;
00717       }
00718     };
00719     friend class reference;
00720 
00721     // 23.3.5.1 constructors:
00723     bitset() { }
00724 
00726     bitset(unsigned long __val) : _Base(__val)
00727     { _M_do_sanitize(); }
00728 
00738     template<class _CharT, class _Traits, class _Alloc>
00739       explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s,
00740               size_t __pos = 0) : _Base()
00741       {
00742     if (__pos > __s.size())
00743       __throw_out_of_range("bitset -- initial position is larger than "
00744                            "the string itself");
00745     _M_copy_from_string(__s, __pos,
00746                 basic_string<_CharT, _Traits, _Alloc>::npos);
00747       }
00748 
00758     template<class _CharT, class _Traits, class _Alloc>
00759       bitset(const basic_string<_CharT, _Traits, _Alloc>& __s,
00760          size_t __pos, size_t __n) : _Base()
00761       {
00762     if (__pos > __s.size())
00763       __throw_out_of_range("bitset -- initial position is larger than "
00764                            "the string itself");
00765     _M_copy_from_string(__s, __pos, __n);
00766       }
00767 
00768     // 23.3.5.2 bitset operations:
00770 
00776     bitset<_Nb>&
00777     operator&=(const bitset<_Nb>& __rhs)
00778     {
00779       this->_M_do_and(__rhs);
00780       return *this;
00781     }
00782 
00783     bitset<_Nb>&
00784     operator|=(const bitset<_Nb>& __rhs)
00785     {
00786       this->_M_do_or(__rhs);
00787       return *this;
00788     }
00789 
00790     bitset<_Nb>&
00791     operator^=(const bitset<_Nb>& __rhs)
00792     {
00793       this->_M_do_xor(__rhs);
00794       return *this;
00795     }
00797 
00799 
00805     bitset<_Nb>&
00806     operator<<=(size_t __pos)
00807     {
00808       this->_M_do_left_shift(__pos);
00809       this->_M_do_sanitize();
00810       return *this;
00811     }
00812 
00813     bitset<_Nb>&
00814     operator>>=(size_t __pos)
00815     {
00816       this->_M_do_right_shift(__pos);
00817       this->_M_do_sanitize();
00818       return *this;
00819     }
00821 
00823 
00828     bitset<_Nb>&
00829     _Unchecked_set(size_t __pos)
00830     {
00831       this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
00832       return *this;
00833     }
00834 
00835     bitset<_Nb>&
00836     _Unchecked_set(size_t __pos, int __val)
00837     {
00838       if (__val)
00839     this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
00840       else
00841     this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
00842       return *this;
00843     }
00844 
00845     bitset<_Nb>&
00846     _Unchecked_reset(size_t __pos)
00847     {
00848       this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
00849       return *this;
00850     }
00851 
00852     bitset<_Nb>&
00853     _Unchecked_flip(size_t __pos)
00854     {
00855       this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
00856       return *this;
00857     }
00858 
00859     bool
00860     _Unchecked_test(size_t __pos) const
00861     {
00862       return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
00863     != static_cast<_WordT>(0);
00864     }
00866 
00867     // Set, reset, and flip.
00871     bitset<_Nb>&
00872     set()
00873     {
00874       this->_M_do_set();
00875       this->_M_do_sanitize();
00876       return *this;
00877     }
00878 
00885     bitset<_Nb>&
00886     set(size_t __pos, bool __val = true)
00887     {
00888       if (__pos >= _Nb)
00889     __throw_out_of_range("bitset -- set() argument too large");
00890       return _Unchecked_set(__pos, __val);
00891     }
00892 
00896     bitset<_Nb>&
00897     reset()
00898     {
00899       this->_M_do_reset();
00900       return *this;
00901     }
00902 
00910     bitset<_Nb>&
00911     reset(size_t __pos)
00912     {
00913       if (__pos >= _Nb)
00914     __throw_out_of_range("bitset -- reset() argument too large");
00915       return _Unchecked_reset(__pos);
00916     }
00917 
00921     bitset<_Nb>&
00922     flip()
00923     {
00924       this->_M_do_flip();
00925       this->_M_do_sanitize();
00926       return *this;
00927     }
00928 
00934     bitset<_Nb>&
00935     flip(size_t __pos)
00936     {
00937       if (__pos >= _Nb)
00938     __throw_out_of_range("bitset -- flip() argument too large");
00939       return _Unchecked_flip(__pos);
00940     }
00941 
00943     bitset<_Nb>
00944     operator~() const { return bitset<_Nb>(*this).flip(); }
00945 
00947 
00963     reference
00964     operator[](size_t __pos) { return reference(*this,__pos); }
00965 
00966     bool
00967     operator[](size_t __pos) const { return _Unchecked_test(__pos); }
00969 
00976     unsigned long
00977     to_ulong() const { return this->_M_do_to_ulong(); }
00978 
00993     template<class _CharT, class _Traits, class _Alloc>
00994       basic_string<_CharT, _Traits, _Alloc>
00995       to_string() const
00996       {
00997     basic_string<_CharT, _Traits, _Alloc> __result;
00998     _M_copy_to_string(__result);
00999     return __result;
01000       }
01001 
01002     // Helper functions for string operations.
01003     template<class _CharT, class _Traits, class _Alloc>
01004       void
01005       _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s,
01006                           size_t, size_t);
01007 
01008     template<class _CharT, class _Traits, class _Alloc>
01009       void
01010       _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const;
01011 
01013     size_t
01014     count() const { return this->_M_do_count(); }
01015 
01017     size_t
01018     size() const { return _Nb; }
01019 
01021 
01022     bool
01023     operator==(const bitset<_Nb>& __rhs) const
01024     { return this->_M_is_equal(__rhs); }
01025 
01026     bool
01027     operator!=(const bitset<_Nb>& __rhs) const
01028     { return !this->_M_is_equal(__rhs); }
01030 
01037     bool
01038     test(size_t __pos) const
01039     {
01040       if (__pos >= _Nb)
01041     __throw_out_of_range("bitset -- test() argument too large");
01042       return _Unchecked_test(__pos);
01043     }
01044 
01049     bool
01050     any() const { return this->_M_is_any(); }
01051 
01056     bool
01057     none() const { return !this->_M_is_any(); }
01058 
01060 
01061     bitset<_Nb>
01062     operator<<(size_t __pos) const
01063     { return bitset<_Nb>(*this) <<= __pos; }
01064 
01065     bitset<_Nb>
01066     operator>>(size_t __pos) const
01067     { return bitset<_Nb>(*this) >>= __pos; }
01069 
01076     size_t
01077     _Find_first() const
01078     { return this->_M_do_find_first(_Nb); }
01079 
01087     size_t
01088     _Find_next(size_t __prev ) const
01089     { return this->_M_do_find_next(__prev, _Nb); }
01090   };
01091 
01092   // Definitions of non-inline member functions.
01093   template<size_t _Nb>
01094     template<class _CharT, class _Traits, class _Alloc>
01095     void
01096     bitset<_Nb>::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, size_t __pos, size_t __n)
01097     {
01098       reset();
01099       const size_t __nbits = min(_Nb, min(__n, __s.size() - __pos));
01100       for (size_t __i = 0; __i < __nbits; ++__i)
01101     {
01102       switch(__s[__pos + __nbits - __i - 1])
01103         {
01104         case '0':
01105           break;
01106         case '1':
01107           set(__i);
01108           break;
01109         default:
01110           __throw_invalid_argument("bitset -- string contains characters "
01111                                    "which are neither 0 nor 1");
01112         }
01113     }
01114     }
01115 
01116   template<size_t _Nb>
01117     template<class _CharT, class _Traits, class _Alloc>
01118     void
01119     bitset<_Nb>::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const
01120     {
01121       __s.assign(_Nb, '0');
01122       for (size_t __i = 0; __i < _Nb; ++__i)
01123     if (_Unchecked_test(__i))
01124       __s[_Nb - 1 - __i] = '1';
01125     }
01126 
01127   // 23.3.5.3 bitset operations:
01129 
01137   template<size_t _Nb>
01138     inline bitset<_Nb>
01139     operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
01140     {
01141       bitset<_Nb> __result(__x);
01142       __result &= __y;
01143       return __result;
01144     }
01145 
01146   template<size_t _Nb>
01147     inline bitset<_Nb>
01148     operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
01149     {
01150       bitset<_Nb> __result(__x);
01151       __result |= __y;
01152       return __result;
01153     }
01154 
01155   template <size_t _Nb>
01156     inline bitset<_Nb>
01157     operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
01158     {
01159       bitset<_Nb> __result(__x);
01160       __result ^= __y;
01161       return __result;
01162     }
01164 
01166 
01174   template<class _CharT, class _Traits, size_t _Nb>
01175     basic_istream<_CharT, _Traits>&
01176     operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
01177     {
01178       typedef typename _Traits::char_type char_type;
01179       basic_string<_CharT, _Traits> __tmp;
01180       __tmp.reserve(_Nb);
01181 
01182       // Skip whitespace
01183       typename basic_istream<_CharT, _Traits>::sentry __sentry(__is);
01184       if (__sentry)
01185     {
01186       basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf();
01187       for (size_t __i = 0; __i < _Nb; ++__i)
01188         {
01189           static typename _Traits::int_type __eof = _Traits::eof();
01190 
01191           typename _Traits::int_type __c1 = __buf->sbumpc();
01192           if (_Traits::eq_int_type(__c1, __eof))
01193         {
01194           __is.setstate(ios_base::eofbit);
01195           break;
01196         }
01197           else
01198         {
01199           char_type __c2 = _Traits::to_char_type(__c1);
01200           char_type __c  = __is.narrow(__c2, '*');
01201 
01202           if (__c == '0' || __c == '1')
01203             __tmp.push_back(__c);
01204           else if (_Traits::eq_int_type(__buf->sputbackc(__c2),
01205                         __eof))
01206             {
01207               __is.setstate(ios_base::failbit);
01208               break;
01209             }
01210         }
01211         }
01212 
01213       if (__tmp.empty() && !_Nb)
01214         __is.setstate(ios_base::failbit);
01215       else
01216         __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb);
01217     }
01218 
01219       return __is;
01220     }
01221 
01222   template <class _CharT, class _Traits, size_t _Nb>
01223     basic_ostream<_CharT, _Traits>&
01224     operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x)
01225     {
01226       basic_string<_CharT, _Traits> __tmp;
01227       __x._M_copy_to_string(__tmp);
01228       return __os << __tmp;
01229     }
01231 } // namespace std
01232 
01233 #undef _GLIBCPP_BITSET_WORDS
01234 
01235 #endif /* _GLIBCPP_BITSET_H */

Generated on Tue Dec 23 12:33:38 2003 for libstdc++-v3 Source by doxygen 1.3.4