4 Copyright (c) 2018, Mungo Carstairs
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are met:
10 * Redistributions of source code must retain the above copyright notice, this
11 list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above copyright notice,
14 this list of conditions and the following disclaimer in the documentation
15 and/or other materials provided with the distribution.
17 * Neither the name of the copyright holder nor the names of its
18 contributors may be used to endorse or promote products derived from
19 this software without specific prior written permission.
21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
24 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
25 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
27 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
29 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 package intervalstore.impl;
34 import java.util.AbstractCollection;
35 import java.util.ArrayList;
36 import java.util.Iterator;
37 import java.util.List;
38 import java.util.NoSuchElementException;
40 import intervalstore.api.IntervalI;
41 import intervalstore.api.IntervalStoreI;
42 import intervalstore.impl.BinarySearcher.Compare;
45 * A collection class to store interval-associated data, with O(log N)
46 * performance for overlap queries, insertion and deletion (where N is the size
47 * of the store). Accepts duplicate entries but not null values.
52 * any type providing <code>getBegin()</code> and <code>getEnd()</code>
54 public class IntervalStore<T extends IntervalI>
55 extends AbstractCollection<T> implements IntervalStoreI<T>
58 * An iterator over the intervals held in this store, with no particular
59 * ordering guaranteed. The iterator does not support the optional
60 * <code>remove</code> operation (throws
61 * <code>UnsupportedOperationException</code> if attempted).
67 private class IntervalIterator<V extends IntervalI> implements Iterator<V>
70 * iterator over top level non-nested intervals
72 Iterator<? extends IntervalI> topLevelIterator;
75 * iterator over NCList (if any)
77 Iterator<? extends IntervalI> nestedIterator;
80 * Constructor initialises iterators over the top level list and any nested
83 * @param intervalStore
85 public IntervalIterator(
86 IntervalStore<? extends IntervalI> intervalStore)
88 topLevelIterator = nonNested.iterator();
91 nestedIterator = nested.iterator();
96 public boolean hasNext()
98 return topLevelIterator.hasNext() ? true
99 : (nestedIterator != null && nestedIterator.hasNext());
105 if (topLevelIterator.hasNext())
107 return (V) topLevelIterator.next();
109 if (nestedIterator != null)
111 return (V) nestedIterator.next();
113 throw new NoSuchElementException();
118 private List<T> nonNested;
120 private NCList<T> nested;
125 public IntervalStore()
127 nonNested = new ArrayList<>();
131 * Constructor given a list of intervals. Note that the list may get sorted as
132 * a side-effect of calling this constructor.
134 public IntervalStore(List<T> intervals)
139 * partition into subranges whose root intervals
140 * have no mutual containment (if no intervals are nested,
141 * each subrange is of length 1 i.e. a single interval)
143 List<IntervalI> sublists = new NCListBuilder<T>()
144 .partitionNestedSublists(intervals);
147 * add all 'subrange root intervals' (and any co-located intervals)
148 * to our top level list of 'non-nested' intervals;
149 * put aside any left over for our NCList
151 List<T> nested = new ArrayList<>();
153 for (IntervalI subrange : sublists)
155 int listIndex = subrange.getBegin();
156 IntervalI root = intervals.get(listIndex);
157 while (listIndex <= subrange.getEnd())
159 T t = intervals.get(listIndex);
160 if (root.equalsInterval(t))
172 if (!nested.isEmpty())
174 this.nested = new NCList<>(nested);
179 * Adds one interval to the store. Answers true unless the feature is a
180 * duplicate (already contained), in which case it is not added.
185 public boolean add(T interval)
187 return add(interval, true);
191 public boolean add(T interval, boolean allowDuplicates)
193 if (interval == null)
197 if (!allowDuplicates && contains(interval))
202 if (!addNonNestedInterval(interval))
205 * detected a nested interval - put it in the NCList structure
207 addNestedInterval(interval);
213 public boolean contains(Object entry)
215 if (listContains(nonNested, entry))
220 return nested == null ? false : nested.contains(entry);
223 protected boolean addNonNestedInterval(T entry)
225 synchronized (nonNested)
228 * find the first stored interval which doesn't precede the new one
230 int insertPosition = BinarySearcher.findFirst(nonNested, true,
231 Compare.GE, entry.getBegin());
233 * fail if we detect interval enclosure
234 * - of the new interval by the one before or after it
235 * - of the next interval by the new one
237 if (insertPosition > 0)
239 if (nonNested.get(insertPosition - 1).properlyContainsInterval(entry))
244 if (insertPosition < nonNested.size())
246 T following = nonNested.get(insertPosition);
247 if (entry.properlyContainsInterval(following)
248 || following.properlyContainsInterval(entry))
255 * checks passed - add the interval
257 nonNested.add(insertPosition, entry);
264 public List<T> findOverlaps(long from, long to)
266 return findOverlaps(from, to, new ArrayList<>());
270 public List<T> findOverlaps(long from, long to, List<T> result)
274 result = new ArrayList<>();
277 findNonNestedOverlaps(from, to, result);
281 nested.findOverlaps(from, to, result);
288 public String prettyPrint()
290 String pp = nonNested.toString();
293 pp += System.lineSeparator() + nested.prettyPrint();
299 * Inspects the data store and answers true if it is validly constructed, else
300 * false. Provided for use in verification by test classes. *
304 public boolean isValid()
306 for (int i = 0; i < nonNested.size() - 1; i++)
308 IntervalI i1 = nonNested.get(i);
309 IntervalI i2 = nonNested.get(i + 1);
311 if (i2.getBegin() < i1.getBegin())
313 System.err.println("nonNested wrong start order : " + i1.toString()
314 + ", " + i2.toString());
317 if (i1.properlyContainsInterval(i2)
318 || i2.properlyContainsInterval(i1))
320 System.err.println("nonNested invalid containment!: "
322 + ", " + i2.toString());
326 return nested == null ? true : nested.isValid();
332 int i = nonNested.size();
341 public synchronized boolean remove(Object o)
349 @SuppressWarnings("unchecked")
353 * try the non-nested positional intervals first
355 boolean removed = removeNonNested(entry);
358 * if not found, try nested intervals
360 if (!removed && nested != null)
362 removed = nested.remove(entry);
366 } catch (ClassCastException e)
373 * Removes the given entry from the list of non-nested entries, returning true
374 * if found and removed, or false if not found. Specifically, removes the
375 * first item in the list for which <code>item.equals(entry)</code>.
380 protected boolean removeNonNested(T entry)
383 * find the first interval that might match, i.e. whose
384 * start position is not less than the target range start
385 * (NB inequality test ensures the first match if any is found)
387 int startIndex = BinarySearcher.findFirst(nonNested, true, Compare.GE,
391 * traverse intervals to look for a match
393 int from = entry.getBegin();
395 int size = nonNested.size();
398 T sf = nonNested.get(i);
399 if (sf.getBegin() > from)
403 if (sf.equals(entry))
414 * Answers 0 if the store is empty, 1 if there are only top level intervals,
415 * else 1 plus the depth of the nested intervals (NCList)
418 public int getDepth()
424 return (nonNested.isEmpty() ? 0 : 1)
425 + (nested == null ? 0 : nested.getDepth());
429 * Adds one interval to the NCList that can manage nested intervals (creating
430 * the NCList if necessary)
432 protected synchronized void addNestedInterval(T interval)
436 nested = new NCList<>();
438 nested.add(interval);
442 * Answers true if the list contains the interval, else false. This method is
443 * optimised for the condition that the list is sorted on interval start
444 * position ascending, and will give unreliable results if this does not hold.
450 protected boolean listContains(List<T> intervals, Object entry)
452 if (intervals == null || entry == null || !(entry instanceof IntervalI))
457 IntervalI interval = (IntervalI) entry;
460 * locate the first entry in the list which does not precede the interval
462 int pos = BinarySearcher.findFirst(intervals, true, Compare.GE,
463 interval.getBegin());
464 int len = intervals.size();
467 T sf = intervals.get(pos);
468 if (sf.getBegin() > interval.getBegin())
470 return false; // no match found
472 if (sf.equals(interval))
482 * Answers an iterator over the intervals in the store, with no particular
483 * ordering guaranteed. The iterator does not support the optional
484 * <code>remove</code> operation (throws
485 * <code>UnsupportedOperationException</code> if attempted).
488 public Iterator<T> iterator()
490 return new IntervalIterator<>(this);
496 this.nonNested.clear();
497 this.nested = new NCList<>();
501 * Adds non-nested intervals to the result list that lie within the target
508 protected void findNonNestedOverlaps(long from, long to,
512 * find the first interval whose end position is
513 * after the target range start
515 int startIndex = BinarySearcher.findFirst(nonNested, false, Compare.GE,
518 final int startIndex1 = startIndex;
520 while (i < nonNested.size())
522 T sf = nonNested.get(i);
523 if (sf.getBegin() > to)
527 if (sf.getBegin() <= to && sf.getEnd() >= from)
536 public String toString()
538 String s = nonNested.toString();
541 s = s + System.lineSeparator() + nested.toString();