IntervalTrees exports one type: `IntervalTree{K, V}`

. It implements an
associative container mapping `(K, K)`

pairs to to values of type `V`

. `K`

may
be any ordered type, but only pairs `(a, b)`

where `a ≤ b`

can be stored.

Intervals in this package are always treated as end-inclusive, similar to the
Julia `Range`

type.

`IntervalTrees`

exports an abstract type `AbstractInterval{K}`

. Types deriving
from it are expected to implement `first`

and `last`

methods that return the
values of type `K`

giving the inclusive range of the interval.

There are also basic interval type provided:

```
immutable Interval{T} <: AbstractInterval{T}
first::T
last::T
end
immutable IntervalValue{K, V} <: AbstractInterval{K}
first::K
last::K
value::V
end
```

The basic data structure implemented is `IntervalTree{K, V}`

, which stores
intervals of type `V`

, that have start and end positions of type `K`

.

`IntervalMap{K, V}`

is a typealias for `IntervalTree{K, IntervalValue{K, V}}`

to simplify associating data of type `V`

with intervals.

New intervals can be added to an `IntervalTree`

with the `push!`

function.

```
xs = IntervalTree{Int, Interval{Int}}()
push!(xs, Interval{Int}(500, 1000))
```

A more efficient means of building the data structure by bulk insertion.
If the intervals are knows up front and provided in a sorted array, an
`IntervalTree`

can be built extremely efficiently.

```
intervals = Interval{Int}[]
# construct a large array of intervals...
sort!(intervals)
xs = IntervalTree{Int, Interval{Int}}(intervals)
```

`IntervalTree`

implements all the standard dictionary operations. You can use it
as an efficient way to map `(K, K)`

tuples to values.

```
using IntervalTrees
# Create an interval tree mapping (Int, Int) intervals to Strings.
xs = IntervalMap{Int, String}()
# Insert values
xs[(1,100)] = "Low"
xs[(101,1000)] = "Medium"
xs[(1001,10000)] = "High"
# Search for values
println(xs[(1001,10000)]) # prints "High"
# Get a value, returning a default value if not found
println(get(xs, (10001, 100000), "Not found")) # prints "Not found"
# Set a value if it's not already present
println(set(xs, (10001, 100000), "Not found"))
# Delete values
delete!(xs, (1,100))
```

As with dictionaries, key/value pairs can be iterated through efficiently.

```
for x in xs
println("Interval $(x.first), $(x.last) has value $(x.value)")
end
```

Some other iteration functions are provided:

**from(t::IntervalTree, query)**: Return an iterator thats iterates through every
key/value pair with an end position >= to query.

**keys(t::IntervalTree)**: Return an iterator that iterates through every
interval key in the tree.

**values(t::IntervalTree)**: Return an iterator that iterates through every
value in the tree.

The primary thing an `IntervalTree`

offers over a `Dict`

is the ability to efficiently
find intersections. `IntervalTrees`

supports searching and iterating over
intersections between two trees or between a tree and a single interval.

**intersect(t::IntervalTree, query::(Any, Any))**: Return an iterator over every
interval in `t`

that intersects `query`

.

**intersect(t1::IntervalTree, t2::IntervalTree)**: Return an iterator over every
pair of intersecting entries `(interval1, interval2)`

, where `interval1`

is
in `t1`

and `interval2`

is in `t2`

.

**hasintersection(t::IntervalTree, position)**: Return true if `position`

intersects some interval in `t`

.

Multiple data structures are refered to as "interval trees". What's implemented here is the data structure described in the Cormen, et al. "Algorithms" book, or what's refered to as an augmented tree in the wikipedia article. This sort of data structure is just an balanced search tree augmented with a field to keep track of the maximum interval end point in that node's subtree.

Many operations over two or more sets of intervals can be most efficiently implemented by jointly iterating over the sets in order. For example, finding all the intersecting intervals in two sets S and T can be implemented similarly to the merge function in mergesort in O(n+m) time.

Thus a general purpose data structure should be optimized for fast in-order iteration while efficiently supporting other operations like insertion, deletion, and single intersection tests. A B+-tree is nicely suited to the task. Since all the intervals and values are stored in contiguous memory in the leaf nodes, and the leaf nodes augmented with sibling pointers, in-order traversal is exceedingly efficient compared to other balanced search trees, while other operations are comparable in performance.

04/16/2014

4 months ago

85 commits