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 
00043 /** @file bitset
00044  *  This is a Standard C++ Library header.  You should @c #include this header
00045  *  in your programs, rather than any of the "st[dl]_*.h" implementation files.
00046  */
00047 
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 
00071   /**
00072    *  @if maint
00073    *  Base class, general case.  It is a class inveriant that _Nw will be
00074    *  nonnegative.
00075    *
00076    *  See documentation for bitset.
00077    *  @endif
00078   */
00079   template<size_t _Nw>
00080     struct _Base_bitset
00081     {
00082       typedef unsigned long _WordT;
00083 
00084       /// 0 is the least significant word.
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 (__builtin_expect(__shift != 0, 1))
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 (__builtin_expect(__shift != 0, 1))
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 
00365   /**
00366    *  @if maint
00367    *  Base class, specialization for a single word.
00368    *
00369    *  See documentation for bitset.
00370    *  @endif
00371   */
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 
00467   /**
00468    *  @if maint
00469    *  Base class, specialization for no storage (zero-length %bitset).
00470    *
00471    *  See documentation for bitset.
00472    *  @endif
00473   */
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 
00573 
00574   /**
00575    *  @brief  The %bitset class represents a @e fixed-size sequence of bits.
00576    *
00577    *  @ingroup Containers
00578    *
00579    *  (Note that %bitset does @e not meet the formal requirements of a
00580    *  <a href="tables.html#65">container</a>.  Mainly, it lacks iterators.)
00581    *
00582    *  The template argument, @a Nb, may be any non-negative number,
00583    *  specifying the number of bits (e.g., "0", "12", "1024*1024").
00584    *
00585    *  In the general unoptimized case, storage is allocated in word-sized
00586    *  blocks.  Let B be the number of bits in a word, then (Nb+(B-1))/B
00587    *  words will be used for storage.  B - Nb%B bits are unused.  (They are
00588    *  the high-order bits in the highest word.)  It is a class invariant
00589    *  that those unused bits are always zero.
00590    *
00591    *  If you think of %bitset as "a simple array of bits," be aware that
00592    *  your mental picture is reversed:  a %bitset behaves the same way as
00593    *  bits in integers do, with the bit at index 0 in the "least significant
00594    *  / right-hand" position, and the bit at index Nb-1 in the "most
00595    *  significant / left-hand" position.  Thus, unlike other containers, a
00596    *  %bitset's index "counts from right to left," to put it very loosely.
00597    *
00598    *  This behavior is preserved when translating to and from strings.  For
00599    *  example, the first line of the following program probably prints
00600    *  "b('a') is 0001100001" on a modern ASCII system.
00601    *
00602    *  @code
00603    *     #include <bitset>
00604    *     #include <iostream>
00605    *     #include <sstream>
00606    *
00607    *     using namespace std;
00608    *
00609    *     int main()
00610    *     {
00611    *         long         a = 'a';
00612    *         bitset<10>   b(a);
00613    *
00614    *         cout << "b('a') is " << b << endl;
00615    *
00616    *         ostringstream s;
00617    *         s << b;
00618    *         string  str = s.str();
00619    *         cout << "index 3 in the string is " << str[3] << " but\n"
00620    *              << "index 3 in the bitset is " << b[3] << endl;
00621    *     }
00622    *  @endcode
00623    *
00624    *  Also see http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23
00625    *  for a description of extensions.
00626    *
00627    *  @if maint
00628    *  Most of the actual code isn't contained in %bitset<> itself, but in the
00629    *  base class _Base_bitset.  The base class works with whole words, not with
00630    *  individual bits.  This allows us to specialize _Base_bitset for the
00631    *  important special case where the %bitset is only a single word.
00632    *
00633    *  Extra confusion can result due to the fact that the storage for
00634    *  _Base_bitset @e is a regular array, and is indexed as such.  This is
00635    *  carefully encapsulated.
00636    *  @endif
00637   */
00638   template<size_t _Nb>
00639     class bitset : private _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)>
00640   {
00641   private:
00642     typedef _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> _Base;
00643     typedef unsigned long _WordT;
00644 
00645     void
00646     _M_do_sanitize()
00647     {
00648       _Sanitize<_Nb%_GLIBCPP_BITSET_BITS_PER_WORD>::
00649           _S_do_sanitize(this->_M_hiword());
00650     }
00651 
00652   public:
00653     /**
00654      *  This encapsulates the concept of a single bit.  An instance of this
00655      *  class is a proxy for an actual bit; this way the individual bit
00656      *  operations are done as faster word-size bitwise instructions.
00657      *
00658      *  Most users will never need to use this class directly; conversions
00659      *  to and from bool are automatic and should be transparent.  Overloaded
00660      *  operators help to preserve the illusion.
00661      *
00662      *  (On a typical system, this "bit %reference" is 64 times the size of
00663      *  an actual bit.  Ha.)
00664     */
00665     class reference
00666     {
00667       friend class bitset;
00668 
00669       _WordT *_M_wp;
00670       size_t _M_bpos;
00671 
00672       // left undefined
00673       reference();
00674 
00675     public:
00676       reference(bitset& __b, size_t __pos)
00677       {
00678     _M_wp = &__b._M_getword(__pos);
00679     _M_bpos = _Base::_S_whichbit(__pos);
00680       }
00681 
00682       ~reference() { }
00683 
00684       // for b[i] = __x;
00685       reference&
00686       operator=(bool __x)
00687       {
00688     if ( __x )
00689       *_M_wp |= _Base::_S_maskbit(_M_bpos);
00690     else
00691       *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
00692     return *this;
00693       }
00694 
00695       // for b[i] = b[__j];
00696       reference&
00697       operator=(const reference& __j)
00698       {
00699     if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) )
00700       *_M_wp |= _Base::_S_maskbit(_M_bpos);
00701     else
00702       *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
00703     return *this;
00704       }
00705 
00706       // flips the bit
00707       bool
00708       operator~() const
00709       { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
00710 
00711       // for __x = b[i];
00712       operator bool() const
00713       { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
00714 
00715       // for b[i].flip();
00716       reference&
00717       flip()
00718       {
00719     *_M_wp ^= _Base::_S_maskbit(_M_bpos);
00720     return *this;
00721       }
00722     };
00723     friend class reference;
00724 
00725     // 23.3.5.1 constructors:
00726     /// All bits set to zero.
00727     bitset() { }
00728 
00729     /// Initial bits bitwise-copied from a single word (others set to zero).
00730     bitset(unsigned long __val) : _Base(__val)
00731     { _M_do_sanitize(); }
00732 
00733     /**
00734      *  @brief  Use a subset of a string.
00735      *  @param  s  A string of '0' and '1' characters.
00736      *  @param  pos  Index of the first character in @a s to use; defaults
00737      *               to zero.
00738      *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
00739      *  @throw  std::invalid_argument  If a character appears in the string
00740      *                                 which is neither '0' nor '1'.
00741     */
00742     template<class _CharT, class _Traits, class _Alloc>
00743       explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s,
00744               size_t __pos = 0) : _Base()
00745       {
00746     if (__pos > __s.size())
00747       __throw_out_of_range("bitset -- initial position is larger than "
00748                            "the string itself");
00749     _M_copy_from_string(__s, __pos,
00750                 basic_string<_CharT, _Traits, _Alloc>::npos);
00751       }
00752 
00753     /**
00754      *  @brief  Use a subset of a string.
00755      *  @param  s  A string of '0' and '1' characters.
00756      *  @param  pos  Index of the first character in @a s to use.
00757      *  @param  n    The number of characters to copy.
00758      *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
00759      *  @throw  std::invalid_argument  If a character appears in the string
00760      *                                 which is neither '0' nor '1'.
00761     */
00762     template<class _CharT, class _Traits, class _Alloc>
00763       bitset(const basic_string<_CharT, _Traits, _Alloc>& __s,
00764          size_t __pos, size_t __n) : _Base()
00765       {
00766     if (__pos > __s.size())
00767       __throw_out_of_range("bitset -- initial position is larger than "
00768                            "the string itself");
00769     _M_copy_from_string(__s, __pos, __n);
00770       }
00771 
00772     // 23.3.5.2 bitset operations:
00773     //@{
00774     /**
00775      *  @brief  Operations on bitsets.
00776      *  @param  rhs  A same-sized bitset.
00777      *
00778      *  These should be self-explanatory.
00779     */
00780     bitset<_Nb>&
00781     operator&=(const bitset<_Nb>& __rhs)
00782     {
00783       this->_M_do_and(__rhs);
00784       return *this;
00785     }
00786 
00787     bitset<_Nb>&
00788     operator|=(const bitset<_Nb>& __rhs)
00789     {
00790       this->_M_do_or(__rhs);
00791       return *this;
00792     }
00793 
00794     bitset<_Nb>&
00795     operator^=(const bitset<_Nb>& __rhs)
00796     {
00797       this->_M_do_xor(__rhs);
00798       return *this;
00799     }
00800     //@}
00801 
00802     //@{
00803     /**
00804      *  @brief  Operations on bitsets.
00805      *  @param  pos  The number of places to shift.
00806      *
00807      *  These should be self-explanatory.
00808     */
00809     bitset<_Nb>&
00810     operator<<=(size_t __pos)
00811     {
00812       if (__builtin_expect(__pos < _Nb, 1))
00813         {
00814           this->_M_do_left_shift(__pos);
00815           this->_M_do_sanitize();
00816         }
00817       else
00818     this->_M_do_reset();
00819       return *this;
00820     }
00821 
00822     bitset<_Nb>&
00823     operator>>=(size_t __pos)
00824     {
00825       if (__builtin_expect(__pos < _Nb, 1))
00826         {
00827           this->_M_do_right_shift(__pos);
00828           this->_M_do_sanitize();
00829         }
00830       else
00831     this->_M_do_reset();
00832       return *this;
00833     }
00834     //@}
00835 
00836     //@{
00837     /**
00838      *  These versions of single-bit set, reset, flip, and test are
00839      *  extensions from the SGI version.  They do no range checking.
00840      *  @ingroup SGIextensions
00841     */
00842     bitset<_Nb>&
00843     _Unchecked_set(size_t __pos)
00844     {
00845       this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
00846       return *this;
00847     }
00848 
00849     bitset<_Nb>&
00850     _Unchecked_set(size_t __pos, int __val)
00851     {
00852       if (__val)
00853     this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
00854       else
00855     this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
00856       return *this;
00857     }
00858 
00859     bitset<_Nb>&
00860     _Unchecked_reset(size_t __pos)
00861     {
00862       this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
00863       return *this;
00864     }
00865 
00866     bitset<_Nb>&
00867     _Unchecked_flip(size_t __pos)
00868     {
00869       this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
00870       return *this;
00871     }
00872 
00873     bool
00874     _Unchecked_test(size_t __pos) const
00875     {
00876       return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
00877     != static_cast<_WordT>(0);
00878     }
00879     //@}
00880 
00881     // Set, reset, and flip.
00882     /**
00883      *  @brief Sets every bit to true.
00884     */
00885     bitset<_Nb>&
00886     set()
00887     {
00888       this->_M_do_set();
00889       this->_M_do_sanitize();
00890       return *this;
00891     }
00892 
00893     /**
00894      *  @brief Sets a given bit to a particular value.
00895      *  @param  pos  The index of the bit.
00896      *  @param  val  Either true or false, defaults to true.
00897      *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
00898     */
00899     bitset<_Nb>&
00900     set(size_t __pos, bool __val = true)
00901     {
00902       if (__pos >= _Nb)
00903     __throw_out_of_range("bitset -- set() argument too large");
00904       return _Unchecked_set(__pos, __val);
00905     }
00906 
00907     /**
00908      *  @brief Sets every bit to false.
00909     */
00910     bitset<_Nb>&
00911     reset()
00912     {
00913       this->_M_do_reset();
00914       return *this;
00915     }
00916 
00917     /**
00918      *  @brief Sets a given bit to false.
00919      *  @param  pos  The index of the bit.
00920      *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
00921      *
00922      *  Same as writing @c set(pos,false).
00923     */
00924     bitset<_Nb>&
00925     reset(size_t __pos)
00926     {
00927       if (__pos >= _Nb)
00928     __throw_out_of_range("bitset -- reset() argument too large");
00929       return _Unchecked_reset(__pos);
00930     }
00931 
00932     /**
00933      *  @brief Toggles every bit to its opposite value.
00934     */
00935     bitset<_Nb>&
00936     flip()
00937     {
00938       this->_M_do_flip();
00939       this->_M_do_sanitize();
00940       return *this;
00941     }
00942 
00943     /**
00944      *  @brief Toggles a given bit to its opposite value.
00945      *  @param  pos  The index of the bit.
00946      *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
00947     */
00948     bitset<_Nb>&
00949     flip(size_t __pos)
00950     {
00951       if (__pos >= _Nb)
00952     __throw_out_of_range("bitset -- flip() argument too large");
00953       return _Unchecked_flip(__pos);
00954     }
00955 
00956     /// See the no-argument flip().
00957     bitset<_Nb>
00958     operator~() const { return bitset<_Nb>(*this).flip(); }
00959 
00960     //@{
00961     /**
00962      *  @brief  Array-indexing support.
00963      *  @param  pos  Index into the %bitset.
00964      *  @return  A bool for a 'const %bitset'.  For non-const bitsets, an
00965      *           instance of the reference proxy class.
00966      *  @note  These operators do no range checking and throw no exceptions,
00967      *         as required by DR 11 to the standard.
00968      *
00969      *  @if maint
00970      *  _GLIBCPP_RESOLVE_LIB_DEFECTS Note that this implementation already
00971      *  resolves DR 11 (items 1 and 2), but does not do the range-checking
00972      *  required by that DR's resolution.  -pme
00973      *  The DR has since been changed:  range-checking is a precondition
00974      *  (users' responsibility), and these functions must not throw.  -pme
00975      *  @endif
00976     */
00977     reference
00978     operator[](size_t __pos) { return reference(*this,__pos); }
00979 
00980     bool
00981     operator[](size_t __pos) const { return _Unchecked_test(__pos); }
00982     //@}
00983 
00984     /**
00985      *  @brief Retuns a numerical interpretation of the %bitset.
00986      *  @return  The integral equivalent of the bits.
00987      *  @throw  std::overflow_error  If there are too many bits to be
00988      *                               represented in an @c unsigned @c long.
00989     */
00990     unsigned long
00991     to_ulong() const { return this->_M_do_to_ulong(); }
00992 
00993     /**
00994      *  @brief Retuns a character interpretation of the %bitset.
00995      *  @return  The string equivalent of the bits.
00996      *
00997      *  Note the ordering of the bits:  decreasing character positions
00998      *  correspond to increasing bit positions (see the main class notes for
00999      *  an example).
01000      *
01001      *  Also note that you must specify the string's template parameters
01002      *  explicitly.  Given a bitset @c bs and a string @s:
01003      *  @code
01004      *     s = bs.to_string<char,char_traits<char>,allocator<char> >();
01005      *  @endcode
01006     */
01007     template<class _CharT, class _Traits, class _Alloc>
01008       basic_string<_CharT, _Traits, _Alloc>
01009       to_string() const
01010       {
01011     basic_string<_CharT, _Traits, _Alloc> __result;
01012     _M_copy_to_string(__result);
01013     return __result;
01014       }
01015 
01016     // Helper functions for string operations.
01017     template<class _CharT, class _Traits, class _Alloc>
01018       void
01019       _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s,
01020                           size_t, size_t);
01021 
01022     template<class _CharT, class _Traits, class _Alloc>
01023       void
01024       _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const;
01025 
01026     /// Returns the number of bits which are set.
01027     size_t
01028     count() const { return this->_M_do_count(); }
01029 
01030     /// Returns the total number of bits.
01031     size_t
01032     size() const { return _Nb; }
01033 
01034     //@{
01035     /// These comparisons for equality/inequality are, well, @e bitwise.
01036     bool
01037     operator==(const bitset<_Nb>& __rhs) const
01038     { return this->_M_is_equal(__rhs); }
01039 
01040     bool
01041     operator!=(const bitset<_Nb>& __rhs) const
01042     { return !this->_M_is_equal(__rhs); }
01043     //@}
01044 
01045     /**
01046      *  @brief Tests the value of a bit.
01047      *  @param  pos  The index of a bit.
01048      *  @return  The value at @a pos.
01049      *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
01050     */
01051     bool
01052     test(size_t __pos) const
01053     {
01054       if (__pos >= _Nb)
01055     __throw_out_of_range("bitset -- test() argument too large");
01056       return _Unchecked_test(__pos);
01057     }
01058 
01059     /**
01060      *  @brief Tests whether any of the bits are on.
01061      *  @return  True if at least one bit is set.
01062     */
01063     bool
01064     any() const { return this->_M_is_any(); }
01065 
01066     /**
01067      *  @brief Tests whether any of the bits are on.
01068      *  @return  True if none of the bits are set.
01069     */
01070     bool
01071     none() const { return !this->_M_is_any(); }
01072 
01073     //@{
01074     /// Self-explanatory.
01075     bitset<_Nb>
01076     operator<<(size_t __pos) const
01077     { return bitset<_Nb>(*this) <<= __pos; }
01078 
01079     bitset<_Nb>
01080     operator>>(size_t __pos) const
01081     { return bitset<_Nb>(*this) >>= __pos; }
01082     //@}
01083 
01084     /**
01085      *  @brief  Finds the index of the first "on" bit.
01086      *  @return  The index of the first bit set, or size() if not found.
01087      *  @ingroup SGIextensions
01088      *  @sa  _Find_next
01089     */
01090     size_t
01091     _Find_first() const
01092     { return this->_M_do_find_first(_Nb); }
01093 
01094     /**
01095      *  @brief  Finds the index of the next "on" bit after prev.
01096      *  @return  The index of the next bit set, or size() if not found.
01097      *  @param  prev  Where to start searching.
01098      *  @ingroup SGIextensions
01099      *  @sa  _Find_first
01100     */
01101     size_t
01102     _Find_next(size_t __prev ) const
01103     { return this->_M_do_find_next(__prev, _Nb); }
01104   };
01105 
01106   // Definitions of non-inline member functions.
01107   template<size_t _Nb>
01108     template<class _CharT, class _Traits, class _Alloc>
01109     void
01110     bitset<_Nb>::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, size_t __pos, size_t __n)
01111     {
01112       reset();
01113       const size_t __nbits = min(_Nb, min(__n, __s.size() - __pos));
01114       for (size_t __i = 0; __i < __nbits; ++__i)
01115     {
01116       switch(__s[__pos + __nbits - __i - 1])
01117         {
01118         case '0':
01119           break;
01120         case '1':
01121           set(__i);
01122           break;
01123         default:
01124           __throw_invalid_argument("bitset -- string contains characters "
01125                                    "which are neither 0 nor 1");
01126         }
01127     }
01128     }
01129 
01130   template<size_t _Nb>
01131     template<class _CharT, class _Traits, class _Alloc>
01132     void
01133     bitset<_Nb>::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const
01134     {
01135       __s.assign(_Nb, '0');
01136       for (size_t __i = 0; __i < _Nb; ++__i)
01137     if (_Unchecked_test(__i))
01138       __s[_Nb - 1 - __i] = '1';
01139     }
01140 
01141   // 23.3.5.3 bitset operations:
01142   //@{
01143   /**
01144    *  @brief  Global bitwise operations on bitsets.
01145    *  @param  x  A bitset.
01146    *  @param  y  A bitset of the same size as @a x.
01147    *  @return  A new bitset.
01148    *
01149    *  These should be self-explanatory.
01150   */
01151   template<size_t _Nb>
01152     inline bitset<_Nb>
01153     operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
01154     {
01155       bitset<_Nb> __result(__x);
01156       __result &= __y;
01157       return __result;
01158     }
01159 
01160   template<size_t _Nb>
01161     inline bitset<_Nb>
01162     operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
01163     {
01164       bitset<_Nb> __result(__x);
01165       __result |= __y;
01166       return __result;
01167     }
01168 
01169   template <size_t _Nb>
01170     inline bitset<_Nb>
01171     operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
01172     {
01173       bitset<_Nb> __result(__x);
01174       __result ^= __y;
01175       return __result;
01176     }
01177   //@}
01178 
01179   //@{
01180   /**
01181    *  @brief Global I/O operators for bitsets.
01182    *
01183    *  Direct I/O between streams and bitsets is supported.  Output is
01184    *  straightforward.  Input will skip whitespace, only accept '0' and '1'
01185    *  characters, and will only extract as many digits as the %bitset will
01186    *  hold.
01187   */
01188   template<class _CharT, class _Traits, size_t _Nb>
01189     basic_istream<_CharT, _Traits>&
01190     operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
01191     {
01192       typedef typename _Traits::char_type char_type;
01193       basic_string<_CharT, _Traits> __tmp;
01194       __tmp.reserve(_Nb);
01195 
01196       // Skip whitespace
01197       typename basic_istream<_CharT, _Traits>::sentry __sentry(__is);
01198       if (__sentry)
01199     {
01200       ios_base::iostate  __state = ios_base::goodbit;
01201       basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf();
01202       for (size_t __i = 0; __i < _Nb; ++__i)
01203         {
01204           static typename _Traits::int_type __eof = _Traits::eof();
01205 
01206           typename _Traits::int_type __c1 = __buf->sbumpc();
01207           if (_Traits::eq_int_type(__c1, __eof))
01208         {
01209           __state |= ios_base::eofbit;
01210           break;
01211         }
01212           else
01213         {
01214           char_type __c2 = _Traits::to_char_type(__c1);
01215           char_type __c  = __is.narrow(__c2, '*');
01216 
01217           if (__c == '0' || __c == '1')
01218             __tmp.push_back(__c);
01219           else if (_Traits::eq_int_type(__buf->sputbackc(__c2), __eof))
01220             {
01221               __state |= ios_base::failbit;
01222               break;
01223             }
01224         }
01225         }
01226 
01227       if (__tmp.empty() && !_Nb)
01228         __state |= ios_base::failbit;
01229       else
01230         __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb);
01231 
01232       if (__state != ios_base::goodbit)
01233         __is.setstate(__state);    // may throw an exception
01234     }
01235 
01236       return __is;
01237     }
01238 
01239   template <class _CharT, class _Traits, size_t _Nb>
01240     basic_ostream<_CharT, _Traits>&
01241     operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x)
01242     {
01243       basic_string<_CharT, _Traits> __tmp;
01244       __x._M_copy_to_string(__tmp);
01245       return __os << __tmp;
01246     }
01247   //@}
01248 } // namespace std
01249 
01250 #undef _GLIBCPP_BITSET_WORDS
01251 
01252 #endif /* _GLIBCPP_BITSET_H */

Generated on Thu Feb 10 23:22:53 2005 for libstdc++-v3 Source by  doxygen 1.4.0