| single |
[![Build status badge][]][build status]
intervaltree
============
A mutable, self-balancing interval tree for Python 2 and 3. Queries may be
by point, by range overlap, or by range envelopment.
This library was designed to allow tagging text and time intervals, where
the intervals include the lower bound but not the upper bound.
**Version 3 changes!**
* The `search(begin, end, strict)` method no longer exists. Instead, use
one of these:
* `at(point)`
* `overlap(begin, end)`
* `envelop(begin, end)`
* The `extend(items)` method no longer exists. Instead, use
`update(items)`.
* Methods like `merge_overlaps()` which took a `strict` argument
consistently default to `strict=True`. Before, some methods defaulted to
`True` and others to `False`.
Installing
----------
`sh
pip install intervaltree
`
Features
--------
* Supports Python 2.7 and Python 3.5+ (Tested under 2.7, and 3.5 thru 3.14)
* Initializing
* blank `tree = IntervalTree()`
* from an iterable of `Interval` objects (`tree =
IntervalTree(intervals)`)
* from an iterable of tuples (`tree =
IntervalTree.from_tuples(interval_tuples)`)
* Insertions
* `tree[begin:end] = data`
* `tree.add(interval)`
* `tree.addi(begin, end, data)`
* Deletions
* `tree.remove(interval)` (raises `ValueError` if not
present)
* `tree.discard(interval)` (quiet if not present)
* `tree.removei(begin, end, data)` (short for
`tree.remove(Interval(begin, end, data))`)
* `tree.discardi(begin, end, data)` (short for
`tree.discard(Interval(begin, end, data))`)
* `tree.remove_overlap(point)`
* `tree.remove_overlap(begin, end)` (removes all overlapping the
range)
* `tree.remove_envelop(begin, end)` (removes all enveloped in the
range)
* Point queries
* `tree[point]`
* `tree.at(point)` (same as previous)
* Overlap queries
* `tree[begin:end]`
* `tree.overlap(begin, end)` (same as previous)
* Envelop queries
* `tree.envelop(begin, end)`
* Membership queries
* `interval_obj in tree` (this is fastest, O(1))
* `tree.containsi(begin, end, data)`
* `tree.overlaps(point)`
* `tree.overlaps(begin, end)`
* Iterable
* `for interval_obj in tree:`
* `tree.items()`
* Sizing
* `len(tree)`
* `tree.is_empty()`
* `not tree`
* `tree.begin()` (the `begin` coordinate of the leftmost
interval)
* `tree.end()` (the `end` coordinate of the rightmost
interval)
* Set-like operations
* union
* `result_tree = tree.union(iterable)`
* `result_tree = tree1 | tree2`
* `tree.update(iterable)`
* `tree |= other_tree`
* difference
* `result_tree = tree.difference(iterable)`
|