"circular" interval tree algorithm

Question

I'm wondering if anyone has implemented/knows of an (preferably javascript) interval-tree algorithm that will handle circular intervals. By circular, I mean intervals with a start > end. Note this also necessitates a cap to how large the intervals can be.

Is this just a subcase of the common interval tree problem?

In response to the questions posed in the comments: Here's an image (thanks G. Bach and wikipedia) of what I mean by a circular subrange:

And (unrelated to the above image) here's an example json representation of the ranges: [{id: 'range1', start: 3, end: 34}, {id: 'range2circular', start: 30, end:6}]

Hope

Thanks!

Answer 1

Sounds related to the idea behind circular arc graphs (but not the graphs themselves, since you start out with the intervals and don't care about a circular arc graph representation of them).

Assuming that's what it is, that means the domain can be represented by a period akin to the degrees of a circle. Then you have a minimum possible value min and a maximum possible value max = min + 1*period, and the first thing you do is find the smallest s such that start = min + s + k*period for integer k (basically, this is a modulo operation), and similarly you find the smallest e such that end = min + e + j*period.

Now you can represent your interval as (s,e) still with s > e. Split it up into two intervals (s, max) and (min, e), throw those into your interval tree, and give both of them a reference to your original interval (start, end). If you start with n intervals that possibly overlap a period, you end up with 2n intervals in the tree, and the asymptotic bounds hold.