Subversion Repositories Applications.papyrus

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
};

}