mjbitset.h

cmjbitset_demo

						memmove(&m_pData[0], &m_pData[1], (m_len -1) * sizeof(_DATA));
						m_len --;
					
						_P -= c+1;
					
					}
				
				}
				// just one problem all top bits are now set
				_INDEX i = 0;
				_INDEX bit = 0;
				while (i < m_len);
				{
					bit += m_pData[i]; //unset bit

					bit++; // position after unset bit
					i++;
				}
				if (bit < _N-_P)
				{
					allocate(m_len+1);
					m_pData[m_len-1] = (_N- _P) - bit;
					bit = _N - _P +1;
				}
				while (bit < _N)
				{
					allocate(m_len+1);
					m_pData[m_len -1] = 0;
					bit++;

				}

			}


			break;
		}
		
#ifdef DEBUG_CMJBITSET
	
		_ASSERT((*this) == m_bitset);
#endif
		return (*this);
		
	}

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

		case BS_SPARSE:
			if (m_len == _N)
			{
				allocate(1);
				m_type = BS_FULL;
				m_pData[0] = _P-1;
			}
			else
			{
				m_pData[0] += _P;
				// remove overflow
				_INDEX bit = 0;
				for (_INDEX i = 0; i < m_len; i++)
				{
					bit += m_pData[i]  ;  // position of set bit
					if (bit >= _N)
					{
						m_len =i;
						break;
					}
					bit++;
				}
			}
			break;
		case BS_NORMAL:
			*(std::bitset<_N> *)m_pData<<=_P;
			break;
		case BS_FULL:
			if (m_len == 0){
				allocate(_P);
				memset(&m_pData[0], 0, m_len * sizeof(_DATA));
			}
			else 
			{
				//if (m_pData[0] + _P < _N)
				//{
					// remove overflow
					_INDEX bit = 0;
					for (_INDEX i = 0; i < m_len; i++)
					{
						bit += m_pData[i] ; // unset bit pos
						if (bit >= _N-_P)
						{
							m_len = i;;
							break;
						}
						bit++;
					}
					if (m_len + _P >= _N)
					{
						m_len = _N;
						
					}
					else
					{
						allocate(m_len +_P);
						memmove(&m_pData[_P], &m_pData[0], sizeof(_DATA) * (m_len - _P));
						memset(&m_pData[0], 0, _P *sizeof(_DATA));
					}
					//for (;bit < _N;bit++)
					//{
					//	reset_set_bit(bit);
					//}
				//}
				//else
				//{
				//	m_len = _N;
				//}

			}

			break;
	
		}
			
#ifdef DEBUG_CMJBITSET
		m_bitset <<= _P;
		_ASSERT((*this) == m_bitset);
	
#endif
		return (*this);
	}

	bool operator==(const bitset<_N>& _R) const {

		_INDEX count = this->count() ;
		if (count != _R.count()) {
#ifdef DEBUG_CMJBITSET
			//
			// example code of the type useful when regressing the CMJBitset class
			//
			int rc = _R.count();
			fprintf(stderr,"CMjBitset::%s\n",this->to_string().c_str());
			fprintf(stderr,"   Bitset::%s\n",this->m_bitset.to_string().c_str());
#endif
			return false;
		}

		if (count == 0 || count == _N) return true;

		switch (m_type)
		{
		case BS_SPARSE:
			{
			_INDEX bit=0;
			for (_INDEX i = 0; i < m_len; i++)
			{
				bit += m_pData[i];

				if (!_R.test(bit)){
					return false;
				}
				bit++;
			}
			}
			return true;
		case BS_NORMAL:
			{
			std::bitset<_N> *pL = (std::bitset<_N> *)m_pData;

			return *pL == _R;
			}
		case BS_FULL:
			{

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

				if (_R.test(bit)) {
					return false;
				}
				bit++;
			}

			return true;
			}
			

		}
		return false;
			
	}

	void make_sparse()
	{

		_ASSERT(m_type != BS_SPARSE);

		CMJBitset<_N> temp;
		switch (m_type)
		{
		case BS_NORMAL:
				{
				for (_INDEX i = 0; i < _N; i++)
				{
					if (test(i))
					{
						temp.set_unset_bit(i, false);
					}
				}
				break;
				}
			case BS_FULL:
				{
					_INDEX bit= 0;
					_INDEX set_bit = 0;
					_INDEX i = 0;
					while(i < m_len)
					{
						bit += m_pData[i]; // unset bit
						for (_INDEX j = set_bit; j < bit; j++)
						{
							temp.set_unset_bit(j, false);
						}
						bit++;
						set_bit = bit;
						i++;

					}
					for (_INDEX j = bit ; j < _N; j++)
					{
						for (_INDEX j = set_bit; j < bit; j++)
						{
							temp.set_unset_bit(j, false);
						}
					}
					break;
				}

		}
#ifdef DEBUG_CMJBITSET
		temp.m_bitset =this->m_bitset; 
#endif
		*this = temp;
			
#ifdef DEBUG_CMJBITSET
	
		_ASSERT((*this) == m_bitset);
	
#endif
	}


	void make_full()
	{

		_ASSERT(m_type != BS_FULL);

		CMJBitset<_N> temp;

		temp.m_type = BS_FULL;
		temp.m_len = 0;
		switch (m_type)
		{
		case BS_NORMAL:
				{
				for (_INDEX i = 0; i < _N; i++)
				{
					if (!test(i))
					{
						temp.reset_set_bit(i, false);
					}
				}
				break;
				}
			case BS_SPARSE:
				{
					_INDEX bit= 0;
					_INDEX unset_bit = 0;
					_INDEX i = 0;
					while(i < m_len)
					{
						bit += m_pData[i]; 
						for (_INDEX j = unset_bit; j < bit; j++)
						{
							temp.reset_set_bit(j, false);
						}
						bit++;
						unset_bit = bit;
						i++;

					}
					for (_INDEX j = bit ; j < _N; j++)
					{
						for (_INDEX j = unset_bit; j < bit; j++)
						{
							temp.reset_set_bit(j, false);
						}
					}
					break;
				}

		}
#ifdef DEBUG_CMJBITSET
		temp.m_bitset =this->m_bitset; 
#endif
		*this = temp;
			
#ifdef DEBUG_CMJBITSET
	
		_ASSERT((*this) == m_bitset);
	
#endif
	}



	void make_normal()
	{

		_ASSERT(m_type != BS_NORMAL);
			
#ifdef DEBUG_CMJBITSET
	
		//_ASSERT((*this) == m_bitset);
	
#endif
		CMJBitset<_N> temp;

		temp.m_type = BS_NORMAL;
		temp.allocate_normal(sizeof(std::bitset<_N>));

		switch (m_type)
		{
		case BS_FULL:
				{
				std::bitset<_N> *pL = (std::bitset<_N> *)temp.m_pData;
					_INDEX bit= 0;
					_INDEX i = 0;
					pL->set();

					while(i < m_len)
					{
						bit += m_pData[i]; // unset bit
					
						
						pL->set(bit,false);
						
						bit++;
						i++;

					}
				
					break;
				}
			case BS_SPARSE:
				{
					std::bitset<_N> *pL = (std::bitset<_N> *)temp.m_pData;
					pL->reset();
		
					_INDEX bit= 0;
					_INDEX i = 0;
					while(i < m_len)
					{
						bit += m_pData[i]; 
					
							pL->set(bit);
						bit++;
						i++;
			
					}
				
					break;
				}

		}
#ifdef DEBUG_CMJBITSET
		temp.m_bitset =this->m_bitset; 
		//_ASSERT(temp == temp.m_bitset);
#endif
		*this = temp;
			
#ifdef DEBUG_CMJBITSET
	
		//_ASSERT((*this) == m_bitset);
	
#endif
	}


	friend ostream& operator<<(ostream& _O, const CMJBitset<_N>& _R)	{
		for (size_t _P = _N; 0 < _P; )
		_O << _R.test(--_P) ? '1' : '0';
		return (_O); 
	}
		// TEMPLATE operator>>
	friend istream& operator>>(istream& _I, CMJBitset<_N>& _R)	{
		ios_base::iostate _St = ios_base::goodbit;
		bool _Chg = false;
		string _X;
		const istream::sentry _Ok(_I);
		if (_Ok)
		{
			_TRY_IO_BEGIN
				int _C = _I.rdbuf()->sgetc();
				for (size_t _M = _R.size(); 0 < _M;
				_C = _I.rdbuf()->snextc(), --_M)
				{
					if (_C == EOF)
					{
						_St |= ios_base::eofbit;
						break;
					}
					else if (_C != '0' && _C != '1')
						break;
					else if (_X.max_size() <= _X.size())
					{
						_St |= ios_base::failbit;
						break; 
					}
					else
						_X.append(1, (char)_C), _Chg = true; 
				}
				_CATCH_IO_(_I); 
		}
		if (!_Chg)
			_St |= ios_base::failbit;
		_I.setstate(_St);
		_R = _X;
		return (_I);
	}


private:
	// 1 (01) (1=0) = 00 (11)
	// 01 (101) (01=1) =  000 (111)
	

	void set_unset_bit(_INDEX bit,bool retype=true){
	if (retype)
		{
			switch (m_type)
			{

			case BS_FULL:
				if ( m_len > _N - ((_N/8)/sizeof(_DATA)))
				{
					make_sparse();
				}
				else if(m_len -1  > ((_N/8)/sizeof(_DATA)))
				{
					make_normal();
				}
				break;
			case BS_NORMAL:
				{
					static int check =0;
					check++;
					if (check & CMJBITSET_CHECK_NORMAL_MASK == CMJBITSET_CHECK_NORMAL_MASK)
					{
						std::bitset<_N> *pL = (std::bitset<_N> *)m_pData;
			
						_INDEX count = pL->count();
						if (count - 1 < ((_N/8)/sizeof(_DATA)))
						{
							make_sparse();
						}
						else if (count > _N - ((_N/8)/sizeof(_DATA)))
						{

							make_full();
						}
			

					}


				}
				break;
			case BS_SPARSE:
				{
				if (m_len != _N-1 && m_len > _N - ((_N/8)/sizeof(_DATA)))
				{
					make_full();
				}
				else if(m_len != _N-1 && m_len +1  > ((_N/8)/sizeof(_DATA)))
				{
					make_normal();
				}
				break;	


				}

			}

		}

		switch (m_type)
		{

		case BS_SPARSE:
			{
			_INDEX pos = 0;
			_INDEX prevpos = 0;
			_INDEX i = 0;	

			if (m_len == _N -1)
			{
				m_len = _N;
			}
			else
			{
				while (i < m_len)
				{
					if (bit <= pos + m_pData[i] )
					{
						allocate(m_len +1);
						memmove(&m_pData[i+1], &m_pData[i], (m_len -1 - i) * sizeof(_DATA));
						m_pData[i] = bit - pos ;
						m_pData[i+1] = m_pData[i+1] + pos - bit -1;
						_ASSERT(test(bit));


						return;

					}
					pos += m_pData[i++] +1;
		
				}
	
				allocate(m_len +1);
				m_pData[m_len-1] = bit - pos;
			}
			break;
			}
		case BS_NORMAL:
			((std::bitset<_N> *)m_pData)->set(bit);
			break;

		case BS_FULL:
			{
				if (m_len == 0)
				{
					m_type = BS_SPARSE;
					allocate(1);
					m_pData[0]= bit;
				}
				else
				{
					_INDEX pos = 0;
					_INDEX i = 0;
					do{

						pos += m_pData[i];
			
						if (pos == bit)
						{
							_INDEX offset = m_pData[i];
							m_len--;
							memmove(&m_pData[i],&m_pData[i+1],(m_len -i) * sizeof(_DATA) );
							m_pData[i] += offset+1;
							return;
						}
						_ASSERT(pos < bit);
						pos++;
						i++;
						_ASSERT(i < _N);
					
					}while(1);
				}
			


			break;
			}
		}


		_ASSERT(test(bit));
		
	}


	void reset_normal_type()
	{

		static int check=0;
		if (m_type == BS_NORMAL)
		{
			check++;
			if ((check & CMJBITSET_CHECK_NORMAL_MASK) == CMJBITSET_CHECK_NORMAL_MASK)
			{
					std::bitset<_N> *pL = (std::bitset<_N> *)m_pData;
			
					_INDEX count = pL->count();
					if (count < ((_N/8)/sizeof(_DATA)))
					{
						make_sparse();
					}
					else if (count > _N - ((_N/8)/sizeof(_DATA)))
					{
						make_full();
					}
			}
		}
	}

	// 01 (101) 0 = 2 (001)

	void reset_set_bit(_INDEX bit, bool retype = true){

		if (retype)
		{
			switch (m_type)
			{

			case BS_FULL:
				if (m_len != _N - 1 && m_len > _N - ((_N/8)/sizeof(_DATA)))
				{
					make_sparse();
				}
				else if(m_len != _N - 1 && m_len +1  > ((_N/8)/sizeof(_DATA)))
				{
					make_normal();
				}
				break;
			case BS_NORMAL:
				{
					static int check =0;
					check++;
					if ((check & CMJBITSET_CHECK_NORMAL_MASK) == CMJBITSET_CHECK_NORMAL_MASK)
					{
						std::bitset<_N> *pL = (std::bitset<_N> *)m_pData;
			
						_INDEX count = pL->count();
						if (count - 1 < ((_N/8)/sizeof(_DATA)))
						{
							make_sparse();
						}
						else if (count > _N - ((_N/8)/sizeof(_DATA)))
						{

							make_full();
						}
			

					}


				}
				break;
			case BS_SPARSE:
				{
				if ( m_len > _N - ((_N/8)/sizeof(_DATA)))
				{
					make_full();
				}
				else if(m_len -1  > ((_N/8)/sizeof(_DATA)))
				{
					make_normal();
				}
				break;	


				}

			}

		}

		switch (m_type)
		{
		case BS_SPARSE:
			if (m_len == _N)	
			{
				allocate(_N -1);
				memset((void *)(m_pData ), 0, (_N -1) * sizeof(_DATA));
				m_pData[bit] = 1;
				//_ASSERT(!test(bit));
			}
			else
			{
				_INDEX pos = 0;
				_INDEX i = 0;
				do{
					pos += m_pData[i];
			
					if (pos == bit)
					{
						_INDEX offset = m_pData[i];
						m_len--;
						memmove(&m_pData[i],&m_pData[i+1],(m_len -i) * sizeof(_DATA) );
						m_pData[i] += offset+1;
						return;
					}
					_ASSERT(pos < bit);
					pos++;
					i++;
					_ASSERT(i < _N);

				}while(1);
			}
			break;
		case BS_NORMAL:
			{
				((std::bitset<_N> *)m_pData)->set(bit,0);
				break;

			}
		case BS_FULL:

			{
			_INDEX pos = 0;
			_INDEX prevpos = 0;
			_INDEX i = 0;	

			if (m_len == _N -1)
			{
				m_len = _N;
			}
			else
			{
				while (i < m_len)
				{
					if (bit <= pos + m_pData[i] )
					{
						allocate(m_len +1);
						memmove(&m_pData[i+1], &m_pData[i], (m_len -1 - i) * sizeof(_DATA));
						m_pData[i] = bit - pos ;
						m_pData[i+1] = m_pData[i+1] + pos - bit -1;
						_ASSERT(!test(bit));


						return;

					}
					pos += m_pData[i++] +1;
		
				}
	
				allocate(m_len +1);
				m_pData[m_len-1] = bit - pos;
			}
			break;
			}
		}
		_ASSERT(!test(bit));

	}
#ifdef DEBUG_CMJBITSET
	void check_heap() const
	{
		_ASSERTE(_CrtCheckMemory());
	
		if (m_pData != &m_Default[0])
		{
			_ASSERTE(_CrtIsValidHeapPointer(m_pData));
		}
	}
#endif

	void _Xinv() const
		{/*_THROW(invalid_argument("invalid CMJBitset<N> char"));*/ }
	void _Xoflo() const
		{/*_THROW(overflow_error(
			"CMJBitset<N> conversion overflow"));*/ }
	void _Xran() const
		{/*_THROW(out_of_range("invalid CMJBitset<N> position"));*/ }

};


#ifdef  _MSC_VER
#pragma pack(pop)
#endif  /* _MSC_VER */

#endif // !defined(AFX_MJBITSET_H__44E16525_5D70_4530_B0C1_5E90AAA4F4CA__INCLUDED_)

/*
 * 
 * Copyright (c) 2004 by MarsJupiter LTD.  ALL RIGHTS RESERVED
 * based on bitset
 * Copyright (c) 1994 by P.J. Plauger.  ALL RIGHTS RESERVED. 
 * Consult your license regarding permissions and restrictions.
 */