mjbitset.h

cmjbitset_demo

			pos++;
		}
#ifdef DEBUG_CMJBITSET
		m_bitset.bitset(_X);

		_ASSERT((*this)== m_bitset);
	
     
#endif
	}



	bool operator!=(const bitset<_N>& _R) const {
		return (!(*this == _R)); 
	}

	CMJBitset<_N>& operator|=(const CMJBitset<_N>& _R) {
#ifdef DEBUG_CMJBITSET
		_ASSERT(_R == _R.m_bitset );
		_ASSERT((*this) == m_bitset);
#endif
	
		reset_normal_type();

		switch (m_type)
		{
		case BS_SPARSE:
			switch (_R.m_type)
			{
			case BS_SPARSE:
				if (_R.m_len == _N || m_len == _N)
				{
					// nothing to do
				}
				else
				{
					_INDEX bit =0;
					for (int i = 0; i < _R.m_len;i++)
					{
						bit += _R.m_pData[i];
						this->set(bit++);
					}
				}
				break;
			case BS_NORMAL:
				if (m_len == _N)
				{
					// nothing to do
				}
				else
				{
					for (_INDEX bit =0; bit < _N; bit++)
					{
						if (_R.test(bit))
						{
							this->set(bit);
						}
					}

				}
				break;
			case BS_FULL:
				if (m_len == 0)
				{
					// nothing to do
				}
				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);
						}
						bit = ++unset_bit;
					}
				}
		
			}
			break;
		case BS_NORMAL:
		switch (_R.m_type)
			{
			case BS_SPARSE:
				if (_R.m_len == _N )
				{
					// nothing to do
				}
				else
				{
					_INDEX bit =0;
					for (int i = 0; i < _R.m_len;i++)
					{
						bit += _R.m_pData[i];
						this->set(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_FULL:
			
				_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);
					}
					bit = ++unset_bit;
				}
				
		
			}
			break;
		case BS_FULL:
			switch (_R.m_type)
			{
			case BS_SPARSE:
				if (_R.m_len == _N || m_len == 0)
				{
					// nothing to do
				}
				else
				{
					_INDEX bit =0;
					for (int i = 0; i < _R.m_len;i++)
					{
						bit += _R.m_pData[i];
						this->set(bit++);
					}
				}
				break;
			case BS_NORMAL:
				if (m_len == 0)
				{
					// nothing to do
				}
				else
				{
					for (_INDEX bit =0; bit < _N; bit++)
					{
						if (_R.test(bit))
						{
							this->set(bit);
						}
					}

				}
				break;
			case BS_FULL:
				if (m_len == 0)
				{
					// nothing to do
				}
				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);
						}
						bit = ++unset_bit;
					}
					// fill remains
					for (;bit <_N;bit++)
					{
						set(bit);
					}
				}
			}

		}


#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
	
		_ASSERT((*this) == m_bitset);
#endif

		if (m_type == BS_NORMAL && _R.m_type == BS_NORMAL)
		{
			*(bitset<N> *)m_pData) ~= *(bitset<N> *)_R.m_pData);
		}
		else
		{
			for (_INDEX i = 0; i < _N; i++)
			{
				this->set(i, test(i) ^ _R.test(i));
			}
		}

#ifdef DEBUG_CMJBITSET
		this->m_bitset ^= _R.bitset();
		_ASSERT((*this) == m_bitset);
#endif
		return (*this); 
	
	}


	bool operator==(const CMJBitset<_N>& _R) const {
#ifdef DEBUG_CMJBITSET
	
		_ASSERT((*this) == m_bitset);
#endif
		switch m_type)
		{
		case BS_SPARSE:
			switch (_R.m_type)
			{
			case BS_SPARSE:
				if (m_len != _R.m_len) return false;
				if (m_len == _N) return true;

				return (memcmp(m_pData,_R.m_pData, m_len  * sizeof(_DATA)) == 0);
			case BS_NORMAL:
				for (_INDEX i = 0; i < _N; i++)
				{
					if (test(i) != _R.test(i)) return false;
				}

				return true;
			case BS_FULL:
				// bad place to be the types should always
				if (_N - m_len != _R.m_len) return false;
				for (_INDEX i = 0; i < _N; i++)
				{
					if (test(i) != _R.test(i)) return false;
				}
				return true;
			}
			_ASSERT(false);
			break;
		case BS_NORMAL:
			switch (_R.m_type)
			{
			case BS_NORMAL:
				return *(bitset<_N> *) m_pData) == *(bitset<_N> *)_R.m_pData);
			case BS_SPARSE:
			case BS_FULL:
				for (_INDEX i = 0; i < _N; i++)
				{
					if (test(i) != _R.test(i)) return false;
				}
				return true;
			}
			_ASSERT(false);
		case BS_FULL:
			switch (_R.m_type)
			{
				case BS_FULL:
				if (m_len != _R.m_len) return false;
				if (m_len == _N) return true;

				return (memcmp(m_pData,_R.m_pData, m_len  * sizeof(_DATA)) == 0);
			case BS_NORMAL:
				for (_INDEX i = 0; i < _N; i++)
				{
					if (test(i) != _R.test(i)) return false;
				}

				return true;
			case BS_SPARSE:
				// bad place to be the types should always
				if (_N - m_len != _R.m_len) return false;
				for (_INDEX i = 0; i < _N; i++)
				{
					if (test(i) != _R.test(i)) return false;
				}
				return true;
			}
			_ASSERT(false);
			break;

		}
	}

	CMJBitset<_N> operator~() const {
#ifdef DEBUG_CMJBITSET
		_ASSERT((*this) == m_bitset);

#endif
		return (CMJBitset<_N>(*this).flip()); 
	}



	CMJBitset<_N>& flip(size_t _P) {
		this->set(_P,!test(_P));
#ifdef DEBUG_CMJBITSET
		m_bitset.flip(_P);
		_ASSERT((*this) == m_bitset);
#endif		
		return (*this); 
	}

	CMJBitset<_N>& flip(){
#ifdef DEBUG_CMJBITSET
		//check_heap();
		_ASSERT((*this) == m_bitset);
#endif

		switch (m_type)
		{

		case BS_SPARSE:
			
			m_type = BS_FULL;
			
			break;
		case BS_FULL:
			m_type = BS_SPARSE;
			break;
		case BS_NORMAL:

			((std::bitset<_N> *)m_pData)->flip();
		}
#ifdef DEBUG_CMJBITSET
		m_bitset.flip();
		_ASSERT((*this) == m_bitset);
		//check_heap();
#endif
		return (*this);
	}


	CMJBitset<_N>& set(size_t _P, bool _X = true) {
#ifdef DEBUG_CMJBITSET
		//check_heap();
		_ASSERT((*this) == m_bitset);
#endif
		if (_N <= _P)
			_Xran();

		switch(m_type)
		{
		case BS_NORMAL:
			((std::bitset<_N> *)m_pData)->set(_P,_X);
			break;
		default:
			if (_X)
			{
				if (!test(_P))
				{
					set_unset_bit(_P);
				}
			}
			else
			{

				if (test(_P))
				{

					reset_set_bit(_P);
				}
			}
		}
#ifdef DEBUG_CMJBITSET
		m_bitset.set(_P,_X);
		_ASSERT((*this) == m_bitset);
		//check_heap();
#endif
		return (*this);
	}

	CMJBitset<_N>& set(){
		m_type = BS_FULL;
		m_len = 0;
#ifdef DEBUG_CMJBITSET
		m_bitset.set();
		_ASSERT((*this) == m_bitset);
#endif
		return (*this); 
	}
	size_t size() const {
		return (_N); 
	}
	string to_string() const {
		string _S;
		_S.reserve(_N);
		for (size_t _P = _N; 0 < _P; )
			_S += test(--_P) ? '1' : '0';
		return (_S); 
	}
	
	bool none() const {
#ifdef DEBUG_CMJBITSET
		//check_heap();
		_ASSERT((*this) == m_bitset);
#endif
		return (!any());
	}

	bool any() const{
#ifdef DEBUG_CMJBITSET
	
		_ASSERT((*this) == m_bitset);
		//check_heap();
#endif
		switch (m_type)
		{
		case BS_SPARSE:

			return m_len >0;
		case BS_FULL:
			return m_len < _N;
		case BS_NORMAL:
			return ((std::bitset<_N> *)m_pData)->any();
		}

		_ASSERT(false);
		return false;
	}

	bool at(size_t _P) const {
		if (_N <= _P)
			_Xran();
		return (test(_P)); 
	}



	bitset<_N> bitset() const{

	
		switch (m_type)
		{
		case BS_NORMAL:

			return *(bitset<N> *)m_pData);

		case  BS_SPARSE:
			
			bitset<_N> bitmap;

			_INDEX bit =0;
			for (_INDEX  i = 0; i < m_len;i++)
			{
		
			
				bit += m_pData[i];
				bitmap.set(bit);
				bit++;
				

			}
		
			return bitmap;
		case BS_FULL:
			bitset<_N> bitmap;
			bitmap.set();

			_INDEX bit =0;
			for (_INDEX  i = 0; i < m_len;i++)
			{
				 
			
				bit += m_pData[i];
				bitmap.reset(bit);
				bit++;
				
			}
		
			return bitmap;
		}
	}
	

	void change_type(unsigned char type)
	{

		if (m_type == type) return;


		if (type == BS_NORMAL)
		{
#ifndef CMJBITSET_RESERVE_SPACE
			free(m_pData);

			m_pData = NULL;
#else
			if (m_pData != &m_Default[0])
			{
				free(m_pData);
				m_pData = &m_Default[0];
			}


#endif
		}
		m_type = type;
	}

	bool save(FILE *fp)
	{
		if (fwrite(&mask->m_bitset.m_type, 1,1, fp) !=1) goto save_error;

		if (fwrite(&mask->m_bitset.m_len, sizeof(unsigned short),1,fp) != 1) goto save_error;

		if (mask->m_bitset.m_len  < BITS_PER_DICT && mask->m_bitset.m_len )
		{
			switch(m_bitset.m_type)
			{
			case CMJBitset<BITS_PER_DICT>::BS_SPARSE:
			case CMJBitset<BITS_PER_DICT>::BS_FULL:
#ifdef CMJBITSET_USE_SHORT		
				if (fwrite((void *)mask->m_bitset.m_pData,sizeof(unsigned short), mask->m_bitset.m_len) != m_len) goto save_error;
#else
				if (fwrite((void *)mask->m_bitset.m_pData,sizeof(unsigned char), mask->m_bitset.m_len) != m_len) goto save_error;

#endif
				break;
			case CMJBitset<BITS_PER_DICT>::BS_NORMAL:
				if (fwrite((void *)this->m_bitset.m_pData,1, this->m_bitset.m_len)!= m_len) goto save_error;
				break;
			default:
				_ASSERT(FALSE);
			}


		}
		return true;
save_error:
		return false;
	}


	bool load(FILE *fp)
	{
		unsigned short len;
		if (fread(&this->m_bitset.m_type,1,1,fp) != 1) goto load_error;
		if (fread(&len, sizeof(unsigned short),1,fp) != 1) goto load_error;
		switch(m_bitset.m_type)
		{
		case CMJBitset<BITS_PER_DICT>::BS_SPARSE:
		case CMJBitset<BITS_PER_DICT>::BS_FULL:
			if (len  < BITS_PER_DICT && len )
			{
				this->m_bitset.allocate(len);
#ifdef CMJBITSET_USE_SHORT
				if (fread(this->m_bitset.m_pData,sizeof(unsigned short), len,fp) != len) goto load_error
#else
				if (fread(this->m_bitset.m_pData,sizeof(unsigned char), len,fp)) != len) goto load_error;
#endif

			}
			else
			{
				this->m_bitset.m_len = len;
			}
			break;
		case CMJBitset<BITS_PER_DICT>::BS_NORMAL:
			this->m_bitset.allocate_normal(len);
			if (fread(this->m_bitset.m_pData,1, len,fp)) != len) goto load_error;
			break;
		
		}
#ifdef DEBUG_CMJBITSET
		this->m_bitset.set_debug_bitset();
#endif
		return true;
load_error:
		return false;

	}

#ifdef CMJBITSET_RESERVE_SPACE
	void allocate(_INDEX len)
	{
		
	
			_ASSERT(m_type != BS_NORMAL);
			_ASSERT(len < _N);
			if (m_pData == &m_Default[0] && len < CMJBITSET_DEFAULT_SIZE)
			{

			}
			else if (m_pData == &m_Default[0] )
			{
				
				_ASSERT(m_len < CMJBITSET_DEFAULT_SIZE || m_len == _N);
#ifdef CMJBITSET_RECORD_ALLOCATION_LENGTH		
				m_alloc = (len>CMJBITSET_SMALLEST_ALLOC?len :CMJBITSET_SMALLEST_ALLOC);
				m_pData = (_DATAPTR ) malloc(sizeof(_DATA) * m_alloc);
#else
				m_pData = (_DATAPTR ) malloc(sizeof(_DATA) *(len>CMJBITSET_SMALLEST_ALLOC?len :CMJBITSET_SMALLEST_ALLOC));
#endif
				if (m_len != _N)
				{
					memcpy(m_pData,&m_Default[0], m_len * sizeof(_DATA));
	}

			}
#ifdef CMJBITSET_RECORD_ALLOCATION_LENGTH
			else if (len > m_alloc)
			
#else
			else if (len > m_len)
#endif
			{
#ifdef CMJBITSET_RECORD_ALLOCATION_LENGTH
				m_alloc = (len>CMJBITSET_SMALLEST_ALLOC? CMJBITSET_ROUNDUP(len) :CMJBITSET_SMALLEST_ALLOC);
				m_pData = (_DATAPTR ) realloc(m_pData, sizeof(_DATA) * m_alloc);

#else
				m_pData = (_DATAPTR ) realloc(m_pData, sizeof(_DATA) *(len>CMJBITSET_SMALLEST_ALLOC? CMJBITSET_ROUNDUP(len) :CMJBITSET_SMALLEST_ALLOC));
#endif
			}
			m_len = len;
	

	

	}


	void allocate_normal(_INDEX len)
	{
		
	
			_ASSERT(m_type == BS_NORMAL);
			_ASSERT(len == sizeof(std::bitset<_N>));
			if (m_pData != &m_Default[0] )
			{
				free(m_pData);
			}		
			
			m_pData = (_DATAPTR )calloc(1,len);
			
		
			m_len = len;
	

	

	}
#else
	void allocate(_INDEX len)
	{
		
	
			_ASSERT(m_type != BS_NORMAL);
			_ASSERT(len < _N);
			if (!m_pData  )
			{
		
#ifdef CMJBITSET_RECORD_ALLOCATION_LENGTH
				m_alloc = (len> CMJBITSET_SMALLEST_ALLOC?len :CMJBITSET_SMALLEST_ALLOC);
				m_pData = (_DATAPTR ) malloc(sizeof(_DATA) * m_alloc);
#else
				m_pData = (_DATAPTR ) malloc(sizeof(_DATA) *(len> CMJBITSET_SMALLEST_ALLOC?len :CMJBITSET_SMALLEST_ALLOC));
#endif			
				
			}
#ifdef CMJBITSET_RECORD_ALLOCATION_LENGTH
			else if (len > m_alloc)
#else
			else if (len > m_len)
#endif
			{
#ifdef CMJBITSET_RECORD_ALLOCATION_LENGTH

				m_alloc = (len>CMJBITSET_SMALLEST_ALLOC? CMJBITSET_ROUNDUP(len) :CMJBITSET_SMALLEST_ALLOC);
				m_pData = (_DATAPTR ) realloc(m_pData, sizeof(_DATA) * m_alloc);
#else
				m_pData = (_DATAPTR ) realloc(m_pData, sizeof(_DATA) *(len>CMJBITSET_SMALLEST_ALLOC? CMJBITSET_ROUNDUP(len) :CMJBITSET_SMALLEST_ALLOC));

#endif
			}
			m_len = len;
	

	

	}


	void allocate_normal(_INDEX len)
	{
		
	
			_ASSERT(m_type == BS_NORMAL);
			_ASSERT(len == sizeof(std::bitset<_N>));
			if (m_pData)
			{
				free(m_pData);
			}		
			
			m_pData = (_DATAPTR )calloc(1,len);
			
		
			m_len = len;
	

	

	}

#endif

	// 4 4 (0000100001) << 5  = 4   (00001)
    // 0 0 0 0 (1111) < 3 = 0  (1)

	// 
	CMJBitset<_N >& operator>>=(size_t _P){
#ifdef DEBUG_CMJBITSET
		
		_ASSERT((*this) == m_bitset);
		m_bitset>>= _P;
		//fprintf(stderr,"CMJBitset::%s\n",this->to_string().c_str());
		//check_heap();
#endif

		switch (m_type)
		{
		case BS_SPARSE:
			if (m_len == _N)
			{
				m_type = BS_FULL;
				allocate(1);
				m_pData[0] = _N - _P ;
			}
			else
			{
				while (m_len && _P>0)
				{
					_INDEX c = m_pData[0];
					if (c >= _P)
					{
						m_pData[0] -= _P;
						break;
					}
					else
					{
						m_len--;
						_P -= c+1;
						memmove(&m_pData[0], &m_pData[1], m_len * sizeof(_DATA));
					}
				}
			}
			break;
		case BS_NORMAL:
			*(std::bitset<_N> *)m_pData>>=_P;
			break;
		case BS_FULL:
			if (m_len == 0)
			{
				allocate(1);
				m_pData[0] = _N - _P;
			}
			else
			{
				while ( _P>0)
				{	
					_INDEX c = m_pData[0];
				
					if (c >= _P)
					{
						m_pData[0] -= _P;
						break;
					}
					else 
					{