> subranges;
/**
* Constructor given a list of things that are each located on a contiguous
* interval. Note that the constructor may reorder the list.
*
* We assume here that for each range, start <= end. Behaviour for reverse
* ordered ranges is undefined.
*
* @param ranges
*/
public NCList(List ranges)
{
this();
build(ranges);
}
/**
* Sorts and groups ranges into sublists where each sublist represents an
* interval and its contained subintervals
*
* @param ranges
*/
protected void build(List ranges)
{
/*
* sort and partition into subranges
* which have no mutual containment
*/
List sublists = partitionNestedSublists(ranges);
/*
* convert each subrange to an NCNode consisting of a range and
* (possibly) its contained NCList
*/
for (IntervalI sublist : sublists)
{
subranges.add(new NCNode<>(
ranges.subList(sublist.getBegin(), sublist.getEnd() + 1)));
}
size = ranges.size();
}
/**
* Default constructor
*/
public NCList()
{
subranges = new ArrayList<>();
}
/**
* Sorts and traverses the ranges to identify sublists, whose start intervals
* are overlapping or disjoint but not mutually contained. Answers a list of
* start-end indices of the sorted list of ranges.
*
* @param ranges
* @return
*/
protected List partitionNestedSublists(List ranges)
{
List sublists = new ArrayList<>();
if (ranges.isEmpty())
{
return sublists;
}
/*
* sort by start ascending, length descending, so that
* contained intervals follow their containing interval
*/
Collections.sort(ranges, IntervalI.COMPARE_BEGIN_ASC_END_DESC);
int listStartIndex = 0;
IntervalI lastParent = ranges.get(0);
boolean first = true;
for (int i = 0; i < ranges.size(); i++)
{
IntervalI nextInterval = ranges.get(i);
if (!first && !lastParent.properlyContainsInterval(nextInterval))
{
/*
* this interval is not properly contained in the parent;
* close off the last sublist
*/
sublists.add(new Range(listStartIndex, i - 1));
listStartIndex = i;
lastParent = nextInterval;
}
first = false;
}
sublists.add(new Range(listStartIndex, ranges.size() - 1));
return sublists;
}
/**
* Adds one entry to the stored set
*
* @param entry
*/
@Override
public synchronized boolean add(final T entry)
{
final NCNode newNode = new NCNode<>(entry);
addNode(newNode);
return true;
}
/**
* Adds one NCNode to this NCList
*
* This method does not update the size
(interval count) of this
* NCList, as it may be used to rearrange nodes without changing their count.
* Callers should increment the count if needed.
*
* @param newNode
*/
protected void addNode(final NCNode newNode)
{
final long start = newNode.getBegin();
final long end = newNode.getEnd();
size += newNode.size();
/*
* cases:
* 1) precedes all subranges - add as NCNode on front of list
* 2) follows all subranges - add as NCNode on end of list
* 3) matches a subrange - add as a sibling in the list
* 4) properly enclosed by a subrange - add recursively to subrange
* 5) properly encloses one or more subranges - push them inside it
* 6) spans two subranges - insert between them
*/
/*
* find the first subrange whose end does not precede entry's start
*/
int candidateIndex = findFirstOverlap(start);
/*
* search for maximal span of subranges i-k that the new entry
* encloses; or a subrange that encloses the new entry
*/
boolean enclosing = false;
int firstEnclosed = 0;
int lastEnclosed = 0;
for (int j = candidateIndex; j < subranges.size(); j++)
{
NCNode subrange = subranges.get(j);
if (subrange.equalsInterval(newNode))
{
/*
* matching interval - insert adjacent
*/
subranges.add(j, newNode);
return;
}
if (end < subrange.getBegin() && !enclosing)
{
/*
* new entry lies between subranges j-1 j
*/
subranges.add(j, newNode);
return;
}
if (subrange.properlyContainsInterval(newNode))
{
/*
* push new entry inside this subrange as it encloses it
*/
subrange.addNode(newNode);
return;
}
if (start <= subrange.getBegin())
{
if (end >= subrange.getEnd())
{
/*
* new entry encloses this subrange (and possibly preceding ones);
* continue to find the maximal list it encloses
*/
if (!enclosing)
{
firstEnclosed = j;
}
lastEnclosed = j;
enclosing = true;
continue;
}
else
{
/*
* entry spans from before this subrange to inside it
*/
if (enclosing)
{
/*
* entry encloses one or more preceding subranges
*/
push(newNode, firstEnclosed, lastEnclosed);
}
else
{
/*
* entry overlaps two subranges but doesn't enclose either
* so just add it
*/
subranges.add(j, newNode);
}
return;
}
}
}
/*
* drops through to here if new range encloses all others
* or overlaps the last one
*/
if (enclosing)
{
push(newNode, firstEnclosed, lastEnclosed);
}
else
{
subranges.add(newNode);
}
}
@Override
public boolean contains(Object entry)
{
if (!(entry instanceof IntervalI))
{
return false;
}
IntervalI interval = (IntervalI) entry;
/*
* find the first sublist that might overlap, i.e.
* the first whose end position is >= from
*/
int candidateIndex = findFirstOverlap(interval.getBegin());
int to = interval.getEnd();
for (int i = candidateIndex; i < subranges.size(); i++)
{
NCNode candidate = subranges.get(i);
if (candidate.getBegin() > to)
{
/*
* we are past the end of our target range
*/
break;
}
if (candidate.contains(interval))
{
return true;
}
}
return false;
}
/**
* Update the tree so that the new node encloses current subranges i to j
* (inclusive). That is, replace subranges i-j (inclusive) with a new subrange
* that contains them.
*
* @param node
* @param i
* @param j
* @throws IllegalArgumentException
* if any of the subranges is not contained by the node's start-end
* range
*/
protected synchronized void push(NCNode node, final int i,
final int j)
{
for (int k = i; k <= j; k++)
{
NCNode n = subranges.get(k);
if (!node.containsInterval(n)) {
throw new IllegalArgumentException("Can't push " + n.toString()
+ " inside " + node.toString());
}
node.addNode(n);
}
for (int k = j; k >= i; k--)
{
subranges.remove(k);
}
subranges.add(i, node);
}
/**
* Answers a list of contained intervals that overlap the given range
*
* @param from
* @param to
* @return
*/
public List findOverlaps(long from, long to)
{
List result = new ArrayList<>();
findOverlaps(from, to, result);
return result;
}
/**
* Recursively searches the NCList adding any items that overlap the from-to
* range to the result list
*
* @param from
* @param to
* @param result
*/
protected void findOverlaps(long from, long to, List result)
{
/*
* find the first sublist that might overlap, i.e.
* the first whose end position is >= from
*/
int candidateIndex = findFirstOverlap(from);
for (int i = candidateIndex; i < subranges.size(); i++)
{
NCNode candidate = subranges.get(i);
if (candidate.getBegin() > to)
{
/*
* we are past the end of our target range
*/
break;
}
candidate.findOverlaps(from, to, result);
}
}
/**
* Search subranges for the first one whose end position is not before the
* target range's start position, i.e. the first one that may overlap the
* target range. Returns the index in the list of the first such range found,
* or the length of the list if none found.
*
* @param from
* @return
*/
protected int findFirstOverlap(final long from)
{
return BinarySearcher.findFirst(subranges, false, Compare.GE,
(int) from);
}
/**
* Formats the tree as a bracketed list e.g.
*
*
* [1-100 [10-30 [10-20]], 15-30 [20-20]]
*
*/
@Override
public String toString()
{
return subranges.toString();
}
/**
* Answers the NCList as an indented list
*
* @return
*/
public String prettyPrint()
{
StringBuilder sb = new StringBuilder(512);
int offset = 0;
int indent = 2;
prettyPrint(sb, offset, indent);
sb.append(System.lineSeparator());
return sb.toString();
}
/**
* @param sb
* @param offset
* @param indent
*/
void prettyPrint(StringBuilder sb, int offset, int indent)
{
boolean first = true;
for (NCNode subrange : subranges)
{
if (!first)
{
sb.append(System.lineSeparator());
}
first = false;
subrange.prettyPrint(sb, offset, indent);
}
}
/**
* Answers true if the store's structure is valid (nesting containment rules
* are obeyed), else false. For use in testing and debugging.
*
* @return
*/
public boolean isValid()
{
int count = 0;
for (NCNode subrange : subranges)
{
count += subrange.size();
}
if (count != size)
{
return false;
}
return isValid(Integer.MIN_VALUE, Integer.MAX_VALUE);
}
/**
* Answers true if the data held satisfy the rules of construction of an
* NCList bounded within the given start-end range, else false.
*
* Each subrange must lie within start-end (inclusive). Subranges must be
* ordered by start position ascending, and within that by end position
* descending.
*
*
* @param start
* @param end
* @return
*/
boolean isValid(final int start, final int end)
{
NCNode lastRange = null;
for (NCNode subrange : subranges)
{
if (subrange.getBegin() < start)
{
System.err.println("error in NCList: range " + subrange.toString()
+ " starts before " + end);
return false;
}
if (subrange.getEnd() > end)
{
System.err.println("error in NCList: range " + subrange.toString()
+ " ends after " + end);
return false;
}
if (lastRange != null)
{
if (subrange.getBegin() < lastRange.getBegin())
{
System.err.println("error in NCList: range " + subrange.toString()
+ " starts before " + lastRange.toString());
return false;
}
if (subrange.properlyContainsInterval(lastRange))
{
System.err.println("error in NCList: range " + subrange.toString()
+ " encloses preceding: " + lastRange.toString());
return false;
}
if (lastRange.properlyContainsInterval(subrange))
{
System.err.println("error in NCList: range " + subrange.toString()
+ " enclosed by preceding: " + lastRange.toString());
return false;
}
}
lastRange = subrange;
if (!subrange.isValid())
{
return false;
}
}
return true;
}
/**
* Answers the number of intervals stored
*
* @return
*/
@Override
public int size()
{
return size;
}
/**
* Answers a list of all entries stored, in no guaranteed order. This method
* is not synchronized, so is not thread-safe.
*/
public List getEntries()
{
List result = new ArrayList<>();
getEntries(result);
return result;
}
/**
* Adds all contained entries to the given list
*
* @param result
*/
void getEntries(List result)
{
for (NCNode subrange : subranges)
{
subrange.getEntries(result);
}
}
/**
* Removes the first interval I
found that is equal to T
* (I.equals(T)
). Answers true if an interval is removed, false
* if no match is found. This method is synchronized so thread-safe.
*
* @param entry
* @return
*/
public synchronized boolean remove(T entry)
{
if (entry == null)
{
return false;
}
int i = findFirstOverlap(entry.getBegin());
for (; i < subranges.size(); i++)
{
NCNode subrange = subranges.get(i);
if (subrange.getBegin() > entry.getBegin())
{
/*
* not found
*/
return false;
}
NCList subRegions = subrange.getSubRegions();
if (subrange.getRegion().equals(entry))
{
/*
* if the subrange is rooted on this entry, remove it,
* and remove and promote its subregions (if any)
*/
subranges.remove(i);
size -= subrange.size();
if (subRegions != null)
{
for (NCNode r : subRegions.subranges)
{
addNode(r);
}
}
return true;
}
else
{
if (subrange.remove(entry))
{
size--;
return true;
}
}
}
return false;
}
/**
* Answers the depth of interval nesting of this object, where 1 means there
* are no nested sub-intervals
*
* @return
*/
public int getDepth()
{
int subDepth = 0;
for (NCNode subrange : subranges)
{
subDepth = Math.max(subDepth, subrange.getDepth());
}
return subDepth;
}
/**
* Answers an iterator over the contained intervals, with no particular order
* guaranteed. The iterator does not support the optional remove
* operation (throws UnsupportedOperationException
if attempted).
*/
@Override
public Iterator iterator()
{
return new NCListIterator();
}
@Override
public synchronized void clear()
{
subranges.clear();
size = 0;
}
}