bitset

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

Generated on Sat Dec 12 09:40:09 2009 for libstdc++ by  doxygen 1.5.6