rangetree: easy range lookups

rangetree is an Apache2 licensed library, written in Python 3, for easy and fast lookups of numeric ranges.

Given three integer ranges, 0 - 9, 10 - 99, and 100 - 999, rangetree makes it trivial to look up exactly which range any integer falls in. (Note Python slices and ranges include the first index, and exclude the second.)

>>> from rangetree import RangeTree
>>>
>>> r = RangeTree()
>>> r[0:10] = 'single digits'
>>> r[10:100] = 'double digits'
>>> r[100:1000] = 'triple digits'
>>>
>>> r[4]
'single digits'

RangeTree s are optimized for lookups, and make use of the excellent bintrees library.

Features

• supports open and closed ranges
• supports integer keys
• optimized for lookups (not insertions)

Installation

To install rangetree, simply:

$ pip install rangetree

Usage

Insertion is done using Python's slice notation, or using range objects.

>>> r = RangeTree()
>>> r[0:10] = 'single digits'
>>> r[range(10, 100)] = 'double digits'

Negative integers are supported.

>>> r[-10:0] = 'negative singles'

Missing a range will result in a KeyError. Use Rangetree.get() or the in operator.

>>> 1000 in r
False
>>> r[1000]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "rangetree.py", line 93, in __getitem__
    raise KeyError(key)
KeyError: 1000
>>> r.get(1000, 'no value')
'no value'

Open ranges (that go to or from infinity) are supported. Setting open ranges is only possible using the slice notation.

>>> r[1000:] = 'quadruple digits or more'
>>> r[999999999]
'quadruple digits or more'

Overlapping ranges will result in a KeyError.

>>> r = RangeTree()
>>> r[1000:] = 'quadruple digits or more'
>>> r[10000:] = 'ten thousand'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "rangetree.py", line 58, in __setitem__
    raise KeyError('Overlapping intervals.')
KeyError: 'Overlapping intervals.'

rangetree is fast. Using perf, given 2000 intervals:

$ pyperf timeit --rigorous -g --duplicate 5 -s "from rangetree import RangeTree; r = RangeTree()" -s "for i in range(2000):" -s " r[i*10:i*10+10] = i" "r[500]"
.........................................
3.75 us:  1 #######
3.77 us:  2 #############
3.80 us:  9 ###########################################################
3.82 us:  5 #################################
3.84 us:  8 #####################################################
3.86 us:  9 ###########################################################
3.89 us:  7 ##############################################
3.91 us:  8 #####################################################
3.93 us:  8 #####################################################
3.95 us:  6 ########################################
3.98 us: 10 ##################################################################
4.00 us: 12 ###############################################################################
4.02 us:  5 #################################
4.05 us:  9 ###########################################################
4.07 us:  5 #################################
4.09 us:  6 ########################################
4.11 us:  3 ####################
4.14 us:  4 ##########################
4.16 us:  2 #############
4.18 us:  0 |
4.20 us:  1 #######

Median +- std dev: 3.97 us +- 0.11 us

The ballpark figure for lookups is in the single digit microseconds.

Changelog

1.0 (2016-10-20)

Initial public release.

Contributing

Contributions are very welcome. Tests can be run with tox, please ensure the coverage at least stays the same before you submit a pull request.

Credits

The development of rangetree is sponsored by Nanobit.

rangetree is tested with Hypothesis, by David R. MacIver.

rangetree is benchmarked using perf, by Victor Stinner.