From e44a7e37b6c7b5961adaffc62b9042b8d442938e Mon Sep 17 00:00:00 2001
From: mensonge <mensonge@b3834d28-1941-0410-a4f8-b48e95affb8f>
Date: Thu, 13 Nov 2008 09:49:11 +0000
Subject: New feature: basic Ajax suggestion for tags and implementation of
 Dojo toolkit

git-svn-id: https://semanticscuttle.svn.sourceforge.net/svnroot/semanticscuttle/trunk@151 b3834d28-1941-0410-a4f8-b48e95affb8f
---
 includes/js/dojox/collections/BinaryTree.js | 211 ++++++++++++++++++++++++++++
 1 file changed, 211 insertions(+)
 create mode 100644 includes/js/dojox/collections/BinaryTree.js

(limited to 'includes/js/dojox/collections/BinaryTree.js')

diff --git a/includes/js/dojox/collections/BinaryTree.js b/includes/js/dojox/collections/BinaryTree.js
new file mode 100644
index 0000000..edd9fbf
--- /dev/null
+++ b/includes/js/dojox/collections/BinaryTree.js
@@ -0,0 +1,211 @@
+if(!dojo._hasResource["dojox.collections.BinaryTree"]){ //_hasResource checks added by build. Do not use _hasResource directly in your code.
+dojo._hasResource["dojox.collections.BinaryTree"] = true;
+dojo.provide("dojox.collections.BinaryTree");
+dojo.require("dojox.collections._base");
+
+dojox.collections.BinaryTree=function(data){
+	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);
+	}
+}
+dojox.collections.BinaryTree.TraversalMethods={
+	Preorder: 1, Inorder: 2, Postorder: 3
+};
+
+}
-- 
cgit v1.2.3