# interval-skip-list

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

Latest version **2.0.1** (published 2015-02-13) · 0 weekly downloads

## Install

```sh
npm install interval-skip-list
pnpm add interval-skip-list
yarn add interval-skip-list
bun add interval-skip-list
```

## Health

**Score 15/100 (F)** — status: abandoned.

Positive: no vulnerabilities.

Warnings: low downloads; no types; no esm support.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 2.0.1 |
| Published | 2015-02-13 |
| First published | 2013-08-27 |
| Weekly downloads | 0 |
| TypeScript types | none |
| Module format | CommonJS |
| Dependencies | 1 |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 13 |
| Author | Nathan Sobo |
| Maintainers | nathansobo, kevinsawicki, zcbenz, benogle, maxbrunsfeld |
| Keywords | data-structures, collections, intervals |

## Links

- npm: https://www.npmjs.com/package/interval-skip-list
- Repository: http://github.com/atom/interval-skip-list
- Homepage: http://atom.github.io/interval-skip-list
- Issues: https://github.com/atom/interval-skip-list/issues
- npm.io page: https://npm.io/package/interval-skip-list

## Dependencies (1)

- [underscore-plus](https://npm.io/package/underscore-plus.md) ^1.6.6

## Recent versions

- 2.0.1 (latest) — 2015-02-13
- 2.0.0 — 2014-06-13
- 1.0.0 — 2014-03-06
- 0.4.0 — 2013-12-31
- 0.3.0 — 2013-12-29
- 0.2.0 — 2013-08-28
- 0.1.0 — 2013-08-27

## README

# Interval Skip List [![Build Status](https://travis-ci.org/atom/interval-skip-list.png)](https://travis-ci.org/atom/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](https://www.cise.ufl.edu/tr/DOC/REP-1992-45.pdf) by
Eric N. Hanson.

## Basic Usage Example

```coffee
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']
```

## API

* `::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.

## Using a Custom Comparator

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:

```coffee
list = new IntervalSkipList
  minIndex: [-Infinity, -Infinity]
  maxIndex: [Infinity, Infinity]
  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", [1, 2], [3, 4])
  list.insert("b", [2, 1], [3, 10])
  list.findContaining([1, Infinity]) # => ["a"]
  list.findContaining([2, 20]) # => ["a", "b"]
```

---
_Source: https://npm.io/package/interval-skip-list · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._