intervaltree JS

A mutable, self-balancing interval tree for JavaScript/TypeScript.

Written in TypeScript with no runtime dependencies (the SHA-256 used by hash() is bundled at build time). Uses an augmented AVL tree under the hood for O(log n) operations.

Install

npm install intervaltree

Quick Start

import { Interval, IntervalTree } from 'intervaltree'

const tree = new IntervalTree()
tree.addInterval(1, 5, 'data for 1-5')
tree.addInterval(3, 7)
tree.addInterval(8, 10)

// Query by point
const intervals = tree.searchPoint(4)  // Returns intervals containing point 4
// Result: [Interval(1, 5, 'data for 1-5'), Interval(3, 7)]

// Query by range (overlaps)
const overlapping = tree.searchOverlap(6, 9)  // Returns intervals overlapping [6, 9)
// Result: [Interval(3, 7), Interval(8, 10)]

Examples

Creating a Tree

import { Interval, IntervalTree } from 'intervaltree'

// Empty tree
const tree = new IntervalTree()

// From array of Interval objects
const intervals = [
  new Interval(1, 3, 'first'),
  new Interval(5, 8, 'second'),
  new Interval(7, 10, 'third')
]
const tree2 = new IntervalTree(intervals)

// From tuples
const tree3 = IntervalTree.fromTuples([
  [1, 3],
  [5, 8],
  [7, 10, 'with data']
])

Adding Intervals

// Add with explicit Interval object
tree.add(new Interval(1, 5, 'my data'))

// Add with convenience method
tree.addInterval(10, 15, 'more data')

// Add multiple intervals at once
tree.addAll([
  new Interval(20, 25),
  new Interval(30, 35, 'bulk add')
])

// Note: Duplicate intervals (same start, end, and data) are ignored
tree.addInterval(1, 5, 'a')
tree.addInterval(1, 5, 'a')  // This is a no-op
tree.addInterval(1, 5, 'b')  // Distinct data: this is added
console.log(tree.size)  // 2

Querying the Tree

// Find all intervals containing a point
const pointResult = tree.searchPoint(6)
// Returns: Array of Interval objects containing point 6

// Find all intervals overlapping a range
const overlapResult = tree.searchOverlap(5, 10)
// Returns: All intervals that overlap with [5, 10)

// Find intervals completely enveloped by a range
const enveloped = tree.searchEnveloped(0, 100)
// Returns: All intervals where start >= 0 and end <= 100

// Find intervals by minimum length starting at/after a point
const byLength = tree.searchByLengthStartingAt(3, 5)
// Returns: All intervals of length >= 3 starting at position 5 or later

// Find first interval of minimum length — O(log n) with early termination
const first = tree.findOneByLengthStartingAt(3, 5)
// Returns: First interval of length >= 3 starting at/after position 5
// If found interval starts before 5, it's adjusted to start at 5

// With optional filter function
const filtered = tree.findOneByLengthStartingAt(3, 5, iv => iv.data?.priority === 'high')

Tree Navigation

// Get the earliest interval (by start)
const earliest = tree.first()   // O(log n)

// Get the latest interval (by start)
const latest = tree.last()      // O(log n)

// O(1) size check (no traversal needed)
console.log(tree.size)  // Number of intervals

Accessing Interval Properties

const interval = new Interval(4, 7, { id: 123, name: 'test' })

console.log(interval.start)   // 4
console.log(interval.end)     // 7
console.log(interval.data)    // { id: 123, name: 'test' }
console.log(interval.length)  // 3

// Check if interval contains a point
interval.containsPoint(5)  // true
interval.containsPoint(7)  // false (end is exclusive)

// Check if interval overlaps with a range
interval.overlapsWith(3, 6)  // true

Removing Intervals

// Remove a specific interval
const toRemove = new Interval(1, 5, 'my data')
tree.remove(toRemove)

// Remove multiple intervals
tree.removeAll([interval1, interval2])

// Remove all intervals overlapping a range
tree.removeEnveloped(5, 10)
// Removes only intervals completely contained within [5, 10)

Chopping (Advanced)

The chop method removes a section from all intervals in the tree, splitting intervals that partially overlap the chopped region.

const tree = new IntervalTree()
tree.addInterval(0, 10)
tree.addInterval(5, 15)
tree.addInterval(12, 20)

// Remove the region [7, 13) from all intervals
tree.chop(7, 13)

console.log(tree.toTuples())
// Result: [[0, 7], [13, 15], [13, 20]]
// The interval [0, 10] becomes [0, 7]
// The interval [5, 15] becomes [13, 15]
// The interval [12, 20] becomes [13, 20]

Batch Chopping

The chopAll method removes multiple ranges in a single operation, much faster than calling chop() individually when removing many ranges (e.g., marking calendar events as busy time).

const tree = new IntervalTree()
tree.addInterval(0, 100)

// Remove multiple ranges at once
tree.chopAll([[10, 20], [30, 40], [50, 60]])

console.log(tree.toTuples())
// Result: [[0, 10], [20, 30], [40, 50], [60, 100]]

// Overlapping chop ranges are merged automatically
tree.chopAll([[10, 30], [20, 40]])
// Equivalent to chopping [10, 40]

For small numbers of ranges (≤3), chopAll delegates to individual chop() calls. For larger batches, it sorts and merges the ranges, then does a single linear sweep — O(n log n) instead of O(n × m) for n ranges on m intervals.

Merging Overlapping Intervals

const tree = IntervalTree.fromTuples([
  [1, 5],
  [4, 8],   // Overlaps with [1, 5]
  [10, 12],
  [11, 15]  // Overlaps with [10, 12]
])

tree.mergeOverlaps()

console.log(tree.toTuples())
// Result: [[1, 8], [10, 15]]

Utility Methods

// Get all intervals as array
const allIntervals = tree.toArray()

// Get sorted array of intervals
const sorted = tree.toSorted()  // Sorted by start, then end

// Get as array of tuples
const tuples = tree.toTuples()  // [[start, end], [start, end, data], ...]

// Get tree size
console.log(tree.size)  // Number of intervals in tree

// Clone the tree
const cloned = tree.clone()

// Get string representation
console.log(tree.toString())
// Output: "IntervalTree([ Interval(1, 5, length=4), Interval(10, 15, length=5) ])"

// Runs the full invariant check on demand. Automatic checks after every
// mutation are off by default; set the environment variable
// INTERVALTREE_DEBUG=1 to turn them on (this repo's test suites do).
tree.verify()

Equality, Serialization, and Hashing

Comparing two trees, detecting changes, and serializing to JSON all use the same canonical form (sorted intervals + data). Construction order doesn't matter:

const a = IntervalTree.fromTuples([[0, 10], [20, 30]])

const b = new IntervalTree()
b.addInterval(20, 30)
b.addInterval(0, 10)

a.equals(b)     // true — same intervals, regardless of insertion order
a.hash() === b.hash()  // true — hash is semantic

JSON.stringify emits the canonical form too, so hashes and diffs are stable across serialize/deserialize cycles:

JSON.stringify(a)
// → '[[0,10,null],[20,30,null]]'

Restore with IntervalTree.fromJSON(json); equals() and hash() both hold after the round trip.

Use equals() when you expect inequality and want an early exit; use hash() when you want a cacheable fingerprint (e.g. memoization keys, cross-request change detection).

Working with Dates

Since intervals work with numbers, you can use timestamps for date-based intervals:

const schedule = new IntervalTree()

// Add time slots (using timestamps)
const start = new Date('2024-01-01T09:00:00').getTime()
const end = new Date('2024-01-01T10:00:00').getTime()
schedule.addInterval(start, end, 'Morning meeting')

// Query for a specific time
const when = new Date('2024-01-01T09:30:00').getTime()
const conflicts = schedule.searchPoint(when)

// Find available slots
const dayStart = new Date('2024-01-01T08:00:00').getTime()
const minDuration = 60 * 60 * 1000  // 1 hour in milliseconds
const available = schedule.findOneByLengthStartingAt(minDuration, dayStart)

API Reference

IntervalTree

Construction:

• constructor(intervals?: Interval<T>[]) - Create a new tree, optionally with initial intervals
• static fromTuples<T>(tuples: Array<[number, number] | [number, number, T]>) - Create from tuple array
• IntervalTree.fromJSON(input) - Inverse of toJSON; accepts the JSON string or parsed tuples

Adding/Removing:

• add(interval: Interval<T>) - Add an interval to the tree
• addInterval(start: number, end: number, data?: T) - Convenience method to add interval
• addAll(intervals: Interval<T>[]) - Add multiple intervals
• remove(interval: Interval<T>) - Remove a specific interval
• removeAll(intervals: Interval<T>[]) - Remove multiple intervals
• removeEnveloped(start: number, end: number) - Remove intervals contained within range

Searching:

• searchPoint(point: number) - Find all intervals containing a point
• searchOverlap(start: number, end: number) - Find all intervals overlapping a range
• searchEnveloped(start: number, end: number) - Find intervals completely within a range
• searchByLengthStartingAt(length: number, start: number) - Find intervals by minimum length
• findOneByLengthStartingAt(minLength: number, startingAt: number, filterFn?: (iv: Interval<T>) => boolean) - O(log n) first matching interval with optional filter

Navigation:

• first(): Interval<T> | null - Get the earliest interval by start (O(log n))
• last(): Interval<T> | null - Get the latest interval by start (O(log n))

Boolean Checks:

• contains(point: number): boolean - Check if any interval contains a point
• overlaps(start: number, end: number): boolean - Check if any interval overlaps with range
• isEmpty: boolean - Check if the tree is empty (getter)

Set Operations:

• union(other: IntervalTree<T>): IntervalTree<T> - Combine interval records from both trees, deduplicating only exact same start, end, and data
• rangeUnion(other: IntervalTree<T>): IntervalTree<T> - Combine trees and merge overlapping or adjacent ranges
• intersection(other: IntervalTree<T>): IntervalTree<T> - Find overlapping regions between trees
• difference(other: IntervalTree<T>): IntervalTree<T> - Remove overlapping intervals from other tree

Iteration & Transformation:

• [Symbol.iterator]() - Enables for...of loops and spread operator
• forEach(callback: (interval: Interval<T>, index: number) => void) - Execute callback for each interval
• map<U>(callback: (interval: Interval<T>) => Interval<U>): IntervalTree<U> - Transform intervals

Manipulation:

• chop(start: number, end: number) - Remove a region from all intervals
• chopAll(ranges: Array<[number, number]>) - Remove several regions in one sweep
• mergeOverlaps() - Merge all overlapping intervals

Utility:

• clone(): IntervalTree<T> - Create a deep copy of the tree
• toArray(): Interval<T>[] - Get all intervals as an array
• toSorted(): Interval<T>[] - Get all intervals sorted by start then end
• toTuples(): IntervalTuple<T>[] - Get intervals as tuple array
• size: number - Get the number of intervals in the tree (getter)

Equality & Serialization:

• equals(other: IntervalCollection<T>): boolean - Semantic equality by sorted intervals + data (short-circuits on size mismatch). Use this instead of comparing hashes when inequality is likely — it exits on the first mismatch.
• hash(): string - SHA-256 of the canonical interval list. Same intervals ⇒ same hash, regardless of construction order or op sequence. Useful for change detection and memoization cache keys.
• toJSON(): Array<[number, number, T | undefined]> - Sorted intervals as [start, end, data] tuples. JSON.stringify(tree) uses this, so serialized trees are stable and topology-independent.

Interval

• constructor(start: number, end: number, data?: unknown) - Create an interval
• start - Get the start point (inclusive)
• end - Get the end point (exclusive)
• data - Get the associated data
• length - Get the interval length (end - start)
• containsPoint(point: number) - Check if interval contains a point
• overlapsWith(start: number, end: number) - Check if interval overlaps with range
• equals(other: Interval) - Check equality with another interval

compareIntervals(a: Interval, b: Interval)

Standalone comparator function for sorting intervals (by start, then by end).

Reference implementation

ArrayIntervalCollection implements the same IntervalCollection interface as IntervalTree, backed by a plain array instead of a tree. Every operation is a straight O(n) scan — no balancing, no augmentation. Reach for it when you want an implementation that's obviously correct rather than fast: as the oracle in property-based tests, for small interval sets where O(n) is irrelevant, or as the executable spec a new IntervalCollection implementation can check itself against.

import { ArrayIntervalCollection } from 'intervaltree'

const tree = new ArrayIntervalCollection<string>()
tree.addInterval(1, 5, 'Meeting')

TypeScript Generics

The library now supports full TypeScript generics for type-safe interval data:

interface Task {
  id: number
  title: string
  priority: 'high' | 'medium' | 'low'
}

const schedule = new IntervalTree<Task>()
schedule.addInterval(9, 17, {
  id: 1,
  title: 'Work on project',
  priority: 'high'
})

// Full type safety - TypeScript knows the data type!
const tasks = schedule.searchPoint(12)
console.log(tasks[0].data?.title)  // Type-safe access

Works with fromTuples too:

const tree = IntervalTree.fromTuples<string>([
  [1, 5, 'Meeting'],
  [10, 15, 'Lunch'],
])

Iterator Support

Use for...of loops and other iterable features:

const tree = IntervalTree.fromTuples([
  [1, 5],
  [10, 15],
  [20, 25],
])

// Iterate with for...of
for (const interval of tree) {
  console.log(`${interval.start}-${interval.end}`)
}

// Use spread operator
const intervals = [...tree]

// Use Array.from
const array = Array.from(tree)

Boolean Checks

Convenient methods for membership checks:

const schedule = IntervalTree.fromTuples([
  [9, 17],   // 9am - 5pm
  [18, 20],  // 6pm - 8pm
])

// Check if a point is in any interval
schedule.contains(12)  // true (noon is during 9-17)
schedule.contains(17)  // false (end is exclusive)
schedule.contains(19)  // true

// Check if range overlaps with any interval
schedule.overlaps(8, 10)   // true
schedule.overlaps(17, 18)  // false

// Check if tree is empty
schedule.isEmpty  // false

Functional Operations

forEach

Execute a callback for each interval:

tree.forEach((interval, index) => {
  console.log(`${index}: ${interval.toString()}`)
})

map

Transform intervals and create a new tree:

const tree = IntervalTree.fromTuples<string>([
  [1, 5, 'task1'],
  [10, 15, 'task2'],
])

// Shift all intervals by 10 units
const shifted = tree.map(interval =>
  new Interval(
    interval.start + 10,
    interval.end + 10,
    interval.data
  )
)

// Result: [[11, 15, 'task1'], [20, 25, 'task2']]

You can even change the data type:

const withStrings = new IntervalTree<string>(...)
const withNumbers = withStrings.map(interval =>
  new Interval<number>(
    interval.start,
    interval.end,
    interval.data?.length ?? 0
  )
)

Set Operations

Combine and compare interval trees with set-like operations:

union

Combine interval records from two trees:

const schedule1 = IntervalTree.fromTuples([
  [9, 12],
  [14, 17],
])

const schedule2 = IntervalTree.fromTuples([
  [10, 11],
  [18, 20],
])

const combined = schedule1.union(schedule2)
// Contains all interval records from both trees.
// Overlapping ranges are not merged automatically.

Use rangeUnion() when you want mathematical union of ranges:

const combinedRanges = schedule1.rangeUnion(schedule2)
// Overlapping or adjacent ranges are merged.

intersection

Find overlapping regions between two trees:

const available = IntervalTree.fromTuples([
  [9, 17],   // 9am-5pm
  [18, 22],  // 6pm-10pm
])

const requested = IntervalTree.fromTuples([
  [10, 12],  // 10am-12pm
  [20, 23],  // 8pm-11pm
])

const conflicts = available.intersection(requested)
// Result: [[10, 12], [20, 22]]
// Only the overlapping time ranges

difference

Remove intervals from one tree that overlap with another:

const fullDay = IntervalTree.fromTuples([[0, 24]])  // Entire day

const meetings = IntervalTree.fromTuples([
  [9, 10],   // 9am meeting
  [14, 15],  // 2pm meeting
])

const freeTime = fullDay.difference(meetings)
// Result: [[0, 9], [10, 14], [15, 24]]
// Available time slots

Real-World Examples

Scheduling System

interface Meeting {
  title: string
  attendees: string[]
  room: string
}

const calendar = new IntervalTree<Meeting>()

calendar.addInterval(9, 10, {
  title: 'Daily Standup',
  attendees: ['Alice', 'Bob', 'Charlie'],
  room: 'Conference A'
})

calendar.addInterval(14, 15.5, {
  title: 'Code Review',
  attendees: ['Alice', 'David'],
  room: 'Conference B'
})

// Check if 11am is free
if (!calendar.contains(11)) {
  console.log('11am is available!')
}

// Find all afternoon meetings
const afternoon = calendar.searchOverlap(12, 18)
afternoon.forEach(interval => {
  console.log(interval.data?.title)
})

// Iterate through all meetings
for (const meeting of calendar) {
  console.log(`${meeting.data?.title} in ${meeting.data?.room}`)
}

Time Range Management

const workWeek = IntervalTree.fromTuples([
  [1, 6],  // Monday-Friday
])

const holidays = IntervalTree.fromTuples([
  [3, 4],  // Wednesday holiday
])

const workDays = workWeek.difference(holidays)
// Result: [[1, 3], [4, 6]]
// Monday-Tuesday and Thursday-Friday

Resource Allocation

const server1 = IntervalTree.fromTuples<string>([
  [0, 100, 'Job A'],
  [150, 300, 'Job B'],
])

const server2 = IntervalTree.fromTuples<string>([
  [50, 200, 'Job C'],
  [250, 350, 'Job D'],
])

// Find resource conflicts
const conflicts = server1.intersection(server2)
if (!conflicts.isEmpty) {
  console.log('Resource conflict detected!')
}

// Get all jobs across both servers
const allJobs = server1.union(server2)
for (const job of allJobs) {
  console.log(job.data)
}

Interval Semantics

This library uses half-open intervals [start, end) where:

• start is inclusive (inside the interval)
• end is exclusive (outside the interval)

Examples:

• Interval(1, 5) contains points 1, 2, 3, 4 (but not 5)
• interval.containsPoint(1) → true
• interval.containsPoint(5) → false
• interval.length → 4 (simply end - start, no +1 needed)

Why half-open intervals?

1. Length calculation: Just end - start (no off-by-one errors)
2. Adjacent intervals: [1, 5) and [5, 10) don't overlap
3. Empty intervals: [5, 5) is naturally empty
4. Consistency: Matches JavaScript conventions (Array.slice, substring, etc.)

This follows the recommendation from Edsger W. Dijkstra's 1982 note on interval notation and is used by most programming languages and CS literature.

Performance Notes

The tree is an augmented AVL tree built from plain objects. That layout is the right choice for read-heavy use at small to medium sizes.

We measured a flat typed-array layout (structure-of-arrays, and a single stride-8 Float64Array) against the shipped tree at 10,000 intervals with 50,000 queries. The flat layout wins on build, clone, and toArray. It loses on searchPoint and contains by 2 to 3x, and those are the calls most applications make.

operation	object tree	flat (best variant)
searchPoint	341 ns	781 ns
contains	303 ns	753 ns
build	155 ns	118 ns
clone	237 ns	77 ns

If you hold millions of intervals and mostly build, clone, or scan, the flat layout may be worth revisiting. The prototypes and benchmark scripts are preserved at the spike-flat-typed-array-tree tag under bench/spike/; the approach was measured and not adopted.