IntervalTree

Common errors

• AttributeError: 'IntervalTree' object has no attribute 'search'

  cause Attempting to use the `search` method which was removed in version 3.0.0.
  fix Replace `tree.search(begin, end)` with `tree.overlap(begin, end)`. For point queries, use `tree.at(point)`.

• ModuleNotFoundError: No module named 'sortedcontainers'

  cause The `sortedcontainers` package, a required dependency, was not installed. This was a known packaging bug in version 3.2.0.
  fix Upgrade `intervaltree` to version 3.2.1 or higher (`pip install --upgrade intervaltree`). If on 3.2.0, you can manually install the dependency: `pip install sortedcontainers`.

• TypeError: 'int' object is not iterable

  cause This can happen if you pass multiple arguments to `tree.add()` or if you try to use `tree.extend()` (which was removed) expecting it to accept multiple `Interval` objects directly without an iterable.
  fix Ensure `tree.add()` is called with a single `Interval` object (e.g., `tree.add(Interval(1, 2))`). If adding multiple intervals, use `tree.update(iterable_of_intervals)`.

Warnings

• breaking Version 3.0.0 introduced significant API changes for querying methods. The `search(begin, end, strict)` method was removed and replaced by `at(point)`, `overlap(begin, end)`, and `envelop(begin, end)`. The `extend(items)` method was also replaced by `update(items)`.
  Fix: Migrate your code to use `tree.at(point)`, `tree.overlap(begin, end)`, `tree.envelop(begin, end)` for queries and `tree.update(items)` for adding multiple intervals.
• breaking The default behavior of `strict` arguments in methods was changed to consistently default to `True` in version 3.0.0. This might alter results for edge cases where interval boundaries are inclusive.
  Fix: Review existing calls to methods that previously implied `strict=False` or did not specify it, and explicitly set `strict=False` if the old inclusive boundary behavior is desired.
• gotcha Version 3.2.0 had a bug where the `sortedcontainers` dependency was missing from the wheel, leading to `ModuleNotFoundError` on installation or runtime.
  Fix: Upgrade to version 3.2.1 or newer, which fixed this packaging issue. Alternatively, manually install `pip install sortedcontainers`.
• breaking Support for Python 2.6, 3.2, and 3.3 was dropped in version 3.0.0. Support for Python 3.4 was dropped in 3.1.0.
  Fix: Ensure your project uses Python 2.7.18 (if on Python 2) or Python 3.5+ (preferably 3.8+) to be compatible with recent versions of `intervaltree`.

Install

• pip install intervaltree Install stable version

Imports

• IntervalTree
  wrong:

  import intervaltree; t = intervaltree.IntervalTree()

  correct:

  from intervaltree import IntervalTree

  While 'import intervaltree' works, direct import is idiomatic and clearer.
• Interval
  wrong:

  from intervaltree.interval import Interval

  correct:

  from intervaltree import Interval

  The Interval class is exposed directly under the top-level package.

Quickstart

This quickstart demonstrates how to create an IntervalTree, add intervals using both slice notation and explicit `Interval` objects, and perform common queries like finding intervals at a point, overlapping a range, or enveloping another range. It also shows how to remove an interval.

from intervaltree import Interval, IntervalTree

# Create an empty interval tree
tree = IntervalTree()

# Add intervals. You can assign data or just add the interval.
# Using slice notation for convenience (requires data assignment)
tree[0:10] = "first_interval"
tree[5:15] = "second_interval"

# Or add Interval objects explicitly
tree.add(Interval(12, 18, "third_interval"))

print(f"Tree size: {len(tree)}")

# Querying intervals
# Find all intervals overlapping a point
intervals_at_point = tree[7] # Using slice notation for point query
print(f"Intervals at point 7: {intervals_at_point}")

# Find all intervals overlapping a range
overlapping_intervals = tree.overlap(6, 13)
print(f"Intervals overlapping [6, 13): {overlapping_intervals}")

# Find all intervals that fully envelop another interval
enveloping_intervals = tree.envelop(4, 8)
print(f"Intervals enveloping [4, 8): {enveloping_intervals}")

# Remove an interval
interval_to_remove = Interval(0, 10, "first_interval")
tree.remove(interval_to_remove)
print(f"Tree size after removal: {len(tree)}")