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;
44 * A collection class to store interval-associated data, with O(log N)
45 * performance for overlap queries, insertion and deletion (where N is the size
46 * of the store). Accepts duplicate entries but not null values.
51 * any type providing <code>getBegin()</code> and <code>getEnd()</code>
53 public class IntervalStore<T extends IntervalI>
54 extends AbstractCollection<T> implements IntervalStoreI<T>
57 * An iterator over the intervals held in this store, with no particular
58 * ordering guaranteed. The iterator does not support the optional
59 * <code>remove</code> operation (throws
60 * <code>UnsupportedOperationException</code> if attempted).
66 private class IntervalIterator<V extends IntervalI> implements Iterator<V>
69 * iterator over top level non-nested intervals
71 Iterator<? extends IntervalI> topLevelIterator;
74 * iterator over NCList (if any)
76 Iterator<? extends IntervalI> nestedIterator;
79 * Constructor initialises iterators over the top level list and any nested
82 * @param intervalStore
84 public IntervalIterator(
85 IntervalStore<? extends IntervalI> intervalStore)
87 topLevelIterator = nonNested.iterator();
90 nestedIterator = nested.iterator();
95 public boolean hasNext()
97 return topLevelIterator.hasNext() ? true
98 : (nestedIterator != null && nestedIterator.hasNext());
104 if (topLevelIterator.hasNext())
106 return (V) topLevelIterator.next();
108 if (nestedIterator != null)
110 return (V) nestedIterator.next();
112 throw new NoSuchElementException();
117 private List<T> nonNested;
119 private NCList<T> nested;
124 public IntervalStore()
126 nonNested = new ArrayList<>();
130 * Constructor given a list of intervals. Note that the list may get sorted as
131 * a side-effect of calling this constructor.
133 public IntervalStore(List<T> intervals)
138 * partition into subranges whose root intervals
139 * have no mutual containment (if no intervals are nested,
140 * each subrange is of length 1 i.e. a single interval)
142 List<IntervalI> sublists = new NCListBuilder<T>()
143 .partitionNestedSublists(intervals);
146 * add all 'subrange root intervals' (and any co-located intervals)
147 * to our top level list of 'non-nested' intervals;
148 * put aside any left over for our NCList
150 List<T> nested = new ArrayList<>();
152 for (IntervalI subrange : sublists)
154 int listIndex = subrange.getBegin();
155 IntervalI root = intervals.get(listIndex);
156 while (listIndex <= subrange.getEnd())
158 T t = intervals.get(listIndex);
159 if (root.equalsInterval(t))
171 if (!nested.isEmpty())
173 this.nested = new NCList<>(nested);
178 * Adds one interval to the store.
183 public boolean add(T interval)
185 if (interval == null)
189 if (!addNonNestedInterval(interval))
192 * detected a nested interval - put it in the NCList structure
194 addNestedInterval(interval);
200 public boolean contains(Object entry)
202 if (listContains(nonNested, entry))
207 return nested == null ? false : nested.contains(entry);
210 protected boolean addNonNestedInterval(T entry)
212 synchronized (nonNested)
215 * find the first stored interval which doesn't precede the new one
217 int insertPosition = BinarySearcher.findFirst(nonNested,
218 val -> val.getBegin() >= entry.getBegin());
220 * fail if we detect interval enclosure
221 * - of the new interval by the one before or after it
222 * - of the next interval by the new one
224 if (insertPosition > 0)
226 if (nonNested.get(insertPosition - 1).properlyContainsInterval(entry))
231 if (insertPosition < nonNested.size())
233 T following = nonNested.get(insertPosition);
234 if (entry.properlyContainsInterval(following)
235 || following.properlyContainsInterval(entry))
242 * checks passed - add the interval
244 nonNested.add(insertPosition, entry);
251 public List<T> findOverlaps(long from, long to)
253 List<T> result = new ArrayList<>();
255 findNonNestedOverlaps(from, to, result);
259 result.addAll(nested.findOverlaps(from, to));
266 public String prettyPrint()
268 String pp = nonNested.toString();
271 pp += System.lineSeparator() + nested.prettyPrint();
277 public boolean isValid()
279 for (int i = 0; i < nonNested.size() - 1; i++)
281 IntervalI i1 = nonNested.get(i);
282 IntervalI i2 = nonNested.get(i + 1);
284 if (i2.getBegin() < i1.getBegin())
286 System.err.println("nonNested wrong start order : " + i1.toString()
287 + ", " + i2.toString());
290 if (i1.properlyContainsInterval(i2)
291 || i2.properlyContainsInterval(i1))
293 System.err.println("nonNested invalid containment!: "
295 + ", " + i2.toString());
299 return nested == null ? true : nested.isValid();
305 int i = nonNested.size();
314 public synchronized boolean remove(Object o)
322 @SuppressWarnings("unchecked")
326 * try the non-nested positional intervals first
328 boolean removed = removeNonNested(entry);
331 * if not found, try nested intervals
333 if (!removed && nested != null)
335 removed = nested.remove(entry);
339 } catch (ClassCastException e)
346 * Removes the given entry from the list of non-nested entries, returning true
347 * if found and removed, or false if not found. Specifically, removes the
348 * first item in the list for which <code>item.equals(entry)</code>.
353 protected boolean removeNonNested(T entry)
356 * find the first interval that might match, i.e. whose
357 * start position is not less than the target range start
358 * (NB inequality test ensures the first match if any is found)
360 int startIndex = BinarySearcher.findFirst(nonNested,
361 val -> val.getBegin() >= entry.getBegin());
364 * traverse intervals to look for a match
366 int from = entry.getBegin();
368 int size = nonNested.size();
371 T sf = nonNested.get(i);
372 if (sf.getBegin() > from)
376 if (sf.equals(entry))
387 public int getDepth()
393 return (nonNested.isEmpty() ? 0 : 1)
394 + (nested == null ? 0 : nested.getDepth());
398 * Adds one interval to the NCList that can manage nested intervals (creating
399 * the NCList if necessary)
401 protected synchronized void addNestedInterval(T interval)
405 nested = new NCList<>();
407 nested.add(interval);
411 * Answers true if the list contains the interval, else false. This method is
412 * optimised for the condition that the list is sorted on interval start
413 * position ascending, and will give unreliable results if this does not hold.
419 protected boolean listContains(List<T> intervals, Object entry)
421 if (intervals == null || entry == null || !(entry instanceof IntervalI))
426 IntervalI interval = (IntervalI) entry;
429 * locate the first entry in the list which does not precede the interval
431 int pos = BinarySearcher.findFirst(intervals,
432 val -> val.getBegin() >= interval.getBegin());
433 int len = intervals.size();
436 T sf = intervals.get(pos);
437 if (sf.getBegin() > interval.getBegin())
439 return false; // no match found
441 if (sf.equals(interval))
451 * Answers an iterator over the intervals in the store, with no particular
452 * ordering guaranteed. The iterator does not support the optional
453 * <code>remove</code> operation (throws
454 * <code>UnsupportedOperationException</code> if attempted).
457 public Iterator<T> iterator()
459 return new IntervalIterator<>(this);
465 this.nonNested.clear();
466 this.nested = new NCList<>();
470 * Adds non-nested intervals to the result list that lie within the target
477 protected void findNonNestedOverlaps(long from, long to,
481 * find the first interval whose end position is
482 * after the target range start
484 int startIndex = BinarySearcher.findFirst(nonNested,
485 val -> val.getEnd() >= from);
487 final int startIndex1 = startIndex;
489 while (i < nonNested.size())
491 T sf = nonNested.get(i);
492 if (sf.getBegin() > to)
496 if (sf.getBegin() <= to && sf.getEnd() >= from)
505 public String toString()
507 String s = nonNested.toString();
510 s = s + System.lineSeparator() + nested.toString();