From f8258d012b4afd77e0dd6fd3743714fbabb59c8f Mon Sep 17 00:00:00 2001 From: hansonr Date: Sun, 22 Sep 2019 11:43:44 -0400 Subject: [PATCH] JAL-3253-applet JAL-3397 - adds IntervalStore0Test - adds nonc.IntervalStoreImpl - adds nonc.IntervalStore0Impl - sets FeatureStore options to these Impl classes in order to override sameInterval for SequenceFeature and allow drop in of nonc.IntervalStore without editing. --- src/intervalstore/nonc/IntervalStore.java | 2 +- src/intervalstore/nonc/IntervalStore0Impl.java | 80 +++ src/intervalstore/nonc/IntervalStoreImpl.java | 76 +++ src/jalview/datamodel/features/FeatureStore.java | 4 +- test/intervalstore/nonc/IntervalStore0Test.java | 725 ++++++++++++++++++++++ test/intervalstore/nonc/IntervalStoreTest.java | 24 +- 6 files changed, 896 insertions(+), 15 deletions(-) create mode 100644 src/intervalstore/nonc/IntervalStore0Impl.java create mode 100644 src/intervalstore/nonc/IntervalStoreImpl.java create mode 100644 test/intervalstore/nonc/IntervalStore0Test.java diff --git a/src/intervalstore/nonc/IntervalStore.java b/src/intervalstore/nonc/IntervalStore.java index 405a471..effbb55 100644 --- a/src/intervalstore/nonc/IntervalStore.java +++ b/src/intervalstore/nonc/IntervalStore.java @@ -1367,7 +1367,7 @@ public class IntervalStore * @param i2 * @return */ - boolean sameInterval(IntervalI i1, IntervalI i2) + protected boolean sameInterval(IntervalI i1, IntervalI i2) { // avoiding equals() for JavaScript performance return ((SequenceFeature) i1).equals((SequenceFeature) i2, false); diff --git a/src/intervalstore/nonc/IntervalStore0Impl.java b/src/intervalstore/nonc/IntervalStore0Impl.java new file mode 100644 index 0000000..8921dd6 --- /dev/null +++ b/src/intervalstore/nonc/IntervalStore0Impl.java @@ -0,0 +1,80 @@ +/* +BSD 3-Clause License + +Copyright (c) 2018, Mungo Carstairs +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + +* Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + +* Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + +* Neither the name of the copyright holder nor the names of its + contributors may be used to endorse or promote products derived from + this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE +FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ +package intervalstore.nonc; + +import jalview.datamodel.SequenceFeature; + +import intervalstore.api.IntervalI; + +/** + * extend intervalstore.nonc.IntervalStore to account for the fact that + * SequenceFeature.equalsInterval only checks ranges + */ +@SuppressWarnings("rawtypes") +public class IntervalStore0Impl extends IntervalStore0 +{ + + + /** + * Constructor + */ + public IntervalStore0Impl() + { + super(); + } + + /** + * CAUTION! This presumes that equalsInterval does check descriptions. Note + * that bartongroup.IntervalStoreJ does NOT do this and + * jalview.datamodel.features.SequenceFeature does not, either. But + * nonc.SimpleFeature in test DOES, because it overrides equalsInterval. + * + * The reason we do it this way is to avoid an unnecessary and costly test for + * obj instanceof IntervalI. + * + * Added by Mungo to use equals, but that requires use of instance checking, + * which is not significant in Java (apparently), but is a bigger deal in + * JavaScript. So here we have to hack + * bobhanson.IntervalStoreJ.nonc.InervalStore to bypass equals. + * + * @param i1 + * @param i2 + * @return + */ + @Override + boolean sameInterval(IntervalI i1, IntervalI i2) + { + // avoiding equals() for JavaScript performance + return ((SequenceFeature) i1).equals((SequenceFeature) i2, false); + } + +} diff --git a/src/intervalstore/nonc/IntervalStoreImpl.java b/src/intervalstore/nonc/IntervalStoreImpl.java new file mode 100644 index 0000000..337b774 --- /dev/null +++ b/src/intervalstore/nonc/IntervalStoreImpl.java @@ -0,0 +1,76 @@ +/* +BSD 3-Clause License + +Copyright (c) 2018, Mungo Carstairs +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + +* Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + +* Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + +* Neither the name of the copyright holder nor the names of its + contributors may be used to endorse or promote products derived from + this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE +FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ +package intervalstore.nonc; + +import jalview.datamodel.SequenceFeature; + +import intervalstore.api.IntervalI; + +/** + * extend intervalstore.nonc.IntervalStore to account for the fact that + * SequenceFeature.equalsInterval only checks ranges + */ +@SuppressWarnings("rawtypes") +public class IntervalStoreImpl extends IntervalStore +{ + + public IntervalStoreImpl() + { + super(); + } + + /** + * CAUTION! This presumes that equalsInterval does check descriptions. Note + * that bartongroup.IntervalStoreJ does NOT do this and + * jalview.datamodel.features.SequenceFeature does not, either. But + * nonc.SimpleFeature in test DOES, because it overrides equalsInterval. + * + * The reason we do it this way is to avoid an unnecessary and costly test for + * obj instanceof IntervalI. + * + * Added by Mungo to use equals, but that requires use of instance checking, + * which is not significant in Java (apparently), but is a bigger deal in + * JavaScript. So here we have to hack + * bobhanson.IntervalStoreJ.nonc.InervalStore to bypass equals. + * + * @param i1 + * @param i2 + * @return + */ + @Override + protected boolean sameInterval(IntervalI i1, IntervalI i2) + { + // avoiding equals() for JavaScript performance + return ((SequenceFeature) i1).equals((SequenceFeature) i2, false); + } + +} diff --git a/src/jalview/datamodel/features/FeatureStore.java b/src/jalview/datamodel/features/FeatureStore.java index b7cd330..615b340 100644 --- a/src/jalview/datamodel/features/FeatureStore.java +++ b/src/jalview/datamodel/features/FeatureStore.java @@ -257,9 +257,9 @@ public class FeatureStore case INTERVAL_STORE_NCLIST_OBJECT: return new intervalstore.impl.IntervalStore<>(); case INTERVAL_STORE_NCARRAY: - return new intervalstore.nonc.IntervalStore<>(); + return new intervalstore.nonc.IntervalStoreImpl(); case INTERVAL_STORE_LINKED_LIST: - return new intervalstore.nonc.IntervalStore0<>(); + return new intervalstore.nonc.IntervalStore0Impl(); } } diff --git a/test/intervalstore/nonc/IntervalStore0Test.java b/test/intervalstore/nonc/IntervalStore0Test.java new file mode 100644 index 0000000..c3dfb17 --- /dev/null +++ b/test/intervalstore/nonc/IntervalStore0Test.java @@ -0,0 +1,725 @@ +/* +BSD 3-Clause License + +Copyright (c) 2018, Mungo Carstairs +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + +* Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + +* Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + +* Neither the name of the copyright holder nor the names of its + contributors may be used to endorse or promote products derived from + this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE +FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ +package intervalstore.nonc; + +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 java.util.ArrayList; +import java.util.List; +import java.util.Random; + +import org.testng.annotations.Test; + +import intervalstore.api.IntervalStoreI; + +public class IntervalStore0Test +{ + + public static void main(String[] args) + { + new IntervalStore0Test().defaultTests(); + } + + private void defaultTests() + { + testAddAndQueryTiming(); + } + + @Test(groups = "Functional") + public void testFindOverlaps_nonNested() + { + IntervalStore0 store = new IntervalStore0Impl(); + SimpleFeature sf1 = add(store, 10, 20); + // same range different description + SimpleFeature sf2 = new SimpleFeature(10, 20, "desc"); + store.add(sf2); + SimpleFeature sf3 = add(store, 15, 25); + SimpleFeature sf4 = add(store, 20, 35); + + assertEquals(store.size(), 4); + List overlaps = store.findOverlaps(1, 9); + assertTrue(overlaps.isEmpty()); + + overlaps = store.findOverlaps(8, 10); + assertEquals(overlaps.size(), 2); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + + overlaps = store.findOverlaps(12, 16); + assertEquals(overlaps.size(), 3); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + assertTrue(overlaps.contains(sf3)); + + overlaps = store.findOverlaps(33, 33); + assertEquals(overlaps.size(), 1); + assertTrue(overlaps.contains(sf4)); + + /* + * ensure edge cases are covered + */ + overlaps = store.findOverlaps(35, 40); + assertEquals(overlaps.size(), 1); + assertTrue(overlaps.contains(sf4)); + assertTrue(store.findOverlaps(36, 100).isEmpty()); + assertTrue(store.findOverlaps(1, 9).isEmpty()); + } + + @Test(groups = "Functional") + public void testFindOverlaps_nested() + { + IntervalStore0 store = new IntervalStore0Impl(); + SimpleFeature sf1 = add(store, 10, 50); + SimpleFeature sf2 = add(store, 10, 40); + SimpleFeature sf3 = add(store, 20, 30); + // feature at same location but different description + SimpleFeature sf4 = new SimpleFeature(20, 30, "different desc"); + store.add(sf4); + SimpleFeature sf5 = add(store, 35, 36); + + List overlaps = store.findOverlaps(1, 9); + assertTrue(overlaps.isEmpty()); + + overlaps = store.findOverlaps(10, 15); + assertEquals(overlaps.size(), 2); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + + overlaps = store.findOverlaps(45, 60); + assertEquals(overlaps.size(), 1); + assertTrue(overlaps.contains(sf1)); + + overlaps = store.findOverlaps(32, 38); + assertEquals(overlaps.size(), 3); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + assertTrue(overlaps.contains(sf5)); + + overlaps = store.findOverlaps(15, 25); + assertEquals(overlaps.size(), 4); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + assertTrue(overlaps.contains(sf3)); + assertTrue(overlaps.contains(sf4)); + } + + @Test(groups = "Functional") + public void testFindOverlaps_mixed() + { + IntervalStore0 store = new IntervalStore0Impl(); + SimpleFeature sf1 = add(store, 10, 50); + SimpleFeature sf2 = add(store, 1, 15); + SimpleFeature sf3 = add(store, 20, 30); + SimpleFeature sf4 = add(store, 40, 100); + SimpleFeature sf5 = add(store, 60, 100); + SimpleFeature sf6 = add(store, 70, 70); + + List overlaps = store.findOverlaps(200, 200); + assertTrue(overlaps.isEmpty()); + + overlaps = store.findOverlaps(1, 9); + assertEquals(overlaps.size(), 1); + assertTrue(overlaps.contains(sf2)); + + overlaps = store.findOverlaps(5, 18); + assertEquals(overlaps.size(), 2); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + + overlaps = store.findOverlaps(30, 40); + assertEquals(overlaps.size(), 3); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf3)); + assertTrue(overlaps.contains(sf4)); + + overlaps = store.findOverlaps(80, 90); + assertEquals(overlaps.size(), 2); + assertTrue(overlaps.contains(sf4)); + assertTrue(overlaps.contains(sf5)); + + overlaps = store.findOverlaps(68, 70); + assertEquals(overlaps.size(), 3); + assertTrue(overlaps.contains(sf4)); + assertTrue(overlaps.contains(sf5)); + assertTrue(overlaps.contains(sf6)); + } + + /** + * Helper method to add a feature with type "desc" + * + * @param store + * @param from + * @param to + * @return + */ + SimpleFeature add(IntervalStore0 store, int from, + int to) + { + SimpleFeature sf1 = new SimpleFeature(from, to, "desc"); + store.add(sf1); + return sf1; + } + + @Test(groups = "Functional") + public void testRemove() + { + IntervalStore0 store = new IntervalStore0Impl(); + SimpleFeature sf1 = add(store, 10, 20); + assertTrue(store.contains(sf1)); + + try + { + store.remove("what is this?"); + } catch (ClassCastException e) + { + // expected; + } + assertFalse(store.remove(null)); + + /* + * simple deletion + */ + assertTrue(store.remove(sf1)); + assertTrue(store.isEmpty()); + + SimpleFeature sf2 = add(store, 0, 0); + SimpleFeature sf2a = add(store, 30, 40); + assertTrue(store.contains(sf2)); + assertFalse(store.remove(sf1)); + assertTrue(store.remove(sf2)); + assertTrue(store.remove(sf2a)); + assertTrue(store.isEmpty()); + + /* + * nested feature deletion + */ + SimpleFeature sf4 = add(store, 20, 30); + SimpleFeature sf5 = add(store, 22, 26); // to NCList + SimpleFeature sf6 = add(store, 23, 24); // child of sf5 + SimpleFeature sf7 = add(store, 25, 25); // sibling of sf6 + SimpleFeature sf8 = add(store, 24, 24); // child of sf6 + SimpleFeature sf9 = add(store, 23, 23); // child of sf6 + assertEquals(store.size(), 6); + + // delete a node with children - they take its place + assertTrue(store.remove(sf6)); // sf8, sf9 should become children of sf5 + assertEquals(store.size(), 5); + assertFalse(store.contains(sf6)); + + // delete a node with no children + assertTrue(store.remove(sf7)); + assertEquals(store.size(), 4); + assertFalse(store.contains(sf7)); + + // delete root of NCList + assertTrue(store.remove(sf5)); + assertEquals(store.size(), 3); + assertFalse(store.contains(sf5)); + + // continue the killing fields + assertTrue(store.remove(sf4)); + assertEquals(store.size(), 2); + assertFalse(store.contains(sf4)); + + assertTrue(store.remove(sf9)); + assertEquals(store.size(), 1); + assertFalse(store.contains(sf9)); + + assertTrue(store.remove(sf8)); + assertTrue(store.isEmpty()); + } + + /** + * A helper method to test whether a list contains a specific object (by + * object identity, not equality test as used by List.contains()) + * + * @param list + * @param o + * @return + */ + private static boolean containsObject(List list, + Object o) + { + for (Object i : list) + { + if (i == o) + { + return true; + } + } + return false; + } + + @Test(groups = "Functional") + public void testAdd() + { + IntervalStore0 store = new IntervalStore0Impl(); + + assertFalse(store.add(null)); + + SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath"); + SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath"); + + assertTrue(store.add(sf1)); + assertEquals(store.size(), 1); + + /* + * contains should return true for the same or an identical feature + */ + assertTrue(store.contains(sf1)); + assertTrue(store.contains(sf2)); + + /* + * duplicates are accepted + */ + assertTrue(store.add(sf2)); + assertEquals(store.size(), 2); + + SimpleFeature sf3 = new SimpleFeature(0, 0, "Cath"); + assertTrue(store.add(sf3)); + assertEquals(store.size(), 3); + } + + @Test(groups = "Functional") + public void testAdd_noDuplicates() + { + IntervalStore0 store = new IntervalStore0Impl(); + + SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath"); + SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath"); + assertTrue(sf1.equals(sf2)); + assertTrue(store.add(sf1)); + assertEquals(store.size(), 1); + assertFalse(store.add(sf2, false)); + assertEquals(store.size(), 1); + assertTrue(store.contains(sf1)); + assertTrue(store.contains(sf2)); // because sf1.equals(sf2) ! + } + + @Test(groups = "Functional") + public void testIsEmpty() + { + IntervalStore0 store = new IntervalStore0Impl(); + assertTrue(store.isEmpty()); + assertEquals(store.size(), 0); + + /* + * non-nested feature + */ + SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath"); + store.add(sf1); + assertFalse(store.isEmpty()); + assertEquals(store.size(), 1); + store.remove(sf1); + assertTrue(store.isEmpty()); + assertEquals(store.size(), 0); + + sf1 = new SimpleFeature(0, 0, "Cath"); + store.add(sf1); + assertFalse(store.isEmpty()); + assertEquals(store.size(), 1); + store.remove(sf1); + assertTrue(store.isEmpty()); + assertEquals(store.size(), 0); + + /* + * sf2, sf3 added as nested features + */ + sf1 = new SimpleFeature(19, 49, "Cath"); + SimpleFeature sf2 = new SimpleFeature(20, 40, "Cath"); + SimpleFeature sf3 = new SimpleFeature(25, 35, "Cath"); + store.add(sf1); + assertEquals(store.size(), 1); + store.add(sf2); + assertEquals(store.size(), 2); + store.add(sf3); + assertEquals(store.size(), 3); + assertTrue(store.remove(sf1)); + assertEquals(store.size(), 2); + + assertFalse(store.isEmpty()); + assertTrue(store.remove(sf2)); + assertEquals(store.size(), 1); + assertFalse(store.isEmpty()); + assertTrue(store.remove(sf3)); + assertEquals(store.size(), 0); + assertTrue(store.isEmpty()); // all gone + } + + @Test(groups = "Functional") + public void testRemove_readd() + { + /* + * add a feature and a nested feature + */ + IntervalStore0 store = new IntervalStore0Impl(); + SimpleFeature sf1 = add(store, 10, 20); + // sf2 is nested in sf1 so will be stored in nestedFeatures + SimpleFeature sf2 = add(store, 12, 14); + assertEquals(store.size(), 2); + assertTrue(store.contains(sf1)); + assertTrue(store.contains(sf2)); + + /* + * delete the first feature + */ + assertTrue(store.remove(sf1)); + assertFalse(store.contains(sf1)); + assertTrue(store.contains(sf2)); + + /* + * re-add the 'nested' feature; it is now duplicated + */ + store.add(sf2); + assertEquals(store.size(), 2); + assertTrue(store.contains(sf2)); + } + + @Test(groups = "Functional") + public void testContains() + { + IntervalStore0 store = new IntervalStore0Impl(); + SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath"); + SimpleFeature sf2 = new SimpleFeature(10, 20, "Pfam"); + + store.add(sf1); + assertTrue(store.contains(sf1)); + assertTrue(store.contains(new SimpleFeature(sf1))); // identical feature + assertFalse(store.contains(sf2)); // different description + + /* + * add a nested feature + */ + SimpleFeature sf3 = new SimpleFeature(12, 16, "Cath"); + store.add(sf3); + assertTrue(store.contains(sf3)); + assertTrue(store.contains(new SimpleFeature(sf3))); + + /* + * delete the outer (enclosing, non-nested) feature + */ + store.remove(sf1); + assertFalse(store.contains(sf1)); + assertTrue(store.contains(sf3)); + + assertFalse(store.contains(null)); + try + { + assertFalse(store.contains("junk")); + } catch (ClassCastException e) + { + // expected; + } + } + + @Test(groups = "Functional") + public void testFindOverlaps_resultsArg_mixed() + { + IntervalStore0 store = new IntervalStore0Impl(); + SimpleFeature sf1 = add(store, 10, 50); + SimpleFeature sf2 = add(store, 1, 15); + SimpleFeature sf3 = add(store, 20, 30); + SimpleFeature sf4 = add(store, 40, 100); + SimpleFeature sf5 = add(store, 60, 100); + SimpleFeature sf6 = add(store, 70, 70); + + List overlaps = new ArrayList<>(); + List overlaps2 = store.findOverlaps(200, 200, overlaps); + assertSame(overlaps, overlaps2); + assertTrue(overlaps.isEmpty()); + + overlaps.clear(); + store.findOverlaps(1, 9, overlaps); + assertEquals(overlaps.size(), 1); + assertTrue(overlaps.contains(sf2)); + + overlaps.clear(); + store.findOverlaps(5, 18, overlaps); + assertEquals(overlaps.size(), 2); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + + overlaps.clear(); + store.findOverlaps(30, 40, overlaps); + assertEquals(overlaps.size(), 3); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf3)); + assertTrue(overlaps.contains(sf4)); + + overlaps.clear(); + store.findOverlaps(80, 90, overlaps); + assertEquals(overlaps.size(), 2); + assertTrue(overlaps.contains(sf4)); + assertTrue(overlaps.contains(sf5)); + + overlaps.clear(); + store.findOverlaps(68, 70, overlaps); + assertEquals(overlaps.size(), 3); + assertTrue(overlaps.contains(sf4)); + assertTrue(overlaps.contains(sf5)); + assertTrue(overlaps.contains(sf6)); + + /* + * and without clearing the list first + * note that sf4 is included twice, as an + * overlap of 68-70 and also of 30-40 + */ + store.findOverlaps(30, 40, overlaps); + assertEquals(overlaps.size(), 6); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf3)); + assertTrue(overlaps.contains(sf4)); + assertTrue(overlaps.contains(sf5)); + assertTrue(overlaps.contains(sf6)); + assertSame(sf4, overlaps.get(2)); // not (0) + assertSame(sf4, overlaps.get(3)); // not (4) + } + + @Test(groups = "Functional") + public void testFindOverlaps_resultsArg_nested() + { + IntervalStore0 store = new IntervalStore0Impl(); + SimpleFeature sf1 = add(store, 10, 50); + SimpleFeature sf2 = add(store, 10, 40); + SimpleFeature sf3 = add(store, 20, 30); + // feature at same location but different description + SimpleFeature sf4 = new SimpleFeature(20, 30, "different desc"); + store.add(sf4); + SimpleFeature sf5 = add(store, 35, 36); + + List overlaps = new ArrayList<>(); + store.findOverlaps(1, 9, overlaps); + assertTrue(overlaps.isEmpty()); + + store.findOverlaps(10, 15, overlaps); + assertEquals(overlaps.size(), 2); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + + overlaps.clear(); + store.findOverlaps(45, 60, overlaps); + assertEquals(overlaps.size(), 1); + assertTrue(overlaps.contains(sf1)); + + overlaps.clear(); + store.findOverlaps(32, 38, overlaps); + assertEquals(overlaps.size(), 3); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + assertTrue(overlaps.contains(sf5)); + + overlaps.clear(); + store.findOverlaps(15, 25, overlaps); + assertEquals(overlaps.size(), 4); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + assertTrue(overlaps.contains(sf3)); + assertTrue(overlaps.contains(sf4)); + } + + @Test(groups = "Functional") + public void testFindOverlaps_resultsArg_nonNested() + { + IntervalStore0 store = new IntervalStore0Impl(); + SimpleFeature sf1 = add(store, 10, 20); + // same range different description + SimpleFeature sf2 = new SimpleFeature(10, 20, "desc"); + store.add(sf2); + SimpleFeature sf3 = add(store, 15, 25); + SimpleFeature sf4 = add(store, 20, 35); + + assertEquals(store.size(), 4); + List overlaps = new ArrayList<>(); + store.findOverlaps(1, 9, overlaps); + assertTrue(overlaps.isEmpty()); + + store.findOverlaps(8, 10, overlaps); + assertEquals(overlaps.size(), 2); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + + overlaps.clear(); + store.findOverlaps(12, 16, overlaps); + assertEquals(overlaps.size(), 3); + assertTrue(overlaps.contains(sf1)); + assertTrue(overlaps.contains(sf2)); + assertTrue(overlaps.contains(sf3)); + + overlaps.clear(); + store.findOverlaps(33, 33, overlaps); + assertEquals(overlaps.size(), 1); + assertTrue(overlaps.contains(sf4)); + + /* + * ensure edge cases are covered + */ + overlaps.clear(); + store.findOverlaps(35, 40, overlaps); + assertEquals(overlaps.size(), 1); + assertTrue(overlaps.contains(sf4)); + + overlaps.clear(); + assertTrue(store.findOverlaps(36, 100, overlaps).isEmpty()); + assertTrue(store.findOverlaps(1, 9, overlaps).isEmpty()); + } + + /** + * Compares alternative IntervalStoreI implementations for time to add an + * interval then query, at a range of different scales of N (the number of + * stored features). + */ + @Test(groups = "Timing", enabled = false) + public void testAddAndQueryTiming() + { + testAddAndQuery(1, 20000000, 10, 20); + testAddAndQuery(0, 0, 10, 20); + + testAddAndQuery(1, 20000000, 10, 200); + testAddAndQuery(0, 0, 10, 200); + + testAddAndQuery(1, 20000000, 10, 2000); + testAddAndQuery(0, 0, 10, 2000); + + testAddAndQuery(1, 20000000, -2000000, 2000000); + testAddAndQuery(0, 0, -2000000, 2000000); + } + + private void testAddAndQuery(int addstart, int addend, int start, int end) + { + System.out.println("\nadd: " + addstart + " " + addend + " query: " + + start + " " + end); + StringBuffer sb = new StringBuffer(); + IntervalStoreI store; + store = new intervalstore.nonc.IntervalStore0Impl(); + testAddAndQueryTiming(store, false, sb, addstart, addend, start, end); + + store = new intervalstore.impl.IntervalStore<>(); + testAddAndQueryTiming(store, true, sb, addstart, addend, start, end); + + System.out.println(sb); + } + + /** + * Populates the store with intervals, then logs the time taken to add an + * interval then query, at a range of different scales of N (the number of + * stored features). + * + * @param store + */ + private void testAddAndQueryTiming(IntervalStoreI store, + boolean isNCList, StringBuffer sb, int addstart, int addend, + int start, int end) + { + final int seqlen = 100000; // e.g. length of gene sequence + final int repeats = 20; + final int K = 1000; + final int warmups = 5; + final int[] scales = new int[] { 10 * K, 100 * K, 1000 * K };// , 10000 * K + // }; + + Random r = new Random(732); // fixed seed = repeatable test + int counter = 0; // to ensure a distinct description for each feature + + // System.out.println("Scale\titeration\tmicrosecs"); + + for (int scale : scales) + { + /* + * add 'scale' features to the store + */ + long ntimeLoad = System.nanoTime(); + for (int i = 0; i < scale; i++) + { + SimpleFeature sf; + sf = makeFeature(seqlen, r, counter); + counter++; + store.add(sf); + } + if (!isNCList) + { + ((intervalstore.nonc.IntervalStore0) store).revalidate(); + } + String line = "time to load " + (isNCList ? "NClist " : "NCArray ") + + (System.nanoTime() - ntimeLoad) / K / K + " ms scale " + + scale; + // System.out.println(line); + sb.append(line); + + /* + * do "add then query" and log the time taken for the query + * we ignore the first 5 repetitions as 'warmups' + */ + long total = 0L; + for (int i = 0; i < repeats + warmups; i++) + { + SimpleFeature sf; + if (addstart == 0) + { + sf = makeFeature(seqlen, r, counter++); + } + else + { + sf = new SimpleFeature(addstart, addend, "desc" + counter++); + } + System.gc(); + long t1 = System.nanoTime(); + store.add(sf); + store.findOverlaps(start, end); + long elapsed = System.nanoTime() - t1; + if (i >= warmups) + { + total += elapsed; + // System.out.println( + // String.format("%d\t%d\t%d", scale, i - warmups, + // elapsed / K)); + } + } + sb.append( + " add+query " + + (isNCList ? "NCList " : "NCArray ") + + (total / (K * repeats)) + " microseconds\n"); + } + } + + SimpleFeature makeFeature(final int seqlen, Random r, int counter) + { + int i1 = r.nextInt(seqlen); + int i2 = r.nextInt(seqlen); + int from = Math.min(i1, i2); + int to = Math.max(i1, i2); + SimpleFeature sf = new SimpleFeature(from, to, "desc" + counter); + return sf; + } +} \ No newline at end of file diff --git a/test/intervalstore/nonc/IntervalStoreTest.java b/test/intervalstore/nonc/IntervalStoreTest.java index e21976a..581f5f4 100644 --- a/test/intervalstore/nonc/IntervalStoreTest.java +++ b/test/intervalstore/nonc/IntervalStoreTest.java @@ -60,7 +60,7 @@ public class IntervalStoreTest @Test(groups = "Functional") public void testFindOverlaps_nonNested() { - IntervalStore store = new IntervalStore<>(); + IntervalStore store = new IntervalStoreImpl(); SimpleFeature sf1 = add(store, 10, 20); // same range different description SimpleFeature sf2 = new SimpleFeature(10, 20, "desc"); @@ -100,7 +100,7 @@ public class IntervalStoreTest @Test(groups = "Functional") public void testFindOverlaps_nested() { - IntervalStore store = new IntervalStore<>(); + IntervalStore store = new IntervalStoreImpl(); SimpleFeature sf1 = add(store, 10, 50); SimpleFeature sf2 = add(store, 10, 40); SimpleFeature sf3 = add(store, 20, 30); @@ -138,7 +138,7 @@ public class IntervalStoreTest @Test(groups = "Functional") public void testFindOverlaps_mixed() { - IntervalStore store = new IntervalStore<>(); + IntervalStore store = new IntervalStoreImpl(); SimpleFeature sf1 = add(store, 10, 50); SimpleFeature sf2 = add(store, 1, 15); SimpleFeature sf3 = add(store, 20, 30); @@ -195,7 +195,7 @@ public class IntervalStoreTest @Test(groups = "Functional") public void testRemove() { - IntervalStore store = new IntervalStore<>(); + IntervalStore store = new IntervalStoreImpl(); SimpleFeature sf1 = add(store, 10, 20); assertTrue(store.contains(sf1)); @@ -285,7 +285,7 @@ public class IntervalStoreTest @Test(groups = "Functional") public void testAdd() { - IntervalStore store = new IntervalStore<>(); + IntervalStore store = new IntervalStoreImpl(); assertFalse(store.add(null)); @@ -315,7 +315,7 @@ public class IntervalStoreTest @Test(groups = "Functional") public void testAdd_noDuplicates() { - IntervalStore store = new IntervalStore<>(); + IntervalStore store = new IntervalStoreImpl(); SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath"); SimpleFeature sf2 = new SimpleFeature(10, 20, "Cath"); @@ -331,7 +331,7 @@ public class IntervalStoreTest @Test(groups = "Functional") public void testIsEmpty() { - IntervalStore store = new IntervalStore<>(); + IntervalStore store = new IntervalStoreImpl(); assertTrue(store.isEmpty()); assertEquals(store.size(), 0); @@ -384,7 +384,7 @@ public class IntervalStoreTest /* * add a feature and a nested feature */ - IntervalStore store = new IntervalStore<>(); + IntervalStore store = new IntervalStoreImpl(); SimpleFeature sf1 = add(store, 10, 20); // sf2 is nested in sf1 so will be stored in nestedFeatures SimpleFeature sf2 = add(store, 12, 14); @@ -410,7 +410,7 @@ public class IntervalStoreTest @Test(groups = "Functional") public void testContains() { - IntervalStore store = new IntervalStore<>(); + IntervalStore store = new IntervalStoreImpl(); SimpleFeature sf1 = new SimpleFeature(10, 20, "Cath"); SimpleFeature sf2 = new SimpleFeature(10, 20, "Pfam"); @@ -447,7 +447,7 @@ public class IntervalStoreTest @Test(groups = "Functional") public void testFindOverlaps_resultsArg_mixed() { - IntervalStore store = new IntervalStore<>(); + IntervalStore store = new IntervalStoreImpl(); SimpleFeature sf1 = add(store, 10, 50); SimpleFeature sf2 = add(store, 1, 15); SimpleFeature sf3 = add(store, 20, 30); @@ -510,7 +510,7 @@ public class IntervalStoreTest @Test(groups = "Functional") public void testFindOverlaps_resultsArg_nested() { - IntervalStore store = new IntervalStore<>(); + IntervalStore store = new IntervalStoreImpl(); SimpleFeature sf1 = add(store, 10, 50); SimpleFeature sf2 = add(store, 10, 40); SimpleFeature sf3 = add(store, 20, 30); @@ -552,7 +552,7 @@ public class IntervalStoreTest @Test(groups = "Functional") public void testFindOverlaps_resultsArg_nonNested() { - IntervalStore store = new IntervalStore<>(); + IntervalStore store = new IntervalStoreImpl(); SimpleFeature sf1 = add(store, 10, 20); // same range different description SimpleFeature sf2 = new SimpleFeature(10, 20, "desc"); -- 1.7.10.2