From 0ea61b395605ecf1854406f8e0c9a0be04404cb1 Mon Sep 17 00:00:00 2001 From: gmungoc Date: Mon, 3 Apr 2017 10:07:03 +0100 Subject: [PATCH] JAL-2446 pseudo-random generator unit test, and fixes arising --- src/jalview/datamodel/features/NCList.java | 162 +++++++++++++++++++++-- src/jalview/datamodel/features/NCNode.java | 46 ++++++- test/jalview/datamodel/features/NCListTest.java | 49 ++++++- 3 files changed, 242 insertions(+), 15 deletions(-) diff --git a/src/jalview/datamodel/features/NCList.java b/src/jalview/datamodel/features/NCList.java index 7046670..40b062a 100644 --- a/src/jalview/datamodel/features/NCList.java +++ b/src/jalview/datamodel/features/NCList.java @@ -14,6 +14,10 @@ import java.util.List; */ public class NCList { + /* + * the number of ranges represented + */ + private int size; /* * a list, in start position order, of sublists of ranges ordered so @@ -38,6 +42,7 @@ public class NCList */ public NCList(List ranges) { + this(); build(ranges); } @@ -54,8 +59,6 @@ public class NCList List sublists = findSubranges(ranges); - subranges = new ArrayList>(); - /* * convert each subrange to an NCNode consisting of a range and * (possibly) its contained NCList @@ -65,16 +68,23 @@ public class NCList subranges.add(new NCNode(ranges.subList(sublist.startIndex, sublist.endIndex + 1))); } - sublists.clear(); + + size = ranges.size(); } public NCList(T entry) { + this(); List ranges = new ArrayList(); ranges.add(entry); build(ranges); } + public NCList() + { + subranges = new ArrayList>(); + } + /** * Traverses the sorted ranges to identify sublists, within which each * interval contains the one that follows it @@ -117,6 +127,7 @@ public class NCList */ public synchronized void add(T entry) { + size++; long start = entry.getBegin(); long end = entry.getEnd(); @@ -146,15 +157,16 @@ public class NCList * search for maximal span of subranges i-k that the new entry * encloses; or a subrange that encloses the new entry */ - int i = candidateIndex; boolean enclosing = false; + int firstEnclosed = 0; + int lastEnclosed = 0; boolean overlapping = false; for (int j = candidateIndex; j < subranges.size(); j++) { NCNode subrange = subranges.get(j); - if (end < subrange.getStart() && !overlapping) + if (end < subrange.getStart() && !overlapping && !enclosing) { /* * new entry lies between subranges j-1 j @@ -180,6 +192,11 @@ public class NCList * new entry encloses this subrange (and possibly preceding ones); * continue to find the maximal list it encloses */ + if (!enclosing) + { + firstEnclosed = j; + } + lastEnclosed = j; enclosing = true; continue; } @@ -193,7 +210,7 @@ public class NCList /* * entry encloses one or more preceding subranges */ - addEnclosingRange(entry, i, j - 1); + addEnclosingRange(entry, firstEnclosed, lastEnclosed); return; } else @@ -207,22 +224,41 @@ public class NCList } } } + else + { + overlapping = true; + } + } + + /* + * drops through to here if new range encloses all others + */ + if (enclosing) + { + addEnclosingRange(entry, firstEnclosed, lastEnclosed); } } /** * Update the tree so that the range of the new entry encloses subranges i to - * j (inclusive). That is, replace subranges i-j with a new subrange that - * contains them. + * j (inclusive). That is, replace subranges i-j (inclusive) with a new + * subrange that contains them. * * @param entry * @param i * @param j */ - protected synchronized void addEnclosingRange(T entry, int i, int j) + protected synchronized void addEnclosingRange(T entry, final int i, + final int j) { - // TODO how to rebuild the subranges as an NCList? - + NCList newNCList = new NCList(); + newNCList.subranges.addAll(subranges.subList(i, j + 1)); + NCNode newNode = new NCNode(entry, newNCList); + for (int k = j; k >= i; k--) + { + subranges.remove(k); + } + subranges.add(i, newNode); } /** @@ -321,4 +357,108 @@ public class NCList { return subranges.toString(); } + + /** + * Returns a string representation of the data where containment is shown bgy + * indentation on new lines + * + * @return + */ + public String prettyPrint() + { + StringBuilder sb = new StringBuilder(512); + int offset = 0; + int indent = 2; + prettyPrint(sb, offset, indent); + return sb.toString(); + } + + /** + * @param sb + * @param offset + * @param indent + */ + void prettyPrint(StringBuilder sb, int offset, int indent) + { + boolean first = true; + for (NCNode subrange : subranges) + { + if (!first) + { + sb.append(System.lineSeparator()); + } + first = false; + subrange.prettyPrint(sb, offset, indent); + } + } + + /** + * Answers true if the data held satisfy the rules of construction of an + * NCList, else false. + * + * @return + */ + public boolean isValid() + { + return isValid(Integer.MIN_VALUE, Integer.MAX_VALUE); + } + + /** + * Answers true if the data held satisfy the rules of construction of an + * NCList bounded within the given start-end range, else false. + *

+ * Each subrange must lie within start-end (inclusive). Subranges must be + * ordered by start position ascending. + *

+ * + * @param start + * @param end + * @return + */ + boolean isValid(final int start, final int end) + { + int lastStart = start; + for (NCNode subrange : subranges) + { + if (subrange.getStart() < lastStart) + { + System.err.println("error in NCList: range " + subrange.toString() + + " starts before " + lastStart); + return false; + } + if (subrange.getEnd() > end) + { + System.err.println("error in NCList: range " + subrange.toString() + + " ends after " + end); + return false; + } + lastStart = subrange.getStart(); + + if (!subrange.isValid()) + { + return false; + } + } + return true; + } + + /** + * Answers the lowest start position enclosed by the ranges + * + * @return + */ + public int getStart() + { + return subranges.isEmpty() ? 0 : subranges.get(0).getStart(); + } + + /** + * Returns the number of ranges held (deep count) + * + * @return + */ + public int getSize() + { + return size; + } } diff --git a/src/jalview/datamodel/features/NCNode.java b/src/jalview/datamodel/features/NCNode.java index d4c7b0c..ab10f67 100644 --- a/src/jalview/datamodel/features/NCNode.java +++ b/src/jalview/datamodel/features/NCNode.java @@ -21,7 +21,7 @@ class NCNode private NCList subregions; /** - * Constructor + * Constructor given a list of ranges * * @param ranges */ @@ -31,7 +31,7 @@ class NCNode } /** - * Constructo + * Constructor given a single range * * @param range */ @@ -42,6 +42,13 @@ class NCNode build(ranges); } + NCNode(V entry, NCList newNCList) + { + region = entry; + subregions = newNCList; + // size = 1 + newNCList.size(); + } + /** * @param ranges */ @@ -69,6 +76,13 @@ class NCNode return region.getEnd(); } + /** + * Formats the node as a bracketed list e.g. + * + * 

+   * [1-100 [10-30 [10-20]], 15-30 [20-20]]
+   *
+ */ @Override public String toString() { StringBuilder sb = new StringBuilder(10 * size); @@ -80,6 +94,17 @@ class NCNode return sb.toString(); } + void prettyPrint(StringBuilder sb, int offset, int indent) { + for (int i = 0 ; i < offset ; i++) { + sb.append(" "); + } + sb.append(region.getBegin()).append("-").append(region.getEnd()); + if (subregions != null) + { + sb.append(System.lineSeparator()); + subregions.prettyPrint(sb, offset + 2, indent); + } + } /** * Add any ranges that overlap the from-to range to the result list * @@ -104,7 +129,7 @@ class NCNode * * @param entry */ - public synchronized void add(V entry) + synchronized void add(V entry) { if (entry.getBegin() < region.getBegin() || entry.getEnd() > region.getEnd()) { throw new IllegalArgumentException(String.format( @@ -121,4 +146,19 @@ class NCNode subregions.add(entry); } } + + /** + * Answers true if the data held satisfy the rules of construction of an + * NCList, else false. + * + * @return + */ + boolean isValid() + { + if (subregions == null) + { + return true; + } + return subregions.isValid(getStart(), getEnd()); + } } diff --git a/test/jalview/datamodel/features/NCListTest.java b/test/jalview/datamodel/features/NCListTest.java index 38227c1..367e424 100644 --- a/test/jalview/datamodel/features/NCListTest.java +++ b/test/jalview/datamodel/features/NCListTest.java @@ -1,10 +1,12 @@ 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.List; +import java.util.Random; import org.testng.annotations.Test; @@ -58,10 +60,12 @@ public class NCListTest NCList ncl = new NCList(ranges); String expected = "[1-100 [10-30 [10-20 [10-20 [11-19]]]], 15-30 [20-20]]"; assertEquals(ncl.toString(), expected); + assertTrue(ncl.isValid()); Collections.reverse(ranges); ncl = new NCList(ranges); assertEquals(ncl.toString(), expected); + assertTrue(ncl.isValid()); } @Test(groups = "Functional") @@ -98,9 +102,11 @@ public class NCListTest ranges.add(new Range(20, 50)); NCList ncl = new NCList(ranges); assertEquals(ncl.toString(), "[20-50]"); + assertTrue(ncl.isValid()); ncl.add(new Range(60, 70)); assertEquals(ncl.toString(), "[20-50, 60-70]"); + assertTrue(ncl.isValid()); } @Test(groups = "Functional") @@ -110,6 +116,7 @@ public class NCListTest ranges.add(new Range(20, 50)); NCList ncl = new NCList(ranges); assertEquals(ncl.toString(), "[20-50]"); + assertTrue(ncl.isValid()); ncl.add(new Range(30, 40)); assertEquals(ncl.toString(), "[20-50 [30-40]]"); @@ -122,9 +129,11 @@ public class NCListTest ranges.add(new Range(20, 50)); NCList ncl = new NCList(ranges); assertEquals(ncl.toString(), "[20-50]"); + assertTrue(ncl.isValid()); ncl.add(new Range(5, 15)); assertEquals(ncl.toString(), "[5-15, 20-50]"); + assertTrue(ncl.isValid()); } @Test(groups = "Functional") @@ -135,9 +144,12 @@ public class NCListTest ranges.add(new Range(30, 60)); NCList ncl = new NCList(ranges); assertEquals(ncl.toString(), "[20-50, 30-60]"); + assertTrue(ncl.isValid()); + assertEquals(ncl.getStart(), 20); ncl.add(new Range(10, 70)); - assertEquals(ncl.toString(), "[10-70 [20-50, 30-60]"); + assertEquals(ncl.toString(), "[10-70 [20-50, 30-60]]"); + assertTrue(ncl.isValid()); } @Test(groups = "Functional") @@ -148,11 +160,46 @@ public class NCListTest ranges.add(new Range(60, 70)); NCList ncl = new NCList(ranges); assertEquals(ncl.toString(), "[20-40, 60-70]"); + assertTrue(ncl.isValid()); ncl.add(new Range(30, 50)); assertEquals(ncl.toString(), "[20-40, 30-50, 60-70]"); + assertTrue(ncl.isValid()); ncl.add(new Range(40, 65)); assertEquals(ncl.toString(), "[20-40, 30-50, 40-65, 60-70]"); + assertTrue(ncl.isValid()); + } + + /** + * 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. + */ + @Test(groups = "Functional") + public void testAdd_pseudoRandom() + { + Random r = new Random(108); // well why not? + int[] scales = new int[] { 10, 100, 1000 }; + + for (int scale : scales) + { + NCList ncl = new NCList(); + int size = 0; + for (int i = 0; i < 100; 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); + } + System.out.println(ncl.prettyPrint()); + } } } -- 1.7.10.2