or run

npx @tessl/cli init
Log in

Version

Tile

Overview

Evals

Files

docs

bulk-operations.mdindex.mdintervals.mdpython-integration.mdqueries.mdset-operations.mdtree-operations.md
tile.json

tessl/pypi-intervaltree

A mutable, self-balancing interval tree data structure that enables efficient querying of intervals by point, range overlap, or range envelopment

Workspace
tessl
Visibility
Public
Created
Last updated
Describes
pypipkg:pypi/intervaltree@3.1.x

To install, run

npx @tessl/cli install tessl/pypi-intervaltree@3.1.0

index.mddocs/

IntervalTree

A mutable, self-balancing interval tree data structure for Python 2 and 3. Queries may be by point, by range overlap, or by range envelopment. This library was designed to allow tagging text and time intervals, where intervals include the lower bound but not the upper bound.

Package Information

  • Package Name: intervaltree
  • Language: Python
  • Installation: pip install intervaltree
  • Dependencies: sortedcontainers >= 2.0, < 3.0
  • Python Support: 2.7, 3.5+

Core Imports

from intervaltree import Interval, IntervalTree

Alternative import pattern:

import intervaltree
tree = intervaltree.IntervalTree()
interval = intervaltree.Interval(0, 10, "data")

Basic Usage

from intervaltree import Interval, IntervalTree

# Create an empty tree
tree = IntervalTree()

# Add intervals using various methods
tree[0:5] = "first interval"
tree.add(Interval(10, 20, "second interval"))
tree.addi(15, 25, "third interval")

# Query for overlapping intervals
overlapping = tree[12]  # Point query
overlapping = tree[12:18]  # Range query
overlapping = tree.overlap(12, 18)  # Explicit overlap query

# Check if intervals exist
if tree.overlaps_point(12):
    print("Point 12 is covered by intervals")

# Iterate over all intervals
for interval in tree:
    print(f"Interval: {interval}")

# Remove intervals
tree.remove(Interval(10, 20, "second interval"))
tree.remove_overlap(12, 18)  # Remove all overlapping intervals

Architecture

The IntervalTree implements a self-balancing binary search tree (based on AVL tree principles) optimized for interval queries:

  • IntervalTree: Main container implementing MutableSet interface with O(log n) operations
  • Interval: Immutable namedtuple representing half-open intervals [begin, end) with optional data
  • Node: Internal tree structure (not part of public API) providing balancing and query optimization
  • SortedDict: Boundary table for efficient range queries using sortedcontainers library

This design provides guaranteed O(log n) performance for single-interval operations and O(m + k*log n) for result-dependent queries, where m is the result size and k is a complexity factor.

Capabilities

Interval Creation and Management

Basic interval construction, validation, and manipulation operations including creation from values or tuples, copying, and property access.

class Interval:
    def __init__(self, begin, end, data=None): ...
    
    # Properties
    begin: Any  # Lower bound (inclusive)
    end: Any    # Upper bound (exclusive)  
    data: Any   # Optional data payload

Intervals

Tree Construction and Modification

Core tree operations for creating, populating, and modifying interval trees including insertions, deletions, updates, and bulk operations.

class IntervalTree:
    def __init__(self, intervals=None): ...
    def add(self, interval): ...
    def addi(self, begin, end, data=None): ...
    def remove(self, interval): ...
    def update(self, intervals): ...
    def clear(self): ...

Tree Operations

Query Operations

Efficient searching and querying capabilities including point queries, range overlap detection, containment queries, and existence checks.

def at(self, p): ...
def overlap(self, begin, end=None): ...
def envelop(self, begin, end=None): ...
def overlaps(self, begin, end=None): ...
def overlaps_point(self, p): ...
def overlaps_range(self, begin, end): ...

Queries

Set Operations

Mathematical set operations for combining, comparing, and manipulating interval trees including union, intersection, difference, and symmetric difference.

def union(self, other): ...
def intersection(self, other): ...
def difference(self, other): ...
def symmetric_difference(self, other): ...

Set Operations

Bulk Modifications

Advanced operations for batch processing, interval manipulation, and tree restructuring including chopping, slicing, merging, and splitting.

def remove_overlap(self, begin, end=None): ...
def remove_envelop(self, begin, end): ...
def chop(self, begin, end, datafunc=None): ...
def slice(self, point, datafunc=None): ...
def merge_overlaps(self, data_reducer=None, data_initializer=None, strict=True): ...
def split_overlaps(self): ...

Bulk Operations

Python Integration

Native Python integration through magic methods enabling slice notation, iteration, membership testing, and standard container operations.

def __getitem__(self, index): ...
def __setitem__(self, index, value): ...
def __contains__(self, item): ...
def __iter__(self): ...
def __len__(self): ...

Python Integration

Types

# Core types
class Interval:
    begin: Any
    end: Any  
    data: Any = None

class IntervalTree(MutableSet):
    # Inherits from collections.abc.MutableSet
    pass

# Common type aliases for documentation
IntervalLike = Union[Interval, Tuple[Any, Any], Tuple[Any, Any, Any]]
Point = Any  # Any comparable type
Range = Tuple[Any, Any]  # (begin, end) tuple