Debian Codegraph @

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

raw
1 // Copyright 2006 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.HeapTest');
16 goog.setTestOnly('goog.structs.HeapTest');
17
18 goog.require('goog.structs');
19 goog.require('goog.structs.Heap');
20 goog.require('goog.testing.jsunit');
21
22
23 /**
24 * Constructs a heap from key-value pairs passed as arguments
25 * @param {...!Array} var_args List of length-2 arrays [key, value]
26 * @return {goog.structs.Heap} Heap constructed from passed in key-value pairs
27 */
28 function makeHeap(var_args) {
29 var h = new goog.structs.Heap();
30 var key, value;
31
32 for (var i = 0; i < arguments.length; i++) {
33 key = arguments[i][0];
34 value = arguments[i][1];
35 h.insert(key, value);
36 }
37
38 return h;
39 }
40
41
42 function testGetCount1() {
43 var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
44 assertEquals('count, should be 4', 4, h.getCount());
45 h.remove();
46 assertEquals('count, should be 3', 3, h.getCount());
47 }
48
49 function testGetCount2() {
50 var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
51 h.remove();
52 h.remove();
53 h.remove();
54 h.remove();
55 assertEquals('count, should be 0', 0, h.getCount());
56 }
57
58
59 function testKeys() {
60 var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
61 var keys = h.getKeys();
62 for (var i = 0; i < 4; i++) {
63 assertTrue('getKeys, key ' + i + ' found', goog.structs.contains(keys, i));
64 }
65 assertEquals('getKeys, Should be 4 keys', 4, goog.structs.getCount(keys));
66 }
67
68
69 function testValues() {
70 var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
71 var values = h.getValues();
72
73 assertTrue('getKeys, value "a" found', goog.structs.contains(values, 'a'));
74 assertTrue('getKeys, value "b" found', goog.structs.contains(values, 'b'));
75 assertTrue('getKeys, value "c" found', goog.structs.contains(values, 'c'));
76 assertTrue('getKeys, value "d" found', goog.structs.contains(values, 'd'));
77 assertEquals('getKeys, Should be 4 keys', 4, goog.structs.getCount(values));
78 }
79
80
81 function testContainsKey() {
82 var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
83
84 for (var i = 0; i < 4; i++) {
85 assertTrue('containsKey, key ' + i + ' found', h.containsKey(i));
86 }
87 assertFalse('containsKey, value 4 not found', h.containsKey(4));
88 }
89
90
91 function testContainsValue() {
92 var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
93
94 assertTrue('containsValue, value "a" found', h.containsValue('a'));
95 assertTrue('containsValue, value "b" found', h.containsValue('b'));
96 assertTrue('containsValue, value "c" found', h.containsValue('c'));
97 assertTrue('containsValue, value "d" found', h.containsValue('d'));
98 assertFalse('containsValue, value "e" not found', h.containsValue('e'));
99 }
100
101
102 function testClone() {
103 var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
104 var h2 = h.clone();
105 assertTrue('clone so it should not be empty', !h2.isEmpty());
106 assertTrue('clone so it should contain key 0', h2.containsKey(0));
107 assertTrue('clone so it should contain value "a"', h2.containsValue('a'));
108 }
109
110
111 function testClear() {
112 var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
113 h.clear();
114 assertTrue('cleared so it should be empty', h.isEmpty());
115 }
116
117
118 function testIsEmpty() {
119 var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
120 assertFalse('4 values so should not be empty', h.isEmpty());
121
122 h.remove();
123 h.remove();
124 h.remove();
125 assertFalse('1 values so should not be empty', h.isEmpty());
126
127 h.remove();
128 assertTrue('0 values so should be empty', h.isEmpty());
129 }
130
131
132 function testPeek1() {
133 var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
134 assertEquals('peek, Should be "a"', 'a', h.peek());
135 }
136
137
138 function testPeek2() {
139 var h = makeHeap([1, 'b'], [3, 'd'], [0, 'a'], [2, 'c']);
140 assertEquals('peek, Should be "a"', 'a', h.peek());
141 }
142
143
144 function testPeek3() {
145 var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
146 h.clear();
147 assertEquals('peek, Should be "undefined"', undefined, h.peek());
148 }
149
150
151 function testPeekKey1() {
152 var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
153 assertEquals('peekKey, Should be "0"', 0, h.peekKey());
154 }
155
156
157 function testPeekKey2() {
158 var h = makeHeap([1, 'b'], [3, 'd'], [0, 'a'], [2, 'c']);
159 assertEquals('peekKey, Should be "0"', 0, h.peekKey());
160 }
161
162
163 function testPeekKey3() {
164 var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
165 h.clear();
166 assertEquals('peekKey, Should be "undefined"', undefined, h.peekKey());
167 }
168
169
170 function testRemove1() {
171 var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
172
173 assertEquals('remove, Should be "a"', 'a', h.remove());
174 assertEquals('remove, Should be "b"', 'b', h.remove());
175 assertEquals('remove, Should be "c"', 'c', h.remove());
176 assertEquals('remove, Should be "d"', 'd', h.remove());
177 }
178
179
180 function testRemove2() {
181 var h = makeHeap([1, 'b'], [3, 'd'], [0, 'a'], [2, 'c']);
182
183 assertEquals('remove, Should be "a"', 'a', h.remove());
184 assertEquals('remove, Should be "b"', 'b', h.remove());
185 assertEquals('remove, Should be "c"', 'c', h.remove());
186 assertEquals('remove, Should be "d"', 'd', h.remove());
187 }
188
189
190 function testInsertPeek1() {
191 var h = makeHeap();
192
193 h.insert(3, 'd');
194 assertEquals('peek, Should be "d"', 'd', h.peek());
195 h.insert(2, 'c');
196 assertEquals('peek, Should be "c"', 'c', h.peek());
197 h.insert(1, 'b');
198 assertEquals('peek, Should be "b"', 'b', h.peek());
199 h.insert(0, 'a');
200 assertEquals('peek, Should be "a"', 'a', h.peek());
201 }
202
203
204 function testInsertPeek2() {
205 var h = makeHeap();
206
207 h.insert(1, 'b');
208 assertEquals('peek, Should be "b"', 'b', h.peek());
209 h.insert(3, 'd');
210 assertEquals('peek, Should be "b"', 'b', h.peek());
211 h.insert(0, 'a');
212 assertEquals('peek, Should be "a"', 'a', h.peek());
213 h.insert(2, 'c');
214 assertEquals('peek, Should be "a"', 'a', h.peek());
215 }
216
217 function testInsertAllPeek1() {
218 var h1 = makeHeap([1, 'e']);
219 var h2 = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
220
221 h1.insertAll(h2);
222 assertEquals('peek, should be "a"', 'a', h1.peek());
223 }
224
225 function testInsertAllPeek2() {
226 var h1 = makeHeap([-1, 'z']);
227 var h2 = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
228
229 h1.insertAll(h2);
230 assertEquals('peek, should be "z"', 'z', h1.peek());
231 }
232
233 function testInsertAllPeek3() {
234 var h1 = makeHeap();
235 var h2 = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
236
237 h1.insertAll(h2);
238 assertEquals('peek, should be "a"', 'a', h1.peek());
239 }