0
# Set Operations
1

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

4
## Capabilities
5

6
### Union Operations
7

8
Combine intervals from multiple trees.
9

10
```python { .api }
11
def union(self, other):
12
    """
13
    Create new tree containing all intervals from both trees.
14
    
15
    Parameters:
16
    - other: IntervalTree to union with
17
    
18
    Returns:
19
    IntervalTree: New tree with intervals from both self and other
20
    
21
    Note: Duplicate intervals (same begin, end, data) appear only once
22
    """
23
```
24

25
### Intersection Operations
26

27
Find common intervals between trees.
28

29
```python { .api }
30
def intersection(self, other):
31
    """
32
    Create new tree containing intervals common to both trees.
33
    
34
    Parameters:
35
    - other: IntervalTree to intersect with
36
    
37
    Returns:
38
    IntervalTree: New tree with intervals present in both trees
39
    
40
    Note: Intervals must match exactly (begin, end, and data)
41
    """
42

43
def intersection_update(self, other):
44
    """
45
    Modify tree to contain only intervals also present in other tree.
46
    
47
    Parameters:
48
    - other: IntervalTree to intersect with
49
    
50
    Modifies tree in-place, removing intervals not in other
51
    """
52
```
53

54
### Difference Operations
55

56
Find intervals present in one tree but not another.
57

58
```python { .api }
59
def difference(self, other):
60
    """
61
    Create new tree with intervals in self but not in other.
62
    
63
    Parameters:
64
    - other: IntervalTree to subtract
65
    
66
    Returns:
67
    IntervalTree: New tree with intervals from self minus those in other
68
    """
69

70
def difference_update(self, other):
71
    """
72
    Remove all intervals in other from this tree.
73
    
74
    Parameters:
75
    - other: IntervalTree containing intervals to remove
76
    
77
    Modifies tree in-place, removing intervals present in other
78
    """
79
```
80

81
### Symmetric Difference Operations
82

83
Find intervals present in either tree but not both.
84

85
```python { .api }
86
def symmetric_difference(self, other):
87
    """
88
    Create new tree with intervals in either tree but not both.
89
    
90
    Parameters:
91
    - other: IntervalTree to compare with
92
    
93
    Returns:
94
    IntervalTree: New tree with intervals unique to each tree
95
    """
96

97
def symmetric_difference_update(self, other):
98
    """
99
    Update tree to contain intervals in either tree but not both.
100
    
101
    Parameters:  
102
    - other: IntervalTree to compare with
103
    
104
    Modifies tree in-place to symmetric difference
105
    """
106
```
107

108
### Equality Testing
109

110
Compare trees for equality.
111

112
```python { .api }
113
def __eq__(self, other):
114
    """
115
    Test if two trees contain exactly the same intervals.
116
    
117
    Parameters:
118
    - other: IntervalTree to compare with
119
    
120
    Returns:
121
    bool: True if trees contain identical intervals
122
    
123
    Time Complexity: O(n) if sizes equal, O(1) otherwise
124
    """
125
```
126

127
## Usage Examples
128

129
### Basic Set Operations
130

131
```python
132
from intervaltree import Interval, IntervalTree
133

134
# Create two trees with some overlapping intervals
135
tree1 = IntervalTree([
136
    Interval(0, 10, "a"),
137
    Interval(15, 25, "b"), 
138
    Interval(30, 40, "c")
139
])
140

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

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

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

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

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

168
### In-Place Set Operations
169

170
```python
171
from intervaltree import Interval, IntervalTree
172

173
# Create trees
174
tree1 = IntervalTree([
175
    Interval(0, 10, "keep"),
176
    Interval(15, 25, "common"),
177
    Interval(30, 40, "remove")
178
])
179

180
tree2 = IntervalTree([
181
    Interval(15, 25, "common"),
182
    Interval(50, 60, "new")
183
])
184

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

191
# Reset tree1
192
tree1 = IntervalTree([
193
    Interval(0, 10, "keep"),
194
    Interval(15, 25, "common"),
195
    Interval(30, 40, "remove")
196
])
197

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

203
# Reset and test symmetric difference update
204
tree1 = IntervalTree([
205
    Interval(0, 10, "unique1"),
206
    Interval(15, 25, "common")
207
])
208

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

214
### Equality and Comparison
215

216
```python
217
from intervaltree import Interval, IntervalTree
218

219
# Create identical trees
220
tree1 = IntervalTree([
221
    Interval(0, 10, "a"),
222
    Interval(15, 25, "b")
223
])
224

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

230
tree3 = IntervalTree([
231
    Interval(0, 10, "a"),
232
    Interval(15, 25, "different_data")  # Different data
233
])
234

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

239
# Empty trees
240
empty1 = IntervalTree()
241
empty2 = IntervalTree()
242
print(empty1 == empty2)  # True - both empty
243
```
244

245
### Complex Set Operations
246

247
```python
248
from intervaltree import Interval, IntervalTree
249

250
# Example: Managing time slots for scheduling
251
scheduled = IntervalTree([
252
    Interval(9, 10, "meeting_a"),
253
    Interval(14, 15, "meeting_b"),
254
    Interval(16, 17, "meeting_c")
255
])
256

257
proposed = IntervalTree([
258
    Interval(9, 10, "meeting_a"),    # Already scheduled
259
    Interval(11, 12, "meeting_d"),   # New proposal
260
    Interval(15, 16, "meeting_e"),   # New proposal
261
    Interval(17, 18, "meeting_f")    # New proposal
262
])
263

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

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

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

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

280
### Working with Multiple Trees
281

282
```python
283
from intervaltree import Interval, IntervalTree
284

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

291
source_b = IntervalTree([
292
    Interval(50, 150, "data_b_1"),
293
    Interval(200, 300, "data_a_2")  # Duplicate
294
])
295

296
source_c = IntervalTree([
297
    Interval(100, 200, "data_c_1"),
298
    Interval(350, 450, "data_c_2")
299
])
300

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

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

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