X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=srcjar%2Fintervalstore%2Fimpl%2FIntervalStore.java;fp=srcjar%2Fintervalstore%2Fimpl%2FIntervalStore.java;h=0cd91f7d7270bbdb8f8ad6cb67918f9bcd79a7ac;hb=9577372b31a3c39a0690d3060503a76a2364a1d9;hp=0000000000000000000000000000000000000000;hpb=3f8a9801f25c5edc1a80ae9c8e8467b56954c202;p=jalview.git

diff --git a/srcjar/intervalstore/impl/IntervalStore.java b/srcjar/intervalstore/impl/IntervalStore.java
new file mode 100644
index 0000000..0cd91f7
--- /dev/null
+++ b/srcjar/intervalstore/impl/IntervalStore.java
@@ -0,0 +1,514 @@
+/*
+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.impl;
+
+import java.util.AbstractCollection;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+
+import intervalstore.api.IntervalI;
+import intervalstore.api.IntervalStoreI;
+
+/**
+ * A collection class to store interval-associated data, with O(log N)
+ * performance for overlap queries, insertion and deletion (where N is the size
+ * of the store). Accepts duplicate entries but not null values.
+ * 
+ * @author gmcarstairs
+ *
+ * @param <T>
+ *          any type providing <code>getBegin()</code> and <code>getEnd()</code>
+ */
+public class IntervalStore<T extends IntervalI>
+        extends AbstractCollection<T> implements IntervalStoreI<T>
+{
+  /**
+   * An iterator over the intervals held in this store, with no particular
+   * ordering guaranteed. The iterator does not support the optional
+   * <code>remove</code> operation (throws
+   * <code>UnsupportedOperationException</code> if attempted).
+   * 
+   * @author gmcarstairs
+   *
+   * @param <V>
+   */
+  private class IntervalIterator<V extends IntervalI> implements Iterator<V>
+  {
+    /*
+     * iterator over top level non-nested intervals
+     */
+    Iterator<? extends IntervalI> topLevelIterator;
+
+    /*
+     * iterator over NCList (if any)
+     */
+    Iterator<? extends IntervalI> nestedIterator;
+
+    /**
+     * Constructor initialises iterators over the top level list and any nested
+     * NCList
+     * 
+     * @param intervalStore
+     */
+    public IntervalIterator(
+            IntervalStore<? extends IntervalI> intervalStore)
+    {
+      topLevelIterator = nonNested.iterator();
+      if (nested != null)
+      {
+        nestedIterator = nested.iterator();
+      }
+    }
+
+    @Override
+    public boolean hasNext()
+    {
+      return topLevelIterator.hasNext() ? true
+              : (nestedIterator != null && nestedIterator.hasNext());
+    }
+
+    @Override
+    public V next()
+    {
+      if (topLevelIterator.hasNext())
+      {
+        return (V) topLevelIterator.next();
+      }
+      if (nestedIterator != null)
+      {
+        return (V) nestedIterator.next();
+      }
+      throw new NoSuchElementException();
+    }
+
+  }
+
+  private List<T> nonNested;
+
+  private NCList<T> nested;
+
+  /**
+   * Constructor
+   */
+  public IntervalStore()
+  {
+    nonNested = new ArrayList<>();
+  }
+
+  /**
+   * Constructor given a list of intervals. Note that the list may get sorted as
+   * a side-effect of calling this constructor.
+   */
+  public IntervalStore(List<T> intervals)
+  {
+    this();
+
+    /*
+     * partition into subranges whose root intervals
+     * have no mutual containment (if no intervals are nested,
+     * each subrange is of length 1 i.e. a single interval)
+     */
+    List<IntervalI> sublists = new NCListBuilder<T>()
+            .partitionNestedSublists(intervals);
+
+    /*
+     * add all 'subrange root intervals' (and any co-located intervals)
+     * to our top level list of 'non-nested' intervals; 
+     * put aside any left over for our NCList
+     */
+    List<T> nested = new ArrayList<>();
+
+    for (IntervalI subrange : sublists)
+    {
+      int listIndex = subrange.getBegin();
+      IntervalI root = intervals.get(listIndex);
+      while (listIndex <= subrange.getEnd())
+      {
+        T t = intervals.get(listIndex);
+        if (root.equalsInterval(t))
+        {
+          nonNested.add(t);
+        }
+        else
+        {
+          nested.add(t);
+        }
+        listIndex++;
+      }
+    }
+
+    if (!nested.isEmpty())
+    {
+      this.nested = new NCList<>(nested);
+    }
+  }
+
+  /**
+   * Adds one interval to the store.
+   * 
+   * @param interval
+   */
+  @Override
+  public boolean add(T interval)
+  {
+    if (interval == null)
+    {
+      return false;
+    }
+    if (!addNonNestedInterval(interval))
+    {
+      /*
+       * detected a nested interval - put it in the NCList structure
+       */
+      addNestedInterval(interval);
+    }
+    return true;
+  }
+
+  @Override
+  public boolean contains(Object entry)
+  {
+    if (listContains(nonNested, entry))
+    {
+      return true;
+    }
+
+    return nested == null ? false : nested.contains(entry);
+  }
+
+  protected boolean addNonNestedInterval(T entry)
+  {
+    synchronized (nonNested)
+    {
+      /*
+       * find the first stored interval which doesn't precede the new one
+       */
+      int insertPosition = BinarySearcher.findFirst(nonNested,
+              val -> val.getBegin() >= entry.getBegin());
+      /*
+       * fail if we detect interval enclosure 
+       * - of the new interval by the one before or after it
+       * - of the next interval by the new one
+       */
+      if (insertPosition > 0)
+      {
+        if (nonNested.get(insertPosition - 1).properlyContainsInterval(entry))
+        {
+          return false;
+        }
+      }
+      if (insertPosition < nonNested.size())
+      {
+        T following = nonNested.get(insertPosition);
+        if (entry.properlyContainsInterval(following)
+                || following.properlyContainsInterval(entry))
+        {
+          return false;
+        }
+      }
+
+      /*
+       * checks passed - add the interval
+       */
+      nonNested.add(insertPosition, entry);
+
+      return true;
+    }
+  }
+
+  @Override
+  public List<T> findOverlaps(long from, long to)
+  {
+    List<T> result = new ArrayList<>();
+
+    findNonNestedOverlaps(from, to, result);
+
+    if (nested != null)
+    {
+      result.addAll(nested.findOverlaps(from, to));
+    }
+
+    return result;
+  }
+
+  @Override
+  public String prettyPrint()
+  {
+    String pp = nonNested.toString();
+    if (nested != null)
+    {
+      pp += System.lineSeparator() + nested.prettyPrint();
+    }
+    return pp;
+  }
+
+  @Override
+  public boolean isValid()
+  {
+    for (int i = 0; i < nonNested.size() - 1; i++)
+    {
+      IntervalI i1 = nonNested.get(i);
+      IntervalI i2 = nonNested.get(i + 1);
+
+      if (i2.getBegin() < i1.getBegin())
+      {
+        System.err.println("nonNested wrong start order : " + i1.toString()
+                + ", " + i2.toString());
+        return false;
+      }
+      if (i1.properlyContainsInterval(i2)
+              || i2.properlyContainsInterval(i1))
+      {
+        System.err.println("nonNested invalid containment!: "
+                + i1.toString()
+                + ", " + i2.toString());
+        return false;
+      }
+    }
+    return nested == null ? true : nested.isValid();
+  }
+
+  @Override
+  public int size()
+  {
+    int i = nonNested.size();
+    if (nested != null)
+    {
+      i += nested.size();
+    }
+    return i;
+  }
+
+  @Override
+  public synchronized boolean remove(Object o)
+  {
+    if (o == null)
+    {
+      return false;
+    }
+    try
+    {
+      @SuppressWarnings("unchecked")
+      T entry = (T) o;
+
+      /*
+       * try the non-nested positional intervals first
+       */
+      boolean removed = removeNonNested(entry);
+
+      /*
+       * if not found, try nested intervals
+       */
+      if (!removed && nested != null)
+      {
+        removed = nested.remove(entry);
+      }
+
+      return removed;
+    } catch (ClassCastException e)
+    {
+      return false;
+    }
+  }
+
+  /**
+   * Removes the given entry from the list of non-nested entries, returning true
+   * if found and removed, or false if not found. Specifically, removes the
+   * first item in the list for which <code>item.equals(entry)</code>.
+   * 
+   * @param entry
+   * @return
+   */
+  protected boolean removeNonNested(T entry)
+  {
+    /*
+     * find the first interval that might match, i.e. whose 
+     * start position is not less than the target range start
+     * (NB inequality test ensures the first match if any is found)
+     */
+    int startIndex = BinarySearcher.findFirst(nonNested,
+            val -> val.getBegin() >= entry.getBegin());
+
+    /*
+     * traverse intervals to look for a match
+     */
+    int from = entry.getBegin();
+    int i = startIndex;
+    int size = nonNested.size();
+    while (i < size)
+    {
+      T sf = nonNested.get(i);
+      if (sf.getBegin() > from)
+      {
+        break;
+      }
+      if (sf.equals(entry))
+      {
+        nonNested.remove(i);
+        return true;
+      }
+      i++;
+    }
+    return false;
+  }
+
+  @Override
+  public int getDepth()
+  {
+    if (size() == 0)
+    {
+      return 0;
+    }
+    return (nonNested.isEmpty() ? 0 : 1)
+            + (nested == null ? 0 : nested.getDepth());
+  }
+
+  /**
+   * Adds one interval to the NCList that can manage nested intervals (creating
+   * the NCList if necessary)
+   */
+  protected synchronized void addNestedInterval(T interval)
+  {
+    if (nested == null)
+    {
+      nested = new NCList<>();
+    }
+    nested.add(interval);
+  }
+
+  /**
+   * Answers true if the list contains the interval, else false. This method is
+   * optimised for the condition that the list is sorted on interval start
+   * position ascending, and will give unreliable results if this does not hold.
+   * 
+   * @param intervals
+   * @param entry
+   * @return
+   */
+  protected boolean listContains(List<T> intervals, Object entry)
+  {
+    if (intervals == null || entry == null || !(entry instanceof IntervalI))
+    {
+      return false;
+    }
+
+    IntervalI interval = (IntervalI) entry;
+
+    /*
+     * locate the first entry in the list which does not precede the interval
+     */
+    int pos = BinarySearcher.findFirst(intervals,
+            val -> val.getBegin() >= interval.getBegin());
+    int len = intervals.size();
+    while (pos < len)
+    {
+      T sf = intervals.get(pos);
+      if (sf.getBegin() > interval.getBegin())
+      {
+        return false; // no match found
+      }
+      if (sf.equals(interval))
+      {
+        return true;
+      }
+      pos++;
+    }
+    return false;
+  }
+
+  /**
+   * Answers an iterator over the intervals in the store, with no particular
+   * ordering guaranteed. The iterator does not support the optional
+   * <code>remove</code> operation (throws
+   * <code>UnsupportedOperationException</code> if attempted).
+   */
+  @Override
+  public Iterator<T> iterator()
+  {
+    return new IntervalIterator<>(this);
+  }
+
+  @Override
+  public void clear()
+  {
+    this.nonNested.clear();
+    this.nested = new NCList<>();
+  }
+
+  /**
+   * Adds non-nested intervals to the result list that lie within the target
+   * range
+   * 
+   * @param from
+   * @param to
+   * @param result
+   */
+  protected void findNonNestedOverlaps(long from, long to,
+          List<T> result)
+  {
+    /*
+     * find the first interval whose end position is
+     * after the target range start
+     */
+    int startIndex = BinarySearcher.findFirst(nonNested,
+            val -> val.getEnd() >= from);
+
+    final int startIndex1 = startIndex;
+    int i = startIndex1;
+    while (i < nonNested.size())
+    {
+      T sf = nonNested.get(i);
+      if (sf.getBegin() > to)
+      {
+        break;
+      }
+      if (sf.getBegin() <= to && sf.getEnd() >= from)
+      {
+        result.add(sf);
+      }
+      i++;
+    }
+  }
+
+  @Override
+  public String toString()
+  {
+    String s = nonNested.toString();
+    if (nested != null)
+    {
+      s = s + System.lineSeparator() + nested.toString();
+    }
+    return s;
+  }
+}