skip to navigation
skip to content

rangetree 1.0

Quick lookups of values in numeric ranges.

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.

 
File Type Py Version Uploaded on Size
rangetree-1.0-py3-none-any.whl (md5) Python Wheel 3.5 2016-11-16 6KB