BX.namespace('DataStructure');
BX.DataStructure.Struct = function(key,value)
{
	this.key = key;
	this.value = value;
}
BX.DataStructure.Stack = function(){this.elements = [];}
BX.DataStructure.Stack.prototype = 
{
	type:BX.DataStructure.Stack,
	getType:function()
	{
		return this.type;
	},
	pop:function()
	{
		if(this.elements.length == 0 ) 
			return null;
		else 
			return this.elements.pop();
	},
	push:function()
	{
		if(arguments.length == 0) 
			return -1;
		for(i = 0; i < arguments.length; i++)
			this.elements.push(arguments[i]);
	},
	clear:function()
	{
		this.elements.length = 0;
	},
	getLength:function()
	{
		return this.elements.length;	
	},
	getTop:function()
	{
		if(this.elements.length == 0) 
			return null;
		else
			return this.elements[this.elements.length-1];
	},
	isEmpty:function()
	{
		return 	this.elements.length == 0 ? true:false;
	},
	traverse:function(func)
	{
		if(this.elements.length == 0) return -1;
		for(i = 0; i < this.elements.length; i++)
			func(this.elements[i]);
	},
	toString:function()
	{
		_string = '';
		this.traverse(
			function(element)
			{
				if(element != null) _string += element.toString();
			}
		);
		return _string;
	}
}
BX.DataStructure.Queue = function(){this.elements = [];}
BX.DataStructure.Queue.prototype = 
{
	type:BX.DataStructure.Queue,
	getType:function()
	{
		return this.type;
	},
	enQueue:function()
	{
		if(arguments.length == 0) 
			return -1;
		for(i = 0; i < arguments.length; i++)
			this.elements.push(arguments[i]);
	},
	deQueue:function()
	{
		if(this.elements.length == 0 ) 
			return null;
		else 
			return this.elements.shift();
	},
	clear:function()
	{
		this.elements.length = 0;
	},
	getLength:function()
	{
		return this.elements.length;	
	},
	getHead:function()
	{
		if(this.elements.length == 0) 
			return null;
		else 
			return this.elements[0];
	},
	getEnd:function()
	{
		if(this.elements.length == 0) 
			return null;
		else 
			return this.elements[this.elements.length - 1];	
	},
	isEmpty:function()
	{
		return 	this.elements.length == 0 ? true:false;
	},
	traverse:function(func)
	{
		if(this.elements.length == 0) return -1;
		for(i = 0; i < this.elements.length; i++)
			func(this.elements[i]);
	},
	toString:function()
	{
		_string = '';
		this.traverse(
			function(element)
			{
				if(element != null) _string += element.toString();
			}
		);
		return _string;
	}
}
BX.DataStructure.List = function(){ this.elements = [];}
BX.DataStructure.List.prototype = 
{
	type:BX.DataStructure.List,
	getType:function()
	{
		return this.type;
	},
	clear:function()
	{
		this.elements.length = 0;
	},
	getLength:function()
	{
		return this.elements.length;
	},
	getElement:function(index)
	{
		if(index < 0 || index > this.elements.length -1) 
			return null;
		else
			return this.elements[index];
	},
	indexOf:function(el)
	{
		for(i = 0; i < this.elements.length; i++)
			if(this.elements[i] == el) 
				return i;
			return -1;
	},
	insert:function(position,el)
	{
		if(position < 0 || position > this.elements.length)
			return -1;
		this.elements.splice(position,0,el);
	},
	remove:function(position)
	{
		this.elements.splice(position,1);	
	},
	add:function(el)
	{
		this.elements[this.elements.length] = el;
	},
	isEmpty:function()
	{
		return 	this.elements.length == 0 ? true:false;
	},
	traverse:function(func)
	{
		if(this.elements.length == 0) return -1;
		for(i = 0; i < this.elements.length; i++)
			func(this.elements[i]);
	},
	toString:function()
	{
		_string = '';
		this.traverse(
			function(element)
			{
				if(element != null) _string += element.toString();
			}
		);
		return _string;
	}
}
/**
*LinkedList.insert()方法不能插入链表的头元素之前，可以插入到链表表尾元素之后，下标从1到链表长度；
*LinkedList.delete()方法不能删除链表的头元素，下标从1到链表长度减1；
*LinkedList.getElement() 下标从0到链表长度减1。
*/
BX.DataStructure.ListNode = function(data)
{
	this.data = null;
	this.next = null;
	if(data != null) this.data = data;
}
BX.DataStructure.LinkedList = function(data)
{
	this.head = new BX.DataStructure.ListNode(data);
}
BX.DataStructure.LinkedList.prototype = 
{
	type:BX.DataStructure.LinkedList,
	getType:function()
	{
		return this.type;
	},
	clear:function()
	{
		this.head = null;
	},
	getLength:function()
	{
		var _head = this.head;
		var i = 0;
		while(_head != null)
		{
			_head = _head.next;
			i++;
		}
		return i;
	},
	getElement:function(index)
	{
		var _head = this.head;
		var i = 0;
		while(_head != null && i < index)
		{
			_head = _head.next;
			i++;
		}
		if(_head == null || i > index)
			return null;
		else  
			return _head;
	},
	indexOf:function(el)
	{
		var _head = this.head;
		var _node = new BX.DataStructure.ListNode(el);
		var i = 0;
		while(_head != null)
		{
			if(this._compare(_head,_node)) return i;
			_head = _head.next;
			i++;
		}
		return -1;
	},
	_compare:function(nodeA,nodeB)
	{
		return nodeA.data == nodeB.data ? true:false;
	},
	getPriorElement:function(el)
	{
		return this.getElement(this.indexOf(el)-1);
	},
	getNextElement:function(el)
	{
		return this.getElement(this.indexOf(el)+1);
	},
	insert:function(position,el)
	{
		var _head = this.head;
		var _node = new BX.DataStructure.ListNode(el);
		var  i = 0;
		while(_head != null && i < position - 1)
		{
			_head = _head.next;
			i++;
		}
		if(_head == null || i > position - 1) return -1;
		_node.next = _head.next;
		_head.next = _node;
	},
	remove:function(position)
	{
		var _head = this.head;
		var  i = 0;
		while(_head != null && i < position - 1)
		{
			_head = _head.next;
			i++;
		}
		if(_head == null || i > position - 1) return -1;
		var _temp = _head.next;
		if(_temp == null) return -1;
		else _head.next = _temp.next;
	},
	add:function(el)
	{
		var _head = this.head;  
		var _node = new BX.DataStructure.ListNode(el);
		while(_head.next != null)
		{
			_head = _head.next;
		}
		_head.next = _node;
	},
	isEmpty:function()
	{
		return this.head == null ? true:false;
	},
	traverse:function(func)
	{
		var _head = this.head;
		while(_head != null)
		{
			func(_head);
			_head = _head.next;
		}
	},
	toString:function()
	{
		_string = '';
		this.traverse(
			function(element)
			{
				if(element != null && element.data != null) _string += element.data.toString();
			}
		);
		return _string;
	}
}
/*
*Tree.getLeafCount() 求所有叶子节点数
*Tree.getNodeCount() 求除根节点外的所有节点数
*/
BX.DataStructure.Tree = function(data)
{
	this.data = null;
	this.parent = null;
	this.children = [];
	if(data != null) this.data = data;
}
BX.DataStructure.Tree.prototype = 
{
	type:BX.DataStructure.Tree,
	getType:function()
	{
		return this.type;
	},
	clear:function()
	{
		this.children.length = 0;
	},
	hasChild:function()
	{
		return this.children.length != 0 ? true:false;
	},
	hasParent:function()
	{
		return this.parent != null ? true:false;
	},
	isEmpty:function()
	{
		return this.children.length == 0 ? true:false;
	},
	isTreeNode:function(treeNode)
	{
		if(treeNode.type != 'undefined' && treeNode.type == BX.DataStructure.Tree)
			return true;
		else
			return false;
	},
	getLeafCount:function()
	{
		var _stack = new BX.DataStructure.Stack();
		var _tree = this;
		var _count = 0;
		while(_tree != null)
		{
			for(var i = 0; i < _tree.children.length; i++)
			{
				if(_tree.children[i].hasChild()) _stack.push(_tree.children[i]);
				else _count++;
			}
			_tree = _stack.pop();
		}
		return _count;
	},
	getNodeCount:function()
	{
		var _count = 1;//从根节点开始，记为1
		for(var i in this.children)
		{
			//如果非叶节点则递归，否则1个叶节点加1
			if(this.children[i].hasChild()) _count += this.children[i].getNodeCount();
			else _count++;
		}
		return _count;
	},
	getDepth:function()
	{
		var _depth = 1;//初始深度为1
		var _max = 1;
		if(this.isEmpty()) return _depth;
		for(var i in this.children)
		{
			if(this.children[i].hasChild()) 
			{
				var _temp = this.children[i].getDepth();
				if(_temp > _max) _max = _temp;
			}
		}
		_depth = _depth+_max;
		return _depth;
	},
	getChildrenByDepth:function(depth)
	{
		if(depth <  1) return -1;
		if(depth == 1) return new Array(this);
		var _queue = new BX.DataStructure.Queue();
		var _depthQueue = new BX.DataStructure.Queue();//同一层元素的个数队列，对头为同一层元素的个数
		var _children = [];
		var _treeNode = null;
		var _depth = 1;
		var _count = 0;
		_queue.enQueue(this);
		while(!_queue.isEmpty())
		{
			if(_depth == depth) { _children = _queue.elements; break;}
			else
			{
				_depthQueue.enQueue(_queue.getLength());
				_treeNode = _queue.deQueue();
				if(_treeNode != null && _treeNode.hasChild()) 
				{
					for(var i in _treeNode.children)
						_queue.enQueue(_treeNode.children[i]);
				}
				_count++;
				//当计数等于同一层元素个数的时候，_depthQueue置0，下一次循环时推入下一层的个数
				if(_count == _depthQueue.getHead())
				{
					_depth++;
					_count = 0;
					_depthQueue.clear();
				}
			}
		}
		return _children;
	},
	getParent:function()
	{
		return this.parent;
	},
	getLeftChild:function()
	{
		return this.isEmpty() ? null : this.children[0];
	},
	getRightChild:function()
	{
		return this.isEmpty() ? null : this.children[this.children.length - 1];
	},
	getLeftSibling:function(treeNode)
	{
		if(!this.isTreeNode(treeNode) || treeNode.parent == null)
			return null;
		var _children = treeNode.parent.children;
		for(var i in _children)
		{
			if(_children[i] == treeNode && i > 0)	return _children[i-1];
		}
		return null;
	},
	getRightSibling:function(treeNode)
	{
		if(!this.isTreeNode(treeNode) || treeNode.parent == null)
			return null;		
		var _children = treeNode.parent.children;
		for(var i = 0 ; i < _children.length; i++)
		{
			if(_children[i] == treeNode && i < _children.length-1)	
				return _children[i+1];
		}
		return null;
	},
	insert:function(parentNode,childNode)
	{
		if(!this.isTreeNode(parentNode) || !this.isTreeNode(childNode))
			return -1;
		parentNode.children.push(childNode);
	},
	remove:function(el)
	{
		if(el == null) return -1;
		if(this.isEmpty()) return;
		if(this.isTreeNode(el))
		{
			for(var i = 0 ; i < this.children.length; i++)
			{
				if(this.children[i].hasChild()) this.children[i].remove(el);
				if(this.children[i] == el) this.children.splice(i,1);
			}
		}
		else
		{
			for(var i = 0 ; i < this.children.length; i++)
			{
				if(this.children[i].hasChild()) this.children[i].remove(el);
				if(this.children[i].data == el) this.children.splice(i,1);
			}
		}
	},
	add:function(el)
	{
		var _node = null;
		if(this.isTreeNode(el))	_node = el;
		else	_node = new BX.DataStructure.Tree(el);
		_node.parent = this;
		this.children.push(_node);
	},
	traverse:function(func)
	{
		func(this);
		for(var i = 0 ; i < this.children.length; i++)
		{
			if(this.children[i].hasChild()) 
				this.children[i].traverse(func);
			else 
				func(this.children[i]);
		}
	},
	levelOrderTraverse:function(func)
	{
		var _queue = new BX.DataStructure.Queue();
		var _tree = this;
		var _treeNode = null;
		func(_tree);
		while(_tree != null)
		{
			if(_tree.hasChild())
			{
				for(var i in _tree.children)
					_queue.enQueue(_tree.children[i]);
			}
			if((_treeNode = _queue.deQueue()) != null) func(_treeNode);
			_tree = _treeNode;
		}
	},
	toString:function()
	{
		var _string = '';
		this.levelOrderTraverse(
			function(treeNode){ 
				if(treeNode.data!=null) 
					_string += treeNode.data.toString();
			}
		);
		return _string;
	}
}

BX.DataStructure.BinaryTree = function(data)
{
	this.data = null;
	this.leftChild = null;
	this.rightChild = null;
	if(data != null) this.data = data;
}
BX.DataStructure.BinaryTree.prototype = 
{
	type:BX.DataStructure.BinaryTree,
	getType:function()
	{
		return this.type;
	},
	clear:function()
	{
		this.leftChild = null;
		this.rightChild = null;
	},
	hasLeftChild:function()
	{
		return this.leftChild != null ? true:false;
	},
	hasRightChild:function()
	{
		return this.rightChild != null ? true:false;
	},
	isEmpty:function()
	{
		return (!this.hasLeftChild() && !this.hasRightChild()) ? true:false;
	},
	isBinaryTreeNode:function(treeNode)
	{
		if(treeNode.type != 'undefined' && treeNode.type == BX.DataStructure.BinaryTree)
			return true;
		else
			return false;
	},
	getLeafCount:function()
	{
		var _stack = new BX.DataStructure.Stack();
		var _tree = this;
		var _count = 0;
		while(_tree != null)
		{
			if(!_tree.isEmpty())
			{
				if(_tree.hasLeftChild()) _stack.push(_tree.leftChild);
				if(_tree.hasRightChild()) _stack.push(_tree.rightChild);
			}
			else	
			{
				_count++;
			}
			_tree = _stack.pop();
		}
		return _count;
	},
	getNodeCount:function()
	{
		var _count = 1;//从根节点开始，记为1
		if(!this.isEmpty())
		{
			if(this.hasLeftChild()) _count += this.leftChild.getNodeCount();
			if(this.hasRightChild()) _count += this.rightChild.getNodeCount();
		}
		return _count;
	},
	getDepth:function()
	{
		var _depth = 1;//初始深度为1
		var _max = 1;
		if(this.isEmpty()) return _depth;
		if(this.hasLeftChild())
		{
			var _temp = this.leftChild.getDepth();
			if(_temp > _max) _max = _temp;
		}
		if(this.hasRightChild())
		{
			var _temp = this.rightChild.getDepth();
			if(_temp > _max) _max = _temp;
		}
		_depth = _depth+_max;
		return _depth;
	},
	getChildrenByDepth:function(depth)
	{
		if(depth <  1) return -1;
		if(depth == 1) return new Array(this);
		var _queue = new BX.DataStructure.Queue();
		var _depthQueue = new BX.DataStructure.Queue();//同一层元素的个数队列，对头为同一层元素的个数
		var _children = [];
		var _treeNode = null;
		var _depth = 1;
		var _count = 0;
		_queue.enQueue(this);
		while(!_queue.isEmpty())
		{
			if(_depth == depth) { _children = _queue.elements; break;}
			else
			{
				_depthQueue.enQueue(_queue.getLength());
				_treeNode = _queue.deQueue();
				if(_treeNode.hasLeftChild()) _queue.enQueue(_treeNode.leftChild);
				if(_treeNode.hasRightChild()) _queue.enQueue(_treeNode.rightChild);		
				_count++;
				//当计数等于同一层元素个数的时候，_depthQueue置0，下一次循环时推入下一层的个数
				if(_count == _depthQueue.getHead())
				{
					_depth++;
					_count = 0;
					_depthQueue.clear();
				}
			}
		}
		return _children;
/*		if(depth <  1) return -1;
		if(depth == 1) return new Array(this);
		var _stack = new BX.DataStructure.Stack();
		var _depthStack = new BX.DataStructure.Stack();
		var _children = [];
		var _treeNode = null;
		var _currentDepth = 1;
		var isMatched = false;
		_stack.push(this);
		_depthStack.push(_currentDepth);
		while(!_stack.isEmpty())
		{
			//元素和该元素相应的深度同时出栈
			_treeNode = _stack.pop();
			_currentDepth = _depthStack.pop();
			
			if(_treeNode.hasLeftChild() || _treeNode.hasRightChild()) _currentDepth++;
			//判断是否到达所求深度，如果是则添加到_children数组，否则当前深度和子元素都入栈
			isMatched = _currentDepth == depth ? true : false;
			if(_treeNode.hasLeftChild()) 
			{
				if(isMatched) _children.push(_treeNode.leftChild);
				else
				{
					_stack.push(_treeNode.leftChild);
					_depthStack.push(_currentDepth);
				}
			}
			if(_treeNode.hasRightChild())
			{
				if(isMatched) _children.push(_treeNode.rightChild);
				else
				{
					_stack.push(_treeNode.rightChild);
					_depthStack.push(_currentDepth);
				}
			}
		}
		return _children;*/
	},
	getHops:function(treeNode)
	{
		if(treeNode == null || !this.isBinaryTreeNode(treeNode)) 
			return -1;
		if(this == treeNode) 
			return 0;
		var _stack = new BX.DataStructure.Stack();
		var _count = 0;
		var _tree = this;
		var _treeNode = _tree.getParent(treeNode);	
		while(_treeNode != null) 
		{
			_count++;
			_treeNode = _tree.getParent(_treeNode);
		}
		return _count;
	},
	getLeftChild:function()
	{
		return this.leftChild != null ? this.leftChild : null;
	},
	getRightChild:function()
	{
		return this.rightChild != null ? this.rightChild : null;
	},
	getParent:function(treeNode)
	{
		if(treeNode == null || !this.isBinaryTreeNode(treeNode) || this == treeNode) 
			return null;
		if(this.getLeftChild() == treeNode || this.getRightChild() == treeNode)
			return this;
		var _parent = null;
		if(this.hasLeftChild()) 
		{
			_parent = this.leftChild.getParent(treeNode); 
			if(_parent != null) return _parent;
		}
		if(this.hasRightChild()) 
		{
			_parent = this.rightChild.getParent(treeNode);
			if(_parent != null) return _parent;
		}
		return null;
	},
	insertLeft:function(parentNode,childNode)
	{
		if(!this.isBinaryTreeNode(parentNode) || !this.isBinaryTreeNode(childNode))
			return -1;
		parentNode.leftChild = childNode;
	},
	insertRight:function(parentNode,childNode)
	{
		if(!this.isBinaryTreeNode(parentNode) || !this.isBinaryTreeNode(childNode))
			return -1;
		parentNode.rightChild = chileNode;
	},
	remove:function(el)
	{
		if(el == null) return -1;
		if(this.isEmpty()) return;
		if(this.isBinaryTreeNode(el))
		{
			if(this.getLeftChild() == el) this.leftChild = null;
			if(this.getRightChild() == el) this.rightChild = null;
			if(this.hasLeftChild())	this.leftChild.remove(el);
			if(this.hasRightChild()) this.rightChild.remove(el);
		}
		else
		{
			if(this.getLeftChild().data == el) this.leftChild = null;
			if(this.getRightChild().data == el) this.rightChild = null;
			if(this.hasLeftChild())	this.leftChild.remove(el);
			if(this.hasRightChild()) this.rightChild.remove(el);
		}	
	},
	addLeft:function(el)
	{
		var _node = null;
		if(this.isBinaryTreeNode(el))	_node = el;
		else	_node = new BX.DataStructure.BinaryTree(el);
		if(!this.hasLeftChild()) this.leftChild = _node;
		else return -1;
	},
	addRight:function(el)
	{
		var _node = null;
		if(this.isBinaryTreeNode(el))	_node = el;
		else	_node = new BX.DataStructure.BinaryTree(el);
		if(!this.hasRightChild()) this.rightChild = _node;
		else return -1;
	},
	preOrderTraverse:function(func)
	{
		func(this);
		if(this.hasLeftChild()) this.leftChild.preOrderTraverse(func);
		if(this.hasRightChild()) this.rightChild.preOrderTraverse(func);
	},
	inOrderTraverse:function(func)
	{
		if(this.hasLeftChild()) this.leftChild.inOrderTraverse(func);
		func(this);
		if(this.hasRightChild()) this.rightChild.inOrderTraverse(func);
	},
	postOrderTraverse:function(func)
	{
		if(this.hasLeftChild()) this.leftChild.postOrderTraverse(func);
		if(this.hasRightChild()) this.rightChild.postOrderTraverse(func);
		func(this);
	},
	levelOrderTraverse:function(func)
	{
		var _queue = new BX.DataStructure.Queue();
		var _tree = this;
		var _treeNode = null;
		func(_tree);
		while(_tree != null)
		{
			if(_tree.hasLeftChild()) _queue.enQueue(_tree.leftChild);
			if(_tree.hasRightChild()) _queue.enQueue(_tree.rightChild);
			if((_treeNode = _queue.deQueue()) != null) func(_treeNode);
			_tree = _treeNode;
		}
	},
	traverse:function(func)
	{
		this.preOrderTraverse(func);
	},
	toString:function()
	{
		var _string = '';
		this.levelOrderTraverse(
			function(treeNode){ 
				if(treeNode.data!=null) 
					_string += treeNode.data.toString();
			}
		);
		return _string;
	}
}
var DS = BX.DataStructure;