# bitset

Go to the documentation of this file.

    00001 // <bitset> -*- C++ -*-
    00002
    00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
    00004 // Free Software Foundation, Inc.
    00005 //
    00006 // This file is part of the GNU ISO C++ Library.  This library is free
    00007 // software; you can redistribute it and/or modify it under the
    00008 // terms of the GNU General Public License as published by the
    00009 // Free Software Foundation; either version 2, or (at your option)
    00010 // any later version.
    00011
    00012 // This library is distributed in the hope that it will be useful,
    00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00015 // GNU General Public License for more details.
    00016
    00017 // You should have received a copy of the GNU General Public License along
    00018 // with this library; see the file COPYING.  If not, write to the Free
    00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
    00020 // USA.
    00021
    00022 // As a special exception, you may use this file as part of a free software
    00023 // library without restriction.  Specifically, if other files instantiate
    00024 // templates or use macros or inline functions from this file, or you compile
    00025 // this file and link it with other files to produce an executable, this
    00026 // file does not by itself cause the resulting executable to be covered by
    00027 // the GNU General Public License.  This exception does not however
    00028 // invalidate any other reasons why the executable file might be covered by
    00029 // the GNU General Public License.
    00030
    00031 /*
    00032  * Copyright (c) 1998
    00033  * Silicon Graphics Computer Systems, Inc.
    00034  *
    00035  * Permission to use, copy, modify, distribute and sell this software
    00036  * and its documentation for any purpose is hereby granted without fee,
    00037  * provided that the above copyright notice appear in all copies and
    00038  * that both that copyright notice and this permission notice appear
    00039  * in supporting documentation.  Silicon Graphics makes no
    00040  * representations about the suitability of this software for any
    00041  * purpose.  It is provided "as is" without express or implied warranty.
    00042  */
    00043
    00044 /** @file include/bitset
    00045  *  This is a Standard C++ Library header.
    00046  */
    00047
    00048 #ifndef _GLIBCXX_BITSET
    00049 #define _GLIBCXX_BITSET 1
    00050
    00051 #pragma GCC system_header
    00052
    00053 #include <cstddef>     // For size_t
    00054 #include <cstring>     // For memset
    00055 #include <limits>      // For numeric_limits
    00056 #include <string>
    00057 #include <bits/functexcept.h>   // For invalid_argument, out_of_range,
    00058                                 // overflow_error
    00059 #include <ostream>     // For ostream (operator<<)
    00060 #include <istream>     // For istream (operator>>)
    00061
    00062 #define _GLIBCXX_BITSET_BITS_PER_WORD  numeric_limits<unsigned long>::digits
    00063 #define _GLIBCXX_BITSET_WORDS(__n) \
    00064  ((__n) < 1 ? 0 : ((__n) + _GLIBCXX_BITSET_BITS_PER_WORD - 1) \
    00065                   / _GLIBCXX_BITSET_BITS_PER_WORD)
    00066
    00067 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
    00068
    00069   /**
    00070    *  @if maint
    00071    *  Base class, general case.  It is a class inveriant that _Nw will be
    00072    *  nonnegative.
    00073    *
    00074    *  See documentation for bitset.
    00075    *  @endif
    00076   */
    00077   template<size_t _Nw>
    00078     struct _Base_bitset
    00079     {
    00080       typedef unsigned long _WordT;
    00081
    00082       /// 0 is the least significant word.
    00083       _WordT        _M_w[_Nw];
    00084
    00085       _Base_bitset()
    00086       { _M_do_reset(); }
    00087
    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 / _GLIBCXX_BITSET_BITS_PER_WORD; }
    00097
    00098       static size_t
    00099       _S_whichbyte(size_t __pos )
    00100       { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
    00101
    00102       static size_t
    00103       _S_whichbit(size_t __pos )
    00104       { return __pos % _GLIBCXX_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()
    00120       { return _M_w[_Nw - 1]; }
    00121
    00122       _WordT
    00123       _M_hiword() const
    00124       { return _M_w[_Nw - 1]; }
    00125
    00126       void
    00127       _M_do_and(const _Base_bitset<_Nw>& __x)
    00128       {
    00129     for (size_t __i = 0; __i < _Nw; __i++)
    00130       _M_w[__i] &= __x._M_w[__i];
    00131       }
    00132
    00133       void
    00134       _M_do_or(const _Base_bitset<_Nw>& __x)
    00135       {
    00136     for (size_t __i = 0; __i < _Nw; __i++)
    00137       _M_w[__i] |= __x._M_w[__i];
    00138       }
    00139
    00140       void
    00141       _M_do_xor(const _Base_bitset<_Nw>& __x)
    00142       {
    00143     for (size_t __i = 0; __i < _Nw; __i++)
    00144       _M_w[__i] ^= __x._M_w[__i];
    00145       }
    00146
    00147       void
    00148       _M_do_left_shift(size_t __shift);
    00149
    00150       void
    00151       _M_do_right_shift(size_t __shift);
    00152
    00153       void
    00154       _M_do_flip()
    00155       {
    00156     for (size_t __i = 0; __i < _Nw; __i++)
    00157       _M_w[__i] = ~_M_w[__i];
    00158       }
    00159
    00160       void
    00161       _M_do_set()
    00162       {
    00163     for (size_t __i = 0; __i < _Nw; __i++)
    00164       _M_w[__i] = ~static_cast<_WordT>(0);
    00165       }
    00166
    00167       void
    00168       _M_do_reset()
    00169       { std::memset(_M_w, 0, _Nw * sizeof(_WordT)); }
    00170
    00171       bool
    00172       _M_is_equal(const _Base_bitset<_Nw>& __x) const
    00173       {
    00174     for (size_t __i = 0; __i < _Nw; ++__i)
    00175       {
    00176         if (_M_w[__i] != __x._M_w[__i])
    00177           return false;
    00178       }
    00179     return true;
    00180       }
    00181
    00182       bool
    00183       _M_is_any() const
    00184       {
    00185     for (size_t __i = 0; __i < _Nw; __i++)
    00186       {
    00187         if (_M_w[__i] != static_cast<_WordT>(0))
    00188           return true;
    00189       }
    00190     return false;
    00191       }
    00192
    00193       size_t
    00194       _M_do_count() const
    00195       {
    00196     size_t __result = 0;
    00197     for (size_t __i = 0; __i < _Nw; __i++)
    00198       __result += __builtin_popcountl(_M_w[__i]);
    00199     return __result;
    00200       }
    00201
    00202       unsigned long
    00203       _M_do_to_ulong() const;
    00204
    00205       // find first "on" bit
    00206       size_t
    00207       _M_do_find_first(size_t __not_found) const;
    00208
    00209       // find the next "on" bit that follows "prev"
    00210       size_t
    00211       _M_do_find_next(size_t __prev, size_t __not_found) const;
    00212     };
    00213
    00214   // Definitions of non-inline functions from _Base_bitset.
    00215   template<size_t _Nw>
    00216     void
    00217     _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift)
    00218     {
    00219       if (__builtin_expect(__shift != 0, 1))
    00220     {
    00221       const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
    00222       const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
    00223
    00224       if (__offset == 0)
    00225         for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
    00226           _M_w[__n] = _M_w[__n - __wshift];
    00227       else
    00228         {
    00229           const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
    00230                        - __offset);
    00231           for (size_t __n = _Nw - 1; __n > __wshift; --__n)
    00232         _M_w[__n] = ((_M_w[__n - __wshift] << __offset)
    00233                  | (_M_w[__n - __wshift - 1] >> __sub_offset));
    00234           _M_w[__wshift] = _M_w[0] << __offset;
    00235         }
    00236
    00237       std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
    00238     }
    00239     }
    00240
    00241   template<size_t _Nw>
    00242     void
    00243     _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift)
    00244     {
    00245       if (__builtin_expect(__shift != 0, 1))
    00246     {
    00247       const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
    00248       const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
    00249       const size_t __limit = _Nw - __wshift - 1;
    00250
    00251       if (__offset == 0)
    00252         for (size_t __n = 0; __n <= __limit; ++__n)
    00253           _M_w[__n] = _M_w[__n + __wshift];
    00254       else
    00255         {
    00256           const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
    00257                        - __offset);
    00258           for (size_t __n = 0; __n < __limit; ++__n)
    00259         _M_w[__n] = ((_M_w[__n + __wshift] >> __offset)
    00260                  | (_M_w[__n + __wshift + 1] << __sub_offset));
    00261           _M_w[__limit] = _M_w[_Nw-1] >> __offset;
    00262         }
    00263
    00264       std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
    00265     }
    00266     }
    00267
    00268   template<size_t _Nw>
    00269     unsigned long
    00270     _Base_bitset<_Nw>::_M_do_to_ulong() const
    00271     {
    00272       for (size_t __i = 1; __i < _Nw; ++__i)
    00273     if (_M_w[__i])
    00274       __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong"));
    00275       return _M_w[0];
    00276     }
    00277
    00278   template<size_t _Nw>
    00279     size_t
    00280     _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const
    00281     {
    00282       for (size_t __i = 0; __i < _Nw; __i++)
    00283     {
    00284       _WordT __thisword = _M_w[__i];
    00285       if (__thisword != static_cast<_WordT>(0))
    00286         return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
    00287             + __builtin_ctzl(__thisword));
    00288     }
    00289       // not found, so return an indication of failure.
    00290       return __not_found;
    00291     }
    00292
    00293   template<size_t _Nw>
    00294     size_t
    00295     _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const
    00296     {
    00297       // make bound inclusive
    00298       ++__prev;
    00299
    00300       // check out of bounds
    00301       if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD)
    00302     return __not_found;
    00303
    00304       // search first word
    00305       size_t __i = _S_whichword(__prev);
    00306       _WordT __thisword = _M_w[__i];
    00307
    00308       // mask off bits below bound
    00309       __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
    00310
    00311       if (__thisword != static_cast<_WordT>(0))
    00312     return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
    00313         + __builtin_ctzl(__thisword));
    00314
    00315       // check subsequent words
    00316       __i++;
    00317       for (; __i < _Nw; __i++)
    00318     {
    00319       __thisword = _M_w[__i];
    00320       if (__thisword != static_cast<_WordT>(0))
    00321         return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
    00322             + __builtin_ctzl(__thisword));
    00323     }
    00324       // not found, so return an indication of failure.
    00325       return __not_found;
    00326     } // end _M_do_find_next
    00327
    00328   /**
    00329    *  @if maint
    00330    *  Base class, specialization for a single word.
    00331    *
    00332    *  See documentation for bitset.
    00333    *  @endif
    00334   */
    00335   template<>
    00336     struct _Base_bitset<1>
    00337     {
    00338       typedef unsigned long _WordT;
    00339       _WordT _M_w;
    00340
    00341       _Base_bitset(void)
    00342       : _M_w(0)
    00343       { }
    00344
    00345       _Base_bitset(unsigned long __val)
    00346       : _M_w(__val)
    00347       { }
    00348
    00349       static size_t
    00350       _S_whichword(size_t __pos )
    00351       { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
    00352
    00353       static size_t
    00354       _S_whichbyte(size_t __pos )
    00355       { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
    00356
    00357       static size_t
    00358       _S_whichbit(size_t __pos )
    00359       {  return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
    00360
    00361       static _WordT
    00362       _S_maskbit(size_t __pos )
    00363       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
    00364
    00365       _WordT&
    00366       _M_getword(size_t)
    00367       { return _M_w; }
    00368
    00369       _WordT
    00370       _M_getword(size_t) const
    00371       { return _M_w; }
    00372
    00373       _WordT&
    00374       _M_hiword()
    00375       { return _M_w; }
    00376
    00377       _WordT
    00378       _M_hiword() const
    00379       { return _M_w; }
    00380
    00381       void
    00382       _M_do_and(const _Base_bitset<1>& __x)
    00383       { _M_w &= __x._M_w; }
    00384
    00385       void
    00386       _M_do_or(const _Base_bitset<1>& __x)
    00387       { _M_w |= __x._M_w; }
    00388
    00389       void
    00390       _M_do_xor(const _Base_bitset<1>& __x)
    00391       { _M_w ^= __x._M_w; }
    00392
    00393       void
    00394       _M_do_left_shift(size_t __shift)
    00395       { _M_w <<= __shift; }
    00396
    00397       void
    00398       _M_do_right_shift(size_t __shift)
    00399       { _M_w >>= __shift; }
    00400
    00401       void
    00402       _M_do_flip()
    00403       { _M_w = ~_M_w; }
    00404
    00405       void
    00406       _M_do_set()
    00407       { _M_w = ~static_cast<_WordT>(0); }
    00408
    00409       void
    00410       _M_do_reset()
    00411       { _M_w = 0; }
    00412
    00413       bool
    00414       _M_is_equal(const _Base_bitset<1>& __x) const
    00415       { return _M_w == __x._M_w; }
    00416
    00417       bool
    00418       _M_is_any() const
    00419       { return _M_w != 0; }
    00420
    00421       size_t
    00422       _M_do_count() const
    00423       { return __builtin_popcountl(_M_w); }
    00424
    00425       unsigned long
    00426       _M_do_to_ulong() const
    00427       { return _M_w; }
    00428
    00429       size_t
    00430       _M_do_find_first(size_t __not_found) const
    00431       {
    00432         if (_M_w != 0)
    00433           return __builtin_ctzl(_M_w);
    00434         else
    00435           return __not_found;
    00436       }
    00437
    00438       // find the next "on" bit that follows "prev"
    00439       size_t
    00440       _M_do_find_next(size_t __prev, size_t __not_found) const
    00441       {
    00442     ++__prev;
    00443     if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD))
    00444       return __not_found;
    00445
    00446     _WordT __x = _M_w >> __prev;
    00447     if (__x != 0)
    00448       return __builtin_ctzl(__x) + __prev;
    00449     else
    00450       return __not_found;
    00451       }
    00452     };
    00453
    00454   /**
    00455    *  @if maint
    00456    *  Base class, specialization for no storage (zero-length %bitset).
    00457    *
    00458    *  See documentation for bitset.
    00459    *  @endif
    00460   */
    00461   template<>
    00462     struct _Base_bitset<0>
    00463     {
    00464       typedef unsigned long _WordT;
    00465
    00466       _Base_bitset()
    00467       { }
    00468
    00469       _Base_bitset(unsigned long)
    00470       { }
    00471
    00472       static size_t
    00473       _S_whichword(size_t __pos )
    00474       { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
    00475
    00476       static size_t
    00477       _S_whichbyte(size_t __pos )
    00478       { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
    00479
    00480       static size_t
    00481       _S_whichbit(size_t __pos )
    00482       {  return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
    00483
    00484       static _WordT
    00485       _S_maskbit(size_t __pos )
    00486       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
    00487
    00488       // This would normally give access to the data.  The bounds-checking
    00489       // in the bitset class will prevent the user from getting this far,
    00490       // but (1) it must still return an lvalue to compile, and (2) the
    00491       // user might call _Unchecked_set directly, in which case this /needs/
    00492       // to fail.  Let's not penalize zero-length users unless they actually
    00493       // make an unchecked call; all the memory ugliness is therefore
    00494       // localized to this single should-never-get-this-far function.
    00495       _WordT&
    00496       _M_getword(size_t) const
    00497       {
    00498     __throw_out_of_range(__N("_Base_bitset::_M_getword"));
    00499     return *new _WordT;
    00500       }
    00501
    00502       _WordT
    00503       _M_hiword() const
    00504       { return 0; }
    00505
    00506       void
    00507       _M_do_and(const _Base_bitset<0>&)
    00508       { }
    00509
    00510       void
    00511       _M_do_or(const _Base_bitset<0>&)
    00512       { }
    00513
    00514       void
    00515       _M_do_xor(const _Base_bitset<0>&)
    00516       { }
    00517
    00518       void
    00519       _M_do_left_shift(size_t)
    00520       { }
    00521
    00522       void
    00523       _M_do_right_shift(size_t)
    00524       { }
    00525
    00526       void
    00527       _M_do_flip()
    00528       { }
    00529
    00530       void
    00531       _M_do_set()
    00532       { }
    00533
    00534       void
    00535       _M_do_reset()
    00536       { }
    00537
    00538       // Are all empty bitsets equal to each other?  Are they equal to
    00539       // themselves?  How to compare a thing which has no state?  What is
    00540       // the sound of one zero-length bitset clapping?
    00541       bool
    00542       _M_is_equal(const _Base_bitset<0>&) const
    00543       { return true; }
    00544
    00545       bool
    00546       _M_is_any() const
    00547       { return false; }
    00548
    00549       size_t
    00550       _M_do_count() const
    00551       { return 0; }
    00552
    00553       unsigned long
    00554       _M_do_to_ulong() const
    00555       { return 0; }
    00556
    00557       // Normally "not found" is the size, but that could also be
    00558       // misinterpreted as an index in this corner case.  Oh well.
    00559       size_t
    00560       _M_do_find_first(size_t) const
    00561       { return 0; }
    00562
    00563       size_t
    00564       _M_do_find_next(size_t, size_t) const
    00565       { return 0; }
    00566     };
    00567
    00568
    00569   // Helper class to zero out the unused high-order bits in the highest word.
    00570   template<size_t _Extrabits>
    00571     struct _Sanitize
    00572     {
    00573       static void _S_do_sanitize(unsigned long& __val)
    00574       { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); }
    00575     };
    00576
    00577   template<>
    00578     struct _Sanitize<0>
    00579     { static void _S_do_sanitize(unsigned long) {} };
    00580
    00581   /**
    00582    *  @brief  The %bitset class represents a @e fixed-size sequence of bits.
    00583    *
    00584    *  @ingroup Containers
    00585    *
    00586    *  (Note that %bitset does @e not meet the formal requirements of a
    00587    *  <a href="tables.html#65">container</a>.  Mainly, it lacks iterators.)
    00588    *
    00589    *  The template argument, @a Nb, may be any non-negative number,
    00590    *  specifying the number of bits (e.g., "0", "12", "1024*1024").
    00591    *
    00592    *  In the general unoptimized case, storage is allocated in word-sized
    00593    *  blocks.  Let B be the number of bits in a word, then (Nb+(B-1))/B
    00594    *  words will be used for storage.  B - Nb%B bits are unused.  (They are
    00595    *  the high-order bits in the highest word.)  It is a class invariant
    00596    *  that those unused bits are always zero.
    00597    *
    00598    *  If you think of %bitset as "a simple array of bits," be aware that
    00599    *  your mental picture is reversed:  a %bitset behaves the same way as
    00600    *  bits in integers do, with the bit at index 0 in the "least significant
    00601    *  / right-hand" position, and the bit at index Nb-1 in the "most
    00602    *  significant / left-hand" position.  Thus, unlike other containers, a
    00603    *  %bitset's index "counts from right to left," to put it very loosely.
    00604    *
    00605    *  This behavior is preserved when translating to and from strings.  For
    00606    *  example, the first line of the following program probably prints
    00607    *  "b('a') is 0001100001" on a modern ASCII system.
    00608    *
    00609    *  @code
    00610    *     #include <bitset>
    00611    *     #include <iostream>
    00612    *     #include <sstream>
    00613    *
    00614    *     using namespace std;
    00615    *
    00616    *     int main()
    00617    *     {
    00618    *         long         a = 'a';
    00619    *         bitset<10>   b(a);
    00620    *
    00621    *         cout << "b('a') is " << b << endl;
    00622    *
    00623    *         ostringstream s;
    00624    *         s << b;
    00625    *         string  str = s.str();
    00626    *         cout << "index 3 in the string is " << str[3] << " but\n"
    00627    *              << "index 3 in the bitset is " << b[3] << endl;
    00628    *     }
    00629    *  @endcode
    00630    *
    00631    *  Also see http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23
    00632    *  for a description of extensions.
    00633    *
    00634    *  @if maint
    00635    *  Most of the actual code isn't contained in %bitset<> itself, but in the
    00636    *  base class _Base_bitset.  The base class works with whole words, not with
    00637    *  individual bits.  This allows us to specialize _Base_bitset for the
    00638    *  important special case where the %bitset is only a single word.
    00639    *
    00640    *  Extra confusion can result due to the fact that the storage for
    00641    *  _Base_bitset @e is a regular array, and is indexed as such.  This is
    00642    *  carefully encapsulated.
    00643    *  @endif
    00644   */
    00645   template<size_t _Nb>
    00646     class bitset
    00647     : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
    00648     {
    00649     private:
    00650       typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base;
    00651       typedef unsigned long _WordT;
    00652
    00653       void
    00654     _M_do_sanitize()
    00655     {
    00656       _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD>::
    00657 	    _S_do_sanitize(this->_M_hiword());
    00658     }
    00659
    00660     public:
    00661       /**
    00662        *  This encapsulates the concept of a single bit.  An instance of this
    00663        *  class is a proxy for an actual bit; this way the individual bit
    00664        *  operations are done as faster word-size bitwise instructions.
    00665        *
    00666        *  Most users will never need to use this class directly; conversions
    00667        *  to and from bool are automatic and should be transparent.  Overloaded
    00668        *  operators help to preserve the illusion.
    00669        *
    00670        *  (On a typical system, this "bit %reference" is 64 times the size of
    00671        *  an actual bit.  Ha.)
    00672        */
    00673       class reference
    00674       {
    00675     friend class bitset;
    00676
    00677     _WordT *_M_wp;
    00678     size_t _M_bpos;
    00679
    00680     // left undefined
    00681     reference();
    00682
    00683       public:
    00684     reference(bitset& __b, size_t __pos)
    00685     {
    00686       _M_wp = &__b._M_getword(__pos);
    00687       _M_bpos = _Base::_S_whichbit(__pos);
    00688     }
    00689
    00690     ~reference()
    00691     { }
    00692
    00693     // For b[i] = __x;
    00694     reference&
    00695     operator=(bool __x)
    00696     {
    00697       if (__x)
    00698         *_M_wp |= _Base::_S_maskbit(_M_bpos);
    00699       else
    00700         *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
    00701       return *this;
    00702     }
    00703
    00704     // For b[i] = b[__j];
    00705     reference&
    00706     operator=(const reference& __j)
    00707     {
    00708       if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
    00709         *_M_wp |= _Base::_S_maskbit(_M_bpos);
    00710       else
    00711         *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
    00712       return *this;
    00713     }
    00714
    00715     // Flips the bit
    00716     bool
    00717     operator~() const
    00718     { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
    00719
    00720     // For __x = b[i];
    00721     operator bool() const
    00722     { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
    00723
    00724     // For b[i].flip();
    00725     reference&
    00726     flip()
    00727     {
    00728       *_M_wp ^= _Base::_S_maskbit(_M_bpos);
    00729       return *this;
    00730     }
    00731       };
    00732       friend class reference;
    00733
    00734       // 23.3.5.1 constructors:
    00735       /// All bits set to zero.
    00736       bitset()
    00737       { }
    00738
    00739       /// Initial bits bitwise-copied from a single word (others set to zero).
    00740       bitset(unsigned long __val)
    00741       : _Base(__val)
    00742       { _M_do_sanitize(); }
    00743
    00744       /**
    00745        *  @brief  Use a subset of a string.
    00746        *  @param  s  A string of '0' and '1' characters.
    00747        *  @param  position  Index of the first character in @a s to use;
    00748        *                    defaults to zero.
    00749        *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
    00750        *  @throw  std::invalid_argument  If a character appears in the string
    00751        *                                 which is neither '0' nor '1'.
    00752        */
    00753       template<class _CharT, class _Traits, class _Alloc>
    00754     explicit
    00755     bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
    00756            size_t __position = 0)
    00757     : _Base()
    00758     {
    00759       if (__position > __s.size())
    00760         __throw_out_of_range(__N("bitset::bitset initial position "
    00761                      "not valid"));
    00762       _M_copy_from_string(__s, __position,
    00763                   std::basic_string<_CharT, _Traits, _Alloc>::npos);
    00764     }
    00765
    00766       /**
    00767        *  @brief  Use a subset of a string.
    00768        *  @param  s  A string of '0' and '1' characters.
    00769        *  @param  position  Index of the first character in @a s to use.
    00770        *  @param  n    The number of characters to copy.
    00771        *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
    00772        *  @throw  std::invalid_argument  If a character appears in the string
    00773        *                                 which is neither '0' nor '1'.
    00774        */
    00775       template<class _CharT, class _Traits, class _Alloc>
    00776     bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
    00777            size_t __position, size_t __n)
    00778     : _Base()
    00779     {
    00780       if (__position > __s.size())
    00781         __throw_out_of_range(__N("bitset::bitset initial position "
    00782                      "not valid"));
    00783       _M_copy_from_string(__s, __position, __n);
    00784     }
    00785
    00786       // 23.3.5.2 bitset operations:
    00787       //@{
    00788       /**
    00789        *  @brief  Operations on bitsets.
    00790        *  @param  rhs  A same-sized bitset.
    00791        *
    00792        *  These should be self-explanatory.
    00793        */
    00794       bitset<_Nb>&
    00795       operator&=(const bitset<_Nb>& __rhs)
    00796       {
    00797     this->_M_do_and(__rhs);
    00798     return *this;
    00799       }
    00800
    00801       bitset<_Nb>&
    00802       operator|=(const bitset<_Nb>& __rhs)
    00803       {
    00804     this->_M_do_or(__rhs);
    00805     return *this;
    00806       }
    00807
    00808       bitset<_Nb>&
    00809       operator^=(const bitset<_Nb>& __rhs)
    00810       {
    00811     this->_M_do_xor(__rhs);
    00812     return *this;
    00813       }
    00814       //@}
    00815
    00816       //@{
    00817       /**
    00818        *  @brief  Operations on bitsets.
    00819        *  @param  position  The number of places to shift.
    00820        *
    00821        *  These should be self-explanatory.
    00822        */
    00823       bitset<_Nb>&
    00824       operator<<=(size_t __position)
    00825       {
    00826     if (__builtin_expect(__position < _Nb, 1))
    00827       {
    00828         this->_M_do_left_shift(__position);
    00829         this->_M_do_sanitize();
    00830       }
    00831     else
    00832       this->_M_do_reset();
    00833     return *this;
    00834       }
    00835
    00836       bitset<_Nb>&
    00837       operator>>=(size_t __position)
    00838       {
    00839     if (__builtin_expect(__position < _Nb, 1))
    00840       {
    00841         this->_M_do_right_shift(__position);
    00842         this->_M_do_sanitize();
    00843       }
    00844     else
    00845       this->_M_do_reset();
    00846     return *this;
    00847       }
    00848       //@}
    00849
    00850       //@{
    00851       /**
    00852        *  These versions of single-bit set, reset, flip, and test are
    00853        *  extensions from the SGI version.  They do no range checking.
    00854        *  @ingroup SGIextensions
    00855        */
    00856       bitset<_Nb>&
    00857       _Unchecked_set(size_t __pos)
    00858       {
    00859     this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
    00860     return *this;
    00861       }
    00862
    00863       bitset<_Nb>&
    00864       _Unchecked_set(size_t __pos, int __val)
    00865       {
    00866     if (__val)
    00867       this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
    00868     else
    00869       this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
    00870     return *this;
    00871       }
    00872
    00873       bitset<_Nb>&
    00874       _Unchecked_reset(size_t __pos)
    00875       {
    00876     this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
    00877     return *this;
    00878       }
    00879
    00880       bitset<_Nb>&
    00881       _Unchecked_flip(size_t __pos)
    00882       {
    00883     this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
    00884     return *this;
    00885       }
    00886
    00887       bool
    00888       _Unchecked_test(size_t __pos) const
    00889       { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
    00890         != static_cast<_WordT>(0)); }
    00891       //@}
    00892
    00893       // Set, reset, and flip.
    00894       /**
    00895        *  @brief Sets every bit to true.
    00896        */
    00897       bitset<_Nb>&
    00898       set()
    00899       {
    00900     this->_M_do_set();
    00901     this->_M_do_sanitize();
    00902     return *this;
    00903       }
    00904
    00905       /**
    00906        *  @brief Sets a given bit to a particular value.
    00907        *  @param  position  The index of the bit.
    00908        *  @param  val  Either true or false, defaults to true.
    00909        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
    00910        */
    00911       bitset<_Nb>&
    00912       set(size_t __position, bool __val = true)
    00913       {
    00914     if (__position >= _Nb)
    00915       __throw_out_of_range(__N("bitset::set"));
    00916     return _Unchecked_set(__position, __val);
    00917       }
    00918
    00919       /**
    00920        *  @brief Sets every bit to false.
    00921        */
    00922       bitset<_Nb>&
    00923       reset()
    00924       {
    00925     this->_M_do_reset();
    00926     return *this;
    00927       }
    00928
    00929       /**
    00930        *  @brief Sets a given bit to false.
    00931        *  @param  position  The index of the bit.
    00932        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
    00933        *
    00934        *  Same as writing @c set(pos,false).
    00935        */
    00936       bitset<_Nb>&
    00937       reset(size_t __position)
    00938       {
    00939     if (__position >= _Nb)
    00940       __throw_out_of_range(__N("bitset::reset"));
    00941     return _Unchecked_reset(__position);
    00942       }
    00943
    00944       /**
    00945        *  @brief Toggles every bit to its opposite value.
    00946        */
    00947       bitset<_Nb>&
    00948       flip()
    00949       {
    00950     this->_M_do_flip();
    00951     this->_M_do_sanitize();
    00952     return *this;
    00953       }
    00954
    00955       /**
    00956        *  @brief Toggles a given bit to its opposite value.
    00957        *  @param  position  The index of the bit.
    00958        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
    00959        */
    00960       bitset<_Nb>&
    00961       flip(size_t __position)
    00962       {
    00963     if (__position >= _Nb)
    00964       __throw_out_of_range(__N("bitset::flip"));
    00965     return _Unchecked_flip(__position);
    00966       }
    00967
    00968       /// See the no-argument flip().
    00969       bitset<_Nb>
    00970       operator~() const
    00971       { return bitset<_Nb>(*this).flip(); }
    00972
    00973       //@{
    00974       /**
    00975        *  @brief  Array-indexing support.
    00976        *  @param  position  Index into the %bitset.
    00977        *  @return  A bool for a 'const %bitset'.  For non-const bitsets, an
    00978        *           instance of the reference proxy class.
    00979        *  @note  These operators do no range checking and throw no exceptions,
    00980        *         as required by DR 11 to the standard.
    00981        *
    00982        *  @if maint
    00983        *  _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already
    00984        *  resolves DR 11 (items 1 and 2), but does not do the range-checking
    00985        *  required by that DR's resolution.  -pme
    00986        *  The DR has since been changed:  range-checking is a precondition
    00987        *  (users' responsibility), and these functions must not throw.  -pme
    00988        *  @endif
    00989        */
    00990       reference
    00991       operator[](size_t __position)
    00992       { return reference(*this,__position); }
    00993
    00994       bool
    00995       operator[](size_t __position) const
    00996       { return _Unchecked_test(__position); }
    00997       //@}
    00998
    00999       /**
    01000        *  @brief Retuns a numerical interpretation of the %bitset.
    01001        *  @return  The integral equivalent of the bits.
    01002        *  @throw  std::overflow_error  If there are too many bits to be
    01003        *                               represented in an @c unsigned @c long.
    01004        */
    01005       unsigned long
    01006       to_ulong() const
    01007       { return this->_M_do_to_ulong(); }
    01008
    01009       /**
    01010        *  @brief Retuns a character interpretation of the %bitset.
    01011        *  @return  The string equivalent of the bits.
    01012        *
    01013        *  Note the ordering of the bits:  decreasing character positions
    01014        *  correspond to increasing bit positions (see the main class notes for
    01015        *  an example).
    01016        */
    01017       template<class _CharT, class _Traits, class _Alloc>
    01018     std::basic_string<_CharT, _Traits, _Alloc>
    01019     to_string() const
    01020     {
    01021       std::basic_string<_CharT, _Traits, _Alloc> __result;
    01022       _M_copy_to_string(__result);
    01023       return __result;
    01024     }
    01025
    01026       // _GLIBCXX_RESOLVE_LIB_DEFECTS
    01027       // 434. bitset::to_string() hard to use.
    01028       template<class _CharT, class _Traits>
    01029     std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
    01030     to_string() const
    01031     { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }
    01032
    01033       template<class _CharT>
    01034     std::basic_string<_CharT, std::char_traits<_CharT>,
    01035                       std::allocator<_CharT> >
    01036     to_string() const
    01037     {
    01038       return to_string<_CharT, std::char_traits<_CharT>,
    01039                        std::allocator<_CharT> >();
    01040     }
    01041
    01042       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
    01043       to_string() const
    01044       {
    01045     return to_string<char, std::char_traits<char>,
    01046                      std::allocator<char> >();
    01047       }
    01048
    01049       // Helper functions for string operations.
    01050       template<class _CharT, class _Traits, class _Alloc>
    01051     void
    01052     _M_copy_from_string(const std::basic_string<_CharT,
    01053                 _Traits, _Alloc>& __s,
    01054                 size_t, size_t);
    01055
    01056       template<class _CharT, class _Traits, class _Alloc>
    01057     void
    01058     _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&) const;
    01059
    01060       /// Returns the number of bits which are set.
    01061       size_t
    01062       count() const
    01063       { return this->_M_do_count(); }
    01064
    01065       /// Returns the total number of bits.
    01066       size_t
    01067       size() const
    01068       { return _Nb; }
    01069
    01070       //@{
    01071       /// These comparisons for equality/inequality are, well, @e bitwise.
    01072       bool
    01073       operator==(const bitset<_Nb>& __rhs) const
    01074       { return this->_M_is_equal(__rhs); }
    01075
    01076       bool
    01077       operator!=(const bitset<_Nb>& __rhs) const
    01078       { return !this->_M_is_equal(__rhs); }
    01079       //@}
    01080
    01081       /**
    01082        *  @brief Tests the value of a bit.
    01083        *  @param  position  The index of a bit.
    01084        *  @return  The value at @a pos.
    01085        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
    01086        */
    01087       bool
    01088       test(size_t __position) const
    01089       {
    01090     if (__position >= _Nb)
    01091       __throw_out_of_range(__N("bitset::test"));
    01092     return _Unchecked_test(__position);
    01093       }
    01094
    01095       /**
    01096        *  @brief Tests whether any of the bits are on.
    01097        *  @return  True if at least one bit is set.
    01098        */
    01099       bool
    01100       any() const
    01101       { return this->_M_is_any(); }
    01102
    01103       /**
    01104        *  @brief Tests whether any of the bits are on.
    01105        *  @return  True if none of the bits are set.
    01106        */
    01107       bool
    01108       none() const
    01109       { return !this->_M_is_any(); }
    01110
    01111       //@{
    01112       /// Self-explanatory.
    01113       bitset<_Nb>
    01114       operator<<(size_t __position) const
    01115       { return bitset<_Nb>(*this) <<= __position; }
    01116
    01117       bitset<_Nb>
    01118       operator>>(size_t __position) const
    01119       { return bitset<_Nb>(*this) >>= __position; }
    01120       //@}
    01121
    01122       /**
    01123        *  @brief  Finds the index of the first "on" bit.
    01124        *  @return  The index of the first bit set, or size() if not found.
    01125        *  @ingroup SGIextensions
    01126        *  @sa  _Find_next
    01127        */
    01128       size_t
    01129       _Find_first() const
    01130       { return this->_M_do_find_first(_Nb); }
    01131
    01132       /**
    01133        *  @brief  Finds the index of the next "on" bit after prev.
    01134        *  @return  The index of the next bit set, or size() if not found.
    01135        *  @param  prev  Where to start searching.
    01136        *  @ingroup SGIextensions
    01137        *  @sa  _Find_first
    01138        */
    01139       size_t
    01140       _Find_next(size_t __prev ) const
    01141       { return this->_M_do_find_next(__prev, _Nb); }
    01142     };
    01143
    01144   // Definitions of non-inline member functions.
    01145   template<size_t _Nb>
    01146     template<class _CharT, class _Traits, class _Alloc>
    01147       void
    01148       bitset<_Nb>::
    01149       _M_copy_from_string(const std::basic_string<_CharT, _Traits,
    01150               _Alloc>& __s, size_t __pos, size_t __n)
    01151       {
    01152     reset();
    01153     const size_t __nbits = std::min(_Nb, std::min(__n, __s.size() - __pos));
    01154     for (size_t __i = __nbits; __i > 0; --__i)
    01155       {
    01156         switch(__s[__pos + __nbits - __i])
    01157           {
    01158           case '0':
    01159         break;
    01160           case '1':
    01161         _Unchecked_set(__i - 1);
    01162         break;
    01163           default:
    01164         __throw_invalid_argument(__N("bitset::_M_copy_from_string"));
    01165           }
    01166       }
    01167       }
    01168
    01169   template<size_t _Nb>
    01170     template<class _CharT, class _Traits, class _Alloc>
    01171       void
    01172       bitset<_Nb>::
    01173       _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s) const
    01174       {
    01175     __s.assign(_Nb, '0');
    01176     for (size_t __i = _Nb; __i > 0; --__i)
    01177       if (_Unchecked_test(__i - 1))
    01178         __s[_Nb - __i] = '1';
    01179       }
    01180
    01181   // 23.3.5.3 bitset operations:
    01182   //@{
    01183   /**
    01184    *  @brief  Global bitwise operations on bitsets.
    01185    *  @param  x  A bitset.
    01186    *  @param  y  A bitset of the same size as @a x.
    01187    *  @return  A new bitset.
    01188    *
    01189    *  These should be self-explanatory.
    01190   */
    01191   template<size_t _Nb>
    01192     inline bitset<_Nb>
    01193     operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
    01194     {
    01195       bitset<_Nb> __result(__x);
    01196       __result &= __y;
    01197       return __result;
    01198     }
    01199
    01200   template<size_t _Nb>
    01201     inline bitset<_Nb>
    01202     operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
    01203     {
    01204       bitset<_Nb> __result(__x);
    01205       __result |= __y;
    01206       return __result;
    01207     }
    01208
    01209   template <size_t _Nb>
    01210     inline bitset<_Nb>
    01211     operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
    01212     {
    01213       bitset<_Nb> __result(__x);
    01214       __result ^= __y;
    01215       return __result;
    01216     }
    01217   //@}
    01218
    01219   //@{
    01220   /**
    01221    *  @brief Global I/O operators for bitsets.
    01222    *
    01223    *  Direct I/O between streams and bitsets is supported.  Output is
    01224    *  straightforward.  Input will skip whitespace, only accept '0' and '1'
    01225    *  characters, and will only extract as many digits as the %bitset will
    01226    *  hold.
    01227   */
    01228   template<class _CharT, class _Traits, size_t _Nb>
    01229     std::basic_istream<_CharT, _Traits>&
    01230     operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
    01231     {
    01232       typedef typename _Traits::char_type char_type;
    01233       std::basic_string<_CharT, _Traits> __tmp;
    01234       __tmp.reserve(_Nb);
    01235
    01236       std::ios_base::iostate __state = std::ios_base::goodbit;
    01237       typename std::basic_istream<_CharT, _Traits>::sentry __sentry(__is);
    01238       if (__sentry)
    01239     {
    01240       try
    01241         {
    01242           basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf();
    01243           // _GLIBCXX_RESOLVE_LIB_DEFECTS
    01244           // 303. Bitset input operator underspecified
    01245           const char_type __zero = __is.widen('0');
    01246           const char_type __one = __is.widen('1');
    01247           for (size_t __i = _Nb; __i > 0; --__i)
    01248         {
    01249           static typename _Traits::int_type __eof = _Traits::eof();
    01250
    01251           typename _Traits::int_type __c1 = __buf->sbumpc();
    01252           if (_Traits::eq_int_type(__c1, __eof))
    01253             {
    01254               __state |= std::ios_base::eofbit;
    01255               break;
    01256             }
    01257           else
    01258             {
    01259               const char_type __c2 = _Traits::to_char_type(__c1);
    01260               if (__c2 == __zero)
    01261             __tmp.push_back('0');
    01262               else if (__c2 == __one)
    01263             __tmp.push_back('1');
    01264               else if (_Traits::eq_int_type(__buf->sputbackc(__c2),
    01265                             __eof))
    01266             {
    01267               __state |= std::ios_base::failbit;
    01268               break;
    01269             }
    01270             }
    01271         }
    01272         }
    01273       catch(...)
    01274         { __is._M_setstate(std::ios_base::badbit); }
    01275     }
    01276
    01277       if (__tmp.empty() && _Nb)
    01278     __state |= std::ios_base::failbit;
    01279       else
    01280     __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb);
    01281       if (__state)
    01282     __is.setstate(__state);
    01283       return __is;
    01284     }
    01285
    01286   template <class _CharT, class _Traits, size_t _Nb>
    01287     std::basic_ostream<_CharT, _Traits>&
    01288     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    01289            const bitset<_Nb>& __x)
    01290     {
    01291       std::basic_string<_CharT, _Traits> __tmp;
    01292       __x._M_copy_to_string(__tmp);
    01293       return __os << __tmp;
    01294     }
    01295
    01296   // Specializations for zero-sized bitsets, to avoid "unsigned comparison
    01297   // with zero" warnings.
    01298   template<>
    01299     inline bitset<0>&
    01300     bitset<0>::
    01301     set(size_t, bool)
    01302     {
    01303       __throw_out_of_range(__N("bitset::set"));
    01304       return *this;
    01305     }
    01306
    01307   template<>
    01308     inline bitset<0>&
    01309     bitset<0>::
    01310     reset(size_t)
    01311     {
    01312       __throw_out_of_range(__N("bitset::reset"));
    01313       return *this;
    01314     }
    01315
    01316   template<>
    01317     inline bitset<0>&
    01318     bitset<0>::
    01319     flip(size_t)
    01320     {
    01321       __throw_out_of_range(__N("bitset::flip"));
    01322       return *this;
    01323     }
    01324
    01325   template<>
    01326     inline bool
    01327     bitset<0>::
    01328     test(size_t) const
    01329     {
    01330       __throw_out_of_range(__N("bitset::test"));
    01331       return false;
    01332     }
    01333   //@}
    01334
    01335 _GLIBCXX_END_NESTED_NAMESPACE
    01336
    01337 #undef _GLIBCXX_BITSET_WORDS
    01338 #undef _GLIBCXX_BITSET_BITS_PER_WORD
    01339
    01340 #ifdef _GLIBCXX_DEBUG
    01341 # include <debug/bitset>
    01342 #endif
    01343
    01344 #endif /* _GLIBCXX_BITSET */