Quicksect is a fast python / cython implementation of interval search.
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.
(https://github.com/brentp/quicksect)
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, 'a')) >>> res = tree.find(Interval(99, 100, 'b')) >>> res [Interval(88, 444)] >>> res[0].start, res[0].end, res[0].data (88, 444, 'a')
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.8a0-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7b822eb43e336305a7dfba7e7e95a6f1ef8b028e54a33d47295740f733033bec |
|
MD5 | cb629f6815a45d8447c0ce125c5333fb |
|
BLAKE2b-256 | 140e91ab4d9a7e3774ea7be4a49182ea9d6d36898871baf5ffd86b35769b4408 |
Hashes for quicksectx-0.3.8a0-cp311-cp311-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f10c23f83e9ac753396c20baca3c0397bacd2504e606c19d2ee109b187c5c351 |
|
MD5 | b23c3f62d7fb833e386e554d42f903dc |
|
BLAKE2b-256 | 787770e90f07c60056d9fa594b373cef8fdbea54a0ac972228aaff8d2f1acb45 |
Hashes for quicksectx-0.3.8a0-cp311-cp311-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c14af8a8003d470a8711ca85801b686f76b625efbc0ab16554a1ae4e6b5bd007 |
|
MD5 | 8929d91a445838442ad824b6304e2f5f |
|
BLAKE2b-256 | d68305e957a44fb0fb0328253e45152fb20abc3b1170e800f738c405c81bf21e |
Hashes for quicksectx-0.3.8a0-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5f1c8f993203fbbc262be6657a789e3525f85f954b82844c7455fca4c0ad46db |
|
MD5 | 652f09f0872d256df766a73a3abe7fd2 |
|
BLAKE2b-256 | 25623e4384417deb72ecb510a866ddbaaa7e7fef47b721814487753b0c9b9409 |
Hashes for quicksectx-0.3.8a0-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 053c4ae1cb90c2c04decbf02a5383d6c50a2bd6a32faa35eb0cd7358f097fca3 |
|
MD5 | 2378a28705ddceaf26a4a1af85b5f32a |
|
BLAKE2b-256 | dbedad478861b8829f68c1d3e736a43dc3a84ffe06aed3f2af88baf6728ba4f7 |
Hashes for quicksectx-0.3.8a0-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c3491988d51e2817d73ceb43667bc1bad3a53a2494760baa55cedf1ca20c8a4b |
|
MD5 | 171564fb2b309a6ad572c9d4e6dd8ab4 |
|
BLAKE2b-256 | 85dd676e69dc3f492d598209fc63b57377339cd2c267c86a6fe7e406c519fd1f |
Hashes for quicksectx-0.3.8a0-cp310-cp310-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | df6f2907893866daeb999990eb80224f1adf90c56c6811735c979db7943c9c9e |
|
MD5 | b93deb400ba65b0c41746e99d29567a5 |
|
BLAKE2b-256 | dffd6e5725b7f7349b23e9eb616f7ef1d9b18329182634ace61e7ee13fa5397e |
Hashes for quicksectx-0.3.8a0-cp310-cp310-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4f4cbb7e6f129d6f2ecfe55eb46403ddb36af2559be049bf9082b37050ebea88 |
|
MD5 | 4e10e46432245db8b9ae363a276b9f00 |
|
BLAKE2b-256 | 344e42e9964cb7e162620ab759f4caa6e449d6453aefc63f163a14711e9d013f |
Hashes for quicksectx-0.3.8a0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4b3c770c3b24e1cf00c23581d381dcc0ec30e54a08f0f0a5da240f935f37f88e |
|
MD5 | 0cbcbc86adb17fb01c574c3a8bf08f57 |
|
BLAKE2b-256 | 083dffbecc6a2e08c5c6427a7762b9f761774fa9c738f9996a28548430d39c56 |
Hashes for quicksectx-0.3.8a0-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | db695237cca99b36f9cc68d6b0ee202ba3692bef3b298e572c8647a5d8263265 |
|
MD5 | 87787ac4911d6ebb64ed57c31367dc96 |
|
BLAKE2b-256 | 71c03e42b0a855408436b070e85f6cb5119fafa9e0b4c1bdef7249cba8b4faa5 |
Hashes for quicksectx-0.3.8a0-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 03b472b7d5b3f003fcd449f9b2bf4c9aaab09eb97f92a0d6effcd7423915a6d3 |
|
MD5 | 3306e911ff249218ea8a109c0aa53263 |
|
BLAKE2b-256 | 63d19765e3324a6ab2dae1a265339c4a242c87d0ae3adc85abe15de6f1f6007c |
Hashes for quicksectx-0.3.8a0-cp39-cp39-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 34a390f0fdf106092c9bc420095386bc78f114f3a57487e783b47b60b9117c85 |
|
MD5 | cf2f4a645c2709854e6b1a63a5778d7f |
|
BLAKE2b-256 | 780747b02bfb3caaf0e0e6f3e0e49c48e241b69bf616f24f327f3a01565b4f0f |
Hashes for quicksectx-0.3.8a0-cp39-cp39-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1111756e5422ac4ba7476e1486841a6159dce6d4bb2f0376cf4bda12227f928b |
|
MD5 | 473af919372bf213e71a2c48635e57ad |
|
BLAKE2b-256 | e574d510af58f6e4e5b276fe0964a09e95046d084ec94fb7d0188a26d5d94943 |
Hashes for quicksectx-0.3.8a0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5f0edfd44c1938465b5f228e3bf73bb0efd5e40e12000bc53916e658b592372b |
|
MD5 | e56129215ad4e764a9ac50ba55714330 |
|
BLAKE2b-256 | 66658bdc5e25f4634907a377a66562dc685e66df3c78571121ac659c884d550b |
Hashes for quicksectx-0.3.8a0-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 69d34c2a690b7c86de2f75bee7064522ea702189274f46725d0be819ac6abf53 |
|
MD5 | 4faa885fbbba64ebd0c5ff44815e5035 |
|
BLAKE2b-256 | 46e353613b25503cda19c4e985e67f7e1f70b2696aac9e540e65679b83c4cedd |
Hashes for quicksectx-0.3.8a0-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a154d7e522058afed696b275edfe29722efdeed1bd6c38fc6ce9c2532d97b139 |
|
MD5 | 0c4f078a0547aefa21b2530ccd71c3fe |
|
BLAKE2b-256 | 1b7b1b614d05babee913b9e6444158ce598d17d45876e172b9dbc5484f376aeb |
Hashes for quicksectx-0.3.8a0-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 68115ab3b0300b67012ed6cf7401064600a3597f61031ffc4f9c1aab6a055f39 |
|
MD5 | f6155574a4ac2d14b505d8f8cea6df00 |
|
BLAKE2b-256 | 2e175ae396a083e8086010d52c4dcc8af8aa7940cb08b0b76a207ac685a2a002 |
Hashes for quicksectx-0.3.8a0-cp38-cp38-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 83058cad7f50fd0fde49a981a7fc09adcd53e7cfb1944065f0472799ba5c055d |
|
MD5 | f092431d267813b71089bb7a2b1ceb79 |
|
BLAKE2b-256 | 325616e5355064ae00bbcfe5d48630d01e083302a6784bec8c73a249625d9358 |
Hashes for quicksectx-0.3.8a0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d6827605f43565c7a2f6af0552a3c65bd52d25a64628221878f3d722344ae2b3 |
|
MD5 | 9b2c9ceaa35dc521b8c484bbdd5c3cd6 |
|
BLAKE2b-256 | e3581c029d52e3d3423dfdf0127149c971a4ccf1e2a92a02d6b326c3c70cad73 |
Hashes for quicksectx-0.3.8a0-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3340fadcfc8cd2d5d99dd151751fb8647ac641ea2ad4214d45c395e98b06e008 |
|
MD5 | 1bf2ab02939ae4a2dd759f903325d67e |
|
BLAKE2b-256 | 6ddd4794628f3e236c42ef29c63e1314ab1d8a5977ac9ff80915836dc834a77f |