WebSVN – Applications.papyrus – Diff – /trunk/api/js/dojo/src/collections/BinaryTree.js


/*
	Copyright (c) 2004-2006, The Dojo Foundation
	All Rights Reserved.
 
	Licensed under the Academic Free License version 2.1 or above OR the
	modified BSD license. For more information on Dojo licensing, see:
 
		http://dojotoolkit.org/community/licensing.shtml
*/
 
 
 
dojo.provide("dojo.collections.BinaryTree");
dojo.require("dojo.collections.Collections");
dojo.require("dojo.experimental");
dojo.experimental("dojo.collections.BinaryTree");
dojo.collections.BinaryTree = function (data) {
	function node(data, rnode, lnode) {
		this.value = data || null;
		this.right = rnode || null;
		this.left = lnode || null;
		this.clone = function () {
			var c = new node();
			if (this.value.value) {
				c.value = this.value.clone();
			} else {
				c.value = this.value;
			}
			if (this.left) {
				c.left = this.left.clone();
			}
			if (this.right) {
				c.right = this.right.clone();
			}
		};
		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 inorderTraversalBuildup(current, a) {
		if (current) {
			inorderTraversalBuildup(current.left, a);
			a.add(current);
			inorderTraversalBuildup(current.right, a);
		}
	}
	function preorderTraversal(current, sep) {
		var s = "";
		if (current) {
			s = current.value.toString() + sep;
			s += preorderTraversal(current.left, sep);
			s += preorderTraversal(current.right, sep);
		}
		return s;
	}
	function inorderTraversal(current, sep) {
		var s = "";
		if (current) {
			s = inorderTraversal(current.left, sep);
			s += current.value.toString() + sep;
			s += inorderTraversal(current.right, sep);
		}
		return s;
	}
	function postorderTraversal(current, sep) {
		var s = "";
		if (current) {
			s = postorderTraversal(current.left, sep);
			s += postorderTraversal(current.right, sep);
			s += current.value.toString() + sep;
		}
		return s;
	}
	function searchHelper(current, data) {
		if (!current) {
			return null;
		}
		var i = current.compareData(data);
		if (i == 0) {
			return current;
		}
		if (i > 0) {
			return searchHelper(current.left, data);
		} else {
			return searchHelper(current.right, data);
		}
	}
	this.add = function (data) {
		var n = new node(data);
		var i;
		var current = root;
		var parent = null;
		while (current) {
			i = current.compare(n);
			if (i == 0) {
				return;
			}
			parent = current;
			if (i > 0) {
				current = current.left;
			} else {
				current = current.right;
			}
		}
		this.count++;
		if (!parent) {
			root = n;
		} else {
			i = parent.compare(n);
			if (i > 0) {
				parent.left = n;
			} else {
				parent.right = n;
			}
		}
	};
	this.clear = function () {
		root = null;
		this.count = 0;
	};
	this.clone = function () {
		var c = new dojo.collections.BinaryTree();
		c.root = root.clone();
		c.count = this.count;
		return c;
	};
	this.contains = function (data) {
		return this.search(data) != null;
	};
	this.deleteData = function (data) {
		var current = root;
		var parent = null;
		var i = current.compareData(data);
		while (i != 0 && current != null) {
			if (i > 0) {
				parent = current;
				current = current.left;
			} else {
				if (i < 0) {
					parent = current;
					current = current.right;
				}
			}
			i = current.compareData(data);
		}
		if (!current) {
			return;
		}
		this.count--;
		if (!current.right) {
			if (!parent) {
				root = current.left;
			} else {
				i = parent.compare(current);
				if (i > 0) {
					parent.left = current.left;
				} else {
					if (i < 0) {
						parent.right = current.left;
					}
				}
			}
		} else {
			if (!current.right.left) {
				if (!parent) {
					root = current.right;
				} else {
					i = parent.compare(current);
					if (i > 0) {
						parent.left = current.right;
					} else {
						if (i < 0) {
							parent.right = current.right;
						}
					}
				}
			} else {
				var leftmost = current.right.left;
				var lmParent = current.right;
				while (leftmost.left != null) {
					lmParent = leftmost;
					leftmost = leftmost.left;
				}
				lmParent.left = leftmost.right;
				leftmost.left = current.left;
				leftmost.right = current.right;
				if (!parent) {
					root = leftmost;
				} else {
					i = parent.compare(current);
					if (i > 0) {
						parent.left = leftmost;
					} else {
						if (i < 0) {
							parent.right = leftmost;
						}
					}
				}
			}
		}
	};
	this.getIterator = function () {
		var a = [];
		inorderTraversalBuildup(root, a);
		return new dojo.collections.Iterator(a);
	};
	this.search = function (data) {
		return searchHelper(root, data);
	};
	this.toString = function (order, sep) {
		if (!order) {
			var order = dojo.collections.BinaryTree.TraversalMethods.Inorder;
		}
		if (!sep) {
			var sep = " ";
		}
		var s = "";
		switch (order) {
		  case dojo.collections.BinaryTree.TraversalMethods.Preorder:
			s = preorderTraversal(root, sep);
			break;
		  case dojo.collections.BinaryTree.TraversalMethods.Inorder:
			s = inorderTraversal(root, sep);
			break;
		  case dojo.collections.BinaryTree.TraversalMethods.Postorder:
			s = postorderTraversal(root, sep);
			break;
		}
		if (s.length == 0) {
			return "";
		} else {
			return s.substring(0, s.length - sep.length);
		}
	};
	this.count = 0;
	var root = this.root = null;
	if (data) {
		this.add(data);
	}
};
dojo.collections.BinaryTree.TraversalMethods = {Preorder:1, Inorder:2, Postorder:3};
 

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

Subversion Repositories Applications.papyrus

(root)/trunk/api/js/dojo/src/collections/BinaryTree.js – Rev 1318 → 1422