fast, simple interval intersection
Project description
Description
Quicksect is a fast python / cython implementation of interval search based on the pure python version in bx-python I pulled it out, optimized and converted to cython and James Taylor has incoporated it back into bx-python with his improvements.
I have brought this project back from the dead because I want a fast, simple, no-dependencies Interval tree.
Extended with removal operations and allows pretty print to display tree structure (By Jianlin)
License is MIT.
Installation
pip install quicksectx
Use
To use extended quicksect(quicksectx):
>>> from quicksectx import IntervalNode, IntervalTree, Interval >>> tree = IntervalTree() >>> tree.add(1, 3, 100) >>> tree.add(3, 7, 110) >>> tree.add(2, 5, 120) >>> tree.add(4, 6, 130) >>> print(tree.pretty_print()) Inv(1, 3, d=100) r: Inv(3, 7, d=110) l: Inv(2, 5, d=120) r: Inv(4, 6, d=130) >>> print(tree.find(Interval(2, 5))) [Inv(1, 3, d=100), Inv(3, 7, d=110), Inv(2, 5, d=120), Inv(4, 6, d=130)] >>> tree.remove(Interval(2, 5)) >>> print(tree.find(Interval(2, 5))) [Inv(1, 3, d=100), Inv(3, 7, d=110), Inv(4, 6, d=130)]
To use traditional quicksect, you can still using the same syntax:
>>> from quicksect import IntervalNode, Interval, IntervalTree
Most common use will be via IntervalTree:
>>> tree = IntervalTree() >>> tree.add(23, 45) >>> tree.add(55, 66) >>> tree.search(46, 47) [] >>> tree.search(44, 56) [Interval(55, 66), Interval(23, 45)]>>> tree.insert(Interval(88, 444)) >>> res = tree.find(Interval(99, 100)) >>> res [Interval(88, 444)] >>> res[0].start, res[0].end (88, 444)
Thats pretty much everything you need to know about the tree.
Test
$ python setup.py test
Low-Level
In some cases, users may want to utilize the lower-level interface that accesses the nodes of the tree:
>>> inter = IntervalNode(Interval(22, 33)) >>> inter = inter.insert(Interval(44, 55)) >>> inter.intersect(24, 26) [Interval(22, 33)]>>> inter.left(Interval(34, 35), n=1) [Interval(22, 33)]>>> inter.right(Interval(34, 35), n=1) [Interval(44, 55)]
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for quicksectx-0.3.1b1-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f1fabe7626dd8710be0c6138da9cea3f5d41cbb718008ed4d5d8730d1c3da6dd |
|
MD5 | ef51f8a5e1f391b592c00afdd05b3f20 |
|
BLAKE2b-256 | ef0c45e8bc8fa857f7f13b101df3ae74f24438134118847531ff1b6eb02412f4 |
Hashes for quicksectx-0.3.1b1-cp310-cp310-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d24399ed1487c2c63212dcc5502b6764aacadbd0d4d5fd11eba98ebdc76f836d |
|
MD5 | 6fc51e5f5aefcfea36b1fa6fed3f9f77 |
|
BLAKE2b-256 | 96791145fe8eec27a69929ca4a7df3f395af8959020f13a5691f516a18a23190 |
Hashes for quicksectx-0.3.1b1-cp310-cp310-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a49d08dd8ee0bbbb7b7e7ae8e74fc14afcacfc04558375b7823cc08d20691a2f |
|
MD5 | 14c0551fd324b60cc5ee84a0b96c7c4a |
|
BLAKE2b-256 | cfa5dc0d4d714684391841b04b51e42e15d7303e854e6801553dc42ebb175f66 |
Hashes for quicksectx-0.3.1b1-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0b616517710c0af9ead822917fd9b023f283c73524bff566e7c7d1f497cdfa9c |
|
MD5 | 5ea9c4dde012b9c612c8cab1485a8b22 |
|
BLAKE2b-256 | 63fe8df22353f330e0867552920d2a6cbbc32dcb892155948b7ab1ea69810dc8 |
Hashes for quicksectx-0.3.1b1-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bb45ddbb328422cf7afe70b2f69e36607c43e1c00f7ade0bf5f635a888ea6939 |
|
MD5 | 41bb600e8f7a9a06e5d7485664df5470 |
|
BLAKE2b-256 | 216c6220ca0f04aceb4213d6df1c7bea0446ac4e105d655a1bcf9330a9e16535 |
Hashes for quicksectx-0.3.1b1-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 570f863fb276ae39f77e6a925008b630fe1417ae929c09d04d96d79f2aea2d34 |
|
MD5 | 9da7ae54344e01144cd0f8b09aa4279e |
|
BLAKE2b-256 | e7f678ff52134ff41bc7ac60042ad8b4472d257039072ba9f835205e483d0155 |
Hashes for quicksectx-0.3.1b1-cp39-cp39-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b9fdaf3a49e7430cbb3d6c7303dffa3e61d4016f3772e7c56f12f6a75bdd9951 |
|
MD5 | 1229931f8966c79265279f6bdcdb4cfe |
|
BLAKE2b-256 | 0e37c837443458134ee2a5fce71e4da03cfd9b69c01128dd743575f133aef893 |
Hashes for quicksectx-0.3.1b1-cp39-cp39-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9bc222aceb704818cb3b24394309a82dfe520803300b173e25384a1957d8dfb9 |
|
MD5 | 66e15c1d1652c93ea72503dc32860d1e |
|
BLAKE2b-256 | 645514d533c4d24a2066b053de24a2bd5793f28fe1ad0a10af2c86ded47f5ee4 |
Hashes for quicksectx-0.3.1b1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 114f3153ec0d15aa73b081afaf3b8a3c10cc9d50729d5a64cc751fd78fcea7c2 |
|
MD5 | 265ae81176ce5271513c4cbfe19db91f |
|
BLAKE2b-256 | c07bfc7be839a05fe9ba47e168664e4449c658295a3faa6ed2ac2b904e6708cf |
Hashes for quicksectx-0.3.1b1-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 60668028471a18314c59dd30ad2ccba937c41dea28d51a670706a01e25c10255 |
|
MD5 | aacfd1983ecdea38c54bd9eb0d637777 |
|
BLAKE2b-256 | a5f8955d32665a0677bbb38a7e162b3cd823deb7cce524df458644fcdac8e722 |
Hashes for quicksectx-0.3.1b1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2033350a5e23cf13517203a390396965fe524d60a6f1240a6a02894ae8d14a46 |
|
MD5 | 3f7c4bba557c3a40fb042e44dc908bf2 |
|
BLAKE2b-256 | ad933c9ca2f7ae47cba822c0224f9d2088cca2a129813d43a5715b4dd6b0e726 |
Hashes for quicksectx-0.3.1b1-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c80784caa68a6c213db8809fa1eafbf8deb870e8b5e4494d97ecadd78e9cb5e2 |
|
MD5 | 77837224a4afb62371c7b3a7e8c25362 |
|
BLAKE2b-256 | 698e5559a90a9a26e225b2528508d8b7854cf1c977456ee23a75659ee45b99b7 |
Hashes for quicksectx-0.3.1b1-cp38-cp38-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3e408cb47aa380f14d2a7425a97eff2c1b0572fbaf6aa3f262c587641b51f859 |
|
MD5 | 4fd362b5a81d0c974df04b08854664be |
|
BLAKE2b-256 | 98c40114fc84d5c330331cc9ebd02fbc981f9248c46997f84004b9248ed49b58 |
Hashes for quicksectx-0.3.1b1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3f3a88cdf934d1436cc66525a576e0c28fdeda032bfa0d7cb49afc50671d4e3d |
|
MD5 | bc7584a233dd7183983d9b29405ad326 |
|
BLAKE2b-256 | cd0fdb7245137cbfdf9cc1bdb760ae4656ce557f4cc3da43c0eb4924746d9ece |
Hashes for quicksectx-0.3.1b1-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 17f181152392873ac15084734aa1af89d592c78e2957ad1c265b3f110ac3c6e1 |
|
MD5 | b3c85bcca9823e7816dc0c607d97d40b |
|
BLAKE2b-256 | 70b20f9eaf5a18216ffd1f108b0f47fd4f02abba1a6abe48a4477ce999bb3040 |
Hashes for quicksectx-0.3.1b1-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b809a128ee1dc795059a936938ed7b30637c9432cc18ede22adb6e9a96f15a04 |
|
MD5 | 226ce0f59c188c00accecaa6e0b48363 |
|
BLAKE2b-256 | cb710830a86412b6def12aaf5e527f0a0cbe02a82d61ef7cb1c16c9d96e856eb |
Hashes for quicksectx-0.3.1b1-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 030ab703e0e4de5902e11a218b0c157da6a3b62a737eb70fea76e96dec2084e7 |
|
MD5 | 6498700bfde6dadcd08e0212954f1a3b |
|
BLAKE2b-256 | d9c8e9e01d53299ceddca4ac616fdce37a717f3119c4427ee86d554e666825c3 |
Hashes for quicksectx-0.3.1b1-cp37-cp37m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5d2e0a76454bb36b65bff622ef8cfc640bd6987c91a9a4114026d5ccf6ef78ed |
|
MD5 | e0e63429482b5643fa5f30bf4f978aae |
|
BLAKE2b-256 | c4f15472a539b9331198efd87add25077aedc71dc2919865c2dfcac979e8dd21 |
Hashes for quicksectx-0.3.1b1-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 10c45ab14b43550666401033841de182b4423981b35256e337977a458f28b09c |
|
MD5 | 691b49b56ca51ef722e05efd0fa7ca01 |
|
BLAKE2b-256 | 449e9aa4958831578a7f064b98a0cb70b07e96e3e154d46c6381f48b5001554c |
Hashes for quicksectx-0.3.1b1-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 610ab4130486329b3015f3b9fdf70284a94671310a727d45053a811cc57c9468 |
|
MD5 | ad6cb1966dfac6944466ddb5d254bad3 |
|
BLAKE2b-256 | 536df497de20aa6e550a9853fc950b8bbbe375d90dbe3c474164731685cb73b8 |
Hashes for quicksectx-0.3.1b1-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8f4a9f225a85aaba3db5c4621efd90934a63de27bd21e2e68fbd03673a1090b1 |
|
MD5 | dc42ea4c7b91ba10978846bf504b005d |
|
BLAKE2b-256 | 94d27f8885376c83eb21d9d94c8f853abdf709458944fd90043611a622952a0e |
Hashes for quicksectx-0.3.1b1-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | de829069d1e3e165f27f6e113e735362764a32b41ef67fca3deddf97bdbeb0d5 |
|
MD5 | 719b266b720bd9b9e68f1119606b6cf8 |
|
BLAKE2b-256 | fea9880c686216f0b1e63dd86f64e30dfb223cc32fe54318333f60c83f9e3e9f |
Hashes for quicksectx-0.3.1b1-cp36-cp36m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b3cadea8e5dd7e7c1c720dd0112d042939186e9e21d3a76dacb61a8059e235e4 |
|
MD5 | 4bacccf7399b63b42d9ee2296185eb80 |
|
BLAKE2b-256 | 29d074792b3f943b17349fae4bce77bf1a8625664f5eff50710e288c53a0317d |
Hashes for quicksectx-0.3.1b1-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a296f22ad949619b256ae808d78213384af628417167fec0dd86ebe5ddeb0ca4 |
|
MD5 | 7b8cc61068e5c3dfcef1a72b268d0723 |
|
BLAKE2b-256 | 134bf387579cb71e2828fdeac80ef36bbb7f5f1c83c07e7b504e74c72edcd67c |
Hashes for quicksectx-0.3.1b1-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7482b4977b38f0ca4842efef2fb54c5b52afe41d27a73210c2cb70b1fe2b7e95 |
|
MD5 | d87765578fa335e6545141c92c8b1a39 |
|
BLAKE2b-256 | 4df6c5d86fa050c989f434427fe86f15afcc3c782120fe0a51bd8f172ddb284f |