Subversion Repositories Applications.papyrus

Rev

Rev 1318 | 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