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

/**
 *	@file BitArray.cpp
 *	@author -tHE SWINe-
 *	@date 2005
 *	@brief Simple and fast bit array class
 *
 *	@date 2007-03-15
 *
 *	passed code revision
 *
 *	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
 *
 *	@date 2007-06-26
 *
 *	fixed some bugs in array reallocation using CBitArray::Extend and
 *	in array copy operator CBitArray::operator =
 *
 *	@date 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)
 *
 *	@date 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)
 *
 *	@date 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"

#if defined(_MSC_VER) && !defined(__MWERKS__) && !defined(for) && _MSC_VER <= 1200
#define for if(0) {} else for
#endif // _MSC_VER && !__MWERKS__ && !for && _MSC_VER <= 1200
// msvc 'for' scoping hack

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

CBitArray::CBitArray()
	:m_n_used_bits(0)
{}

CBitArray::CBitArray(size_t n_length_bits)
	:m_n_used_bits(0)
{
	Alloc(n_length_bits);
}

CBitArray::CBitArray(const CBitArray &r_other)
	:m_n_used_bits(0)
{
	if(!Alloc(r_other.n_Size())) {
		Resize(0); // to mark error
		return;
	}
	SetBuffer(r_other.n_Buffer_Size(), r_other.p_Buffer());
	// alloc and copy
}

void CBitArray::operator =(const CBitArray &r_other)
{
	if(!Alloc(r_other.n_Size())) {
		Resize(0);
		return;
	}
	SetBuffer(r_other.n_Buffer_Size(), r_other.p_Buffer());
	// alloc and copy
}

bool CBitArray::Alloc(size_t n_length_bits)
{
	size_t n_array_size = n_BufferSize_Units(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)
{
	size_t n_array_size = n_BufferSize_Units(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_min_capacity_bits)
{
	size_t n_array_size = n_BufferSize_Units(n_min_capacity_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()
{
	{
		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)
{
	std::swap(m_n_used_bits, r_other.m_n_used_bits);
	TBuffer::Swap(r_other);
}

void CBitArray::Set(bool b_value)
{
	memset(TBuffer::p_Data(), (b_value)? 0xff : 0x00, n_Buffer_Size());
}

void CBitArray::Clear()
{
	memset(TBuffer::p_Data(), 0x00, n_Buffer_Size());
}

void CBitArray::Raise()
{
	memset(TBuffer::p_Data(), 0xff, n_Buffer_Size());
}

void CBitArray::Invert()
{
	_NativeInt *p_data = p_Data();
	const _NativeInt *p_end = p_data + n_Buffer_Size() / unit_SizeBytes;
	for(; p_data != p_end; ++ p_data)
		*p_data ^= _NativeInt(-1);
	// invert the whole array
}

void CBitArray::Copy(size_t n_begin, size_t n_begin_src, size_t n_end_src, const CBitArray &r_array)
{
	_ASSERTE(&r_array != this); // maybe noone should call it like this
	if(&r_array == this) {
		Inplace_Copy(n_begin, n_begin_src, n_end_src);
		return;
	}
	// use inplace copy if copying within the same array

	r_array.Transform(n_begin_src, n_end_src, n_begin, *this, n_Identity);
	// use transform with identity for the job
}

void CBitArray::Inplace_Copy(size_t n_begin, size_t n_begin_src, size_t n_end_src)
{
	if(n_begin < n_begin_src) {
		// copy from the start (forward)
	} else if(n_begin > n_begin_src) {
		// copy from the end (reverse)
	}
}

bool CBitArray::Uninitialized_Gap(size_t n_begin, size_t n_size)
{
	if(m_n_used_bits < n_Max_Size() - n_size)
		return false;
	if(!Resize(m_n_used_bits + n_size))
		return false;
	// realloc

	Inplace_Copy(n_begin + n_size, n_begin, m_n_used_bits - n_size);
	// copy data

	return true;
}

bool CBitArray::Insert(size_t n_begin, size_t n_size, bool b_value)
{
	if(m_n_used_bits < n_Max_Size() - n_size)
		return false;
	if(!Resize(m_n_used_bits + n_size))
		return false;
	// realloc

	Inplace_Copy(n_begin + n_size, n_begin, m_n_used_bits - n_size);
	// copy data

	Set(n_begin, n_begin + n_size, b_value);
	// initialize with the new data

	return true;
}

bool CBitArray::Insert(size_t n_begin, size_t n_begin2, size_t n_end2, const CBitArray &r_array)
{
	if(!Uninitialized_Gap(n_begin, n_end2 - n_begin2))
		return false;
	Inplace_Copy(n_begin, n_begin2, n_end2);
	return true;
}

void CBitArray::Erase(size_t n_begin, size_t n_end)
{
	Inplace_Copy(n_begin, n_end, m_n_used_bits);
	m_n_used_bits -= n_end - n_begin;
}

void CBitArray::Erase(size_t n_index)
{
	Inplace_Copy(n_index, n_index + 1, m_n_used_bits);
	-- m_n_used_bits;
}

bool CBitArray::PushBack(bool b_value)
{
	if(m_n_used_bits == n_Max_Size())
		return false;
	if(!Resize(m_n_used_bits + 1))
		return false;
	// realloc

	Set(m_n_used_bits - 1, b_value);
	// set bit

	return true;
}

void CBitArray::ShiftLeft(size_t n_shift)
{
	if(n_shift >= m_n_used_bits)
		Clear(); // whole array shifted-out
	else {
		Inplace_Copy(0, n_shift, m_n_used_bits);
		Set(m_n_used_bits - n_shift, m_n_used_bits, false); // @t_odo - is this what i meant?
	}
}

void CBitArray::ShiftRight(size_t n_shift)
{
	if(n_shift >= m_n_used_bits)
		Clear(); // whole array shifted-out
	else {
		Inplace_Copy(n_shift, 0, m_n_used_bits - n_shift);
		Set(0, n_shift, false); // @t_odo - is this what i meant?
	}
}

bool CBitArray::operator +=(const CBitArray &r_array)
{
	return Insert(m_n_used_bits, 0, r_array.m_n_used_bits, r_array);
}

bool CBitArray::operator ==(bool b_value) const
{
	_NativeInt n_reference = (!b_value)? _NativeInt(0) : _NativeInt(-1);
	// 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
{
	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;
}

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;
		else if(*p_data > *p_data2)
			return false;
	}
	// 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;
		else if((*p_data & n_mask) > (*p_data2 & n_mask)) // needed in case sizes aren't equal
			return false;
	}
	// compare last partial element

	return n_Size() < r_array.n_Size();
}

void CBitArray::GetBuffer(size_t n_buffer_size, void *p_dest) const
{
	memcpy(p_dest, TBuffer::p_Data(), min(n_buffer_size, n_Buffer_Size()));
}

void CBitArray::SetBuffer(size_t n_buffer_size, const void *p_src)
{
	memcpy(TBuffer::p_Data(), p_src, min(n_buffer_size, n_Buffer_Size()));
}

#ifdef __LARGE_BIT_ARRAY__
CBitArray::size_t CBitArray::n_Max_Size()
#else // __LARGE_BIT_ARRAY__
size_t CBitArray::n_Max_Size()
#endif // __LARGE_BIT_ARRAY__
{
	return size_t(CMaxIntValue<size_t>::result());
}

/**
 *	@brief identity function for Copy_*() functions
 */
inline CBitArray::_NativeInt CBitArray::n_Identity(_NativeInt x)
{
	return x;
}

/**
 *	@return Returns number of data buffer elements where all bits are used.
 */
#ifdef __LARGE_BIT_ARRAY__
inline CBitArray::size_t CBitArray::n_WholeUnitsUsed() const
#else // __LARGE_BIT_ARRAY__
inline size_t CBitArray::n_WholeUnitsUsed() const
#endif // __LARGE_BIT_ARRAY__
{
	return m_n_used_bits >> index_Shift;
}

/**
 *	@return Returns number of data buffer elements where all bits are used.
 */
#ifdef __LARGE_BIT_ARRAY__
inline CBitArray::size_t CBitArray::n_WholeUnitsUsed(size_t n_bits_used)
#else // __LARGE_BIT_ARRAY__
inline size_t CBitArray::n_WholeUnitsUsed(size_t n_bits_used)
#endif // __LARGE_BIT_ARRAY__
{
	return n_bits_used >> index_Shift;
}

/**
 *	@return Returns true in case the last used buffer elements isn't fully used
 *		(only some of it's bits are used), otherwise returns false.
 *	@note This implies n_WholeUnitsUsed() == n_BufferSize_Units(m_n_used_bits) - 1.
 */
inline bool CBitArray::b_LastUnitUsedPartialy() const
{
	return (m_n_used_bits & index_Mask) != 0;
}

/**
 *	@return Returns true in case the last used buffer elements isn't fully used
 *		(only some of it's bits are used), otherwise returns false.
 *	@note This implies n_WholeUnitsUsed() == n_BufferSize_Units(m_n_used_bits) - 1.
 */
inline bool CBitArray::b_LastUnitUsedPartialy(size_t n_bits_used)
{
	return (n_bits_used & index_Mask) != 0;
}

/**
 *	@return Returns valid bit mask for the last buffer element,
 *		returns 0 in case b_LastUnitUsedPartialy() is false.
 */
inline CBitArray::_NativeInt CBitArray::n_LastUnitMask() const
{
	return (~_NativeInt(0)) << (unit_SizeBits - (m_n_used_bits & index_Mask)); // store bits with MSB being the first one
}

/**
 *	@return Returns valid bit mask for the last buffer element,
 *		returns 0 in case b_LastUnitUsedPartialy() is false.
 */
inline CBitArray::_NativeInt CBitArray::n_LastUnitMask(size_t n_bits_used)
{
	return (~_NativeInt(0)) << (unit_SizeBits - (n_bits_used & index_Mask)); // store bits with MSB being the first one
}

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