Subversion Repositories Applications.papyrus

Rev

Rev 1372 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
1318 alexandre_ 1 
/*
2 
	Copyright (c) 2004-2006, The Dojo Foundation
3 
	All Rights Reserved.
4 
 
5 
	Licensed under the Academic Free License version 2.1 or above OR the
6 
	modified BSD license. For more information on Dojo licensing, see:
7 
 
8 
		http://dojotoolkit.org/community/licensing.shtml
9 
*/
10 
 
1422 alexandre_ 11 
 
12 
 
1318 alexandre_ 13 
dojo.provide("dojo.collections.BinaryTree");
14 
dojo.require("dojo.collections.Collections");
15 
dojo.require("dojo.experimental");
16 
dojo.experimental("dojo.collections.BinaryTree");
17 
dojo.collections.BinaryTree = function (data) {
18 
	function node(data, rnode, lnode) {
19 
		this.value = data || null;
20 
		this.right = rnode || null;
21 
		this.left = lnode || null;
22 
		this.clone = function () {
23 
			var c = new node();
24 
			if (this.value.value) {
25 
				c.value = this.value.clone();
26 
			} else {
27 
				c.value = this.value;
28 
			}
29 
			if (this.left) {
30 
				c.left = this.left.clone();
31 
			}
32 
			if (this.right) {
33 
				c.right = this.right.clone();
34 
			}
35 
		};
36 
		this.compare = function (n) {
37 
			if (this.value > n.value) {
38 
				return 1;
39 
			}
40 
			if (this.value < n.value) {
41 
				return -1;
42 
			}
43 
			return 0;
44 
		};
45 
		this.compareData = function (d) {
46 
			if (this.value > d) {
47 
				return 1;
48 
			}
49 
			if (this.value < d) {
50 
				return -1;
51 
			}
52 
			return 0;
53 
		};
54 
	}
55 
	function inorderTraversalBuildup(current, a) {
56 
		if (current) {
57 
			inorderTraversalBuildup(current.left, a);
58 
			a.add(current);
59 
			inorderTraversalBuildup(current.right, a);
60 
		}
61 
	}
62 
	function preorderTraversal(current, sep) {
63 
		var s = "";
64 
		if (current) {
65 
			s = current.value.toString() + sep;
66 
			s += preorderTraversal(current.left, sep);
67 
			s += preorderTraversal(current.right, sep);
68 
		}
69 
		return s;
70 
	}
71 
	function inorderTraversal(current, sep) {
72 
		var s = "";
73 
		if (current) {
74 
			s = inorderTraversal(current.left, sep);
75 
			s += current.value.toString() + sep;
76 
			s += inorderTraversal(current.right, sep);
77 
		}
78 
		return s;
79 
	}
80 
	function postorderTraversal(current, sep) {
81 
		var s = "";
82 
		if (current) {
83 
			s = postorderTraversal(current.left, sep);
84 
			s += postorderTraversal(current.right, sep);
85 
			s += current.value.toString() + sep;
86 
		}
87 
		return s;
88 
	}
89 
	function searchHelper(current, data) {
90 
		if (!current) {
91 
			return null;
92 
		}
93 
		var i = current.compareData(data);
94 
		if (i == 0) {
95 
			return current;
96 
		}
97 
		if (i > 0) {
98 
			return searchHelper(current.left, data);
99 
		} else {
100 
			return searchHelper(current.right, data);
101 
		}
102 
	}
103 
	this.add = function (data) {
104 
		var n = new node(data);
105 
		var i;
106 
		var current = root;
107 
		var parent = null;
108 
		while (current) {
109 
			i = current.compare(n);
110 
			if (i == 0) {
111 
				return;
112 
			}
113 
			parent = current;
114 
			if (i > 0) {
115 
				current = current.left;
116 
			} else {
117 
				current = current.right;
118 
			}
119 
		}
120 
		this.count++;
121 
		if (!parent) {
122 
			root = n;
123 
		} else {
124 
			i = parent.compare(n);
125 
			if (i > 0) {
126 
				parent.left = n;
127 
			} else {
128 
				parent.right = n;
129 
			}
130 
		}
131 
	};
132 
	this.clear = function () {
133 
		root = null;
134 
		this.count = 0;
135 
	};
136 
	this.clone = function () {
137 
		var c = new dojo.collections.BinaryTree();
138 
		c.root = root.clone();
139 
		c.count = this.count;
140 
		return c;
141 
	};
142 
	this.contains = function (data) {
143 
		return this.search(data) != null;
144 
	};
145 
	this.deleteData = function (data) {
146 
		var current = root;
147 
		var parent = null;
148 
		var i = current.compareData(data);
149 
		while (i != 0 && current != null) {
150 
			if (i > 0) {
151 
				parent = current;
152 
				current = current.left;
153 
			} else {
154 
				if (i < 0) {
155 
					parent = current;
156 
					current = current.right;
157 
				}
158 
			}
159 
			i = current.compareData(data);
160 
		}
161 
		if (!current) {
162 
			return;
163 
		}
164 
		this.count--;
165 
		if (!current.right) {
166 
			if (!parent) {
167 
				root = current.left;
168 
			} else {
169 
				i = parent.compare(current);
170 
				if (i > 0) {
171 
					parent.left = current.left;
172 
				} else {
173 
					if (i < 0) {
174 
						parent.right = current.left;
175 
					}
176 
				}
177 
			}
178 
		} else {
179 
			if (!current.right.left) {
180 
				if (!parent) {
181 
					root = current.right;
182 
				} else {
183 
					i = parent.compare(current);
184 
					if (i > 0) {
185 
						parent.left = current.right;
186 
					} else {
187 
						if (i < 0) {
188 
							parent.right = current.right;
189 
						}
190 
					}
191 
				}
192 
			} else {
193 
				var leftmost = current.right.left;
194 
				var lmParent = current.right;
195 
				while (leftmost.left != null) {
196 
					lmParent = leftmost;
197 
					leftmost = leftmost.left;
198 
				}
199 
				lmParent.left = leftmost.right;
200 
				leftmost.left = current.left;
201 
				leftmost.right = current.right;
202 
				if (!parent) {
203 
					root = leftmost;
204 
				} else {
205 
					i = parent.compare(current);
206 
					if (i > 0) {
207 
						parent.left = leftmost;
208 
					} else {
209 
						if (i < 0) {
210 
							parent.right = leftmost;
211 
						}
212 
					}
213 
				}
214 
			}
215 
		}
216 
	};
217 
	this.getIterator = function () {
218 
		var a = [];
219 
		inorderTraversalBuildup(root, a);
220 
		return new dojo.collections.Iterator(a);
221 
	};
222 
	this.search = function (data) {
223 
		return searchHelper(root, data);
224 
	};
225 
	this.toString = function (order, sep) {
226 
		if (!order) {
227 
			var order = dojo.collections.BinaryTree.TraversalMethods.Inorder;
228 
		}
229 
		if (!sep) {
230 
			var sep = " ";
231 
		}
232 
		var s = "";
233 
		switch (order) {
234 
		  case dojo.collections.BinaryTree.TraversalMethods.Preorder:
235 
			s = preorderTraversal(root, sep);
236 
			break;
237 
		  case dojo.collections.BinaryTree.TraversalMethods.Inorder:
238 
			s = inorderTraversal(root, sep);
239 
			break;
240 
		  case dojo.collections.BinaryTree.TraversalMethods.Postorder:
241 
			s = postorderTraversal(root, sep);
242 
			break;
243 
		}
244 
		if (s.length == 0) {
245 
			return "";
246 
		} else {
247 
			return s.substring(0, s.length - sep.length);
248 
		}
249 
	};
250 
	this.count = 0;
251 
	var root = this.root = null;
252 
	if (data) {
253 
		this.add(data);
254 
	}
255 
};
256 
dojo.collections.BinaryTree.TraversalMethods = {Preorder:1, Inorder:2, Postorder:3};
257