interval-skip-list

JavaScript data structure for finding all intervals that overlap a point

View the Project on GitHub atom/interval-skip-list

Interval Skip List Build Status

This data structure maps intervals to values and allows you to find all intervals that contain an index in O(ln(n)), where n is the number of intervals stored. This implementation is based on the paper The Interval Skip List by Eric N. Hanson.

IntervalSkipList = require 'interval-skip-list'
list = new IntervalSkipList

list.insert('a', 2, 7)
list.insert('b', 1, 5)
list.insert('c', 8, 8)

list.findContaining(1) # => ['b']
list.findContaining(2) # => ['b', 'a']
list.findContaining(8) # => ['c']

list.remove('b')

list.findContaining(2) # => ['a']