aboutsummaryrefslogtreecommitdiff
path: root/includes/js/dojox/collections/BinaryTree.js
diff options
context:
space:
mode:
authormensonge <mensonge@b3834d28-1941-0410-a4f8-b48e95affb8f>2008-11-14 15:39:19 +0000
committermensonge <mensonge@b3834d28-1941-0410-a4f8-b48e95affb8f>2008-11-14 15:39:19 +0000
commit1c5685d68f1b73270fb814fe04cbb490eb90ba5f (patch)
tree3d3ada08a934b96fc31531f1327690d7edc6f766 /includes/js/dojox/collections/BinaryTree.js
parent104d59099e048688c4dbac37d72137006e396558 (diff)
downloadsemanticscuttle-1c5685d68f1b73270fb814fe04cbb490eb90ba5f.tar.gz
semanticscuttle-1c5685d68f1b73270fb814fe04cbb490eb90ba5f.tar.bz2
Minor fix: Remove DOJO library (60Mo) replaced by link to Google CDN (online DOJO library)
git-svn-id: https://semanticscuttle.svn.sourceforge.net/svnroot/semanticscuttle/trunk@159 b3834d28-1941-0410-a4f8-b48e95affb8f
Diffstat (limited to 'includes/js/dojox/collections/BinaryTree.js')
-rw-r--r--includes/js/dojox/collections/BinaryTree.js211
1 files changed, 0 insertions, 211 deletions
diff --git a/includes/js/dojox/collections/BinaryTree.js b/includes/js/dojox/collections/BinaryTree.js
deleted file mode 100644
index edd9fbf..0000000
--- a/includes/js/dojox/collections/BinaryTree.js
+++ /dev/null
@@ -1,211 +0,0 @@
-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
-};
-
-}