/* Portions Copyright 2003, QNX Software Systems Ltd. All Rights Reserved */

// bitset standard header
#ifndef _BITSET_
#define _BITSET_
#include <string>
_STD_BEGIN

		// TEMPLATE CLASS bitset
template<size_t _Bits>
	class bitset
	{	// store fixed-length sequence of Boolean elements
	typedef unsigned short _Ty;	// base type for a storage word

public:
	typedef bool element_type;	// retained

		// CLASS reference
	class reference
		{	// proxy for an element
		friend class bitset<_Bits>;

	public:
		reference& operator=(bool _Val)
			{	// assign Boolean to element
			_Pbitset->set(_Mypos, _Val);
			return (*this);
			}

		reference& operator=(const reference& _Bitref)
			{	// assign reference to element
			_Pbitset->set(_Mypos, bool(_Bitref));
			return (*this);
			}

		reference& flip()
			{	// complement stored element
			_Pbitset->flip(_Mypos);
			return (*this);
			}

		bool operator~() const
			{	// return complemented element
			return (!_Pbitset->test(_Mypos));
			}

		operator bool() const
			{	// return element
			return (_Pbitset->test(_Mypos));
			}

	private:
		reference(bitset<_Bits>& _Bitset, size_t _Pos)
			: _Pbitset(&_Bitset), _Mypos(_Pos)
			{	// construct from bitset reference and position
			}

		bitset<_Bits> *_Pbitset;	// pointer to the bitset
		size_t _Mypos;	// position of element in bitset
		};

	bool at(size_t _Pos) const	// retained
		{	// subscript nonmutable sequence with checking
		if (_Bits <= _Pos)
			_Xran();
		return (test(_Pos));
		}

	reference at(size_t _Pos)	// retained
		{	// subscript mutable sequence with checking
		if (_Bits <= _Pos)
			_Xran();
		return (reference(*this, _Pos));
		}

	bool operator[](size_t _Pos) const
		{	// subscript nonmutable sequence
		return (test(_Pos));
		}

	reference operator[](size_t _Pos)
		{	// subscript mutable sequence
		return (reference(*this, _Pos));
		}

	bitset()
		{	// construct with all false values
		_Tidy();
		}

	bitset(unsigned long _Val)
		{	// construct from bits in unsigned long
		_Tidy();
		for (size_t _Pos = 0; _Val != 0 && _Pos < _Bits; _Val >>= 1, ++_Pos)
			if (_Val & 1)
				set(_Pos);
		}

	explicit bitset(const string& _Str,
		size_t _Pos = 0,
		size_t _Count = (size_t)(-1))
		{	// construct from elements in string
		size_t _Num;
		if (_Str.size() < _Pos)
			_Xran();	// _Pos off end
		if (_Str.size() - _Pos < _Count)
			_Count = _Str.size() - _Pos;	// trim _Count to size
		if (_Bits < _Count)
			_Count = _Bits;	// trim _Count to length of bitset
		_Tidy();

		for (_Pos += _Count, _Num = 0; _Num < _Count; ++_Num)
			if (_Str[--_Pos] == '1')
				set(_Num);
			else if (_Str[_Pos] != '0')
				_Xinv();
		}

	bitset<_Bits>& operator&=(const bitset<_Bits>& _Right)
		{	// AND in _Right
		for (int _Wpos = _Words; 0 <= _Wpos; --_Wpos)
			_Array[_Wpos] &= _Right._Getword(_Wpos);
		return (*this);
		}

	bitset<_Bits>& operator|=(const bitset<_Bits>& _Right)
		{	// OR in _Right
		for (int _Wpos = _Words; 0 <= _Wpos; --_Wpos)
			_Array[_Wpos] |= _Right._Getword(_Wpos);
		return (*this);
		}

	bitset<_Bits>& operator^=(const bitset<_Bits>& _Right)
		{	// XOR in _Right
		for (int _Wpos = _Words; 0 <= _Wpos; --_Wpos)
			_Array[_Wpos] ^= _Right._Getword(_Wpos);
		return (*this);
		}

	bitset<_Bits>& operator<<=(size_t _Pos)
		{	// shift left by _Pos
		const int _Wordshift = _Pos / _Bitsperword;
		if (_Wordshift != 0)
			for (int _Wpos = _Words; 0 <= _Wpos; --_Wpos)	// shift by words
				_Array[_Wpos] = _Wordshift <= _Wpos
					? _Array[_Wpos - _Wordshift] : (_Ty)0;

		if ((_Pos %= _Bitsperword) != 0)
			{	// 0 < _Pos < _Bitsperword, shift by bits
			for (int _Wpos = _Words; 0 < _Wpos; --_Wpos)
				_Array[_Wpos] = (_Ty)((_Array[_Wpos] << _Pos)
					| (_Array[_Wpos - 1] >> (_Bitsperword - _Pos)));
			_Array[0] <<= _Pos;
			_Trim();
			}
		return (*this);
		}

	bitset<_Bits>& operator>>=(size_t _Pos)
		{	// shift right by _Pos
		const int _Wordshift = _Pos / _Bitsperword;
		if (_Wordshift != 0)
			for (int _Wpos = 0; _Wpos <= _Words; ++_Wpos)	// shift by words
				_Array[_Wpos] = _Wordshift <= _Words - _Wpos
						? _Array[_Wpos + _Wordshift] : (_Ty)0;

		if ((_Pos %= _Bitsperword) != 0)
			{	// 0 < _Pos < _Bitsperword, shift by bits
			for (int _Wpos = 0; _Wpos < _Words; ++_Wpos)
				_Array[_Wpos] = (_Ty)((_Array[_Wpos] >> _Pos)
					| (_Array[_Wpos + 1] << (_Bitsperword - _Pos)));
			_Array[_Words] >>= _Pos;
			}
		return (*this);
		}

	bitset<_Bits>& set()
		{	// set all bits true
		_Tidy((_Ty)~0);
		return (*this);
		}

	bitset<_Bits>& set(size_t _Pos,
		bool _Val = true)
		{	// set bit at _Pos to _Val
		if (_Bits <= _Pos)
			_Xran();	// _Pos off end
		if (_Val)
			_Array[_Pos / _Bitsperword] |= (_Ty)1 << _Pos % _Bitsperword;
		else
			_Array[_Pos / _Bitsperword] &= ~((_Ty)1 << _Pos % _Bitsperword);
		return (*this);
		}

	bitset<_Bits>& reset()
		{	// set all bits false
		_Tidy();
		return (*this);
		}

	bitset<_Bits>& reset(size_t _Pos)
		{	// set bit at _Pos to false
		return (set(_Pos, false));
		}

	bitset<_Bits> operator~() const
		{	// flip all bits
		return (bitset<_Bits>(*this).flip());
		}

	bitset<_Bits>& flip()
		{	// flip all bits
		for (int _Wpos = _Words; 0 <= _Wpos; --_Wpos)
			_Array[_Wpos] = (_Ty)~_Array[_Wpos];

		_Trim();
		return (*this);
		}

	bitset<_Bits>& flip(size_t _Pos)
		{	// flip bit at _Pos
		if (_Bits <= _Pos)
			_Xran();	// _Pos off end
		_Array[_Pos / _Bitsperword] ^= (_Ty)1 << _Pos % _Bitsperword;
		return (*this);
		}

	unsigned long to_ulong() const
		{	// convert bitset to unsigned long
		enum
			{	// cause zero divide if unsigned long not multiple of _Ty
			_Assertion = 1
				/ (int)(sizeof (unsigned long) % sizeof (_Ty) == 0)};

		int _Wpos = _Words;
		for (; sizeof (unsigned long) / sizeof (_Ty) <= _Wpos; --_Wpos)
			if (_Array[_Wpos] != 0)
				_Xoflo();	// fail if any high-order words are nonzero

		unsigned long _Val = _Array[_Wpos];
		for (; 0 <= --_Wpos; )
			_Val = _Val << _Bitsperword | _Array[_Wpos];
		return (_Val);
			}

	string to_string() const
		{	// convert bitset to string
		string _Str;
		_Str.reserve(_Bits);

		for (size_t _Pos = _Bits; 0 < _Pos; )
			_Str += (char)('0' + (int)test(--_Pos));
		return (_Str);
		}

	size_t count() const
		{	// count number of set bits
		static char _Bitsperhex[] = "\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4";
		size_t _Val = 0;
		for (int _Wpos = _Words; 0 <= _Wpos; --_Wpos)
			for (_Ty _Wordval = _Array[_Wpos]; _Wordval != 0; _Wordval >>= 4)
				_Val += _Bitsperhex[_Wordval & 0xF];
		return (_Val);
		}

	size_t size() const
		{	// return size of bitset
		return (_Bits);
		}

	bool operator==(const bitset<_Bits>& _Right) const
		{	// test for bitset equality
		for (int _Wpos = _Words; 0 <= _Wpos; --_Wpos)
			if (_Array[_Wpos] != _Right._Getword(_Wpos))
				return (false);
		return (true);
		}

	bool operator!=(const bitset<_Bits>& _Right) const
		{	// test for bitset inequality
		return (!(*this == _Right));
		}

	bool test(size_t _Pos) const
		{	// test if bit at _Pos is set
		if (_Bits <= _Pos)
			_Xran();	// _Pos off end
		return ((_Array[_Pos / _Bitsperword]
			& ((_Ty)1 << _Pos % _Bitsperword)) != 0);
		}

	bool any() const
		{	// test if any bits are set
		for (int _Wpos = _Words; 0 <= _Wpos; --_Wpos)
			if (_Array[_Wpos] != 0)
				return (true);
		return (false);
		}

	bool none() const
		{	// test if no bits are set
		return (!any());
		}

	bitset<_Bits> operator<<(size_t _Pos) const
		{	// return bitset shifted left by _Pos
		return (bitset<_Bits>(*this) <<= _Pos);
		}

	bitset<_Bits> operator>>(size_t _Pos) const
		{	// return bitset shifted right by _Pos
		return (bitset<_Bits>(*this) >>= _Pos);
		}

	_Ty _Getword(size_t _Wpos) const
		{	// get word at _Wpos
		return (_Array[_Wpos]);
		}

private:
	enum
		{	// parameters for packing bits into words
		_Bitsperword = CHAR_BIT * sizeof (_Ty),	// bits in each word
		_Words = _Bits == 0
			? 0 : (_Bits - 1) / _Bitsperword};	// NB: number of words - 1

	void _Tidy(_Ty _Wordval = 0)
		{	// set all words to _Wordval
		for (int _Wpos = _Words; 0 <= _Wpos; --_Wpos)
			_Array[_Wpos] = _Wordval;
		if (_Wordval != 0)
			_Trim();
		}

	void _Trim()
		{	// clear any trailing bits in last word
		if (_Bits % _Bitsperword != 0)
			_Array[_Words] &= ((_Ty)1 << _Bits % _Bitsperword) - 1;
		}

	void _Xinv() const
		{	// report invalid string element in bitset conversion
		_THROW(invalid_argument, "invalid bitset<N> char");
		}

	void _Xoflo() const
		{	// report converted value too big to represent
		_THROW(overflow_error, "bitset<N> overflow");
		}

	void _Xran() const
		{	// report bit index out of range
		_THROW(out_of_range, "invalid bitset<N> position");
		}

	_Ty _Array[_Words + 1];	// the set of bits
	};

		// bitset TEMPLATE FUNCTIONS
template<size_t _Bits> inline
	bitset<_Bits> operator&(const bitset<_Bits>& _Left,
		const bitset<_Bits>& _Right)
		{	// return bitset _Left AND _Right
		bitset<_Bits> _Ans = _Left;
		return (_Ans &= _Right);
		}

template<size_t _Bits> inline
	bitset<_Bits> operator|(const bitset<_Bits>& _Left,
		const bitset<_Bits>& _Right)
		{	// return bitset _Left OR _Right
		bitset<_Bits> _Ans = _Left;
		return (_Ans |= _Right);
		}

template<size_t _Bits> inline
	bitset<_Bits> operator^(const bitset<_Bits>& _Left,
		const bitset<_Bits>& _Right)
		{	// return bitset _Left XOR _Right
		bitset<_Bits> _Ans = _Left;
		return (_Ans ^= _Right);
		}

template<size_t _Bits> inline
	ostream& operator<<(ostream& _Ostr,
		const bitset<_Bits>& _Right)
		{	// insert bitset as a string
		return (_Ostr << _Right.to_string());
		}

template<size_t _Bits> inline
	istream& operator>>(istream& _Istr, bitset<_Bits>& _Right)
		{	// extract bitset as a string
		ios_base::iostate _State = ios_base::goodbit;
		bool _Changed = false;
		string _Str;
		const istream::sentry _Ok(_Istr);

		if (_Ok)
			{	// valid stream, extract elements
			_TRY_IO_BEGIN
			int _Meta = _Istr.rdbuf()->sgetc();
			for (size_t _Count = _Right.size(); 0 < _Count;
				_Meta = _Istr.rdbuf()->snextc(), --_Count)
				{	// test _Meta
				if (_Meta == EOF)
					{	// end of file, quit
					_State |= ios_base::eofbit;
					break;
					}
				else if (_Meta != '0' && _Meta != '1')
					break;	// invalid element
				else if (_Str.max_size() <= _Str.size())
					{	// no room in string, give up (unlikely)
					_State |= ios_base::failbit;
					break;
					}
				else
					_Str.append(1, (char)_Meta), _Changed = true;
				}
			_CATCH_IO_(_Istr)
			}

		if (!_Changed)
			_State |= ios_base::failbit;
		_Istr.setstate(_State);
		_Right = bitset<_Bits>(_Str);	// convert string and store
		return (_Istr);
		}
_STD_END
#endif /* _BITSET */

/*
 * Copyright (c) 1992-2003 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
V4.02:1296 */
