williamr@2: /*
williamr@2:  * Copyright (c) 1998
williamr@2:  * Silicon Graphics Computer Systems, Inc.
williamr@2:  *
williamr@4:  * Copyright (c) 1999
williamr@2:  * Boris Fomitchev
williamr@2:  *
williamr@2:  * This material is provided "as is", with absolutely no warranty expressed
williamr@2:  * or implied. Any use is at your own risk.
williamr@2:  *
williamr@4:  * Permission to use or copy this software for any purpose is hereby granted
williamr@2:  * without fee, provided the above notices are retained on all copies.
williamr@2:  * Permission to modify the code and to distribute modified code is granted,
williamr@2:  * provided the above notices are retained, and a notice that the code was
williamr@2:  * modified is included with the above copyright notice.
williamr@2:  *
williamr@2:  */
williamr@2: 
williamr@2: #ifndef _STLP_BITSET_C
williamr@4: #define _STLP_BITSET_C
williamr@2: 
williamr@4: #ifndef _STLP_BITSET_H
williamr@2: #  include <stl/_bitset.h>
williamr@4: #endif
williamr@2: 
williamr@4: #define __BITS_PER_WORD (CHAR_BIT * sizeof(unsigned long))
williamr@2: 
williamr@2: _STLP_BEGIN_NAMESPACE
williamr@2: 
williamr@4: _STLP_MOVE_TO_PRIV_NAMESPACE
williamr@2: //
williamr@2: // Definitions of non-inline functions from _Base_bitset.
williamr@4: //
williamr@2: template<size_t _Nw>
williamr@4: void _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) {
williamr@2:   if (__shift != 0) {
williamr@2:     const size_t __wshift = __shift / __BITS_PER_WORD;
williamr@2:     const size_t __offset = __shift % __BITS_PER_WORD;
williamr@2: 
williamr@2:     if (__offset == 0)
williamr@2:       for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
williamr@2:         _M_w[__n] = _M_w[__n - __wshift];
williamr@2: 
williamr@2:     else {
williamr@2:       const size_t __sub_offset = __BITS_PER_WORD - __offset;
williamr@2:       for (size_t __n = _Nw - 1; __n > __wshift; --__n)
williamr@4:         _M_w[__n] = (_M_w[__n - __wshift] << __offset) |
williamr@2:                     (_M_w[__n - __wshift - 1] >> __sub_offset);
williamr@2:       _M_w[__wshift] = _M_w[0] << __offset;
williamr@2:     }
williamr@2: 
williamr@2:     fill(_M_w + 0, _M_w + __wshift, __STATIC_CAST(_WordT,0));
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: template<size_t _Nw>
williamr@4: void _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) {
williamr@2:   if (__shift != 0) {
williamr@2:     const size_t __wshift = __shift / __BITS_PER_WORD;
williamr@2:     const size_t __offset = __shift % __BITS_PER_WORD;
williamr@2:     const size_t __limit = _Nw - __wshift - 1;
williamr@2: 
williamr@2:     if (__offset == 0)
williamr@2:       for (size_t __n = 0; __n <= __limit; ++__n)
williamr@2:         _M_w[__n] = _M_w[__n + __wshift];
williamr@2: 
williamr@2:     else {
williamr@2:       const size_t __sub_offset = __BITS_PER_WORD - __offset;
williamr@2:       for (size_t __n = 0; __n < __limit; ++__n)
williamr@2:         _M_w[__n] = (_M_w[__n + __wshift] >> __offset) |
williamr@2:                     (_M_w[__n + __wshift + 1] << __sub_offset);
williamr@2:       _M_w[__limit] = _M_w[_Nw-1] >> __offset;
williamr@2:     }
williamr@2: 
williamr@2:     fill(_M_w + __limit + 1, _M_w + _Nw, __STATIC_CAST(_WordT,0));
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: template<size_t _Nw>
williamr@4: unsigned long _Base_bitset<_Nw>::_M_do_to_ulong() const {
williamr@4:   for (size_t __i = 1; __i < _Nw; ++__i)
williamr@4:     if (_M_w[__i])
williamr@2:       __stl_throw_overflow_error("bitset");
williamr@2:   return _M_w[0];
williamr@2: } // End _M_do_to_ulong
williamr@2: 
williamr@2: template<size_t _Nw>
williamr@4: size_t _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const {
williamr@2:   for ( size_t __i = 0; __i < _Nw; __i++ ) {
williamr@2:     _WordT __thisword = _M_w[__i];
williamr@2:     if ( __thisword != __STATIC_CAST(_WordT,0) ) {
williamr@2:       // find byte within word
williamr@2:       for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) {
williamr@2:         unsigned char __this_byte
williamr@2:           = __STATIC_CAST(unsigned char,(__thisword & (~(unsigned char)0)));
williamr@2:         if ( __this_byte )
williamr@2:           return __i*__BITS_PER_WORD + __j*CHAR_BIT +
williamr@4:             _Bs_G::_S_first_one(__this_byte);
williamr@2: 
williamr@2:         __thisword >>= CHAR_BIT;
williamr@2:       }
williamr@2:     }
williamr@2:   }
williamr@2:   // not found, so return an indication of failure.
williamr@2:   return __not_found;
williamr@2: }
williamr@2: 
williamr@2: template<size_t _Nw>
williamr@2: size_t
williamr@4: _Base_bitset<_Nw>::_M_do_find_next(size_t __prev,
williamr@4:                                    size_t __not_found) const {
williamr@2:   // make bound inclusive
williamr@2:   ++__prev;
williamr@2: 
williamr@2:   // check out of bounds
williamr@2:   if ( __prev >= _Nw * __BITS_PER_WORD )
williamr@2:     return __not_found;
williamr@2: 
williamr@2:     // search first word
williamr@2:   size_t __i = _S_whichword(__prev);
williamr@2:   _WordT __thisword = _M_w[__i];
williamr@2: 
williamr@2:     // mask off bits below bound
williamr@2:   __thisword &= (~__STATIC_CAST(_WordT,0)) << _S_whichbit(__prev);
williamr@2: 
williamr@2:   if ( __thisword != __STATIC_CAST(_WordT,0) ) {
williamr@2:     // find byte within word
williamr@2:     // get first byte into place
williamr@2:     __thisword >>= _S_whichbyte(__prev) * CHAR_BIT;
williamr@4:     for ( size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); ++__j ) {
williamr@2:       unsigned char __this_byte
williamr@2:         = __STATIC_CAST(unsigned char,(__thisword & (~(unsigned char)0)));
williamr@2:       if ( __this_byte )
williamr@2:         return __i*__BITS_PER_WORD + __j*CHAR_BIT +
williamr@4:           _Bs_G::_S_first_one(__this_byte);
williamr@2: 
williamr@2:       __thisword >>= CHAR_BIT;
williamr@2:     }
williamr@2:   }
williamr@2: 
williamr@2:   // check subsequent words
williamr@4:   ++__i;
williamr@4:   for ( ; __i < _Nw; ++__i ) {
williamr@2:     /* _WordT */ __thisword = _M_w[__i];
williamr@2:     if ( __thisword != __STATIC_CAST(_WordT,0) ) {
williamr@2:       // find byte within word
williamr@4:       for ( size_t __j = 0; __j < sizeof(_WordT); ++__j ) {
williamr@2:         unsigned char __this_byte
williamr@2:           = __STATIC_CAST(unsigned char,(__thisword & (~(unsigned char)0)));
williamr@2:         if ( __this_byte )
williamr@2:           return __i*__BITS_PER_WORD + __j*CHAR_BIT +
williamr@4:             _Bs_G::_S_first_one(__this_byte);
williamr@2: 
williamr@2:         __thisword >>= CHAR_BIT;
williamr@2:       }
williamr@2:     }
williamr@2:   }
williamr@2: 
williamr@2:   // not found, so return an indication of failure.
williamr@2:   return __not_found;
williamr@2: } // end _M_do_find_next
williamr@2: 
williamr@4: _STLP_MOVE_TO_STD_NAMESPACE
williamr@2: 
williamr@4: #if !defined (_STLP_NON_TYPE_TMPL_PARAM_BUG)
williamr@2: 
williamr@4: #  if !defined (_STLP_USE_NO_IOSTREAMS)
williamr@2: 
williamr@4: _STLP_END_NAMESPACE
williamr@4: 
williamr@4: #ifndef _STLP_STRING_IO_H
williamr@4: #  include <stl/_string_io.h> //includes _istream.h and _ostream.h
williamr@4: #endif
williamr@4: 
williamr@4: _STLP_BEGIN_NAMESPACE
williamr@2: 
williamr@2: template <class _CharT, class _Traits, size_t _Nb>
williamr@2: basic_istream<_CharT, _Traits>& _STLP_CALL
williamr@4: operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) {
williamr@2:   basic_string<_CharT, _Traits> __tmp;
williamr@2:   __tmp.reserve(_Nb);
williamr@2: 
williamr@2:   // Skip whitespace
williamr@2:   typename basic_istream<_CharT, _Traits>::sentry __sentry(__is);
williamr@2:   if (__sentry) {
williamr@2:     basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf();
williamr@2:     for (size_t __i = 0; __i < _Nb; ++__i) {
williamr@2:       static typename _Traits::int_type __eof = _Traits::eof();
williamr@2: 
williamr@2:       typename _Traits::int_type __c1 = __buf->sbumpc();
williamr@2:       if (_Traits::eq_int_type(__c1, __eof)) {
williamr@2:         __is.setstate(ios_base::eofbit);
williamr@2:         break;
williamr@2:       }
williamr@2:       else {
williamr@4:         typename _Traits::char_type __c2 = _Traits::to_char_type(__c1);
williamr@4:         char __c = __is.narrow(__c2, '*');
williamr@2: 
williamr@2:         if (__c == '0' || __c == '1')
williamr@2:           __tmp.push_back(__c);
williamr@2:         else if (_Traits::eq_int_type(__buf->sputbackc(__c2), __eof)) {
williamr@2:           __is.setstate(ios_base::failbit);
williamr@2:           break;
williamr@2:         }
williamr@2:       }
williamr@2:     }
williamr@2: 
williamr@2:     if (__tmp.empty())
williamr@2:       __is.setstate(ios_base::failbit);
williamr@2:     else
williamr@2:       __x._M_copy_from_string(__tmp, __STATIC_CAST(size_t,0), _Nb);
williamr@2:   }
williamr@2: 
williamr@2:   return __is;
williamr@2: }
williamr@2: 
williamr@2: template <class _CharT, class _Traits, size_t _Nb>
williamr@2: basic_ostream<_CharT, _Traits>& _STLP_CALL
williamr@2: operator<<(basic_ostream<_CharT, _Traits>& __os,
williamr@4:            const bitset<_Nb>& __x) {
williamr@2:   basic_string<_CharT, _Traits> __tmp;
williamr@2:   __x._M_copy_to_string(__tmp);
williamr@2:   return __os << __tmp;
williamr@2: }
williamr@2: 
williamr@4: #  endif /* !_STLP_USE_NO_IOSTREAMS */
williamr@2: 
williamr@4: #endif /* _STLP_NON_TYPE_TMPL_PARAM_BUG */
williamr@2: 
williamr@2: _STLP_END_NAMESPACE
williamr@2: 
williamr@4: #undef __BITS_PER_WORD
williamr@4: #undef bitset
williamr@2: 
williamr@2: #endif /*  _STLP_BITSET_C */