Debian Codegraph @

closure-library/closure/goog/math/rangeset_test.js

raw
1 // Copyright 2009 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.math.RangeSetTest');
16 goog.setTestOnly('goog.math.RangeSetTest');
17
18 goog.require('goog.iter');
19 goog.require('goog.math.Range');
20 goog.require('goog.math.RangeSet');
21 goog.require('goog.testing.jsunit');
22
23
24 /**
25 * Produce legible assertion results for comparing ranges. The expected range
26 * may be defined as a goog.math.Range or as a two-element array of numbers. If
27 * two ranges are not equal, the error message will be in the format:
28 * "Expected <[1, 2]> (Object) but was <[3, 4]> (Object)"
29 *
30 * @param {!goog.math.Range|!Array<number>|string} a A descriptive string or
31 * the expected range.
32 * @param {!goog.math.Range|!Array<number>} b The expected range when a
33 * descriptive string is present, or the range to compare.
34 * @param {goog.math.Range=} opt_c The range to compare when a descriptive
35 * string is present.
36 */
37 function assertRangesEqual(a, b, opt_c) {
38 var message = opt_c ? a : '';
39 var expected = opt_c ? b : a;
40 var actual = opt_c ? opt_c : b;
41
42 if (goog.isArray(expected)) {
43 assertEquals(
44 message + '\n' +
45 'Expected ranges must be specified as goog.math.Range ' +
46 'objects or as 2-element number arrays. Found [' +
47 expected.join(', ') + ']',
48 2, expected.length);
49 expected = new goog.math.Range(expected[0], expected[1]);
50 }
51
52 if (!goog.math.Range.equals(
53 /** @type {!goog.math.Range} */ (expected),
54 /** @type {!goog.math.Range} */ (actual))) {
55 if (message) {
56 assertEquals(message, expected, actual);
57 } else {
58 assertEquals(expected, actual);
59 }
60 }
61 }
62
63
64 /**
65 * Produce legible assertion results for comparing two lists of ranges. Expected
66 * lists may be specified as a list of goog.math.Ranges, or as a list of
67 * two-element arrays of numbers.
68 *
69 * @param {Array<goog.math.Range|Array<number>>|string} a A help
70 * string or the list of expected ranges.
71 * @param {Array<goog.math.Range|Array<number>>} b The list of
72 * expected ranges when a descriptive string is present, or the list of
73 * ranges to compare.
74 * @param {Array<goog.math.Range>=} opt_c The list of ranges to compare when a
75 * descriptive string is present.
76 */
77 function assertRangeListsEqual(a, b, opt_c) {
78 var message = opt_c ? a + '\n' : '';
79 var expected = opt_c ? b : a;
80 var actual = opt_c ? opt_c : b;
81
82 assertEquals(
83 message + 'Array lengths unequal.', expected.length, actual.length);
84
85 for (var i = 0; i < expected.length; i++) {
86 assertRangesEqual(
87 message + 'Range ' + i + ' mismatch.', expected[i], actual[i]);
88 }
89 }
90
91
92 function testClone() {
93 var r = new goog.math.RangeSet();
94
95 var test = new goog.math.RangeSet(r);
96 assertRangeListsEqual([], test.ranges_);
97
98 r.add(new goog.math.Range(-10, -2));
99 r.add(new goog.math.Range(2.72, 3.14));
100 r.add(new goog.math.Range(8, 11));
101
102 test = r.clone();
103 assertRangeListsEqual([[-10, -2], [2.72, 3.14], [8, 11]], test.ranges_);
104
105 var test2 = r.clone();
106 assertRangeListsEqual(test.ranges_, test2.ranges_);
107
108 assertNotEquals(
109 'The clones should not share the same list reference.', test.ranges_,
110 test2.ranges_);
111
112 for (var i = 0; i < test.ranges_.length; i++) {
113 assertNotEquals(
114 'The clones should not share references to ranges.', test.ranges_[i],
115 test2.ranges_[i]);
116 }
117 }
118
119
120 function testAddNoCorruption() {
121 var r = new goog.math.RangeSet();
122
123 var range = new goog.math.Range(1, 2);
124 r.add(range);
125
126 assertNotEquals(
127 'Only a copy of the input range should be stored.', range, r.ranges_[0]);
128
129 range.end = 5;
130 assertRangeListsEqual(
131 'Modifying an input range after use should not ' +
132 'affect the set.',
133 [[1, 2]], r.ranges_);
134 }
135
136
137 function testAdd() {
138 var r = new goog.math.RangeSet();
139
140 r.add(new goog.math.Range(7, 12));
141 assertRangeListsEqual([[7, 12]], r.ranges_);
142
143 r.add(new goog.math.Range(1, 3));
144 assertRangeListsEqual([[1, 3], [7, 12]], r.ranges_);
145
146 r.add(new goog.math.Range(13, 18));
147 assertRangeListsEqual([[1, 3], [7, 12], [13, 18]], r.ranges_);
148
149 r.add(new goog.math.Range(5, 5));
150 assertRangeListsEqual(
151 'Zero length ranges should be ignored.', [[1, 3], [7, 12], [13, 18]],
152 r.ranges_);
153
154 var badRange = new goog.math.Range(5, 5);
155 badRange.end = 4;
156 r.add(badRange);
157 assertRangeListsEqual(
158 'Negative length ranges should be ignored.', [[1, 3], [7, 12], [13, 18]],
159 r.ranges_);
160
161 r.add(new goog.math.Range(-22, -15));
162 assertRangeListsEqual(
163 'Negative ranges should work fine.',
164 [[-22, -15], [1, 3], [7, 12], [13, 18]], r.ranges_);
165
166 r.add(new goog.math.Range(3.1, 6.9));
167 assertRangeListsEqual(
168 'Non-integer ranges should work fine.',
169 [[-22, -15], [1, 3], [3.1, 6.9], [7, 12], [13, 18]], r.ranges_);
170 }
171
172
173 function testAddWithOverlaps() {
174 var r = new goog.math.RangeSet();
175
176 r.add(new goog.math.Range(7, 12));
177 r.add(new goog.math.Range(5, 8));
178 assertRangeListsEqual([[5, 12]], r.ranges_);
179
180 r.add(new goog.math.Range(15, 20));
181 r.add(new goog.math.Range(18, 25));
182 assertRangeListsEqual([[5, 12], [15, 25]], r.ranges_);
183
184 r.add(new goog.math.Range(10, 17));
185 assertRangeListsEqual([[5, 25]], r.ranges_);
186
187 r.add(new goog.math.Range(-4, 4.5));
188 assertRangeListsEqual([[-4, 4.5], [5, 25]], r.ranges_);
189
190 r.add(new goog.math.Range(4.2, 5.3));
191 assertRangeListsEqual([[-4, 25]], r.ranges_);
192 }
193
194
195 function testAddWithAdjacentSpans() {
196 var r = new goog.math.RangeSet();
197
198 r.add(new goog.math.Range(7, 12));
199 r.add(new goog.math.Range(13, 19));
200 assertRangeListsEqual([[7, 12], [13, 19]], r.ranges_);
201
202 r.add(new goog.math.Range(4, 6));
203 assertRangeListsEqual([[4, 6], [7, 12], [13, 19]], r.ranges_);
204
205 r.add(new goog.math.Range(6, 7));
206 assertRangeListsEqual([[4, 12], [13, 19]], r.ranges_);
207
208 r.add(new goog.math.Range(12, 13));
209 assertRangeListsEqual([[4, 19]], r.ranges_);
210
211 r.add(new goog.math.Range(19.1, 22));
212 assertRangeListsEqual([[4, 19], [19.1, 22]], r.ranges_);
213
214 r.add(new goog.math.Range(19, 19.1));
215 assertRangeListsEqual([[4, 22]], r.ranges_);
216
217 r.add(new goog.math.Range(-3, -2));
218 assertRangeListsEqual([[-3, -2], [4, 22]], r.ranges_);
219
220 r.add(new goog.math.Range(-2, 4));
221 assertRangeListsEqual([[-3, 22]], r.ranges_);
222 }
223
224
225 function testAddWithSubsets() {
226 var r = new goog.math.RangeSet();
227
228 r.add(new goog.math.Range(7, 12));
229 assertRangeListsEqual([[7, 12]], r.ranges_);
230
231 r.add(new goog.math.Range(7, 12));
232 assertRangeListsEqual([[7, 12]], r.ranges_);
233
234 r.add(new goog.math.Range(8, 11));
235 assertRangeListsEqual([[7, 12]], r.ranges_);
236
237 for (var i = 20; i < 30; i += 2) {
238 r.add(new goog.math.Range(i, i + 1));
239 }
240 assertRangeListsEqual(
241 [[7, 12], [20, 21], [22, 23], [24, 25], [26, 27], [28, 29]], r.ranges_);
242
243 r.add(new goog.math.Range(1, 30));
244 assertRangeListsEqual([[1, 30]], r.ranges_);
245 }
246
247
248 function testRemove() {
249 var r = new goog.math.RangeSet();
250
251 r.add(new goog.math.Range(1, 3));
252 r.add(new goog.math.Range(7, 8));
253 r.add(new goog.math.Range(10, 20));
254
255 r.remove(new goog.math.Range(3, 6));
256 assertRangeListsEqual([[1, 3], [7, 8], [10, 20]], r.ranges_);
257
258 r.remove(new goog.math.Range(7, 8));
259 assertRangeListsEqual([[1, 3], [10, 20]], r.ranges_);
260
261 r.remove(new goog.math.Range(1, 3));
262 assertRangeListsEqual([[10, 20]], r.ranges_);
263
264 r.remove(new goog.math.Range(8, 11));
265 assertRangeListsEqual([[11, 20]], r.ranges_);
266
267 r.remove(new goog.math.Range(18, 25));
268 assertRangeListsEqual([[11, 18]], r.ranges_);
269
270 r.remove(new goog.math.Range(15, 16));
271 assertRangeListsEqual([[11, 15], [16, 18]], r.ranges_);
272
273 r.remove(new goog.math.Range(11, 15));
274 assertRangeListsEqual([[16, 18]], r.ranges_);
275
276 r.remove(new goog.math.Range(16, 16));
277 assertRangeListsEqual(
278 'Empty ranges should be ignored.', [[16, 18]], r.ranges_);
279
280 r.remove(new goog.math.Range(16, 17));
281 assertRangeListsEqual([[17, 18]], r.ranges_);
282
283 r.remove(new goog.math.Range(17, 18));
284 assertRangeListsEqual([], r.ranges_);
285 }
286
287
288 function testRemoveWithNonOverlappingRanges() {
289 var r = new goog.math.RangeSet();
290
291 r.add(new goog.math.Range(10, 20));
292
293 r.remove(new goog.math.Range(5, 8));
294 assertRangeListsEqual(
295 'Non-overlapping ranges should be ignored.', [[10, 20]], r.ranges_);
296
297 r.remove(new goog.math.Range(20, 30));
298 assertRangeListsEqual(
299 'Non-overlapping ranges should be ignored.', [[10, 20]], r.ranges_);
300
301 r.remove(new goog.math.Range(15, 15));
302 assertRangeListsEqual(
303 'Zero-length ranges should be ignored.', [[10, 20]], r.ranges_);
304 }
305
306
307 function testRemoveWithIdenticalRanges() {
308 var r = new goog.math.RangeSet();
309
310 r.add(new goog.math.Range(10, 20));
311 r.add(new goog.math.Range(30, 40));
312 r.add(new goog.math.Range(50, 60));
313 assertRangeListsEqual([[10, 20], [30, 40], [50, 60]], r.ranges_);
314
315 r.remove(new goog.math.Range(30, 40));
316 assertRangeListsEqual([[10, 20], [50, 60]], r.ranges_);
317
318 r.remove(new goog.math.Range(50, 60));
319 assertRangeListsEqual([[10, 20]], r.ranges_);
320
321 r.remove(new goog.math.Range(10, 20));
322 assertRangeListsEqual([], r.ranges_);
323 }
324
325
326 function testRemoveWithOverlappingSubsets() {
327 var r = new goog.math.RangeSet();
328
329 r.add(new goog.math.Range(1, 10));
330
331 r.remove(new goog.math.Range(1, 4));
332 assertRangeListsEqual([[4, 10]], r.ranges_);
333
334 r.remove(new goog.math.Range(8, 10));
335 assertRangeListsEqual([[4, 8]], r.ranges_);
336 }
337
338
339 function testRemoveMultiple() {
340 var r = new goog.math.RangeSet();
341
342 r.add(new goog.math.Range(5, 8));
343 r.add(new goog.math.Range(10, 20));
344 r.add(new goog.math.Range(30, 35));
345
346 for (var i = 20; i < 30; i += 2) {
347 r.add(new goog.math.Range(i, i + 1));
348 }
349
350 assertRangeListsEqual(
351 'Setting up the test data seems to have failed, how embarrassing.',
352 [[5, 8], [10, 21], [22, 23], [24, 25], [26, 27], [28, 29], [30, 35]],
353 r.ranges_);
354
355 r.remove(new goog.math.Range(15, 32));
356 assertRangeListsEqual([[5, 8], [10, 15], [32, 35]], r.ranges_);
357 }
358
359
360 function testRemoveWithRealNumbers() {
361 var r = new goog.math.RangeSet();
362
363 r.add(new goog.math.Range(2, 4));
364
365 r.remove(new goog.math.Range(1.1, 2.72));
366 assertRangeListsEqual([[2.72, 4]], r.ranges_);
367
368 r.remove(new goog.math.Range(3.14, 5));
369 assertRangeListsEqual([[2.72, 3.14]], r.ranges_);
370
371 r.remove(new goog.math.Range(2.8, 3));
372 assertRangeListsEqual([[2.72, 2.8], [3, 3.14]], r.ranges_);
373 }
374
375
376 function testEquals() {
377 var a = new goog.math.RangeSet();
378 var b = new goog.math.RangeSet();
379
380 assertTrue(goog.math.RangeSet.equals(a, b));
381
382 a.add(new goog.math.Range(3, 9));
383 assertFalse(goog.math.RangeSet.equals(a, b));
384
385 b.add(new goog.math.Range(4, 9));
386 assertFalse(goog.math.RangeSet.equals(a, b));
387
388 b.add(new goog.math.Range(3, 4));
389 assertTrue(goog.math.RangeSet.equals(a, b));
390
391 a.add(new goog.math.Range(12, 14));
392 b.add(new goog.math.Range(11, 14));
393 assertFalse(goog.math.RangeSet.equals(a, b));
394
395 a.add(new goog.math.Range(11, 12));
396 assertTrue(goog.math.RangeSet.equals(a, b));
397 }
398
399
400 function testContains() {
401 var r = new goog.math.RangeSet();
402
403 assertFalse(r.contains(7, 9));
404
405 r.add(new goog.math.Range(5, 6));
406 r.add(new goog.math.Range(10, 20));
407
408 assertFalse(r.contains(new goog.math.Range(7, 9)));
409 assertFalse(r.contains(new goog.math.Range(9, 11)));
410 assertFalse(r.contains(new goog.math.Range(18, 22)));
411
412 assertTrue(r.contains(new goog.math.Range(17, 19)));
413 assertTrue(r.contains(new goog.math.Range(5, 6)));
414
415 assertTrue(r.contains(new goog.math.Range(5.9, 5.999)));
416
417 assertFalse(
418 'An empty input range should always return false.',
419 r.contains(new goog.math.Range(15, 15)));
420
421 var badRange = new goog.math.Range(15, 15);
422 badRange.end = 14;
423 assertFalse(
424 'An invalid range should always return false.', r.contains(badRange));
425 }
426
427
428 function testContainsValue() {
429 var r = new goog.math.RangeSet();
430
431 assertFalse(r.containsValue(5));
432
433 r.add(new goog.math.Range(1, 4));
434 r.add(new goog.math.Range(10, 20));
435
436 assertFalse(r.containsValue(0));
437 assertFalse(r.containsValue(0.999));
438 assertFalse(r.containsValue(5));
439 assertFalse(r.containsValue(25));
440 assertFalse(r.containsValue(20));
441
442 assertTrue(r.containsValue(3));
443 assertTrue(r.containsValue(10));
444 assertTrue(r.containsValue(19));
445 assertTrue(r.containsValue(19.999));
446 }
447
448
449 function testUnion() {
450 var a = new goog.math.RangeSet();
451
452 a.add(new goog.math.Range(1, 5));
453 a.add(new goog.math.Range(10, 11));
454 a.add(new goog.math.Range(15, 20));
455
456 var b = new goog.math.RangeSet();
457
458 b.add(new goog.math.Range(0, 5));
459 b.add(new goog.math.Range(8, 18));
460
461 var test = a.union(b);
462 assertRangeListsEqual([[0, 5], [8, 20]], test.ranges_);
463
464 var test = b.union(a);
465 assertRangeListsEqual([[0, 5], [8, 20]], test.ranges_);
466
467 var test = a.union(a);
468 assertRangeListsEqual(a.ranges_, test.ranges_);
469 }
470
471
472 function testDifference() {
473 var a = new goog.math.RangeSet();
474
475 a.add(new goog.math.Range(1, 5));
476 a.add(new goog.math.Range(10, 11));
477 a.add(new goog.math.Range(15, 20));
478
479 var b = new goog.math.RangeSet();
480
481 b.add(new goog.math.Range(0, 5));
482 b.add(new goog.math.Range(8, 18));
483
484 var test = a.difference(b);
485 assertRangeListsEqual([[18, 20]], test.ranges_);
486
487 var test = b.difference(a);
488 assertRangeListsEqual([[0, 1], [8, 10], [11, 15]], test.ranges_);
489
490 var test = a.difference(a);
491 assertRangeListsEqual([], test.ranges_);
492
493 var test = b.difference(b);
494 assertRangeListsEqual([], test.ranges_);
495 }
496
497
498 function testIntersection() {
499 var a = new goog.math.RangeSet();
500
501 a.add(new goog.math.Range(1, 5));
502 a.add(new goog.math.Range(10, 11));
503 a.add(new goog.math.Range(15, 20));
504
505 var b = new goog.math.RangeSet();
506
507 b.add(new goog.math.Range(0, 5));
508 b.add(new goog.math.Range(8, 18));
509
510 var test = a.intersection(b);
511 assertRangeListsEqual([[1, 5], [10, 11], [15, 18]], test.ranges_);
512
513 var test = b.intersection(a);
514 assertRangeListsEqual([[1, 5], [10, 11], [15, 18]], test.ranges_);
515
516 var test = a.intersection(a);
517 assertRangeListsEqual(a.ranges_, test.ranges_);
518 }
519
520
521 function testSlice() {
522 var r = new goog.math.RangeSet();
523
524 r.add(new goog.math.Range(2, 4));
525 r.add(new goog.math.Range(5, 6));
526 r.add(new goog.math.Range(9, 15));
527
528 var test = r.slice(new goog.math.Range(0, 2));
529 assertRangeListsEqual([], test.ranges_);
530
531 test = r.slice(new goog.math.Range(2, 4));
532 assertRangeListsEqual([[2, 4]], test.ranges_);
533
534 test = r.slice(new goog.math.Range(7, 20));
535 assertRangeListsEqual([[9, 15]], test.ranges_);
536
537 test = r.slice(new goog.math.Range(4, 30));
538 assertRangeListsEqual([[5, 6], [9, 15]], test.ranges_);
539
540 test = r.slice(new goog.math.Range(2, 15));
541 assertRangeListsEqual([[2, 4], [5, 6], [9, 15]], test.ranges_);
542
543 test = r.slice(new goog.math.Range(10, 10));
544 assertRangeListsEqual(
545 'An empty range should produce an empty set.', [], test.ranges_);
546
547 var badRange = new goog.math.Range(10, 10);
548 badRange.end = 9;
549 test = r.slice(badRange);
550 assertRangeListsEqual(
551 'An invalid range should produce an empty set.', [], test.ranges_);
552 }
553
554
555 function testInverse() {
556 var r = new goog.math.RangeSet();
557
558 r.add(new goog.math.Range(1, 3));
559 r.add(new goog.math.Range(5, 6));
560 r.add(new goog.math.Range(8, 10));
561
562 var test = r.inverse(new goog.math.Range(10, 20));
563 assertRangeListsEqual([[10, 20]], test.ranges_);
564
565 test = r.inverse(new goog.math.Range(1, 3));
566 assertRangeListsEqual([], test.ranges_);
567
568 test = r.inverse(new goog.math.Range(0, 2));
569 assertRangeListsEqual([[0, 1]], test.ranges_);
570
571 test = r.inverse(new goog.math.Range(9, 12));
572 assertRangeListsEqual([[10, 12]], test.ranges_);
573
574 test = r.inverse(new goog.math.Range(2, 9));
575 assertRangeListsEqual([[3, 5], [6, 8]], test.ranges_);
576
577 test = r.inverse(new goog.math.Range(4, 9));
578 assertRangeListsEqual([[4, 5], [6, 8]], test.ranges_);
579
580 test = r.inverse(new goog.math.Range(9, 9));
581 assertRangeListsEqual(
582 'An empty range should produce an empty set.', [], test.ranges_);
583
584 var badRange = new goog.math.Range(9, 9);
585 badRange.end = 8;
586 test = r.inverse(badRange);
587 assertRangeListsEqual(
588 'An invalid range should produce an empty set.', [], test.ranges_);
589 }
590
591
592 function testCoveredLength() {
593 var r = new goog.math.RangeSet();
594 assertEquals(0, r.coveredLength());
595
596 r.add(new goog.math.Range(5, 9));
597 assertEquals(4, r.coveredLength());
598
599 r.add(new goog.math.Range(0, 3));
600 r.add(new goog.math.Range(12, 13));
601 assertEquals(8, r.coveredLength());
602
603 r.add(new goog.math.Range(-1, 13));
604 assertEquals(14, r.coveredLength());
605
606 r.add(new goog.math.Range(13, 13.5));
607 assertEquals(14.5, r.coveredLength());
608 }
609
610
611 function testGetBounds() {
612 var r = new goog.math.RangeSet();
613
614 assertNull(r.getBounds());
615
616 r.add(new goog.math.Range(12, 54));
617 assertRangesEqual([12, 54], r.getBounds());
618
619 r.add(new goog.math.Range(108, 139));
620 assertRangesEqual([12, 139], r.getBounds());
621 }
622
623
624 function testIsEmpty() {
625 var r = new goog.math.RangeSet();
626 assertTrue(r.isEmpty());
627
628 r.add(new goog.math.Range(0, 1));
629 assertFalse(r.isEmpty());
630
631 r.remove(new goog.math.Range(0, 1));
632 assertTrue(r.isEmpty());
633 }
634
635
636 function testClear() {
637 var r = new goog.math.RangeSet();
638
639 r.add(new goog.math.Range(1, 2));
640 r.add(new goog.math.Range(3, 5));
641 r.add(new goog.math.Range(8, 13));
642
643 assertFalse(r.isEmpty());
644
645 r.clear();
646 assertTrue(r.isEmpty());
647 }
648
649
650 function testIter() {
651 var r = new goog.math.RangeSet();
652
653 r.add(new goog.math.Range(1, 3));
654 r.add(new goog.math.Range(5, 6));
655 r.add(new goog.math.Range(8, 10));
656
657 assertRangeListsEqual([[1, 3], [5, 6], [8, 10]], goog.iter.toArray(r));
658
659 var i = 0;
660 goog.iter.forEach(r, function(testRange) {
661 assertRangesEqual(
662 'Iterated set values should match the originals.', r.ranges_[i],
663 testRange);
664 assertNotEquals(
665 'Iterated range should not be a reference to the original.',
666 r.ranges_[i], testRange);
667 i++;
668 });
669 }