X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=test%2Fjalview%2Fdatamodel%2Ffeatures%2FNCListTest.java;h=2c7f752d43fe19c8039f722d4e63b467077ba9c5;hb=refs%2Fheads%2Ffeatures%2FJAL-1793VCF;hp=367e424d90a033be0128ae5d99a4ea95fbb9ddca;hpb=0ea61b395605ecf1854406f8e0c9a0be04404cb1;p=jalview.git diff --git a/test/jalview/datamodel/features/NCListTest.java b/test/jalview/datamodel/features/NCListTest.java index 367e424..2c7f752 100644 --- a/test/jalview/datamodel/features/NCListTest.java +++ b/test/jalview/datamodel/features/NCListTest.java @@ -1,46 +1,30 @@ package jalview.datamodel.features; - import static org.testng.Assert.assertEquals; +import static org.testng.Assert.assertFalse; +import static org.testng.Assert.assertSame; import static org.testng.Assert.assertTrue; +import jalview.datamodel.ContiguousI; +import jalview.datamodel.Range; +import jalview.datamodel.SequenceFeature; + import java.util.ArrayList; import java.util.Collections; +import java.util.Comparator; import java.util.List; import java.util.Random; +import junit.extensions.PA; + +import org.testng.annotations.DataProvider; import org.testng.annotations.Test; public class NCListTest { - class Range implements ContiguousI - { - int start; - - int end; - - @Override - public int getBegin() - { - return start; - } - - @Override - public int getEnd() - { - return end; - } - Range(int i, int j) - { - start = i; - end = j; - } + private Random random = new Random(107); - @Override - public String toString() { - return String.valueOf(start) + "-" + String.valueOf(end); - } - } + private Comparator sorter = new RangeComparator(true); /** * A basic sanity test of the constructor @@ -172,34 +156,527 @@ public class NCListTest } /** - * Do a number of pseudo-random (reproducible) builds of an NCList, with - * checks for validity of the data structure, for greater (but not perfect!) - * confidence that corner cases are being handled correctly. + * Provides the scales for pseudo-random NCLists i.e. the range of the maximal + * [0-scale] interval to be stored + * + * @return */ - @Test(groups = "Functional") - public void testAdd_pseudoRandom() + @DataProvider(name = "scalesOfLife") + public Object[][] getScales() { - Random r = new Random(108); // well why not? - int[] scales = new int[] { 10, 100, 1000 }; + return new Object[][] { new Integer[] { 10 }, new Integer[] { 100 } }; + } - for (int scale : scales) + /** + * Do a number of pseudo-random (reproducible) builds of an NCList, to + * exercise as many methods of the class as possible while generating the + * range of possible structure topologies + * + */ + @Test(groups = "Functional", dataProvider = "scalesOfLife") + public void test_pseudoRandom(Integer scale) + { + NCList ncl = new NCList(); + List features = new ArrayList(scale); + + testAdd_pseudoRandom(scale, ncl, features); + + /* + * sort the list of added ranges - this doesn't affect the test, + * just makes it easier to inspect the data in the debugger + */ + Collections.sort(features, sorter); + + testFindOverlaps_pseudoRandom(ncl, scale, features); + + testDelete_pseudoRandom(ncl, features); + } + + /** + * Pick randomly selected entries to delete in turn, checking the NCList size + * and validity at each stage, until it is empty + * + * @param ncl + * @param features + */ + protected void testDelete_pseudoRandom(NCList ncl, + List features) + { + int deleted = 0; + + while (!features.isEmpty()) { - NCList ncl = new NCList(); - int size = 0; - for (int i = 0; i < 100; i++) + assertEquals(ncl.size(), features.size()); + int toDelete = random.nextInt(features.size()); + SequenceFeature entry = features.get(toDelete); + assertTrue(ncl.contains(entry), String.format( + "NCList doesn't contain entry [%d] '%s'!", deleted, + entry.toString())); + + ncl.delete(entry); + assertFalse(ncl.contains(entry), String.format( + "NCList still contains deleted entry [%d] '%s'!", deleted, + entry.toString())); + features.remove(toDelete); + deleted++; + + assertTrue(ncl.isValid(), String.format( + "NCList invalid after %d deletions, last deleted was '%s'", + deleted, entry.toString())); + + /* + * brute force check that deleting one entry didn't delete any others + */ + for (int i = 0; i < features.size(); i++) { - int r1 = r.nextInt(scale); - int r2 = r.nextInt(scale); - int nextFrom = Math.min(r1, r2); - int nextTo = Math.max(r1, r2); - Range range = new Range(nextFrom, nextTo); - ncl.add(range); - assertTrue(ncl.isValid(), - String.format("Failed for scale = %d, i=%d", scale, i)); - size++; - assertEquals(ncl.getSize(), size); + SequenceFeature sf = features.get(i); + assertTrue(ncl.contains(sf), String.format( + "NCList doesn't contain entry [%d] %s after deleting '%s'!", + i, sf.toString(), entry.toString())); } - System.out.println(ncl.prettyPrint()); } + assertEquals(ncl.size(), 0); // all gone + } + + /** + * Randomly generate entries and add them to the NCList, checking its validity + * and size at each stage. A few entries should be duplicates (by equals test) + * so not get added. + * + * @param scale + * @param ncl + * @param features + */ + protected void testAdd_pseudoRandom(Integer scale, + NCList ncl, + List features) + { + int count = 0; + final int size = 50; + + for (int i = 0; i < size; i++) + { + int r1 = random.nextInt(scale + 1); + int r2 = random.nextInt(scale + 1); + int from = Math.min(r1, r2); + int to = Math.max(r1, r2); + + /* + * choice of two feature values means that occasionally an identical + * feature may be generated, in which case it should not be added + */ + float value = (float) i % 2; + SequenceFeature feature = new SequenceFeature("Pfam", "", from, to, + value, "group"); + + /* + * add to NCList - with duplicate entries (by equals) disallowed + */ + ncl.add(feature, false); + if (features.contains(feature)) + { + System.out.println("Duplicate feature generated " + + feature.toString()); + } + else + { + features.add(feature); + count++; + } + + /* + * check list format is valid at each stage of its construction + */ + assertTrue(ncl.isValid(), + String.format("Failed for scale = %d, i=%d", scale, i)); + assertEquals(ncl.size(), count); + } + // System.out.println(ncl.prettyPrint()); + } + + /** + * A helper method that generates pseudo-random range queries and veries that + * findOverlaps returns the correct matches + * + * @param ncl + * the NCList to query + * @param scale + * ncl maximal range is [0, scale] + * @param features + * a list of the ranges stored in ncl + */ + protected void testFindOverlaps_pseudoRandom(NCList ncl, + int scale, + List features) + { + int halfScale = scale / 2; + int minIterations = 20; + + /* + * generates ranges in [-halfScale, scale+halfScale] + * - some should be internal to [0, scale] P = 1/4 + * - some should lie before 0 P = 1/16 + * - some should lie after scale P = 1/16 + * - some should overlap left P = 1/4 + * - some should overlap right P = 1/4 + * - some should enclose P = 1/8 + * + * 50 iterations give a 96% probability of including the + * unlikeliest case; keep going until we have done all! + */ + boolean inside = false; + boolean enclosing = false; + boolean before = false; + boolean after = false; + boolean overlapLeft = false; + boolean overlapRight = false; + boolean allCasesCovered = false; + + int i = 0; + while (i < minIterations || !allCasesCovered) + { + i++; + int r1 = random.nextInt((scale + 1) * 2); + int r2 = random.nextInt((scale + 1) * 2); + int from = Math.min(r1, r2) - halfScale; + int to = Math.max(r1, r2) - halfScale; + + /* + * ensure all cases of interest get covered + */ + inside |= from >= 0 && to <= scale; + enclosing |= from <= 0 && to >= scale; + before |= to < 0; + after |= from > scale; + overlapLeft |= from < 0 && to >= 0 && to <= scale; + overlapRight |= from >= 0 && from <= scale && to > scale; + if (!allCasesCovered) + { + allCasesCovered |= inside && enclosing && before && after + && overlapLeft && overlapRight; + if (allCasesCovered) + { + System.out + .println(String + .format("Covered all findOverlaps cases after %d iterations for scale %d", + i, scale)); + } + } + + verifyFindOverlaps(ncl, from, to, features); + } + } + + /** + * A helper method that verifies that overlaps found by interrogating an + * NCList correctly match those found by brute force search + * + * @param ncl + * @param from + * @param to + * @param features + */ + protected void verifyFindOverlaps(NCList ncl, int from, + int to, List features) + { + List overlaps = ncl.findOverlaps(from, to); + + /* + * check returned entries do indeed overlap from-to range + */ + for (ContiguousI sf : overlaps) + { + int begin = sf.getBegin(); + int end = sf.getEnd(); + assertTrue(begin <= to && end >= from, String.format( + "[%d, %d] does not overlap query range [%d, %d]", begin, end, + from, to)); + } + + /* + * check overlapping ranges are included in the results + * (the test above already shows non-overlapping ranges are not) + */ + for (ContiguousI sf : features) + { + int begin = sf.getBegin(); + int end = sf.getEnd(); + if (begin <= to && end >= from) + { + boolean found = overlaps.contains(sf); + assertTrue(found, String.format( + "[%d, %d] missing in query range [%d, %d]", begin, end, + from, to)); + } + } + } + + @Test(groups = "Functional") + public void testGetEntries() + { + List ranges = new ArrayList(); + Range r1 = new Range(20, 20); + Range r2 = new Range(10, 20); + Range r3 = new Range(15, 30); + Range r4 = new Range(10, 30); + Range r5 = new Range(11, 19); + Range r6 = new Range(10, 20); + ranges.add(r1); + ranges.add(r2); + ranges.add(r3); + ranges.add(r4); + ranges.add(r5); + ranges.add(r6); + + NCList ncl = new NCList(ranges); + Range r7 = new Range(1, 100); + ncl.add(r7); + + List contents = ncl.getEntries(); + assertEquals(contents.size(), 7); + assertTrue(contents.contains(r1)); + assertTrue(contents.contains(r2)); + assertTrue(contents.contains(r3)); + assertTrue(contents.contains(r4)); + assertTrue(contents.contains(r5)); + assertTrue(contents.contains(r6)); + assertTrue(contents.contains(r7)); + + ncl = new NCList(); + assertTrue(ncl.getEntries().isEmpty()); + } + + @Test(groups = "Functional") + public void testDelete() + { + List ranges = new ArrayList(); + Range r1 = new Range(20, 30); + ranges.add(r1); + NCList ncl = new NCList(ranges); + assertTrue(ncl.getEntries().contains(r1)); + + Range r2 = new Range(20, 30); + assertFalse(ncl.delete(null)); // null argument + assertFalse(ncl.delete(r2)); // never added + assertTrue(ncl.delete(r1)); // success + assertTrue(ncl.getEntries().isEmpty()); + + /* + * tests where object.equals() == true + */ + NCList features = new NCList(); + SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f, + "group"); + SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f, + "group"); + features.add(sf1); + assertEquals(sf1, sf2); // sf1.equals(sf2) + assertFalse(features.delete(sf2)); // equality is not enough for deletion + assertTrue(features.getEntries().contains(sf1)); // still there! + assertTrue(features.delete(sf1)); + assertTrue(features.getEntries().isEmpty()); // gone now + + /* + * test with duplicate objects in NCList + */ + features.add(sf1); + features.add(sf1); + assertEquals(features.getEntries().size(), 2); + assertSame(features.getEntries().get(0), sf1); + assertSame(features.getEntries().get(1), sf1); + assertTrue(features.delete(sf1)); // first match only is deleted + assertTrue(features.contains(sf1)); + assertEquals(features.size(), 1); + assertTrue(features.delete(sf1)); + assertTrue(features.getEntries().isEmpty()); + } + + @Test(groups = "Functional") + public void testAdd_overlapping() + { + List ranges = new ArrayList(); + ranges.add(new Range(40, 50)); + ranges.add(new Range(20, 30)); + NCList ncl = new NCList(ranges); + assertEquals(ncl.toString(), "[20-30, 40-50]"); + assertTrue(ncl.isValid()); + + /* + * add range overlapping internally + */ + ncl.add(new Range(25, 35)); + assertEquals(ncl.toString(), "[20-30, 25-35, 40-50]"); + assertTrue(ncl.isValid()); + + /* + * add range overlapping last range + */ + ncl.add(new Range(45, 55)); + assertEquals(ncl.toString(), "[20-30, 25-35, 40-50, 45-55]"); + assertTrue(ncl.isValid()); + + /* + * add range overlapping first range + */ + ncl.add(new Range(15, 25)); + assertEquals(ncl.toString(), "[15-25, 20-30, 25-35, 40-50, 45-55]"); + assertTrue(ncl.isValid()); + } + + /** + * Test the contains method (which uses object equals test) + */ + @Test(groups = "Functional") + public void testContains() + { + NCList ncl = new NCList(); + SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f, + "group"); + SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f, + "group"); + SequenceFeature sf3 = new SequenceFeature("type", "desc", 1, 10, 2f, + "anothergroup"); + ncl.add(sf1); + + assertTrue(ncl.contains(sf1)); + assertTrue(ncl.contains(sf2)); // sf1.equals(sf2) + assertFalse(ncl.contains(sf3)); // !sf1.equals(sf3) + + /* + * make some deeper structure in the NCList + */ + SequenceFeature sf4 = new SequenceFeature("type", "desc", 2, 9, 2f, + "group"); + ncl.add(sf4); + assertTrue(ncl.contains(sf4)); + SequenceFeature sf5 = new SequenceFeature("type", "desc", 4, 5, 2f, + "group"); + SequenceFeature sf6 = new SequenceFeature("type", "desc", 6, 8, 2f, + "group"); + ncl.add(sf5); + ncl.add(sf6); + assertTrue(ncl.contains(sf5)); + assertTrue(ncl.contains(sf6)); + } + + @Test(groups = "Functional") + public void testIsValid() + { + List ranges = new ArrayList(); + Range r1 = new Range(40, 50); + ranges.add(r1); + NCList ncl = new NCList(ranges); + assertTrue(ncl.isValid()); + + Range r2 = new Range(42, 44); + ncl.add(r2); + assertTrue(ncl.isValid()); + Range r3 = new Range(46, 48); + ncl.add(r3); + assertTrue(ncl.isValid()); + Range r4 = new Range(43, 43); + ncl.add(r4); + assertTrue(ncl.isValid()); + + assertEquals(ncl.toString(), "[40-50 [42-44 [43-43], 46-48]]"); + assertTrue(ncl.isValid()); + + PA.setValue(r1, "start", 43); + assertFalse(ncl.isValid()); // r2 not inside r1 + PA.setValue(r1, "start", 40); + assertTrue(ncl.isValid()); + + PA.setValue(r3, "start", 41); + assertFalse(ncl.isValid()); // r3 should precede r2 + PA.setValue(r3, "start", 46); + assertTrue(ncl.isValid()); + + PA.setValue(r4, "start", 41); + assertFalse(ncl.isValid()); // r4 not inside r2 + PA.setValue(r4, "start", 43); + assertTrue(ncl.isValid()); + + PA.setValue(r4, "start", 44); + assertFalse(ncl.isValid()); // r4 has reverse range + } + + @Test(groups = "Functional") + public void testPrettyPrint() + { + /* + * construct NCList from a list of ranges + * they are sorted then assembled into NCList subregions + * notice that 42-42 end up inside 41-46 + */ + List ranges = new ArrayList(); + ranges.add(new Range(40, 50)); + ranges.add(new Range(45, 55)); + ranges.add(new Range(40, 45)); + ranges.add(new Range(41, 46)); + ranges.add(new Range(42, 42)); + ranges.add(new Range(42, 42)); + NCList ncl = new NCList(ranges); + assertTrue(ncl.isValid()); + assertEquals(ncl.toString(), + "[40-50 [40-45], 41-46 [42-42 [42-42]], 45-55]"); + String expected = "40-50\n 40-45\n41-46\n 42-42\n 42-42\n45-55\n"; + assertEquals(ncl.prettyPrint(), expected); + + /* + * repeat but now add ranges one at a time + * notice that 42-42 end up inside 40-50 so we get + * a different but equal valid NCList structure + */ + ranges.clear(); + ncl = new NCList(ranges); + ncl.add(new Range(40, 50)); + ncl.add(new Range(45, 55)); + ncl.add(new Range(40, 45)); + ncl.add(new Range(41, 46)); + ncl.add(new Range(42, 42)); + ncl.add(new Range(42, 42)); + assertTrue(ncl.isValid()); + assertEquals(ncl.toString(), + "[40-50 [40-45 [42-42 [42-42]], 41-46], 45-55]"); + expected = "40-50\n 40-45\n 42-42\n 42-42\n 41-46\n45-55\n"; + assertEquals(ncl.prettyPrint(), expected); + } + + /** + * A test that shows different valid trees can be constructed from the same + * set of ranges, depending on the order of construction + */ + @Test(groups = "Functional") + public void testConstructor_alternativeTrees() + { + List ranges = new ArrayList(); + ranges.add(new Range(10, 60)); + ranges.add(new Range(20, 30)); + ranges.add(new Range(40, 50)); + + /* + * constructor with greedy traversal of sorted ranges to build nested + * containment lists results in 20-30 inside 10-60, 40-50 a sibling + */ + NCList ncl = new NCList(ranges); + assertEquals(ncl.toString(), "[10-60 [20-30], 40-50]"); + assertTrue(ncl.isValid()); + + /* + * adding ranges one at a time results in 40-50 + * a sibling of 20-30 inside 10-60 + */ + ncl = new NCList(new Range(10, 60)); + ncl.add(new Range(20, 30)); + ncl.add(new Range(40, 50)); + assertEquals(ncl.toString(), "[10-60 [20-30, 40-50]]"); + assertTrue(ncl.isValid()); } }