bitarray.cpp

The Bit Array structure provides a compacted arrays of Booleans, with one bit for each Boolean value

						else	if(nByte+2 < nSrcLen && src[nByte+1] == 0xff && *(COMPRESS_TYPE*)(src+nByte+2) != COMPRESS_COUNT)
						{	// increment next runlength only
							memmove(src+nByte, src+nByte+1, nSrcLen-nByte-1);
							src[--nSrcLen] = 0;
							*(COMPRESS_TYPE*)(src+nByte+2) += 1;
						}
						else
						{
							src = (BYTE*)ReAllocPtr(src, nSrcLen+COMPRESS_SIZE);
							memmove(src+nByte+1+COMPRESS_SIZE, src+nByte+1, nSrcLen-nByte-1);
							*(COMPRESS_TYPE*)(src+nByte+1) = 1;
							nSrcLen += COMPRESS_SIZE;
						}
					return true;
				}
				nByte++;
				byType = 0;
			}
	}
	bool bAlloc = nSrcLen == 0;
	int nLength = nDesByte-nDesLen;
 	int nRun = nLength/COMPRESS_COUNT+((nLength%COMPRESS_COUNT)?1:0);
	if(nRun > 0)
		nSrcLen += nRun*(1+COMPRESS_SIZE)+1;
	else
		nSrcLen++;
	if(bAlloc)
	{
		nSrcLen++;	// keep first byte for compression info
		src = (BYTE*)AllocPtr(nSrcLen);
		src[0] = 1;
	}
	else
		src = (BYTE*)ReAllocPtr(src, nSrcLen);
	while(nRun > 0)
		*(COMPRESS_TYPE*)(src+nSrcLen-(nRun--)*(1+COMPRESS_SIZE)) = (nLength>=COMPRESS_COUNT?COMPRESS_COUNT:nLength), nLength -= COMPRESS_COUNT;
	SetBit(src+nSrcLen-1, nBit&7);
	return true;
}

bool CBitArray::GetAt(BYTE *src, int nSrcLen, int nBit)
{
	int nDesLen = 0, nDesByte = nBit/8;
	if(nSrcLen > 0)
	{
		int nByte = 1, nRunLength = 0;
		while(nByte < nSrcLen)
			if(src[nByte] == 0 || src[nByte] == 0xff)
			{
				nRunLength = *(COMPRESS_TYPE*)(src+nByte+1);
				if(nDesLen+nRunLength > nDesByte)
					return src[nByte] == 0xff;
				nDesLen += nRunLength;
				nByte += COMPRESS_SIZE+1;
			}
			else
			{
				if(nDesLen++ == nDesByte)
					return GetBit(src+nByte, nBit&7);
				nByte++;
			}
	}
	return false;
}

int CBitArray::DecompressLength(BYTE *src, int nSrcLen)
{
	int nDesLen = 0, nByte = 0;
	while(nByte < nSrcLen)
		if(src[nByte] == 0 || src[nByte] == 0xff)
			nDesLen += *(COMPRESS_TYPE*)(src+(++nByte)), nByte += COMPRESS_SIZE;
		else
			nDesLen++, nByte++;
	return nDesLen;
}

int CBitArray::GetIndexBit(int nIndex)
{
	if(nIndex <= -1 || nIndex >= GetCount())
		return -1;
	if(m_nIndexes == NULL)
		Index();

	int nMapIndex = nIndex / m_nBitSeg;
	if(nMapIndex >= m_nIndexesCount)
		return -1;
	if(m_nBitSeg == 1)
		return m_nIndexes[nIndex];
	int dwBitmapIndex = m_nIndexes[nMapIndex];
	int lReminder = nIndex % m_nBitSeg, nMaxBit = GetLength()<<3;
	while(lReminder > 0)
	{
		if(++dwBitmapIndex >= nMaxBit)
			return -1;
		if(GetAt(dwBitmapIndex))
			--lReminder;
	}
	return dwBitmapIndex;
}

int CBitArray::GetBitIndex(int nBit)
{
	if(GetCount() == 0)
		return -1;
	if(m_nIndexes == NULL)
		Index();

	int nStart = 0, nEnd = m_nIndexesCount, nMapIndex = 0;
	while(nStart < nEnd)
	{
		nMapIndex = (nEnd+nStart)/2;
		if(nBit == m_nIndexes[nMapIndex])
			break;
		if(nBit < m_nIndexes[nMapIndex])
			nEnd = nMapIndex-1;
		else
			nStart = nMapIndex+1;
	}
	while(nMapIndex > 0 && nBit < m_nIndexes[nMapIndex])
		nMapIndex--;
	
	int nBitIndex = nMapIndex*m_nBitSeg;
	for(int dwCount = m_nIndexes[nMapIndex]; dwCount < nBit; dwCount++)
		if(GetAt(dwCount))
			nBitIndex++;
	if(GetAt(nBit) == FALSE)
		nBitIndex--;

	return nBitIndex;
}

void CBitArray::Init(BYTE* pBuffer, int nLength)
{
	FreeBuffer();
	m_nLength = m_nAllocLength = nLength;
	if(nLength > 0)
	{
		m_pBuffer = (BYTE*)AllocPtr(nLength);
		memcpy(m_pBuffer, pBuffer, nLength);
		while(m_nLength  && m_pBuffer[m_nLength-1] == 0)
			m_nLength--;
	}
	m_bModified = true;
}

void CBitArray::operator=(const CBitArray& src)
{
	Init(src.m_pBuffer, src.m_nLength);
	m_nCount = src.m_nCount;
	if(src.m_nIndexes)
	{
		m_nIndexesCount = src.m_nIndexesCount;
		m_nIndexes = (int*)malloc(m_nIndexesCount*sizeof(DWORD));
		memcpy(m_nIndexes, src.m_nIndexes, m_nIndexesCount*sizeof(DWORD));
		m_nBitSeg = src.m_nBitSeg;
	}
	m_bModified = true;
}

void CBitArray::operator|=(const CBitArray& src)
{
	if(m_nLength < src.m_nLength)
		SetLength(src.m_nLength);
	for(int nByte = 0; nByte < src.m_nLength; nByte++)
		m_pBuffer[nByte] |= src.m_pBuffer[nByte];
	SetModified();
}

void CBitArray::operator&=(const CBitArray& src)
{
	m_nLength = min(m_nLength, src.m_nLength);
	for(int nByte = 0; nByte < m_nLength; nByte++)
		m_pBuffer[nByte] &= src.m_pBuffer[nByte];
	while(m_nLength  && m_pBuffer[m_nLength-1] == 0)
		m_nLength--;
	if(m_nLength == 0)
		FreeBuffer();
	SetModified();
}

void CBitArray::operator^=(const CBitArray& src)
{
	if(m_nLength < src.m_nLength)
		SetLength(src.m_nLength);
	for(int nByte = 0; nByte < src.m_nLength; nByte++)
		m_pBuffer[nByte] ^= src.m_pBuffer[nByte];
	SetModified();
}

bool CBitArray::operator==(const CBitArray& src)
{
	return m_nLength == src.m_nLength && memcmp(m_pBuffer, src.m_pBuffer, m_nLength) == 0;
}

bool CBitArray::operator!=(const CBitArray& src)
{
	return m_nLength != src.m_nLength || memcmp(m_pBuffer, src.m_pBuffer, m_nLength) != 0;
}

bool CBitArray::operator&&(const CBitArray& src)
{
	int nLength = min(m_nLength, src.m_nLength);
	for(int nByte = 0; nByte < nLength; nByte++)
		if((m_pBuffer[nByte] & src.m_pBuffer[nByte]) != 0)
			return true;
	return false;
}

CBitArray CBitArray::operator&(const CBitArray& src)
{
	CBitArray bitArray = *this;
	bitArray &= src;
	return bitArray;
}

CBitArray CBitArray::operator|(const CBitArray& src)
{
	CBitArray bitArray = *this;
	bitArray |= src;
	return bitArray;
}

CBitArray CBitArray::operator^(const CBitArray& src)
{
	CBitArray bitArray = *this;
	bitArray ^= src;
	return bitArray;
}

bool CBitArray::IsEmpty()
{
	if(m_nLength == 0)
		return true;
	if(m_nCount > 0)
		return false;
	for(int nByte = 0; nByte < m_nLength; nByte++)
		if(m_pBuffer[nByte])
			return false;
	return true;
}

bool CBitArray::IsRangeEmpty(int nStartBit, int nEndBit)
{
	if(m_nLength == 0)
		return true;
	if(nEndBit >= m_nLength*8)
		nEndBit = m_nLength*8-1;
	for(int dwBit = nStartBit; dwBit < (nStartBit/8+1)*8; dwBit++)
		if(GetAt(dwBit))
			return false;
	for(int nByte = nStartBit/8+1; nByte < nEndBit/8; nByte++)
		if(m_pBuffer[nByte])
			return false;
	if((nEndBit+1)&7)
		for(dwBit = nEndBit/8*8; dwBit <= nEndBit; dwBit++)
			if(GetAt(dwBit))
				return false;
	return true;
}

void CBitArray::Invert(int nMaxBits)
{
	SetModified();

	m_nLength = (nMaxBits+7)/8;
	if(m_nLength > m_nAllocLength)
	{
		m_nAllocLength = m_nLength;
		if(m_pBuffer == NULL)
			m_pBuffer = (BYTE*)AllocPtr(m_nAllocLength);
		else
			m_pBuffer = (BYTE*)ReAllocPtr(m_pBuffer, m_nAllocLength);
	}
	for(int nByte = 0; nByte < m_nLength; nByte++)
		m_pBuffer[nByte] = ~m_pBuffer[nByte];
	for(int nBit = nMaxBits; nBit < m_nLength*8; nBit++)
		ResetBit(m_pBuffer, nBit);
}

void CBitArray::SetModified()
{
	m_nCount = -1;
	if(m_nIndexes)
		free(m_nIndexes);
	m_nIndexes = NULL;
	m_bModified = true;
}

void CBitArray::Delete(int nStart, int nEnd)
{
	int nMaxBits = m_nLength*8;
	if(nStart >= nMaxBits || nStart > nEnd)
		return;
	nEnd = min(nEnd, nMaxBits-1);
	ResetRange(nStart, nEnd);
	for(int nIndex = nEnd+1; nIndex < nMaxBits; nIndex++)
		if(GetAt(nIndex))
		{
			ResetAt(nIndex);
			SetAt(nStart+nIndex-(nEnd+1));
		}
		else
			ResetAt(nStart+nIndex-(nEnd+1));
	m_bModified = true;
	nMaxBits = max(0, nMaxBits -(nEnd-nStart+1));
	m_nLength = nMaxBits/8 + ((nMaxBits%8)?1:0);
	for(nIndex = nMaxBits; nIndex < nMaxBits+(8-nMaxBits%8); nIndex++)
		ResetBit(m_pBuffer, nIndex);
}

void CBitArray::Insert(int nStart, int nCount, bool bSet)
{
	int nMaxBits = m_nLength*8;
	int lOldMaxBits = nMaxBits;
	SetLength(nMaxBits+nCount+max(0, nStart-nMaxBits));
	for(int nIndex = lOldMaxBits-1; nIndex > nStart; nIndex--)
		if(GetBit(m_pBuffer, nIndex))
		{
			ResetBit(m_pBuffer, nIndex);
			SetBit(m_pBuffer, nIndex+nCount);
		}
	if(bSet)
		SetRange(nStart+1, nStart+nCount);
	else
		ResetRange(nStart+1, nStart+nCount);
}

int CBitArray::GetHeadBit()
{
	return GetIndexBit(0);
}

int CBitArray::GetTailBit()
{
	return GetIndexBit(GetCount()-1);
}

int CBitArray::GetActualBit(int dwIndexBit)
{
	if(GetAt(dwIndexBit))
		return dwIndexBit;
	int nIndex = GetBitIndex(dwIndexBit);
	if(nIndex == 0)
		return GetHeadBit();
	if(nIndex == GetCount())
		return GetTailBit();
	return GetIndexBit(nIndex);
}

int CBitArray::Bmp2Array(int *&pBuffer, bool bAllocated /*= false*/)
{
	int nCount = GetCount();
	if(nCount == 0)
		return 0;
	if(bAllocated == false)
		pBuffer = (int*)AllocPtr(sizeof(int)*nCount);
	nCount = 0;
	BYTE by;
	for(int nBit, nByte = 0; nByte < m_nLength; nByte++)
		if(by = m_pBuffer[nByte])
		{
			nBit = nByte<<3;
			while(by)
			{
				if(by&1)
					pBuffer[nCount++] = nBit;
				by >>= 1, nBit++;
			}
		}
	return nCount;
}

int CBitArray::Bmp2Array(vector<int> &nArray)
{
	nArray.resize(GetCount());
	return Bmp2Array((int*&)*nArray.begin(), true);
}

void CBitArray::Append2Array(vector<int> &nArray)
{
	int nArraySize = nArray.size();
	nArray.resize(nArraySize+GetCount());
	BYTE by;
	for(int nBit, nByte = 0; nByte < m_nLength; nByte++)
		if(by = m_pBuffer[nByte])
		{
			nBit = nByte<<3;
			while(by)
			{
				if(by&1)
					nArray[nArraySize++] = nBit;
				by >>= 1, nBit++;
			}
		}
}

int CBitArray::Range2Array(int nStartBit, int nEndBit, vector<int> &nArray)
{
	if(nStartBit >= m_nLength*8)
		return 0;
	nEndBit = min(nEndBit, m_nLength*8-1);

	int nCount = 0, nBit;
	BOOL bFirstByte = (nStartBit&7) != 0;
	if(bFirstByte)
		for(nBit = nStartBit; nBit < (nStartBit/8+1)*8; nBit++)
			if(GetAt(nBit))
				nArray.push_back(nBit), nCount++;
	int nEndByte = nEndBit/8;
	BYTE by;
	for(int nByte = nStartBit/8+bFirstByte; nByte < nEndByte; nByte++)
		if(by = m_pBuffer[nByte])
		{
			nBit = nByte<<3;
			while(by)
			{
				if(by&1)
					nArray.push_back(nBit), nCount++;
				by >>= 1, nBit++;
			}
		}
	for(nBit = nEndByte*8; nBit <= nEndBit; nBit++)
		if(GetAt(nBit))
			nArray.push_back(nBit), nCount++;
	return nCount;
}