0
# Bulk Operations
1
2
Advanced operations for batch processing, interval manipulation, and tree restructuring. These operations enable efficient modification of multiple intervals simultaneously and provide powerful tools for interval-based data processing.
3
4
## Capabilities
5
6
### Bulk Removal Operations
7
8
Remove multiple intervals based on overlap criteria.
9
10
```python { .api }
11
def remove_overlap(self, begin, end=None):
12
"""
13
Remove all intervals overlapping with point or range.
14
15
Parameters:
16
- begin: Point, range start, or Interval object
17
- end: Range end (optional if begin is Interval or point query)
18
19
Time Complexity: O((r+m)*log n) where r is removed count, m is result size
20
"""
21
22
def remove_envelop(self, begin, end):
23
"""
24
Remove all intervals completely contained within range.
25
26
Parameters:
27
- begin: Range start
28
- end: Range end
29
30
Time Complexity: O((r+m)*log n) where r is removed count, m is result size
31
"""
32
```
33
34
### Interval Modification Operations
35
36
Modify intervals by chopping, slicing, and splitting.
37
38
```python { .api }
39
def chop(self, begin, end, datafunc=None):
40
"""
41
Remove portion [begin, end) from all intervals, splitting as needed.
42
43
Parameters:
44
- begin: Start of region to remove
45
- end: End of region to remove
46
- datafunc: Optional function to modify data of split intervals
47
Signature: datafunc(interval, is_left_part) -> new_data
48
49
Intervals overlapping [begin, end) are modified:
50
- Completely contained intervals are removed
51
- Partially overlapping intervals are trimmed or split
52
"""
53
54
def slice(self, point, datafunc=None):
55
"""
56
Split all intervals crossing point into two intervals.
57
58
Parameters:
59
- point: Point at which to split intervals
60
- datafunc: Optional function to modify data of split intervals
61
Signature: datafunc(interval, is_left_part) -> new_data
62
63
Each interval containing point becomes two intervals:
64
- Left part: [original_begin, point)
65
- Right part: [point, original_end)
66
"""
67
```
68
69
### Overlap Processing Operations
70
71
Detect and resolve overlapping intervals.
72
73
```python { .api }
74
def split_overlaps(self):
75
"""
76
Split all overlapping intervals at their boundary points.
77
78
After this operation, no two intervals will overlap - they will
79
either be disjoint or share exact boundaries.
80
81
Time Complexity: O(n²*log n) worst case, O(n*log n) best case
82
"""
83
84
def merge_overlaps(self, data_reducer=None, data_initializer=None, strict=True):
85
"""
86
Merge all overlapping intervals into single intervals.
87
88
Parameters:
89
- data_reducer: Function to combine data from merged intervals
90
Signature: data_reducer(current_data, new_data) -> combined_data
91
- data_initializer: Function to initialize data for merged intervals
92
Signature: data_initializer(intervals_list) -> initial_data
93
- strict: If True, merge only overlapping intervals
94
If False, also merge adjacent intervals
95
96
Time Complexity: O(n*log n)
97
"""
98
99
def merge_equals(self, data_reducer=None, data_initializer=None):
100
"""
101
Merge intervals with identical ranges (same begin and end).
102
103
Parameters:
104
- data_reducer: Function to combine data from merged intervals
105
- data_initializer: Function to initialize data for merged intervals
106
107
Time Complexity: O(n*log n)
108
"""
109
```
110
111
### Analysis Operations
112
113
Find complex interval relationships.
114
115
```python { .api }
116
def find_nested(self):
117
"""
118
Find nested interval relationships.
119
120
Returns:
121
dict: Mapping of parent intervals to sets of nested child intervals
122
{parent_interval: {child1, child2, ...}, ...}
123
124
Time Complexity: O(n²)
125
"""
126
```
127
128
## Usage Examples
129
130
### Bulk Removal
131
132
```python
133
from intervaltree import Interval, IntervalTree
134
135
# Create tree with overlapping intervals
136
tree = IntervalTree([
137
Interval(0, 10, "a"),
138
Interval(5, 15, "b"),
139
Interval(12, 18, "c"),
140
Interval(20, 30, "d"),
141
Interval(25, 35, "e")
142
])
143
144
print(f"Initial tree: {len(tree)} intervals")
145
146
# Remove all intervals that overlap with range [8, 22)
147
tree.remove_overlap(8, 22)
148
print(f"After remove_overlap(8, 22): {len(tree)} intervals")
149
# Removes intervals a, b, c, d (all overlap with [8, 22))
150
# Remaining: interval e (25, 35)
151
152
# Reset tree
153
tree = IntervalTree([
154
Interval(0, 10, "a"),
155
Interval(5, 15, "b"),
156
Interval(12, 18, "c"),
157
Interval(20, 30, "d")
158
])
159
160
# Remove only intervals completely contained within [6, 25)
161
tree.remove_envelop(6, 25)
162
print(f"After remove_envelop(6, 25): {len(tree)} intervals")
163
# Removes intervals c, d (completely within [6, 25))
164
# Remaining: intervals a, b (partially overlap but not completely contained)
165
```
166
167
### Chopping and Slicing
168
169
```python
170
from intervaltree import Interval, IntervalTree
171
172
# Create tree for chopping example
173
tree = IntervalTree([
174
Interval(0, 20, "long_interval"),
175
Interval(5, 15, "middle_interval"),
176
Interval(25, 35, "separate_interval")
177
])
178
179
# Chop out the region [8, 12) from all intervals
180
tree.chop(8, 12)
181
print(f"After chop(8, 12): {len(tree)} intervals")
182
# Original interval (0, 20) becomes two: (0, 8) and (12, 20)
183
# Interval (5, 15) becomes two: (5, 8) and (12, 15)
184
# Interval (25, 35) unchanged (no overlap with [8, 12))
185
186
# Reset for slicing example
187
tree = IntervalTree([
188
Interval(0, 20, "span_point"),
189
Interval(15, 25, "also_spans"),
190
Interval(30, 40, "no_span")
191
])
192
193
# Split all intervals that cross point 18
194
tree.slice(18)
195
print(f"After slice(18): {len(tree)} intervals")
196
# Interval (0, 20) becomes: (0, 18) and (18, 20)
197
# Interval (15, 25) becomes: (15, 18) and (18, 25)
198
# Interval (30, 40) unchanged (doesn't contain point 18)
199
```
200
201
### Data Modification During Operations
202
203
```python
204
from intervaltree import Interval, IntervalTree
205
206
# Example with data modification functions
207
def modify_chopped_data(interval, is_left_part):
208
"""Modify data when interval is split by chopping"""
209
original_data = interval.data
210
if is_left_part:
211
return f"{original_data}_left"
212
else:
213
return f"{original_data}_right"
214
215
def modify_sliced_data(interval, is_left_part):
216
"""Modify data when interval is split by slicing"""
217
original_data = interval.data
218
part = "before" if is_left_part else "after"
219
return f"{original_data}_{part}_split"
220
221
# Create tree
222
tree = IntervalTree([
223
Interval(0, 20, "original"),
224
Interval(10, 30, "another")
225
])
226
227
# Chop with data modification
228
tree.chop(8, 12, datafunc=modify_chopped_data)
229
# Results in intervals with modified data like "original_left", "original_right"
230
231
# Reset and slice with data modification
232
tree = IntervalTree([Interval(0, 20, "data")])
233
tree.slice(10, datafunc=modify_sliced_data)
234
# Results in "data_before_split" and "data_after_split"
235
```
236
237
### Merging Operations
238
239
```python
240
from intervaltree import Interval, IntervalTree
241
242
# Create tree with overlapping intervals
243
tree = IntervalTree([
244
Interval(0, 10, "a"),
245
Interval(5, 15, "b"),
246
Interval(12, 20, "c"),
247
Interval(25, 30, "d"),
248
Interval(28, 35, "e")
249
])
250
251
def combine_data(current, new):
252
"""Combine data from merged intervals"""
253
return f"{current}+{new}"
254
255
def initialize_data(intervals):
256
"""Initialize data for merged intervals"""
257
data_parts = [i.data for i in intervals]
258
return "+".join(sorted(data_parts))
259
260
print(f"Before merge: {len(tree)} intervals")
261
262
# Merge overlapping intervals
263
tree.merge_overlaps(data_reducer=combine_data, data_initializer=initialize_data)
264
print(f"After merge_overlaps: {len(tree)} intervals")
265
# Overlapping intervals (0,10), (5,15), (12,20) become one interval (0,20)
266
# Overlapping intervals (25,30), (28,35) become one interval (25,35)
267
268
# Example with equal intervals
269
tree = IntervalTree([
270
Interval(0, 10, "first"),
271
Interval(0, 10, "second"), # Same range
272
Interval(0, 10, "third"), # Same range
273
Interval(15, 25, "different")
274
])
275
276
print(f"Before merge_equals: {len(tree)} intervals")
277
tree.merge_equals(data_initializer=initialize_data)
278
print(f"After merge_equals: {len(tree)} intervals")
279
# Three intervals with range (0,10) become one with combined data
280
```
281
282
### Split Overlaps
283
284
```python
285
from intervaltree import Interval, IntervalTree
286
287
# Create tree with complex overlaps
288
tree = IntervalTree([
289
Interval(0, 15, "a"),
290
Interval(5, 20, "b"),
291
Interval(10, 25, "c"),
292
Interval(30, 40, "d")
293
])
294
295
print(f"Before split_overlaps: {len(tree)} intervals")
296
for interval in sorted(tree):
297
print(f" {interval}")
298
299
# Split all overlaps at boundary points
300
tree.split_overlaps()
301
302
print(f"After split_overlaps: {len(tree)} intervals")
303
for interval in sorted(tree):
304
print(f" {interval}")
305
306
# Result: intervals are split at points 5, 10, 15, 20 where boundaries cross
307
# No two intervals overlap anymore - they're either disjoint or adjacent
308
```
309
310
### Finding Nested Intervals
311
312
```python
313
from intervaltree import Interval, IntervalTree
314
315
# Create tree with nested structure
316
tree = IntervalTree([
317
Interval(0, 100, "outer"),
318
Interval(10, 30, "inner1"),
319
Interval(40, 60, "inner2"),
320
Interval(15, 25, "nested_in_inner1"),
321
Interval(70, 90, "another_inner"),
322
Interval(200, 300, "separate")
323
])
324
325
# Find nesting relationships
326
nested_map = tree.find_nested()
327
328
print("Nesting relationships:")
329
for parent, children in nested_map.items():
330
print(f"Parent {parent}:")
331
for child in children:
332
print(f" -> {child}")
333
334
# Output shows:
335
# - "outer" contains "inner1", "inner2", "nested_in_inner1", "another_inner"
336
# - "inner1" contains "nested_in_inner1"
337
# - "separate" has no nested intervals
338
```
339
340
### Complex Bulk Processing
341
342
```python
343
from intervaltree import Interval, IntervalTree
344
345
# Example: Processing time series data with gaps
346
data_tree = IntervalTree([
347
Interval(0, 100, "sensor_data_1"),
348
Interval(50, 150, "sensor_data_2"),
349
Interval(120, 200, "sensor_data_3"),
350
Interval(300, 400, "sensor_data_4")
351
])
352
353
# Step 1: Merge overlapping data segments
354
def combine_sensor_data(current, new):
355
return f"merged({current},{new})"
356
357
print("Original data segments:", len(data_tree))
358
data_tree.merge_overlaps(data_reducer=combine_sensor_data)
359
print("After merging overlaps:", len(data_tree))
360
361
# Step 2: Remove data during maintenance window [175, 225)
362
maintenance_start, maintenance_end = 175, 225
363
print(f"Removing data during maintenance [{maintenance_start}, {maintenance_end})")
364
data_tree.remove_overlap(maintenance_start, maintenance_end)
365
print("After maintenance removal:", len(data_tree))
366
367
# Step 3: Split remaining data at analysis boundary
368
analysis_point = 350
369
print(f"Splitting data at analysis point {analysis_point}")
370
data_tree.slice(analysis_point)
371
print("Final data segments:", len(data_tree))
372
373
for interval in sorted(data_tree):
374
print(f" Data segment: {interval}")
375
```