// bitset standard header
#ifndef _BITSET_
#define _BITSET_

#pragma info(none)
#ifndef __CHKHDR__
#  pragma report(level, E)
#endif
#pragma info(restore)

#if __IBMCPP__ < 400
#error This file to be used only with IBM VisualAge C++ v4 and later compilers.
#endif /* __IBMCPP__ */

#pragma namemangling(ansi)

   /********************************************************************/
   /*  <bitset> header file                                            */
   /*                                                                  */
   /*  VisualAge C++, Version 4.0                                      */
   /*    Licensed Material - Property of IBM                           */
   /*                                                                  */
   /*  5801-AAR and Other Materials                                    */
   /*                                                                  */
   /*  (c) Copyright IBM Corp 1991, 1998. All rights reserved.         */
   /*                                                                  */
   /*                                                                  */
   /*  Licensed Materials.                                             */
   /*                                                                  */
   /*  Dinkum C++ Library                                              */
   /*  Copyright (c) 1998.  Licensed to IBM Corp. and its suppliers.   */
   /*                                                                  */
   /********************************************************************/

#include <string>
		// TEMPLATE CLASS bitset
_STD_BEGIN
template<size_t _N> class bitset {
	typedef unsigned long _Ty;
public:
	typedef bool element_type;
	class reference {
		friend class bitset<_N>;
	public:
		reference& operator=(bool _X)
			{_Pbs->set(_Off, _X);
			return (*this); }
		reference& operator=(const reference& _Bs)
			{_Pbs->set(_Off, bool(_Bs));
			return (*this); }
		reference& flip()
			{_Pbs->flip(_Off);
			return (*this); }
		bool operator~() const
			{return (!_Pbs->test(_Off)); }
		operator bool() const
			{return (_Pbs->test(_Off)); }
	private:
		reference(bitset<_N>& _X, size_t _P)
			: _Pbs(&_X), _Off(_P) {}
		bitset<_N> *_Pbs;
		size_t _Off;
		};
	static const size_t bitset_size;
	bool at(size_t _P) const
		{if (_N <= _P)
			_Xran();
		return (test(_P)); }
	reference at(size_t _P)
		{if (_N <= _P)
			_Xran();
		return (reference(*this, _P)); }
	bool operator[](size_t _P) const
		{return (test(_P)); }
	reference operator[](size_t _P)
		{return (reference(*this, _P)); }
	bitset()
		{_Tidy(); }
	bitset(unsigned long _X)
		{_Tidy();
		for (size_t _P = 0; _X != 0 && _P < _N; _X >>= 1, ++_P)
			if (_X & 1)
				set(_P); }
	template<class _E, class _Tr, class _A>
		explicit bitset(const basic_string<_E, _Tr, _A>& _S,
		typename basic_string<_E, _Tr, _A>::size_type _P = 0,
		typename basic_string<_E, _Tr, _A>::size_type _L =
			basic_string<_E, _Tr, _A>::npos)
		{typename basic_string<_E, _Tr, _A>::size_type _I;
		if (_S.size() < _P)
			_Xran();
		if (_S.size() - _P < _L)
			_L = _S.size() - _P;
		if (_N < _L)
			_L = _N;
		_Tidy(), _P += _L;
		for (_I = 0; _I < _L; ++_I)
			if (_S[--_P] == '1')
				set(_I);
			else if (_S[_P] != '0')
				_Xinv(); }
	bitset<_N>& operator&=(const bitset<_N>& _R)
		{for (int _I = _Nw; 0 <= _I; --_I)
			_A[_I] &= _R._W(_I);
		return (*this); }
	bitset<_N>& operator|=(const bitset<_N>& _R)
		{for (int _I = _Nw; 0 <= _I; --_I)
			_A[_I] |= _R._W(_I);
		return (*this); }
	bitset<_N>& operator^=(const bitset<_N>& _R)
		{for (int _I = _Nw; 0 <= _I; --_I)
			_A[_I] ^= _R._W(_I);
		return (*this); }
	bitset<_N>& operator<<=(size_t _P)
		{const int _D = _P / _Nb;
		if (_D != 0)
			for (int _I = _Nw; 0 <= _I; --_I)
				_A[_I] = _D <= _I ? _A[_I - _D] : 0;
		if ((_P %= _Nb) != 0)
			{for (int _I = _Nw; 0 < _I; --_I)
				_A[_I] = (_A[_I] << _P)
					| (_A[_I - 1] >> (_Nb - _P));
			_A[0] <<= _P, _Trim(); }
		return (*this); }
	bitset<_N>& operator>>=(size_t _P)
		{const int _D = _P / _Nb;
		if (_D != 0)
			for (int _I = 0; _I <= _Nw; ++_I)
				_A[_I] = _D <= _Nw - _I ? _A[_I + _D] : 0;
		if ((_P %= _Nb) != 0)
			{for (int _I = 0; _I < _Nw; ++_I)
				_A[_I] = (_A[_I] >> _P)
					| (_A[_I + 1] << (_Nb - _P));
			_A[_Nw] >>= _P; }
		return (*this); }
	bitset<_N>& set()
		{_Tidy(~(_Ty)0);
		return (*this); }
	bitset<_N>& set(size_t _P, bool _X = true)
		{if (_N <= _P)
			_Xran();
		if (_X)
			_A[_P / _Nb] |= (_Ty)1 << _P % _Nb;
		else
			_A[_P / _Nb] &= ~((_Ty)1 << _P % _Nb);
		return (*this); }
	bitset<_N>& reset()
		{_Tidy();
		return (*this); }
	bitset<_N>& reset(size_t _P)
		{return (set(_P, 0)); }
	bitset<_N> operator~() const
		{return (bitset<_N>(*this).flip()); }
	bitset<_N>& flip()
		{for (int _I = _Nw; 0 <= _I; --_I)
			_A[_I] = ~_A[_I];
		_Trim();
		return (*this); }
	bitset<_N>& flip(size_t _P)
		{if (_N <= _P)
			_Xran();
		_A[_P / _Nb] ^= (_Ty)1 << _P % _Nb;
		return (*this); }
	unsigned long to_ulong() const
		{enum {_Assertion = 1 /
			(sizeof (unsigned long) % sizeof (_Ty) == 0)};
		int _I = _Nw;
		for (; sizeof (unsigned long) / sizeof (_Ty) <= _I; --_I)
			if (_A[_I] != 0)
				_Xoflo();
		unsigned long _V = _A[_I];
		for (; 0 <= --_I; )
			_V = _V << _Nb | _A[_I];
		return (_V); }
	template<class _E, class _Tr, class _A>
		basic_string<_E, _Tr, _A> to_string() const
		{basic_string<_E, _Tr, _A> _S;
		typename basic_string<_E, _Tr, _A>::size_type _P;
		_S.reserve(_N);
		for (_P = _N; 0 < _P; )
			_S += test(--_P) ? '1' : '0';
		return (_S); }
	size_t count() const
		{size_t _V = 0;
		for (int _I = _Nw; 0 <= _I; --_I)
			for (_Ty _X = _A[_I]; _X != 0; _X >>= 4)
				_V += "\0\1\1\2\1\2\2\3"
					"\1\2\2\3\2\3\3\4"[_X & 0xF];
		return (_V); }
	size_t size() const
		{return (_N); }
	bool operator==(const bitset<_N>& _R) const
		{for (int _I = _Nw; 0 <= _I; --_I)
			if (_A[_I] != _R._W(_I))
				return (false);
		return (true); }
	bool operator!=(const bitset<_N>& _R) const
		{return (!(*this == _R)); }
	bool test(size_t _P) const
		{if (_N <= _P)
			_Xran();
		return ((_A[_P / _Nb] & ((_Ty)1 << _P % _Nb)) != 0); }
	bool any() const
		{for (int _I = _Nw; 0 <= _I; --_I)
			if (_A[_I] != 0)
				return (true);
		return (false); }
	bool none() const
		{return (!any()); }
	bitset<_N> operator<<(size_t _R) const
		{return (bitset<_N>(*this) <<= _R); }
	bitset<_N> operator>>(size_t _R) const
		{return (bitset<_N>(*this) >>= _R); }
	friend bitset<_N> operator&(const bitset<_N>& _L,
		const bitset<_N>& _R)
		{return (bitset<_N>(_L) &= _R); }
	friend bitset<_N> operator|(const bitset<_N>& _L,
		const bitset<_N>& _R)
		{return (bitset<_N>(_L) |= _R); }
	friend bitset<_N> operator^(const bitset<_N>& _L,
		const bitset<_N>& _R)
		{return (bitset<_N>(_L) ^= _R); }
	_Ty _W(size_t _I) const
		{return (_A[_I]); }
private:
	enum {_Nb = CHAR_BIT * sizeof (_Ty),
		_Nw = _N == 0 ? 0 : (_N - 1) / _Nb};
	void _Tidy(_Ty _X = 0)
		{for (int _I = _Nw; 0 <= _I; --_I)
			_A[_I] = _X;
		if (_X != 0)
			_Trim(); }
	void _Trim()
		{if (_N % _Nb != 0)
			_A[_Nw] &= ((_Ty)1 << _N % _Nb) - 1; }
	void _Xinv() const
		{_THROW(invalid_argument, ""); }
	void _Xoflo() const
		{_THROW(overflow_error, ""); }
	void _Xran() const
		{_THROW(out_of_range, ""); }
	_Ty _A[_Nw + 1];
	};
template<size_t _N>
	const size_t bitset<_N>::bitset_size = _N;
		// TEMPLATE operator<<
template<class _E, class _Tr, size_t _N> inline
	basic_ostream<_E, _Tr>& operator<<(
		basic_ostream<_E, _Tr>& _O, const bitset<_N>& _R)
	{return (_O
		<< _R.template to_string<_E, _Tr, allocator<_E> >()); }
		// TEMPLATE operator>>
template<class _E, class _Tr, size_t _N> inline
	basic_istream<_E, _Tr>& operator>>(
		basic_istream<_E, _Tr>& _I, bitset<_N>& _R)
	{ios_base::iostate _St = ios_base::goodbit;
	bool _Chg = false;
	string _X;
	const typename basic_istream<_E, _Tr>::sentry _Ok(_I);
	if (_Ok)
		{_TRY_IO_BEGIN
		typename _Tr::int_type _C = _I.rdbuf()->sgetc();
		for (size_t _M = _R.size(); 0 < _M;
			_C = _I.rdbuf()->snextc(), --_M)
			{char _Ch;
			if (_Tr::eq_int_type(_Tr::eof(), _C))
				{_St |= ios_base::eofbit;
				break; }
			else if ((_Ch = _NARROW(_E, _Tr::to_char_type(_C)))
				!= '0' && _Ch != '1')
				break;
			else if (_X.max_size() <= _X.size())
				{_St |= ios_base::failbit;
				break; }
			else
				_X.append(1, _Ch), _Chg = true; }
		_CATCH_IO_(_I); }
	if (!_Chg)
		_St |= ios_base::failbit;
	_I.setstate(_St);
	_R = bitset<_N>(_X);
	return (_I); }
_STD_END

#pragma namemangling()

#pragma info(none)
#ifndef __CHKHDR__
#  pragma report(pop)
#endif
#pragma info(restore)

#endif /* _BITSET */

/*
 * Copyright (c) 1994-1998 by P.J. Plauger.  ALL RIGHTS RESERVED. 
 * Consult your license regarding permissions and restrictions.
V2.2:0081 */
