Interval Search Tree

Package interval provides a generic interval tree implementation.

An interval tree is a data structure useful for storing values associated with intervals, and efficiently search those values based on intervals that overlap with any given interval. This generic implementation uses a self-balancing binary search tree algorithm, so searching for any intersection has a worst-case time-complexity guarantee of <= 2 log N, where N is the number of items in the tree.

For more on interval trees, see

Installing

$ go get github.com/rdleal/intervalst

Usage

Importing the package:

import "github.com/rdleal/intervalst/interval"

Creating a tree with time.Time as interval key type and string as value type:

cmpFn := func(t1, t2 time.Time) int {
        switch{
        case t1.After(t2): return 1
        case t1.Before(t2): return -1
        default: return 0
        }
}
st := interval.NewSearchTree[string](cmpFn)

Upserting a value:

start := time.Now()
end := start.Add(2*time.Hour)
err := st.Insert(start, end, "event 1")
if err != nil {
        // error handling...
}

Searching for any intersection:

start := time.Now()
end := start.Add(2*time.Hour)
val, ok := st.AnyIntersection(start, end)
if !ok {
        // no intersection found for start and end...
}

Deleting an interval from the tree:

start := time.Now()
end := start.Add(2*time.Hour)
err := st.Delete(start, end)
if err != nil {
        // error handling...
}

For more operations, check out the GoDoc page.

Testing

Running unit tests:

$ go test -v -cover -race ./...

Benchmarks

Running benchmarks:

$ cd interval && go test -run='^$' -bench=. -benchtime=20s -benchmem

License

MIT