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 org.testng.annotations.DataProvider;
16 import org.testng.annotations.Test;
18 public class NCListTest
21 private Random random = new Random(107);
23 private Comparator<ContiguousI> sorter = new RangeComparator(true);
26 * A basic sanity test of the constructor
28 @Test(groups = "Functional")
29 public void testConstructor()
31 List<Range> ranges = new ArrayList<Range>();
32 ranges.add(new Range(20, 20));
33 ranges.add(new Range(10, 20));
34 ranges.add(new Range(15, 30));
35 ranges.add(new Range(10, 30));
36 ranges.add(new Range(11, 19));
37 ranges.add(new Range(10, 20));
38 ranges.add(new Range(1, 100));
40 NCList<Range> ncl = new NCList<Range>(ranges);
41 String expected = "[1-100 [10-30 [10-20 [10-20 [11-19]]]], 15-30 [20-20]]";
42 assertEquals(ncl.toString(), expected);
43 assertTrue(ncl.isValid());
45 Collections.reverse(ranges);
46 ncl = new NCList<Range>(ranges);
47 assertEquals(ncl.toString(), expected);
48 assertTrue(ncl.isValid());
51 @Test(groups = "Functional")
52 public void testFindOverlaps()
54 List<Range> ranges = new ArrayList<Range>();
55 ranges.add(new Range(20, 50));
56 ranges.add(new Range(30, 70));
57 ranges.add(new Range(1, 100));
58 ranges.add(new Range(70, 120));
60 NCList<Range> ncl = new NCList<Range>(ranges);
62 List<Range> overlaps = ncl.findOverlaps(121, 122);
63 assertEquals(overlaps.size(), 0);
65 overlaps = ncl.findOverlaps(21, 22);
66 assertEquals(overlaps.size(), 2);
67 assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 1);
68 assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 100);
69 assertEquals(((ContiguousI) overlaps.get(1)).getBegin(), 20);
70 assertEquals(((ContiguousI) overlaps.get(1)).getEnd(), 50);
72 overlaps = ncl.findOverlaps(110, 110);
73 assertEquals(overlaps.size(), 1);
74 assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 70);
75 assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 120);
78 @Test(groups = "Functional")
79 public void testAdd_onTheEnd()
81 List<Range> ranges = new ArrayList<Range>();
82 ranges.add(new Range(20, 50));
83 NCList<Range> ncl = new NCList<Range>(ranges);
84 assertEquals(ncl.toString(), "[20-50]");
85 assertTrue(ncl.isValid());
87 ncl.add(new Range(60, 70));
88 assertEquals(ncl.toString(), "[20-50, 60-70]");
89 assertTrue(ncl.isValid());
92 @Test(groups = "Functional")
93 public void testAdd_inside()
95 List<Range> ranges = new ArrayList<Range>();
96 ranges.add(new Range(20, 50));
97 NCList<Range> ncl = new NCList<Range>(ranges);
98 assertEquals(ncl.toString(), "[20-50]");
99 assertTrue(ncl.isValid());
101 ncl.add(new Range(30, 40));
102 assertEquals(ncl.toString(), "[20-50 [30-40]]");
105 @Test(groups = "Functional")
106 public void testAdd_onTheFront()
108 List<Range> ranges = new ArrayList<Range>();
109 ranges.add(new Range(20, 50));
110 NCList<Range> ncl = new NCList<Range>(ranges);
111 assertEquals(ncl.toString(), "[20-50]");
112 assertTrue(ncl.isValid());
114 ncl.add(new Range(5, 15));
115 assertEquals(ncl.toString(), "[5-15, 20-50]");
116 assertTrue(ncl.isValid());
119 @Test(groups = "Functional")
120 public void testAdd_enclosing()
122 List<Range> ranges = new ArrayList<Range>();
123 ranges.add(new Range(20, 50));
124 ranges.add(new Range(30, 60));
125 NCList<Range> ncl = new NCList<Range>(ranges);
126 assertEquals(ncl.toString(), "[20-50, 30-60]");
127 assertTrue(ncl.isValid());
128 assertEquals(ncl.getStart(), 20);
130 ncl.add(new Range(10, 70));
131 assertEquals(ncl.toString(), "[10-70 [20-50, 30-60]]");
132 assertTrue(ncl.isValid());
135 @Test(groups = "Functional")
136 public void testAdd_spanning()
138 List<Range> ranges = new ArrayList<Range>();
139 ranges.add(new Range(20, 40));
140 ranges.add(new Range(60, 70));
141 NCList<Range> ncl = new NCList<Range>(ranges);
142 assertEquals(ncl.toString(), "[20-40, 60-70]");
143 assertTrue(ncl.isValid());
145 ncl.add(new Range(30, 50));
146 assertEquals(ncl.toString(), "[20-40, 30-50, 60-70]");
147 assertTrue(ncl.isValid());
149 ncl.add(new Range(40, 65));
150 assertEquals(ncl.toString(), "[20-40, 30-50, 40-65, 60-70]");
151 assertTrue(ncl.isValid());
155 * Provides the scales for pseudo-random NCLists i.e. the range of the maximal
156 * [0-scale] interval to be stored
160 @DataProvider(name = "scalesOfLife")
161 public Object[][] getScales()
163 return new Object[][] { new Integer[] { 10 }, new Integer[] { 100 } };
167 * Do a number of pseudo-random (reproducible) builds of an NCList, to
168 * exercise as many methods of the class as possible while generating the
169 * range of possible structure topologies
171 * <li>verify that add adds an entry and increments size</li>
172 * <li>...except where the entry is already contained (by equals test)</li>
173 * <li>verify that the structure is valid at all stages of construction</li>
174 * <li>generate, run and verify a range of overlap queries</li>
175 * <li>tear down the structure by deleting entries, verifying correctness at
179 @Test(groups = "Functional", dataProvider = "scalesOfLife")
180 public void test_pseudoRandom(Integer scale)
182 NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
183 List<SequenceFeature> features = new ArrayList<SequenceFeature>(scale);
185 testAdd_pseudoRandom(scale, ncl, features);
188 * sort the list of added ranges - this doesn't affect the test,
189 * just makes it easier to inspect the data in the debugger
191 Collections.sort(features, sorter);
193 testFindOverlaps_pseudoRandom(ncl, scale, features);
195 testDelete_pseudoRandom(ncl, features);
199 * Pick randomly selected entries to delete in turn, checking the NCList size
200 * and validity at each stage, until it is empty
205 protected void testDelete_pseudoRandom(NCList<SequenceFeature> ncl,
206 List<SequenceFeature> features)
210 while (!features.isEmpty())
212 assertEquals(ncl.size(), features.size());
213 int toDelete = random.nextInt(features.size());
214 SequenceFeature entry = features.get(toDelete);
215 String lastDeleted = "'" + entry.toString() + "'";
216 assertTrue(ncl.contains(entry), String.format(
217 "NCList doesn't contain entry [%d] %s!", deleted,
220 assertFalse(ncl.contains(entry), String.format(
221 "NCList still contains deleted entry [%d] %s!", deleted,
223 features.remove(toDelete);
226 assertTrue(ncl.isValid(), String.format(
227 "NCList invalid after %d deletions, last deleted was %s",
228 deleted, lastDeleted));
231 * brute force check that deleting one entry didn't delete any others
233 for (int i = 0; i < features.size(); i++)
235 SequenceFeature sf = features.get(i);
236 assertTrue(ncl.contains(sf), String.format(
237 "NCList doesn't contain entry [%d] %s after deleting %s!",
238 i, sf.toString(), lastDeleted));
241 assertEquals(ncl.size(), 0); // all gone
245 * Randomly generate entries and add them to the NCList, checking its validity
246 * and size at each stage. A few entries should be duplicates (by equals test)
253 protected void testAdd_pseudoRandom(Integer scale,
254 NCList<SequenceFeature> ncl,
255 List<SequenceFeature> features)
260 for (int i = 0; i < size; i++)
262 int r1 = random.nextInt(scale + 1);
263 int r2 = random.nextInt(scale + 1);
264 int from = Math.min(r1, r2);
265 int to = Math.max(r1, r2);
268 * choice of two feature values means that occasionally an identical
269 * feature may be generated, in which case it should not be added
271 float value = (float) i % 2;
272 SequenceFeature feature = new SequenceFeature("Pfam", "", from, to,
276 * add to NCList - with duplicate entries (by equals) disallowed
278 ncl.add(feature, false);
279 if (features.contains(feature))
281 System.out.println("Duplicate feature generated "
282 + feature.toString());
286 features.add(feature);
291 * check list format is valid at each stage of its construction
293 assertTrue(ncl.isValid(),
294 String.format("Failed for scale = %d, i=%d", scale, i));
295 assertEquals(ncl.size(), count);
297 // System.out.println(ncl.prettyPrint());
301 * A helper method that generates pseudo-random range queries and veries that
302 * findOverlaps returns the correct matches
305 * the NCList to query
307 * ncl maximal range is [0, scale]
309 * a list of the ranges stored in ncl
311 protected void testFindOverlaps_pseudoRandom(NCList<SequenceFeature> ncl,
313 List<SequenceFeature> features)
315 int halfScale = scale / 2;
316 int minIterations = 20;
319 * generates ranges in [-halfScale, scale+halfScale]
320 * - some should be internal to [0, scale] P = 1/4
321 * - some should lie before 0 P = 1/16
322 * - some should lie after scale P = 1/16
323 * - some should overlap left P = 1/4
324 * - some should overlap right P = 1/4
325 * - some should enclose P = 1/8
327 * 50 iterations give a 96% probability of including the
328 * unlikeliest case; keep going until we have done all!
330 boolean inside = false;
331 boolean enclosing = false;
332 boolean before = false;
333 boolean after = false;
334 boolean overlapLeft = false;
335 boolean overlapRight = false;
336 boolean allCasesCovered = false;
339 while (i < minIterations || !allCasesCovered)
342 int r1 = random.nextInt((scale + 1) * 2);
343 int r2 = random.nextInt((scale + 1) * 2);
344 int from = Math.min(r1, r2) - halfScale;
345 int to = Math.max(r1, r2) - halfScale;
348 * ensure all cases of interest get covered
350 inside |= from >= 0 && to <= scale;
351 enclosing |= from <= 0 && to >= scale;
353 after |= from > scale;
354 overlapLeft |= from < 0 && to >= 0 && to <= scale;
355 overlapRight |= from >= 0 && from <= scale && to > scale;
356 if (!allCasesCovered)
358 allCasesCovered |= inside && enclosing && before && after
359 && overlapLeft && overlapRight;
364 .format("Covered all findOverlaps cases after %d iterations for scale %d",
369 verifyFindOverlaps(ncl, from, to, features);
374 * A helper method that verifies that overlaps found by interrogating an
375 * NCList correctly match those found by brute force search
382 protected void verifyFindOverlaps(NCList<SequenceFeature> ncl, int from,
383 int to, List<SequenceFeature> features)
385 List<SequenceFeature> overlaps = ncl.findOverlaps(from, to);
388 * check returned entries do indeed overlap from-to range
390 for (ContiguousI sf : overlaps)
392 int begin = sf.getBegin();
393 int end = sf.getEnd();
394 assertTrue(begin <= to && end >= from, String.format(
395 "[%d, %d] does not overlap query range [%d, %d]", begin, end,
400 * check overlapping ranges are included in the results
401 * (the test above already shows non-overlapping ranges are not)
403 for (ContiguousI sf : features)
405 int begin = sf.getBegin();
406 int end = sf.getEnd();
407 if (begin <= to && end >= from)
409 boolean found = overlaps.contains(sf);
410 assertTrue(found, String.format(
411 "[%d, %d] missing in query range [%d, %d]", begin, end,
417 @Test(groups = "Functional")
418 public void testGetEntries()
420 List<Range> ranges = new ArrayList<Range>();
421 Range r1 = new Range(20, 20);
422 Range r2 = new Range(10, 20);
423 Range r3 = new Range(15, 30);
424 Range r4 = new Range(10, 30);
425 Range r5 = new Range(11, 19);
426 Range r6 = new Range(10, 20);
434 NCList<Range> ncl = new NCList<Range>(ranges);
435 Range r7 = new Range(1, 100);
438 List<Range> contents = ncl.getEntries();
439 assertEquals(contents.size(), 7);
440 assertTrue(contents.contains(r1));
441 assertTrue(contents.contains(r2));
442 assertTrue(contents.contains(r3));
443 assertTrue(contents.contains(r4));
444 assertTrue(contents.contains(r5));
445 assertTrue(contents.contains(r6));
446 assertTrue(contents.contains(r7));
448 ncl = new NCList<Range>();
449 assertTrue(ncl.getEntries().isEmpty());
452 @Test(groups = "Functional")
453 public void testDelete()
455 List<Range> ranges = new ArrayList<Range>();
456 Range r1 = new Range(20, 30);
458 NCList<Range> ncl = new NCList<Range>(ranges);
459 assertTrue(ncl.getEntries().contains(r1));
461 Range r2 = new Range(20, 30);
462 assertFalse(ncl.delete(null)); // null argument
463 assertFalse(ncl.delete(r2)); // never added
464 assertTrue(ncl.delete(r1)); // success
465 assertTrue(ncl.getEntries().isEmpty());
468 * tests where object.equals() == true
470 NCList<SequenceFeature> features = new NCList<SequenceFeature>();
471 SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
473 SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
476 assertEquals(sf1, sf2); // sf1.equals(sf2)
477 assertFalse(features.delete(sf2)); // equality is not enough for deletion
478 assertTrue(features.getEntries().contains(sf1)); // still there!
479 assertTrue(features.delete(sf1));
480 assertTrue(features.getEntries().isEmpty()); // gone now
483 * test with duplicate objects in NCList
487 assertEquals(features.getEntries().size(), 2);
488 assertSame(features.getEntries().get(0), sf1);
489 assertSame(features.getEntries().get(1), sf1);
490 assertTrue(features.delete(sf1)); // first match only is deleted
491 assertTrue(features.contains(sf1));
492 assertEquals(features.size(), 1);
493 assertTrue(features.delete(sf1));
494 assertTrue(features.getEntries().isEmpty());
497 @Test(groups = "Functional")
498 public void testAdd_overlapping()
500 List<Range> ranges = new ArrayList<Range>();
501 ranges.add(new Range(40, 50));
502 ranges.add(new Range(20, 30));
503 NCList<Range> ncl = new NCList<Range>(ranges);
504 assertEquals(ncl.toString(), "[20-30, 40-50]");
505 assertTrue(ncl.isValid());
508 * add range overlapping internally
510 ncl.add(new Range(25, 35));
511 assertEquals(ncl.toString(), "[20-30, 25-35, 40-50]");
512 assertTrue(ncl.isValid());
515 * add range overlapping last range
517 ncl.add(new Range(45, 55));
518 assertEquals(ncl.toString(), "[20-30, 25-35, 40-50, 45-55]");
519 assertTrue(ncl.isValid());
522 * add range overlapping first range
524 ncl.add(new Range(15, 25));
525 assertEquals(ncl.toString(), "[15-25, 20-30, 25-35, 40-50, 45-55]");
526 assertTrue(ncl.isValid());
530 * Test the contains method (which uses object equals test)
532 @Test(groups = "Functional")
533 public void testContains()
535 NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
536 SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
538 SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
540 SequenceFeature sf3 = new SequenceFeature("type", "desc", 1, 10, 2f,
544 assertTrue(ncl.contains(sf1));
545 assertTrue(ncl.contains(sf2)); // sf1.equals(sf2)
546 assertFalse(ncl.contains(sf3)); // !sf1.equals(sf3)
549 * make some deeper structure in the NCList
551 SequenceFeature sf4 = new SequenceFeature("type", "desc", 2, 9, 2f,
554 assertTrue(ncl.contains(sf4));
555 SequenceFeature sf5 = new SequenceFeature("type", "desc", 4, 5, 2f,
557 SequenceFeature sf6 = new SequenceFeature("type", "desc", 6, 8, 2f,
561 assertTrue(ncl.contains(sf5));
562 assertTrue(ncl.contains(sf6));
565 @Test(groups = "Functional")
566 public void testIsValid()
568 List<Range> ranges = new ArrayList<Range>();
569 Range r1 = new Range(40, 50);
571 NCList<Range> ncl = new NCList<Range>(ranges);
572 assertTrue(ncl.isValid());
574 Range r2 = new Range(42, 44);
576 assertTrue(ncl.isValid());
577 Range r3 = new Range(46, 48);
579 assertTrue(ncl.isValid());
580 Range r4 = new Range(43, 43);
582 assertTrue(ncl.isValid());
584 assertEquals(ncl.toString(), "[40-50 [42-44 [43-43], 46-48]]");
585 assertTrue(ncl.isValid());
588 assertFalse(ncl.isValid()); // r2 not inside r1
590 assertTrue(ncl.isValid());
593 assertFalse(ncl.isValid()); // r3 should precede r2
595 assertTrue(ncl.isValid());
598 assertFalse(ncl.isValid()); // r4 not inside r2
600 assertTrue(ncl.isValid());
603 assertFalse(ncl.isValid()); // r4 has reverse range
606 @Test(groups = "Functional")
607 public void testPrettyPrint()
610 * construct NCList from a list of ranges
611 * they are sorted then assembled into NCList subregions
612 * notice that 42-42 end up inside 41-46
614 List<Range> ranges = new ArrayList<Range>();
615 ranges.add(new Range(40, 50));
616 ranges.add(new Range(45, 55));
617 ranges.add(new Range(40, 45));
618 ranges.add(new Range(41, 46));
619 ranges.add(new Range(42, 42));
620 ranges.add(new Range(42, 42));
621 NCList<Range> ncl = new NCList<Range>(ranges);
622 assertTrue(ncl.isValid());
623 assertEquals(ncl.toString(),
624 "[40-50 [40-45], 41-46 [42-42 [42-42]], 45-55]");
625 String expected = "40-50\n 40-45\n41-46\n 42-42\n 42-42\n45-55\n";
626 assertEquals(ncl.prettyPrint(), expected);
629 * repeat but now add ranges one at a time
630 * notice that 42-42 end up inside 40-50 so we get
631 * a different but equal valid NCList structure
634 ncl = new NCList<Range>(ranges);
635 ncl.add(new Range(40, 50));
636 ncl.add(new Range(45, 55));
637 ncl.add(new Range(40, 45));
638 ncl.add(new Range(41, 46));
639 ncl.add(new Range(42, 42));
640 ncl.add(new Range(42, 42));
641 assertTrue(ncl.isValid());
642 assertEquals(ncl.toString(),
643 "[40-50 [40-45 [42-42 [42-42]], 41-46], 45-55]");
644 expected = "40-50\n 40-45\n 42-42\n 42-42\n 41-46\n45-55\n";
645 assertEquals(ncl.prettyPrint(), expected);
649 * A test that shows different valid trees can be constructed from the same
650 * set of ranges, depending on the order of construction
652 @Test(groups = "Functional")
653 public void testConstructor_alternativeTrees()
655 List<Range> ranges = new ArrayList<Range>();
656 ranges.add(new Range(10, 60));
657 ranges.add(new Range(20, 30));
658 ranges.add(new Range(40, 50));
661 * constructor with greedy traversal of sorted ranges to build nested
662 * containment lists results in 20-30 inside 10-60, 40-50 a sibling
664 NCList<Range> ncl = new NCList<Range>(ranges);
665 assertEquals(ncl.toString(), "[10-60 [20-30], 40-50]");
666 assertTrue(ncl.isValid());
669 * adding ranges one at a time results in 40-50
670 * a sibling of 20-30 inside 10-60
672 ncl = new NCList<Range>(new Range(10, 60));
673 ncl.add(new Range(20, 30));
674 ncl.add(new Range(40, 50));
675 assertEquals(ncl.toString(), "[10-60 [20-30, 40-50]]");
676 assertTrue(ncl.isValid());