From 7f4b42c9b73c4e5e101aa2bb390af2d1df9a0f0a Mon Sep 17 00:00:00 2001 From: gmungoc Date: Fri, 7 Apr 2017 10:26:37 +0100 Subject: [PATCH] JAL-2446 added delete/contains to pseudo-random tests, fail fixes --- src/jalview/datamodel/features/NCList.java | 51 ++--- src/jalview/datamodel/features/NCNode.java | 17 +- test/jalview/datamodel/features/NCListTest.java | 278 ++++++++++++++++++++--- test/jalview/datamodel/features/NCNodeTest.java | 38 +++- 4 files changed, 311 insertions(+), 73 deletions(-) diff --git a/src/jalview/datamodel/features/NCList.java b/src/jalview/datamodel/features/NCList.java index 17e08eb..9906884 100644 --- a/src/jalview/datamodel/features/NCList.java +++ b/src/jalview/datamodel/features/NCList.java @@ -99,6 +99,11 @@ public class NCList { List sublists = new ArrayList(); + if (ranges.isEmpty()) + { + return sublists; + } + int listStartIndex = 0; long lastEndPos = Long.MAX_VALUE; @@ -188,7 +193,7 @@ public class NCList { NCNode subrange = subranges.get(j); - if (end < subrange.getStart() && !overlapping && !enclosing) + if (end < subrange.getBegin() && !overlapping && !enclosing) { /* * new entry lies between subranges j-1 j @@ -197,7 +202,7 @@ public class NCList return true; } - if (subrange.getStart() <= start && subrange.getEnd() >= end) + if (subrange.getBegin() <= start && subrange.getEnd() >= end) { /* * push new entry inside this subrange as it encloses it @@ -206,7 +211,7 @@ public class NCList return true; } - if (start <= subrange.getStart()) + if (start <= subrange.getBegin()) { if (end >= subrange.getEnd()) { @@ -293,7 +298,7 @@ public class NCList for (int i = candidateIndex; i < subranges.size(); i++) { NCNode candidate = subranges.get(i); - if (candidate.getStart() > to) + if (candidate.getBegin() > to) { /* * we are past the end of our target range @@ -373,7 +378,7 @@ public class NCList for (int i = candidateIndex; i < subranges.size(); i++) { NCNode candidate = subranges.get(i); - if (candidate.getStart() > to) + if (candidate.getBegin() > to) { /* * we are past the end of our target range @@ -427,7 +432,7 @@ public class NCList } /** - * Returns a string representation of the data where containment is shown bgy + * Returns a string representation of the data where containment is shown by * indentation on new lines * * @return @@ -438,6 +443,7 @@ public class NCList int offset = 0; int indent = 2; prettyPrint(sb, offset, indent); + sb.append(System.lineSeparator()); return sb.toString(); } @@ -488,7 +494,7 @@ public class NCList int lastStart = start; for (NCNode subrange : subranges) { - if (subrange.getStart() < lastStart) + if (subrange.getBegin() < lastStart) { System.err.println("error in NCList: range " + subrange.toString() + " starts before " + lastStart); @@ -500,7 +506,7 @@ public class NCList + " ends after " + end); return false; } - lastStart = subrange.getStart(); + lastStart = subrange.getBegin(); if (!subrange.isValid()) { @@ -517,7 +523,7 @@ public class NCList */ public int getStart() { - return subranges.isEmpty() ? 0 : subranges.get(0).getStart(); + return subranges.isEmpty() ? 0 : subranges.get(0).getBegin(); } /** @@ -579,12 +585,17 @@ public class NCList { /* * if the subrange is rooted on this entry, promote its - * subregions (if any) to replace the subrange here + * subregions (if any) to replace the subrange here; + * NB have to resort subranges after doing this since e.g. + * [10-30 [12-20 [16-18], 13-19]] + * after deleting 12-20, 16-18 is promoted to sibling of 13-19 + * but should follow it in the list of subranges of 10-30 */ subranges.remove(i); if (subRegions != null) { subranges.addAll(i, subRegions.subranges); + Collections.sort(subranges, intervalSorter); } size--; return true; @@ -600,24 +611,4 @@ public class NCList } return false; } - - /** - * Answers true if this contains no ranges - * - * @return - */ - public boolean isEmpty() - { - return getSize() == 0; - } - - /** - * Answer the list of subranges held in this NCList - * - * @return - */ - List> getSubregions() - { - return subranges; - } } diff --git a/src/jalview/datamodel/features/NCNode.java b/src/jalview/datamodel/features/NCNode.java index 0755614..5fb2d0d 100644 --- a/src/jalview/datamodel/features/NCNode.java +++ b/src/jalview/datamodel/features/NCNode.java @@ -9,7 +9,7 @@ import java.util.List; * * @param */ -class NCNode +class NCNode implements ContiguousI { /* * deep size (number of ranges included) @@ -69,12 +69,14 @@ class NCNode } } - int getStart() + @Override + public int getBegin() { return region.getBegin(); } - int getEnd() + @Override + public int getEnd() { return region.getEnd(); } @@ -158,11 +160,18 @@ class NCNode */ boolean isValid() { + /* + * we don't handle reverse ranges + */ + if (region != null && region.getBegin() > region.getEnd()) + { + return false; + } if (subregions == null) { return true; } - return subregions.isValid(getStart(), getEnd()); + return subregions.isValid(getBegin(), getEnd()); } /** diff --git a/test/jalview/datamodel/features/NCListTest.java b/test/jalview/datamodel/features/NCListTest.java index e0d3659..e874ce4 100644 --- a/test/jalview/datamodel/features/NCListTest.java +++ b/test/jalview/datamodel/features/NCListTest.java @@ -164,45 +164,136 @@ public class NCListTest } /** - * Do a number of pseudo-random (reproducible) builds of an NCList, with - * 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. + * 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 + *
    + *
  • verify that add adds an entry and increments size
    • + *
  • ...except where the entry is already contained (by equals test)
    • + *
  • verify that the structure is valid at all stages of construction
    • + *
  • generate, run and verify a range of overlap queries
    • + *
  • tear down the structure by deleting entries, verifying correctness at + * each stage
    • + *
*/ @Test(groups = "Functional", dataProvider = "scalesOfLife") - public void testAdd_FindOverlaps_pseudoRandom(Integer scale) + public void test_pseudoRandom(Integer scale) { - NCList ncl = new NCList(); - int count = 0; - List ranges = new ArrayList(scale); + NCList ncl = new NCList(); + List features = new ArrayList(scale); - for (int i = 0; i < scale; i++) + 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 + */ + void testDelete_pseudoRandom(NCList ncl, + List features) + { + int deleted = 0; + + while (!features.isEmpty()) + { + assertEquals(ncl.getSize(), features.size()); + int toDelete = random.nextInt(features.size()); + SequenceFeature entry = features.get(toDelete); + String lastDeleted = "'" + entry.toString() + "'"; + assertTrue(ncl.contains(entry), String.format( + "NCList doesn't contain entry [%d] %s!", deleted, + lastDeleted)); + ncl.delete(entry); + assertFalse(ncl.contains(entry), String.format( + "NCList still contains deleted entry [%d] %s!", deleted, + lastDeleted)); + features.remove(toDelete); + deleted++; + + assertTrue(ncl.isValid(), String.format( + "NCList invalid after %d deletions, last deleted was %s", + deleted, lastDeleted)); + + /* + * brute force check that deleting one entry didn't delete any others + */ + for (int i = 0; i < features.size(); i++) + { + SequenceFeature sf = features.get(i); + assertTrue(ncl.contains(sf), String.format( + "NCList doesn't contain entry [%d] %s after deleting %s!", + i, sf.toString(), lastDeleted)); + } + } + assertEquals(ncl.getSize(), 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 + */ + 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); - Range range = new Range(from, to); - ncl.add(range); - ranges.add(range); + + /* + * 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)); - 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); } /** @@ -213,11 +304,12 @@ public class NCListTest * the NCList to query * @param scale * ncl maximal range is [0, scale] - * @param ranges + * @param features * a list of the ranges stored in ncl */ - protected void testFindOverlaps(NCList ncl, int scale, - List ranges) + protected void testFindOverlaps_pseudoRandom(NCList ncl, + int scale, + List features) { int halfScale = scale / 2; int minIterations = 20; @@ -273,7 +365,7 @@ public class NCListTest } } - verifyFindOverlaps(ncl, from, to, ranges); + verifyFindOverlaps(ncl, from, to, features); } } @@ -284,20 +376,20 @@ public class NCListTest * @param ncl * @param from * @param to - * @param ranges + * @param features */ - protected void verifyFindOverlaps(NCList ncl, int from, int to, - List ranges) + protected void verifyFindOverlaps(NCList ncl, int from, + int to, List features) { - List overlaps = ncl.findOverlaps(from, to); + List overlaps = ncl.findOverlaps(from, to); /* * check returned entries do indeed overlap from-to range */ - for (Range r : overlaps) + for (ContiguousI sf : overlaps) { - int begin = r.getBegin(); - int end = r.getEnd(); + 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)); @@ -307,13 +399,13 @@ public class NCListTest * check overlapping ranges are included in the results * (the test above already shows non-overlapping ranges are not) */ - for (Range r : ranges) + for (ContiguousI sf : features) { - int begin = r.getBegin(); - int end = r.getEnd(); + int begin = sf.getBegin(); + int end = sf.getEnd(); if (begin <= to && end >= from) { - boolean found = overlaps.contains(r); + boolean found = overlaps.contains(sf); assertTrue(found, String.format( "[%d, %d] missing in query range [%d, %d]", begin, end, from, to)); @@ -468,4 +560,118 @@ public class NCListTest 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()); + + r1.start = 43; + assertFalse(ncl.isValid()); // r2 not inside r1 + r1.start = 40; + assertTrue(ncl.isValid()); + + r3.start = 41; + assertFalse(ncl.isValid()); // r3 should precede r2 + r3.start = 46; + assertTrue(ncl.isValid()); + + r4.start = 41; + assertFalse(ncl.isValid()); // r4 not inside r2 + r4.start = 43; + assertTrue(ncl.isValid()); + + 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()); + } } diff --git a/test/jalview/datamodel/features/NCNodeTest.java b/test/jalview/datamodel/features/NCNodeTest.java index 73f957e..4198fec 100644 --- a/test/jalview/datamodel/features/NCNodeTest.java +++ b/test/jalview/datamodel/features/NCNodeTest.java @@ -18,7 +18,7 @@ public class NCNodeTest { Range r1 = new Range(10, 20); NCNode node = new NCNode(r1); - assertEquals(node.getStart(), 10); + assertEquals(node.getBegin(), 10); Range r2 = new Range(10, 15); node.add(r2); @@ -36,7 +36,7 @@ public class NCNodeTest { Range r1 = new Range(10, 20); NCNode node = new NCNode(r1); - assertEquals(node.getStart(), 10); + assertEquals(node.getBegin(), 10); Range r2 = new Range(9, 15); node.add(r2); } @@ -48,7 +48,7 @@ public class NCNodeTest { Range r1 = new Range(10, 20); NCNode node = new NCNode(r1); - assertEquals(node.getStart(), 10); + assertEquals(node.getBegin(), 10); Range r2 = new Range(12, 21); node.add(r2); } @@ -99,4 +99,36 @@ public class NCNodeTest assertFalse(node.contains(sf3)); // !sf1.equals(sf3) } + /** + * Test method that checks for valid structure. Valid means that all + * subregions (if any) lie within the root range, and that all subregions have + * valid structure. + */ + @Test(groups = "Functional") + public void testIsValid() + { + Range r1 = new Range(10, 20); + Range r2 = new Range(14, 15); + Range r3 = new Range(16, 17); + NCNode node = new NCNode(r1); + node.add(r2); + node.add(r3); + + /* + * node has root range [10-20] and contains an + * NCList of [14-15, 16-17] + */ + assertTrue(node.isValid()); + r1.start = 15; + assertFalse(node.isValid()); // r2 not within r1 + r1.start = 10; + assertTrue(node.isValid()); + r1.end = 16; + assertFalse(node.isValid()); // r3 not within r1 + r1.end = 20; + assertTrue(node.isValid()); + r3.start = 12; + assertFalse(node.isValid()); // r3 should precede r2 + + } } -- 1.7.10.2