/*
								+----------------------------------+
								|                                  |
								|    ***  Bit array class   ***    |
								|                                  |
								|   Copyright © -tHE SWINe- 2005   |
								|                                  |
								|           BitArray.cpp           |
								|                                  |
								+----------------------------------+
*/

/*
 *	passed code revision at 2007-03-15
 *
 *	improved code to meet ÜberLame quality standards
 *	now using unsigned integers for lengths instead of signed
 *	made CBit owned by CBitArray (as was logical)
 *	fixed hack in constant bit access using operator []
 *	renamed CBitArray::Free() to CBitArray::Erase()
 *	CBitArray::operator ==() now returns wheter arrays are equal (bool)
 *	instead of integer equality sign which is now returned by CBitArray::n_Compare()
 *	added inequality comparison operators
 *	removed most of non-operator functions (Set_Bit_High() and Set_Bit_Low()
 *	remains only for preformance purposes)
 *	most stuff is now inline, the whole thing is significantly faster
 *
 *	2007-06-26
 *
 *	fixed some bugs in array reallocation using CBitArray::Extend and
 *	in array copy operator CBitArray::operator =
 *
 *	2007-03-04
 *
 *	changed integer types for more safety (now using uint32_t type as array
 *	base unit and unsigned long to store array length)
 *
 *	2008-12-28
 *
 *	exposed internal data buffer for easier and faster serialization
 *	fixed error which occured when copying bits from one array to another
 *	(CBit instances were copied, no array writes occured)
 *
 *	2009-04-23
 *
 *	motivation for writing this file:
 *		std::vector<bool> is troublesome and generally two considered options are
 *			to erase (not deprecate) it, or rename it
 *		std::vector<bool> doesn't offer access to it's data buffer
 *		std::vector<bool> doesn't offer Set_Bit_Low() and Set_Bit_High() functions,
 *			therefore theoretically offers lower reachable performance
 *
 *	added CBitArray::n_Capacity(), CBitArray::Reserve() functions for more efficient
 *	(re)allocation
 *
 *	renamed CBitArray::CBit to CBitArray::CBitReference
 *
 *	added CBitArray::CBitReference::Raise() and CBitArray::CBitReference::Clear()
 *	functions for more efficient writes to individual bits (note
 *	CBitArray::CBitReference::operator =(bool) contains branch, not present
 *	in either of above functions)
 *
 */

#include "NewFix.h"

#include "CallStack.h"
#include <vector>
#include <string.h>
#include <stdio.h>
#include "BitArray.h"
#include "MinMax.h"

/*
 *								=== CBitArray ===
 */

/*
 *	CBitArray::CBitArray(size_t n_length_bits)
 *		- default constructor with array length specifier
 *		- see CBitArray::n_Size()() to find out if there was enough memory
 */
CBitArray::CBitArray(size_t n_length_bits)
	:m_n_used_bits(0)
{
	Alloc(n_length_bits);
	// set array empty and alloc
}

/*
 *	bool CBitArray::Alloc(size_t n_length_bits)
 *		- allocates array to lenght n_length bits
 *		- original contents are erased
 *		- returns true on success, false on failure (not enough memory)
 */
bool CBitArray::Alloc(size_t n_length_bits)
{
	size_t n_array_size = n_UnitsUsed(n_length_bits);
	// calc necessary buffer length (round up)

	if(!TBuffer::Resize(n_array_size * unit_SizeBytes, false)) {
		m_n_used_bits = 0;
		return false;
	}
	// resize the buffer

	m_n_used_bits = n_length_bits;
	// remember new size

	return true;
}

/*
 *	bool CBitArray::Resize(size_t n_length_bits)
 *		- extends array to lenght n_length bits
 *		- returns true on success, false on failure (not enough memory)
 */
bool CBitArray::Resize(size_t n_length_bits)
{
	size_t n_array_size = n_UnitsUsed(n_length_bits);
	// calc necessary buffer length (round up)

	if(!TBuffer::Resize(n_array_size * unit_SizeBytes, true)) {
		m_n_used_bits = 0;
		return false;
	}
	// resize the buffer

	m_n_used_bits = n_length_bits;
	// remember new size

	return true;
}

/*
 *	bool CBitArray::Reserve(size_t n_length_bits)
 *		- extends bufer to total lenght n_length bits,
 *		  but does not change array length (changes capacity)
 *		- returns true on success, false on failure (not enough memory)
 */
bool CBitArray::Reserve(size_t n_length_bits)
{
	size_t n_array_size = n_UnitsUsed(n_length_bits);
	// calc necessary buffer length (round up)

	if(!TBuffer::Resize(n_array_size * unit_SizeBytes, true)) {
		m_n_used_bits = 0;
		return false;
	}
	// resize the buffer

	return true;
}

/*
 *	void CBitArray::Erase()
 *		- erase array, free it's memory
 */
void CBitArray::Erase()
{
	{
		TBuffer t_tmp;
		TBuffer::Swap(t_tmp);
	}
	// erase buffer data via swap with temp buffer, which is in turn destroyed

	m_n_used_bits = 0;
	// clear the array
}

/*
 *	void CBitArray::Swap(CBitArray &r_other)
 *		- swaps this array with r_t_other
 */
void CBitArray::Swap(CBitArray &r_other)
{
	std::swap(m_n_used_bits, r_other.m_n_used_bits);
	TBuffer::Swap(r_other);
}

/*
 *	bool CBitArray::operator =(bool b_value)
 *		- sets all bits in array to b_value
 *		- returns b_value
 */
bool CBitArray::operator =(bool b_value)
{
	memset(TBuffer::p_Data(), (b_value)? 0xff : 0x00, n_Buffer_Size());
	// set whole array to 0-s or 1-s, depending on b_value

	return b_value;
}

/*
 *	void CBitArray::Invert()
 *		- inverts all bits in the array
 */
void CBitArray::Invert()
{
	_NativeInt *p_data = p_Data();
	const _NativeInt *p_end = p_data + n_UnitsUsed();
	for(; p_data != p_end; ++ p_data)
		*p_data ^= _NativeInt(-1);
	// invert the whole array
}

/*
 *	bool CBitArray::operator =(const CBitArray &r_array)
 *		- copies r_array to this bit array
 *		- returns true if there was enough memory and array was successfully copied, otherwise false
 */
bool CBitArray::operator =(const CBitArray &r_array)
{
	if(!Alloc(r_array.n_Size()))
		return false;
	Set_Buffer(r_array.n_Buffer_Size(), r_array.p_Get_Buffer());
	// alloc and copy

	return true;
}

/*
 *	bool CBitArray::operator +=(const CBitArray &r_array)
 *		- array concatenation
 *		- return true in case there was enough memory and arrays
 *		  were concatenated, otherwise false
 */
bool CBitArray::operator +=(const CBitArray &r_array)
{
	size_t n_last_bit;
	if(!Resize((n_last_bit = n_Size()) + r_array.n_Size()))
		return false;
	// alloc

	_NativeInt *p_data = p_Data();
	const _NativeInt *p_data2 = r_array.p_Data();

	for(size_t i = 0, n = r_array.n_Size(); i < n;) {
		if(!(n_last_bit & index_Mask)) { // dest array aligned
			if(!(i & index_Mask)) { // source array aligned
				p_data[n_last_bit >> index_Shift] = p_data2[i >> index_Shift];
				i += unit_SizeBits;
				n_last_bit += unit_SizeBits;
			} else { // source array un-aligned
				unsigned long n_bits = unit_SizeBits - (i & index_Mask);
				// number of bits to copy

				p_data[n_last_bit >> index_Shift] = p_data2[i >> index_Shift] >> (i & index_Mask);
				i += n_bits;
				n_last_bit += n_bits;
			}
		} else { // dest array un-aligned
			if(!(i & index_Mask)) { // source array aligned
				unsigned long n_bits = /*unit_SizeBits -*/ (n_last_bit & index_Mask);
				// number of bits to copy

				p_data[n_last_bit >> index_Shift] &= (1 << (/*unit_SizeBits -*/ n_bits)) - 1;
				p_data[n_last_bit >> index_Shift] |= p_data2[i >> index_Shift] << (n_last_bit & index_Mask);

				i += n_bits;
				n_last_bit += unit_SizeBits - n_bits; // save 1 sub by reordering "unit_SizeBits - " part here
			} else { // source array un-aligned
				unsigned long n_bits = unit_SizeBits - (((i & index_Mask) < (n_last_bit & index_Mask))?
					(n_last_bit & index_Mask) : (i & index_Mask));
				// number of bits to copy

				p_data[n_last_bit >> index_Shift] &= (1 << (n_last_bit & index_Mask)) - 1;
				p_data[n_last_bit >> index_Shift] |= (p_data2[i >> index_Shift] >> (i & index_Mask)) <<
					(n_last_bit & index_Mask);

				i += n_bits;
				n_last_bit += n_bits;
			}
		}
	}

	return true;
}

/*
 *	bool CBitArray::operator ==(bool b_value) const
 *		- return true in case all bits in array are equal to b_value, otherwise false
 *		- always returns true for an empty array
 */
bool CBitArray::operator ==(bool b_value) const
{
	_NativeInt n_reference = (b_value)? ~_NativeInt(0) : _NativeInt(0);
	// get reference value

	const _NativeInt *p_data = p_Data();
	const _NativeInt *p_end = p_data + n_WholeUnitsUsed();
	// get interval of buffer, where all bits are used in each element

	for(; p_data != p_end; ++ p_data) {
		if(*p_data != n_reference)
			return false;
	}
	// compare full elements

	if(b_LastUnitUsedPartialy()) {
		_NativeInt n_mask = n_LastUnitMask();
		return (*p_data & n_mask) == (n_reference & n_mask);
	}
	// compare last partial element

	return true;
}

/*
 *	bool CBitArray::operator ==(const CBitArray &r_array) const
 *		- returns true in case array lengths and contents are equal, otherwise false
 */
bool CBitArray::operator ==(const CBitArray &r_array) const
{
	if(n_Size() != r_array.n_Size())
		return false;
	// compare sizes

	const _NativeInt *p_data = p_Data();
	const _NativeInt *p_data2 = r_array.p_Data();
	const _NativeInt *p_end = p_data + n_WholeUnitsUsed();
	// get interval of buffer, where all bits are used in each element

	for(; p_data != p_end; ++ p_data, ++ p_data2) {
		if(*p_data != *p_data2)
			return false;
	}
	// compare full elements
	
	if(b_LastUnitUsedPartialy()) {
		_NativeInt n_mask = n_LastUnitMask();
		return (*p_data & n_mask) == (*p_data2 & n_mask);
	}
	// compare last partial element

	return true;
}

/*
 *	int CBitArray::n_Compare(const CBitArray &r_array) const
 *		- aray comparison in strcmp() like fashion
 *		- compares bits in natural order, first bit decides
 *		- in case all bits are equal, compare lengths
 *		- returns 1 if this > r_array, 0 if this == r_array or -1 if this < r_array
 */
int CBitArray::n_Compare(const CBitArray &r_array) const
{
	size_t n_lesser_size = min(n_Size(), r_array.n_Size());
	// get size of lesser of two arrays

	const _NativeInt *p_data = p_Data();
	const _NativeInt *p_data2 = r_array.p_Data();
	const _NativeInt *p_end = p_data + n_WholeUnitsUsed(n_lesser_size);
	// get interval of buffer, where all bits are used in each element

	for(; p_data != p_end; ++ p_data, ++ p_data2) {
		if(*p_data != *p_data2)
			return (*p_data > *p_data2)? 1 : -1;
	}
	// compare full elements
	
	if(b_LastUnitUsedPartialy(n_lesser_size)) {
		_NativeInt n_mask = n_LastUnitMask(n_lesser_size);
		if((*p_data & n_mask) != (*p_data2 & n_mask))
			return ((*p_data & n_mask) > (*p_data2 & n_mask))? 1 : -1;
	}
	// compare last partial element

	return (n_Size() > r_array.n_Size())? 1 :
		((n_Size() == r_array.n_Size())? 0 : -1);
}

bool CBitArray::operator <(const CBitArray &r_array) const
{
	size_t n_lesser_size = min(n_Size(), r_array.n_Size());
	// get size of lesser of two arrays

	const _NativeInt *p_data = p_Data();
	const _NativeInt *p_data2 = r_array.p_Data();
	const _NativeInt *p_end = p_data + n_WholeUnitsUsed(n_lesser_size);
	// get interval of buffer, where all bits are used in each element

	for(; p_data != p_end; ++ p_data, ++ p_data2) {
		if(*p_data < *p_data2)
			return true;
	}
	// compare full elements
	
	if(b_LastUnitUsedPartialy(n_lesser_size)) {
		_NativeInt n_mask = n_LastUnitMask(n_lesser_size);
		if((*p_data & n_mask) < (*p_data2 & n_mask))
			return true;
	}
	// compare last partial element

	return (n_Size() < r_array.n_Size())? 1 : 0;
}

/**
 *	@brief copies internal data buffer
 *
 *	Fills p_data with data from intrernal buffer
 *
 *	@param p_data is pointer to destination buffer, it must be allocated
 *		to n_Buffer_Size() bytes
 *	@param n_size is size of p_data array, in bytes (for parameter validation only)
 */
void CBitArray::Get_Buffer(size_t n_size, void *p_data) const
{
	_ASSERTE(n_size == n_Buffer_Size());
	// this should be used to initialize the whole array, also there might be
	// endianness issues when using multi-byte type for array buffer

	memcpy(p_data, TBuffer::p_Data(), min(n_size, n_Buffer_Size()));
}

/*
 *	void CBitArray::Set_Buffer(size_t n_size, const void *p_data)
 *		- fills data buffer with data from p_data
 *		- note p_data must contain n_Buffer_Size() * sizeof(uint32_t) bytes
 */
void CBitArray::Set_Buffer(size_t n_size, const void *p_data)
{
	_ASSERTE(n_size == n_Buffer_Size());
	// this should be used to initialize the whole array, also there might be
	// endianness issues when using multi-byte type for array buffer

	memcpy(TBuffer::p_Data(), p_data, min(n_size, n_Buffer_Size()));
}

/*
 *	bool CBitArray::Store(FILE *p_fw) const
 *		- writes array to file p_fw (should be opened for writing in binary mode)
 *		- returns true if successful, otherwise false
 */
bool CBitArray::Store(FILE *p_fw) const
{
	return fwrite(&m_n_used_bits, sizeof(size_t), 1, p_fw) == 1 &&
	   fwrite(TBuffer::p_Data(), sizeof(uint8_t), n_Buffer_Size(), p_fw) == n_Buffer_Size();
}

/*
 *	bool CBitArray::Load(FILE *p_fr)
 *		- loads an array from file p_fr (should be opened for reading in binary mode)
 *		- returns true if successful, otherwise false
 */
bool CBitArray::Load(FILE *p_fr)
{
	unsigned long n_bits_used;
	return fread(&n_bits_used, sizeof(size_t), 1, p_fr) == 1 && Resize(n_bits_used) &&
		fread(TBuffer::p_Data(), sizeof(uint8_t), n_Buffer_Size(), p_fr) == n_Buffer_Size();
}

/*
 *								=== ~CBitArray ===
 */
