// bsymtree.cpp

// 

// Copyright (c) 2010 Accenture. All rights reserved.

// This component and the accompanying materials are made available

// under the terms of the "Eclipse Public License v1.0"

// which accompanies this distribution, and is available

// at the URL "http://www.eclipse.org/legal/epl-v10.html".

// 

// Initial Contributors:

// Accenture - Initial contribution

//

#include "bsymtree.h"

#include <badesca.h>

#include <fshell/descriptorutils.h>

//#include <e32debug.h>

using namespace LtkUtils;

RNode* RNode::NewL()

	{

	RNode* top = new(ELeave) RNode(0);

	CleanupDeletePushL(top);

	top->iPtr = new(ELeave) RArray<RNode*>(8);

	top->iHasChildArray = 1;

	CleanupStack::Pop(top);

	return top;

	}

RNode::RNode(char aLetter)

	: iLetter(aLetter), iHasChildArray(0), iPad(0), iPtr(NULL)

	{

	}

RNode* RNode::Sprog() const

	{

	ASSERT(!iHasChildArray);

	ASSERT(iLetter != 0);

	return reinterpret_cast<RNode*>(iPtr);

	}

RArray<RNode*>& RNode::Sprogs() const

	{

	ASSERT(iHasChildArray);

	return *reinterpret_cast<RArray<RNode*>*>(iPtr);

	}

RNode* RNode::ChildForLetter(char aChild) const

	{

	if (iHasChildArray)

		{

		const TInt count = Sprogs().Count();

		for (TInt i = 0; i < count; i++)

			{

			RNode* node = Sprogs()[i];

			if (node->iLetter == aChild) return node;

			}

		}

	else if (iLetter != 0) // null terminators use next for the value

		{

		RNode* child = Sprog();

		if (child && child->iLetter == aChild) return child;

		}

	return NULL;

	}

RNode* RNode::AddChildL(char aChild)

	{

	RNode* node = new(ELeave) RNode(aChild);

	CleanupStack::PushL(node);

	if (!iHasChildArray)

		{

		if (iPtr == NULL)

			{

			// Easy

			CleanupStack::Pop(node);

			iPtr = node;

			return node;

			}

		else

			{

			// Need to upgrade to a childArray

			RArray<RNode*>* children = new(ELeave) RArray<RNode*>(8);

			CleanupStack::PushL(children);

			children->AppendL(reinterpret_cast<RNode*>(iPtr));

			iPtr = children;

			CleanupStack::Pop(children);

			iHasChildArray = 1;

			}

		}

	Sprogs().AppendL(node);

	CleanupStack::Pop(node);

	return node;

	}

void RNode::InsertStringL(const TUint16* aString, TInt aValue)

	{

	char letter = (char)*aString;

	RNode* child = ChildForLetter(letter);

	if (!child)

		{

		child = AddChildL(letter);

		}

	if (letter == 0)

		{

		// If the letter was the null termination at the end, we're finished and just need to set the value

		//ASSERT(child->iPtr == NULL); // There should never be a child of a null terminator (unless the same string has been inserted twice...)

		// ^ Annoyingly there can be duplicate symbols that are only distinguished by information we've actually thrown away in the BSYM.

		//   We will ignore such duplicate symbols. If this is a problem, someone feel free to fix it.

		if (!child->iPtr)

			{

			child->iPtr = (TAny*)aValue;

			}

		}

	else

		{

		aString++;

		child->InsertStringL(aString, aValue);

		}

	}

RNode* RNode::WalkToEndOfString(TUint16*& aString)

	{

	RNode* currentNode = this;

	while (*aString)

		{

		RNode* child = currentNode->ChildForLetter((char)*aString);

		if (!child) return currentNode;

		currentNode = child;

		aString++;

		}

	return currentNode;

	}

RNode* RNode::TabFill(TUint16*& aString, const TUint16* aEnd)

	{

	// This function completes as far as the next choice point

	// aString is a pointer into a buffer with plenty of space in it

	//Dump(); // DEBUG

	if (!iHasChildArray && iLetter && iPtr && aString+1 < aEnd)

		{

		*aString = Sprog()->iLetter;

		aString++;

		*aString = 0;

		return Sprog()->TabFill(aString, aEnd);

		}

	else

		{

		return this;

		}

	}

void RNode::CompleteL(TDes& aPrefix, CDesC16Array& aResults)

	{

	TUint16* ptr = (TUint16*)aPrefix.PtrZ();

	TUint16* end = ptr + aPrefix.MaxLength();

	RNode* endNode = WalkToEndOfString(ptr);

	if (ptr != aPrefix.Ptr() + aPrefix.Length()) return; // We failed to walk the whole of the string so we have nothing to suggest (the string is longer than anything in the tree)

	endNode = endNode->TabFill(ptr, end);

	TInt newLen = ptr - aPrefix.Ptr();

	if (endNode->iLetter == 0 && newLen > 0) newLen--; // If ptr got as far as the null termination, we need to make our length one shorter

	//RDebug::Printf("Setting aPrefix len to %d, len=%d maxlen=%d", newLen, aPrefix.Length(), aPrefix.MaxLength());

	aPrefix.SetLength(newLen);

	// Now that aPrefix has been completed with as much as didn't have any choices, fill aResults with the choices

	RLtkBuf current;

	current.CreateLC(256);

	current.AppendL(aPrefix);

	if (current.Length()) current.SetLength(current.Length()-1); // Remove endNode's char as DoCompleteOptionsL expects to do that bit

	endNode->DoCompleteOptionsL(aResults, current);

	// Make sure last string is included

	aResults.AppendL(current);

	CleanupStack::PopAndDestroy(&current);

	aResults.Sort();

	}

void RNode::DoCompleteOptionsL(CDesC16Array& aResults, RLtkBuf& aCurrent)

	{

	if (iLetter)

		{

		aCurrent.ReserveExtraL(1);

		aCurrent.Append(TChar(iLetter));

		}

	TInt currentLen = aCurrent.Length();

	if (iHasChildArray)

		{

		for (int i = 0; i < Sprogs().Count(); i++)

			{

			RNode* child = Sprogs()[i];

			if (i > 0)

				{

				// A new prefix is in order

				aResults.AppendL(aCurrent);

				aCurrent.SetLength(currentLen);

				}

			child->DoCompleteOptionsL(aResults, aCurrent);

			}

		}

	else if (iLetter != 0)

		{

		if (Sprog()) Sprog()->DoCompleteOptionsL(aResults, aCurrent);

		}

	}

RNode::~RNode()

	{

	if (iHasChildArray)

		{

		RArray<RNode*>& children = Sprogs();

		const TInt count = children.Count();

		for (TInt i = 0; i < count; i++)

			{

			RNode* node = children[i];

			delete node;

			}

		children.Close();

		delete &children;

		}

	else if (iLetter != 0)

		{

		delete Sprog();

		}

	}

/*

#include <e32debug.h>

void RNode::Dump() const

	{

	TInt sprogCount = Sprogs().Count();

	for (int i = 0; i < sprogCount; i++)

		{

		RNode* child = Sprogs()[i];

		RDebug::Printf("Sprog %i is letter %c", i, child->iLetter);

		}

	}

*/

TInt RNode::ValueForStringL(const TDesC& aString) const

	{

	const RNode* node = this;

	for (TInt i = 0; i < aString.Length(); i++)

		{

		node = node->ChildForLetter(aString[i]);

		if (!node) User::Leave(KErrNotFound);

		}

	node = node->ChildForLetter(0); // The null terminator node is the one with the value in

	if (!node) User::Leave(KErrNotFound);

	ASSERT(!node->iHasChildArray);

	return reinterpret_cast<TInt>(node->iPtr);

	}