/*
 * Copyright (c) 1998
 * Silicon Graphics Computer Systems, Inc.
 *
 * Copyright (c) 1999 
 * Boris Fomitchev
 *
 * This material is provided "as is", with absolutely no warranty expressed
 * or implied. Any use is at your own risk.
 *
 * Permission to use or copy this software for any purpose is hereby granted 
 * without fee, provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 *
 */

#ifndef __STL_BITSET_C
# define  __STL_BITSET_C

#define __BITS_PER_WORDT(__wt) (CHAR_BIT*sizeof(__wt))
#define __BITSET_WORDS(__n,__wt) \
 ((__n) < 1 ? 1 : ((__n) + __BITS_PER_WORDT(__wt) - 1)/__BITS_PER_WORDT(__wt))

# if ! defined (__STL_DEFAULT_TYPE_PARAM)
#  define bitset __bitset
# endif

#if defined(__IBMCPP__)
// supress EDC3130: A constant is being used as a conditional expression
#pragma info(nocnd) 
#endif

__STL_BEGIN_NAMESPACE

//
// Definitions of non-inline functions from _Base_bitset.
// 

template<size_t _Nw, class _WordT>
_Base_bitset<_Nw, _WordT>::_Base_bitset(unsigned long __val)
{
  _M_do_reset();
  const size_t __n = min(sizeof(unsigned long)*CHAR_BIT,
                         __BITS_PER_WORDT(_WordT)*_Nw);
  for(size_t __i = 0; __i < __n; ++__i, __val >>= 1)
    if ( __val & 0x1 )
      _M_getword(__i) |= _S_maskbit(__i);
}

template<size_t _Nw, class _WordT>
void _Base_bitset<_Nw, _WordT>::_M_do_left_shift(size_t __shift) 
{
  if (__shift != 0) {
    const size_t __wshift = __shift / __BITS_PER_WORDT(_WordT);
    const size_t __offset = __shift % __BITS_PER_WORDT(_WordT);
    const size_t __sub_offset = __BITS_PER_WORDT(_WordT) - __offset;
    size_t __n = _Nw - 1;
    for ( ; __n > __wshift; --__n)
      _M_w[__n] = (_M_w[__n - __wshift] << __offset) | 
                (_M_w[__n - __wshift - 1] >> __sub_offset);
    if (__n == __wshift)
      _M_w[__n] = _M_w[0] << __offset;
    for (size_t __n1 = 0; __n1 < __n; ++__n1)
      _M_w[__n1] = __STATIC_CAST(_WordT,0);
  }
}

template<size_t _Nw, class _WordT>
void _Base_bitset<_Nw, _WordT>::_M_do_right_shift(size_t __shift) 
{
  if (__shift != 0) {
    const size_t __wshift = __shift / __BITS_PER_WORDT(_WordT);
    const size_t __offset = __shift % __BITS_PER_WORDT(_WordT);
    const size_t __sub_offset = __BITS_PER_WORDT(_WordT) - __offset;
    const size_t __limit = _Nw - __wshift - 1;
    size_t __n = 0;
    for ( ; __n < __limit; ++__n)
      _M_w[__n] = (_M_w[__n + __wshift] >> __offset) | 
                  (_M_w[__n + __wshift + 1] << __sub_offset);
    _M_w[__limit] = _M_w[_Nw-1] >> __offset;
    for (size_t __n1 = __limit + 1; __n1 < _Nw; ++__n1)
      _M_w[__n1] = __STATIC_CAST(_WordT,0);
  }
}

template<size_t _Nw, class _WordT>
unsigned long _Base_bitset<_Nw, _WordT>::_M_do_to_ulong() const
{
  if (sizeof(_WordT) >= sizeof(unsigned long)) {
    for (size_t __i = 1; __i < _Nw; ++__i) 
      if (_M_w[__i]) 
        __STL_THROW(overflow_error("bitset"));

    const _WordT __mask = __STATIC_CAST(_WordT,__STATIC_CAST(unsigned long,-1));
    if (_M_w[0] & ~__mask) 
      __STL_THROW(overflow_error("bitset"));


    return __STATIC_CAST(unsigned long,_M_w[0] & __mask);
  }
  else {                      // sizeof(_WordT) < sizeof(unsigned long).
    const size_t __nwords =
      (sizeof(unsigned long) + sizeof(_WordT) - 1) / sizeof(_WordT);

    size_t __min_nwords = __nwords;
    if (_Nw > __nwords) {
      for (size_t __i = __nwords; __i < _Nw; ++__i) 
        if (_M_w[__i]) 
	  __STL_THROW(overflow_error("bitset"));
    }
    else 
      __min_nwords = _Nw;
      
    // If unsigned long is 8 bytes and _WordT is 6 bytes, then an unsigned
    // long consists of all of one word plus 2 bytes from another word.
    const size_t __part = sizeof(unsigned long) % sizeof(_WordT);

    if (__part != 0 && __nwords <= _Nw && 
        (_M_w[__min_nwords - 1] >> ((sizeof(_WordT) - __part) * CHAR_BIT)) != 0)
      __STL_THROW(overflow_error("bitset"));

    unsigned long __result = 0;
    for (size_t __i = 0; __i < __min_nwords; ++__i) {
      __result |= __STATIC_CAST(const unsigned long,
         _M_w[__i]) << (__i * sizeof(_WordT) * CHAR_BIT);
    }
    return __result;
  }
} // End _M_do_to_ulong

template<size_t _Nw, class _WordT>
size_t _Base_bitset<_Nw, _WordT>::_M_do_find_first(size_t __not_found) const 
{
  for ( size_t __i = 0; __i < _Nw; __i++ ) {
    _WordT __thisword = _M_w[__i];
    if ( __thisword != __STATIC_CAST(_WordT,0) ) {
      // find byte within word
      for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) {
        unsigned char __this_byte
          = __STATIC_CAST(unsigned char,(__thisword & (~(unsigned char)0)));
        if ( __this_byte )
          return __i*__BITS_PER_WORDT(_WordT) + __j*CHAR_BIT +
            _First_one<true>::_S_first_one[__this_byte];

        __thisword >>= CHAR_BIT;
      }
    }
  }
  // not found, so return an indication of failure.
  return __not_found;
}

template<size_t _Nw, class _WordT>
size_t
_Base_bitset<_Nw, _WordT>::_M_do_find_next(size_t __prev, 
                                           size_t __not_found) const
{
  // make bound inclusive
  ++__prev;

  // check out of bounds
  if ( __prev >= _Nw * __BITS_PER_WORDT(_WordT) )
    return __not_found;

    // search first word
  size_t __i = _S_whichword(__prev);
  _WordT __thisword = _M_w[__i];

    // mask off bits below bound
  __thisword &= (~__STATIC_CAST(_WordT,0)) << _S_whichbit(__prev);

  if ( __thisword != __STATIC_CAST(_WordT,0) ) {
    // find byte within word
    // get first byte into place
    __thisword >>= _S_whichbyte(__prev) * CHAR_BIT;
    for ( size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++ ) {
      unsigned char __this_byte
        = __STATIC_CAST(unsigned char,(__thisword & (~(unsigned char)0)));
      if ( __this_byte )
        return __i*__BITS_PER_WORDT(_WordT) + __j*CHAR_BIT +
          _First_one<true>::_S_first_one[__this_byte];

      __thisword >>= CHAR_BIT;
    }
  }

  // check subsequent words
  __i++;
  for ( ; __i < _Nw; __i++ ) {
    _WordT __thisword = _M_w[__i];
    if ( __thisword != __STATIC_CAST(_WordT,0) ) {
      // find byte within word
      for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) {
        unsigned char __this_byte
          = __STATIC_CAST(unsigned char,(__thisword & (~(unsigned char)0)));
        if ( __this_byte )
          return __i*__BITS_PER_WORDT(_WordT) + __j*CHAR_BIT +
            _First_one<true>::_S_first_one[__this_byte];

        __thisword >>= CHAR_BIT;
      }
    }
  }

  // not found, so return an indication of failure.
  return __not_found;
} // end _M_do_find_next


// ------------------------------------------------------------
//
// Definitions of non-inline functions from the single-word version of
//  _Base_bitset.
//

# if defined (__STL_CLASS_PARTIAL_SPECIALIZATION)

template <class _WordT>
size_t _Base_bitset<1, _WordT>::_M_do_find_first(size_t __not_found) const
{
  _WordT __thisword = _M_w;

  if ( __thisword != __STATIC_CAST(_WordT,0) ) {
    // find byte within word
    for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) {
      unsigned char __this_byte
        = __STATIC_CAST(unsigned char,(__thisword & (~(unsigned char)0)));
      if ( __this_byte )
        return __j*CHAR_BIT + _First_one<true>::_S_first_one[__this_byte];

      __thisword >>= CHAR_BIT;
    }
  }
  // not found, so return a value that indicates failure.
  return __not_found;
}

template <class _WordT>
size_t 
_Base_bitset<1, _WordT>::_M_do_find_next(size_t __prev, 
                                         size_t __not_found ) const
{
  // make bound inclusive
  ++__prev;

  // check out of bounds
  if ( __prev >= __BITS_PER_WORDT(_WordT) )
    return __not_found;

    // search first (and only) word
  _WordT __thisword = _M_w;

  // mask off bits below bound
  __thisword &= (~__STATIC_CAST(_WordT,0)) << _S_whichbit(__prev);