From 41cee8a4b26678d0d4c5e42e852a0b50cbc9bb2e Mon Sep 17 00:00:00 2001 From: gmungoc Date: Thu, 6 Apr 2017 12:07:13 +0100 Subject: [PATCH] JAL-2446 pseudo-random test of findOverlaps, bug fix for for add overlapping range at end --- src/jalview/datamodel/features/NCList.java | 5 + test/jalview/datamodel/features/NCListTest.java | 225 ++++++++++++++++++++--- 2 files changed, 208 insertions(+), 22 deletions(-) diff --git a/src/jalview/datamodel/features/NCList.java b/src/jalview/datamodel/features/NCList.java index 6a9f750..02f94b6 100644 --- a/src/jalview/datamodel/features/NCList.java +++ b/src/jalview/datamodel/features/NCList.java @@ -235,11 +235,16 @@ public class NCList /* * drops through to here if new range encloses all others + * or overlaps the last one */ if (enclosing) { addEnclosingRange(entry, firstEnclosed, lastEnclosed); } + else + { + subranges.add(new NCNode(entry)); + } } /** diff --git a/test/jalview/datamodel/features/NCListTest.java b/test/jalview/datamodel/features/NCListTest.java index cb3a133..ca4288c 100644 --- a/test/jalview/datamodel/features/NCListTest.java +++ b/test/jalview/datamodel/features/NCListTest.java @@ -1,18 +1,23 @@ package jalview.datamodel.features; - import static org.testng.Assert.assertEquals; import static org.testng.Assert.assertTrue; import java.util.ArrayList; import java.util.Collections; +import java.util.Comparator; import java.util.List; import java.util.Random; +import org.testng.annotations.DataProvider; import org.testng.annotations.Test; public class NCListTest { + private Random random = new Random(107); + + private Comparator sorter = new RangeComparator(true); + /** * A basic sanity test of the constructor */ @@ -143,34 +148,172 @@ public class NCListTest } /** + * Provides the scales for pseudo-random NCLists i.e. the range of the maximal + * [0-scale] interval to be stored + * + * @return + */ + @DataProvider(name = "scalesOfLife") + public Object[][] getScales() + { + return new Object[][] { new Integer[] { 10 }, new Integer[] { 100 } }; + } + + /** * 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. + * checks for validity of the data structure, and searches for (pseudo-random) + * overlap ranges, for greater (but not perfect!) confidence that corner cases + * are being handled correctly. */ - @Test(groups = "Functional") - public void testAdd_pseudoRandom() + @Test(groups = "Functional", dataProvider = "scalesOfLife") + public void testAdd_FindOverlaps_pseudoRandom(Integer scale) { - Random r = new Random(108); // well why not? - int[] scales = new int[] { 10, 100, 1000 }; + NCList ncl = new NCList(); + int count = 0; + List ranges = new ArrayList(scale); + + for (int i = 0; i < scale; 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); + Range range = new Range(from, to); + ncl.add(range); + ranges.add(range); + + /* + * check list format is valid at each stage of its construction + */ + assertTrue(ncl.isValid(), + String.format("Failed for scale = %d, i=%d", scale, i)); + count++; + assertEquals(ncl.getSize(), count); + } + // System.out.println(ncl.prettyPrint()); + + /* + * 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(ranges, sorter); + + testFindOverlaps(ncl, scale, ranges); + } - for (int scale : scales) + /** + * 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 ranges + * a list of the ranges stored in ncl + */ + protected void testFindOverlaps(NCList ncl, int scale, + List ranges) + { + 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) { - NCList ncl = new NCList(); - int size = 0; - for (int i = 0; i < 100; i++) + 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) { - 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); + 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, ranges); + } + } + + /** + * 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 ranges + */ + protected void verifyFindOverlaps(NCList ncl, int from, int to, + List ranges) + { + List overlaps = ncl.findOverlaps(from, to); + + /* + * check returned entries do indeed overlap from-to range + */ + for (Range r : overlaps) + { + int begin = r.getBegin(); + int end = r.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 (Range r : ranges) + { + int begin = r.getBegin(); + int end = r.getEnd(); + if (begin <= to && end >= from) + { + boolean found = overlaps.contains(r); + assertTrue(found, String.format( + "[%d, %d] missing in query range [%d, %d]", begin, end, + from, to)); } - System.out.println(ncl.prettyPrint()); } } @@ -208,4 +351,42 @@ public class NCListTest ncl = new NCList(); assertTrue(ncl.getEntries().isEmpty()); } + + @Test(groups = "Functional") + public void testDelete() + { + assertTrue(false, "todo"); + } + + @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()); + } } -- 1.7.10.2