--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/libraries/ltkutils/src/bsymtree.cpp	Wed Jun 23 15:52:26 2010 +0100
@@ -0,0 +1,253 @@
+// 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);
+	}