Subversion Repositories Applications.papyrus

Rev

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