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 quicksect
or
conda install -c bioconda quicksect
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.2.5-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5ae78676d308307996a6836dca819fdd06f8738ac44b235f1b29385ddebf36ae |
|
MD5 | 1b2fa0c98c2f1eff1829e5b01eff5cd5 |
|
BLAKE2b-256 | 8350a01016eb2663d73857bea0541f83fe62472b3a916e451acd72413955bde0 |
Hashes for quicksectx-0.2.5-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 866527a697355e35fa8af345d987618c31074780ca05ad7b9e6fe914b744ae6d |
|
MD5 | efb8d8b3a818dfe72f9e8458d3b3658e |
|
BLAKE2b-256 | 4346859f4bf3bd7df54180083da75bb72ebac81a9e372bfc893cbf20a44eb261 |
Hashes for quicksectx-0.2.5-cp38-cp38-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e68bfc018f1277445445a96b7ce1df0232e0ce87f2a847979cde0355f4f03c4b |
|
MD5 | 09636cc3f9041ed9eba4a512443844d6 |
|
BLAKE2b-256 | 3edaf9d5c59c980812ba8653cc65f7cd6626d4667e0f26f69b010391fc8e27e5 |
Hashes for quicksectx-0.2.5-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 50f31be1ee911ff1700d222cbbb084bfb7783e5a50a89b00f66d3437e2f5a389 |
|
MD5 | 907533168eb6218534f79e224bad4517 |
|
BLAKE2b-256 | 9bee9521806796f4fed1e3d0dd73582bc9fba328887a862cecb38d952c786d82 |
Hashes for quicksectx-0.2.5-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 596648278d37fe771cbd8f1b7a10cb929df3e5d3aa1bad45eca69fec36009603 |
|
MD5 | 08bce0d9b5b9ee58c2ac355c9867a52e |
|
BLAKE2b-256 | 60c5fe2584be2e8a99d57cb35ca5562b4d0cbc9c930a7451087c81a322abd4a0 |
Hashes for quicksectx-0.2.5-cp37-cp37m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fd229f6d28bb0c259de6b27fa17e79e9c9e9863173a26cbb77af38a95e9274d3 |
|
MD5 | aee1db06f32d74b4ff47b51e385adf06 |
|
BLAKE2b-256 | 20b6f26748a0ef1ab4dee4ebe13872035f69a8f98d5e22945bfd819694a34914 |
Hashes for quicksectx-0.2.5-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 37dd1d0a88ae1ded8f9fb164611292c7dbda64ff318343a09cd756d855eb6b39 |
|
MD5 | b2bc3f6751e351d44580fcfb0e9fc0f6 |
|
BLAKE2b-256 | 516e5196099533b7e51aca52dda67d5143135d5afa9fae080e5abe80fe689c02 |
Hashes for quicksectx-0.2.5-cp36-cp36m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dcdc8a477d2b30c8d2e5d7ae23c9e39fd160a5bd3a57a8918939d6add73d6089 |
|
MD5 | 214de26bfe3b3c4da9f70fee64300ff8 |
|
BLAKE2b-256 | 2518df3bac8922b04e27300806ede7be8a0b927f424b4176bc931266dbde35ce |
Hashes for quicksectx-0.2.5-cp36-cp36m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 74571613911d049343006674041ec79e8ee666af7d06d50263926b739c7adc6c |
|
MD5 | fadb9b3cd312574081f56577b8f14569 |
|
BLAKE2b-256 | 2265e0d36f1764b0033f01b5d1d40417286299779bcf3b90b6093655ff4faab2 |