+/*
+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 org.testng.annotations.Test;
+
+public class IntervalStoreTest
+{
+ @Test(groups = "Functional")
+ public void testFindOverlaps_nonNested()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ 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<SimpleFeature> 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()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ 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<SimpleFeature> 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()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ 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<SimpleFeature> 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(IntervalStore<SimpleFeature> store, int from,
+ int to)
+ {
+ SimpleFeature sf1 = new SimpleFeature(from, to, "desc");
+ store.add(sf1);
+ return sf1;
+ }
+
+ @Test(groups = "Functional")
+ public void testRemove()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ 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<? extends Object> list,
+ Object o)
+ {
+ for (Object i : list)
+ {
+ if (i == o)
+ {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ @Test(groups = "Functional")
+ public void testAdd()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+
+ 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()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+
+ 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()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ 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
+ */
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ 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()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ 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()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ 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<SimpleFeature> overlaps = new ArrayList<>();
+ List<SimpleFeature> 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(0));
+ assertSame(sf4, overlaps.get(4));
+ }
+
+ @Test(groups = "Functional")
+ public void testFindOverlaps_resultsArg_nested()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ 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<SimpleFeature> 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()
+ {
+ IntervalStore<SimpleFeature> store = new IntervalStore<>();
+ 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<SimpleFeature> 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());
+ }
+}