tessl/pypi-intervaltree
A mutable, self-balancing interval tree data structure that enables efficient querying of intervals by point, range overlap, or range envelopment
—
Pending
tree-operations.mddocs/
Tree Operations
Core operations for creating, populating, and modifying interval trees. These operations maintain the tree's self-balancing properties and provide efficient O(log n) performance for most single-interval operations.
Capabilities
Construction
Create interval trees from various sources.
class IntervalTree:
def __init__(self, intervals=None):
"""
Initialize interval tree.
Parameters:
- intervals: Optional iterable of Interval objects to populate tree
Time Complexity: O(n*log n) if intervals provided, O(1) if empty
"""
@classmethod
def from_tuples(cls, tups):
"""
Create tree from iterable of tuples.
Parameters:
- tups: Iterable of 2-tuples (begin, end) or 3-tuples (begin, end, data)
Returns:
IntervalTree: New tree containing intervals from tuples
Time Complexity: O(n*log n)
"""Adding Intervals
Insert individual intervals or batches of intervals.
def add(self, interval):
"""
Add interval to tree if not already present.
Parameters:
- interval: Interval object to add
Time Complexity: O(log n)
"""
def append(self, interval):
"""Alias for add()."""
def addi(self, begin, end, data=None):
"""
Add interval by begin/end values.
Parameters:
- begin: Lower bound (inclusive)
- end: Upper bound (exclusive)
- data: Optional data payload
Time Complexity: O(log n)
"""
def appendi(self, begin, end, data=None):
"""Alias for addi()."""
def update(self, intervals):
"""
Add multiple intervals from iterable.
Parameters:
- intervals: Iterable of Interval objects
Time Complexity: O(m*log(n+m)) where m is number of intervals to add
"""Removing Intervals
Remove individual intervals or clear the entire tree.
def remove(self, interval):
"""
Remove interval from tree.
Parameters:
- interval: Interval object to remove
Raises:
ValueError: If interval not present in tree
Time Complexity: O(log n)
"""
def removei(self, begin, end, data=None):
"""
Remove interval by begin/end/data values.
Parameters:
- begin: Lower bound
- end: Upper bound
- data: Data payload (must match exactly)
Raises:
ValueError: If interval not present in tree
Time Complexity: O(log n)
"""
def discard(self, interval):
"""
Remove interval if present, otherwise do nothing.
Parameters:
- interval: Interval object to remove
Time Complexity: O(log n)
"""
def discardi(self, begin, end, data=None):
"""
Remove interval by values if present.
Parameters:
- begin: Lower bound
- end: Upper bound
- data: Data payload
Time Complexity: O(log n)
"""
def clear(self):
"""
Remove all intervals from tree.
Time Complexity: O(1)
"""Tree Information
Access tree properties and statistics.
def __len__(self):
"""
Get number of intervals in tree.
Returns:
int: Number of intervals
Time Complexity: O(1)
"""
def is_empty(self):
"""
Test if tree contains no intervals.
Returns:
bool: True if tree is empty
Time Complexity: O(1)
"""
def begin(self):
"""
Get earliest begin value in tree.
Returns:
Any: Minimum begin value across all intervals
Raises:
ValueError: If tree is empty
Time Complexity: O(1)
"""
def end(self):
"""
Get latest end value in tree.
Returns:
Any: Maximum end value across all intervals
Raises:
ValueError: If tree is empty
Time Complexity: O(1)
"""
def range(self):
"""
Get minimum-spanning interval containing all intervals.
Returns:
Interval: Interval from earliest begin to latest end
Raises:
ValueError: If tree is empty
"""
def span(self):
"""
Get length of minimum-spanning interval.
Returns:
Number: Length from earliest begin to latest end
Raises:
ValueError: If tree is empty
"""Tree Access
Retrieve intervals and iterate over tree contents.
def items(self):
"""
Get all intervals as a set.
Returns:
set: Set containing all intervals in tree
Time Complexity: O(n)
"""
def __iter__(self):
"""
Iterate over all intervals in tree.
Returns:
iterator: Iterator over intervals in sorted order
Time Complexity: O(1) to create iterator, O(n) to consume
"""
def iter(self):
"""Alias for __iter__()."""
def copy(self):
"""
Create shallow copy of tree.
Returns:
IntervalTree: New tree with same intervals
Time Complexity: O(n*log n)
"""Tree Validation and Debugging
Methods for debugging and verifying tree integrity.
def verify(self):
"""
Verify tree invariants for debugging.
Raises:
AssertionError: If tree structure is invalid
"""
def print_structure(self, tostring=False):
"""
Pretty-print tree structure for debugging.
Parameters:
- tostring: If True, return as string instead of printing
Returns:
str or None: Tree structure representation
"""
def score(self, full_report=False):
"""
Calculate tree optimization score.
Parameters:
- full_report: If True, return detailed scoring information
Returns:
float or dict: Score from 0-1 (lower is better) or detailed report
"""Usage Examples
Basic Tree Operations
from intervaltree import Interval, IntervalTree
# Create empty tree
tree = IntervalTree()
# Add intervals using different methods
tree.add(Interval(0, 10, "first"))
tree.addi(15, 25, "second")
tree[30:40] = "third" # Using slice notation
# Create tree from existing intervals
intervals = [Interval(0, 5), Interval(10, 15), Interval(20, 25)]
tree2 = IntervalTree(intervals)
# Create from tuples
tree3 = IntervalTree.from_tuples([(0, 5, "a"), (10, 15, "b")])
print(f"Tree has {len(tree)} intervals")
print(f"Tree spans from {tree.begin()} to {tree.end()}")Modification Operations
from intervaltree import Interval, IntervalTree
tree = IntervalTree()
tree.update([Interval(0, 10), Interval(15, 25), Interval(30, 40)])
# Remove specific interval
tree.remove(Interval(15, 25))
# Safe removal (won't raise error if not present)
tree.discard(Interval(100, 200))
# Remove by values
tree.removei(30, 40)
# Batch addition
new_intervals = [Interval(5, 15), Interval(20, 30)]
tree.update(new_intervals)
# Clear all intervals
tree.clear()
print(f"After clear: {tree.is_empty()}") # TrueTree Copying and Inspection
from intervaltree import Interval, IntervalTree
# Create and populate tree
original = IntervalTree([Interval(i, i+5) for i in range(0, 50, 10)])
# Create shallow copy
copy_tree = original.copy()
# Get all intervals
all_intervals = original.items() # Returns set
interval_list = list(original) # Convert iterator to list
# Tree statistics
print(f"Tree contains {len(original)} intervals")
print(f"Spans from {original.begin()} to {original.end()}")
print(f"Total span length: {original.span()}")
# Debug information
original.verify() # Check tree invariants
score = original.score() # Get optimization score
print(f"Tree optimization score: {score}")Install with Tessl CLI
npx tessl i tessl/pypi-intervaltree