473 lines
12 KiB
Plaintext
473 lines
12 KiB
Plaintext
|
// bitset standard header
|
||
|
|
#pragma once
|
||
|
|
#ifndef _BITSET_
|
||
|
|
#define _BITSET_
|
||
|
|
#include <string>
|
||
|
|
|
||
|
|
#pragma pack(push,8)
|
||
|
|
#pragma warning(push,3)
|
||
|
|
|
||
|
|
#pragma warning(disable: 4127)
|
||
|
|
_STD_BEGIN
|
||
|
|
|
||
|
|
// TEMPLATE CLASS bitset
|
||
|
|
template<size_t _Bits> class bitset
|
||
|
|
{ // store fixed-length sequence of Boolean elements
|
||
|
|
typedef unsigned long _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);
|
||
|
|
}
|
||
|
|
|
||
|
|
#define _BITSET_SIZE_TYPE \
|
||
|
|
typename basic_string<_Elem, _Tr, _Alloc>::size_type
|
||
|
|
|
||
|
|
template<class _Elem,
|
||
|
|
class _Tr,
|
||
|
|
class _Alloc>
|
||
|
|
explicit bitset(const basic_string<_Elem, _Tr, _Alloc>& _Str,
|
||
|
|
_BITSET_SIZE_TYPE _Pos = 0)
|
||
|
|
{ // construct from [_Pos, ...) elements in string
|
||
|
|
_Construct(_Str, _Pos, basic_string<_Elem, _Tr, _Alloc>::npos);
|
||
|
|
}
|
||
|
|
|
||
|
|
template<class _Elem,
|
||
|
|
class _Tr,
|
||
|
|
class _Alloc>
|
||
|
|
explicit bitset(const basic_string<_Elem, _Tr, _Alloc>& _Str,
|
||
|
|
_BITSET_SIZE_TYPE _Pos,
|
||
|
|
_BITSET_SIZE_TYPE _Count)
|
||
|
|
{ // construct from [_Pos, _Pos + _Count) elements in string
|
||
|
|
_Construct(_Str, _Pos, _Count);
|
||
|
|
}
|
||
|
|
|
||
|
|
template<class _Elem,
|
||
|
|
class _Tr,
|
||
|
|
class _Alloc>
|
||
|
|
void _Construct(const basic_string<_Elem, _Tr, _Alloc>& _Str,
|
||
|
|
_BITSET_SIZE_TYPE _Pos,
|
||
|
|
_BITSET_SIZE_TYPE _Count)
|
||
|
|
{ // initialize from [_Pos, _Pos + _Count) elements in string
|
||
|
|
typename basic_string<_Elem, _Tr, _Alloc>::size_type _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);
|
||
|
|
}
|
||
|
|
|
||
|
|
template<class _Elem,
|
||
|
|
class _Tr,
|
||
|
|
class _Alloc>
|
||
|
|
basic_string<_Elem, _Tr, _Alloc> to_string() const
|
||
|
|
{ // convert bitset to string
|
||
|
|
basic_string<_Elem, _Tr, _Alloc> _Str;
|
||
|
|
typename basic_string<_Elem, _Tr, _Alloc>::size_type _Pos;
|
||
|
|
_Str.reserve(_Bits);
|
||
|
|
|
||
|
|
for (_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);
|
||
|
|
}
|
||
|
|
|
||
|
|
bitset<_Bits> operator&(const bitset<_Bits>& _Right) const
|
||
|
|
{ // return bitset AND _Right
|
||
|
|
return (bitset<_Bits>(*this) &= _Right);
|
||
|
|
}
|
||
|
|
|
||
|
|
bitset<_Bits> operator|(const bitset<_Bits>& _Right) const
|
||
|
|
{ // return bitset OR _Right
|
||
|
|
return (bitset<_Bits>(*this) |= _Right);
|
||
|
|
}
|
||
|
|
|
||
|
|
bitset<_Bits> operator^(const bitset<_Bits>& _Right) const
|
||
|
|
{ // return bitset XOR _Right
|
||
|
|
return (bitset<_Bits>(*this) ^= _Right);
|
||
|
|
}
|
||
|
|
|
||
|
|
_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
|
||
|
|
};
|
||
|
|
|
||
|
|
// TEMPLATE operator<<
|
||
|
|
template<class _Elem,
|
||
|
|
class _Tr,
|
||
|
|
size_t _Bits> inline
|
||
|
|
basic_ostream<_Elem, _Tr>& operator<<(
|
||
|
|
basic_ostream<_Elem, _Tr>& _Ostr, const bitset<_Bits>& _Right)
|
||
|
|
{ // insert bitset as a string
|
||
|
|
return (_Ostr
|
||
|
|
<< _Right.template to_string<_Elem, _Tr, allocator<_Elem> >());
|
||
|
|
}
|
||
|
|
|
||
|
|
// TEMPLATE operator>>
|
||
|
|
template<class _Elem,
|
||
|
|
class _Tr,
|
||
|
|
size_t _Bits> inline
|
||
|
|
basic_istream<_Elem, _Tr>& operator>>(
|
||
|
|
basic_istream<_Elem, _Tr>& _Istr, bitset<_Bits>& _Right)
|
||
|
|
{ // extract bitset as a string
|
||
|
|
ios_base::iostate _State = ios_base::goodbit;
|
||
|
|
bool _Changed = false;
|
||
|
|
string _Str;
|
||
|
|
const typename basic_istream<_Elem, _Tr>::sentry _Ok(_Istr);
|
||
|
|
|
||
|
|
if (_Ok)
|
||
|
|
{ // valid stream, extract elements
|
||
|
|
_TRY_IO_BEGIN
|
||
|
|
typename _Tr::int_type _Meta = _Istr.rdbuf()->sgetc();
|
||
|
|
for (size_t _Count = _Right.size(); 0 < _Count;
|
||
|
|
_Meta = _Istr.rdbuf()->snextc(), --_Count)
|
||
|
|
{ // test _Meta
|
||
|
|
char _Byte;
|
||
|
|
if (_Tr::eq_int_type(_Tr::eof(), _Meta))
|
||
|
|
{ // end of file, quit
|
||
|
|
_State |= ios_base::eofbit;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
else if ((_Byte = _NARROW(_Elem, _Tr::to_char_type(_Meta)))
|
||
|
|
!= '0' && _Byte != '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, _Byte), _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
|
||
|
|
|
||
|
|
#pragma warning(default: 4127)
|
||
|
|
#pragma warning(pop)
|
||
|
|
#pragma pack(pop)
|
||
|
|
|
||
|
|
#endif /* _BITSET */
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Copyright (c) 1992-2001 by P.J. Plauger. ALL RIGHTS RESERVED.
|
||
|
|
* Consult your license regarding permissions and restrictions.
|
||
|
|
V3.10:0009 */
|