README.md

IntervalMap.js

IntervalMap.js is a fast map-like data structure where the key is a numeric interval and the value is arbitrary data.
Internally it uses an AVL-balanced interval tree for efficient insertions and queries.
It builds on top of Interval.js.

Interval semantics are closed: an interval [a, b] contains both endpoints a and b.

Features

• Map semantics: set(interval, value), get(interval), delete(interval)
• Interval queries:
  • hasOverlap(queryInterval) - fast overlap check
  • getOverlapping(queryInterval) - collect all overlapping entries (sorted by start, then end)
  • getAt(x, getAll = false) - point query (single fast match, or all matches)
• Efficient core: AVL tree with subtree max endpoint for tight pruning
• Batch build: IntervalMap.fromArray(pairs, mergeSame) builds a perfectly balanced tree
• Utilities: forEach, toArray, clear, clone, getSize, isEmpty, toString

Installation

npm install intervalmap
# or
yarn add intervalmap

Usage

Browser (minified bundle):

<script src="path/to/interval.min.js"></script>
<script src="path/to/intervalmap.min.js"></script>
<script>
  const map = new IntervalMap();
  map.set(new Interval(0, 10), 'A');
  console.log(map.getAt(5)); // 'A'
</script>

Node / bundlers (ESM):

import Interval from '@rawify/interval';
import IntervalMap from 'intervalmap';

const map = new IntervalMap();
map.set(new Interval(0, 10), 'A');
map.set(new Interval(20, 30), 'B');

console.log(map.hasOverlap(new Interval(8, 22))); // true
console.log(map.getAt(25)); // 'B'  (single fast match)
console.log(map.getAt(10, true)); // [{ interval:[0,10], value:'A' }] (all matches)

CommonJS:

const Interval = require('@rawify/interval');
const IntervalMap = require('intervalmap');

API

new IntervalMap()

Create an empty map.

set(interval: Interval, value: any): this

Insert or replace the value for an exact interval key. If the same [a,b] key is inserted again, the previous value is overwritten.

get(interval: Interval): any | null

Return the value for the exact interval key, or null if not found.

delete(interval: Interval): boolean

Remove the exact interval key. Returns true if a node was removed.

hasOverlap(q: Interval): boolean

true if any stored interval overlaps q. Uses subtree max to prune.

getOverlapping(q: Interval): Array<{ interval: Interval, value: any }>

Collect all overlaps with q. Results are in-order (sorted by (start,end)).

getAt(x: number, getAll = false): any | Array<{ interval, value }>

Point query:

• getAll === false (default): returns one matching value using a fast BST walk. If multiple intervals contain x, the chosen result is not guaranteed to be deterministic. This is more optimized for speed on non-overlapping intervals.
• getAll === true: returns all intervals that contain x (sorted).

forEach(fn: (interval, value) => void): this

In-order traversal.

toArray(): Array<{ interval: Interval, value: any }>

In-order snapshot of the map.

clear(): this

Resets the AVL tree.

getSize(): number

Gets the number of elements in the tree.

isEmpty(): boolean

Checks if the tree is empty

toString(): string

Gets a string representation of the tree

clone(): IntervalMap

Clones the IntervalMap object

static fromArray(pairs, mergeSame = false): IntervalMap

Build a perfectly balanced map from an array of { interval: Interval, value: any }.

• When mergeSame is true, touching/overlapping intervals with the same value are coalesced first (value-aware merge).
• When false, all provided intervals are kept as-is.

const pairs = [
  { interval: new Interval(0, 2), value: 'X' },
  { interval: new Interval(2, 5), value: 'X' }, // touches -> coalesce when mergeSame=true
  { interval: new Interval(4, 6), value: 'Y' }
];

const map1 = IntervalMap.fromArray(pairs, false); // keeps both X intervals
const map2 = IntervalMap.fromArray(pairs, true);  // merges X -> [0,5]

Performance Notes

• Insert / Delete / Exact Get: O(log n) (AVL-balanced)
• Overlap / Point queries: typically O(log n + k) where k is the number of results
• Pre-coalescing (mergeSame=true) reduces node count and improves cache locality
• fromArray() avoids n log n rebalancing by building the tree bottom-up

Coding Style

As every library I publish, IntervalMap is also built to be as small as possible after compressing it with Google Closure Compiler in advanced mode. Thus the coding style orientates a little on maxing-out the compression rate. Please make sure you keep this style if you plan to extend the library.

Building the library

After cloning the Git repository run:

npm install
npm run build

Run tests

npm run test

Copyright and Licensing

Copyright (c) 2025, Robert Eisele Licensed under the MIT license.