OLD | NEW |
1 // Copyright 2013 Google Inc. All Rights Reserved. | 1 // Copyright 2013 Google Inc. All Rights Reserved. |
2 // | 2 // |
3 // Licensed under the Apache License, Version 2.0 (the "License"); | 3 // Licensed under the Apache License, Version 2.0 (the "License"); |
4 // you may not use this file except in compliance with 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 | 5 // You may obtain a copy of the License at |
6 // | 6 // |
7 // http://www.apache.org/licenses/LICENSE-2.0 | 7 // http://www.apache.org/licenses/LICENSE-2.0 |
8 // | 8 // |
9 // Unless required by applicable law or agreed to in writing, software | 9 // Unless required by applicable law or agreed to in writing, software |
10 // distributed under the License is distributed on an "AS IS" BASIS, | 10 // distributed under the License is distributed on an "AS IS" BASIS, |
(...skipping 172 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
183 }); | 183 }); |
184 | 184 |
185 test("inserted endpoint, non-inclusive, works backward", () { | 185 test("inserted endpoint, non-inclusive, works backward", () { |
186 var it = tree.fromIterator(10, inclusive: false); | 186 var it = tree.fromIterator(10, inclusive: false); |
187 expect(it.current, isNull, reason: "iteration starts with null"); | 187 expect(it.current, isNull, reason: "iteration starts with null"); |
188 expect(it.movePrevious(), isFalse, | 188 expect(it.movePrevious(), isFalse, |
189 reason: "movePrevious() from spot is null"); | 189 reason: "movePrevious() from spot is null"); |
190 | 190 |
191 it = tree.fromIterator(30, inclusive: false); | 191 it = tree.fromIterator(30, inclusive: false); |
192 expect(it.current, isNull, reason: "iteration starts with null"); | 192 expect(it.current, isNull, reason: "iteration starts with null"); |
193 expect( | 193 expect(it.movePrevious(), isTrue, |
194 it.movePrevious(), isTrue, reason: "moveNext() from spot works"); | 194 reason: "moveNext() from spot works"); |
195 expect(it.current, equals(21)); | 195 expect(it.current, equals(21)); |
196 }); | 196 }); |
197 | 197 |
198 test("inserted midpoint, non-inclusive, reversed, works forward", () { | 198 test("inserted midpoint, non-inclusive, reversed, works forward", () { |
199 var it = tree.fromIterator(20, inclusive: false, reversed: true); | 199 var it = tree.fromIterator(20, inclusive: false, reversed: true); |
200 expect(it.current, isNull, reason: "iteration starts with null"); | 200 expect(it.current, isNull, reason: "iteration starts with null"); |
201 expect(it.moveNext(), isTrue, reason: "moveNext() from spot works"); | 201 expect(it.moveNext(), isTrue, reason: "moveNext() from spot works"); |
202 expect(it.current, equals(15)); | 202 expect(it.current, equals(15)); |
203 }); | 203 }); |
204 | 204 |
205 test("inserted endpoint, non-inclusive, reversed, works forward", () { | 205 test("inserted endpoint, non-inclusive, reversed, works forward", () { |
206 var it = tree.fromIterator(30, inclusive: false, reversed: true); | 206 var it = tree.fromIterator(30, inclusive: false, reversed: true); |
207 expect(it.current, isNull, reason: "iteration starts with null"); | 207 expect(it.current, isNull, reason: "iteration starts with null"); |
208 expect(it.moveNext(), isTrue, reason: "moveNext() from spot works"); | 208 expect(it.moveNext(), isTrue, reason: "moveNext() from spot works"); |
209 expect(it.current, equals(21)); | 209 expect(it.current, equals(21)); |
210 | 210 |
211 it = tree.fromIterator(10, inclusive: false, reversed: true); | 211 it = tree.fromIterator(10, inclusive: false, reversed: true); |
212 expect(it.current, isNull, reason: "iteration starts with null"); | 212 expect(it.current, isNull, reason: "iteration starts with null"); |
213 expect(it.moveNext(), isFalse, reason: "moveNext() works"); | 213 expect(it.moveNext(), isFalse, reason: "moveNext() works"); |
214 }); | 214 }); |
215 | 215 |
216 test("inserted endpoint, non-inclusive, reversed, works backward", () { | 216 test("inserted endpoint, non-inclusive, reversed, works backward", () { |
217 var it = tree.fromIterator(10, inclusive: false, reversed: true); | 217 var it = tree.fromIterator(10, inclusive: false, reversed: true); |
218 expect(it.current, isNull, reason: "iteration starts with null"); | 218 expect(it.current, isNull, reason: "iteration starts with null"); |
219 expect( | 219 expect(it.movePrevious(), isTrue, |
220 it.movePrevious(), isTrue, reason: "moveNext() from spot works"); | 220 reason: "moveNext() from spot works"); |
221 expect(it.current, equals(15)); | 221 expect(it.current, equals(15)); |
222 | 222 |
223 it = tree.fromIterator(30, inclusive: false, reversed: true); | 223 it = tree.fromIterator(30, inclusive: false, reversed: true); |
224 expect(it.current, isNull, reason: "iteration starts with null"); | 224 expect(it.current, isNull, reason: "iteration starts with null"); |
225 expect( | 225 expect(it.movePrevious(), isFalse, |
226 it.movePrevious(), isFalse, reason: "moveNext() from spot works"); | 226 reason: "moveNext() from spot works"); |
227 }); | 227 }); |
228 }); | 228 }); |
229 | 229 |
230 group("fails", () { | 230 group("fails", () { |
231 var it; | 231 var it; |
232 setUp(() => it = tree.iterator); | 232 setUp(() => it = tree.iterator); |
233 | 233 |
234 test("after tree is cleared", () { | 234 test("after tree is cleared", () { |
235 tree.clear(); | 235 tree.clear(); |
236 var error; | 236 var error; |
(...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
306 | 306 |
307 setUp(() { | 307 setUp(() { |
308 tree = new TreeSet()..addAll([10, 20, 15, 21, 30, 20]); | 308 tree = new TreeSet()..addAll([10, 20, 15, 21, 30, 20]); |
309 expectedUnion = [10, 15, 18, 20, 21, 22, 30]; | 309 expectedUnion = [10, 15, 18, 20, 21, 22, 30]; |
310 expectedIntersection = [10, 15]; | 310 expectedIntersection = [10, 15]; |
311 expectedDifference = [20, 21, 30]; | 311 expectedDifference = [20, 21, 30]; |
312 nonSortedTestSet = new Set.from([10, 18, 22, 15]); | 312 nonSortedTestSet = new Set.from([10, 18, 22, 15]); |
313 sortedTestSet = new TreeSet()..addAll(nonSortedTestSet); | 313 sortedTestSet = new TreeSet()..addAll(nonSortedTestSet); |
314 }); | 314 }); |
315 | 315 |
316 test("union with non sorted set", () => | 316 test( |
317 expect(tree.union(nonSortedTestSet).toList(), equals(expectedUnion))); | 317 "union with non sorted set", |
318 test("union with sorted set", () => | 318 () => expect( |
319 expect(tree.union(sortedTestSet).toList(), equals(expectedUnion))); | 319 tree.union(nonSortedTestSet).toList(), equals(expectedUnion))); |
320 test("intersection with non sorted set", () => expect( | 320 test( |
321 tree.intersection(nonSortedTestSet).toList(), | 321 "union with sorted set", |
322 equals(expectedIntersection))); | 322 () => expect( |
323 test("intersection with sorted set", () => expect( | 323 tree.union(sortedTestSet).toList(), equals(expectedUnion))); |
324 tree.intersection(sortedTestSet).toList(), | 324 test( |
325 equals(expectedIntersection))); | 325 "intersection with non sorted set", |
326 test("difference with non sorted set", () => expect( | 326 () => expect(tree.intersection(nonSortedTestSet).toList(), |
327 tree.difference(nonSortedTestSet).toList(), | 327 equals(expectedIntersection))); |
328 equals(expectedDifference))); | 328 test( |
329 test("difference with sorted set", () => expect( | 329 "intersection with sorted set", |
330 tree.difference(sortedTestSet).toList(), equals(expectedDifference))); | 330 () => expect(tree.intersection(sortedTestSet).toList(), |
| 331 equals(expectedIntersection))); |
| 332 test( |
| 333 "difference with non sorted set", |
| 334 () => expect(tree.difference(nonSortedTestSet).toList(), |
| 335 equals(expectedDifference))); |
| 336 test( |
| 337 "difference with sorted set", |
| 338 () => expect(tree.difference(sortedTestSet).toList(), |
| 339 equals(expectedDifference))); |
331 }); | 340 }); |
332 | 341 |
333 group("AVL implementaiton", () { | 342 group("AVL implementaiton", () { |
334 /// NOTE: This is implementation specific testing for coverage. | 343 /// NOTE: This is implementation specific testing for coverage. |
335 /// Users do not have access to [AvlNode] or [AvlTreeSet] | 344 /// Users do not have access to [AvlNode] or [AvlTreeSet] |
336 test("RightLeftRotation", () { | 345 test("RightLeftRotation", () { |
337 AvlTreeSet<num> tree = new TreeSet<num>(); | 346 AvlTreeSet<num> tree = new TreeSet<num>(); |
338 tree.add(10); | 347 tree.add(10); |
339 tree.add(20); | 348 tree.add(20); |
340 tree.add(15); | 349 tree.add(15); |
(...skipping 118 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
459 expect(val, equals(100), reason: "199 rounds down to 100"); | 468 expect(val, equals(100), reason: "199 rounds down to 100"); |
460 }); | 469 }); |
461 | 470 |
462 test("GREATER_THAN is sane", () { | 471 test("GREATER_THAN is sane", () { |
463 var val = tree.nearest(101, nearestOption: TreeSearch.GREATER_THAN); | 472 var val = tree.nearest(101, nearestOption: TreeSearch.GREATER_THAN); |
464 expect(val, equals(200), reason: "101 rounds up to 200"); | 473 expect(val, equals(200), reason: "101 rounds up to 200"); |
465 }); | 474 }); |
466 }); | 475 }); |
467 }); | 476 }); |
468 } | 477 } |
OLD | NEW |