IntervalMap.js

IntervalMap.js is a generic TypeScript map for closed numeric intervals. An AVL tree keeps updates and exact lookups balanced, while cached subtree endpoints accelerate point and overlap queries.

Intervals use closed semantics: [a, b] contains both endpoints, and intervals overlap when they share an endpoint.

Features

• Generic IntervalMap<Value> API with generated declarations
• Exact set, get, has, and delete operations
• Point and overlap queries with subtree pruning
• Sorted iteration by interval start and end
• Balanced bulk construction with optional value-aware coalescing
• Defensive interval snapshots that protect tree invariants
• CommonJS, ESM, browser-global, AMD, and browser-ESM builds

Installation

npm install intervalmap

@rawify/interval is installed as a dependency. Node.js 20 or newer is required.

Usage

ES modules

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

const schedule = new IntervalMap<string>();
schedule.set(new Interval(0, 10), 'setup');
schedule.set(new Interval(8, 20), 'run');

console.log(schedule.get(new Interval(0, 10))); // 'setup'
console.log(schedule.getAt(9));                  // 'setup'
console.log(schedule.getAt(9, true).map(entry => entry.value));
// ['setup', 'run']

Default and named class exports are available:

import IntervalMap, { IntervalMap as NamedIntervalMap } from 'intervalmap';

CommonJS

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

const map = new IntervalMap();
map.set(new Interval(1, 5), 'active');

Browser global

<script src="https://cdn.jsdelivr.net/npm/@rawify/[email protected]/dist/interval.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/intervalmap.min.js"></script>
<script>
  const map = new IntervalMap();
  map.set(new Interval(0, 10), 'active');
  console.log(map.getAt(5));
</script>

The same files are available from unpkg:

<script src="https://unpkg.com/@rawify/[email protected]/dist/interval.min.js"></script>
<script src="https://unpkg.com/[email protected]/dist/intervalmap.min.js"></script>

The browser-global build registers an AMD module when define.amd is present.

Browser ES modules

<script type="module">
  import Interval from 'https://cdn.jsdelivr.net/npm/@rawify/[email protected]/dist/interval.min.mjs';
  import IntervalMap from 'https://cdn.jsdelivr.net/npm/[email protected]/dist/intervalmap.min.mjs';

  const map = new IntervalMap();
  map.set(new Interval(0, 10), 'active');
</script>

Bundlers can select the minified browser ESM build explicitly:

import IntervalMap from 'intervalmap/browser';

Queries

Exact keys

const key = new Interval(10, 20);
map.set(key, 'value');

map.get(new Interval(10, 20));    // 'value'
map.has(new Interval(10, 20));    // true
map.delete(new Interval(10, 20)); // true

has() distinguishes a missing key from a key whose value is null or undefined.

Overlap queries

map.set(new Interval(0, 10), 'left');
map.set(new Interval(15, 20), 'right');

map.hasOverlap(new Interval(10, 15)); // true
map.getOverlapping(new Interval(8, 16));
// Both entries, sorted by interval start and end

Touching endpoints count as overlap because intervals are closed.

Point queries

map.getAt(9);       // First matching value in interval order, or null
map.getAt(9, true); // Every matching entry in interval order

The single-result overload avoids allocating an array. Use the second overload when all overlapping intervals are required.

Iteration

The map, entries(), keys(), and values() all iterate in interval order:

for (const { interval, value } of map) {
  console.log(interval.a, interval.b, value);
}

forEach(callback) uses the same order. toArray() returns a sorted snapshot.

Intervals are cloned on insertion and when returned by public methods. Mutating an input or returned interval does not alter the map. Values remain shared by reference.

Bulk Construction

IntervalMap.fromArray(entries, mergeSame) sorts entries and builds a minimal-height tree directly:

const map = IntervalMap.fromArray([
  { interval: new Interval(0, 2), value: 'X' },
  { interval: new Interval(2, 5), value: 'X' },
  { interval: new Interval(4, 6), value: 'Y' },
], true);

// X is stored once as [0, 5]; Y remains [4, 6].

With mergeSame = true, touching or overlapping intervals with strictly equal values are coalesced. Exact duplicate keys use normal map semantics: the last input value wins. Inputs are not mutated.

API

| Member | Description | | --- | --- | | size | Number of exact interval keys | | set(interval, value) | Insert or replace an entry and return the map | | get(interval) | Return an exact value or null | | has(interval) | Check for an exact key | | delete(interval) | Delete an exact key | | hasOverlap(interval) | Check whether any interval overlaps the query | | getOverlapping(interval) | Return every overlapping entry | | getAt(point) | Return the first value containing the point | | getAt(point, true) | Return every entry containing the point | | entries(), keys(), values() | Return sorted iterators | | forEach(callback) | Visit entries in sorted order | | toArray() | Return a sorted entry snapshot | | clear() | Remove all entries and return the map | | isEmpty() | Check whether the map is empty | | getSize() | Compatibility alias for size | | clone() | Clone nodes and intervals while retaining value references | | toString() | Format entries as [a, b] -> value | | IntervalMap.fromArray(entries, mergeSame) | Build a balanced map from entries |

TypeScript

ESM consumers can import the entry type directly:

import type { IntervalMapEntry } from 'intervalmap';

const entries: IntervalMapEntry<string>[] = [];

For TypeScript using CommonJS syntax, it is available through the class namespace:

import IntervalMap = require('intervalmap');

const entries: IntervalMap.Entry<string>[] = [];

Complexity

| Operation | Cost | | --- | ---: | | set, get, has, delete | O(log n) | | hasOverlap, single getAt | Typically O(log n), worst case O(n) | | All-match queries | Typically O(log n + k), worst case O(n) | | Sorted iteration | O(n) | | fromArray | O(n log n) sorting and O(n) construction |

Here, k is the number of returned matches. Heavy overlap can reduce pruning effectiveness.

Development

npm install
npm test

The test command rebuilds every distribution, type-checks ESM and CommonJS consumers, and runs runtime and package-export tests.

Copyright and License

Copyright (c) 2026 Robert Eisele

Licensed under the MIT license.