C++ - Interval Tree Implementation

C implementation of an interval tree?

C code for a red and black tree, licensed with the very generous MIT license.

_{(Backup at archive.org.)}

C++ - interval tree implementation

Boost-like ? Boost ICL!

The Boost Interval Container Library

Interval Tree algorithm inplementation

max is needed to find the overlap, eg use this data

 {{15, 20}, {10, 11}, {17, 22}, {5, 20}, {12, 25}, {30, 40}};

and search for 24

C# Interval tree class

There is a download on the codeplex page: http://intervaltree.codeplex.com/SourceControl/list/changesets -> Right hand side -> Download

Is there a collection for storing discrete intervals?

This is a well known question. There is a wikipedia page on possible solutions to your question. Of course in the C++ STL you could implement a solution based on the Naive approach, explained in wikipedia, using a std::map because a map is a Red-Black Tree which is a type of Binary Search Tree.

Structures for Efficient Indexing Of Objects by Intervals

This solution isn't particularly memory-efficient, but if I understand you correctly, it should allow for a relatively simple implementation of the functionality you want.

Keep an array or slice funcs of all your function objects, so that they each have a canonical integer index, and can be looked up by that index.
Keep a slice of ints s that is always the same size as your buffer of floats; it maps a particular index in your buffer to a "function index" in the slice of functions. You can use -1 to represent a number that is not part of any interval.
Keep a slice of (int, int) pairs intervals such that intervals[i] contains the start-end indices for the function stored at funcs[i].

I believe this enables you to implement your desired functionality without too much hassle. For example, to query by index i, look up s[i], then return funcs[s[i]] and intervals[s[i]]. When changes occur to the buffer, change s as well, cross-referencing between s and the intervals slice to figure out if neighboring intervals are affected. I'm happy to explain this part in more detail, but I don't totally understand the requirements for interval updates. (When you do an interval insert, does it correspond to an insert in the underlying buffer? Or are you just changing which buffer elements are associated with which functions? In which case, does an insert cause a deletion at the beginning of the next interval? Most schemes should work, but it changes the procedure.)

Data structure for handling intervals

It sounds like you could just use a balanced binary tree of all the boundary times.

For example, represent {(1,4), (8,10), (12,15)} as a tree containing 1, 4, 8, 10, 12, and 15.

Each node needs to say whether it's the start or end of an interval. So:

                          8 (start)
                         /        \
                1 (start)         12 (start)
                      \             /      \
                     4 (end)   10 (end)   15 (end)

(Here all the "end" nodes ended up at the bottom by coincidence.)

Then I think you can have all your operations in O(log n) time. To add an interval:

Find the start time. If it's already in the tree as a start time, you can leave it there. If it's already in the tree as an end time, you'll want to remove it. If it's not in the tree and it doesn't fall during an existing interval, you'll want to add it. Otherwise you don't want to add it.
Find the stop time, using the same method to find out if you need to add it, remove it, or neither.
Now you just want to add or remove the abovementioned start and stop nodes and, at the same time, delete all the existing nodes in between. To do this you only need to rebuild the tree nodes at or directly above those two places in the tree. If the height of the tree is O(log n), which you can guarantee by using a balanced tree, this takes O(log n) time.

(Disclaimer: If you're in C++ and doing explicit memory management, you might end up freeing more than O(log n) pieces of memory as you do this, but really the time it takes to free a node should be billed to whoever added it, I think.)

Removing an interval is largely the same.

Checking a point or interval is straightforward.

Finding the first gap of at least a given size after a given time can be done in O(log n) too, if you also cache two more pieces of information per node:

In each start node (other than the leftmost), the size of the gap immediately to the left.
In every node, the size of the largest gap that appears in that subtree.

To find the first gap of a given size that appears after a given time, first find that time in the tree. Then walk up until you reach a node that claims to contain a large enough gap. If you came up from the right, you know this gap is to the left, so you ignore it and keep walking up. Otherwise you came from the left. If the node is a start node, check to see if the gap to its left is large enough. If so, you're done. Otherwise, the large-enough gap must be somewhere to the right. Walk down to the right and continue down until you find the gap. Again, because the height of the tree is O(log n), walking it three times (down, up, and possibly down again) is O(log n).