# bitset

    00001 // <bitset> -*- C++ -*-
    00002
    00003 // Copyright (C) 2001, 2002, 2003, 2004 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 _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 namespace _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 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                   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 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        *  Also note that you must specify the string's template parameters
    01018        *  explicitly.  Given a bitset @c bs and a string @s:
    01019        *  @code
    01020        *     s = bs.to_string<char,char_traits<char>,allocator<char> >();
    01021        *  @endcode
    01022        */
    01023       template<class _CharT, class _Traits, class _Alloc>
    01024     basic_string<_CharT, _Traits, _Alloc>
    01025     to_string() const
    01026     {
    01027       basic_string<_CharT, _Traits, _Alloc> __result;
    01028       _M_copy_to_string(__result);
    01029       return __result;
    01030     }
    01031
    01032       // Helper functions for string operations.
    01033       template<class _CharT, class _Traits, class _Alloc>
    01034     void
    01035     _M_copy_from_string(const basic_string<_CharT, _Traits, _Alloc>& __s,
    01036                 size_t, size_t);
    01037
    01038       template<class _CharT, class _Traits, class _Alloc>
    01039     void
    01040     _M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>&) const;
    01041
    01042       /// Returns the number of bits which are set.
    01043       size_t
    01044       count() const
    01045       { return this->_M_do_count(); }
    01046
    01047       /// Returns the total number of bits.
    01048       size_t
    01049       size() const
    01050       { return _Nb; }
    01051
    01052       //@{
    01053       /// These comparisons for equality/inequality are, well, @e bitwise.
    01054       bool
    01055       operator==(const bitset<_Nb>& __rhs) const
    01056       { return this->_M_is_equal(__rhs); }
    01057
    01058       bool
    01059       operator!=(const bitset<_Nb>& __rhs) const
    01060       { return !this->_M_is_equal(__rhs); }
    01061       //@}
    01062
    01063       /**
    01064        *  @brief Tests the value of a bit.
    01065        *  @param  position  The index of a bit.
    01066        *  @return  The value at @a pos.
    01067        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
    01068        */
    01069       bool
    01070       test(size_t __position) const
    01071       {
    01072     if (__position >= _Nb)
    01073       __throw_out_of_range(__N("bitset::test"));
    01074     return _Unchecked_test(__position);
    01075       }
    01076
    01077       /**
    01078        *  @brief Tests whether any of the bits are on.
    01079        *  @return  True if at least one bit is set.
    01080        */
    01081       bool
    01082       any() const
    01083       { return this->_M_is_any(); }
    01084
    01085       /**
    01086        *  @brief Tests whether any of the bits are on.
    01087        *  @return  True if none of the bits are set.
    01088        */
    01089       bool
    01090       none() const
    01091       { return !this->_M_is_any(); }
    01092
    01093       //@{
    01094       /// Self-explanatory.
    01095       bitset<_Nb>
    01096       operator<<(size_t __position) const
    01097       { return bitset<_Nb>(*this) <<= __position; }
    01098
    01099       bitset<_Nb>
    01100       operator>>(size_t __position) const
    01101       { return bitset<_Nb>(*this) >>= __position; }
    01102       //@}
    01103
    01104       /**
    01105        *  @brief  Finds the index of the first "on" bit.
    01106        *  @return  The index of the first bit set, or size() if not found.
    01107        *  @ingroup SGIextensions
    01108        *  @sa  _Find_next
    01109        */
    01110       size_t
    01111       _Find_first() const
    01112       { return this->_M_do_find_first(_Nb); }
    01113
    01114       /**
    01115        *  @brief  Finds the index of the next "on" bit after prev.
    01116        *  @return  The index of the next bit set, or size() if not found.
    01117        *  @param  prev  Where to start searching.
    01118        *  @ingroup SGIextensions
    01119        *  @sa  _Find_first
    01120        */
    01121       size_t
    01122       _Find_next(size_t __prev ) const
    01123       { return this->_M_do_find_next(__prev, _Nb); }
    01124     };
    01125
    01126   // Definitions of non-inline member functions.
    01127   template<size_t _Nb>
    01128     template<class _CharT, class _Traits, class _Alloc>
    01129       void
    01130       bitset<_Nb>::_M_copy_from_string(const basic_string<_CharT, _Traits,
    01131                        _Alloc>& __s, size_t __pos, size_t __n)
    01132       {
    01133     reset();
    01134     const size_t __nbits = std::min(_Nb, std::min(__n, __s.size() - __pos));
    01135     for (size_t __i = 0; __i < __nbits; ++__i)
    01136       {
    01137         switch(__s[__pos + __nbits - __i - 1])
    01138           {
    01139           case '0':
    01140         break;
    01141           case '1':
    01142         set(__i);
    01143         break;
    01144           default:
    01145         __throw_invalid_argument(__N("bitset::_M_copy_from_string"));
    01146           }
    01147       }
    01148       }
    01149
    01150   template<size_t _Nb>
    01151     template<class _CharT, class _Traits, class _Alloc>
    01152       void
    01153       bitset<_Nb>::_M_copy_to_string(basic_string<_CharT, _Traits,
    01154                      _Alloc>& __s) const
    01155       {
    01156     __s.assign(_Nb, '0');
    01157     for (size_t __i = 0; __i < _Nb; ++__i)
    01158       if (_Unchecked_test(__i))
    01159         __s[_Nb - 1 - __i] = '1';
    01160       }
    01161
    01162   // 23.3.5.3 bitset operations:
    01163   //@{
    01164   /**
    01165    *  @brief  Global bitwise operations on bitsets.
    01166    *  @param  x  A bitset.
    01167    *  @param  y  A bitset of the same size as @a x.
    01168    *  @return  A new bitset.
    01169    *
    01170    *  These should be self-explanatory.
    01171   */
    01172   template<size_t _Nb>
    01173     inline bitset<_Nb>
    01174     operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
    01175     {
    01176       bitset<_Nb> __result(__x);
    01177       __result &= __y;
    01178       return __result;
    01179     }
    01180
    01181   template<size_t _Nb>
    01182     inline bitset<_Nb>
    01183     operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
    01184     {
    01185       bitset<_Nb> __result(__x);
    01186       __result |= __y;
    01187       return __result;
    01188     }
    01189
    01190   template <size_t _Nb>
    01191     inline bitset<_Nb>
    01192     operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
    01193     {
    01194       bitset<_Nb> __result(__x);
    01195       __result ^= __y;
    01196       return __result;
    01197     }
    01198   //@}
    01199
    01200   //@{
    01201   /**
    01202    *  @brief Global I/O operators for bitsets.
    01203    *
    01204    *  Direct I/O between streams and bitsets is supported.  Output is
    01205    *  straightforward.  Input will skip whitespace, only accept '0' and '1'
    01206    *  characters, and will only extract as many digits as the %bitset will
    01207    *  hold.
    01208   */
    01209   template<class _CharT, class _Traits, size_t _Nb>
    01210     basic_istream<_CharT, _Traits>&
    01211     operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
    01212     {
    01213       typedef typename _Traits::char_type char_type;
    01214       basic_string<_CharT, _Traits> __tmp;
    01215       __tmp.reserve(_Nb);
    01216
    01217       ios_base::iostate __state = ios_base::goodbit;
    01218       typename basic_istream<_CharT, _Traits>::sentry __sentry(__is);
    01219       if (__sentry)
    01220     {
    01221       try
    01222         {
    01223           basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf();
    01224           // _GLIBCXX_RESOLVE_LIB_DEFECTS
    01225           // 303. Bitset input operator underspecified
    01226           const char_type __zero = __is.widen('0');
    01227           const char_type __one = __is.widen('1');
    01228           for (size_t __i = 0; __i < _Nb; ++__i)
    01229         {
    01230           static typename _Traits::int_type __eof = _Traits::eof();
    01231
    01232           typename _Traits::int_type __c1 = __buf->sbumpc();
    01233           if (_Traits::eq_int_type(__c1, __eof))
    01234             {
    01235               __state |= ios_base::eofbit;
    01236               break;
    01237             }
    01238           else
    01239             {
    01240               const char_type __c2 = _Traits::to_char_type(__c1);
    01241               if (__c2 == __zero)
    01242             __tmp.push_back('0');
    01243               else if (__c2 == __one)
    01244             __tmp.push_back('1');
    01245               else if (_Traits::eq_int_type(__buf->sputbackc(__c2),
    01246                             __eof))
    01247             {
    01248               __state |= ios_base::failbit;
    01249               break;
    01250             }
    01251             }
    01252         }
    01253         }
    01254       catch(...)
    01255         { __is._M_setstate(ios_base::badbit); }
    01256     }
    01257
    01258       if (__tmp.empty() && _Nb)
    01259     __state |= ios_base::failbit;
    01260       else
    01261     __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb);
    01262       if (__state)
    01263     __is.setstate(__state);
    01264       return __is;
    01265     }
    01266
    01267   template <class _CharT, class _Traits, size_t _Nb>
    01268     basic_ostream<_CharT, _Traits>&
    01269     operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x)
    01270     {
    01271       basic_string<_CharT, _Traits> __tmp;
    01272       __x._M_copy_to_string(__tmp);
    01273       return __os << __tmp;
    01274     }
    01275   //@}
    01276 } // namespace std
    01277
    01278 #undef _GLIBCXX_BITSET_WORDS
    01279 #undef _GLIBCXX_BITSET_BITS_PER_WORD
    01280
    01281 #ifdef _GLIBCXX_DEBUG
    01282 # include <debug/bitset>
    01283 #endif
    01284
    01285 #endif /* _GLIBCXX_BITSET */