0
# IntervalTree
1

2
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.
3

4
## Package Information
5

6
- **Package Name**: intervaltree
7
- **Language**: Python
8
- **Installation**: `pip install intervaltree`
9
- **Dependencies**: `sortedcontainers >= 2.0, < 3.0`
10
- **Python Support**: 2.7, 3.5+
11

12
## Core Imports
13

14
```python
15
from intervaltree import Interval, IntervalTree
16
```
17

18
Alternative import pattern:
19

20
```python
21
import intervaltree
22
tree = intervaltree.IntervalTree()
23
interval = intervaltree.Interval(0, 10, "data")
24
```
25

26
## Basic Usage
27

28
```python
29
from intervaltree import Interval, IntervalTree
30

31
# Create an empty tree
32
tree = IntervalTree()
33

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

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

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

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

52
# Remove intervals
53
tree.remove(Interval(10, 20, "second interval"))
54
tree.remove_overlap(12, 18)  # Remove all overlapping intervals
55
```
56

57
## Architecture
58

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

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

66
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.
67

68
## Capabilities
69

70
### Interval Creation and Management
71

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

74
```python { .api }
75
class Interval:
76
    def __init__(self, begin, end, data=None): ...
77
    
78
    # Properties
79
    begin: Any  # Lower bound (inclusive)
80
    end: Any    # Upper bound (exclusive)  
81
    data: Any   # Optional data payload
82
```
83

84
[Intervals](./intervals.md)
85

86
### Tree Construction and Modification
87

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

90
```python { .api }
91
class IntervalTree:
92
    def __init__(self, intervals=None): ...
93
    def add(self, interval): ...
94
    def addi(self, begin, end, data=None): ...
95
    def remove(self, interval): ...
96
    def update(self, intervals): ...
97
    def clear(self): ...
98
```
99

100
[Tree Operations](./tree-operations.md)
101

102
### Query Operations
103

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

106
```python { .api }
107
def at(self, p): ...
108
def overlap(self, begin, end=None): ...
109
def envelop(self, begin, end=None): ...
110
def overlaps(self, begin, end=None): ...
111
def overlaps_point(self, p): ...
112
def overlaps_range(self, begin, end): ...
113
```
114

115
[Queries](./queries.md)
116

117
### Set Operations
118

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

121
```python { .api }
122
def union(self, other): ...
123
def intersection(self, other): ...
124
def difference(self, other): ...
125
def symmetric_difference(self, other): ...
126
```
127

128
[Set Operations](./set-operations.md)
129

130
### Bulk Modifications
131

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

134
```python { .api }
135
def remove_overlap(self, begin, end=None): ...
136
def remove_envelop(self, begin, end): ...
137
def chop(self, begin, end, datafunc=None): ...
138
def slice(self, point, datafunc=None): ...
139
def merge_overlaps(self, data_reducer=None, data_initializer=None, strict=True): ...
140
def split_overlaps(self): ...
141
```
142

143
[Bulk Operations](./bulk-operations.md)
144

145
### Python Integration
146

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

149
```python { .api }
150
def __getitem__(self, index): ...
151
def __setitem__(self, index, value): ...
152
def __contains__(self, item): ...
153
def __iter__(self): ...
154
def __len__(self): ...
155
```
156

157
[Python Integration](./python-integration.md)
158

159
## Types
160

161
```python { .api }
162
# Core types
163
class Interval:
164
    begin: Any
165
    end: Any  
166
    data: Any = None
167

168
class IntervalTree(MutableSet):
169
    # Inherits from collections.abc.MutableSet
170
    pass
171

172
# Common type aliases for documentation
173
IntervalLike = Union[Interval, Tuple[Any, Any], Tuple[Any, Any, Any]]
174
Point = Any  # Any comparable type
175
Range = Tuple[Any, Any]  # (begin, end) tuple
176
```