Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

BenzeneBitset.hpp

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


6 Jan 2011 Doxygen 1.6.3