bitset

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

Generated on Thu Jul 23 21:16:01 2009 for libstdc++ by  doxygen 1.5.8