libsst/Include/ZUtil/ZKVTree.hpp

		/*
	ZKVTree.hpp
	Author: James Russell <jcrussell@762studios.com>
	Created: 3/22/2012

	Purpose:	
	
	ZKVTree defines a KV-Tree that uses strings as both keys and values.  The model
	supported is hierarchical with no nesting limit, and individual nodes can be addressed
	directly or the tree can be iterated.  This makes ZKVTree's typical use case as an
	in memory representation of hierarchical text formats such as XML and JSON, and can 
	be used for simpler formats such as INI.  When the layout and keys are known 
	(such as with most INI files), lookup via path string is the easiest route.  When the layout 
	is not known (such as with an XML file with variable numbers of children and attributes),
	then iteration is the preferred method of getting access to the data.
	
	Multiple nodes of the same name existing at the same level in the tree is supported.  
	When a path is given that does not contain the number, then it is assumed to be 
	referencing the first sibling node at that location (index 0). 

	Unnamed tree nodes are supported, with the key used to access those being omitted from the 
	path string but the subscript being required.

	If the tree has	the following layout, with the values at each node contained 
	in parenthesis:

	Root
	|
	+-> A (0)
	|   |
	|   +-> B (8)
	|   |   |
	|   |   +-> c (16)
	|   |   +-> c (32)
	|	|	+->   (100)
	|	|	+->   (200)
	|   |
	|   +-> B (8)
	|   |   |
	|   |   +-> c (64)
	|   |   +-> d (128)
	|	|	+->   (10)
	|	|	+->   (20)
	|   |
	|   +-> b (5)
	|   +-> b (10)
	|   +-> c (15)
	|   +-> d (20)
	|
	+-> B (8)
	|   |
	|   +-> c (50)
	|   +-> d (100)
	|
	+-> a (1)
	+-> a (2)
	+-> a (3)
	+-> b (4)

	Then valid path strings include (but are not limited to): 

	A.B			- would get the value of node 'B[0]' (8) with parent node 'A[0]'
	A.B.c		- would get the value of node 'c[0]' (16) with parent node 'A[0].B[0]'
	A.B.c[1]	- would get the value of node 'c[1]' (32) with parent node 'A[0].B[0]'
	A.B[1].c	- would get the value of node 'c[0]' (64) with parent node 'A[0].B[1]'
	A.B[1].c[1]	- would get the value of node 'c[1]' (128) with parent node 'A[0].B[1]'
	A.b[1]		- would get the value of node 'b[1]' (10) with parent node 'A[0]'
	B.c			- would get the value of node 'c[0]' (50) with parent node 'B[0]'
	a			- would get the value of node 'a[0]' (1) with root parent node ''
	a[2]		- would get the value of node 'a[2]' (3) with root parent node '' 

	If this KVTree were to be iterated using ZKVTree::Iterator::Next(), a depth first 
	traversal of the structure would take place, giving us the following order:

	A
	A.B[0]
	A.B[0].c[0]
	A.B[0].c[1]
	A.B[0].[0]
	A.B[0].[1]
	A.B[1].c
	A.B[1].d
	A.B[1].[0]
	A.B[1].[1]
	A.b[0]
	A.b[1]
	A.c
	A.d
	B
	B.c
	B.d
	a[0]
	a[1]
	a[2]

    A special syntax for accessing unnamed children is supported, which enables nested array behavior
	for values:

	A.B[0][0]	- would get the value of (unnamed) node '[0]' (100) with parent node 'A.B[0]'
    A.B[1][0]   - would get the value of (unnamed) node '[0]' (10) with parent node 'A.B[0]'
	A.B[1][1]	- would get the value of (unnamed) node '[1]' (20) with parent node 'A.B[1]'

	Note that these are syntactic sugar for:

	A.B[0].[0]  (could also be expressed as A.B[0]. or A.B. due to the implicit [0])
	A.B[1].[0]	(could also be expressed as A.B[1]. due to the implicit [0])
	A.B[1].[1]

	License: 

	TODO
*/

#ifndef _ZREGISTRY_H
#define _ZREGISTRY_H

#include <SST/SST_Hash.h>

#include <ZSTL/ZHashMap.hpp>
#include <ZSTL/ZString.hpp>
#include <ZSTL/ZBasicStringAlgo.hpp>

#include <ZUtil/ZConcurrency.hpp>
#include <ZUtil/ZSlabAllocator.hpp>

#include <stdarg.h>

//Valid path separator for ZKVTree
#ifndef ZKVTREE_PATH_SEPARATOR
#define ZKVTREE_PATH_SEPARATOR		'.'
#endif

//Default number of nodes preallocated
#ifndef ZKVTREE_NODE_COUNT
#define ZKVTREE_NODE_COUNT			(128)
#endif

//Invalid characters for a path ([] valid on subscript only)
#define ZKVTREE_INVALID_PATH_CHARS	"%[]"

/*
ZKVTree class.
*/
class ZKVTree
{
public:
	//KVTree node structure
	struct Node
	{
		ZString Name;				//Name of the node
		ZString Value;				//Value held by this node
		Node*   ParentNode;			//Pointer to our parent node
		size_t  Index;				//Index of this node in the parent's children array
		ZArray< Node* > Children;	//Children of this node

		//Determines if this is the root node
		bool IsRootNode() const {
			if (ParentNode == NULL) {
				return true;
			} else return false;
		}

		//Finds the node with the given name in the child array
		Node* GetChildByName(const ZString& _name, size_t _start, size_t _end, size_t _subscript) const {
			for (size_t i = 0; i < Children.Size(); i++) {
				Node* child = Children.Data()[i];
				if (child->Name.Length() == (_end - _start)) {
					if (ZStringAlgo::Equal(child->Name, 0, child->Name.Length(), _name, _start, _end)) {
						if (_subscript-- == 0) {
							return child;
						}
					}
				}
			}
			return NULL;
		}

		//Finds the number of children with the given name
		size_t GetChildCountByName(const ZString& _name, size_t _start, size_t _end) const {
			size_t num = 0;
			for (size_t i = 0; i < Children.Size(); i++) {
				Node* child = Children.Data()[i];
				if (child->Name.Length() == (_end - _start)) {
					if (ZStringAlgo::Equal(child->Name, 0, child->Name.Length(), _name, _start, _end)) {
						num++;
					}
				}
			}
			return num;
		}

		//Finds the index of the last occurrence of a node with the given name
		size_t GetLastIndexByName(const ZString& _name, size_t _start, size_t _end) const {
			size_t idx = 0;
			for (size_t i = 0; i < Children.Size(); i++) {
				Node* child = Children.Data()[i];
				if (child->Name.Length() == (_end - _start)) {
					if (ZStringAlgo::Equal(child->Name, 0, child->Name.Length(), _name, _start, _end)) {
						idx = i;
					}
				}
			}
			return idx;
		}

		//Gets the path to this node
		void GetPath(ZString& _out, Node* _end = NULL) const {
			if (this != _end && ParentNode != NULL) {
				ParentNode->GetPath(_out, _end);
			} else return;

			if (!_out.Empty()) {
				_out.PushBack(ZKVTREE_PATH_SEPARATOR);
			}

			if (!IsRootNode()) {
				size_t siblings = ParentNode->GetChildCountByName(Name, 0, Name.Length());
				size_t last_idx = ParentNode->GetLastIndexByName(Name, 0, Name.Length());

				_out += Name;

				if (ParentNode != _end) {
					ZString subscript;
					ZStringAlgo::BuildPrintf(subscript, "[%i]", siblings - (1 + last_idx - Index));

					_out += subscript;
				}
			}
		}

		// gets the simple path to this node (avoids [0] subscript)
		void GetSimplePath(ZString& _out, Node* _end = NULL) const {
			if (this != _end && ParentNode != NULL) {
				ParentNode->GetSimplePath(_out, _end);
			} else return;

			if (!_out.Empty()) {
				_out.PushBack(ZKVTREE_PATH_SEPARATOR);
			}

			if (!IsRootNode()) {
				size_t siblings = ParentNode->GetChildCountByName(Name, 0, Name.Length());
				size_t last_idx = ParentNode->GetLastIndexByName(Name, 0, Name.Length());

				_out += Name;

				if (ParentNode != _end && siblings - (1 + last_idx - Index) != 0) {
					ZString subscript;
					ZStringAlgo::BuildPrintf(subscript, "[%i]", siblings - (1 + last_idx - Index));

					_out += subscript;
				}
			}
		}
	};

	/*
	KVTree iterator, used to directly iterate the nodes in the KVTree.
	*/
	class Iterator
	{
	friend class ZKVTree;
	public:
		/*
		Parameterized Constructor.

		@param _node - the node to start the iterator at
		@param _tree - the KVTree we are iterating (reference needed for locking / unlocking)
		*/
		Iterator(Node* _node, ZKVTree* _tree)
			: CurrentNode(_node), KVTree(_tree) { }

		/*
		Copy Constructor.

		@param _other - the other iterator
		*/
		Iterator(const Iterator& _other)
			:CurrentNode(_other.CurrentNode), KVTree(_other.KVTree) { }

		/*
		Destructor.  Releases the lock (when 'Lock' is destructed).
		*/
		~Iterator()	{ }
		
		/*
		Gets the path to the current iterator location.

		@return (ZString) - path to this node
		*/
		ZString GetPath() const 
			{ ZString path; CurrentNode->GetPath(path); return path; }

		/*
		Gets the path to the current iterator from an end node.  If the end node
		is not on the parent path, functionally equivalent to GetPath.

		@param _end - node we should get path from
		@return (ZString) - path to this node from provided node
		*/
		ZString GetPath(Iterator end) const 
			{ ZString path; CurrentNode->GetPath(path, end.CurrentNode); return path; }

		/*
		As GetPath, but avoids the [0] subscript.

		@return (ZString) - path to this node
		*/
		ZString GetSimplePath() const
			{ ZString path; CurrentNode->GetSimplePath(path); return path; }

		/*
		As GetPath, but avoids the [0] subscript.

		@param _end - node we should get path from
		@return (ZString) - path to this node from provided node
		*/
		ZString GetSimplePath(Iterator end) const 
			{ ZString path; CurrentNode->GetSimplePath(path, end.CurrentNode); return path; }

		/*
		Gets a reference to the name of the current node.

		@return (const ZString&) - reference to the name of the current node
		*/
		const ZString& GetName() const
			{ ZASSERT(!CurrentNode->IsRootNode(), "Cannot get name on root node!"); return CurrentNode->Name; }

		/*
		Gets a reference to the value of the current node.

		@return (ZString&) - reference to the value of the current node
		*/
		const ZString& GetValue() const
			{ ZASSERT(!CurrentNode->IsRootNode(), "Cannot get value on root node!"); return CurrentNode->Value; }
		
		/*
		Gets the index of the current node (sibling index).

		@return (size_t) - the index of the current node.
		*/
		size_t GetIndex() const 
			{ return CurrentNode->Index; }
		
		/*
		Gets the number of children contained by this node.
		*/
		size_t GetChildCount() const
			{ return CurrentNode->Children.Size(); }

		/*
		Gets the number of children of this node with the given name.
		*/
		size_t GetChildCountByName(const ZString& _name) const 
			{ return CurrentNode->GetChildCountByName(_name, 0, _name.Length()); }

		/*
		Gets the index of the nth child of the given name (ZSTL::InvalidPos if not found).
		*/
		size_t GetChildIndexByName(const ZString& _name, size_t _n = 0) const
		{
			Node* childNode = CurrentNode->GetChildByName(_name, 0, _name.Length(), _n);
			
			return (childNode == NULL ? ZSTL::InvalidPos : childNode->Index);
		}
		
		/*
		Gets the number of siblings to the current node, including the current node.
		*/
		size_t GetSiblingCount() const
		{
			if (CurrentNode->ParentNode == NULL)
				return 0;

			return CurrentNode->ParentNode->Children.Size();
		}

		/*
		Gets the number of siblings to the current node with the given name (can
		include this node if name is equivalent).
		*/
		size_t GetSiblingCountByName(const ZString& _name) const 
		{
			if (CurrentNode->ParentNode == NULL)
				return 0;

			return CurrentNode->ParentNode->GetChildCountByName(_name, 0, _name.Length());
		}

		/*
		Gets the index of the nth sibling of the given name (ZSTL::InvalidPos if not found, can 
		be the node this iterator points to).
		*/
		size_t GetSiblingIndexByName(const ZString& _name, size_t _n = 0) const
		{
			if (CurrentNode->ParentNode == NULL)
				return ZSTL::InvalidPos;

			Node* siblingNode = CurrentNode->ParentNode->GetChildByName(_name, 0, _name.Length(), _n);	

			return (siblingNode == NULL ? ZSTL::InvalidPos : siblingNode->Index);
		}
		
		//Checks to see if this is an end node
		bool CheckEnd()
			{ return CurrentNode->IsRootNode(); }
		
		//Checks to see if we can move to the parent node
		bool CheckParent()	
			{ return CurrentNode->ParentNode != NULL; }

		//Checks to see if we can move to the child node
		bool CheckChild(size_t _index = 0)	
			{ return _index < CurrentNode->Children.Size(); }

		//Checks to see if we can move to the sibling node
		bool CheckSibling(size_t _index = 0)
			{ return CurrentNode->ParentNode != NULL && _index < CurrentNode->ParentNode->Children.Size() - 1; }

		//Checks to see if we can move to the next sibling node
		bool CheckNextSibling()
			{ return CurrentNode->ParentNode != NULL && CurrentNode->Index < CurrentNode->ParentNode->Children.Size() - 1; }

		//Checks to see if we can move to the previous sibling node
		bool CheckPrevSibling()
			{ return CurrentNode->Index > 0; }
		
		/*
		Sets the value of the current node.

		@param (ZString&) - value to set this node to
		*/
		void SetValue(const ZString& _value) 
			{ CurrentNode->Value = _value; }

		/*
		public ZKVTree::Iterator::Next

		This operation attempts to move this iterator to the first child of this node.  If this 
		is an invalid move, then it attempts to iterate to the next sibling.  If this is invalid, 
		it will attempt to iterate to the next sibling of the parent, and will continue to 
		attempt this until it has either reached the end or it can do so.

		This basically means using nothing but 'Next' from beginning to end will result in 
		a depth-first traversal of the KVTree.
				
		@return (Iterator&) - this iterator
		*/
		Iterator& Next()
		{
			if (CheckChild())
				Child();
			else if (CheckNextSibling())
				NextSibling();
			else {
				while (CurrentNode->ParentNode != NULL) {
					if (CheckParent()) {
						Parent();
						if (CheckNextSibling()) {
							NextSibling();
							break;
						}
					}
				}
			}

			return *this;
		}

		/*
		public ZKVTree::Iterator::Parent
		
		This operation attempts to move the iterator to the parent node of this node.

		@return (Iterator&) - this iterator
		*/
		Iterator& Parent()
		{			
			if (CheckParent()) {
				CurrentNode = CurrentNode->ParentNode;
			} else *this = KVTree->End();

			return *this;
		}

		/*
		public ZKVTree::Iterator::Child
		
		This operation moves the iterator to child node at the given index.

		@param _index - the child number to move to
		@return (Iterator&) - this iterator
		*/
		Iterator& Child(size_t _index = 0)
		{
			if (CheckChild(_index)) {
				CurrentNode = CurrentNode->Children[_index];
			} else *this = KVTree->End();

			return *this;
		}

		/*
		public ZKVTree::Iterator::Sibling

		This operation moves the iterator to the sibling node at the given index.

		@param _index - the sibling index
		@return (Iterator&) - this iterator
		*/
		Iterator& Sibling(size_t _index = 0)
		{
			ZASSERT(CheckSibling(_index), "ZKVTree::Iterator unable to move to sibling node!");

			if (CheckSibling(_index)) {
				CurrentNode = CurrentNode->ParentNode->Children[_index];
			} else *this = KVTree->End();

			return *this;
		}
		
		/*
		public ZKVTree::Iterator::PrevSibling
		
		This operation moves the iterator to the previous sibling node of this node.

		@return (Iterator&) - this iterator
		*/
		Iterator& PrevSibling()
		{			
			if (CheckPrevSibling()) {
				CurrentNode = CurrentNode->ParentNode->Children[CurrentNode->Index - 1];
			} else *this = KVTree->End();

			return *this;
		}

		/*
		public ZKVTree::Iterator::NextSibling
		
		This operation moves the iterator to the next sibling node of this node.

		@return (Iterator&) - this iterator
		*/
		Iterator& NextSibling()
		{
			if (CheckNextSibling()) {
				CurrentNode = CurrentNode->ParentNode->Children[CurrentNode->Index + 1];
			} else *this = KVTree->End();
			
			return *this;
		}

		/*
		public ZKVTree::Iterator::ParentItr
		
		This operation returns an iterator to the parent node.
		
		@return (ZKVTree::Iterator) - iterator to the parent node
		*/
		Iterator ParentItr() const
		{
			ZASSERT(CurrentNode->ParentNode != NULL, "Unable to get KVTree parent!");

			return Iterator(CurrentNode->ParentNode, KVTree);
		}
		
		/*
		public ZKVTree::Iterator::ChildItr

		This operation returns an iterator to the first child node of this iterator,
		or the end iterator if no child is found.

		@param _index - the child node index to get an iterator to
		@return (Iterator) - iterator to the child node
		*/
		Iterator ChildItr() const 
		{
			return ChildItr(0);
		}
		
		/*
		public ZKVTree::Iterator::ChildItr

		This operation returns an iterator to the child node at the given index.

		@param _index - the child node index to get an iterator to
		@return (Iterator) - iterator to the child node
		*/
		Iterator ChildItr(size_t _index) const
		{
			if (_index == ZSTL::InvalidPos || _index >= CurrentNode->Children.Size()) {
				return KVTree->End();
			} else return Iterator(CurrentNode->Children.Data()[_index], KVTree);
		}
		
		/*
		public ZKVTree::Iterator::ChildItr

		This returns an iterator to the nth child of the given name.

		@param _name - the name of the child to get an iterator to
		@param _n - the occurrence of the child to get (0 = first occurrence)
		@return (Iterator) - iterator to the child node
		*/
		Iterator ChildItr(const ZString& name, size_t _n = 0) const
		{
			return ChildItr(GetChildIndexByName(name, _n));
		}
		
		/*
		public ZKVTree::Iterator::GetSibling

		This operation returns an iterator to the sibling node at the given index.

		@param _index - the child node index to get an iterator to
		@return (Iterator) - iterator to the child node
		*/
		Iterator SiblingItr(size_t _index) const
		{
			if (_index == ZSTL::InvalidPos || _index >= CurrentNode->ParentNode->Children.Size()) {
				return KVTree->End();
			} else return Iterator(CurrentNode->ParentNode->Children.Data()[_index], KVTree);
		}	
		
		/*
		public ZKVTree::Iterator::GetSibling

		This operation returns an iterator to the nth sibling of the given name.

		@param _name - the name of the sibling to get an iterator to
		@param _n - the occurrence of the sibling to get (0 = first occurrence)
		@return (Iterator) - iterator to the sibling node
		*/
		Iterator SiblingItr(const ZString& name, size_t _n = 0) const
		{
			return SiblingItr(GetSiblingIndexByName(name, _n));
		}		

		//Operator Overloads
		Iterator& operator ++ ()						{ return Next(); } 
		Iterator  operator ++ (int)						{ Iterator itr = *this; Next(); return itr; }

		Iterator& operator =  (const Iterator& _other)	{ CurrentNode = _other.CurrentNode; KVTree = _other.KVTree; return *this; }

		bool	  operator == (const Iterator& _other) const { return CurrentNode == _other.CurrentNode; }
		bool	  operator != (const Iterator& _other) const { return !(*this == _other); }
		
	private:
		Node*		CurrentNode;	//Our current KVTree node
		ZKVTree*	KVTree;			//The KVTree we are iterating
	};
	
	/*
	Constructor.
	*/
	ZKVTree();

	/*
	Copy Constructor.
	*/
	ZKVTree(const ZKVTree& _other);

	/*
	Destructor.
	*/
	~ZKVTree();

	/*
	= operator.  Performs a copy of node names and data.

	@param _other - the KVTree to copy from
	*/
	ZKVTree& operator = (const ZKVTree& _other);

	/*
	public ZKVTree::Add

	Adds a node to the tree under the given parent node.  The version that takes no parent path
	will add the child under the root node.  The iterator returned is used to directly address the 
	node.

	The two parameter version of this function adds children to the root node.

	@param _parent - the path to the parent node
	@param _itr - iterator to the parent node
	@param _name - the name of the child node
	@param _value - the value of the child node
	@return (Iterator) - iterator to the created node
	*/
	Iterator Add(const ZString& _name, const ZString& _value);
	Iterator Add(const ZString& _parent, const ZString& _name, const ZString& _value);
	Iterator Add(const Iterator& _itr, const ZString& _name, const ZString& _value);

	/*
	public ZKVTree::Begin
	
	Gets a ZKVTree::Iterator to the first child of the root node of this KVTree.  If there
	are no children, returns ZKVTree::End().
	
	@return (ZKVTree::Iterator) - iterator to the beginning of the KVTree (first child node)
	*/
	Iterator Begin() const;

	/*
	public ZKVTree::Clear

	Clears the KVTree of all values.

	@return (void)
	*/
	void Clear();

	/*
	public ZKVTree::End
	
	Gets a ZKVTree::Iterator to the end of the KVTree.
	
	@return (ZKVTree::Iterator) - iterator to the end of the KVTree
	*/
	const Iterator End() const;

	/*
	public ZKVTree::Erase

	Erases the node at the given position and all children.

	@param _path - the path to the node
	@param _itr - iterator to the node (invalidated by this call)
	@return (void)
	*/
	void Erase(const ZString& _path);
	void Erase(const Iterator& _itr);
	
	/*
	public ZKVTree::Find
	
	Gets a ZKVTree::Iterator to the given element if found.  Returns an iterator
	equivalent to ZKVTree::End() if not found.

	@param _path - path to the node to get an iterator to
	@param _itr - parent iterator to search from (path will be searched from this node as root)
	@return (ZKVTree::Iterator) - iterator to value if found, End() otherwise
	*/
	Iterator Find(const ZString& _path) const;
	Iterator Find(const Iterator& _itr, const ZString& _path) const;

	/*
	public ZKVTree::Get
	
	Gets a value from the KVTree that held by the node at the provided path.

	@param _path - the path to the node to get the value from (if no subscript, [0] is assumed)
	@return (const ZString&) - reference to the value held by the node at the provided path
	@assert - if no value exists at the provided path
	*/
	const ZString& Get(const ZString& _path) const;
	const ZString& Get(const Iterator& _itr, const ZString& _path);
	
	/*
	public ZKVTree::Merge
	
	Merges this KVTree with another, bringing in the values defined in the other
	KVTree.
	
	@param _other - the KVTree to merge values from
	@param _overwrite - if true, values will be overwritten when a conflict occurs
	@return (void)
	*/
	void Merge(const ZKVTree& _other, bool _overwrite);

	/*
	public ZKVTree::Put
	
	Puts a node with the given value into the KVTree at the provided path.  Will overwrite
	any existing value at that location. 

	If the path string has a child node that does not exist, it will be created so long as the 
	subscript is for the next child node, i.e., if A.B.c[1] is passed in, it will be created so
	long as A.B.c[0] exists.

	The iterator version overwrites the data at that location if the iterator was created by this
	tree, and will attempt to create it as above if not from this tree.

	@param _path - the path to the KVTree value (if no index, [0] is assumed)
	@param _itr - iterator to the node to assign the value to (will overwrite)
	@param _value - the value to assign to the node
	@return (Iterator) - iterator to the created value
	*/	
	Iterator Put(const ZString& _key, const ZString& _value);
	Iterator Put(const Iterator& _itr, const ZString& _value);

    /*
    public ZKVTree::IsValidKeyName

    Checks that a key name is able to be put into the KVTree.

    This basically ensures that a key will be valid for use in pathing.
    A valid key name doesn't contain whitespace, square brackets, or periods.

    @param _name - the name being considered for validity.
    @return (bool) - true if the keyname would be valid in a path, false otherwise
    */
    bool IsValidKeyName( const ZString& _key ) const;
	
protected:
	ZSlabAllocator<Node, ZKVTREE_NODE_COUNT> NodeAllocator;

	Node RootNode;	// The root node of the KVTree (also acts as the end node)

	//Gets a node from the KVTree given a path (NULL if not found)
	Node* GetFromPath(const ZString& _path) const;

	//Creates all the nodes needed along a path to be able to get and set the value, returning the node
	Node* CreatePath(const ZString& _path);

	//Helper function used to check in all nodes
	void NodeCheckIn(Node* _node);
};

#endif