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