/*TITLE dynamic hashing class implementation */

/****keyword-flag*** "%v %f %n" */
/* "14 21-May-98,19:17:26 DYNHASH.CPP" */

#include "common.h"
#include "crc32.h"

int DynamicHashString::s_ChainCount = 0;

DynamicHashString::DynamicHashString()
{
	m_Count = 0;
	m_Chain = 0;
}

ArrayIndex DynamicHashString::GetCount()
{
	return m_Count;
}

char DynamicHashString::GetChain()
{
	return m_Chain;
}

void DynamicHashString::SetChain()
{
	m_Chain = 1;
}

int DynamicHashString::GetChainCount()
{
	return s_ChainCount;
}

void DynamicHashString::BumpChainCount()
{
	s_ChainCount ++;
}

DynamicHashString::DynamicHashString(ModifiableElement p_Element)
{
	char *ElementPtr = (char *)p_Element.GetDataAddress();
	char *StartingElementPtr = ElementPtr;
	char *KeyStartingAddress;
	ArrayIndex TotalDataLength;

	// if there isn't any data in the ModifiableElement, done
	if (p_Element == "")
		{
		m_Count = 0;
		m_Chain = 0;
		return;
		}

	// set indicator as to whether this has a chain

	m_Chain = *(char *)ElementPtr;
	ElementPtr += sizeof(char);

	// if there aren't any elements in the ModifiableElement, done
	
	m_Count = *(ArrayIndex *)ElementPtr;
	if (m_Count == 0)
		return;

	// Calculate address of key length vector
	ElementPtr += sizeof(m_Count);

	// Set up SVector of key lengths
	m_KeyLength = SVector<ArrayIndex>(m_Count, (ArrayIndex *)ElementPtr);

	// Calculate address of data offset vector
	ElementPtr += m_Count * sizeof(ArrayIndex);

	// Set up vector of data offsets
	m_DataOffset = SVector<ArrayIndex>(m_Count, (ArrayIndex *)ElementPtr);

	// Calculate address of beginning of string area
	ElementPtr += m_Count * sizeof(ArrayIndex);

	// The keys start after the header
	KeyStartingAddress = ElementPtr;

    // Set up vector of keys
	m_Key = SVector<AccountNumber>(m_Count);
	ArrayIndex i;
	ArrayIndex KeyOffset = KeyStartingAddress - StartingElementPtr;
	ArrayIndex CurrentKeyLength;
	for (i = 0; i < m_Count; i ++)
		{
		CurrentKeyLength = m_KeyLength[i];
		m_Key[i] = p_Element.Mid(KeyOffset,CurrentKeyLength);
		KeyOffset += CurrentKeyLength;
		ElementPtr += CurrentKeyLength;
		}

	ArrayIndex CurrentOffset = ElementPtr - StartingElementPtr;
	TotalDataLength = p_Element.GetSize() - CurrentOffset;

	m_Data = ModifiableElement(TotalDataLength,ElementPtr);
	}


DynamicHashString::operator ModifiableElement()
{
	ArrayIndex HeaderLength;
	ArrayIndex DataLength = 0;
	ModifiableElement TempValue;
	ArrayIndex CurrentKeyLength = 0;
	char *TempPtr;
	ArrayIndex i;
	ModifiableElement Result;

	// if there isn't anything in the element, return null string

	if (m_Count == 0)
		return ModifiableElement();

	// We have some data. Start by calculating length of header
	// this consists of:
	// the chain indicator
	// the count of elements
	// the offsets of the keys
	// the offsets of the data 
	
	HeaderLength = sizeof(m_Chain) + sizeof(m_Count) + m_Count *
		(sizeof(ArrayIndex) + sizeof(ArrayIndex));

	DataLength = m_Data.GetSize();

	ArrayIndex KeyLength = 0;
	for (i = 0; i < m_Count; i ++)
		KeyLength += m_Key[i].GetSize();

	TempValue.SetSize(HeaderLength+KeyLength+DataLength);

	TempPtr = (char *)TempValue.GetDataAddress();

	*(char *)TempPtr = m_Chain;
	TempPtr += sizeof(m_Chain);

	*(ArrayIndex *)TempPtr = m_Count;
	TempPtr += sizeof(m_Count);

	memcpy(TempPtr,m_KeyLength.GetDataAddress(),m_Count * sizeof(ArrayIndex));
	TempPtr += m_Count * sizeof(ArrayIndex);

	memcpy(TempPtr,m_DataOffset.GetDataAddress(),m_Count * sizeof(ArrayIndex));
	TempPtr += m_Count * sizeof(ArrayIndex);

	for (i = 0; i < m_Count; i ++)
		{
		ArrayIndex KeySize = m_KeyLength[i];
		memcpy(TempPtr,m_Key[i].GetDataAddress(),KeySize);
		TempPtr += KeySize;
		}

	memcpy(TempPtr,m_Data.GetDataAddress(),m_Data.GetSize());

	Result = ModifiableElement(TempValue.GetSize(),(char *)TempValue.GetDataAddress());

	return Result;
}


void DynamicHashString::AddElement(AccountNumber p_Key, ModifiableElement p_Element)
{
	ArrayIndex OldSize;
	ArrayIndex NewElementSize;
	ArrayIndex OldCount = m_Count;

	m_Count ++;

	m_Key.SetSize(m_Count);
	m_Key[OldCount] = p_Key;

	m_KeyLength.SetSize(m_Count);
	m_KeyLength[OldCount] = p_Key.GetSize();

	OldSize = m_Data.GetSize();
	m_DataOffset.SetSize(m_Count);
	m_DataOffset[OldCount] = OldSize;

	NewElementSize = p_Element.GetSize();
	m_Data.SetSize(OldSize+NewElementSize);
	memcpy((char *)m_Data.GetDataAddress()+OldSize,p_Element.GetDataAddress(),
	NewElementSize);
}

bool DynamicHashString::DeleteElement(AccountNumber p_Key)
{
	bool Found = false;
	ArrayIndex Where;
	char* To;
	char* From;
	ArrayIndex MoveLength;
	ArrayIndex DeletedLength;
	ArrayIndex i;

	for (Where = 0; Where < m_Count; Where ++)
		{
		if (m_Key[Where] == p_Key)
			{
			Found = true;
			break;
			}
		}

	if (Found == false) // none there yet
		return false;

	if (Where < m_Count-1) // not deleting the last one
		{
		char* DataStart = (char*)m_Data.GetDataAddress();
		To = DataStart+m_DataOffset[Where];
		From = DataStart+m_DataOffset[Where+1];
		MoveLength = m_Data.GetSize()-m_DataOffset[Where+1];
		memcpy(To,From, MoveLength);
		DeletedLength = From-To;
		}
	else // Deleting the last one
		{
		DeletedLength = m_Data.GetSize()-m_DataOffset[m_Count-1];
		}

	for (i = Where; i < m_Count-1; i ++)
		{
		m_Key[i] = m_Key[i+1];
		m_KeyLength[i] = m_KeyLength[i+1];
		m_DataOffset[i] = m_DataOffset[i+1] - DeletedLength;
		}

	m_Count --;

	m_Key.SetSize(m_Count);

	m_KeyLength.SetSize(m_Count);

	m_DataOffset.SetSize(m_Count);

	ArrayIndex OldSize = m_Data.GetSize();

	m_Data.SetSize(OldSize-DeletedLength);

	return true;
}

ModifiableElement DynamicHashString::GetSubString(ArrayIndex p_Index)
{
	if (p_Index < m_Count - 1)
		return m_Data.Mid(m_DataOffset[p_Index],m_DataOffset[p_Index+1]-m_DataOffset[p_Index]);
	else
		return m_Data.Mid(m_DataOffset[p_Index],m_Data.GetSize()-m_DataOffset[p_Index]);
}

ModifiableElement DynamicHashString::FindElement(AccountNumber p_Key)
{
	ArrayIndex i;

	for (i = 0; i < m_Count; i ++)
		{
		if (m_Key[i] == p_Key)
			return GetSubString(i);
		}

	return ModifiableElement();
}

DynamicHashArray::DynamicHashArray()
{
	m_ObjectNumber = 0;
	m_CurrentSlotCount = 0;
	m_CurrentMaxSlotCount = 0;
	m_ElementsBeforeExpansion = 0;
}

DynamicHashArray::~DynamicHashArray()
{
	ModifiableElement TempString;
	ModifiableElement OldString;
	char buf[30];

	OldString = GetString((unsigned long)-1);
	sprintf(buf,"%6u %6lu %6u",m_CurrentSlotCount, m_CurrentMaxSlotCount, m_ElementsBeforeExpansion);
	TempString = buf;
	if (OldString != TempString)
		PutString((unsigned long)-1,TempString);
}

DynamicHashArray::DynamicHashArray(QuantumFile *p_QF, ModifiableElement p_ArrayName)
{
	Open(p_QF, p_ArrayName);
}

void DynamicHashArray::Open(QuantumFile *p_QF, ModifiableElement p_ArrayName)
{
	ArrayIndex i;
	ModifiableElement TempString;

	m_ArrayName = p_ArrayName;
	m_QF = p_QF;
	m_MOA = MainObjectArrayPtr(m_QF);

	m_ObjectNumber = m_MOA->FindObjectByName(m_ArrayName);
	if (m_ObjectNumber == NoObject)
		{
		m_ObjectNumber = m_MOA->FindAvailableObject();
		m_MOA->CreateMainObject(m_ArrayName,m_ObjectNumber);
		m_CurrentSlotCount = InitCurrentSlotCount;
		m_CurrentMaxSlotCount = InitCurrentMaxSlotCount;
		m_ElementsBeforeExpansion = ElementsPerSlot * InitCurrentSlotCount;
		for (i = 0; i < m_CurrentSlotCount; i ++)
			PutString(i,TempString);
		PutString((unsigned long)-1,""); // clear parameter string
		}
	else
		{
		TempString = GetString((unsigned long)-1); // get parameter string
		m_CurrentSlotCount = (ArrayIndex)atol(TempString);
		m_CurrentMaxSlotCount = (Ulong)atol(TempString.Mid(7,7));
		m_ElementsBeforeExpansion = (ArrayIndex)atol(TempString.Mid(14,7));
		}
}

ArrayIndex DynamicHashArray::CalculateHash(AccountNumber p_Key)
{
	crc32 CRC;

	unsigned long Result;
	unsigned long HashNumber = 0;
	unsigned long TempHash = 0;
	ArrayIndex KeyLength;
	KeyLength = p_Key.GetSize();

	CRC.processBuffer((unsigned char*)p_Key.GetDataAddress(),KeyLength);
	HashNumber = CRC.get_result().crc;

	Result = HashNumber & (m_CurrentMaxSlotCount-1);
	if (Result >= m_CurrentSlotCount)
		Result -= m_CurrentMaxSlotCount/2;

	return (ArrayIndex)Result;
}

void DynamicHashArray::StoreElement(AccountNumber p_Key, ModifiableElement p_Element)
{
	ArrayIndex SlotNumber;
	DynamicHashString DHString;
	DynamicHashString BuddyString;
	DynamicHashString NewSlotString;
	ArrayIndex i;
	ArrayIndex BuddySlotNumber;
	ArrayIndex NewSlotNumber;
	AccountNumber AcctNumber;
	ModifiableElement Data;
	DynamicHashString TempString;
	bool Status = false;

	if (m_ElementsBeforeExpansion == 0)
		{
		if (m_CurrentSlotCount == UINT_MAX)
			exit(1); // should be an exception, but not yet
		if (m_CurrentSlotCount == m_CurrentMaxSlotCount)
			m_CurrentMaxSlotCount *= 2;
//		PutString(m_CurrentSlotCount,ModifiableElement());
		BuddySlotNumber = (ArrayIndex)(m_CurrentSlotCount - m_CurrentMaxSlotCount/2);
		NewSlotNumber = m_CurrentSlotCount;
		m_CurrentSlotCount ++;
		TempString = DynamicHashString(GetString(BuddySlotNumber));
//		PutString(BuddySlotNumber,ModifiableElement());
		for (i = 0; i < TempString.m_Count; i ++)
			{
			AcctNumber = TempString.m_Key[i];
			SlotNumber = CalculateHash(AcctNumber);
			if (SlotNumber == BuddySlotNumber)
				BuddyString.AddElement(AcctNumber, TempString.GetSubString(i));
			else if (SlotNumber == NewSlotNumber)
				NewSlotString.AddElement(AcctNumber, TempString.GetSubString(i));
			else
				qfassert(0); // should never happen
			}
		if (TempString.GetChain())
			{
			NewSlotString.SetChain();
			BuddyString.SetChain();
			BuddyString.BumpChainCount();
			}
		PutString(NewSlotNumber,NewSlotString);
		PutString(BuddySlotNumber,BuddyString);
		m_ElementsBeforeExpansion = ElementsPerSlot;
		}

	m_ElementsBeforeExpansion --;

	ArrayIndex Size;
	AccountNumber p_Temp = p_Key;
	char buf[10];

	Status = DeleteElement(p_Key); // get rid of old element
	if (p_Element == "") // if new element null, we are done
		return;

	for (i = 0; ; i ++)
		{
		SlotNumber = CalculateHash(p_Temp);
		DHString = DynamicHashString(GetString(SlotNumber));
		Size = ModifiableElement(DHString).GetSize();
		if (Size + p_Element.GetSize() < MaxItemSize)
			{
			DHString.AddElement(p_Temp, p_Element);
			PutString(SlotNumber,DHString);
			break;
			}
		else
			{
			DHString.SetChain();
			DHString.BumpChainCount();
			PutString(SlotNumber,DHString);
			sprintf(buf,"\f%d",i);
			p_Temp = p_Key + buf;
			p_Temp = p_Temp.Mid(0,p_Temp.GetSize()-1);
			}
		}


}

void DynamicHashArray::PutString(ArrayIndex p_Index, ModifiableElement p_Element)
{
	p_Index ++;
	qfassert(p_Index < m_MOA->GetMainObjectMaxElementCount(m_ObjectNumber));
	if (p_Index >= m_MOA->GetMainObjectElementCount(m_ObjectNumber))
		m_MOA->GrowMainObject(m_ObjectNumber,p_Index+1);

     m_MOA->PutElement(m_ObjectNumber,p_Index,p_Element);
}

ModifiableElement DynamicHashArray::GetString(ArrayIndex p_Index)
{
 	p_Index ++;
	qfassert(p_Index < m_MOA->GetMainObjectElementCount(m_ObjectNumber));
	return m_MOA->GetModifiableElement(m_ObjectNumber,p_Index);
}

bool DynamicHashArray::DeleteElement(AccountNumber p_Key)
{
	ArrayIndex SlotNumber;
	DynamicHashString DHString;
	bool Result;

	AccountNumber p_Temp = p_Key;
	char buf[10];

	for (int i = 0; ; i ++)
		{
		SlotNumber = CalculateHash(p_Temp);
		DHString = DynamicHashString(GetString(SlotNumber));
		Result = DHString.DeleteElement(p_Temp);
		if (Result == true)
			break;
		else if (DHString.GetChain() == 0)
			break;
		else
			{
			sprintf(buf,"\f%d",i);
			p_Temp = p_Key + buf;
			p_Temp = p_Temp.Mid(0,p_Temp.GetSize()-1);
			}
		}

//	if (Result == true)
		PutString(SlotNumber,DHString); // fix actual hash string

	return Result;
}

ModifiableElement DynamicHashArray::FindElement(AccountNumber p_Key)
{
	ArrayIndex SlotNumber;
	DynamicHashString DHString;
	ModifiableElement Result;

	AccountNumber p_Temp = p_Key;
	char buf[10];

	for (int i = 0; ; i ++)
		{
		SlotNumber = CalculateHash(p_Temp);
		DHString = DynamicHashString(GetString(SlotNumber));
		Result = DHString.FindElement(p_Temp);
		if (Result != "")
			break;
		else if (DHString.GetChain() == 0)
			break;
		else
			{
			sprintf(buf,"\f%d",i);
			p_Temp = p_Key + buf;
			p_Temp = p_Temp.Mid(0,p_Temp.GetSize()-1);
			}
		}

	return Result;
}

DynamicHashArrayRef::DynamicHashArrayRef(DynamicHashArray &p_DHA, AccountNumber p_DHAIndex)
 : m_DHA(p_DHA), m_DHAIndex(p_DHAIndex)
{
}

DynamicHashArrayRef &DynamicHashArrayRef::operator=(ModifiableElement p_ME)
{
	m_DHA.StoreElement(m_DHAIndex,p_ME);
	return *this;
}

DynamicHashArrayRef::operator ModifiableElement()
{
	return m_DHA.FindElement(m_DHAIndex);
}

DynamicHashArrayRef DynamicHashArray::operator[](AccountNumber p_AccountNumber)
{
	return DynamicHashArrayRef(*this, p_AccountNumber);
}

void DynamicHashString::DumpModifiableElement(ModifiableElement p_Element)
{
	char *ElementPtr = (char *)p_Element.GetDataAddress();
	char *StartingElementPtr = ElementPtr;
	char *KeyStartingAddress;
	ArrayIndex TotalDataLength;
	ArrayIndex HeaderLength;
	ArrayIndex Count;
	SVector<ArrayIndex> KeyLength;
	SVector<ArrayIndex> DataOffset;
	SVector<String> Key;
	ArrayIndex i;
	ArrayIndex j;
	ArrayIndex MaxKeyLength;
	char Chain;

	cout << endl;

	// if there isn't any data in the ModifiableElement, done
	if (p_Element.GetSize() == 0)
		{
		cout << "No data in element" << endl;
		Count = 0;
		return;
		}

	// set indicator as to whether this has a chain
	Chain = *(char *)ElementPtr;
	ElementPtr += sizeof(char);

	cout << "Number of subelements: ";

	// if there aren't any elements in the ModifiableElement, done
	
	Count = *(ArrayIndex *)ElementPtr;
	if (Count == 0)
		{
		cout << 0 << endl;
		return;
		}

	// We have some data. Start by calculating length of header
	// this consists of:
	// the count of elements
	// the lengths of the keys
	// the offsets of the data

	cout << Count << endl;

	cout << "Chain indicator: " << (int)Chain << endl;

	HeaderLength = sizeof(Chain) + sizeof(Count) + Count *
		(sizeof(ArrayIndex) + sizeof(ArrayIndex));

	// Calculate address of key length vector
	ElementPtr += sizeof(Count);

	cout << "Key length vector: " << endl;

	// Set up vector of key lengths
	KeyLength = SVector<ArrayIndex>(Count, (ArrayIndex *)ElementPtr);

	MaxKeyLength = 0;

	for (i = 0; i < Count; i ++)
		{
		cout << KeyLength[i] << " ";
		if (KeyLength[i] > MaxKeyLength)
			MaxKeyLength = KeyLength[i];
		}
	cout << endl;

	// Calculate address of data offset vector
	ElementPtr += Count * sizeof(ArrayIndex);

	cout << "Data offset vector: " << endl;

	// Set up vector of data offsets
	DataOffset = SVector<ArrayIndex>(Count, (ArrayIndex *)ElementPtr);

	for (i = 0; i < Count; i ++)
		cout << DataOffset[i] << " ";
	cout << endl;

	// Calculate address of beginning of string area
	ElementPtr += Count * sizeof(ArrayIndex);

	// The keys start after the header
	KeyStartingAddress = ElementPtr;

	cout << "Key vector: " << endl;

    // Set up vector of keys
	Key = SVector<AccountNumber>(Count);
	ArrayIndex KeyOffset = KeyStartingAddress - StartingElementPtr;
	ArrayIndex CurrentKeyLength;
	for (i = 0; i < Count; i ++)
		{
		CurrentKeyLength = KeyLength[i];
		Key[i] = p_Element.Mid(KeyOffset,CurrentKeyLength);
		KeyOffset += CurrentKeyLength;
		ElementPtr += CurrentKeyLength;
		}

	// display keys
	for (i = 0; i < Count; i ++)
		{
		String TempKey = Key[i];
		for (j = 0; j < TempKey.GetSize(); j ++)
			{
			cout << TempKey[j];
			}
		cout << " ";
		}
	cout << endl;
	cout << endl;

	// display data

	cout << "Data vector: " << endl;

	ArrayIndex DataStart = ElementPtr - StartingElementPtr;
	String TempKey;
	for (i = 0; i < Count; i ++)
		{
		if (i < Count - 1)
			TempKey = p_Element.Mid(DataOffset[i]+DataStart,DataOffset[i+1]-DataOffset[i]);
		else
			TempKey = p_Element.Mid(DataOffset[i]+DataStart,p_Element.GetSize()-(DataOffset[i]+DataStart));
		for (j = 0; j < TempKey.GetSize(); j ++)
			{
			cout << TempKey[j];
			}
		cout << endl;
		}
	cout << endl;
	cout << endl;

	TotalDataLength = ElementPtr - StartingElementPtr;
}