Skip to main content

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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for quicksectx, version 0.3.0
Filename, size File type Python version Upload date Hashes
Filename, size quicksectx-0.3.0-cp36-cp36m-macosx_10_9_x86_64.whl (205.7 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size quicksectx-0.3.0-cp36-cp36m-manylinux1_i686.whl (564.3 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size quicksectx-0.3.0-cp36-cp36m-manylinux1_x86_64.whl (591.5 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size quicksectx-0.3.0-cp36-cp36m-manylinux2010_x86_64.whl (643.9 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size quicksectx-0.3.0-cp36-cp36m-win_amd64.whl (184.5 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size quicksectx-0.3.0-cp37-cp37m-macosx_10_9_x86_64.whl (201.8 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size quicksectx-0.3.0-cp37-cp37m-manylinux1_i686.whl (561.0 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size quicksectx-0.3.0-cp37-cp37m-manylinux1_x86_64.whl (589.2 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size quicksectx-0.3.0-cp37-cp37m-manylinux2010_x86_64.whl (640.8 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size quicksectx-0.3.0-cp37-cp37m-win_amd64.whl (184.5 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size quicksectx-0.3.0-cp38-cp38-macosx_10_9_x86_64.whl (204.0 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size quicksectx-0.3.0-cp38-cp38-manylinux1_i686.whl (563.8 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size quicksectx-0.3.0-cp38-cp38-manylinux1_x86_64.whl (593.2 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size quicksectx-0.3.0-cp38-cp38-manylinux2010_x86_64.whl (720.0 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size quicksectx-0.3.0-cp38-cp38-win_amd64.whl (187.7 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size quicksectx-0.3.0.tar.gz (212.2 kB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page