1 package jalview.datamodel.features;
3 import java.util.ArrayList;
4 import java.util.Collections;
5 import java.util.Comparator;
9 * An adapted implementation of NCList as described in the paper
15 public class NCList<T extends ContiguousI>
19 * a list, in start position order, of sublists of ranges ordered so
20 * that each contains (or is the same as) the one that follows it
22 private List<NCNode<T>> subranges;
25 * a comparator to sort intervals by start position ascending, with
26 * longer (enclosing) intervals preceding those they enclose
28 Comparator<ContiguousI> intervalSorter = new RangeComparator(true);
31 * Constructor given a list of things that are each located on a contiguous
32 * interval. Note that the constructor may reorder the list.
34 * We assume here that for each range, start <= end. Behaviour for reverse
35 * ordered ranges is undefined.
39 public NCList(List<T> ranges)
47 protected void build(List<T> ranges)
50 * sort by start ascending so that contained intervals
51 * follow their containing interval
53 Collections.sort(ranges, intervalSorter);
55 List<SubList> sublists = findSubranges(ranges);
57 subranges = new ArrayList<NCNode<T>>();
60 * convert each subrange to an NCNode consisting of a range and
61 * (possibly) its contained NCList
63 for (SubList sublist : sublists)
65 subranges.add(new NCNode<T>(ranges.subList(sublist.startIndex,
66 sublist.endIndex + 1)));
71 public NCList(T entry)
73 List<T> ranges = new ArrayList<T>();
79 * Traverses the sorted ranges to identify sublists, within which each
80 * interval contains the one that follows it
85 protected List<SubList> findSubranges(List<T> ranges)
87 List<SubList> sublists = new ArrayList<SubList>();
89 int listStartIndex = 0;
90 long lastEndPos = Long.MAX_VALUE;
92 for (int i = 0; i < ranges.size(); i++)
94 ContiguousI nextInterval = ranges.get(i);
95 long nextStart = nextInterval.getBegin();
96 long nextEnd = nextInterval.getEnd();
97 if (nextStart > lastEndPos || nextEnd > lastEndPos)
100 * this interval is not contained in the preceding one
101 * close off the last sublist
103 sublists.add(new SubList(listStartIndex, i - 1));
106 lastEndPos = nextEnd;
109 sublists.add(new SubList(listStartIndex, ranges.size() - 1));
114 * Adds one entry to the stored set
118 public synchronized void add(T entry)
120 long start = entry.getBegin();
121 long end = entry.getEnd();
125 * - precedes all subranges: add as NCNode on front of list
126 * - follows all subranges: add as NCNode on end of list
127 * - enclosed by a subrange - add recursively to subrange
128 * - encloses one or more subranges - push them inside it
129 * - none of the above - add as a new node and resort nodes list (?)
133 * find the first subrange whose end does not precede entry's start
135 int candidateIndex = findFirstOverlap(start);
136 if (candidateIndex == -1)
139 * all subranges precede this one - add it on the end
141 subranges.add(new NCNode<T>(entry));
146 * search for maximal span of subranges i-k that the new entry
147 * encloses; or a subrange that encloses the new entry
149 int i = candidateIndex;
150 boolean enclosing = false;
151 boolean overlapping = false;
153 for (int j = candidateIndex; j < subranges.size(); j++)
155 NCNode<T> subrange = subranges.get(j);
157 if (end < subrange.getStart() && !overlapping)
160 * new entry lies between subranges j-1 j
162 subranges.add(j, new NCNode<T>(entry));
166 if (subrange.getStart() <= start && subrange.getEnd() >= end)
169 * push new entry inside this subrange as it encloses it
175 if (start <= subrange.getStart())
177 if (end >= subrange.getEnd())
180 * new entry encloses this subrange (and possibly preceding ones);
181 * continue to find the maximal list it encloses
189 * entry spans from before this subrange to inside it
194 * entry encloses one or more preceding subranges
196 addEnclosingRange(entry, i, j - 1);
202 * entry spans two subranges but doesn't enclose any
205 subranges.add(j, new NCNode<T>(entry));
214 * Update the tree so that the range of the new entry encloses subranges i to
215 * j (inclusive). That is, replace subranges i-j with a new subrange that
222 protected synchronized void addEnclosingRange(T entry, int i, int j)
224 // TODO how to rebuild the subranges as an NCList?
229 * Returns a (possibly empty) list of items whose extent overlaps the given
233 * start of overlap range (inclusive)
235 * end of overlap range (inclusive)
238 public List<T> findOverlaps(long from, long to)
240 List<T> result = new ArrayList<T>();
242 findOverlaps(from, to, result);
248 * Recursively searches the NCList adding any items that overlap the from-to
249 * range to the result list
255 protected void findOverlaps(long from, long to,
259 * find the first sublist that might overlap, i.e.
260 * the first whose end position is >= from
262 int candidateIndex = findFirstOverlap(from);
264 if (candidateIndex == -1)
269 for (int i = candidateIndex; i < subranges.size(); i++)
271 NCNode<T> candidate = subranges.get(i);
272 if (candidate.getStart() > to)
275 * we are past the end of our target range
279 candidate.addOverlaps(from, to, result);
285 * Search subranges for the first one whose end position is not before the
286 * target range's start position, i.e. the first one that may overlap the
287 * target range. Returns the index in the list of the first such range found,
288 * or -1 if none found.
293 protected int findFirstOverlap(long from)
295 // TODO binary search
296 // for now quick cheat linear search
298 if (subranges != null)
300 for (NCNode<T> subrange : subranges)
302 if (subrange.getEnd() >= from)
313 * Formats the tree as a bracketed list e.g.
316 * [1-100 [10-30 [10-20]], 15-30 [20-20]]
320 public String toString()
322 return subranges.toString();