Python: dynamic interval data structure

Question

I am looking for some python code to efficiently calculate interval overlaps. I used to use the bx-python package spacing tree, but now I need to remove the spacing from the tree (or, better yet, change them). The bx-python tree does not seem to support this.

Any pointers?

Answer 1

banyan supports removing spacing from a tree. For example, to remove the minimum number of intervals from the interval list so that the remaining intervals do not overlap in O(n log n) , you could use banyan.SortedSet (added red-black tree):

 from banyan import SortedSet, OverlappingIntervalsUpdator # pip install banyan def maximize_nonoverlapping_count(intervals): # build "interval" tree sorted by the end-point O(n log n) tree = SortedSet(intervals, key=lambda (start, end): (end, (end - start)), updator=OverlappingIntervalsUpdator) result = [] while tree: # until there are intervals left to consider # pop the interval with the smallest end-point, keep it in the result result.append(tree.pop()) # O(log n) # remove intervals that overlap with the popped interval overlapping_intervals = tree.overlap(result[-1]) # O(m log n) tree -= overlapping_intervals # O(m log n) return result 

Example:

 print maximize_nonoverlapping_count([[3, 4], [5, 8], [0, 6], [1, 2]]) # -> [[1, 2], [3, 4], [5, 8]] 

See Python - Removing overlapping lists .

Answer 2

Maybe it helps to preserve all intersection intervals.

You need:

• the boundaries of the union of all intervals,
• for each left border of the intersection and the list of intervals from which the intersection is made.

Intersection intervals can be stored in a tree because they are represented only with the left border. The interval for inserting and deleting methods looks like (simplified):

Paste: find the intersection intervals for the left and right borders of the new interval, divide these intersection intervals into 2 or 3 new intersection intervals. For each intersection interval between adding a pointer to a new interval.

Delete: find intersection intervals for the left and right borders, combine them into intersection intervals up to. For each intersection interval between a remote pointer to a remote interval.

Answer 3

If you are looking for a Python library that handles arithmetic intervals, consider python-interval . Disclaimer: I support this library.

This library has support for checking matches and automatically merging intervals. For example:

 >>> import intervals as I >>> I.closed(1,2) | I.closed(2,3) [1,3] >>> I.closed(1,2).overlaps(I.closed(3,4)) False 

If you want to specifically calculate the overlap:

 >>> I.closed(1,3) & I.closed(2, 4) [2,3] 

It supports open / closed intervals, finite or infinite. To remove intervals for a given one, simply use the difference operator:

 >>> I.closed(1, 4) - I.closed(2, 3) [1,2) | (3,4] 

I can help you if you can be a little more specific.