a:23:{s:9:"#provides";s:28:"dojox.collections.BinaryTree";s:9:"#resource";s:25:"collections/BinaryTree.js";s:9:"#requires";a:1:{i:0;a:2:{i:0;s:6:"common";i:1;s:23:"dojox.collections._base";}}s:45:"dojox.collections.BinaryTree.TraversalMethods";a:2:{s:4:"type";s:6:"Object";s:7:"summary";s:0:"";}s:54:"dojox.collections.BinaryTree.TraversalMethods.Preorder";a:1:{s:7:"summary";s:0:"";}s:28:"dojox.collections.BinaryTree";a:5:{s:4:"type";s:8:"Function";s:10:"parameters";a:1:{s:4:"data";a:1:{s:4:"type";s:0:"";}}s:6:"source";s:4469:"	function node(data, rnode, lnode){
		this.value=data||null;
		this.right=rnode||null;
		this.left=lnode||null;
		this.clone=function(){
			var c=new node();
			if(this.value.value){
				c.value=this.value.clone();
			}else{ 
				c.value=this.value;
			}
			if(this.left!=null){
				c.left=this.left.clone();
			}
			if(this.right!=null){
				c.right=this.right.clone();
			}
			return c;
		}
		this.compare=function(n){
			if(this.value>n.value){ return 1; }
			if(this.value<n.value){ return -1; }
			return 0;
		}
		this.compareData=function(d){
			if(this.value>d){ return 1; }
			if(this.value<d){ return -1; }
			return 0;
		}
	}


	function inorderTraversalBuildup(current, a){
		if(current){
			inorderTraversalBuildup(current.left, a);
			a.push(current.value);
			inorderTraversalBuildup(current.right, a);
		}
	}


	function preorderTraversal(current, sep){
		var s="";
		if (current){
			s=current.value.toString() + sep;
			s+=preorderTraversal(current.left, sep);
			s+=preorderTraversal(current.right, sep);
		}
		return s;
	}
	function inorderTraversal(current, sep){
		var s="";
		if (current){
			s=inorderTraversal(current.left, sep);
			s+=current.value.toString() + sep;
			s+=inorderTraversal(current.right, sep);
		}
		return s;
	}
	function postorderTraversal(current, sep){
		var s="";
		if (current){
			s=postorderTraversal(current.left, sep);
			s+=postorderTraversal(current.right, sep);
			s+=current.value.toString() + sep;
		}
		return s;
	}

	
	function searchHelper(current, data){
		if(!current){ return null; }
		var i=current.compareData(data);
		if(i==0){ return current; }
		if(i>0){ return searchHelper(current.left, data); }
		else{ return searchHelper(current.right, data); }
	}


	this.add=function(data){
		var n=new node(data);
		var i;
		var current=root;
		var parent=null;
		while(current){
			i=current.compare(n);
			if(i==0){ return; }
			parent=current;
			if(i>0){ current=current.left; }
			else{ current=current.right; }
		}
		this.count++;
		if(!parent){
			root=n;
		}else{
			i=parent.compare(n);
			if(i>0){ 
				parent.left=n;
			}else{
				parent.right=n;
			}
		}
	};
	this.clear=function(){
		root=null;
		this.count=0;
	};
	this.clone=function(){
		var c=new dojox.collections.BinaryTree();
		var itr=this.getIterator();
		while(!itr.atEnd()){
			c.add(itr.get());
		}
		return c;
	};
	this.contains=function(data){
		return this.search(data) != null;
	};
	this.deleteData=function(data){
		var current=root;
		var parent=null;
		var i=current.compareData(data);
		while(i!=0&&current!=null){
			if(i>0){
				parent=current;
				current=current.left;
			}else if(i<0){
				parent=current;
				current=current.right;
			}
			i=current.compareData(data);
		}
		if(!current){ return; }
		this.count--;
		if(!current.right){
			if(!parent){ 
				root=current.left;
			}else{
				i=parent.compare(current);
				if(i>0){ parent.left=current.left; }
				else if(i<0){ parent.right=current.left; }
			}
		} 
		else if(!current.right.left){
			if(!parent){
				root=current.right;
			}else{
				i=parent.compare(current);
				if(i>0){ parent.left=current.right; }
				else if(i<0){ parent.right=current.right; }
			}
		}
		else{
			var leftmost=current.right.left;
			var lmParent=current.right;
			while(leftmost.left!=null){
				lmParent=leftmost;
				leftmost=leftmost.left;
			}
			lmParent.left=leftmost.right;
			leftmost.left=current.left;
			leftmost.right=current.right;
			if(!parent){ 
				root=leftmost;
			}else{
				i=parent.compare(current);
				if(i>0){ parent.left=leftmost; }
				else if(i<0){ parent.right=leftmost; }
			}
		}
	};
	this.getIterator=function(){
		var a=[];
		inorderTraversalBuildup(root, a);
		return new dojox.collections.Iterator(a);
	};
	this.search=function(data){
		return searchHelper(root, data);
	};
	this.toString=function(order, sep){
		if(!order){ order=dojox.collections.BinaryTree.TraversalMethods.Inorder; }
		if(!sep){ sep=","; }
		var s="";
		switch(order){
			case dojox.collections.BinaryTree.TraversalMethods.Preorder:
				s=preorderTraversal(root, sep);
				break;
			case dojox.collections.BinaryTree.TraversalMethods.Inorder:
				s=inorderTraversal(root, sep);
				break;
			case dojox.collections.BinaryTree.TraversalMethods.Postorder:
				s=postorderTraversal(root, sep);
				break;
		};
		if(s.length==0){ return ""; }
		else{ return s.substring(0, s.length - sep.length); }
	};


	this.count=0;
	var root=this.root=null;
	if(data){
		this.add(data);
	}";s:9:"classlike";b:1;s:7:"summary";s:0:"";}s:34:"dojox.collections.BinaryTree.value";a:2:{s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:34:"dojox.collections.BinaryTree.right";a:2:{s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:33:"dojox.collections.BinaryTree.left";a:2:{s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:34:"dojox.collections.BinaryTree.count";a:2:{s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:33:"dojox.collections.BinaryTree.root";a:2:{s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:34:"dojox.collections.BinaryTree.clone";a:4:{s:4:"type";s:8:"Function";s:6:"source";s:133:"		var c=new dojox.collections.BinaryTree();
		var itr=this.getIterator();
		while(!itr.atEnd()){
			c.add(itr.get());
		}
		return c;";s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:36:"dojox.collections.BinaryTree.compare";a:5:{s:4:"type";s:8:"Function";s:10:"parameters";a:1:{s:1:"n";a:1:{s:4:"type";s:0:"";}}s:6:"source";s:91:"			if(this.value>n.value){ return 1; }
			if(this.value<n.value){ return -1; }
			return 0;";s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:40:"dojox.collections.BinaryTree.compareData";a:5:{s:4:"type";s:8:"Function";s:10:"parameters";a:1:{s:1:"d";a:1:{s:4:"type";s:0:"";}}s:6:"source";s:79:"			if(this.value>d){ return 1; }
			if(this.value<d){ return -1; }
			return 0;";s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:32:"dojox.collections.BinaryTree.add";a:5:{s:4:"type";s:8:"Function";s:10:"parameters";a:1:{s:4:"data";a:1:{s:4:"type";s:0:"";}}s:6:"source";s:376:"		var n=new node(data);
		var i;
		var current=root;
		var parent=null;
		while(current){
			i=current.compare(n);
			if(i==0){ return; }
			parent=current;
			if(i>0){ current=current.left; }
			else{ current=current.right; }
		}
		this.count++;
		if(!parent){
			root=n;
		}else{
			i=parent.compare(n);
			if(i>0){ 
				parent.left=n;
			}else{
				parent.right=n;
			}
		}";s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:34:"dojox.collections.BinaryTree.clear";a:4:{s:4:"type";s:8:"Function";s:6:"source";s:28:"		root=null;
		this.count=0;";s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:37:"dojox.collections.BinaryTree.contains";a:5:{s:4:"type";s:8:"Function";s:10:"parameters";a:1:{s:4:"data";a:1:{s:4:"type";s:0:"";}}s:6:"source";s:35:"		return this.search(data) != null;";s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:39:"dojox.collections.BinaryTree.deleteData";a:5:{s:4:"type";s:8:"Function";s:10:"parameters";a:1:{s:4:"data";a:1:{s:4:"type";s:0:"";}}s:6:"source";s:1147:"		var current=root;
		var parent=null;
		var i=current.compareData(data);
		while(i!=0&&current!=null){
			if(i>0){
				parent=current;
				current=current.left;
			}else if(i<0){
				parent=current;
				current=current.right;
			}
			i=current.compareData(data);
		}
		if(!current){ return; }
		this.count--;
		if(!current.right){
			if(!parent){ 
				root=current.left;
			}else{
				i=parent.compare(current);
				if(i>0){ parent.left=current.left; }
				else if(i<0){ parent.right=current.left; }
			}
		} 
		else if(!current.right.left){
			if(!parent){
				root=current.right;
			}else{
				i=parent.compare(current);
				if(i>0){ parent.left=current.right; }
				else if(i<0){ parent.right=current.right; }
			}
		}
		else{
			var leftmost=current.right.left;
			var lmParent=current.right;
			while(leftmost.left!=null){
				lmParent=leftmost;
				leftmost=leftmost.left;
			}
			lmParent.left=leftmost.right;
			leftmost.left=current.left;
			leftmost.right=current.right;
			if(!parent){ 
				root=leftmost;
			}else{
				i=parent.compare(current);
				if(i>0){ parent.left=leftmost; }
				else if(i<0){ parent.right=leftmost; }
			}
		}";s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:40:"dojox.collections.BinaryTree.getIterator";a:4:{s:4:"type";s:8:"Function";s:6:"source";s:91:"		var a=[];
		inorderTraversalBuildup(root, a);
		return new dojox.collections.Iterator(a);";s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:35:"dojox.collections.BinaryTree.search";a:5:{s:4:"type";s:8:"Function";s:10:"parameters";a:1:{s:4:"data";a:1:{s:4:"type";s:0:"";}}s:6:"source";s:34:"		return searchHelper(root, data);";s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:37:"dojox.collections.BinaryTree.toString";a:5:{s:4:"type";s:8:"Function";s:10:"parameters";a:2:{s:5:"order";a:1:{s:4:"type";s:0:"";}s:3:"sep";a:1:{s:4:"type";s:0:"";}}s:6:"source";s:554:"		if(!order){ order=dojox.collections.BinaryTree.TraversalMethods.Inorder; }
		if(!sep){ sep=","; }
		var s="";
		switch(order){
			case dojox.collections.BinaryTree.TraversalMethods.Preorder:
				s=preorderTraversal(root, sep);
				break;
			case dojox.collections.BinaryTree.TraversalMethods.Inorder:
				s=inorderTraversal(root, sep);
				break;
			case dojox.collections.BinaryTree.TraversalMethods.Postorder:
				s=postorderTraversal(root, sep);
				break;
		};
		if(s.length==0){ return ""; }
		else{ return s.substring(0, s.length - sep.length); }";s:8:"instance";s:28:"dojox.collections.BinaryTree";s:7:"summary";s:0:"";}s:17:"dojox.collections";a:2:{s:4:"type";s:6:"Object";s:7:"summary";s:0:"";}s:5:"dojox";a:2:{s:4:"type";s:6:"Object";s:7:"summary";s:0:"";}}