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

Overview

Eval results

Files

Set Operations

Name: tessl/pypi-intervaltree
Author: tessl

Mathematical set operations for combining, comparing, and manipulating interval trees. These operations treat interval trees as sets of intervals and provide standard set theory operations with modifications to support the updating variants.

Capabilities

Union Operations

Combine intervals from multiple trees.

def union(self, other):
    """
    Create new tree containing all intervals from both trees.
    
    Parameters:
    - other: IntervalTree to union with
    
    Returns:
    IntervalTree: New tree with intervals from both self and other
    
    Note: Duplicate intervals (same begin, end, data) appear only once
    """

Intersection Operations

Find common intervals between trees.

def intersection(self, other):
    """
    Create new tree containing intervals common to both trees.
    
    Parameters:
    - other: IntervalTree to intersect with
    
    Returns:
    IntervalTree: New tree with intervals present in both trees
    
    Note: Intervals must match exactly (begin, end, and data)
    """

def intersection_update(self, other):
    """
    Modify tree to contain only intervals also present in other tree.
    
    Parameters:
    - other: IntervalTree to intersect with
    
    Modifies tree in-place, removing intervals not in other
    """

Difference Operations

Find intervals present in one tree but not another.

def difference(self, other):
    """
    Create new tree with intervals in self but not in other.
    
    Parameters:
    - other: IntervalTree to subtract
    
    Returns:
    IntervalTree: New tree with intervals from self minus those in other
    """

def difference_update(self, other):
    """
    Remove all intervals in other from this tree.
    
    Parameters:
    - other: IntervalTree containing intervals to remove
    
    Modifies tree in-place, removing intervals present in other
    """

Symmetric Difference Operations

Find intervals present in either tree but not both.

def symmetric_difference(self, other):
    """
    Create new tree with intervals in either tree but not both.
    
    Parameters:
    - other: IntervalTree to compare with
    
    Returns:
    IntervalTree: New tree with intervals unique to each tree
    """

def symmetric_difference_update(self, other):
    """
    Update tree to contain intervals in either tree but not both.
    
    Parameters:  
    - other: IntervalTree to compare with
    
    Modifies tree in-place to symmetric difference
    """

Equality Testing

Compare trees for equality.

def __eq__(self, other):
    """
    Test if two trees contain exactly the same intervals.
    
    Parameters:
    - other: IntervalTree to compare with
    
    Returns:
    bool: True if trees contain identical intervals
    
    Time Complexity: O(n) if sizes equal, O(1) otherwise
    """

Usage Examples

Basic Set Operations

from intervaltree import Interval, IntervalTree

# Create two trees with some overlapping intervals
tree1 = IntervalTree([
    Interval(0, 10, "a"),
    Interval(15, 25, "b"), 
    Interval(30, 40, "c")
])

tree2 = IntervalTree([
    Interval(15, 25, "b"),  # Same as in tree1
    Interval(20, 30, "d"),  # Different
    Interval(45, 55, "e")   # Different
])

# Union - all intervals from both trees
union_tree = tree1.union(tree2)
print(f"Union contains {len(union_tree)} intervals")
# Contains: (0,10,"a"), (15,25,"b"), (30,40,"c"), (20,30,"d"), (45,55,"e")

# Intersection - only intervals in both trees
intersection_tree = tree1.intersection(tree2)
print(f"Intersection contains {len(intersection_tree)} intervals")
# Contains: (15,25,"b")

# Difference - intervals in tree1 but not tree2
difference_tree = tree1.difference(tree2)
print(f"Difference contains {len(difference_tree)} intervals")
# Contains: (0,10,"a"), (30,40,"c")

# Symmetric difference - intervals in either but not both
sym_diff_tree = tree1.symmetric_difference(tree2)
print(f"Symmetric difference contains {len(sym_diff_tree)} intervals")
# Contains: (0,10,"a"), (30,40,"c"), (20,30,"d"), (45,55,"e")

In-Place Set Operations

from intervaltree import Interval, IntervalTree

# Create trees
tree1 = IntervalTree([
    Interval(0, 10, "keep"),
    Interval(15, 25, "common"),
    Interval(30, 40, "remove")
])

tree2 = IntervalTree([
    Interval(15, 25, "common"),
    Interval(50, 60, "new")
])

# Modify tree1 in-place to keep only common intervals
original_size = len(tree1)
tree1.intersection_update(tree2)
print(f"Reduced from {original_size} to {len(tree1)} intervals")
# tree1 now contains only: (15,25,"common")

# Reset tree1
tree1 = IntervalTree([
    Interval(0, 10, "keep"),
    Interval(15, 25, "common"),
    Interval(30, 40, "remove")
])

# Remove intervals that are in tree2
tree1.difference_update(tree2)
print(f"After difference_update: {len(tree1)} intervals")
# tree1 now contains: (0,10,"keep"), (30,40,"remove")

# Reset and test symmetric difference update
tree1 = IntervalTree([
    Interval(0, 10, "unique1"),
    Interval(15, 25, "common")
])

tree1.symmetric_difference_update(tree2)
print(f"After symmetric_difference_update: {len(tree1)} intervals")
# tree1 now contains: (0,10,"unique1"), (50,60,"new")

Equality and Comparison

from intervaltree import Interval, IntervalTree

# Create identical trees
tree1 = IntervalTree([
    Interval(0, 10, "a"),
    Interval(15, 25, "b")
])

tree2 = IntervalTree([
    Interval(15, 25, "b"),  # Order doesn't matter
    Interval(0, 10, "a")
])

tree3 = IntervalTree([
    Interval(0, 10, "a"),
    Interval(15, 25, "different_data")  # Different data
])

# Test equality
print(tree1 == tree2)  # True - same intervals, order doesn't matter
print(tree1 == tree3)  # False - different data in second interval

# Empty trees
empty1 = IntervalTree()
empty2 = IntervalTree()
print(empty1 == empty2)  # True - both empty

Complex Set Operations

from intervaltree import Interval, IntervalTree

# Example: Managing time slots for scheduling
scheduled = IntervalTree([
    Interval(9, 10, "meeting_a"),
    Interval(14, 15, "meeting_b"),
    Interval(16, 17, "meeting_c")
])

proposed = IntervalTree([
    Interval(9, 10, "meeting_a"),    # Already scheduled
    Interval(11, 12, "meeting_d"),   # New proposal
    Interval(15, 16, "meeting_e"),   # New proposal
    Interval(17, 18, "meeting_f")    # New proposal
])

# Find meetings that are already scheduled
already_scheduled = scheduled.intersection(proposed)
print(f"Already scheduled: {len(already_scheduled)} meetings")

# Find new meeting proposals
new_proposals = proposed.difference(scheduled)
print(f"New proposals: {len(new_proposals)} meetings")

# Create combined schedule
all_meetings = scheduled.union(proposed)
print(f"Total meetings: {len(all_meetings)}")

# Find conflicts by checking if any intervals overlap (would need additional logic)
# This is a simple example - real conflict detection would need overlap checking

Working with Multiple Trees

from intervaltree import Interval, IntervalTree

# Example: Combining data from multiple sources
source_a = IntervalTree([
    Interval(0, 100, "data_a_1"),
    Interval(200, 300, "data_a_2")
])

source_b = IntervalTree([
    Interval(50, 150, "data_b_1"),
    Interval(200, 300, "data_a_2")  # Duplicate
])

source_c = IntervalTree([
    Interval(100, 200, "data_c_1"),
    Interval(350, 450, "data_c_2")
])

# Combine all sources
combined = source_a.union(source_b).union(source_c)
print(f"Combined data from 3 sources: {len(combined)} intervals")

# Find data unique to source_a
unique_to_a = source_a.difference(source_b).difference(source_c)
print(f"Unique to source A: {len(unique_to_a)} intervals")

# Find data common to all sources (if any)
common_ab = source_a.intersection(source_b)
common_all = common_ab.intersection(source_c)
print(f"Common to all sources: {len(common_all)} intervals")

Install with Tessl CLI