Debian Codegraph @

closure-library/closure/goog/structs/treenode_test.js

raw
1 // Copyright 2010 The Closure Library Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 goog.provide('goog.structs.TreeNodeTest');
16 goog.setTestOnly('goog.structs.TreeNodeTest');
17
18 goog.require('goog.structs.TreeNode');
19 goog.require('goog.testing.jsunit');
20
21 function testConstructor() {
22 var node = new goog.structs.TreeNode('key', 'value');
23 assertEquals('key', 'key', node.getKey());
24 assertEquals('value', 'value', node.getValue());
25 assertNull('parent', node.getParent());
26 assertArrayEquals('children', [], node.getChildren());
27 assertTrue('leaf', node.isLeaf());
28 }
29
30 function testClone() {
31 var node1 = new goog.structs.TreeNode(1, '1');
32 var node2 = new goog.structs.TreeNode(2, '2');
33 var node3 = new goog.structs.TreeNode(3, '3');
34 node1.addChild(node2);
35 node2.addChild(node3);
36
37 var clone = node2.clone();
38 assertEquals('key', 2, clone.getKey());
39 assertEquals('value', '2', clone.getValue());
40 assertNull('parent', clone.getParent());
41 assertArrayEquals('children', [], clone.getChildren());
42 }
43
44 function testDeepClone() {
45 var node1 = new goog.structs.TreeNode(1, '1');
46 var node2 = new goog.structs.TreeNode(2, '2');
47 var node3 = new goog.structs.TreeNode(3, '3');
48 node1.addChild(node2);
49 node2.addChild(node3);
50
51 var clone = node2.deepClone();
52 assertEquals('key', 2, clone.getKey());
53 assertEquals('value', '2', clone.getValue());
54 assertNull('parent', clone.getParent());
55 assertEquals('number of children', 1, clone.getChildren().length);
56 assertEquals('first child key', 3, clone.getChildAt(0).getKey());
57 assertNotEquals('first child has been cloned', node3, clone.getChildAt(0));
58 }
59
60 function testGetParent() {
61 var node1 = new goog.structs.TreeNode(1, null);
62 var node2 = new goog.structs.TreeNode(2, null);
63 node1.addChild(node2);
64 assertEquals('parent', node1, node2.getParent());
65 assertNull('orphan', node1.getParent());
66 }
67
68 function testIsLeaf() {
69 var node1 = new goog.structs.TreeNode(1, null);
70 var node2 = new goog.structs.TreeNode(2, null);
71 node1.addChild(node2);
72 assertFalse('not leaf', node1.isLeaf());
73 assertTrue('leaf', node2.isLeaf());
74 }
75
76 function testIsLastChild() {
77 var node1 = new goog.structs.TreeNode(1, '1');
78 var node2 = new goog.structs.TreeNode(2, '2');
79 var node3 = new goog.structs.TreeNode(3, '3');
80 node1.addChild(node2);
81 node1.addChild(node3);
82 assertFalse('root', node1.isLastChild());
83 assertFalse('first child out of the two', node2.isLastChild());
84 assertTrue('second child out of the two', node3.isLastChild());
85 }
86
87 function testGetChildren() {
88 var node1 = new goog.structs.TreeNode(1, null);
89 var node2 = new goog.structs.TreeNode(2, null);
90 node1.addChild(node2);
91 assertArrayEquals('1 child', [node2], node1.getChildren());
92 assertArrayEquals('no children', [], node2.getChildren());
93 }
94
95 function testGetChildAt() {
96 var node1 = new goog.structs.TreeNode(1, null);
97 var node2 = new goog.structs.TreeNode(2, null);
98 node1.addChild(node2);
99 assertNull('index too low', node1.getChildAt(-1));
100 assertEquals('first child', node2, node1.getChildAt(0));
101 assertNull('index too high', node1.getChildAt(1));
102 assertNull('no children', node2.getChildAt(0));
103 }
104
105 function testGetChildCount() {
106 var node1 = new goog.structs.TreeNode(1, null);
107 var node2 = new goog.structs.TreeNode(2, null);
108 node1.addChild(node2);
109 assertEquals('child count of root node', 1, node1.getChildCount());
110 assertEquals('child count of leaf node', 0, node2.getChildCount());
111 }
112
113 function testGetDepth() {
114 var node1 = new goog.structs.TreeNode(1, null);
115 var node2 = new goog.structs.TreeNode(2, null);
116 var node3 = new goog.structs.TreeNode(3, null);
117 node1.addChild(node2);
118 node2.addChild(node3);
119 assertEquals('no parent', 0, node1.getDepth());
120 assertEquals('1 ancestor', 1, node2.getDepth());
121 assertEquals('2 ancestors', 2, node3.getDepth());
122 }
123
124 function testGetAncestors() {
125 var node1 = new goog.structs.TreeNode(1, null);
126 var node2 = new goog.structs.TreeNode(2, null);
127 var node3 = new goog.structs.TreeNode(3, null);
128 node1.addChild(node2);
129 node2.addChild(node3);
130 assertArrayEquals('no ancestors', [], node1.getAncestors());
131 assertArrayEquals('2 ancestors', [node2, node1], node3.getAncestors());
132 }
133
134 function testGetRoot() {
135 var node1 = new goog.structs.TreeNode(1, null);
136 var node2 = new goog.structs.TreeNode(2, null);
137 node1.addChild(node2);
138 assertEquals('no ancestors', node1, node1.getRoot());
139 assertEquals('has ancestors', node1, node2.getRoot());
140 }
141
142 function testGetSubtreeKeys() {
143 var root = new goog.structs.TreeNode('root', null);
144 var child1 = new goog.structs.TreeNode('child1', null);
145 var child2 = new goog.structs.TreeNode('child2', null);
146 var grandchild = new goog.structs.TreeNode('grandchild', null);
147 root.addChild(child1);
148 root.addChild(child2);
149 child1.addChild(grandchild);
150 assertArrayEquals(
151 'node hierarchy', ['child1', ['grandchild'], 'child2'],
152 root.getSubtreeKeys());
153 }
154
155 function testContains() {
156 var node1 = new goog.structs.TreeNode(1, null);
157 var node2 = new goog.structs.TreeNode(2, null);
158 var node3 = new goog.structs.TreeNode(3, null);
159 var node4 = new goog.structs.TreeNode(4, null);
160 node1.addChild(node2);
161 node2.addChild(node3);
162 node2.addChild(node4);
163
164 assertTrue('parent', node1.contains(node2));
165 assertTrue('grandparent', node1.contains(node3));
166 assertFalse('child', node2.contains(node1));
167 assertFalse('grandchild', node3.contains(node1));
168 assertFalse('sibling', node3.contains(node4));
169 }
170
171 function testFindCommonAncestor() {
172 var findCommonAncestor = goog.structs.TreeNode.findCommonAncestor;
173 var node1 = new goog.structs.TreeNode(1, null);
174 var node2 = new goog.structs.TreeNode(2, null);
175 var node3 = new goog.structs.TreeNode(3, null);
176 var node4 = new goog.structs.TreeNode(4, null);
177 var node5 = new goog.structs.TreeNode(5, null);
178 node1.addChild(node2);
179 node2.addChild(node3);
180 node1.addChild(node4);
181
182 assertNull('0 nodes', findCommonAncestor());
183 assertEquals('1 node', node2, findCommonAncestor(node2));
184 assertEquals('same nodes', node3, findCommonAncestor(node3, node3));
185 assertEquals('node and child node', node2, findCommonAncestor(node2, node3));
186 assertEquals('node and parent node', node1, findCommonAncestor(node2, node1));
187 assertEquals('siblings', node1, findCommonAncestor(node2, node4));
188 assertEquals(
189 'all nodes', node1, findCommonAncestor(node2, node3, node4, node1));
190 assertNull('disconnected nodes', findCommonAncestor(node3, node5));
191 }
192
193 function testGetNodeByKey() {
194 var node1 = new goog.structs.TreeNode(1, null);
195 var node2 = new goog.structs.TreeNode(2, null);
196 var node3 = new goog.structs.TreeNode(3, null);
197 var node4 = new goog.structs.TreeNode(4, null);
198 var node5 = new goog.structs.TreeNode(2, null);
199 var node6 = new goog.structs.TreeNode(3, null);
200 node1.addChild(node2);
201 node2.addChild(node3);
202 node1.addChild(node4);
203 node4.addChild(node5);
204 node1.addChild(node6);
205
206 assertEquals('root', node1, node1.getNodeByKey(1));
207 assertEquals('child with unique key', node5, node4.getNodeByKey(2));
208 assertEquals('child with duplicate keys', node2, node1.getNodeByKey(2));
209 assertEquals('grandchild with duplicate keys', node3, node1.getNodeByKey(3));
210 assertNull('disconnected', node2.getNodeByKey(4));
211 assertNull('missing', node1.getNodeByKey(5));
212 }
213
214 function testForEachChild() {
215 var node1 = new goog.structs.TreeNode(1, null);
216 var node2 = new goog.structs.TreeNode(2, null);
217 var node3 = new goog.structs.TreeNode(3, null);
218 node1.addChild(node2);
219 node1.addChild(node3);
220
221 var thisContext = {};
222 var visitedNodes = [];
223 var indices = [];
224 node1.forEachChild(function(node, index, children) {
225 assertEquals('value of this', thisContext, this);
226 visitedNodes.push(node);
227 indices.push(index);
228 assertArrayEquals('children argument', [node2, node3], children);
229 }, thisContext);
230 assertArrayEquals('visited nodes', [node2, node3], visitedNodes);
231 assertArrayEquals('index of visited nodes', [0, 1], indices);
232 }
233
234 function testForEachDescendant() {
235 var node1 = new goog.structs.TreeNode(1, null);
236 var node2 = new goog.structs.TreeNode(2, null);
237 var node3 = new goog.structs.TreeNode(3, null);
238 var node4 = new goog.structs.TreeNode(4, null);
239 node1.addChild(node2);
240 node2.addChild(node3);
241 node2.addChild(node4);
242
243 var thisContext = {};
244 var visitedNodes = [];
245 node1.forEachDescendant(function(node) {
246 assertEquals('value of this', thisContext, this);
247 visitedNodes.push(node);
248 }, thisContext);
249 assertArrayEquals('visited nodes', [node2, node3, node4], visitedNodes);
250 }
251
252 function testTraverse() {
253 var node1 = new goog.structs.TreeNode(1, null);
254 var node2 = new goog.structs.TreeNode(2, null);
255 var node3 = new goog.structs.TreeNode(3, null);
256 var node4 = new goog.structs.TreeNode(4, null);
257 node1.addChild(node2);
258 node2.addChild(node3);
259 node2.addChild(node4);
260
261 var thisContext = {};
262 var visitedNodes = [];
263 node1.traverse(function(node) {
264 assertEquals('value of this', thisContext, this);
265 visitedNodes.push(node);
266 }, thisContext);
267 assertArrayEquals(
268 'callback returns nothing => all nodes are visited',
269 [node1, node2, node3, node4], visitedNodes);
270
271 visitedNodes = [];
272 node1.traverse(function(node) {
273 visitedNodes.push(node);
274 return node != node2; // Cut off at node2.
275 });
276 assertArrayEquals(
277 'children of node2 are skipped', [node1, node2], visitedNodes);
278 }
279
280 function testAddChild() {
281 var node1 = new goog.structs.TreeNode(1, null);
282 var node2 = new goog.structs.TreeNode(2, null);
283 var node3 = new goog.structs.TreeNode(3, null);
284 assertArrayEquals('0 children', [], node1.getChildren());
285 node1.addChild(node2);
286 assertArrayEquals('1 child', [node2], node1.getChildren());
287 assertEquals('parent is set', node1, node2.getParent());
288 node1.addChild(node3);
289 assertArrayEquals('2 children', [node2, node3], node1.getChildren());
290 }
291
292 function testAddChildAt() {
293 var node1 = new goog.structs.TreeNode(1, null);
294 var node2 = new goog.structs.TreeNode(2, null);
295 var node3 = new goog.structs.TreeNode(3, null);
296 var node4 = new goog.structs.TreeNode(4, null);
297 var node5 = new goog.structs.TreeNode(5, null);
298 node1.addChildAt(node2, 0);
299 assertArrayEquals('add first child', [node2], node1.getChildren());
300 assertEquals('parent is set', node1, node2.getParent());
301 node1.addChildAt(node3, 0);
302 assertArrayEquals('add to the front', [node3, node2], node1.getChildren());
303 node1.addChildAt(node4, 1);
304 assertArrayEquals(
305 'add to the middle', [node3, node4, node2], node1.getChildren());
306 node1.addChildAt(node5, 3);
307 assertArrayEquals(
308 'add to the end', [node3, node4, node2, node5], node1.getChildren());
309 }
310
311 function testReplaceChildAt() {
312 var root = new goog.structs.TreeNode(0, null);
313 var node1 = new goog.structs.TreeNode(1, null);
314 root.addChild(node1);
315
316 var node2 = new goog.structs.TreeNode(2, null);
317 assertEquals('original node', node1, root.replaceChildAt(node2, 0));
318 assertEquals('parent is set', root, node2.getParent());
319 assertArrayEquals('children are updated', [node2], root.getChildren());
320 assertNull('old child node is detached', node1.getParent());
321 }
322
323 function testReplaceChild() {
324 var root = new goog.structs.TreeNode(0, null);
325 var node1 = new goog.structs.TreeNode(1, null);
326 root.addChild(node1);
327
328 var node2 = new goog.structs.TreeNode(2, null);
329 assertEquals('original node', node1, root.replaceChild(node2, node1));
330 assertEquals('parent is set', root, node2.getParent());
331 assertArrayEquals('children are updated', [node2], root.getChildren());
332 assertNull('old child node is detached', node1.getParent());
333 }
334
335 function testRemoveChildAt() {
336 var node1 = new goog.structs.TreeNode(1, null);
337 var node2 = new goog.structs.TreeNode(2, null);
338 var node3 = new goog.structs.TreeNode(3, null);
339 node1.addChild(node2);
340 node1.addChild(node3);
341
342 assertNull('index too low', node1.removeChildAt(-1));
343 assertNull('index too high', node1.removeChildAt(2));
344 assertArrayEquals('node1 is intact', [node2, node3], node1.getChildren());
345
346 assertEquals('remove first child', node2, node1.removeChildAt(0));
347 assertArrayEquals('remove from the front', [node3], node1.getChildren());
348 assertNull('parent is unset', node2.getParent());
349
350 assertEquals('remove last child', node3, node1.removeChildAt(0));
351 assertArrayEquals('remove last child', [], node1.getChildren());
352 assertTrue('node1 became leaf', node1.isLeaf());
353 }
354
355 function testRemoveChild() {
356 var node1 = new goog.structs.TreeNode(1, null);
357 var node2 = new goog.structs.TreeNode(2, null);
358 var node3 = new goog.structs.TreeNode(3, null);
359 node1.addChild(node2);
360 node1.addChild(node3);
361
362 assertNull('remove null', node1.removeChild(null));
363 assertNull('remove non-child', node1.removeChild(node1));
364 assertArrayEquals('node1 is intact', [node2, node3], node1.getChildren());
365
366 assertEquals('remove node3, return value', node3, node1.removeChild(node3));
367 assertArrayEquals('node is removed', [node2], node1.getChildren());
368 }
369
370 function testRemoveChildren() {
371 var node1 = new goog.structs.TreeNode(1, null);
372 var node2 = new goog.structs.TreeNode(2, null);
373 var node3 = new goog.structs.TreeNode(3, null);
374 node1.addChild(node2);
375 node1.addChild(node3);
376
377 node2.removeChildren();
378 assertArrayEquals(
379 'removing a leaf node\'s children has no effect', [],
380 node2.getChildren());
381 assertEquals('node still has parent', node1, node2.getParent());
382
383 node1.removeChildren();
384 assertArrayEquals('children have been removed', [], node1.getChildren());
385 assertNull('children\'s parents have been unset', node2.getParent());
386 }