1Metadata-Version: 2.1
2Name: intervaltree
3Version: 3.1.0
4Summary: Editable interval tree data structure for Python 2 and 3
5Home-page: https://github.com/chaimleib/intervaltree
6Author: Chaim Leib Halbert, Konstantin Tretyakov
7Author-email: chaim.leib.halbert@gmail.com
8License: Apache License, Version 2.0
9Download-URL: https://github.com/chaimleib/intervaltree/tarball/3.1.0
10Description: [![Build status badge][]][build status]
11
12        intervaltree
13        ============
14
15        A mutable, self-balancing interval tree for Python 2 and 3. Queries may be by point, by range overlap, or by range envelopment.
16
17        This library was designed to allow tagging text and time intervals, where the intervals include the lower bound but not the upper bound.
18
19        **Version 3 changes!**
20
21        * The `search(begin, end, strict)` method no longer exists. Instead, use one of these:
22            * `at(point)`
23            * `overlap(begin, end)`
24            * `envelop(begin, end)`
25        * The `extend(items)` method no longer exists. Instead, use `update(items)`.
26        * Methods like `merge_overlaps()` which took a `strict` argument consistently default to `strict=True`. Before, some methods defaulted to `True` and others to `False`.
27
28        Installing
29        ----------
30
31        ```sh
32        pip install intervaltree
33        ```
34
35        Features
36        --------
37
38        * Supports Python 2.7 and Python 3.5+ (Tested under 2.7, and 3.5 thru 3.8)
39        * Initializing
40            * blank `tree = IntervalTree()`
41            * from an iterable of `Interval` objects (`tree = IntervalTree(intervals)`)
42            * from an iterable of tuples (`tree = IntervalTree.from_tuples(interval_tuples)`)
43
44        * Insertions
45            * `tree[begin:end] = data`
46            * `tree.add(interval)`
47            * `tree.addi(begin, end, data)`
48
49        * Deletions
50            * `tree.remove(interval)`             (raises `ValueError` if not present)
51            * `tree.discard(interval)`            (quiet if not present)
52            * `tree.removei(begin, end, data)`    (short for `tree.remove(Interval(begin, end, data))`)
53            * `tree.discardi(begin, end, data)`   (short for `tree.discard(Interval(begin, end, data))`)
54            * `tree.remove_overlap(point)`
55            * `tree.remove_overlap(begin, end)`   (removes all overlapping the range)
56            * `tree.remove_envelop(begin, end)`   (removes all enveloped in the range)
57
58        * Point queries
59            * `tree[point]`
60            * `tree.at(point)`                    (same as previous)
61
62        * Overlap queries
63            * `tree[begin:end]`
64            * `tree.overlap(begin, end)`          (same as previous)
65
66        * Envelop queries
67            * `tree.envelop(begin, end)`
68
69        * Membership queries
70            * `interval_obj in tree`              (this is fastest, O(1))
71            * `tree.containsi(begin, end, data)`
72            * `tree.overlaps(point)`
73            * `tree.overlaps(begin, end)`
74
75        * Iterable
76            * `for interval_obj in tree:`
77            * `tree.items()`
78
79        * Sizing
80            * `len(tree)`
81            * `tree.is_empty()`
82            * `not tree`
83            * `tree.begin()`          (the `begin` coordinate of the leftmost interval)
84            * `tree.end()`            (the `end` coordinate of the rightmost interval)
85
86        * Set-like operations
87            * union
88                * `result_tree = tree.union(iterable)`
89                * `result_tree = tree1 | tree2`
90                * `tree.update(iterable)`
91                * `tree |= other_tree`
92
93            * difference
94                * `result_tree = tree.difference(iterable)`
95                * `result_tree = tree1 - tree2`
96                * `tree.difference_update(iterable)`
97                * `tree -= other_tree`
98
99            * intersection
100                * `result_tree = tree.intersection(iterable)`
101                * `result_tree = tree1 & tree2`
102                * `tree.intersection_update(iterable)`
103                * `tree &= other_tree`
104
105            * symmetric difference
106                * `result_tree = tree.symmetric_difference(iterable)`
107                * `result_tree = tree1 ^ tree2`
108                * `tree.symmetric_difference_update(iterable)`
109                * `tree ^= other_tree`
110
111            * comparison
112                * `tree1.issubset(tree2)` or `tree1 <= tree2`
113                * `tree1 <= tree2`
114                * `tree1.issuperset(tree2)` or `tree1 > tree2`
115                * `tree1 >= tree2`
116                * `tree1 == tree2`
117
118        * Restructuring
119            * `chop(begin, end)`      (slice intervals and remove everything between `begin` and `end`, optionally modifying the data fields of the chopped-up intervals)
120            * `slice(point)`          (slice intervals at `point`)
121            * `split_overlaps()`      (slice at all interval boundaries, optionally modifying the data field)
122            * `merge_overlaps()` (joins overlapping intervals into a single interval, optionally merging the data fields)
123            * `merge_equals()` (joins intervals with matching ranges into a single interval, optionally merging the data fields)
124
125        * Copying and typecasting
126            * `IntervalTree(tree)`    (`Interval` objects are same as those in tree)
127            * `tree.copy()`           (`Interval` objects are shallow copies of those in tree)
128            * `set(tree)`             (can later be fed into `IntervalTree()`)
129            * `list(tree)`            (ditto)
130
131        * Pickle-friendly
132        * Automatic AVL balancing
133
134        Examples
135        --------
136
137        * Getting started
138
139            ``` python
140            >>> from intervaltree import Interval, IntervalTree
141            >>> t = IntervalTree()
142            >>> t
143            IntervalTree()
144
145            ```
146
147        * Adding intervals - any object works!
148
149            ``` python
150            >>> t[1:2] = "1-2"
151            >>> t[4:7] = (4, 7)
152            >>> t[5:9] = {5: 9}
153
154            ```
155
156        * Query by point
157
158            The result of a query is a `set` object, so if ordering is important,
159            you must sort it first.
160
161            ``` python
162            >>> sorted(t[6])
163            [Interval(4, 7, (4, 7)), Interval(5, 9, {5: 9})]
164            >>> sorted(t[6])[0]
165            Interval(4, 7, (4, 7))
166
167            ```
168
169        * Query by range
170
171            Note that ranges are inclusive of the lower limit, but non-inclusive of the upper limit. So:
172
173            ``` python
174            >>> sorted(t[2:4])
175            []
176
177            ```
178
179            Since our search was over `2 ≤ x < 4`, neither `Interval(1, 2)` nor `Interval(4, 7)`
180            was included. The first interval, `1 ≤ x < 2` does not include `x = 2`. The second
181            interval, `4 ≤ x < 7`, does include `x = 4`, but our search interval excludes it. So,
182            there were no overlapping intervals. However:
183
184            ``` python
185            >>> sorted(t[1:5])
186            [Interval(1, 2, '1-2'), Interval(4, 7, (4, 7))]
187
188            ```
189
190            To only return intervals that are completely enveloped by the search range:
191
192            ``` python
193            >>> sorted(t.envelop(1, 5))
194            [Interval(1, 2, '1-2')]
195
196            ```
197
198        * Accessing an `Interval` object
199
200            ``` python
201            >>> iv = Interval(4, 7, (4, 7))
202            >>> iv.begin
203            4
204            >>> iv.end
205            7
206            >>> iv.data
207            (4, 7)
208
209            >>> begin, end, data = iv
210            >>> begin
211            4
212            >>> end
213            7
214            >>> data
215            (4, 7)
216
217            ```
218
219        * Constructing from lists of intervals
220
221            We could have made a similar tree this way:
222
223            ``` python
224            >>> ivs = [(1, 2), (4, 7), (5, 9)]
225            >>> t = IntervalTree(
226            ...    Interval(begin, end, "%d-%d" % (begin, end)) for begin, end in ivs
227            ... )
228
229            ```
230
231            Or, if we don't need the data fields:
232
233            ``` python
234            >>> t2 = IntervalTree(Interval(*iv) for iv in ivs)
235
236            ```
237
238            Or even:
239
240            ``` python
241            >>> t2 = IntervalTree.from_tuples(ivs)
242
243            ```
244
245        * Removing intervals
246
247            ``` python
248            >>> t.remove(Interval(1, 2, "1-2"))
249            >>> sorted(t)
250            [Interval(4, 7, '4-7'), Interval(5, 9, '5-9')]
251
252            >>> t.remove(Interval(500, 1000, "Doesn't exist"))  # raises ValueError
253            Traceback (most recent call last):
254            ValueError
255
256            >>> t.discard(Interval(500, 1000, "Doesn't exist"))  # quietly does nothing
257
258            >>> del t[5]  # same as t.remove_overlap(5)
259            >>> t
260            IntervalTree()
261
262            ```
263
264            We could also empty a tree entirely:
265
266            ``` python
267            >>> t2.clear()
268            >>> t2
269            IntervalTree()
270
271            ```
272
273            Or remove intervals that overlap a range:
274
275            ``` python
276            >>> t = IntervalTree([
277            ...     Interval(0, 10),
278            ...     Interval(10, 20),
279            ...     Interval(20, 30),
280            ...     Interval(30, 40)])
281            >>> t.remove_overlap(25, 35)
282            >>> sorted(t)
283            [Interval(0, 10), Interval(10, 20)]
284
285            ```
286
287            We can also remove only those intervals completely enveloped in a range:
288
289            ``` python
290            >>> t.remove_envelop(5, 20)
291            >>> sorted(t)
292            [Interval(0, 10)]
293
294            ```
295
296        * Chopping
297
298            We could also chop out parts of the tree:
299
300            ``` python
301            >>> t = IntervalTree([Interval(0, 10)])
302            >>> t.chop(3, 7)
303            >>> sorted(t)
304            [Interval(0, 3), Interval(7, 10)]
305
306            ```
307
308            To modify the new intervals' data fields based on which side of the interval is being chopped:
309
310            ``` python
311            >>> def datafunc(iv, islower):
312            ...     oldlimit = iv[islower]
313            ...     return "oldlimit: {0}, islower: {1}".format(oldlimit, islower)
314            >>> t = IntervalTree([Interval(0, 10)])
315            >>> t.chop(3, 7, datafunc)
316            >>> sorted(t)[0]
317            Interval(0, 3, 'oldlimit: 10, islower: True')
318            >>> sorted(t)[1]
319            Interval(7, 10, 'oldlimit: 0, islower: False')
320
321            ```
322
323        * Slicing
324
325            You can also slice intervals in the tree without removing them:
326
327            ``` python
328            >>> t = IntervalTree([Interval(0, 10), Interval(5, 15)])
329            >>> t.slice(3)
330            >>> sorted(t)
331            [Interval(0, 3), Interval(3, 10), Interval(5, 15)]
332
333            ```
334
335            You can also set the data fields, for example, re-using `datafunc()` from above:
336
337            ``` python
338            >>> t = IntervalTree([Interval(5, 15)])
339            >>> t.slice(10, datafunc)
340            >>> sorted(t)[0]
341            Interval(5, 10, 'oldlimit: 15, islower: True')
342            >>> sorted(t)[1]
343            Interval(10, 15, 'oldlimit: 5, islower: False')
344
345            ```
346
347        Future improvements
348        -------------------
349
350        See the [issue tracker][] on GitHub.
351
352        Based on
353        --------
354
355        * Eternally Confuzzled's [AVL tree][Confuzzled AVL tree]
356        * Wikipedia's [Interval Tree][Wiki intervaltree]
357        * Heavily modified from Tyler Kahn's [Interval Tree implementation in Python][Kahn intervaltree] ([GitHub project][Kahn intervaltree GH])
358        * Incorporates contributions from:
359            * [konstantint/Konstantin Tretyakov][Konstantin intervaltree] of the University of Tartu (Estonia)
360            * [siniG/Avi Gabay][siniG intervaltree]
361            * [lmcarril/Luis M. Carril][lmcarril intervaltree] of the Karlsruhe Institute for Technology (Germany)
362            * [depristo/MarkDePristo][depristo intervaltree]
363
364        Copyright
365        ---------
366
367        * [Chaim Leib Halbert][GH], 2013-2020
368        * Modifications, [Konstantin Tretyakov][Konstantin intervaltree], 2014
369
370        Licensed under the [Apache License, version 2.0][Apache].
371
372        The source code for this project is at https://github.com/chaimleib/intervaltree
373
374
375        [build status badge]: https://travis-ci.org/chaimleib/intervaltree.svg?branch=master
376        [build status]: https://travis-ci.org/chaimleib/intervaltree
377        [GH]: https://github.com/chaimleib/intervaltree
378        [issue tracker]: https://github.com/chaimleib/intervaltree/issues
379        [Konstantin intervaltree]: https://github.com/konstantint/PyIntervalTree
380        [siniG intervaltree]: https://github.com/siniG/intervaltree
381        [lmcarril intervaltree]: https://github.com/lmcarril/intervaltree
382        [depristo intervaltree]: https://github.com/depristo/intervaltree
383        [Confuzzled AVL tree]: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
384        [Wiki intervaltree]: http://en.wikipedia.org/wiki/Interval_tree
385        [Kahn intervaltree]: http://zurb.com/forrst/posts/Interval_Tree_implementation_in_python-e0K
386        [Kahn intervaltree GH]: https://github.com/tylerkahn/intervaltree-python
387        [Apache]: http://www.apache.org/licenses/LICENSE-2.0
388
389Keywords: interval-tree data-structure intervals tree
390Platform: UNKNOWN
391Classifier: Development Status :: 5 - Production/Stable
392Classifier: Programming Language :: Python :: Implementation :: PyPy
393Classifier: Intended Audience :: Developers
394Classifier: Intended Audience :: Information Technology
395Classifier: Intended Audience :: Science/Research
396Classifier: Programming Language :: Python
397Classifier: Programming Language :: Python :: 2
398Classifier: Programming Language :: Python :: 2.7
399Classifier: Programming Language :: Python :: 3
400Classifier: Programming Language :: Python :: 3.5
401Classifier: Programming Language :: Python :: 3.6
402Classifier: Programming Language :: Python :: 3.7
403Classifier: Programming Language :: Python :: 3.8
404Classifier: License :: OSI Approved :: Apache Software License
405Classifier: Topic :: Scientific/Engineering :: Artificial Intelligence
406Classifier: Topic :: Scientific/Engineering :: Bio-Informatics
407Classifier: Topic :: Scientific/Engineering :: Information Analysis
408Classifier: Topic :: Software Development :: Libraries
409Classifier: Topic :: Text Processing :: General
410Classifier: Topic :: Text Processing :: Linguistic
411Classifier: Topic :: Text Processing :: Markup
412Description-Content-Type: text/markdown
413