interval-skip-list

A data structure for finding all intervals that overlap a point in O(ln n)

Interval Skip List

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'27)
list.insert('b'15)
list.insert('c'88)
 
list.findContaining(1) # => ['b'] 
list.findContaining(2) # => ['b', 'a'] 
list.findContaining(8) # => ['c'] 
 
list.remove('b')
 
list.findContaining(2) # => ['a'] 
  • ::insert(label, startIndex, endIndex) Adds an interval with the given unique label to the list.

  • ::remove(label) Removes the interval with the given unique label from the list.

  • ::update(label, startIndex, endIndex) Inserts or updates the interval corresponding to the given unique label. Unlike ::insert, this method allows you to specify a label that's already been inserted in the list.

  • ::findContaining(indices...) Returns the labels of all intervals containing the given indices.

  • ::findIntersecting(indices...) Returns the labels of all intervals intersecting the given set of indices. Unlike ::findContaining, this method does not require that the intervals contain all the given indices.

  • ::findStartingAt(index) Returns the labels of all intervals starting at the given index.

  • ::findEndingAt(index) Returns the labels of all intervals ending at the given index.

  • ::findStartingIn(startIndex, endIndex) Returns the labels of all intervals starting within the interval described by the given start and end indices.

  • ::findEndingIn(startIndex, endIndex) Returns the labels of all intervals ending within the interval described by the given start and end indices.

You can also supply a custom comparator function with corresponding min and max index values. The following example uses arrays expressing coordinate pairs instead of the default numeric values:

list = new IntervalSkipList
  minIndex: [-Infinity-Infinity]
  maxIndex: [InfinityInfinity]
  compare: (a, b) ->
    if a[0< b[0]
      -1
    else if a[0> b[0]
      1
    else
      if a[1< b[1]
        -1
      else if a[1> b[1]
        1
      else
        0
 
  list.insert("a"[12][34])
  list.insert("b"[21][310])
  list.findContaining([1Infinity]) # => ["a"] 
  list.findContaining([220]) # => ["a", "b"]