0
# Queries
1
2
Efficient searching and querying capabilities for finding intervals based on point overlap, range overlap, or containment relationships. All query operations maintain the tree's performance guarantees.
3
4
## Capabilities
5
6
### Point Queries
7
8
Find intervals that contain or overlap with specific points.
9
10
```python { .api }
11
def at(self, p):
12
"""
13
Get all intervals containing point p.
14
15
Parameters:
16
- p: Point to query (any comparable type)
17
18
Returns:
19
set: Set of intervals where begin <= p < end
20
21
Time Complexity: O(m + log n) where m is result size
22
"""
23
24
def overlaps_point(self, p):
25
"""
26
Test if any interval contains point p.
27
28
Parameters:
29
- p: Point to test
30
31
Returns:
32
bool: True if any interval contains p
33
34
Time Complexity: O(log n)
35
"""
36
```
37
38
### Range Queries
39
40
Find intervals that overlap with or are contained within ranges.
41
42
```python { .api }
43
def overlap(self, begin, end=None):
44
"""
45
Get all intervals overlapping with range or interval.
46
47
Parameters:
48
- begin: Range start or Interval object
49
- end: Range end (optional if begin is Interval)
50
51
Returns:
52
set: Set of intervals that overlap with [begin, end)
53
54
Time Complexity: O(m + k*log n) where m is result size, k is complexity factor
55
"""
56
57
def envelop(self, begin, end=None):
58
"""
59
Get all intervals completely contained within range.
60
61
Parameters:
62
- begin: Range start or Interval object
63
- end: Range end (optional if begin is Interval)
64
65
Returns:
66
set: Set of intervals completely within [begin, end)
67
68
Time Complexity: O(m + k*log n) where m is result size, k is complexity factor
69
"""
70
71
def overlaps(self, begin, end=None):
72
"""
73
Test if any interval overlaps with range or point.
74
75
Parameters:
76
- begin: Range start, point, or Interval object
77
- end: Range end (optional)
78
79
Returns:
80
bool: True if any interval overlaps
81
82
Time Complexity: O(r*log n) where r is complexity factor
83
"""
84
85
def overlaps_range(self, begin, end):
86
"""
87
Test if any interval overlaps with range [begin, end).
88
89
Parameters:
90
- begin: Range start
91
- end: Range end
92
93
Returns:
94
bool: True if any interval overlaps with range
95
96
Time Complexity: O(r*log n) where r is complexity factor
97
"""
98
```
99
100
### Slice Notation Queries
101
102
Use Python slice notation for intuitive querying.
103
104
```python { .api }
105
def __getitem__(self, index):
106
"""
107
Query intervals using slice notation.
108
109
Parameters:
110
- index: Point (for point query) or slice object (for range query)
111
112
Returns:
113
set: Set of overlapping intervals
114
115
Usage:
116
- tree[point] -> intervals containing point
117
- tree[start:stop] -> intervals overlapping [start, stop)
118
119
Time Complexity: O(k*log(n) + m) where m is result size, k is complexity factor
120
"""
121
```
122
123
### Membership Testing
124
125
Test for exact interval presence in tree.
126
127
```python { .api }
128
def __contains__(self, item):
129
"""
130
Test if exact interval exists in tree.
131
132
Parameters:
133
- item: Interval object to test
134
135
Returns:
136
bool: True if exact interval (including data) exists in tree
137
138
Time Complexity: O(1)
139
"""
140
141
def containsi(self, begin, end, data=None):
142
"""
143
Test if interval with specific begin/end/data exists.
144
145
Parameters:
146
- begin: Lower bound
147
- end: Upper bound
148
- data: Data payload
149
150
Returns:
151
bool: True if exact interval exists in tree
152
153
Time Complexity: O(1)
154
"""
155
```
156
157
## Usage Examples
158
159
### Point Queries
160
161
```python
162
from intervaltree import Interval, IntervalTree
163
164
# Create tree with some intervals
165
tree = IntervalTree([
166
Interval(0, 10, "first"),
167
Interval(5, 15, "second"),
168
Interval(20, 30, "third")
169
])
170
171
# Find all intervals containing point 7
172
overlapping = tree.at(7)
173
print(overlapping) # {Interval(0, 10, 'first'), Interval(5, 15, 'second')}
174
175
# Using slice notation (equivalent to tree.at(7))
176
overlapping = tree[7]
177
print(overlapping) # Same result
178
179
# Test if any interval contains point
180
if tree.overlaps_point(7):
181
print("Point 7 is covered")
182
183
if tree.overlaps_point(50):
184
print("Point 50 is covered") # Won't print - no intervals contain 50
185
```
186
187
### Range Queries
188
189
```python
190
from intervaltree import Interval, IntervalTree
191
192
tree = IntervalTree([
193
Interval(0, 10, "first"),
194
Interval(5, 15, "second"),
195
Interval(12, 18, "third"),
196
Interval(20, 30, "fourth")
197
])
198
199
# Find intervals overlapping with range [8, 14)
200
overlapping = tree.overlap(8, 14)
201
print(overlapping) # {Interval(0, 10, 'first'), Interval(5, 15, 'second'), Interval(12, 18, 'third')}
202
203
# Using slice notation (equivalent)
204
overlapping = tree[8:14]
205
print(overlapping) # Same result
206
207
# Find intervals completely contained within [6, 16)
208
contained = tree.envelop(6, 16)
209
print(contained) # {Interval(12, 18, 'third')} - only this one is fully contained
210
211
# Test if any interval overlaps with range
212
if tree.overlaps(8, 14):
213
print("Range [8, 14) has overlapping intervals")
214
215
if tree.overlaps_range(25, 35):
216
print("Range [25, 35) has overlapping intervals")
217
```
218
219
### Interval-based Queries
220
221
```python
222
from intervaltree import Interval, IntervalTree
223
224
tree = IntervalTree([
225
Interval(0, 10, "first"),
226
Interval(15, 25, "second"),
227
Interval(30, 40, "third")
228
])
229
230
# Query using another interval
231
query_interval = Interval(5, 20)
232
233
# Find overlapping intervals
234
overlapping = tree.overlap(query_interval)
235
print(overlapping) # {Interval(0, 10, 'first'), Interval(15, 25, 'second')}
236
237
# Find contained intervals
238
contained = tree.envelop(query_interval)
239
print(contained) # set() - no intervals fully contained in [5, 20)
240
241
# Test overlap with interval
242
if tree.overlaps(query_interval):
243
print("Query interval overlaps with tree intervals")
244
```
245
246
### Membership Testing
247
248
```python
249
from intervaltree import Interval, IntervalTree
250
251
tree = IntervalTree([
252
Interval(0, 10, "data1"),
253
Interval(15, 25, "data2")
254
])
255
256
# Test for exact interval presence
257
test_interval = Interval(0, 10, "data1")
258
if test_interval in tree:
259
print("Exact interval found")
260
261
# Test with different data (won't match)
262
test_interval2 = Interval(0, 10, "different_data")
263
if test_interval2 not in tree:
264
print("Interval with different data not found")
265
266
# Test using values
267
if tree.containsi(0, 10, "data1"):
268
print("Interval (0, 10, 'data1') exists")
269
270
if not tree.containsi(0, 10, "data3"):
271
print("Interval (0, 10, 'data3') does not exist")
272
```
273
274
### Complex Query Patterns
275
276
```python
277
from intervaltree import Interval, IntervalTree
278
279
# Create tree with overlapping intervals
280
tree = IntervalTree([
281
Interval(0, 20, "big_interval"),
282
Interval(5, 10, "small1"),
283
Interval(12, 15, "small2"),
284
Interval(25, 35, "separate")
285
])
286
287
# Find all intervals that might affect processing in range [8, 16)
288
affected = tree.overlap(8, 16)
289
print(f"Intervals affected by range [8, 16): {len(affected)}")
290
291
# Find intervals completely within a processing window
292
window_start, window_end = 3, 18
293
contained = tree.envelop(window_start, window_end)
294
print(f"Intervals fully contained in window: {len(contained)}")
295
296
# Check if a point is in a "gap" (not covered by any interval)
297
test_point = 22
298
if not tree.overlaps_point(test_point):
299
print(f"Point {test_point} is in a gap")
300
301
# Find all intervals that would be partially processed
302
all_overlapping = tree.overlap(8, 16)
303
fully_contained = tree.envelop(8, 16)
304
partially_overlapping = all_overlapping - fully_contained
305
print(f"Partially overlapping intervals: {len(partially_overlapping)}")
306
```