Shrink s_center with aggressive restructuring

[chaimleib]

If many overlapping Intervals are inserted, the tree becomes the degenerate case of a single set containing all the intervals, making O(r_log n) search into O(r_n).

If no Intervals are added after initialization, issue #5 will resolve this.

This issue is about what happens after the tree is initialized and an overlapping Interval is being added.

Is it possible to rebalance in amortized O(log n) time when an overlapping Interval is inserted?

[chaimleib]

If such a system were devised, all Nodes would be optimally-sized, with one Interval in each s_center (if none of the intervals overlap each other).

If a new Interval overlaps none of the x_centers, a new Node will be created, and all s_center sizes remain optimal.

If the new Interval overlaps one of the x_centers, it must overlap all the interval(s) in that s_center, and possibly other, deeper s_centers as well. Each of these may need to be relocated.

The possibilities:

1. The new Interval has the same range as the interval(s) in s_center.
   * Just add it to s_center, and we retain optimality.
2. The new Interval is smaller than s_center, with no protrusion.
   * If so, let s_old = s_center and set s_center to contain only the new Interval.
   * Now that the new Interval has been inserted, re-run the insertion with s_old.
   * (s_old does not fit cases 1 or 2, so this will not result in an infinite loop.)
3. The new Interval protrudes beyond s_center.
   * Does the protruding part contain any points that do not overlap the IntervalTree? (Use boundary_table, which is O(n_log n) time worst-case.)
   + If so, use a point in the protrusion as the x_center of a new Node. We retain optimal structure, at the cost of suboptimal O(n_log n) worst-case time complexity.
   - If not, add it to s_center. The this s_center is no longer optimal for this Node, but the solution on the level of the tree is optimally-structured. Still, we have O(n*log n) worst-case time complexity.

[chaimleib]

Another idea: add an optimize() method that may exceed n*log(n) time.

[chaimleib]

optimize() implementation using split_overlaps():
Completes in n^2 * log(n) time worst-case (lots of nested intervals), n*log(n) time on an already-optimized tree.

1. overlap_tree = split_overlaps()
2. Iterate over boundary_table to find intervals within the tree where a minimal number (!=0) of Intervals is present.
3. Recursively choose the first batch of x_centers based on those those Intervals.
4. Repeat for the next set of intervals containing more overlaps.

[chaimleib]

optimize() implementation using boundary_table:

This is based on the fact that over the range of the tree, the number of overlapping intervals only changes at Interval boundaries, which we are conveniently already storing in boundary_table.

# map boundary points to overlapping intervals
# O(n)
overlap_counts = {bound: self[bound] for bound in boundary_table.keys()}  

# map number of overlaps to sets of all intervals in overlap sets of that cardinality
# O(n)
overlaps = defaultdict(set)
for bound, ivs in overlap_counts.iteritems():
    count = len(ivs)
    overlaps[count] += ivs

# build optimized tree starting with least-overlapping Intervals
result = IntervalTree()
for _, ivs in sorted(overlaps.items()):  
    ivs -= result.all_intervals  # so that extend() does not sort stuff it doesn't need
    result.extend(ivs)

This assumes that extend() works to add intervals an optimal order, bisecting its sorted input recursively. This is O(n*log(n):

def extend(self, intervals):
    intervals = sorted(intervals)
    if len(intervals) < 3:
        for iv in intervals:
            self.add(iv)
        return
    half = len(intervals) // 2
    self.add(intervals[half])
    self.extend(intervals[:half])
    self.extend(intervals[half+1:]