4 Copyright (c) 2018, Mungo Carstairs
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are met:
10 * Redistributions of source code must retain the above copyright notice, this
11 list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above copyright notice,
14 this list of conditions and the following disclaimer in the documentation
15 and/or other materials provided with the distribution.
17 * Neither the name of the copyright holder nor the names of its
18 contributors may be used to endorse or promote products derived from
19 this software without specific prior written permission.
21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
24 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
25 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
27 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
29 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 package intervalstore.nonc;
34 import static org.testng.Assert.assertEquals;
35 import static org.testng.Assert.assertFalse;
36 import static org.testng.Assert.assertSame;
37 import static org.testng.Assert.assertTrue;
39 import java.util.ArrayList;
40 import java.util.List;
41 import java.util.Random;
43 import org.testng.annotations.Test;
45 import intervalstore.api.IntervalStoreI;
47 public class IntervalStoreTest
50 public static void main(String[] args)
52 new IntervalStoreTest().defaultTests();
55 private void defaultTests()
57 testAddAndQueryTiming();
60 @Test(groups = "Functional")
61 public void testFindOverlaps_nonNested()
63 IntervalStore<SimpleFeature> store = new IntervalStore<>();
64 SimpleFeature sf1 = add(store, 10, 20);
65 // same range different description
66 SimpleFeature sf2 = new SimpleFeature(10, 20, "desc");
68 SimpleFeature sf3 = add(store, 15, 25);
69 SimpleFeature sf4 = add(store, 20, 35);
71 assertEquals(store.size(), 4);
72 List<SimpleFeature> overlaps = store.findOverlaps(1, 9);
73 assertTrue(overlaps.isEmpty());
75 overlaps = store.findOverlaps(8, 10);
76 assertEquals(overlaps.size(), 2);
77 assertTrue(overlaps.contains(sf1));
78 assertTrue(overlaps.contains(sf2));
80 overlaps = store.findOverlaps(12, 16);
81 assertEquals(overlaps.size(), 3);
82 assertTrue(overlaps.contains(sf1));
83 assertTrue(overlaps.contains(sf2));
84 assertTrue(overlaps.contains(sf3));
86 overlaps = store.findOverlaps(33, 33);
87 assertEquals(overlaps.size(), 1);
88 assertTrue(overlaps.contains(sf4));
91 * ensure edge cases are covered
93 overlaps = store.findOverlaps(35, 40);
94 assertEquals(overlaps.size(), 1);
95 assertTrue(overlaps.contains(sf4));
96 assertTrue(store.findOverlaps(36, 100).isEmpty());
97 assertTrue(store.findOverlaps(1, 9).isEmpty());
100 @Test(groups = "Functional")
101 public void testFindOverlaps_nested()
103 IntervalStore<SimpleFeature> store = new IntervalStore<>();
104 SimpleFeature sf1 = add(store, 10, 50);
105 SimpleFeature sf2 = add(store, 10, 40);
106 SimpleFeature sf3 = add(store, 20, 30);
107 // feature at same location but different description
108 SimpleFeature sf4 = new SimpleFeature(20, 30, "different desc");
110 SimpleFeature sf5 = add(store, 35, 36);
112 List<SimpleFeature> overlaps = store.findOverlaps(1, 9);
113 assertTrue(overlaps.isEmpty());
115 overlaps = store.findOverlaps(10, 15);
116 assertEquals(overlaps.size(), 2);
117 assertTrue(overlaps.contains(sf1));
118 assertTrue(overlaps.contains(sf2));
120 overlaps = store.findOverlaps(45, 60);
121 assertEquals(overlaps.size(), 1);
122 assertTrue(overlaps.contains(sf1));
124 overlaps = store.findOverlaps(32, 38);
125 assertEquals(overlaps.size(), 3);
126 assertTrue(overlaps.contains(sf1));
127 assertTrue(overlaps.contains(sf2));
128 assertTrue(overlaps.contains(sf5));
130 overlaps = store.findOverlaps(15, 25);
131 assertEquals(overlaps.size(), 4);
132 assertTrue(overlaps.contains(sf1));
133 assertTrue(overlaps.contains(sf2));
134 assertTrue(overlaps.contains(sf3));
135 assertTrue(overlaps.contains(sf4));
138 @Test(groups = "Functional")
139 public void testFindOverlaps_mixed()
141 IntervalStore<SimpleFeature> store = new IntervalStore<>();
142 SimpleFeature sf1 = add(store, 10, 50);
143 SimpleFeature sf2 = add(store, 1, 15);
144 SimpleFeature sf3 = add(store, 20, 30);
145 SimpleFeature sf4 = add(store, 40, 100);
146 SimpleFeature sf5 = add(store, 60, 100);
147 SimpleFeature sf6 = add(store, 70, 70);
149 List<SimpleFeature> overlaps = store.findOverlaps(200, 200);
150 assertTrue(overlaps.isEmpty());
152 overlaps = store.findOverlaps(1, 9);
153 assertEquals(overlaps.size(), 1);
154 assertTrue(overlaps.contains(sf2));
156 overlaps = store.findOverlaps(5, 18);
157 assertEquals(overlaps.size(), 2);
158 assertTrue(overlaps.contains(sf1));
159 assertTrue(overlaps.contains(sf2));
161 overlaps = store.findOverlaps(30, 40);
162 assertEquals(overlaps.size(), 3);
163 assertTrue(overlaps.contains(sf1));
164 assertTrue(overlaps.contains(sf3));
165 assertTrue(overlaps.contains(sf4));
167 overlaps = store.findOverlaps(80, 90);
168 assertEquals(overlaps.size(), 2);
169 assertTrue(overlaps.contains(sf4));
170 assertTrue(overlaps.contains(sf5));
172 overlaps = store.findOverlaps(68, 70);
173 assertEquals(overlaps.size(), 3);
174 assertTrue(overlaps.contains(sf4));
175 assertTrue(overlaps.contains(sf5));
176 assertTrue(overlaps.contains(sf6));
180 * Helper method to add a feature with type "desc"
187 SimpleFeature add(IntervalStore<SimpleFeature> store, int from,
190 SimpleFeature sf1 = new SimpleFeature(from, to, "desc");
195 @Test(groups = "Functional")
196 public void testRemove()
198 IntervalStore<SimpleFeature> store = new IntervalStore<>();
199 SimpleFeature sf1 = add(store, 10, 20);
200 assertTrue(store.contains(sf1));
204 store.remove("what is this?");
205 } catch (ClassCastException e)
209 assertFalse(store.remove(null));
214 assertTrue(store.remove(sf1));
215 assertTrue(store.isEmpty());
217 SimpleFeature sf2 = add(store, 0, 0);
218 SimpleFeature sf2a = add(store, 30, 40);
219 assertTrue(store.contains(sf2));
220 assertFalse(store.remove(sf1));
221 assertTrue(store.remove(sf2));
222 assertTrue(store.remove(sf2a));
223 assertTrue(store.isEmpty());
226 * nested feature deletion
228 SimpleFeature sf4 = add(store, 20, 30);
229 SimpleFeature sf5 = add(store, 22, 26); // to NCList
230 SimpleFeature sf6 = add(store, 23, 24); // child of sf5
231 SimpleFeature sf7 = add(store, 25, 25); // sibling of sf6
232 SimpleFeature sf8 = add(store, 24, 24); // child of sf6
233 SimpleFeature sf9 = add(store, 23, 23); // child of sf6
234 assertEquals(store.size(), 6);
236 // delete a node with children - they take its place
237 assertTrue(store.remove(sf6)); // sf8, sf9 should become children of sf5
238 assertEquals(store.size(), 5);
239 assertFalse(store.contains(sf6));
241 // delete a node with no children
242 assertTrue(store.remove(sf7));
243 assertEquals(store.size(), 4);
244 assertFalse(store.contains(sf7));
246 // delete root of NCList
247 assertTrue(store.remove(sf5));
248 assertEquals(store.size(), 3);
249 assertFalse(store.contains(sf5));
251 // continue the killing fields
252 assertTrue(store.remove(sf4));
253 assertEquals(store.size(), 2);
254 assertFalse(store.contains(sf4));
256 assertTrue(store.remove(sf9));
257 assertEquals(store.size(), 1);
258 assertFalse(store.contains(sf9));
260 assertTrue(store.remove(sf8));
261 assertTrue(store.isEmpty());
265 * A helper method to test whether a list contains a specific object (by
266 * object identity, not equality test as used by List.contains())
272 private static boolean containsObject(List<? extends Object> list,
275 for (Object i : list)
285 @Test(groups = "Functional")
286 public void testAdd()
288 IntervalStore<SimpleFeature> store = new IntervalStore<>();
290 assertFalse(store.add(null));
292 SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
293 SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath");
295 assertTrue(store.add(sf1));
296 assertEquals(store.size(), 1);
299 * contains should return true for the same or an identical feature
301 assertTrue(store.contains(sf1));
302 assertTrue(store.contains(sf2));
305 * duplicates are accepted
307 assertTrue(store.add(sf2));
308 assertEquals(store.size(), 2);
310 SimpleFeature sf3 = new SimpleFeature(0, 0, "Cath");
311 assertTrue(store.add(sf3));
312 assertEquals(store.size(), 3);
315 @Test(groups = "Functional")
316 public void testAdd_noDuplicates()
318 IntervalStore<SimpleFeature> store = new IntervalStore<>();
320 SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
321 SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath");
322 assertTrue(sf1.equals(sf2));
323 assertTrue(store.add(sf1));
324 assertEquals(store.size(), 1);
325 assertFalse(store.add(sf2, false));
326 assertEquals(store.size(), 1);
327 assertTrue(store.contains(sf1));
328 assertTrue(store.contains(sf2)); // because sf1.equals(sf2) !
331 @Test(groups = "Functional")
332 public void testIsEmpty()
334 IntervalStore<SimpleFeature> store = new IntervalStore<>();
335 assertTrue(store.isEmpty());
336 assertEquals(store.size(), 0);
341 SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
343 assertFalse(store.isEmpty());
344 assertEquals(store.size(), 1);
346 assertTrue(store.isEmpty());
347 assertEquals(store.size(), 0);
349 sf1 = new SimpleFeature(0, 0, "Cath");
351 assertFalse(store.isEmpty());
352 assertEquals(store.size(), 1);
354 assertTrue(store.isEmpty());
355 assertEquals(store.size(), 0);
358 * sf2, sf3 added as nested features
360 sf1 = new SimpleFeature(19, 49, "Cath");
361 SimpleFeature sf2 = new SimpleFeature(20, 40, "Cath");
362 SimpleFeature sf3 = new SimpleFeature(25, 35, "Cath");
364 assertEquals(store.size(), 1);
366 assertEquals(store.size(), 2);
368 assertEquals(store.size(), 3);
369 assertTrue(store.remove(sf1));
370 assertEquals(store.size(), 2);
372 assertFalse(store.isEmpty());
373 assertTrue(store.remove(sf2));
374 assertEquals(store.size(), 1);
375 assertFalse(store.isEmpty());
376 assertTrue(store.remove(sf3));
377 assertEquals(store.size(), 0);
378 assertTrue(store.isEmpty()); // all gone
381 @Test(groups = "Functional")
382 public void testRemove_readd()
385 * add a feature and a nested feature
387 IntervalStore<SimpleFeature> store = new IntervalStore<>();
388 SimpleFeature sf1 = add(store, 10, 20);
389 // sf2 is nested in sf1 so will be stored in nestedFeatures
390 SimpleFeature sf2 = add(store, 12, 14);
391 assertEquals(store.size(), 2);
392 assertTrue(store.contains(sf1));
393 assertTrue(store.contains(sf2));
396 * delete the first feature
398 assertTrue(store.remove(sf1));
399 assertFalse(store.contains(sf1));
400 assertTrue(store.contains(sf2));
403 * re-add the 'nested' feature; it is now duplicated
406 assertEquals(store.size(), 2);
407 assertTrue(store.contains(sf2));
410 @Test(groups = "Functional")
411 public void testContains()
413 IntervalStore<SimpleFeature> store = new IntervalStore<>();
414 SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath");
415 SimpleFeature sf2 = new SimpleFeature(10, 20, "Pfam");
418 assertTrue(store.contains(sf1));
419 assertTrue(store.contains(new SimpleFeature(sf1))); // identical feature
420 assertFalse(store.contains(sf2)); // different description
423 * add a nested feature
425 SimpleFeature sf3 = new SimpleFeature(12, 16, "Cath");
427 assertTrue(store.contains(sf3));
428 assertTrue(store.contains(new SimpleFeature(sf3)));
431 * delete the outer (enclosing, non-nested) feature
434 assertFalse(store.contains(sf1));
435 assertTrue(store.contains(sf3));
437 assertFalse(store.contains(null));
440 assertFalse(store.contains("junk"));
441 } catch (ClassCastException e)
447 @Test(groups = "Functional")
448 public void testFindOverlaps_resultsArg_mixed()
450 IntervalStore<SimpleFeature> store = new IntervalStore<>();
451 SimpleFeature sf1 = add(store, 10, 50);
452 SimpleFeature sf2 = add(store, 1, 15);
453 SimpleFeature sf3 = add(store, 20, 30);
454 SimpleFeature sf4 = add(store, 40, 100);
455 SimpleFeature sf5 = add(store, 60, 100);
456 SimpleFeature sf6 = add(store, 70, 70);
458 List<SimpleFeature> overlaps = new ArrayList<>();
459 List<SimpleFeature> overlaps2 = store.findOverlaps(200, 200, overlaps);
460 assertSame(overlaps, overlaps2);
461 assertTrue(overlaps.isEmpty());
464 store.findOverlaps(1, 9, overlaps);
465 assertEquals(overlaps.size(), 1);
466 assertTrue(overlaps.contains(sf2));
469 store.findOverlaps(5, 18, overlaps);
470 assertEquals(overlaps.size(), 2);
471 assertTrue(overlaps.contains(sf1));
472 assertTrue(overlaps.contains(sf2));
475 store.findOverlaps(30, 40, overlaps);
476 assertEquals(overlaps.size(), 3);
477 assertTrue(overlaps.contains(sf1));
478 assertTrue(overlaps.contains(sf3));
479 assertTrue(overlaps.contains(sf4));
482 store.findOverlaps(80, 90, overlaps);
483 assertEquals(overlaps.size(), 2);
484 assertTrue(overlaps.contains(sf4));
485 assertTrue(overlaps.contains(sf5));
488 store.findOverlaps(68, 70, overlaps);
489 assertEquals(overlaps.size(), 3);
490 assertTrue(overlaps.contains(sf4));
491 assertTrue(overlaps.contains(sf5));
492 assertTrue(overlaps.contains(sf6));
495 * and without clearing the list first
496 * note that sf4 is included twice, as an
497 * overlap of 68-70 and also of 30-40
499 store.findOverlaps(30, 40, overlaps);
500 assertEquals(overlaps.size(), 6);
501 assertTrue(overlaps.contains(sf1));
502 assertTrue(overlaps.contains(sf3));
503 assertTrue(overlaps.contains(sf4));
504 assertTrue(overlaps.contains(sf5));
505 assertTrue(overlaps.contains(sf6));
506 assertSame(sf4, overlaps.get(0));
507 assertSame(sf4, overlaps.get(4));
510 @Test(groups = "Functional")
511 public void testFindOverlaps_resultsArg_nested()
513 IntervalStore<SimpleFeature> store = new IntervalStore<>();
514 SimpleFeature sf1 = add(store, 10, 50);
515 SimpleFeature sf2 = add(store, 10, 40);
516 SimpleFeature sf3 = add(store, 20, 30);
517 // feature at same location but different description
518 SimpleFeature sf4 = new SimpleFeature(20, 30, "different desc");
520 SimpleFeature sf5 = add(store, 35, 36);
522 List<SimpleFeature> overlaps = new ArrayList<>();
523 store.findOverlaps(1, 9, overlaps);
524 assertTrue(overlaps.isEmpty());
526 store.findOverlaps(10, 15, overlaps);
527 assertEquals(overlaps.size(), 2);
528 assertTrue(overlaps.contains(sf1));
529 assertTrue(overlaps.contains(sf2));
532 store.findOverlaps(45, 60, overlaps);
533 assertEquals(overlaps.size(), 1);
534 assertTrue(overlaps.contains(sf1));
537 store.findOverlaps(32, 38, overlaps);
538 assertEquals(overlaps.size(), 3);
539 assertTrue(overlaps.contains(sf1));
540 assertTrue(overlaps.contains(sf2));
541 assertTrue(overlaps.contains(sf5));
544 store.findOverlaps(15, 25, overlaps);
545 assertEquals(overlaps.size(), 4);
546 assertTrue(overlaps.contains(sf1));
547 assertTrue(overlaps.contains(sf2));
548 assertTrue(overlaps.contains(sf3));
549 assertTrue(overlaps.contains(sf4));
552 @Test(groups = "Functional")
553 public void testFindOverlaps_resultsArg_nonNested()
555 IntervalStore<SimpleFeature> store = new IntervalStore<>();
556 SimpleFeature sf1 = add(store, 10, 20);
557 // same range different description
558 SimpleFeature sf2 = new SimpleFeature(10, 20, "desc");
560 SimpleFeature sf3 = add(store, 15, 25);
561 SimpleFeature sf4 = add(store, 20, 35);
563 assertEquals(store.size(), 4);
564 List<SimpleFeature> overlaps = new ArrayList<>();
565 store.findOverlaps(1, 9, overlaps);
566 assertTrue(overlaps.isEmpty());
568 store.findOverlaps(8, 10, overlaps);
569 assertEquals(overlaps.size(), 2);
570 assertTrue(overlaps.contains(sf1));
571 assertTrue(overlaps.contains(sf2));
574 store.findOverlaps(12, 16, overlaps);
575 assertEquals(overlaps.size(), 3);
576 assertTrue(overlaps.contains(sf1));
577 assertTrue(overlaps.contains(sf2));
578 assertTrue(overlaps.contains(sf3));
581 store.findOverlaps(33, 33, overlaps);
582 assertEquals(overlaps.size(), 1);
583 assertTrue(overlaps.contains(sf4));
586 * ensure edge cases are covered
589 store.findOverlaps(35, 40, overlaps);
590 assertEquals(overlaps.size(), 1);
591 assertTrue(overlaps.contains(sf4));
594 assertTrue(store.findOverlaps(36, 100, overlaps).isEmpty());
595 assertTrue(store.findOverlaps(1, 9, overlaps).isEmpty());
599 * Compares alternative IntervalStoreI implementations for time to add an
600 * interval then query, at a range of different scales of N (the number of
603 @Test(groups = "Timing")
604 public void testAddAndQueryTiming()
606 testAddAndQuery(1, 20000000, 10, 20);
607 testAddAndQuery(0, 0, 10, 20);
609 testAddAndQuery(1, 20000000, 10, 200);
610 testAddAndQuery(0, 0, 10, 200);
612 testAddAndQuery(1, 20000000, 10, 2000);
613 testAddAndQuery(0, 0, 10, 2000);
615 testAddAndQuery(1, 20000000, -2000000, 2000000);
616 testAddAndQuery(0, 0, -2000000, 2000000);
619 private void testAddAndQuery(int addstart, int addend, int start, int end)
621 System.out.println("\nadd: " + addstart + " " + addend + " query: "
622 + start + " " + end);
623 StringBuffer sb = new StringBuffer();
624 IntervalStoreI<SimpleFeature> store;
625 store = new intervalstore.nonc.IntervalStore<>();
626 testAddAndQueryTiming(store, false, sb, addstart, addend, start, end);
628 store = new intervalstore.impl.IntervalStore<>();
629 testAddAndQueryTiming(store, true, sb, addstart, addend, start, end);
631 System.out.println(sb);
635 * Populates the store with intervals, then logs the time taken to add an
636 * interval then query, at a range of different scales of N (the number of
641 private void testAddAndQueryTiming(IntervalStoreI<SimpleFeature> store,
642 boolean isNCList, StringBuffer sb, int addstart, int addend,
645 final int seqlen = 100000; // e.g. length of gene sequence
646 final int repeats = 20;
648 final int warmups = 5;
649 final int[] scales = new int[] { 10 * K, 100 * K, 1000 * K };// , 10000 * K
652 Random r = new Random(732); // fixed seed = repeatable test
653 int counter = 0; // to ensure a distinct description for each feature
655 // System.out.println("Scale\titeration\tmicrosecs");
657 for (int scale : scales)
660 * add 'scale' features to the store
662 long ntimeLoad = System.nanoTime();
663 for (int i = 0; i < scale; i++)
666 sf = makeFeature(seqlen, r, counter);
672 ((intervalstore.nonc.IntervalStore) store).revalidate();
674 String line = "time to load " + (isNCList ? "NClist " : "NCArray ")
675 + (System.nanoTime() - ntimeLoad) / K / K + " ms scale "
677 // System.out.println(line);
681 * do "add then query" and log the time taken for the query
682 * we ignore the first 5 repetitions as 'warmups'
685 for (int i = 0; i < repeats + warmups; i++)
690 sf = makeFeature(seqlen, r, counter++);
694 sf = new SimpleFeature(addstart, addend, "desc" + counter++);
697 long t1 = System.nanoTime();
699 store.findOverlaps(start, end);
700 long elapsed = System.nanoTime() - t1;
704 // System.out.println(
705 // String.format("%d\t%d\t%d", scale, i - warmups,
711 + (isNCList ? "NCList " : "NCArray ")
712 + (total / (K * repeats)) + " microseconds\n");
716 SimpleFeature makeFeature(final int seqlen, Random r, int counter)
718 int i1 = r.nextInt(seqlen);
719 int i2 = r.nextInt(seqlen);
720 int from = Math.min(i1, i2);
721 int to = Math.max(i1, i2);
722 SimpleFeature sf = new SimpleFeature(from, to, "desc" + counter);