Metadata-Version: 2.4
Name: fastintervaltree
Version: 0.1.0
Summary: Drop-in subclass of intervaltree's IntervalTree with range queries done in one walk of the tree
Author: Ramcharan
License-Expression: Apache-2.0
Project-URL: Homepage, https://github.com/p-ramcharan-dev/fastintervaltree
Project-URL: Source, https://github.com/p-ramcharan-dev/fastintervaltree
Project-URL: Issues, https://github.com/p-ramcharan-dev/fastintervaltree/issues
Project-URL: Changelog, https://github.com/p-ramcharan-dev/fastintervaltree/blob/main/CHANGELOG.md
Project-URL: Original library, https://github.com/chaimleib/intervaltree
Keywords: intervaltree,interval tree,interval,range query,overlap,performance
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Operating System :: OS Independent
Classifier: Topic :: Software Development :: Libraries
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
License-File: NOTICE
Requires-Dist: intervaltree<3.3,>=3.2.1
Provides-Extra: test
Requires-Dist: pytest; extra == "test"
Requires-Dist: hypothesis; extra == "test"
Dynamic: license-file

# fastintervaltree

[![PyPI](https://img.shields.io/pypi/v/fastintervaltree)](https://pypi.org/project/fastintervaltree/)
[![ci](https://github.com/p-ramcharan-dev/fastintervaltree/actions/workflows/ci.yml/badge.svg)](https://github.com/p-ramcharan-dev/fastintervaltree/actions/workflows/ci.yml)
![License: Apache-2.0](https://img.shields.io/badge/license-Apache--2.0-blue)

A drop-in subclass of [intervaltree](https://github.com/chaimleib/intervaltree)'s `IntervalTree` whose range
queries walk the tree once. It returns the same sets as intervaltree 3.2.1, and is pure Python.

```python
# before
from intervaltree import Interval, IntervalTree
# after: nothing else changes
from fastintervaltree import Interval, IntervalTree
```

Status: version 0.1.0, working and tested. The `overlap` and
`envelop` change has also been offered to intervaltree itself as
[pull request #166](https://github.com/chaimleib/intervaltree/pull/166); if that is merged and released,
most of the reason for this package goes away.

## Why

intervaltree answers `overlap(begin, end)` with one point search for `begin` and then one more for every
interval boundary inside the range. On a tree of 12,000 intervals a query that returns 71 of them takes
about 1.4 ms. Users have reported this on intervaltree's tracker
([#120](https://github.com/chaimleib/intervaltree/issues/120),
[#127](https://github.com/chaimleib/intervaltree/issues/127)). `envelop` works the same way, and `overlaps`
with a range scans the whole table of boundaries when the answer is not found at once.

Here each of these is a single descent that skips a subtree the range cannot reach. The tree, its nodes and
every operation that changes the tree are intervaltree's own code, inherited unchanged.

## Numbers

Microseconds per query, intervaltree 3.2.1 against this package on identical trees, random integer
intervals. Python 3.13.5, Windows, one laptop; process pinned, 5 rounds with the two variants alternating,
best round of each. Full output: [results/bench_queries.txt](https://github.com/p-ramcharan-dev/fastintervaltree/blob/main/results/bench_queries.txt).

| Tree | Query width | Hits per query | `overlap` | `envelop` | `overlaps` (yes/no) |
|---|---|---|---|---|---|
| 12,000 intervals, length up to 2,000 | 5,000 | 71 | 1,383 → 12.5 (111x) | 1,390 → 14.0 (99x) | 10.5 → 3.3 (3.2x) |
| 100,000 intervals, length up to 2,000 | 5,000 | 59 | 1,540 → 19.1 (81x) | 1,572 → 18.9 (83x) | 14.3 → 5.8 (2.5x) |
| same tree | 100,000 | 1,013 | 30,640 → 119 (257x) | 31,879 → 378 (84x) | 14.1 → 2.7 (5.2x) |
| 100,000 intervals, length up to 200,000 | 5,000 | 1,027 | 69,981 → 654 (107x) | 61,706 → 1.3 | 277 → 134 (2.1x) |
| 450,000 intervals, length up to 400 | 5,000 | 52 | 896 → 17.4 (51x) | 939 → 22.7 (42x) | 2,973 → 4.1 (723x) |
| 450,000 short intervals with gaps | 200 | 0.2 | 12.5 → 4.2 (3.0x) | 11.6 → 1.6 (7.1x) | 57,613 → 2.2 |
| 12,000 intervals with endpoints in 0..63 | 8 | 4,686 | 33,516 → 5,074 (6.6x) | 32,832 → 1,839 (18x) | 13.9 → 5.3 (2.6x) |

How to read it:

- **The gain grows with the number of boundaries inside the query range.** Narrow queries on sparse trees
  gain about 3x; wide ones gain 50x to 250x.
- **Rows where the original took tens of milliseconds were timed on few queries** (5 to 20 per round), so
  those ratios are rough. Two cells have no ratio because it would mislead: the `envelop` that drops from
  62 ms to 1.3 us returns 0.6 intervals per query, and the `overlaps` that drops from 58 ms to 2.2 us is
  the case where the original scans all of the roughly 900,000 boundaries.
- **The last row is the shape reported in issue #120, and it gains least.** See "What is not faster".
- Point queries (`at`, `tree[p]`) are 1.0x to 1.5x. Building a tree and `add` cost 0% to 5% more than the
  original in two runs, which is within this machine's noise.

`remove_overlap`, `remove_envelop`, `chop` and `tree[a:b]` call these queries and get faster with them.
They were not timed separately.

## What is not faster

- **Many intervals with the same range.** `Interval.__hash__` uses only `begin` and `end`, so intervals that
  share a range and differ in `data` all land in one hash bucket, and every set that holds k of them costs
  on the order of k squared comparisons. With 1,000 such intervals one `at` took 129 ms in the original;
  with 5,000 it took 3.0 s. This package does not change that
  ([#126](https://github.com/chaimleib/intervaltree/issues/126)), and it is why the 0..63 row above gains
  only 6.6x. `Interval` is intervaltree's own class here, so its hash cannot be changed without breaking
  equality with intervals made elsewhere.
- **Building, `add`, `remove`, `merge_*`, `split_overlaps` and the set operations** are intervaltree's code.
  `split_overlaps` on 100,000 sparse intervals took 29.7 s in one profiling run
  ([results/profile_ops.txt](https://github.com/p-ramcharan-dev/fastintervaltree/blob/main/results/profile_ops.txt)).

## Differences from intervaltree

Results are equal sets of the same `Interval` objects. Three things differ:

1. **Iteration order of a result set** from `overlap` and `envelop` can differ, because hits are found in a
   different order. `at` keeps the original's order. Since `remove_overlap(begin, end)`, `remove_envelop`
   and `chop` remove hits in iteration order, the internal layout of the tree afterwards can differ from
   what intervaltree would have built. Its contents, and the answers to every query, do not.
2. **`copy`, `union`, `difference`, `intersection`, `symmetric_difference`, `from_tuples` and unpickling
   return this package's `IntervalTree`.** In intervaltree 3.2.1 a subclass gets plain `IntervalTree`s back
   from these; its development branch has already changed that.
3. **NaN.** If a query endpoint or any endpoint in the tree is NaN, the call is passed to intervaltree's own
   code, so the answer is whatever intervaltree gives.

Endpoints are assumed to be totally ordered apart from NaN. Types with a partial order (sets, for example)
are not supported and not tested.

## Evidence

- **Parity tests** ([tests/test_parity.py](https://github.com/p-ramcharan-dev/fastintervaltree/blob/main/tests/test_parity.py)): every query at every pair of points
  against intervaltree, with int, float (including infinities and -0.0), `Fraction`, `str` and `datetime`
  endpoints; trees built at once and one interval at a time; and again after every step of random sequences
  drawn from 28 operations. Exception types are compared as well as results. Hypothesis generates the
  cases.
- **The fast path is the code under test** ([tests/test_fast_path.py](https://github.com/p-ramcharan-dev/fastintervaltree/blob/main/tests/test_fast_path.py)): a counter
  on intervaltree's two search routines reads zero for ordinary trees, and non-zero when NaN forces the
  fallback.
- **Mutation check** ([tools/mutation_check.py](https://github.com/p-ramcharan-dev/fastintervaltree/blob/main/tools/mutation_check.py)): 37 deliberate one-line
  breakages; the tests catch 33. The other 4 cannot change any answer, and the reasons are printed in
  [results/mutation_check.txt](https://github.com/p-ramcharan-dev/fastintervaltree/blob/main/results/mutation_check.txt).
- **intervaltree's own test suite** at tag 3.2.1 passes with this class swapped in
  ([tools/swap_in_fast.py](https://github.com/p-ramcharan-dev/fastintervaltree/blob/main/tools/swap_in_fast.py)): 99 tests, the same count as without the swap.

CI runs the tests on Linux, Windows and macOS with Python 3.10, 3.13 and 3.15, and on Linux with Python 3.9,
always against intervaltree 3.2.1. Python 3.11 was run once by hand.

## Install

```
pip install fastintervaltree
```

It needs Python 3.9 or newer and installs `intervaltree` 3.2.x as a dependency.

To run the checks, from a clone:

```
pip install -e ".[test]"
python -m pytest                      # about 2 minutes
python tools/mutation_check.py        # several minutes, 6 processes
python research/bench_queries.py      # a few minutes; needs a quiet machine
```

## Licence

Apache-2.0, the same as intervaltree, from which this is derived. See [NOTICE](https://github.com/p-ramcharan-dev/fastintervaltree/blob/main/NOTICE).
Written with the help of an AI coding assistant (Claude Code).
