Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. /*
  2.  * Copyright (c) 1998
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  */
  13.  
  14. #ifndef __SGI_STL_BITSET
  15. #define __SGI_STL_BITSET
  16.  
  17. #pragma GCC system_header
  18.  
  19. // A bitset of size N has N % (sizeof(unsigned long) * CHAR_BIT) unused
  20. // bits.  (They are the high- order bits in the highest word.)  It is
  21. // a class invariant of class bitset<> that those unused bits are
  22. // always zero.
  23.  
  24. // Most of the actual code isn't contained in bitset<> itself, but in the
  25. // base class _Base_bitset.  The base class works with whole words, not with
  26. // individual bits.  This allows us to specialize _Base_bitset for the
  27. // important special case where the bitset is only a single word.
  28.  
  29. // The C++ standard does not define the precise semantics of operator[].
  30. // In this implementation the const version of operator[] is equivalent
  31. // to test(), except that it does no range checking.  The non-const version
  32. // returns a reference to a bit, again without doing any range checking.
  33.  
  34.  
  35. #include <bits/std_cstddef.h>     // for size_t
  36. #include <bits/std_cstring.h>     // for memset
  37. #include <bits/std_string.h>
  38. #include <bits/std_stdexcept.h>   // for invalid_argument, out_of_range,
  39.                                   // overflow_error
  40.  
  41. #include <bits/std_ostream.h>     // for ostream (operator<<)
  42. #include <bits/std_istream.h>     // for istream (operator>>)
  43.  
  44. #define _GLIBCPP_BITSET_BITS_PER_WORD (CHAR_BIT*sizeof(unsigned long))
  45. #define __BITSET_WORDS(__n) \
  46.  ((__n) < 1 ? 1 : ((__n) + _GLIBCPP_BITSET_BITS_PER_WORD - 1)/_GLIBCPP_BITSET_BITS_PER_WORD)
  47.  
  48. namespace std
  49. {
  50.  
  51. // structure to aid in counting bits
  52. template<bool __dummy>
  53. struct _Bit_count {
  54.   static unsigned char _S_bit_count[256];
  55. };
  56.  
  57. // Mapping from 8 bit unsigned integers to the index of the first one
  58. // bit:
  59. template<bool __dummy>
  60. struct _First_one {
  61.   static unsigned char _S_first_one[256];
  62. };
  63.  
  64. //
  65. // Base class: general case.
  66. //
  67.  
  68. template<size_t _Nw>
  69. struct _Base_bitset {
  70.   typedef unsigned long _WordT;
  71.  
  72.   _WordT _M_w[_Nw];                // 0 is the least significant word.
  73.  
  74.   _Base_bitset( void ) { _M_do_reset(); }
  75.   _Base_bitset(unsigned long __val) {
  76.     _M_do_reset();
  77.     _M_w[0] = __val;
  78.   }
  79.  
  80.   static size_t _S_whichword( size_t __pos )
  81.     { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; }
  82.   static size_t _S_whichbyte( size_t __pos )
  83.     { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; }
  84.   static size_t _S_whichbit( size_t __pos )
  85.     { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; }
  86.   static _WordT _S_maskbit( size_t __pos )
  87.     { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
  88.  
  89.   _WordT& _M_getword(size_t __pos)       { return _M_w[_S_whichword(__pos)]; }
  90.   _WordT  _M_getword(size_t __pos) const { return _M_w[_S_whichword(__pos)]; }
  91.  
  92.   _WordT& _M_hiword()       { return _M_w[_Nw - 1]; }
  93.   _WordT  _M_hiword() const { return _M_w[_Nw - 1]; }
  94.  
  95.   void _M_do_and(const _Base_bitset<_Nw>& __x) {
  96.     for ( size_t __i = 0; __i < _Nw; __i++ ) {
  97.       _M_w[__i] &= __x._M_w[__i];
  98.     }
  99.   }
  100.  
  101.   void _M_do_or(const _Base_bitset<_Nw>& __x) {
  102.     for ( size_t __i = 0; __i < _Nw; __i++ ) {
  103.       _M_w[__i] |= __x._M_w[__i];
  104.     }
  105.   }
  106.  
  107.   void _M_do_xor(const _Base_bitset<_Nw>& __x) {
  108.     for ( size_t __i = 0; __i < _Nw; __i++ ) {
  109.       _M_w[__i] ^= __x._M_w[__i];
  110.     }
  111.   }
  112.  
  113.   void _M_do_left_shift(size_t __shift);
  114.   void _M_do_right_shift(size_t __shift);
  115.  
  116.   void _M_do_flip() {
  117.     for ( size_t __i = 0; __i < _Nw; __i++ ) {
  118.       _M_w[__i] = ~_M_w[__i];
  119.     }
  120.   }
  121.  
  122.   void _M_do_set() {
  123.     for ( size_t __i = 0; __i < _Nw; __i++ ) {
  124.       _M_w[__i] = ~static_cast<_WordT>(0);
  125.     }
  126.   }
  127.  
  128.   void _M_do_reset() { memset(_M_w, 0, _Nw * sizeof(_WordT)); }
  129.  
  130.   bool _M_is_equal(const _Base_bitset<_Nw>& __x) const {
  131.     for (size_t __i = 0; __i < _Nw; ++__i) {
  132.       if (_M_w[__i] != __x._M_w[__i])
  133.         return false;
  134.     }
  135.     return true;
  136.   }
  137.  
  138.   bool _M_is_any() const {
  139.     for ( size_t __i = 0; __i < _Nw; __i++ ) {
  140.       if ( _M_w[__i] != static_cast<_WordT>(0) )
  141.         return true;
  142.     }
  143.     return false;
  144.   }
  145.  
  146.   size_t _M_do_count() const {
  147.     size_t __result = 0;
  148.     const unsigned char* __byte_ptr = (const unsigned char*)_M_w;
  149.     const unsigned char* __end_ptr = (const unsigned char*)(_M_w+_Nw);
  150.  
  151.     while ( __byte_ptr < __end_ptr ) {
  152.       __result += _Bit_count<true>::_S_bit_count[*__byte_ptr];
  153.       __byte_ptr++;
  154.     }
  155.     return __result;
  156.   }
  157.  
  158.   unsigned long _M_do_to_ulong() const;
  159.  
  160.   // find first "on" bit
  161.   size_t _M_do_find_first(size_t __not_found) const;
  162.  
  163.   // find the next "on" bit that follows "prev"
  164.   size_t _M_do_find_next(size_t __prev, size_t __not_found) const;
  165. };
  166.  
  167. //
  168. // Definitions of non-inline functions from _Base_bitset.
  169. //
  170.  
  171. template<size_t _Nw>
  172. void _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift)
  173. {
  174.   if (__shift != 0) {
  175.     const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD;
  176.     const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD;
  177.  
  178.     if (__offset == 0)
  179.       for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
  180.         _M_w[__n] = _M_w[__n - __wshift];
  181.  
  182.     else {
  183.       const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset;
  184.       for (size_t __n = _Nw - 1; __n > __wshift; --__n)
  185.         _M_w[__n] = (_M_w[__n - __wshift] << __offset) |
  186.                     (_M_w[__n - __wshift - 1] >> __sub_offset);
  187.       _M_w[__wshift] = _M_w[0] << __offset;
  188.     }
  189.  
  190.     fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
  191.   }
  192. }
  193.  
  194. template<size_t _Nw>
  195. void _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift)
  196. {
  197.   if (__shift != 0) {
  198.     const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD;
  199.     const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD;
  200.     const size_t __limit = _Nw - __wshift - 1;
  201.  
  202.     if (__offset == 0)
  203.       for (size_t __n = 0; __n <= __limit; ++__n)
  204.         _M_w[__n] = _M_w[__n + __wshift];
  205.  
  206.     else {
  207.       const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset;
  208.       for (size_t __n = 0; __n < __limit; ++__n)
  209.         _M_w[__n] = (_M_w[__n + __wshift] >> __offset) |
  210.                     (_M_w[__n + __wshift + 1] << __sub_offset);
  211.       _M_w[__limit] = _M_w[_Nw-1] >> __offset;
  212.     }
  213.  
  214.     fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
  215.   }
  216. }
  217.  
  218. template<size_t _Nw>
  219. unsigned long _Base_bitset<_Nw>::_M_do_to_ulong() const
  220. {
  221.   for (size_t __i = 1; __i < _Nw; ++__i)
  222.     if (_M_w[__i])
  223.       __STL_THROW(overflow_error("bitset"));
  224.  
  225.   return _M_w[0];
  226. }
  227.  
  228. template<size_t _Nw>
  229. size_t _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const
  230. {
  231.   for ( size_t __i = 0; __i < _Nw; __i++ ) {
  232.     _WordT __thisword = _M_w[__i];
  233.     if ( __thisword != static_cast<_WordT>(0) ) {
  234.       // find byte within word
  235.       for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) {
  236.         unsigned char __this_byte
  237.           = static_cast<unsigned char>(__thisword & (~(unsigned char)0));
  238.         if ( __this_byte )
  239.           return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT +
  240.             _First_one<true>::_S_first_one[__this_byte];
  241.  
  242.         __thisword >>= CHAR_BIT;
  243.       }
  244.     }
  245.   }
  246.   // not found, so return an indication of failure.
  247.   return __not_found;
  248. }
  249.  
  250. template<size_t _Nw>
  251. size_t
  252. _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const
  253. {
  254.   // make bound inclusive
  255.   ++__prev;
  256.  
  257.   // check out of bounds
  258.   if ( __prev >= _Nw * _GLIBCPP_BITSET_BITS_PER_WORD )
  259.     return __not_found;
  260.  
  261.     // search first word
  262.   size_t __i = _S_whichword(__prev);
  263.   _WordT __thisword = _M_w[__i];
  264.  
  265.     // mask off bits below bound
  266.   __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
  267.  
  268.   if ( __thisword != static_cast<_WordT>(0) ) {
  269.     // find byte within word
  270.     // get first byte into place
  271.     __thisword >>= _S_whichbyte(__prev) * CHAR_BIT;
  272.     for ( size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++ ) {
  273.       unsigned char __this_byte
  274.         = static_cast<unsigned char>(__thisword & (~(unsigned char)0));
  275.       if ( __this_byte )
  276.         return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT +
  277.           _First_one<true>::_S_first_one[__this_byte];
  278.  
  279.       __thisword >>= CHAR_BIT;
  280.     }
  281.   }
  282.  
  283.   // check subsequent words
  284.   __i++;
  285.   for ( ; __i < _Nw; __i++ ) {
  286.     __thisword = _M_w[__i];
  287.     if ( __thisword != static_cast<_WordT>(0) ) {
  288.       // find byte within word
  289.       for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) {
  290.         unsigned char __this_byte
  291.           = static_cast<unsigned char>(__thisword & (~(unsigned char)0));
  292.         if ( __this_byte )
  293.           return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT +
  294.             _First_one<true>::_S_first_one[__this_byte];
  295.  
  296.         __thisword >>= CHAR_BIT;
  297.       }
  298.     }
  299.   }
  300.  
  301.   // not found, so return an indication of failure.
  302.   return __not_found;
  303. } // end _M_do_find_next
  304.  
  305.  
  306. // ------------------------------------------------------------
  307.  
  308. //
  309. // Base class: specialization for a single word.
  310. //
  311.  
  312. template<> struct _Base_bitset<1> {
  313.   typedef unsigned long _WordT;
  314.   _WordT _M_w;
  315.  
  316.   _Base_bitset( void ) : _M_w(0) {}
  317.   _Base_bitset(unsigned long __val) : _M_w(__val) {}
  318.  
  319.   static size_t _S_whichword( size_t __pos )
  320.     { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; }
  321.   static size_t _S_whichbyte( size_t __pos )
  322.     { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; }
  323.   static size_t _S_whichbit( size_t __pos )
  324.     {  return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; }
  325.   static _WordT _S_maskbit( size_t __pos )
  326.     { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
  327.  
  328.   _WordT& _M_getword(size_t)       { return _M_w; }
  329.   _WordT  _M_getword(size_t) const { return _M_w; }
  330.  
  331.   _WordT& _M_hiword()       { return _M_w; }
  332.   _WordT  _M_hiword() const { return _M_w; }
  333.  
  334.   void _M_do_and(const _Base_bitset<1>& __x) { _M_w &= __x._M_w; }
  335.   void _M_do_or(const _Base_bitset<1>& __x)  { _M_w |= __x._M_w; }
  336.   void _M_do_xor(const _Base_bitset<1>& __x) { _M_w ^= __x._M_w; }
  337.   void _M_do_left_shift(size_t __shift)     { _M_w <<= __shift; }
  338.   void _M_do_right_shift(size_t __shift)    { _M_w >>= __shift; }
  339.   void _M_do_flip()                       { _M_w = ~_M_w; }
  340.   void _M_do_set()                        { _M_w = ~static_cast<_WordT>(0); }
  341.   void _M_do_reset()                      { _M_w = 0; }
  342.  
  343.   bool _M_is_equal(const _Base_bitset<1>& __x) const
  344.     { return _M_w == __x._M_w; }
  345.   bool _M_is_any() const
  346.     { return _M_w != 0; }
  347.  
  348.   size_t _M_do_count() const {
  349.     size_t __result = 0;
  350.     const unsigned char* __byte_ptr = (const unsigned char*)&_M_w;
  351.     const unsigned char* __end_ptr
  352.       = ((const unsigned char*)&_M_w)+sizeof(_M_w);
  353.     while ( __byte_ptr < __end_ptr ) {
  354.       __result += _Bit_count<true>::_S_bit_count[*__byte_ptr];
  355.       __byte_ptr++;
  356.     }
  357.     return __result;
  358.   }
  359.  
  360.   unsigned long _M_do_to_ulong() const { return _M_w; }
  361.  
  362.   size_t _M_do_find_first(size_t __not_found) const;
  363.  
  364.   // find the next "on" bit that follows "prev"
  365.   size_t _M_do_find_next(size_t __prev, size_t __not_found) const;
  366.  
  367. };
  368.  
  369.  
  370. // ------------------------------------------------------------
  371. // Helper class to zero out the unused high-order bits in the highest word.
  372.  
  373. template <size_t _Extrabits> struct _Sanitize {
  374.   static void _M_do_sanitize(unsigned long& __val)
  375.     { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); }
  376. };
  377.  
  378. template<> struct _Sanitize<0> {
  379.   static void _M_do_sanitize(unsigned long) {}
  380. };
  381.  
  382.  
  383.  
  384. // ------------------------------------------------------------
  385. // Class bitset.
  386. //   _Nb may be any nonzero number of type size_t.
  387.  
  388. template<size_t _Nb>
  389. class bitset : private _Base_bitset<__BITSET_WORDS(_Nb)>
  390. {
  391. private:
  392.   typedef _Base_bitset<__BITSET_WORDS(_Nb)> _Base;
  393.   typedef unsigned long _WordT;
  394.  
  395. private:
  396.   void _M_do_sanitize() {
  397.     _Sanitize<_Nb%_GLIBCPP_BITSET_BITS_PER_WORD>::_M_do_sanitize(this->_M_hiword());
  398.   }
  399.  
  400. public:
  401.  
  402.   // bit reference:
  403.   class reference;
  404.   friend class reference;
  405.  
  406.   class reference {
  407.     friend class bitset;
  408.  
  409.     _WordT *_M_wp;
  410.     size_t _M_bpos;
  411.  
  412.     // left undefined
  413.     reference();
  414.  
  415.   public:
  416.     reference( bitset& __b, size_t __pos ) {
  417.       _M_wp = &__b._M_getword(__pos);
  418.       _M_bpos = _Base::_S_whichbit(__pos);
  419.     }
  420.  
  421.     ~reference() {}
  422.  
  423.     // for b[i] = __x;
  424.     reference& operator=(bool __x) {
  425.       if ( __x )
  426.         *_M_wp |= _Base::_S_maskbit(_M_bpos);
  427.       else
  428.         *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
  429.  
  430.       return *this;
  431.     }
  432.  
  433.     // for b[i] = b[__j];
  434.     reference& operator=(const reference& __j) {
  435.       if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) )
  436.         *_M_wp |= _Base::_S_maskbit(_M_bpos);
  437.       else
  438.         *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
  439.  
  440.       return *this;
  441.     }
  442.  
  443.     // flips the bit
  444.     bool operator~() const
  445.       { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
  446.  
  447.     // for __x = b[i];
  448.     operator bool() const
  449.       { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
  450.  
  451.     // for b[i].flip();
  452.     reference& flip() {
  453.       *_M_wp ^= _Base::_S_maskbit(_M_bpos);
  454.       return *this;
  455.     }
  456.   };
  457.  
  458.   // 23.3.5.1 constructors:
  459.   bitset() {}
  460.   bitset(unsigned long __val) : _Base_bitset<__BITSET_WORDS(_Nb)>(__val)
  461.     { _M_do_sanitize(); }
  462.  
  463.   template<class _CharT, class _Traits, class _Alloc>
  464.   explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s,
  465.                   size_t __pos = 0)
  466.     : _Base()
  467.   {
  468.     if (__pos > __s.size())
  469.       __STL_THROW(out_of_range("bitset"));
  470.     _M_copy_from_string(__s, __pos,
  471.                         basic_string<_CharT, _Traits, _Alloc>::npos);
  472.   }
  473.   template<class _CharT, class _Traits, class _Alloc>
  474.   bitset(const basic_string<_CharT, _Traits, _Alloc>& __s,
  475.          size_t __pos,
  476.          size_t __n)
  477.     : _Base()
  478.   {
  479.     if (__pos > __s.size())
  480.       __STL_THROW(out_of_range("bitset"));
  481.     _M_copy_from_string(__s, __pos, __n);
  482.   }
  483.  
  484.   // 23.3.5.2 bitset operations:
  485.   bitset<_Nb>& operator&=(const bitset<_Nb>& __rhs) {
  486.     this->_M_do_and(__rhs);
  487.     return *this;
  488.   }
  489.  
  490.   bitset<_Nb>& operator|=(const bitset<_Nb>& __rhs) {
  491.     this->_M_do_or(__rhs);
  492.     return *this;
  493.   }
  494.  
  495.   bitset<_Nb>& operator^=(const bitset<_Nb>& __rhs) {
  496.     this->_M_do_xor(__rhs);
  497.     return *this;
  498.   }
  499.  
  500.   bitset<_Nb>& operator<<=(size_t __pos) {
  501.     this->_M_do_left_shift(__pos);
  502.     this->_M_do_sanitize();
  503.     return *this;
  504.   }
  505.  
  506.   bitset<_Nb>& operator>>=(size_t __pos) {
  507.     this->_M_do_right_shift(__pos);
  508.     this->_M_do_sanitize();
  509.     return *this;
  510.   }
  511.  
  512.   //
  513.   // Extension:
  514.   // Versions of single-bit set, reset, flip, test with no range checking.
  515.   //
  516.  
  517.   bitset<_Nb>& _Unchecked_set(size_t __pos) {
  518.     this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
  519.     return *this;
  520.   }
  521.  
  522.   bitset<_Nb>& _Unchecked_set(size_t __pos, int __val) {
  523.     if (__val)
  524.       this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
  525.     else
  526.       this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
  527.  
  528.     return *this;
  529.   }
  530.  
  531.   bitset<_Nb>& _Unchecked_reset(size_t __pos) {
  532.     this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
  533.     return *this;
  534.   }
  535.  
  536.   bitset<_Nb>& _Unchecked_flip(size_t __pos) {
  537.     this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
  538.     return *this;
  539.   }
  540.  
  541.   bool _Unchecked_test(size_t __pos) const {
  542.     return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
  543.       != static_cast<_WordT>(0);
  544.   }
  545.  
  546.   // Set, reset, and flip.
  547.  
  548.   bitset<_Nb>& set() {
  549.     this->_M_do_set();
  550.     this->_M_do_sanitize();
  551.     return *this;
  552.   }
  553.  
  554.   bitset<_Nb>& set(size_t __pos, bool __val = true) {
  555.     if (__pos >= _Nb)
  556.       __STL_THROW(out_of_range("bitset"));
  557.  
  558.     return _Unchecked_set(__pos, __val);
  559.   }
  560.  
  561.   bitset<_Nb>& reset() {
  562.     this->_M_do_reset();
  563.     return *this;
  564.   }
  565.  
  566.   bitset<_Nb>& reset(size_t __pos) {
  567.     if (__pos >= _Nb)
  568.       __STL_THROW(out_of_range("bitset"));
  569.  
  570.     return _Unchecked_reset(__pos);
  571.   }
  572.  
  573.   bitset<_Nb>& flip() {
  574.     this->_M_do_flip();
  575.     this->_M_do_sanitize();
  576.     return *this;
  577.   }
  578.  
  579.   bitset<_Nb>& flip(size_t __pos) {
  580.     if (__pos >= _Nb)
  581.       __STL_THROW(out_of_range("bitset"));
  582.  
  583.     return _Unchecked_flip(__pos);
  584.   }
  585.  
  586.   bitset<_Nb> operator~() const {
  587.     return bitset<_Nb>(*this).flip();
  588.   }
  589.  
  590.   // element access:
  591.   //for b[i];
  592.   reference operator[](size_t __pos) { return reference(*this,__pos); }
  593.   bool operator[](size_t __pos) const { return _Unchecked_test(__pos); }
  594.  
  595.   unsigned long to_ulong() const { return this->_M_do_to_ulong(); }
  596.  
  597.   template <class _CharT, class _Traits, class _Alloc>
  598.   basic_string<_CharT, _Traits, _Alloc> to_string() const {
  599.     basic_string<_CharT, _Traits, _Alloc> __result;
  600.     _M_copy_to_string(__result);
  601.     return __result;
  602.   }
  603.  
  604.   // Helper functions for string operations.
  605.   template<class _CharT, class _Traits, class _Alloc>
  606.   void _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s,
  607.                           size_t,
  608.                           size_t);
  609.  
  610.   template<class _CharT, class _Traits, class _Alloc>
  611.   void _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const;
  612.  
  613.   size_t count() const { return this->_M_do_count(); }
  614.  
  615.   size_t size() const { return _Nb; }
  616.  
  617.   bool operator==(const bitset<_Nb>& __rhs) const {
  618.     return this->_M_is_equal(__rhs);
  619.   }
  620.   bool operator!=(const bitset<_Nb>& __rhs) const {
  621.     return !this->_M_is_equal(__rhs);
  622.   }
  623.  
  624.   bool test(size_t __pos) const {
  625.     if (__pos >= _Nb)
  626.       __STL_THROW(out_of_range("bitset"));
  627.  
  628.     return _Unchecked_test(__pos);
  629.   }
  630.  
  631.   bool any() const { return this->_M_is_any(); }
  632.   bool none() const { return !this->_M_is_any(); }
  633.  
  634.   bitset<_Nb> operator<<(size_t __pos) const
  635.     { return bitset<_Nb>(*this) <<= __pos; }
  636.   bitset<_Nb> operator>>(size_t __pos) const
  637.     { return bitset<_Nb>(*this) >>= __pos; }
  638.  
  639.   //
  640.   // EXTENSIONS: bit-find operations.  These operations are
  641.   // experimental, and are subject to change or removal in future
  642.   // versions.
  643.   //
  644.  
  645.   // find the index of the first "on" bit
  646.   size_t _Find_first() const
  647.     { return this->_M_do_find_first(_Nb); }
  648.  
  649.   // find the index of the next "on" bit after prev
  650.   size_t _Find_next( size_t __prev ) const
  651.     { return this->_M_do_find_next(__prev, _Nb); }
  652.  
  653. };
  654.  
  655. //
  656. // Definitions of non-inline member functions.
  657. //
  658.  
  659. template <size_t _Nb>
  660. template<class _CharT, class _Traits, class _Alloc>
  661. void bitset<_Nb>
  662.   ::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s,
  663.                         size_t __pos,
  664.                         size_t __n)
  665. {
  666.   reset();
  667.   const size_t __nbits = min(_Nb, min(__n, __s.size() - __pos));
  668.   for (size_t __i = 0; __i < __nbits; ++__i) {
  669.     switch(__s[__pos + __nbits - __i - 1]) {
  670.     case '0':
  671.       break;
  672.     case '1':
  673.       set(__i);
  674.       break;
  675.     default:
  676.       __STL_THROW(invalid_argument("bitset"));
  677.     }
  678.   }
  679. }
  680.  
  681. template <size_t _Nb>
  682. template <class _CharT, class _Traits, class _Alloc>
  683. void bitset<_Nb>
  684.   ::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const
  685. {
  686.   __s.assign(_Nb, '0');
  687.  
  688.   for (size_t __i = 0; __i < _Nb; ++__i)
  689.     if (_Unchecked_test(__i))
  690.       __s[_Nb - 1 - __i] = '1';
  691. }
  692.  
  693. // ------------------------------------------------------------
  694.  
  695. //
  696. // 23.3.5.3 bitset operations:
  697. //
  698.  
  699. template <size_t _Nb>
  700. inline bitset<_Nb> operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) {
  701.   bitset<_Nb> __result(__x);
  702.   __result &= __y;
  703.   return __result;
  704. }
  705.  
  706.  
  707. template <size_t _Nb>
  708. inline bitset<_Nb> operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) {
  709.   bitset<_Nb> __result(__x);
  710.   __result |= __y;
  711.   return __result;
  712. }
  713.  
  714. template <size_t _Nb>
  715. inline bitset<_Nb> operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) {
  716.   bitset<_Nb> __result(__x);
  717.   __result ^= __y;
  718.   return __result;
  719. }
  720.  
  721. template <class _CharT, class _Traits, size_t _Nb>
  722. basic_istream<_CharT, _Traits>&
  723. operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
  724. {
  725.   typedef typename _Traits::char_type char_type;
  726.   basic_string<_CharT, _Traits> __tmp;
  727.   __tmp.reserve(_Nb);
  728.  
  729.   // Skip whitespace
  730.   typename basic_istream<_CharT, _Traits>::sentry __sentry(__is);
  731.   if (__sentry) {
  732.     basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf();
  733.     for (size_t __i = 0; __i < _Nb; ++__i) {
  734.       static typename _Traits::int_type __eof = _Traits::eof();
  735.  
  736.       typename _Traits::int_type __c1 = __buf->sbumpc();
  737.       if (_Traits::eq_int_type(__c1, __eof)) {
  738.         __is.setstate(ios_base::eofbit);
  739.         break;
  740.       }
  741.       else {
  742.         char_type __c2 = _Traits::to_char_type(__c1);
  743.         char_type __c  = __is.narrow(__c2, '*');
  744.  
  745.         if (__c == '0' || __c == '1')
  746.           __tmp.push_back(__c);
  747.         else if (_Traits::eq_int_type(__buf->sputbackc(__c2), __eof)) {
  748.           __is.setstate(ios_base::failbit);
  749.           break;
  750.         }
  751.       }
  752.     }
  753.  
  754.     if (__tmp.empty())
  755.       __is.setstate(ios_base::failbit);
  756.     else
  757.       __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb);
  758.   }
  759.  
  760.   return __is;
  761. }
  762.  
  763. template <class _CharT, class _Traits, size_t _Nb>
  764. basic_ostream<_CharT, _Traits>&
  765. operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x)
  766. {
  767.   basic_string<_CharT, _Traits> __tmp;
  768.   __x._M_copy_to_string(__tmp);
  769.   return __os << __tmp;
  770. }
  771.  
  772. } // namespace std
  773.  
  774. #undef __BITSET_WORDS
  775.  
  776. #endif /* __SGI_STL_BITSET */
  777.  
  778.  
  779. // Local Variables:
  780. // mode:C++
  781. // End:
  782.  
  783.