+++ /dev/null
-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
-{
-
- private Random random = new Random(107);
-
- private Comparator<ContiguousI> sorter = new RangeComparator(true);
-
- /**
- * A basic sanity test of the constructor
- */
- @Test(groups = "Functional")
- public void testConstructor()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(20, 20));
- ranges.add(new Range(10, 20));
- ranges.add(new Range(15, 30));
- ranges.add(new Range(10, 30));
- ranges.add(new Range(11, 19));
- ranges.add(new Range(10, 20));
- ranges.add(new Range(1, 100));
-
- NCList<Range> ncl = new NCList<Range>(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<Range>(ranges);
- assertEquals(ncl.toString(), expected);
- assertTrue(ncl.isValid());
- }
-
- @Test(groups = "Functional")
- public void testFindOverlaps()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(20, 50));
- ranges.add(new Range(30, 70));
- ranges.add(new Range(1, 100));
- ranges.add(new Range(70, 120));
-
- NCList<Range> ncl = new NCList<Range>(ranges);
-
- List<Range> overlaps = ncl.findOverlaps(121, 122);
- assertEquals(overlaps.size(), 0);
-
- overlaps = ncl.findOverlaps(21, 22);
- assertEquals(overlaps.size(), 2);
- assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 1);
- assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 100);
- assertEquals(((ContiguousI) overlaps.get(1)).getBegin(), 20);
- assertEquals(((ContiguousI) overlaps.get(1)).getEnd(), 50);
-
- overlaps = ncl.findOverlaps(110, 110);
- assertEquals(overlaps.size(), 1);
- assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 70);
- assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 120);
- }
-
- @Test(groups = "Functional")
- public void testAdd_onTheEnd()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(20, 50));
- NCList<Range> ncl = new NCList<Range>(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")
- public void testAdd_inside()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(20, 50));
- NCList<Range> ncl = new NCList<Range>(ranges);
- assertEquals(ncl.toString(), "[20-50]");
- assertTrue(ncl.isValid());
-
- ncl.add(new Range(30, 40));
- assertEquals(ncl.toString(), "[20-50 [30-40]]");
- }
-
- @Test(groups = "Functional")
- public void testAdd_onTheFront()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(20, 50));
- NCList<Range> ncl = new NCList<Range>(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")
- public void testAdd_enclosing()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(20, 50));
- ranges.add(new Range(30, 60));
- NCList<Range> ncl = new NCList<Range>(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]]");
- assertTrue(ncl.isValid());
- }
-
- @Test(groups = "Functional")
- public void testAdd_spanning()
- {
- List<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(20, 40));
- ranges.add(new Range(60, 70));
- NCList<Range> ncl = new NCList<Range>(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());
- }
-
- /**
- * 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, to
- * exercise as many methods of the class as possible while generating the
- * range of possible structure topologies
- * <ul>
- * <li>verify that add adds an entry and increments size</li>
- * <li>...except where the entry is already contained (by equals test)</li>
- * <li>verify that the structure is valid at all stages of construction</li>
- * <li>generate, run and verify a range of overlap queries</li>
- * <li>tear down the structure by deleting entries, verifying correctness at
- * each stage</li>
- * </ul>
- */
- @Test(groups = "Functional", dataProvider = "scalesOfLife")
- public void test_pseudoRandom(Integer scale)
- {
- NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
- List<SequenceFeature> features = new ArrayList<SequenceFeature>(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<SequenceFeature> ncl,
- List<SequenceFeature> features)
- {
- int deleted = 0;
-
- while (!features.isEmpty())
- {
- 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++)
- {
- 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()));
- }
- }
- 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<SequenceFeature> ncl,
- List<SequenceFeature> 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<SequenceFeature> ncl,
- int scale,
- List<SequenceFeature> 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<SequenceFeature> ncl, int from,
- int to, List<SequenceFeature> features)
- {
- List<SequenceFeature> 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<Range> ranges = new ArrayList<Range>();
- 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<Range> ncl = new NCList<Range>(ranges);
- Range r7 = new Range(1, 100);
- ncl.add(r7);
-
- List<Range> 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<Range>();
- assertTrue(ncl.getEntries().isEmpty());
- }
-
- @Test(groups = "Functional")
- public void testDelete()
- {
- List<Range> ranges = new ArrayList<Range>();
- Range r1 = new Range(20, 30);
- ranges.add(r1);
- NCList<Range> ncl = new NCList<Range>(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<SequenceFeature> features = new NCList<SequenceFeature>();
- 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<Range> ranges = new ArrayList<Range>();
- ranges.add(new Range(40, 50));
- ranges.add(new Range(20, 30));
- NCList<Range> ncl = new NCList<Range>(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<SequenceFeature> ncl = new NCList<SequenceFeature>();
- 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<Range> ranges = new ArrayList<Range>();
- Range r1 = new Range(40, 50);
- ranges.add(r1);
- NCList<Range> ncl = new NCList<Range>(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<Range> ranges = new ArrayList<Range>();
- 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<Range> ncl = new NCList<Range>(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<Range>(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<Range> ranges = new ArrayList<Range>();
- 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<Range> ncl = new NCList<Range>(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<Range>(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());
- }
-}
git://source.jalview.org / jalview.git / blobdiff