/************************************************************************************************************
* -----------------------------------------------jsTreeClasses-----------------------------------------------
*								!! COPYRIGHT lars bagamery 2004 [lsblsb@gmx.de] !!	
*************************************************************************************************************/

/* * *
 * CLASS Tree
 * @param [optional] string pSerializedTree
 * @param string strObjName
 */
	
	function Tree(pSerializedTree, strObjName)
	{
		this.name = strObjName; //String Name des zu erstellenden objekts
		this.rootNode = null;
		this.currentNode = this.rootNode;
		this.pointer = 0;
		this.nodes = new Array();
		this.serializedTree = "";
		
		/**
		 * return elements by class-name
		 */
		this.getElementsByClass = function(searchClass, node, tag)
		{
	        var classElements = new Array();
	        if (node == null) node = document;
	        if (tag == null) tag = '*';
	        var els = node.getElementsByTagName(tag);
	        var elsLen = els.length;
	        var pattern = new RegExp("(^|\\s)"+searchClass+"(\\s|$)");
	        for (var i=0, j=0; i<elsLen; i++)
                if(pattern.test(els[i].className))
                {
					classElements[j] = els[i];
					j++;
                }
	        return classElements;
		}
		
		/* * *
		 * getName()
		 * returns the Name of this Object (should be the name of the instance variable!)
		 * @return String
		 */
		
		this.getName = function()
		{
			return this.name;
		}
		
		/* * *
		 * getNodes()
		 * return all nodes of this tree in an array
		 * @return Array
		 */
		
		this.getNodes = function()
		{
			return this.nodes;
		}
		
		this.hasNodes = function()
		{
			return this.nodes.length != 0;
		}
		
		/* * *
		 * setRootNode()
		 * set the root node
		 * @param Node pNodeObj
		 * @return void
		 */
		
		this.setRootNode = function(pNodeObj)
		{
			this.rootNode = pNodeObj;
			this.currentNode = this.rootNode;
			this.nodes[this.nodes.length] = pNodeObj;
		}
		
		/* * *
		 * getRootNode()
		 * get the root node
		 * @return Node pNodeObj | NULL
		 */
		
		this.getRootNode = function()
		{
			return this.rootNode;
		}
		
		/* * *
		 * addNode()
		 * adds a node to the tree
		 * @access public
		 * @param Node pNodeObj
		 * @param Nod pParentNodeObj
		 * @return Boolean
		 */
		 
		this.addNode = function(pNodeObj, pParentNodeObj)
		{
			if(pParentNodeObj && this.rootNode != null)
			{
				var pParentNodeObjChildren = pParentNodeObj.getChildren();
				var pParentNodeObjChildrenLen = pParentNodeObjChildren.length;
				if(pParentNodeObjChildrenLen > 0)
				{
					var pNodeObjLeftNeighbour = pParentNodeObjChildren[pParentNodeObjChildrenLen-1];
					pNodeObjLeftNeighbour.setRightNeighbour(pNodeObj);
					pNodeObj.setLeftNeighbour(pNodeObjLeftNeighbour);
				}
				pNodeObj.setParent(pParentNodeObj);
				pParentNodeObj.setChild(pNodeObj);
				this.nodes[this.nodes.length] = pNodeObj;
				return true;
			}
			else
			{
				return false;
			}
		}
		
		/* * *
		 * getNodeById()
		 * returns a node identified by its id.
		 * @access public
		 * @param String|Int pId
		 * @return Node
		 */
		
		this.getNodeById = function(pId)
		{
			var nodeObj = false;
			var nodesLen = this.nodes.length;
			for(i=0; i<nodesLen; i++)
				if(this.nodes[i].getId() == pId)
					nodeObj = this.nodes[i];
			return nodeObj;
		}
		
		/**
		 * check if current node has previous node
		 * @return bool
		 */
		
		this.hasPrevious = function()
		{ 	
			var result = this.getPrevious(false);
			return result ? true : false;
		}
		
		/**
		 * return previous node
		 * @param optional movePointer = true
		 * @return Node
		 */
		
		this.getPrevious = function(movePointer)
		{	//@todo
			var result = null;
			
			if(typeof movePointer != "boolean") movePointer = true;
			
			var currNode = this.currentNode;
			var i=0;
			
			while(currNode.getChild(currNode.getChildren().length-1) && !(i == 0 && this.getNext(false) && this.getNext(false).getLeftNeighbour() == null))
			{
				result = currNode = currNode.getChild(currNode.getChildren().length-1);
				i++;
			}
			
			if(!result)
			{
				result = currNode.getLeftNeighbour();
				if(result && i==0)
				{
					currNode = result;
					while(currNode.getChild(currNode.getChildren().length-1))
						result = currNode = currNode.getChild(currNode.getChildren().length-1);
				}
			}
			
			if(!result)
				result = currNode.getParent();
			
			if(result && movePointer)
			{
				this.pointer--;
				this.currentNode = result;
			}
			return result;
		}
		
		/**
		 * return current node 
		 * @return Node
		 */
		
		this.getCurrent = function()
		{
			return this.currentNode;
		}
		
		/**
		 * check if current node has next node
		 * @return bool
		 */
		
		this.hasNext = function()
		{
			var result = this.getNext(false);
			return result ? true : false;
		}
		
		/**
		 * return next node
		 * @param optional movePointer = true
		 * @return Node
		 */
		
		this.getNext = function(movePointer)
		{
			var result = null;
			
			if(typeof movePointer != "boolean") movePointer = true;
			
			var currNode = this.currentNode;
			if(currNode.getChild(0) && !(currNode == this.rootNode && this.pointer > 0))
				result = currNode.getChild(0);
			else if(currNode.getRightNeighbour())
				result = currNode.getRightNeighbour();
			else
				while(currNode.getParent())
					if(currNode.getParent().getRightNeighbour())
					{
						result = currNode.getParent().getRightNeighbour();
						break;
					}
					else
						result = currNode = currNode.getParent();
			if(result && movePointer)
			{
				this.currentNode = result;
				this.pointer++;
			}
			return result;
		}
		
		/**
		 * reset internal pointer to root-node
		 */
		 
		this.reset = function()
		{
			this.currentNode = this.rootNode;
			this.pointer = 0;
		}
		
		/* * *
		 * convertSerializedTree()
		 * converts a serializedTree String into a Tree-Object
		 * Tree should be empty when using this function
		 * returns the tree object itself
		 * @access public
		 * @param String serializedTree
		 * @return Tree
		 */
		
		this.convertSerializedTree = function(serializedTree, pointer, lastVals, lastObjs, depth, treeObj)
		{
			if(!pointer)
			{
				var pointer = 0;
				var depth = 0;
				var lastVals = new Array();
				var lastObjs = new Array();
				var treeObj = this;
			}
			
			if(pointer != serializedTree.length)
			{
				//lese naechsten value aus
				var actLengthLen = parseInt(serializedTree.charAt(pointer));
				pointer ++;
				var actValLen = parseInt(serializedTree.substr(pointer, actLengthLen));
				pointer += actLengthLen;
				var actVal = serializedTree.substr(pointer, actValLen);
				pointer += actValLen;
				
				lastValsArrLen = lastVals.length;
				lastObjsArrLen = lastObjs.length;
				
				if(inArray(actVal, lastVals))
				{
					lastVals.length = lastValsArrLen-1;
					lastObjs.length = lastObjsArrLen-1;
					depth--;
				}
				else
				{	
					lastVals[lastValsArrLen] = actVal;
					
					//objects
					if(lastObjsArrLen == 0)
					{
						var parentNode = null;
					}
					else
					{
						parentNode = lastObjs[lastObjsArrLen-1];
					}
					//create new node
					actNode = new Node(actVal);
					//set depth property
					actNode.setProperty("depth",depth);
					//add node to tree
					if(lastObjsArrLen == 0)
					{	//create root node
						treeObj.setRootNode(actNode);
					}
					else
					{
						treeObj.addNode(actNode, parentNode);
					}
					//add node to lastObjs-array
					lastObjs[lastObjsArrLen] = actNode;
					depth++;
				}
				return this.convertSerializedTree(serializedTree, pointer, lastVals, lastObjs, depth, treeObj);
			}
			return treeObj;
		}
		
		/* * *
		 * getSubtree()
		 * returns a subtree of this tree as Default output. pStartNode will be the root of the returned tree
		 * @access public
		 * @param Node pStartNode
		 * @param [optional] Int pMaxDepth
		 * @return String
		 */
		
		this.getSubtree = function(pStartNode, pMaxDepth, pActNode, pChildNum, pDepth)
		{
			if(!pStartNode)
			{
				pStartNode = this.rootNode;
			}
			if(!pMaxDepth)
			{
				pMaxDepth = -1;
			}
			if(!pActNode)
			{
				subTreeDefaultOutput = "";
				pActNode = pStartNode;
				pDepth = 0;
			}
			var rightNeighbour = pActNode.getRightNeighbour();
			//save return value in variable
			for(i=0; i<pDepth; i++)
			{
				subTreeDefaultOutput += "> ";
			}
			subTreeDefaultOutput += pActNode.getId()+"<br>";
			//end save
			var children = pActNode.getChildren();
			var firstChild = children[0];
			if((children.length > 0) && ((pDepth < pMaxDepth) || (pMaxDepth == -1)))
			{
				pDepth++;
				pActNode = firstChild;
				this.getSubtree(pStartNode, pMaxDepth, pActNode, pChildNum, pDepth);
				pDepth--;
			}
			if(rightNeighbour != null)
			{
				pActNode = rightNeighbour;
				this.getSubtree(pStartNode, pMaxDepth, pActNode, pChildNum, pDepth);
			}
			return subTreeDefaultOutput;
		}
		
		//wenn serializedTree bei Objekterstellung uebergeben wurde, dann lese es in den Objektbaum ein
		if(pSerializedTree)
		{
			this.serializedTree = pSerializedTree;
			this.convertSerializedTree(this.serializedTree);
		}
	}
	
/* * *
 * CLASS Tree
 * @param [optional] string pSerializedTree
 * @param String|Int pId
 */

	function Node(pId)
	{
		this.parent = null;
		this.children = new Array();
		this.rightNeighbour = null;
		this.leftNeighbour = null;
		this.id = "";
		this.properties = new Array();
		
		if(pId)
		{
			this.id = pId;
		}
		
		this.addProperty = function(pKey, pValue)
		{
			this.properties[pKey] = pValue;
		}
		
		this.setProperty = function(pKey, pValue)
		{
			return this.properties[pKey] = pValue;
		}
		
		this.getProperty = function(pKey)
		{
			return this.properties[pKey];
		}
		
		this.getProperties = function()
		{
			return this.properties;
		}
		
		this.removeProperty = function(pKey)
		{
			var deleted = false;
			var properties_temp = new Array();

			for (var key in this.properties)
			{
				if(key != pKey)
				{
					properties_temp[key] = this.properties[key];
				}
				else
				{
					deleted = true;
				}
			}
			this.properties = properties_temp;
			return deleted;
		}
		
		this.setParent = function(pNodeObj)
		{
			this.parent = pNodeObj;
		}
		
		this.getParent = function()
		{
			return this.parent;
		}
		
		this.setChild = function(pNodeObj)
		{
			var childrenLen = this.children.length;
			this.children[childrenLen] = pNodeObj;
		}
		
		this.getChild = function(pChildPos)
		{
			return this.children[pChildPos];
		}
		
		this.getChildren = function()
		{
			return this.children;
		}
		
		this.hasChildren = function()
		{
			return this.children.length > 0;
		}
		
		this.setRightNeighbour = function(pNodeObj)
		{
			this.rightNeighbour = pNodeObj;
		}
		
		this.getRightNeighbour = function()
		{
			return this.rightNeighbour;
		}
		
		this.setLeftNeighbour = function(pNodeObj)
		{
			this.leftNeighbour = pNodeObj;
		}
		
		this.getLeftNeighbour = function()
		{
			return this.leftNeighbour;
		}
		
		this.setId = function(pStrId)
		{
			this.id = pStrId;
		}
		
		this.getId = function()
		{
			return this.id;
		}
		
		this.isRootNode = function()
		{
			return this.parent ? false : true;
		}
	}
	
///////////functions to handle serialized tree strings/////////////////////////////////

//array-funktion: sucht ein element in einem eindim. array
	function inArray(needle, arrHaystack)
	{
		var result = false;
		var arrHaystackLen = arrHaystack.length;
		for(var i=0; i<arrHaystackLen; i++)
		{
			if(arrHaystack[i] == needle)
			{
				result = needle;
			}
		}
		return result;
	}
	
//wandle serializedTree String in Tree-Objekt um/////////////////////////////////

	function serializedTreeToObject(serializedTree, pointer, lastVals, lastObjs, depth, treeObj)
	{
		//hole i-ten intwert aus String
		if(!pointer)
		{
			var pointer = 0;
			var depth = 0;
			var lastVals = new Array();
			var lastObjs = new Array();
			var treeObj = new Tree();
		}
		
		if(pointer != serializedTree.length)
		{
			//lese naechsten value aus
			var actLengthLen = parseInt(serializedTree.charAt(pointer));
			pointer += actLengthLen;
			var actValLen = parseInt(serializedTree.substr(pointer, actLengthLen));
			pointer += actLengthLen;
			var actVal = serializedTree.substr(pointer, actValLen);
			pointer += actValLen;
			
			lastValsArrLen = lastVals.length;
			lastObjsArrLen = lastObjs.length;
			
			if(inArray(actVal, lastVals))
			{
				lastVals.length = lastValsArrLen-1;
				lastObjs.length = lastObjsArrLen-1;
				depth--;
			}
			else
			{
				lastVals[lastValsArrLen] = actVal;
				
				//objects
				if(lastObjsArrLen == 0)
				{
					var parentNode = null;
				}
				else
				{
					parentNode = lastObjs[lastObjsArrLen-1];
				}
				//create new node
				actNode = new Node(actVal);
				//add node to tree
				if(lastObjsArrLen == 0)
				{	//create root node
					treeObj.setRootNode(actNode);
				}
				else
				{
					treeObj.addNode(actNode, parentNode);
				}
				//add node to lastObjs-array
				lastObjs[lastObjsArrLen] = actNode;
				depth++;
			}
			
			return serializedTreeToObject(serializedTree, pointer, lastVals, lastObjs, depth, treeObj)
		}
		return treeObj;
	}

/////////////////////////////////////////////////////////////////////////////////////////////////////////