StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You could use an <a href="http://en.wikipedia.org/wiki/Interval_tree" rel="nofollow">IntervalTree</a>. Here's one I made earlier.</p> <pre><code>public class IntervalTree<T extends IntervalTree.Interval> { // My intervals. private final List<T> intervals; // My center value. All my intervals contain this center. private final long center; // My interval range. private final long lBound; private final long uBound; // My left tree. All intervals that end below my center. private final IntervalTree<T> left; // My right tree. All intervals that start above my center. private final IntervalTree<T> right; public IntervalTree(List<T> intervals) { if (intervals == null) { throw new NullPointerException(); } // Initially, my root contains all intervals. this.intervals = intervals; // Find my center. center = findCenter(); /* * Builds lefts out of all intervals that end below my center. * Builds rights out of all intervals that start above my center. * What remains contains all the intervals that contain my center. */ // Lefts contains all intervals that end below my center point. final List<T> lefts = new ArrayList<T>(); // Rights contains all intervals that start above my center point. final List<T> rights = new ArrayList<T>(); long uB = Long.MIN_VALUE; long lB = Long.MAX_VALUE; for (T i : intervals) { long start = i.getStart(); long end = i.getEnd(); if (end < center) { lefts.add(i); } else if (start > center) { rights.add(i); } else { // One of mine. lB = Math.min(lB, start); uB = Math.max(uB, end); } } // Remove all those not mine. intervals.removeAll(lefts); intervals.removeAll(rights); uBound = uB; lBound = lB; // Build the subtrees. left = lefts.size() > 0 ? new IntervalTree<T>(lefts) : null; right = rights.size() > 0 ? new IntervalTree<T>(rights) : null; // Build my ascending and descending arrays. /** @todo Build my ascending and descending arrays. */ } /* * Returns a list of all intervals containing the point. */ List<T> query(long point) { // Check my range. if (point >= lBound) { if (point <= uBound) { // In my range but remember, there may also be contributors from left or right. List<T> found = new ArrayList<T>(); // Gather all intersecting ones. // Could be made faster (perhaps) by holding two sorted lists by start and end. for (T i : intervals) { if (i.getStart() <= point && point <= i.getEnd()) { found.add(i); } } // Gather others. if (point < center && left != null) { found.addAll(left.query(point)); } if (point > center && right != null) { found.addAll(right.query(point)); } return found; } else { // To right. return right != null ? right.query(point) : Collections.<T>emptyList(); } } else { // To left. return left != null ? left.query(point) : Collections.<T>emptyList(); } } private long findCenter() { //return average(); return median(); } protected long median() { // Choose the median of all centers. Could choose just ends etc or anything. long[] points = new long[intervals.size()]; int x = 0; for (T i : intervals) { // Take the mid point. points[x++] = (i.getStart() + i.getEnd()) / 2; } Arrays.sort(points); return points[points.length / 2]; } /* * What an interval looks like. */ public interface Interval { public long getStart(); public long getEnd(); } /* * A simple implemementation of an interval. */ public static class SimpleInterval implements Interval { private final long start; private final long end; public SimpleInterval(long start, long end) { this.start = start; this.end = end; } public long getStart() { return start; } public long getEnd() { return end; } @Override public String toString() { return "{" + start + "," + end + "}"; } } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload