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.
(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.3-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ff4145a0448f396086cd907ee507b36cfa9b34fca82d8f00935af25c2ef2489b |
|
MD5 | 58538e0f444af1a6be5fb34570672823 |
|
BLAKE2b-256 | 136512a52c01c12c39123976ec157b32f38c419345cb11adfcf9f0153f132271 |
Hashes for quicksectx-0.3.3-cp311-cp311-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2a5583438c450b54368913702f484aa5fe05e4b5e20cc2dd715739eabeb3a1e5 |
|
MD5 | 49f52294d1b44c814d83edb589ece568 |
|
BLAKE2b-256 | a743fd163cf3d32dda736b2fc77416a7e27dfda13b4ccc7d48dfbe66688a8a86 |
Hashes for quicksectx-0.3.3-cp311-cp311-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bec0f416a9b75a6583b3df02c5dbaf6a0d1c18df6813fd9d1ebb2ea26053b014 |
|
MD5 | ba99f5848f6e41e8af4fdf4a235b82ad |
|
BLAKE2b-256 | 8892a1e8c0ba4c075f1f55e09d4ed1539fe14d2b2f892c95b9d28c611c9b9084 |
Hashes for quicksectx-0.3.3-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 827bebb440dd6e796b2a59e0a17d80e19b09b535353b379152d948c725bd6ff3 |
|
MD5 | 77a37c4670565d5a42cce63cab01bb17 |
|
BLAKE2b-256 | 1765752f3986fac50b0393971d3c7587dd475874ec6c25b507fcbd5bdc33f23a |
Hashes for quicksectx-0.3.3-cp311-cp311-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e655ef1ba1ba0c27e16f9ab487d76aa61c298565233f83c8eabec45620bbd58b |
|
MD5 | 55e3d7f31d6eae848ebe9495f0d5e95a |
|
BLAKE2b-256 | 1eb9236655cfe9d8c1a73c0a2b2bebc2120cda0f92186e57bd16c6bacfc61536 |
Hashes for quicksectx-0.3.3-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ba9e99c857295c1edd3b847e75b4537c37908be04697036074c0a05644b92359 |
|
MD5 | c11420fd8727e0dc9b9c2498681122f7 |
|
BLAKE2b-256 | 199c7319aec75e2e30e8945ac0dc7f8f8a6066a7a359efe990b7c003db822a2b |
Hashes for quicksectx-0.3.3-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 66917fc8b0561b0cda88975e017946bc4f662fa299aa5266abaab3bb87c10873 |
|
MD5 | 256415994e5e43eb2e55d819b9429013 |
|
BLAKE2b-256 | de189dc78fde28a8b5ec9350ff9d33df38470ba43c56ed35c51eb6bc0afc9c43 |
Hashes for quicksectx-0.3.3-cp310-cp310-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 373640cddf6e03951e2abf2c9a54b341e2ee427e970e9d2a84098c6d04db19b7 |
|
MD5 | 1e26f300a85333a86b0e02a1d779d3a7 |
|
BLAKE2b-256 | bba46103c60a39f400e86cfa460dfcb93e513cb654142b42c7542211a65620d9 |
Hashes for quicksectx-0.3.3-cp310-cp310-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b10a5ecce98396b8b6e8a3cbb1670c9599a17ca5c3ef46e8c700429db6941aa7 |
|
MD5 | 51a844a12470162a67aa11643a75db8d |
|
BLAKE2b-256 | 0aa16ed6338f91eefe16808900945f7219820d4820211c94167de624dd351a5b |
Hashes for quicksectx-0.3.3-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 752ec09058298e40631c6949f109bff644f30c659eb2900bf20c5fc884afbfcc |
|
MD5 | a8f5096844af0fac496cbc90eb4f51af |
|
BLAKE2b-256 | 902d2ba255854245608312e92f203863eb74fa40edef1811dec5247e334cc7bc |
Hashes for quicksectx-0.3.3-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 76b684151379082ac5437ffb3606d61ae9737fdf4cba951fc8cb43bdf38a9545 |
|
MD5 | aec391c59224d0a1fe7a052322f992c6 |
|
BLAKE2b-256 | 446eaf33ec7b0c17998ceda76f6f5fe4ae1c2f524ee86de284bdacbf630c29ba |
Hashes for quicksectx-0.3.3-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5583c866689c24b3f33ba5477ce69ca2a3a36d376c50e13311447bbc20bde3f5 |
|
MD5 | 1bcac7e3da7385fae0e0470c81737dce |
|
BLAKE2b-256 | 8b2756dcb1bc381fbf755b6351c97d7b082f9ed508af1a78dc0e606e5910a26b |
Hashes for quicksectx-0.3.3-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 67d2da823d5af4148083e530077e1dd6912fce6b436b1bfe65940a718e1eba26 |
|
MD5 | c60f6c4cd7b7ebc70495994e790cb4ab |
|
BLAKE2b-256 | c86a904474cf3f129034b727349c9c7b2dc86ab770ffb17fa28ff4d76ff5da2a |
Hashes for quicksectx-0.3.3-cp39-cp39-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4d0bc0d1937c48a87b24f3b5ebbe13fccbed21fd9cc98e9458898de215f82e82 |
|
MD5 | 3b6942be6426e21033ee4ed7e37d61eb |
|
BLAKE2b-256 | 74521bbd37a7f58f0c30a74c717529917ee73e7c686248d037644ca909cbe555 |
Hashes for quicksectx-0.3.3-cp39-cp39-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 19ed50bd80c109f3a26bc59b64c372e5b9c1d1397bfe8685b73dcb4e09399e12 |
|
MD5 | 9c6b331ff31b42ab5cdb3e93308f1fc3 |
|
BLAKE2b-256 | f1cbc52c42c9c064e340f397d4f9d9c4cf94a1dcb67d44d662ca456043e5fb0e |
Hashes for quicksectx-0.3.3-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | afeca2e5585a01df8ddde3f3e4dd20fdf59dce5e6107cf8696c5bb36d410ed76 |
|
MD5 | 2e62793bd8567ab3972d32c8278d6804 |
|
BLAKE2b-256 | 861953cc31a6ba0fbdfa63e5980857a0485616b9ef263e28fb407c1c7c65612f |
Hashes for quicksectx-0.3.3-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c8fb85d0afc17b02f3f42061f2fc1c55e2bf15b5fe82758b16963111ee08b273 |
|
MD5 | c0b27595fa92d55d1071756b4ebca191 |
|
BLAKE2b-256 | 6225782a1a0323aae6409e8c846ed1ad3c2a284ca116871804606c2c74335a3e |
Hashes for quicksectx-0.3.3-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a1e8efb9f6ee6c8219227d3a3a6fa2df1f87aebc39a46b261d29bf9cf1fcaeda |
|
MD5 | 139dd2e57b156d146f1beb5e53afe316 |
|
BLAKE2b-256 | 1887ddcdacf42265b68ed3b17151559a5858f02fdb8c28e0924d80b94815a7f6 |
Hashes for quicksectx-0.3.3-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 677378e459a8119b516d8c7e52a6e59735f1c206c97acfcfabb21b7ee8d535ff |
|
MD5 | 04c805eb8859ac34b3569c9ad7f1841d |
|
BLAKE2b-256 | eeaa60d7d67961aa40f76bb39a822eb5d8ecfb6b11f1bbea5e1fdbc070cb159a |
Hashes for quicksectx-0.3.3-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a5b266fcb63133f9eea9ba398ac308e8383ff2517bef05bb2fed36ab9be24a2e |
|
MD5 | cb4e11e89f7115914670453e63e895b4 |
|
BLAKE2b-256 | 108bf74534a27942ba9377d2534412232d37a3da22e5d9f244af5b1e478c935f |
Hashes for quicksectx-0.3.3-cp38-cp38-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 454476493c3289f85be4e1c70dbe50a200581675f93223a3e4b51e9298947c23 |
|
MD5 | 9f44fc2163bb4d41840dbab1984e3e8a |
|
BLAKE2b-256 | 672bc2913e22ac14bcdcb355204d496c9bacc443d87fc216b1f3829593953461 |
Hashes for quicksectx-0.3.3-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | abf63399a75c28689cbbde41f62f0c9df7b4034daad46a181e75c18908325cc8 |
|
MD5 | 06be29fa56c3c463feb33dd8ea544e64 |
|
BLAKE2b-256 | a207247c9defd3fcb46967cc04ffe19df124e3faf3a798f7a5c332591abffbc8 |
Hashes for quicksectx-0.3.3-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ba442a94eeae607331d624d058ba5524d9a12bd89fc4f1cc2a089bbf3bbb2915 |
|
MD5 | befd8235f308c9f9e8b6d30eff6ac83d |
|
BLAKE2b-256 | b17bf6c0b50401fac0524628b02ab35f0932cb35ce16f91afda145104f9758e6 |
Hashes for quicksectx-0.3.3-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3256ef4e86f91367d524d22169d2ebea4eddea4d5b2ea1cb20d42031034265a6 |
|
MD5 | 8ddbdb2e46319f6514e8e23bced95b0c |
|
BLAKE2b-256 | 0fe0e54668667c618156d78d6e189959e89c4aaa81688f9783ab246ae9be8ef0 |
Hashes for quicksectx-0.3.3-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 811dc9eb1d192da5e9b2ab7e241e070e781ec36d3d9dd9f1cf648094958a4dbc |
|
MD5 | 8640e9d59663299b37a6a3750a54bfd1 |
|
BLAKE2b-256 | 23f1e7f1c0c036a61f7185db80e84421a3d21a1713c938693f9172db5f90ad40 |
Hashes for quicksectx-0.3.3-cp37-cp37m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 594a4a9ea817eb816e80e86dc96996a6f17a1a2133573d7be3e11256473a413e |
|
MD5 | e63841535a7f7a539ffabffcb3d8d1c0 |
|
BLAKE2b-256 | 7665ff7d594991df14281fd3ed3985ca05fb9115157361399803393a71531178 |
Hashes for quicksectx-0.3.3-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ad3f5a0be6f5ce4751ce4906a6e9e4a263e6f84c5216a572c70387cb137dbd71 |
|
MD5 | aaf89146bb138dd4da9bfa7a61fb5de9 |
|
BLAKE2b-256 | c6c17b1dd5c65f8fd2bf5b0b0dea834fbcae4bae5fe3096456cb2318704d73d2 |
Hashes for quicksectx-0.3.3-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dd4b896ed757821bcd498e2b4839a17f9821023210a834f91401731113600398 |
|
MD5 | 81c8a4362aae9ca4faf26fd3e3fbd436 |
|
BLAKE2b-256 | 1f4c37075ab04efa0b96eb2142ce7e5d6ba5f0fb6d6a439cdd097c70ae1ae86a |
Hashes for quicksectx-0.3.3-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a80217fe35bd65cc006dfddfb567e9643a594031b1219720273d8296e98571b1 |
|
MD5 | 43131932f3321aa3b30a18bd81cfbbb7 |
|
BLAKE2b-256 | a769c55d00463c4ac7f66c0e8d22f809aef026b214e49d6927915099ac0d74af |
Hashes for quicksectx-0.3.3-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 777866d7d21b7bda7ae2506a85832d42377c33f698e4afa5451edcf207906732 |
|
MD5 | 70c902e2950374dbd25015573abac29d |
|
BLAKE2b-256 | 0ec46fd2d4b4eec9f5d5535ea341bd1150f37ac9e37020126fa6f5727b1d74f6 |
Hashes for quicksectx-0.3.3-cp36-cp36m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9800a4c01bee1d465c4aa4dc6a261a4ae05f56f81b27e071f9f51854e9990651 |
|
MD5 | 7b9c7d06012f78fd77764a8136f4126a |
|
BLAKE2b-256 | 07c5ced36bc8a06006de4ca52ba1b1e8ad2580e3f3db01e4da0b5f9b518050fc |
Hashes for quicksectx-0.3.3-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a4d91fa2dbd94c7952ffee9fcadc9b0be064b1485cfb0041165a5e7f2dc304d4 |
|
MD5 | 4441d6466a75f309878aabdc8d334499 |
|
BLAKE2b-256 | ee0f5619e036c420af38e1b607c7eb7b32d774c408d352abf2caf18eb812b773 |
Hashes for quicksectx-0.3.3-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6a707e11dfddd2e797aea5828f7b2d2d7dfb52ee7082caf18d4b7532138a0524 |
|
MD5 | 1a559a0f51ac0e89b32ada13b6701a7e |
|
BLAKE2b-256 | 1eb1bb30b18c3df283d271247778b65663850b227463487f9152bb1aa1abdaf4 |