📄 mjbitset.h
字号:
// MJBitset.h: interface for the CMJBitset class.
//
// (c) 2004 MarsJupiter LTD
//
//
// You may use and distribute this class freely,
// but may not remove this header or claim ownership.
//
// If you do use this class we would appreciate an email to
// martin@marsjupiter.com
//
// If you are a decent sized company and use this class then
// some payment would also be appreciated.
//
//
// Version history
//
// 1.00 June 14th 2004
//
//
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_MJBITSET_H__44E16525_5D70_4530_B0C1_5E90AAA4F4CA__INCLUDED_)
#define AFX_MJBITSET_H__44E16525_5D70_4530_B0C1_5E90AAA4F4CA__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include <use_ansi.h>
#include <istream>
#ifdef _MSC_VER
/*
* Currently, all MS C compilers for Win32 platforms default to 8 byte
* alignment.
*/
#pragma pack(push,8)
#endif /* _MSC_VER */
//
// When DEBUG_CMMJBITSET is defined, then a shadow bitset is kept and validated against operations.
// This is obviously very slow and uses loads of memory and defeats any purpose in using this class
// and hence should never be used outside of a debug session.
//
//
//#define DEBUG_CMJBITSET
//
// data representation type for bitsets <= 256 CMJBITSET_USE_CHAR should be defined
//
//#define CMJBITSET_USE_CHAR
#define CMJBITSET_USE_SHORT
//#define CMJBITSET_USE_LONG
#include <bitset>
#include <vector>
using namespace std;
// Tweakable parameters
//
// Reserving space usually is effective, as in a sparse bitset it does save the overhead of
// malloc/free. How much space to reserve for best performance will very according to how
// sparse the average bitset in your program is.
//
// remembering the allocated length, adds memory to each instance and would probably only help
// if the realloc being used was really brain dead.
//
//
// in a similar fashion the ROUNDBITS/ROUNDUP/SMALLEST_ALLOC stuff will have little postive effect
// unless malloc/realloc are pretty bad.
//
#define CMJBITSET_ROUNDBITS 0
#define CMJBITSET_ROUNDUP(len) ((len) | CMJBITSET_ROUNDBITS)
// never allocate less than this amount.
#define CMJBITSET_SMALLEST_ALLOC ((_N/64))
//
// use some space within the class to avoid the need for malloc/free in many cases
//
#define CMJBITSET_RESERVE_SPACE
#define CMJBITSET_DEFAULT_SIZE 4 // applies only if CMJBITSET_RESERVE_SPACE is set
// check representation type for BS_NORMAL when (check & CMJBITSET_CHECK_NORMAL_MASK)==CMJBITSET_CHECK_NORMAL_MASK
#define CMJBITSET_CHECK_NORMAL_MASK 31
// record allocation length
#undef CMJBITSET_RECORD_ALLOCATION_LENGTH
template<size_t _N> class CMJBitset
{
public:
enum Format {BS_NORMAL, BS_SPARSE, BS_FULL};
#ifdef CMJBITSET_USE_CHAR
//typedef unsigned char _TYPE;
typedef short _INDEX; // needed if we have _N = 256
typedef unsigned char * _DATAPTR;
typedef unsigned char _DATA;
#endif
#ifdef CMJBITSET_USE_SHORT
//typedef unsigned long _TYPE;
typedef unsigned short _INDEX; // must be able to index _N hence _N cannot be 0x10000
typedef unsigned short * _DATAPTR;
typedef unsigned short _DATA;
#endif
#ifdef CMJBITSET_USE_LONG
//typedef unsigned long _TYPE;
typedef unsigned long _INDEX; // must be able to index _N hence _N cannot be 0x10000
typedef unsigned long * _DATAPTR;
typedef unsigned long _DATA;
#endif
unsigned char m_type;
_INDEX m_len;
_DATAPTR m_pData;
#ifdef CMJBITSET_RESERVE_SPACE
_DATA m_Default[CMJBITSET_DEFAULT_SIZE];
#endif
#ifdef CMJBITSET_RECORD_ALLOCATION_LENGTH
_INDEX m_alloc;
#endif
#ifdef DEBUG_CMJBITSET
bitset <_N> m_bitset;
#endif
public:
CMJBitset<_N>(){
#ifdef CMJBITSET_RESERVE_SPACE
m_pData = (_DATAPTR)&m_Default[0];
#else
m_pData = NULL;
#endif
m_len = 0;
m_type = BS_SPARSE;
#ifdef DEBUG_CMJBITSET
_ASSERT((*this)== m_bitset);
#endif
}
CMJBitset<_N>( const CMJBitset<_N> &_L)
{
#ifdef CMJBITSET_RESERVE_SPACE
m_pData = (_DATAPTR )&m_Default[0];
#else
m_pData = NULL;
#endif
switch (_L.m_type)
{
case BS_SPARSE:
// all bits set is a special case
m_type = BS_SPARSE;
if (_L.m_len == _N)
{
m_len = (_INDEX) _N;
}
else
{
m_len = 0;;
allocate( _L.m_len);
memcpy(m_pData, _L.m_pData, m_len * sizeof(_DATA));
}
break;
case BS_FULL:
m_type = BS_FULL;
// no bits set is a special case
if (_L.m_len == _N)
{
m_len = (_INDEX) _N;
}
else
{
m_len = 0;;
allocate( _L.m_len);
memcpy(m_pData, _L.m_pData, m_len * sizeof(_DATA));
}
break;
case BS_NORMAL:
m_type = BS_NORMAL;
m_len = _L.m_len;
allocate_normal(m_len);
memcpy(m_pData, _L.m_pData, m_len);
break;
}
#ifdef DEBUG_CMJBITSET
m_bitset = _L.m_bitset;
_ASSERT((*this)== m_bitset);
#endif
}
~CMJBitset<_N>(){
#ifdef DEBUG_CMJBITSET
//_ASSERT((*this)== m_bitset);
//check_heap();
#endif
#ifdef CMJBITSET_RESERVE_SPACE
if (m_pData != &m_Default[0]) free(m_pData);
#else
if (m_pData) free(m_pData);
#endif
}
size_t count() const {
switch (m_type)
{
case BS_SPARSE:
return m_len;
case BS_NORMAL:
{
std::bitset<_N> *pData = (std::bitset<_N> *)m_pData;
return pData->count();
}
case BS_FULL:
return _N - m_len;
}
_ASSERT(false);
return false;
}
bool test(_INDEX bit) const{
switch(m_type)
{
case BS_SPARSE:
{
if (!m_len) return false;
if (m_len == _N) return true;
_INDEX i = 0;
_INDEX pos = 0;
while (i < m_len)
{
_ASSERT(m_pData[i] < _N);
pos += m_pData[i++];
if (pos == bit) return true;
if (pos > bit) return false;
pos++;
}
return false;
}
case BS_NORMAL:
return ((std::bitset<_N> *)m_pData)->test(bit);
case BS_FULL:
{
if (!m_len) return true;
if (m_len == _N) return false;
_INDEX i = 0;
_INDEX pos = 0;
while (i < m_len)
{
_ASSERT(m_pData[i] < _N);
pos += m_pData[i++];
if (pos == bit) return false;
if (pos > bit) return true;
pos++;
}
return true;
}
}
_ASSERT(false);
return false;
}
#ifdef DEBUG_CMJBITSET
void set_debug_bitset()
{
switch(m_type)
{
case BS_SPARSE:
{
this->m_bitset.reset();
_INDEX bit=0;
for (_INDEX i = 0; i < m_len;i++)
{
bit += m_pData[i];
m_bitset.set(bit);
bit++;
}
break;
}
case BS_FULL:
{
this->m_bitset.set();
_INDEX bit=0;
for (_INDEX i = 0; i < m_len;i++)
{
bit += m_pData[i];
m_bitset.set(bit,0);
bit++;
}
break;
}
case BS_NORMAL:
{
std::bitset<_N> *pL = (std::bitset<_N> *)m_pData;
m_bitset = *pL;
}
break;
}
_ASSERT((*this) == m_bitset);
}
#endif
CMJBitset<_N>& operator = (const CMJBitset<_N> &_R){
#ifdef DEBUG_CMJBITSET
//_ASSERT(_R == _R.m_bitset );
// _ASSERT((*this)== m_bitset);
#endif
change_type(_R.m_type);
switch (_R.m_type)
{
case BS_NORMAL:
allocate_normal(_R.m_len);
memcpy(m_pData,_R.m_pData,m_len);
break;
default:
if (_R.m_len == _N)
{
m_len = _N;
}
else
{
allocate(_R.m_len);
memcpy(m_pData,_R.m_pData,m_len * sizeof(_DATA));
}
}
#ifdef DEBUG_CMJBITSET
m_bitset = _R.m_bitset;
//_ASSERT((*this)== m_bitset);
#endif
return (*this);
}
CMJBitset<_N>& operator&=(const CMJBitset<_N>& _R){
#ifdef DEBUG_CMJBITSET
//check_heap();
_ASSERT((*this) == m_bitset);
#endif
reset_normal_type();
switch (m_type)
{
case BS_SPARSE:
switch (_R.m_type)
{
case BS_SPARSE:
{
_INDEX bit =0;
if (m_len == _R.m_len && m_len == _N)
{
}
else
{
CMJBitset<_N> temp;
if (m_len < _R.m_len)
{
for (_INDEX i = 0; i < m_len;i++)
{
bit += m_pData[i];
if (_R.test(bit)){ temp.set(bit); }
bit++;
}
}
else
{
for (_INDEX i = 0; i < _R.m_len;i++)
{
bit += _R.m_pData[i];
if (test(bit)) { temp.set(bit); }
bit++;
}
}
*this = temp;
}
break;
}
default:
{
CMJBitset<_N> temp;
_INDEX bit=0;
for (_INDEX i = 0; i < m_len;i++)
{
bit += m_pData[i];
if (_R.test(bit)){ temp.set(bit); }
bit++;
}
*this = temp;
break;
}
}
break;
case BS_FULL:
switch(_R.m_type)
{
case BS_FULL:
{
_INDEX bit = 0;
for (_INDEX i = 0; i < _R.m_len;i++)
{
bit += _R.m_pData[i];
set(bit,0);
bit++;
}
}
break;
case BS_SPARSE:
{
CMJBitset<_N> temp;
_INDEX bit = 0;
for (_INDEX i = 0; i < _R.m_len;i++)
{
bit += _R.m_pData[i];
if (test(bit)) { temp.set(bit); }
bit++;
}
*this = temp;
break;
}
case BS_NORMAL:
{
CMJBitset<_N> temp;
for (_INDEX bit = 0; bit < _N; bit++)
{
if (_R.test(bit)){ temp.set(bit); }
}
*this = temp;
break;
}
}
break;
case BS_NORMAL:
switch (_R.m_type)
{
case BS_FULL:
{
_INDEX bit = 0;
for (_INDEX i = 0; i < _R.m_len;i++)
{
bit += _R.m_pData[i];
set(bit,0);
bit++;
}
break;
}
case BS_NORMAL:
{
std::bitset<_N> *pL = (std::bitset<_N> *)m_pData;
std::bitset<_N> *pR = (std::bitset<_N> *)_R.m_pData;
*pL &= *pR;
break;
}
case BS_SPARSE:
{
CMJBitset<_N> temp;
_INDEX bit = 0;
for (_INDEX i = 0; i < _R.m_len;i++)
{
bit += _R.m_pData[i];
if (test(bit)) { temp.set(bit); }
bit++;
}
*this = temp;
break;
}
}
break;
}
#ifdef DEBUG_CMJBITSET
//check_heap();
this->m_bitset &= _R.m_bitset;
_ASSERT((*this) == m_bitset);
#endif
return (*this);
}
friend CMJBitset< _N> operator&(const CMJBitset<_N>& _L,const CMJBitset<_N>& _R)
{
return (CMJBitset<_N>(_L) &= _R);
}
friend CMJBitset<_N> operator|(const CMJBitset<_N>& _L,
const CMJBitset<_N>& _R)
{return (CMJBitset<_N>(_L) |= _R); }
CMJBitset<_N> operator<<(size_t _R) const {
return (CMJBitset<_N>(*this) <<= _R);
}
CMJBitset<_N> operator>>(size_t _R) const {
return (CMJBitset<_N>(*this) >>= _R);
}
CMJBitset<_N>& reset( CMJBitset<_N> &_R){
switch (m_type)
{
case BS_SPARSE:
switch(_R.m_type)
{
case BS_SPARSE:
if (_R.m_len == _N)
{
m_len = 0;
}
else
{
_INDEX bit = 0;
for (_INDEX i = 0; i < _R.m_len;i++)
{
bit += _R.m_pData[i];;
set(bit,0);
bit++;
}
}
break;
case BS_FULL:
if (_R.m_len == 0)
{
m_len = 0;
}
else
{
_INDEX bit=0;
_INDEX unset_bit = 0;
for (_INDEX i = 0; i < _R.m_len; i++)
{
unset_bit += _R.m_pData[i];
for (;bit < unset_bit; bit++)
{
set(bit,0);
}
bit = ++unset_bit;
}
for (;bit < _N;bit++)
{
set(bit,0);
}
}
break;
case BS_NORMAL:
for (_INDEX bit = 0; bit < _N;bit++)
{
if (_R.test(bit))
{
set(bit,0);
}
}
break;
}
break;
case BS_FULL:
switch (_R.m_type)
{
case BS_SPARSE:
if (_R.m_len == _N)
{
m_type = BS_SPARSE;
m_len = 0;
}
else
{
_INDEX bit = 0;
for (_INDEX i = 0; i < _R.m_len;i++)
{
bit += _R.m_pData[i];;
set(bit,0);
bit++;
}
}
break;
case BS_NORMAL:
{
for (_INDEX bit = 0; bit < _N;bit++)
{
if (_R.test(bit))
{
set(bit,0);
}
}
break;
}
case BS_FULL:
if (_R.m_len =0)
{
this->m_len = 0;
}
else
{
_INDEX bit=0;
_INDEX unset_bit = 0;
for (_INDEX i = 0; i < _R.m_len; i++)
{
unset_bit += _R.m_pData[i];
for (;bit < unset_bit; bit++)
{
set(bit,0);
}
bit = ++unset_bit;
}
for (;bit < _N; bit++)
{
set(bit,0);
}
break;
}
}
break;
case BS_NORMAL:
switch (_R.m_type)
{
case BS_NORMAL:
{
std::bitset<_N> *pL = (std::bitset<_N> *)m_pData;
std::bitset<_N> *pR = (std::bitset<_N> *)_R.m_pData;
*pL &= ~(*pR);
break;
}
case BS_SPARSE:
{
_INDEX bit = 0;
for (_INDEX i = 0; i < _R.m_len;i++)
{
bit += _R.m_pData[i];;
set(bit,0);
bit++;
}
break;
}
case BS_FULL:
if (_R.m_len == 0)
{
m_type = BS_SPARSE;
m_len = 0;
}
else
{
_INDEX bit=0;
_INDEX unset_bit = 0;
for (_INDEX i = 0; i < _R.m_len; i++)
{
unset_bit += _R.m_pData[i];
for (;bit < unset_bit; bit++)
{
set(bit,0);
}
bit = ++unset_bit;
}
for (;bit < _N;bit++)
{
set(bit,0);
}
}
break;
}
break;
}
#ifdef DEBUG_CMJBITSET
m_bitset &= ~_R.m_bitset;
_ASSERT((*this) == m_bitset);
#endif
return (*this);
}
CMJBitset<_N>& reset(){
m_type = BS_SPARSE;
m_len = 0;
#ifdef DEBUG_CMJBITSET
m_bitset.reset();
_ASSERT((*this) == m_bitset);
#endif
return (*this);
}
CMJBitset(unsigned long _X){
m_type = BS_SPARSE;
m_len = 0;
int pos=0;
while(_X)
{
if (_X & 1) set(pos);
_X >>=1;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -