Quadratic performance characteristics

[avikivity]

pyinter is incredibly slow; adding a thousand intervals requires a million operations, because add() loops over all the existing elements in the set.

add() (and similar functions) should take advantage of the sorted order and only touch elements which intersect other.

[intiocean]

I agree @avikivity – It's never been optimised for large sets of intervals. A PR to improve this would be very appreciated as I won't have time to do this at the moment.

[ilius]

Also intersection takes O(M*N) running time (the easiest way to implement). This operation was the only reason I looked up for an interval set library.
Here is my simple (but a little messy) code with O(M+N) running time: https://github.com/ilius/starcal/blob/master/scal3/interval_utils.py#L70

My only problem is handling open/closed boundaries properly