1 package jalview.datamodel.features;
2 import static org.testng.Assert.assertEquals;
3 import static org.testng.Assert.assertFalse;
4 import static org.testng.Assert.assertSame;
5 import static org.testng.Assert.assertTrue;
7 import jalview.datamodel.SequenceFeature;
9 import java.util.ArrayList;
10 import java.util.Collections;
11 import java.util.Comparator;
12 import java.util.List;
13 import java.util.Random;
15 import junit.extensions.PA;
17 import org.testng.annotations.DataProvider;
18 import org.testng.annotations.Test;
20 public class NCListTest
23 private Random random = new Random(107);
25 private Comparator<ContiguousI> sorter = new RangeComparator(true);
28 * A basic sanity test of the constructor
30 @Test(groups = "Functional")
31 public void testConstructor()
33 List<Range> ranges = new ArrayList<Range>();
34 ranges.add(new Range(20, 20));
35 ranges.add(new Range(10, 20));
36 ranges.add(new Range(15, 30));
37 ranges.add(new Range(10, 30));
38 ranges.add(new Range(11, 19));
39 ranges.add(new Range(10, 20));
40 ranges.add(new Range(1, 100));
42 NCList<Range> ncl = new NCList<Range>(ranges);
43 String expected = "[1-100 [10-30 [10-20 [10-20 [11-19]]]], 15-30 [20-20]]";
44 assertEquals(ncl.toString(), expected);
45 assertTrue(ncl.isValid());
47 Collections.reverse(ranges);
48 ncl = new NCList<Range>(ranges);
49 assertEquals(ncl.toString(), expected);
50 assertTrue(ncl.isValid());
53 @Test(groups = "Functional")
54 public void testFindOverlaps()
56 List<Range> ranges = new ArrayList<Range>();
57 ranges.add(new Range(20, 50));
58 ranges.add(new Range(30, 70));
59 ranges.add(new Range(1, 100));
60 ranges.add(new Range(70, 120));
62 NCList<Range> ncl = new NCList<Range>(ranges);
64 List<Range> overlaps = ncl.findOverlaps(121, 122);
65 assertEquals(overlaps.size(), 0);
67 overlaps = ncl.findOverlaps(21, 22);
68 assertEquals(overlaps.size(), 2);
69 assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 1);
70 assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 100);
71 assertEquals(((ContiguousI) overlaps.get(1)).getBegin(), 20);
72 assertEquals(((ContiguousI) overlaps.get(1)).getEnd(), 50);
74 overlaps = ncl.findOverlaps(110, 110);
75 assertEquals(overlaps.size(), 1);
76 assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 70);
77 assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 120);
80 @Test(groups = "Functional")
81 public void testAdd_onTheEnd()
83 List<Range> ranges = new ArrayList<Range>();
84 ranges.add(new Range(20, 50));
85 NCList<Range> ncl = new NCList<Range>(ranges);
86 assertEquals(ncl.toString(), "[20-50]");
87 assertTrue(ncl.isValid());
89 ncl.add(new Range(60, 70));
90 assertEquals(ncl.toString(), "[20-50, 60-70]");
91 assertTrue(ncl.isValid());
94 @Test(groups = "Functional")
95 public void testAdd_inside()
97 List<Range> ranges = new ArrayList<Range>();
98 ranges.add(new Range(20, 50));
99 NCList<Range> ncl = new NCList<Range>(ranges);
100 assertEquals(ncl.toString(), "[20-50]");
101 assertTrue(ncl.isValid());
103 ncl.add(new Range(30, 40));
104 assertEquals(ncl.toString(), "[20-50 [30-40]]");
107 @Test(groups = "Functional")
108 public void testAdd_onTheFront()
110 List<Range> ranges = new ArrayList<Range>();
111 ranges.add(new Range(20, 50));
112 NCList<Range> ncl = new NCList<Range>(ranges);
113 assertEquals(ncl.toString(), "[20-50]");
114 assertTrue(ncl.isValid());
116 ncl.add(new Range(5, 15));
117 assertEquals(ncl.toString(), "[5-15, 20-50]");
118 assertTrue(ncl.isValid());
121 @Test(groups = "Functional")
122 public void testAdd_enclosing()
124 List<Range> ranges = new ArrayList<Range>();
125 ranges.add(new Range(20, 50));
126 ranges.add(new Range(30, 60));
127 NCList<Range> ncl = new NCList<Range>(ranges);
128 assertEquals(ncl.toString(), "[20-50, 30-60]");
129 assertTrue(ncl.isValid());
130 assertEquals(ncl.getStart(), 20);
132 ncl.add(new Range(10, 70));
133 assertEquals(ncl.toString(), "[10-70 [20-50, 30-60]]");
134 assertTrue(ncl.isValid());
137 @Test(groups = "Functional")
138 public void testAdd_spanning()
140 List<Range> ranges = new ArrayList<Range>();
141 ranges.add(new Range(20, 40));
142 ranges.add(new Range(60, 70));
143 NCList<Range> ncl = new NCList<Range>(ranges);
144 assertEquals(ncl.toString(), "[20-40, 60-70]");
145 assertTrue(ncl.isValid());
147 ncl.add(new Range(30, 50));
148 assertEquals(ncl.toString(), "[20-40, 30-50, 60-70]");
149 assertTrue(ncl.isValid());
151 ncl.add(new Range(40, 65));
152 assertEquals(ncl.toString(), "[20-40, 30-50, 40-65, 60-70]");
153 assertTrue(ncl.isValid());
157 * Provides the scales for pseudo-random NCLists i.e. the range of the maximal
158 * [0-scale] interval to be stored
162 @DataProvider(name = "scalesOfLife")
163 public Object[][] getScales()
165 return new Object[][] { new Integer[] { 10 }, new Integer[] { 100 } };
169 * Do a number of pseudo-random (reproducible) builds of an NCList, to
170 * exercise as many methods of the class as possible while generating the
171 * range of possible structure topologies
173 * <li>verify that add adds an entry and increments size</li>
174 * <li>...except where the entry is already contained (by equals test)</li>
175 * <li>verify that the structure is valid at all stages of construction</li>
176 * <li>generate, run and verify a range of overlap queries</li>
177 * <li>tear down the structure by deleting entries, verifying correctness at
181 @Test(groups = "Functional", dataProvider = "scalesOfLife")
182 public void test_pseudoRandom(Integer scale)
184 NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
185 List<SequenceFeature> features = new ArrayList<SequenceFeature>(scale);
187 testAdd_pseudoRandom(scale, ncl, features);
190 * sort the list of added ranges - this doesn't affect the test,
191 * just makes it easier to inspect the data in the debugger
193 Collections.sort(features, sorter);
195 testFindOverlaps_pseudoRandom(ncl, scale, features);
197 testDelete_pseudoRandom(ncl, features);
201 * Pick randomly selected entries to delete in turn, checking the NCList size
202 * and validity at each stage, until it is empty
207 protected void testDelete_pseudoRandom(NCList<SequenceFeature> ncl,
208 List<SequenceFeature> features)
212 while (!features.isEmpty())
214 assertEquals(ncl.size(), features.size());
215 int toDelete = random.nextInt(features.size());
216 SequenceFeature entry = features.get(toDelete);
217 assertTrue(ncl.contains(entry), String.format(
218 "NCList doesn't contain entry [%d] '%s'!", deleted,
222 assertFalse(ncl.contains(entry), String.format(
223 "NCList still contains deleted entry [%d] '%s'!", deleted,
225 features.remove(toDelete);
228 assertTrue(ncl.isValid(), String.format(
229 "NCList invalid after %d deletions, last deleted was '%s'",
230 deleted, entry.toString()));
233 * brute force check that deleting one entry didn't delete any others
235 for (int i = 0; i < features.size(); i++)
237 SequenceFeature sf = features.get(i);
238 assertTrue(ncl.contains(sf), String.format(
239 "NCList doesn't contain entry [%d] %s after deleting '%s'!",
240 i, sf.toString(), entry.toString()));
243 assertEquals(ncl.size(), 0); // all gone
247 * Randomly generate entries and add them to the NCList, checking its validity
248 * and size at each stage. A few entries should be duplicates (by equals test)
255 protected void testAdd_pseudoRandom(Integer scale,
256 NCList<SequenceFeature> ncl,
257 List<SequenceFeature> features)
262 for (int i = 0; i < size; i++)
264 int r1 = random.nextInt(scale + 1);
265 int r2 = random.nextInt(scale + 1);
266 int from = Math.min(r1, r2);
267 int to = Math.max(r1, r2);
270 * choice of two feature values means that occasionally an identical
271 * feature may be generated, in which case it should not be added
273 float value = (float) i % 2;
274 SequenceFeature feature = new SequenceFeature("Pfam", "", from, to,
278 * add to NCList - with duplicate entries (by equals) disallowed
280 ncl.add(feature, false);
281 if (features.contains(feature))
283 System.out.println("Duplicate feature generated "
284 + feature.toString());
288 features.add(feature);
293 * check list format is valid at each stage of its construction
295 assertTrue(ncl.isValid(),
296 String.format("Failed for scale = %d, i=%d", scale, i));
297 assertEquals(ncl.size(), count);
299 // System.out.println(ncl.prettyPrint());
303 * A helper method that generates pseudo-random range queries and veries that
304 * findOverlaps returns the correct matches
307 * the NCList to query
309 * ncl maximal range is [0, scale]
311 * a list of the ranges stored in ncl
313 protected void testFindOverlaps_pseudoRandom(NCList<SequenceFeature> ncl,
315 List<SequenceFeature> features)
317 int halfScale = scale / 2;
318 int minIterations = 20;
321 * generates ranges in [-halfScale, scale+halfScale]
322 * - some should be internal to [0, scale] P = 1/4
323 * - some should lie before 0 P = 1/16
324 * - some should lie after scale P = 1/16
325 * - some should overlap left P = 1/4
326 * - some should overlap right P = 1/4
327 * - some should enclose P = 1/8
329 * 50 iterations give a 96% probability of including the
330 * unlikeliest case; keep going until we have done all!
332 boolean inside = false;
333 boolean enclosing = false;
334 boolean before = false;
335 boolean after = false;
336 boolean overlapLeft = false;
337 boolean overlapRight = false;
338 boolean allCasesCovered = false;
341 while (i < minIterations || !allCasesCovered)
344 int r1 = random.nextInt((scale + 1) * 2);
345 int r2 = random.nextInt((scale + 1) * 2);
346 int from = Math.min(r1, r2) - halfScale;
347 int to = Math.max(r1, r2) - halfScale;
350 * ensure all cases of interest get covered
352 inside |= from >= 0 && to <= scale;
353 enclosing |= from <= 0 && to >= scale;
355 after |= from > scale;
356 overlapLeft |= from < 0 && to >= 0 && to <= scale;
357 overlapRight |= from >= 0 && from <= scale && to > scale;
358 if (!allCasesCovered)
360 allCasesCovered |= inside && enclosing && before && after
361 && overlapLeft && overlapRight;
366 .format("Covered all findOverlaps cases after %d iterations for scale %d",
371 verifyFindOverlaps(ncl, from, to, features);
376 * A helper method that verifies that overlaps found by interrogating an
377 * NCList correctly match those found by brute force search
384 protected void verifyFindOverlaps(NCList<SequenceFeature> ncl, int from,
385 int to, List<SequenceFeature> features)
387 List<SequenceFeature> overlaps = ncl.findOverlaps(from, to);
390 * check returned entries do indeed overlap from-to range
392 for (ContiguousI sf : overlaps)
394 int begin = sf.getBegin();
395 int end = sf.getEnd();
396 assertTrue(begin <= to && end >= from, String.format(
397 "[%d, %d] does not overlap query range [%d, %d]", begin, end,
402 * check overlapping ranges are included in the results
403 * (the test above already shows non-overlapping ranges are not)
405 for (ContiguousI sf : features)
407 int begin = sf.getBegin();
408 int end = sf.getEnd();
409 if (begin <= to && end >= from)
411 boolean found = overlaps.contains(sf);
412 assertTrue(found, String.format(
413 "[%d, %d] missing in query range [%d, %d]", begin, end,
419 @Test(groups = "Functional")
420 public void testGetEntries()
422 List<Range> ranges = new ArrayList<Range>();
423 Range r1 = new Range(20, 20);
424 Range r2 = new Range(10, 20);
425 Range r3 = new Range(15, 30);
426 Range r4 = new Range(10, 30);
427 Range r5 = new Range(11, 19);
428 Range r6 = new Range(10, 20);
436 NCList<Range> ncl = new NCList<Range>(ranges);
437 Range r7 = new Range(1, 100);
440 List<Range> contents = ncl.getEntries();
441 assertEquals(contents.size(), 7);
442 assertTrue(contents.contains(r1));
443 assertTrue(contents.contains(r2));
444 assertTrue(contents.contains(r3));
445 assertTrue(contents.contains(r4));
446 assertTrue(contents.contains(r5));
447 assertTrue(contents.contains(r6));
448 assertTrue(contents.contains(r7));
450 ncl = new NCList<Range>();
451 assertTrue(ncl.getEntries().isEmpty());
454 @Test(groups = "Functional")
455 public void testDelete()
457 List<Range> ranges = new ArrayList<Range>();
458 Range r1 = new Range(20, 30);
460 NCList<Range> ncl = new NCList<Range>(ranges);
461 assertTrue(ncl.getEntries().contains(r1));
463 Range r2 = new Range(20, 30);
464 assertFalse(ncl.delete(null)); // null argument
465 assertFalse(ncl.delete(r2)); // never added
466 assertTrue(ncl.delete(r1)); // success
467 assertTrue(ncl.getEntries().isEmpty());
470 * tests where object.equals() == true
472 NCList<SequenceFeature> features = new NCList<SequenceFeature>();
473 SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
475 SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
478 assertEquals(sf1, sf2); // sf1.equals(sf2)
479 assertFalse(features.delete(sf2)); // equality is not enough for deletion
480 assertTrue(features.getEntries().contains(sf1)); // still there!
481 assertTrue(features.delete(sf1));
482 assertTrue(features.getEntries().isEmpty()); // gone now
485 * test with duplicate objects in NCList
489 assertEquals(features.getEntries().size(), 2);
490 assertSame(features.getEntries().get(0), sf1);
491 assertSame(features.getEntries().get(1), sf1);
492 assertTrue(features.delete(sf1)); // first match only is deleted
493 assertTrue(features.contains(sf1));
494 assertEquals(features.size(), 1);
495 assertTrue(features.delete(sf1));
496 assertTrue(features.getEntries().isEmpty());
499 @Test(groups = "Functional")
500 public void testAdd_overlapping()
502 List<Range> ranges = new ArrayList<Range>();
503 ranges.add(new Range(40, 50));
504 ranges.add(new Range(20, 30));
505 NCList<Range> ncl = new NCList<Range>(ranges);
506 assertEquals(ncl.toString(), "[20-30, 40-50]");
507 assertTrue(ncl.isValid());
510 * add range overlapping internally
512 ncl.add(new Range(25, 35));
513 assertEquals(ncl.toString(), "[20-30, 25-35, 40-50]");
514 assertTrue(ncl.isValid());
517 * add range overlapping last range
519 ncl.add(new Range(45, 55));
520 assertEquals(ncl.toString(), "[20-30, 25-35, 40-50, 45-55]");
521 assertTrue(ncl.isValid());
524 * add range overlapping first range
526 ncl.add(new Range(15, 25));
527 assertEquals(ncl.toString(), "[15-25, 20-30, 25-35, 40-50, 45-55]");
528 assertTrue(ncl.isValid());
532 * Test the contains method (which uses object equals test)
534 @Test(groups = "Functional")
535 public void testContains()
537 NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
538 SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
540 SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
542 SequenceFeature sf3 = new SequenceFeature("type", "desc", 1, 10, 2f,
546 assertTrue(ncl.contains(sf1));
547 assertTrue(ncl.contains(sf2)); // sf1.equals(sf2)
548 assertFalse(ncl.contains(sf3)); // !sf1.equals(sf3)
551 * make some deeper structure in the NCList
553 SequenceFeature sf4 = new SequenceFeature("type", "desc", 2, 9, 2f,
556 assertTrue(ncl.contains(sf4));
557 SequenceFeature sf5 = new SequenceFeature("type", "desc", 4, 5, 2f,
559 SequenceFeature sf6 = new SequenceFeature("type", "desc", 6, 8, 2f,
563 assertTrue(ncl.contains(sf5));
564 assertTrue(ncl.contains(sf6));
567 @Test(groups = "Functional")
568 public void testIsValid()
570 List<Range> ranges = new ArrayList<Range>();
571 Range r1 = new Range(40, 50);
573 NCList<Range> ncl = new NCList<Range>(ranges);
574 assertTrue(ncl.isValid());
576 Range r2 = new Range(42, 44);
578 assertTrue(ncl.isValid());
579 Range r3 = new Range(46, 48);
581 assertTrue(ncl.isValid());
582 Range r4 = new Range(43, 43);
584 assertTrue(ncl.isValid());
586 assertEquals(ncl.toString(), "[40-50 [42-44 [43-43], 46-48]]");
587 assertTrue(ncl.isValid());
589 PA.setValue(r1, "start", 43);
590 assertFalse(ncl.isValid()); // r2 not inside r1
591 PA.setValue(r1, "start", 40);
592 assertTrue(ncl.isValid());
594 PA.setValue(r3, "start", 41);
595 assertFalse(ncl.isValid()); // r3 should precede r2
596 PA.setValue(r3, "start", 46);
597 assertTrue(ncl.isValid());
599 PA.setValue(r4, "start", 41);
600 assertFalse(ncl.isValid()); // r4 not inside r2
601 PA.setValue(r4, "start", 43);
602 assertTrue(ncl.isValid());
604 PA.setValue(r4, "start", 44);
605 assertFalse(ncl.isValid()); // r4 has reverse range
608 @Test(groups = "Functional")
609 public void testPrettyPrint()
612 * construct NCList from a list of ranges
613 * they are sorted then assembled into NCList subregions
614 * notice that 42-42 end up inside 41-46
616 List<Range> ranges = new ArrayList<Range>();
617 ranges.add(new Range(40, 50));
618 ranges.add(new Range(45, 55));
619 ranges.add(new Range(40, 45));
620 ranges.add(new Range(41, 46));
621 ranges.add(new Range(42, 42));
622 ranges.add(new Range(42, 42));
623 NCList<Range> ncl = new NCList<Range>(ranges);
624 assertTrue(ncl.isValid());
625 assertEquals(ncl.toString(),
626 "[40-50 [40-45], 41-46 [42-42 [42-42]], 45-55]");
627 String expected = "40-50\n 40-45\n41-46\n 42-42\n 42-42\n45-55\n";
628 assertEquals(ncl.prettyPrint(), expected);
631 * repeat but now add ranges one at a time
632 * notice that 42-42 end up inside 40-50 so we get
633 * a different but equal valid NCList structure
636 ncl = new NCList<Range>(ranges);
637 ncl.add(new Range(40, 50));
638 ncl.add(new Range(45, 55));
639 ncl.add(new Range(40, 45));
640 ncl.add(new Range(41, 46));
641 ncl.add(new Range(42, 42));
642 ncl.add(new Range(42, 42));
643 assertTrue(ncl.isValid());
644 assertEquals(ncl.toString(),
645 "[40-50 [40-45 [42-42 [42-42]], 41-46], 45-55]");
646 expected = "40-50\n 40-45\n 42-42\n 42-42\n 41-46\n45-55\n";
647 assertEquals(ncl.prettyPrint(), expected);
651 * A test that shows different valid trees can be constructed from the same
652 * set of ranges, depending on the order of construction
654 @Test(groups = "Functional")
655 public void testConstructor_alternativeTrees()
657 List<Range> ranges = new ArrayList<Range>();
658 ranges.add(new Range(10, 60));
659 ranges.add(new Range(20, 30));
660 ranges.add(new Range(40, 50));
663 * constructor with greedy traversal of sorted ranges to build nested
664 * containment lists results in 20-30 inside 10-60, 40-50 a sibling
666 NCList<Range> ncl = new NCList<Range>(ranges);
667 assertEquals(ncl.toString(), "[10-60 [20-30], 40-50]");
668 assertTrue(ncl.isValid());
671 * adding ranges one at a time results in 40-50
672 * a sibling of 20-30 inside 10-60
674 ncl = new NCList<Range>(new Range(10, 60));
675 ncl.add(new Range(20, 30));
676 ncl.add(new Range(40, 50));
677 assertEquals(ncl.toString(), "[10-60 [20-30, 40-50]]");
678 assertTrue(ncl.isValid());