Subversion Repositories Applications.papyrus

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
2150 mathias 1 
if(!dojo._hasResource["dojox.collections.BinaryTree"]){ //_hasResource checks added by build. Do not use _hasResource directly in your code.
2 
dojo._hasResource["dojox.collections.BinaryTree"] = true;
3 
dojo.provide("dojox.collections.BinaryTree");
4 
dojo.require("dojox.collections._base");
5 
 
6 
dojox.collections.BinaryTree=function(data){
7 
	function node(data, rnode, lnode){
8 
		this.value=data||null;
9 
		this.right=rnode||null;
10 
		this.left=lnode||null;
11 
		this.clone=function(){
12 
			var c=new node();
13 
			if(this.value.value){
14 
				c.value=this.value.clone();
15 
			}else{
16 
				c.value=this.value;
17 
			}
18 
			if(this.left!=null){
19 
				c.left=this.left.clone();
20 
			}
21 
			if(this.right!=null){
22 
				c.right=this.right.clone();
23 
			}
24 
			return c;
25 
		}
26 
		this.compare=function(n){
27 
			if(this.value>n.value){ return 1; }
28 
			if(this.value<n.value){ return -1; }
29 
			return 0;
30 
		}
31 
		this.compareData=function(d){
32 
			if(this.value>d){ return 1; }
33 
			if(this.value<d){ return -1; }
34 
			return 0;
35 
		}
36 
	}
37 
 
38 
	function inorderTraversalBuildup(current, a){
39 
		if(current){
40 
			inorderTraversalBuildup(current.left, a);
41 
			a.push(current.value);
42 
			inorderTraversalBuildup(current.right, a);
43 
		}
44 
	}
45 
 
46 
	function preorderTraversal(current, sep){
47 
		var s="";
48 
		if (current){
49 
			s=current.value.toString() + sep;
50 
			s+=preorderTraversal(current.left, sep);
51 
			s+=preorderTraversal(current.right, sep);
52 
		}
53 
		return s;
54 
	}
55 
	function inorderTraversal(current, sep){
56 
		var s="";
57 
		if (current){
58 
			s=inorderTraversal(current.left, sep);
59 
			s+=current.value.toString() + sep;
60 
			s+=inorderTraversal(current.right, sep);
61 
		}
62 
		return s;
63 
	}
64 
	function postorderTraversal(current, sep){
65 
		var s="";
66 
		if (current){
67 
			s=postorderTraversal(current.left, sep);
68 
			s+=postorderTraversal(current.right, sep);
69 
			s+=current.value.toString() + sep;
70 
		}
71 
		return s;
72 
	}
73 
 
74 
	function searchHelper(current, data){
75 
		if(!current){ return null; }
76 
		var i=current.compareData(data);
77 
		if(i==0){ return current; }
78 
		if(i>0){ return searchHelper(current.left, data); }
79 
		else{ return searchHelper(current.right, data); }
80 
	}
81 
 
82 
	this.add=function(data){
83 
		var n=new node(data);
84 
		var i;
85 
		var current=root;
86 
		var parent=null;
87 
		while(current){
88 
			i=current.compare(n);
89 
			if(i==0){ return; }
90 
			parent=current;
91 
			if(i>0){ current=current.left; }
92 
			else{ current=current.right; }
93 
		}
94 
		this.count++;
95 
		if(!parent){
96 
			root=n;
97 
		}else{
98 
			i=parent.compare(n);
99 
			if(i>0){
100 
				parent.left=n;
101 
			}else{
102 
				parent.right=n;
103 
			}
104 
		}
105 
	};
106 
	this.clear=function(){
107 
		root=null;
108 
		this.count=0;
109 
	};
110 
	this.clone=function(){
111 
		var c=new dojox.collections.BinaryTree();
112 
		var itr=this.getIterator();
113 
		while(!itr.atEnd()){
114 
			c.add(itr.get());
115 
		}
116 
		return c;
117 
	};
118 
	this.contains=function(data){
119 
		return this.search(data) != null;
120 
	};
121 
	this.deleteData=function(data){
122 
		var current=root;
123 
		var parent=null;
124 
		var i=current.compareData(data);
125 
		while(i!=0&&current!=null){
126 
			if(i>0){
127 
				parent=current;
128 
				current=current.left;
129 
			}else if(i<0){
130 
				parent=current;
131 
				current=current.right;
132 
			}
133 
			i=current.compareData(data);
134 
		}
135 
		if(!current){ return; }
136 
		this.count--;
137 
		if(!current.right){
138 
			if(!parent){
139 
				root=current.left;
140 
			}else{
141 
				i=parent.compare(current);
142 
				if(i>0){ parent.left=current.left; }
143 
				else if(i<0){ parent.right=current.left; }
144 
			}
145 
		}
146 
		else if(!current.right.left){
147 
			if(!parent){
148 
				root=current.right;
149 
			}else{
150 
				i=parent.compare(current);
151 
				if(i>0){ parent.left=current.right; }
152 
				else if(i<0){ parent.right=current.right; }
153 
			}
154 
		}
155 
		else{
156 
			var leftmost=current.right.left;
157 
			var lmParent=current.right;
158 
			while(leftmost.left!=null){
159 
				lmParent=leftmost;
160 
				leftmost=leftmost.left;
161 
			}
162 
			lmParent.left=leftmost.right;
163 
			leftmost.left=current.left;
164 
			leftmost.right=current.right;
165 
			if(!parent){
166 
				root=leftmost;
167 
			}else{
168 
				i=parent.compare(current);
169 
				if(i>0){ parent.left=leftmost; }
170 
				else if(i<0){ parent.right=leftmost; }
171 
			}
172 
		}
173 
	};
174 
	this.getIterator=function(){
175 
		var a=[];
176 
		inorderTraversalBuildup(root, a);
177 
		return new dojox.collections.Iterator(a);
178 
	};
179 
	this.search=function(data){
180 
		return searchHelper(root, data);
181 
	};
182 
	this.toString=function(order, sep){
183 
		if(!order){ order=dojox.collections.BinaryTree.TraversalMethods.Inorder; }
184 
		if(!sep){ sep=","; }
185 
		var s="";
186 
		switch(order){
187 
			case dojox.collections.BinaryTree.TraversalMethods.Preorder:
188 
				s=preorderTraversal(root, sep);
189 
				break;
190 
			case dojox.collections.BinaryTree.TraversalMethods.Inorder:
191 
				s=inorderTraversal(root, sep);
192 
				break;
193 
			case dojox.collections.BinaryTree.TraversalMethods.Postorder:
194 
				s=postorderTraversal(root, sep);
195 
				break;
196 
		};
197 
		if(s.length==0){ return ""; }
198 
		else{ return s.substring(0, s.length - sep.length); }
199 
	};
200 
 
201 
	this.count=0;
202 
	var root=this.root=null;
203 
	if(data){
204 
		this.add(data);
205 
	}
206 
}
207 
dojox.collections.BinaryTree.TraversalMethods={
208 
	Preorder: 1, Inorder: 2, Postorder: 3
209 
};
210 
 
211 
}