Debian Codegraph @

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

raw
1 // Copyright 2008 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.QuadTreeTest');
16 goog.setTestOnly('goog.structs.QuadTreeTest');
17
18 goog.require('goog.structs');
19 goog.require('goog.structs.QuadTree');
20 goog.require('goog.testing.jsunit');
21
22 function getTree() {
23 var qt = new goog.structs.QuadTree(0, 0, 100, 100);
24 qt.set(5, 20, 'Foo');
25 qt.set(50, 32, 'Bar');
26 qt.set(47, 96, 'Baz');
27 qt.set(50, 50, 'Bing');
28 qt.set(12, 0, 'Bong');
29 return qt;
30 }
31
32 function testGetCount() {
33 var qt = getTree();
34 assertEquals('Count should be 5', 5, qt.getCount());
35 qt.remove(50, 32);
36 assertEquals('Count should be 4', 4, qt.getCount());
37 }
38
39 function testGetKeys() {
40 var keys = getTree().getKeys();
41 var keyString = keys.sort().join(' ');
42 var expected = '(12, 0) (47, 96) (5, 20) (50, 32) (50, 50)';
43 assertEquals('Sorted keys should be ' + expected, expected, keyString);
44 }
45
46 function testGetValues() {
47 var values = getTree().getValues();
48 var valueString = values.sort().join(',');
49 assertEquals(
50 'Sorted values should be Bar,Baz,Bing,Bong,Foo', 'Bar,Baz,Bing,Bong,Foo',
51 valueString);
52 }
53
54 function testContains() {
55 var qt = getTree();
56 assertTrue('Should contain (5, 20)', qt.contains(5, 20));
57 assertFalse('Should not contain (13, 13)', qt.contains(13, 13));
58 }
59
60 function testClear() {
61 var qt = getTree();
62 qt.clear();
63 assertTrue('Tree should be empty', qt.isEmpty());
64 assertFalse('Tree should not contain (5, 20)', qt.contains(5, 20));
65 }
66
67 function testConstructor() {
68 var qt = new goog.structs.QuadTree(-10, -5, 6, 12);
69 var root = qt.getRootNode();
70 assertEquals('X of root should be -10', -10, root.x);
71 assertEquals('Y of root should be -5', -5, root.y);
72 assertEquals('Width of root should be 16', 16, root.w);
73 assertEquals('Height of root should be 17', 17, root.h);
74 assertTrue('Tree should be empty', qt.isEmpty());
75 }
76
77 function testClone() {
78 var qt = getTree().clone();
79 assertFalse('Clone should not be empty', qt.isEmpty());
80 assertTrue('Should contain (47, 96)', qt.contains(47, 96));
81 }
82
83 function testRemove() {
84 var qt = getTree();
85 assertEquals('(5, 20) should be removed', 'Foo', qt.remove(5, 20));
86 assertEquals('(5, 20) should be removed', 'Bar', qt.remove(50, 32));
87 assertEquals('(5, 20) should be removed', 'Baz', qt.remove(47, 96));
88 assertEquals('(5, 20) should be removed', 'Bing', qt.remove(50, 50));
89 assertEquals('(5, 20) should be removed', 'Bong', qt.remove(12, 0));
90 assertNull('(6, 6) wasn\'t there to remove', qt.remove(6, 6));
91 assertTrue('Tree should be empty', qt.isEmpty());
92 assertTreesChildrenAreNull(qt);
93 }
94
95 function testIsEmpty() {
96 var qt = getTree();
97 qt.clear();
98 assertTrue(qt.isEmpty());
99 assertEquals(
100 'Root should be empty node', goog.structs.QuadTree.NodeType.EMPTY,
101 qt.getRootNode().nodeType);
102 assertTreesChildrenAreNull(qt);
103 }
104
105 function testForEach() {
106 var qt = getTree();
107 var s = '';
108 goog.structs.forEach(qt, function(val, key, qt2) {
109 assertNotUndefined(key);
110 assertEquals(qt, qt2);
111 s += key.x + ',' + key.y + '=' + val + ' ';
112 });
113 assertEquals('50,32=Bar 50,50=Bing 47,96=Baz 5,20=Foo 12,0=Bong ', s);
114 }
115
116 function testBalancing() {
117 var qt = new goog.structs.QuadTree(0, 0, 100, 100);
118 var root = qt.getRootNode();
119
120 // Add a point to the NW quadrant.
121 qt.set(25, 25, 'first');
122
123 assertEquals(
124 'Root should be a leaf node.', goog.structs.QuadTree.NodeType.LEAF,
125 root.nodeType);
126 assertTreesChildrenAreNull(qt);
127
128 assertEquals('first', root.point.value);
129
130 // Add another point in the NW quadrant
131 qt.set(25, 30, 'second');
132
133 assertEquals(
134 'Root should now be a pointer.', goog.structs.QuadTree.NodeType.POINTER,
135 root.nodeType);
136 assertNotNull('NE should be not be null', root.ne);
137 assertNotNull('NW should be not be null', root.nw);
138 assertNotNull('SE should be not be null', root.se);
139 assertNotNull('SW should be not be null', root.sw);
140 assertNull(root.point);
141
142 // Delete the second point.
143 qt.remove(25, 30);
144
145 assertEquals(
146 'Root should have been rebalanced and be a leaf node.',
147 goog.structs.QuadTree.NodeType.LEAF, root.nodeType);
148 assertTreesChildrenAreNull(qt);
149 assertEquals('first', root.point.value);
150 }
151
152 function testTreeBounds() {
153 var qt = getTree();
154 assertFails(qt, qt.set, [-10, -10, 1]);
155 assertFails(qt, qt.set, [-10, 10, 2]);
156 assertFails(qt, qt.set, [10, -10, 3]);
157 assertFails(qt, qt.set, [-10, 110, 4]);
158 assertFails(qt, qt.set, [10, 130, 5]);
159 assertFails(qt, qt.set, [110, -10, 6]);
160 assertFails(qt, qt.set, [150, 14, 7]);
161 }
162
163 // Helper functions
164
165 function assertFails(context, fn, args) {
166 assertThrows(
167 'Exception expected from ' + fn.toString() + ' with arguments ' + args,
168 function() { fn.apply(context, args); });
169 }
170
171 function assertTreesChildrenAreNull(qt) {
172 var root = qt.getRootNode();
173 assertNull('NE should be null', root.ne);
174 assertNull('NW should be null', root.nw);
175 assertNull('SE should be null', root.se);
176 assertNull('SW should be null', root.sw);
177 }