From 4bb1a8a4b8fc08ed5b0d51f0ea03d9a9ad7dc419 Mon Sep 17 00:00:00 2001 From: gmungoc Date: Fri, 12 May 2017 15:56:33 +0100 Subject: [PATCH] JAL-2480 more efficient contains check on add; tidied comparators --- src/jalview/datamodel/features/FeatureStore.java | 69 ++++++++++++++++---- src/jalview/datamodel/features/NCList.java | 11 +--- .../datamodel/features/RangeComparator.java | 31 +++++---- .../datamodel/features/FeatureStoreTest.java | 24 +++++++ .../datamodel/features/RangeComparatorTest.java | 30 ++------- 5 files changed, 106 insertions(+), 59 deletions(-) diff --git a/src/jalview/datamodel/features/FeatureStore.java b/src/jalview/datamodel/features/FeatureStore.java index 75e99c7..432f62d 100644 --- a/src/jalview/datamodel/features/FeatureStore.java +++ b/src/jalview/datamodel/features/FeatureStore.java @@ -72,10 +72,6 @@ public class FeatureStore } } - Comparator startOrdering = new RangeComparator(true); - - Comparator endOrdering = new RangeComparator(false); - /* * Non-positional features have no (zero) start/end position. * Kept as a separate list in case this criterion changes in future. @@ -182,7 +178,7 @@ public class FeatureStore } else { - if (!nonNestedFeatures.contains(feature)) + if (!contains(nonNestedFeatures, feature)) { added = addNonNestedFeature(feature); if (!added) @@ -308,7 +304,7 @@ public class FeatureStore * find the first stored feature which doesn't precede the new one */ int insertPosition = binarySearch(nonNestedFeatures, - SearchCriterion.byFeature(feature, startOrdering)); + SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION)); /* * fail if we detect feature enclosure - of the new feature by @@ -382,21 +378,70 @@ public class FeatureStore contactFeatureEnds = new ArrayList(); } - // TODO binary search for insertion points! - if (contactFeatureStarts.contains(feature)) + if (contains(contactFeatureStarts, feature)) { return false; } - contactFeatureStarts.add(feature); - Collections.sort(contactFeatureStarts, startOrdering); + /* + * binary search the sorted list to find the insertion point + */ + int insertPosition = binarySearch(contactFeatureStarts, + SearchCriterion.byFeature(feature, + RangeComparator.BY_START_POSITION)); + contactFeatureStarts.add(insertPosition, feature); + // and resort to mak siccar...just in case insertion point not quite right + Collections.sort(contactFeatureStarts, RangeComparator.BY_START_POSITION); + + insertPosition = binarySearch(contactFeatureStarts, + SearchCriterion.byFeature(feature, + RangeComparator.BY_END_POSITION)); contactFeatureEnds.add(feature); - Collections.sort(contactFeatureEnds, endOrdering); + Collections.sort(contactFeatureEnds, RangeComparator.BY_END_POSITION); return true; } /** + * Answers true if the list contains the feature, else false. This method is + * optimised for the condition that the list is sorted on feature start + * position ascending, and will give unreliable results if this does not hold. + * + * @param features + * @param feature + * @return + */ + protected static boolean contains(List features, + SequenceFeature feature) + { + if (features == null || feature == null) + { + return false; + } + + /* + * locate the first entry in the list which does not precede the feature + */ + int pos = binarySearch(features, + SearchCriterion.byFeature(feature, RangeComparator.BY_START_POSITION)); + int len = features.size(); + while (pos < len) + { + SequenceFeature sf = features.get(pos); + if (sf.getBegin() > feature.getBegin()) + { + return false; // no match found + } + if (sf.equals(feature)) + { + return true; + } + pos++; + } + return false; + } + + /** * Returns a (possibly empty) list of features whose extent overlaps the given * range. The returned list is not ordered. Contact features are included if * either of the contact points lies within the range. @@ -842,7 +887,7 @@ public class FeatureStore * @param sc * @return */ - protected int binarySearch(List features, + protected static int binarySearch(List features, SearchCriterion sc) { int start = 0; diff --git a/src/jalview/datamodel/features/NCList.java b/src/jalview/datamodel/features/NCList.java index 0af9d50..a911666 100644 --- a/src/jalview/datamodel/features/NCList.java +++ b/src/jalview/datamodel/features/NCList.java @@ -2,7 +2,6 @@ package jalview.datamodel.features; import java.util.ArrayList; import java.util.Collections; -import java.util.Comparator; import java.util.List; /** @@ -28,12 +27,6 @@ public class NCList */ private List> subranges; - /* - * a comparator to sort intervals by start position ascending, with - * longer (enclosing) intervals preceding those they enclose - */ - Comparator intervalSorter = new RangeComparator(true); - /** * Constructor given a list of things that are each located on a contiguous * interval. Note that the constructor may reorder the list. @@ -61,7 +54,7 @@ public class NCList * sort by start ascending so that contained intervals * follow their containing interval */ - Collections.sort(ranges, intervalSorter); + Collections.sort(ranges, RangeComparator.BY_START_POSITION); List sublists = buildSubranges(ranges); @@ -610,7 +603,7 @@ public class NCList if (subRegions != null) { subranges.addAll(subRegions.subranges); - Collections.sort(subranges, intervalSorter); + Collections.sort(subranges, RangeComparator.BY_START_POSITION); } size--; return true; diff --git a/src/jalview/datamodel/features/RangeComparator.java b/src/jalview/datamodel/features/RangeComparator.java index 57e9b5f..05d3f0a 100644 --- a/src/jalview/datamodel/features/RangeComparator.java +++ b/src/jalview/datamodel/features/RangeComparator.java @@ -4,15 +4,33 @@ import java.util.Comparator; /** * A comparator that orders ranges by either start position or end position - * ascending. If the position matches, + * ascending. If the position matches, ordering is resolved by end position (or + * start position). * * @author gmcarstairs * */ public class RangeComparator implements Comparator { + public static final Comparator BY_START_POSITION = new RangeComparator( + true); + + public static final Comparator BY_END_POSITION = new RangeComparator( + false); + boolean byStart; + /** + * Constructor + * + * @param byStartPosition + * if true, order based on start position, if false by end position + */ + RangeComparator(boolean byStartPosition) + { + byStart = byStartPosition; + } + @Override public int compare(ContiguousI o1, ContiguousI o2) { @@ -55,15 +73,4 @@ public class RangeComparator implements Comparator } return order; } - - /** - * Constructor - * - * @param byStartPosition - * if true, order based on start position, if false by end position - */ - public RangeComparator(boolean byStartPosition) - { - byStart = byStartPosition; - } } diff --git a/test/jalview/datamodel/features/FeatureStoreTest.java b/test/jalview/datamodel/features/FeatureStoreTest.java index 5d3b13f..d2893e5 100644 --- a/test/jalview/datamodel/features/FeatureStoreTest.java +++ b/test/jalview/datamodel/features/FeatureStoreTest.java @@ -6,6 +6,7 @@ import static org.testng.Assert.assertTrue; import jalview.datamodel.SequenceFeature; +import java.util.ArrayList; import java.util.List; import java.util.Set; @@ -687,4 +688,27 @@ public class FeatureStoreTest assertEquals(fs.getMinimumScore(false), Float.NaN); assertEquals(fs.getMaximumScore(false), Float.NaN); } + + @Test(groups = "Functional") + public void testContains() + { + assertFalse(FeatureStore.contains(null, null)); + List features = new ArrayList(); + assertFalse(FeatureStore.contains(features, null)); + + SequenceFeature sf1 = new SequenceFeature("type1", "desc1", 20, 30, 3f, + "group1"); + assertFalse(FeatureStore.contains(null, sf1)); + assertFalse(FeatureStore.contains(features, sf1)); + + features.add(sf1); + SequenceFeature sf2 = new SequenceFeature("type1", "desc1", 20, 30, 3f, + "group1"); + SequenceFeature sf3 = new SequenceFeature("type1", "desc1", 20, 40, 3f, + "group1"); + + // sf2.equals(sf1) so contains should return true + assertTrue(FeatureStore.contains(features, sf2)); + assertFalse(FeatureStore.contains(features, sf3)); + } } diff --git a/test/jalview/datamodel/features/RangeComparatorTest.java b/test/jalview/datamodel/features/RangeComparatorTest.java index 6f22add..e58ce6a 100644 --- a/test/jalview/datamodel/features/RangeComparatorTest.java +++ b/test/jalview/datamodel/features/RangeComparatorTest.java @@ -2,34 +2,12 @@ package jalview.datamodel.features; import static org.testng.Assert.assertEquals; +import java.util.Comparator; + import org.testng.annotations.Test; public class RangeComparatorTest { - class Range implements ContiguousI - { - int begin; - - int end; - - @Override - public int getBegin() - { - return begin; - } - - @Override - public int getEnd() - { - return end; - } - - Range(int i, int j) - { - begin = i; - end = j; - } - } @Test(groups = "Functional") public void testCompare() @@ -51,7 +29,7 @@ public class RangeComparatorTest @Test(groups = "Functional") public void testCompare_byStart() { - RangeComparator comp = new RangeComparator(true); + Comparator comp = RangeComparator.BY_START_POSITION; // same start position, same length assertEquals(comp.compare(new Range(10, 20), new Range(10, 20)), 0); @@ -68,7 +46,7 @@ public class RangeComparatorTest @Test(groups = "Functional") public void testCompare_byEnd() { - RangeComparator comp = new RangeComparator(false); + Comparator comp = RangeComparator.BY_END_POSITION; // same end position, same length assertEquals(comp.compare(new Range(10, 20), new Range(10, 20)), 0); -- 1.7.10.2