| /* |
| Copyright (c) 2004-2009, The Dojo Foundation All Rights Reserved. |
| Available via Academic Free License >= 2.1 OR the modified BSD license. |
| see: http://dojotoolkit.org/license for details |
| */ |
| |
| |
| if(!dojo._hasResource["dojox.collections.BinaryTree"]){ |
| dojo._hasResource["dojox.collections.BinaryTree"]=true; |
| dojo.provide("dojox.collections.BinaryTree"); |
| dojo.require("dojox.collections._base"); |
| dojox.collections.BinaryTree=function(_1){ |
| function _2(_3,_4,_5){ |
| this.value=_3||null; |
| this.right=_4||null; |
| this.left=_5||null; |
| this.clone=function(){ |
| var c=new _2(); |
| 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 _6(_7,a){ |
| if(_7){ |
| _6(_7.left,a); |
| a.push(_7.value); |
| _6(_7.right,a); |
| } |
| }; |
| function _8(_9,_a){ |
| var s=""; |
| if(_9){ |
| s=_9.value.toString()+_a; |
| s+=_8(_9.left,_a); |
| s+=_8(_9.right,_a); |
| } |
| return s; |
| }; |
| function _b(_c,_d){ |
| var s=""; |
| if(_c){ |
| s=_b(_c.left,_d); |
| s+=_c.value.toString()+_d; |
| s+=_b(_c.right,_d); |
| } |
| return s; |
| }; |
| function _e(_f,sep){ |
| var s=""; |
| if(_f){ |
| s=_e(_f.left,sep); |
| s+=_e(_f.right,sep); |
| s+=_f.value.toString()+sep; |
| } |
| return s; |
| }; |
| function _10(_11,_12){ |
| if(!_11){ |
| return null; |
| } |
| var i=_11.compareData(_12); |
| if(i==0){ |
| return _11; |
| } |
| if(i>0){ |
| return _10(_11.left,_12); |
| }else{ |
| return _10(_11.right,_12); |
| } |
| }; |
| this.add=function(_13){ |
| var n=new _2(_13); |
| var i; |
| var _14=_15; |
| var _16=null; |
| while(_14){ |
| i=_14.compare(n); |
| if(i==0){ |
| return; |
| } |
| _16=_14; |
| if(i>0){ |
| _14=_14.left; |
| }else{ |
| _14=_14.right; |
| } |
| } |
| this.count++; |
| if(!_16){ |
| _15=n; |
| }else{ |
| i=_16.compare(n); |
| if(i>0){ |
| _16.left=n; |
| }else{ |
| _16.right=n; |
| } |
| } |
| }; |
| this.clear=function(){ |
| _15=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(_17){ |
| return this.search(_17)!=null; |
| }; |
| this.deleteData=function(_18){ |
| var _19=_15; |
| var _1a=null; |
| var i=_19.compareData(_18); |
| while(i!=0&&_19!=null){ |
| if(i>0){ |
| _1a=_19; |
| _19=_19.left; |
| }else{ |
| if(i<0){ |
| _1a=_19; |
| _19=_19.right; |
| } |
| } |
| i=_19.compareData(_18); |
| } |
| if(!_19){ |
| return; |
| } |
| this.count--; |
| if(!_19.right){ |
| if(!_1a){ |
| _15=_19.left; |
| }else{ |
| i=_1a.compare(_19); |
| if(i>0){ |
| _1a.left=_19.left; |
| }else{ |
| if(i<0){ |
| _1a.right=_19.left; |
| } |
| } |
| } |
| }else{ |
| if(!_19.right.left){ |
| if(!_1a){ |
| _15=_19.right; |
| }else{ |
| i=_1a.compare(_19); |
| if(i>0){ |
| _1a.left=_19.right; |
| }else{ |
| if(i<0){ |
| _1a.right=_19.right; |
| } |
| } |
| } |
| }else{ |
| var _1b=_19.right.left; |
| var _1c=_19.right; |
| while(_1b.left!=null){ |
| _1c=_1b; |
| _1b=_1b.left; |
| } |
| _1c.left=_1b.right; |
| _1b.left=_19.left; |
| _1b.right=_19.right; |
| if(!_1a){ |
| _15=_1b; |
| }else{ |
| i=_1a.compare(_19); |
| if(i>0){ |
| _1a.left=_1b; |
| }else{ |
| if(i<0){ |
| _1a.right=_1b; |
| } |
| } |
| } |
| } |
| } |
| }; |
| this.getIterator=function(){ |
| var a=[]; |
| _6(_15,a); |
| return new dojox.collections.Iterator(a); |
| }; |
| this.search=function(_1d){ |
| return _10(_15,_1d); |
| }; |
| this.toString=function(_1e,sep){ |
| if(!_1e){ |
| _1e=dojox.collections.BinaryTree.TraversalMethods.Inorder; |
| } |
| if(!sep){ |
| sep=","; |
| } |
| var s=""; |
| switch(_1e){ |
| case dojox.collections.BinaryTree.TraversalMethods.Preorder: |
| s=_8(_15,sep); |
| break; |
| case dojox.collections.BinaryTree.TraversalMethods.Inorder: |
| s=_b(_15,sep); |
| break; |
| case dojox.collections.BinaryTree.TraversalMethods.Postorder: |
| s=_e(_15,sep); |
| break; |
| } |
| if(s.length==0){ |
| return ""; |
| }else{ |
| return s.substring(0,s.length-sep.length); |
| } |
| }; |
| this.count=0; |
| var _15=this.root=null; |
| if(_1){ |
| this.add(_1); |
| } |
| }; |
| dojox.collections.BinaryTree.TraversalMethods={Preorder:1,Inorder:2,Postorder:3}; |
| } |