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.nonc;
34 import java.util.AbstractCollection;
35 import java.util.ArrayList;
36 import java.util.Collections;
37 import java.util.Comparator;
38 import java.util.Iterator;
39 import java.util.List;
41 import intervalstore.api.IntervalI;
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>
55 implements intervalstore.api.IntervalStoreI<T>
57 private List<T> intervals;
59 private boolean isTainted;
61 private IntervalI[] orderedIntervalStarts;
66 public IntervalStore()
68 intervals = new ArrayList<>();
71 class IntervalComparator implements Comparator<T>
75 public int compare(IntervalI o1, IntervalI o2)
78 int order = Integer.compare(o1.getBegin(), o2.getBegin());
82 * if tied on start position, longer length sorts to left
83 * i.e. the negation of normal ordering by length
85 order = Integer.compare(o2.getEnd(), o1.getEnd());
94 * Constructor given a list of intervals. Note that the list may get sorted as
95 * a side-effect of calling this constructor.
97 public IntervalStore(List<T> intervals)
99 Collections.sort(this.intervals = intervals,
100 new IntervalComparator());
102 findOverlaps(0, -1); // ensure this is ordered
106 * Adds one interval to the store.
111 public boolean add(T interval)
113 if (interval == null)
118 synchronized (intervals)
120 int insertPosition = findFirstBegin(intervals, interval.getBegin());
121 intervals.add(insertPosition, interval);
131 orderedIntervalStarts = null;
136 public boolean contains(Object entry)
138 return listContains(intervals, entry);
141 protected int findFirstBegin(List<T> list, long pos)
144 int end = list.size() - 1;
145 int matched = list.size();
149 int mid = (start + end) / 2;
150 if (list.get(mid).getBegin() >= pos)
163 protected int findFirstEnd(List<T> list, long pos)
166 int end = list.size() - 1;
167 int matched = list.size();
171 int mid = (start + end) / 2;
172 if (list.get(mid).getEnd() >= pos)
186 * Adds non-nested intervals to the result list that lie within the target
193 protected void findIntervalOverlaps(long from, long to,
197 int startIndex = findFirstEnd(intervals, from);
198 final int startIndex1 = startIndex;
200 while (i < intervals.size())
202 T sf = intervals.get(i);
203 if (sf.getBegin() > to)
207 if (sf.getBegin() <= to && sf.getEnd() >= from)
216 public List<T> findOverlaps(long start, long end)
219 List<T> result = new ArrayList<>();
221 int n = intervals.size();
227 justCheckOne(intervals.get(0), start, end, result);
233 orderedIntervalStarts = intervals.toArray(new IntervalI[0]);
234 linkFeatures(orderedIntervalStarts);
242 // just ensuring not tainted -- fully loaded
246 // (1) Find the closest feature to this position.
248 int index = getClosestFeature(orderedIntervalStarts, start);
249 IntervalI sf = (index < 0 ? null : orderedIntervalStarts[index]);
251 // (2) Traverse the containedBy field, checking for overlap.
255 if (sf.getEnd() >= start)
259 sf = sf.getContainedBy();
262 // (3) For an interval, find the last feature that starts in this interval,
263 // and add all features up through that feature.
267 // fill in with all features that start within this interval, fully
269 int index2 = getClosestFeature(orderedIntervalStarts, end);
270 while (++index <= index2)
272 result.add((T) orderedIntervalStarts[index]);
279 private int getClosestFeature(IntervalI[] l, long pos)
282 int high = l.length - 1;
285 int mid = (low + high) >>> 1;
286 IntervalI f = l[mid];
287 switch (Long.signum(f.getBegin() - pos))
297 while (++mid <= high && l[mid].getBegin() == pos)
304 return (high < 0 ? -1 : high);
307 @SuppressWarnings("unchecked")
308 public T getContainedBy(T sf, T sf0)
310 int begin = sf0.getBegin();
313 if (begin <= sf.getEnd())
315 // System.out.println("\nIS found " + sf0.getIndex1() + ":" + sf0
316 // + "\nFS in " + sf.getIndex1() + ":" + sf);
319 sf = (T) sf.getContainedBy();
325 public int getDepth()
332 for (int i = intervals.size(); --i >= 0;)
334 T element = intervals.get(i);
335 T container = element;
337 while ((container = (T) container.getContainedBy()) != null)
339 if (++depth > maxDepth && container == this)
350 public boolean isValid()
352 for (int i = 0; i < intervals.size() - 1; i++)
354 T i1 = intervals.get(i);
355 T i2 = intervals.get(i + 1);
357 if (i2.getBegin() < i1.getBegin())
359 System.err.println("nonNested wrong start order : " + i1.toString()
360 + ", " + i2.toString());
368 * Answers an iterator over the intervals in the store, with no particular
369 * ordering guaranteed. The iterator does not support the optional
370 * <code>remove</code> operation (throws
371 * <code>UnsupportedOperationException</code> if attempted).
374 public Iterator<T> iterator()
376 return intervals.iterator();
380 private void justCheckOne(T sf, long start, long end, List<T> result)
382 if (sf.getBegin() <= end && sf.getEnd() >= start)
389 private void linkFeatures(IntervalI[] features)
391 int n = features.length;
397 features[0].setIndex1(1);
400 int maxEnd = features[0].getEnd();
401 for (int i = 1; i < n;)
403 T sf = (T) features[i];
405 if (sf.getBegin() <= maxEnd)
407 sf.setContainedBy(getContainedBy((T) features[i - 2], sf));
409 if (sf.getEnd() > maxEnd)
411 maxEnd = sf.getEnd();
418 * Answers true if the list contains the interval, else false. This method is
419 * optimised for the condition that the list is sorted on interval start
420 * position ascending, and will give unreliable results if this does not hold.
426 protected boolean listContains(List<T> intervals, Object entry)
428 if (intervals == null || entry == null)
433 T interval = (T) entry;
436 * locate the first entry in the list which does not precede the interval
438 int pos = findFirstBegin(intervals, interval.getBegin());
439 int len = intervals.size();
442 T sf = intervals.get(pos);
443 if (sf.getBegin() > interval.getBegin())
445 return false; // no match found
447 if (sf.getEnd() == interval.getEnd() && sf.equals(interval))
457 public String prettyPrint()
463 public synchronized boolean remove(Object o)
465 if (o == null || !(o instanceof IntervalI))
473 * try the non-nested positional intervals first
475 boolean removed = removeInterval(entry);
486 * Removes the given entry from the list of non-nested entries, returning true
487 * if found and removed, or false if not found. Specifically, removes the
488 * first item in the list for which <code>item.equals(entry)</code>.
493 protected boolean removeInterval(T entry)
496 * find the first interval that might match, i.e. whose
497 * start position is not less than the target range start
498 * (NB inequality test ensures the first match if any is found)
500 int startIndex = findFirstBegin(intervals, entry.getBegin());
503 * traverse intervals to look for a match
505 int from = entry.getBegin();
507 int size = intervals.size();
510 T sf = intervals.get(i);
511 if (sf.getBegin() > from)
515 if (sf.equals(entry))
528 return intervals.size();
532 public String toString()
535 StringBuffer sb = new StringBuffer();
537 return sb.toString();