Skip to main content

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)]

Since 0.3.7, you can use python’s native pickle to pickle an IntervalTree object. For details, check test_serialization.py

For Dev

Now the version specification has been integrated with setup.py and pyproject.toml. To update versions, only need to change the __version__ in quicksectx/__init__.py

Project details


Download files

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

Source Distribution

quicksectx-0.4.0.tar.gz (238.2 kB view details)

Uploaded Source

Built Distributions

quicksectx-0.4.0-cp312-cp312-win_amd64.whl (356.9 kB view details)

Uploaded CPython 3.12 Windows x86-64

quicksectx-0.4.0-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.1 MB view details)

Uploaded CPython 3.12 manylinux: glibc 2.17+ x86-64

quicksectx-0.4.0-cp312-cp312-macosx_10_13_universal2.whl (505.5 kB view details)

Uploaded CPython 3.12 macOS 10.13+ universal2 (ARM64, x86-64)

quicksectx-0.4.0-cp311-cp311-win_amd64.whl (356.4 kB view details)

Uploaded CPython 3.11 Windows x86-64

quicksectx-0.4.0-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.1 MB view details)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64

quicksectx-0.4.0-cp311-cp311-macosx_10_9_universal2.whl (505.8 kB view details)

Uploaded CPython 3.11 macOS 10.9+ universal2 (ARM64, x86-64)

quicksectx-0.4.0-cp310-cp310-win_amd64.whl (356.1 kB view details)

Uploaded CPython 3.10 Windows x86-64

quicksectx-0.4.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.0 MB view details)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64

quicksectx-0.4.0-cp310-cp310-macosx_10_9_universal2.whl (504.9 kB view details)

Uploaded CPython 3.10 macOS 10.9+ universal2 (ARM64, x86-64)

quicksectx-0.4.0-cp39-cp39-win_amd64.whl (356.3 kB view details)

Uploaded CPython 3.9 Windows x86-64

quicksectx-0.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.0 MB view details)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64

quicksectx-0.4.0-cp39-cp39-macosx_10_9_universal2.whl (506.1 kB view details)

Uploaded CPython 3.9 macOS 10.9+ universal2 (ARM64, x86-64)

quicksectx-0.4.0-cp38-cp38-win_amd64.whl (356.8 kB view details)

Uploaded CPython 3.8 Windows x86-64

quicksectx-0.4.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.0 MB view details)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64

quicksectx-0.4.0-cp38-cp38-macosx_10_9_universal2.whl (506.4 kB view details)

Uploaded CPython 3.8 macOS 10.9+ universal2 (ARM64, x86-64)

File details

Details for the file quicksectx-0.4.0.tar.gz.

File metadata

  • Download URL: quicksectx-0.4.0.tar.gz
  • Upload date:
  • Size: 238.2 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.1.1 CPython/3.8.18

File hashes

Hashes for quicksectx-0.4.0.tar.gz
Algorithm Hash digest
SHA256 25bc4ce3638c0713c8b57274454adac071e36ee76265707771eb3dab75245c55
MD5 2f4626fb3abf7eaf26e803b672e6f4ca
BLAKE2b-256 40aff890ee37cb2801e548aaa7479073427cf0586a414564eaba13c76647c9fe

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp312-cp312-win_amd64.whl.

File metadata

File hashes

Hashes for quicksectx-0.4.0-cp312-cp312-win_amd64.whl
Algorithm Hash digest
SHA256 cb0466e5d5ed80e81560a90bc8cf40de4777c13f62a11852840e02351675c366
MD5 7e87811243f2bef6b3451fa7d5039e2a
BLAKE2b-256 4e24fc47ddc2238bcd101a0f9da7ede0594cfc1a07499039497fb1132575744c

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for quicksectx-0.4.0-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 607694b64eda1a4ac90f7de9db9989ca7246fda5f1d2d2025e4e81210a54e8e6
MD5 dcd9c698412875917c251d5cd070129e
BLAKE2b-256 ce8bb78668747d96c0f40f50988320c6a43024b7fe64df96aea8d0c30420adb5

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp312-cp312-macosx_10_13_universal2.whl.

File metadata

File hashes

Hashes for quicksectx-0.4.0-cp312-cp312-macosx_10_13_universal2.whl
Algorithm Hash digest
SHA256 1a673f6d34e160671a2cb6e7a0efde6696aa4f61914764e2188e32f5675e5c01
MD5 1ac61c7fe4979316dd3f57ea0b175259
BLAKE2b-256 9c8bbd38db6a6e8dfc1f477631ed8aad0704dedd59017bdbed0d9eebe5f74e5c

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp311-cp311-win_amd64.whl.

File metadata

File hashes

Hashes for quicksectx-0.4.0-cp311-cp311-win_amd64.whl
Algorithm Hash digest
SHA256 cec691ca82e914ce79fc790bac4d715677c6015c38b52d2e10d0afef5533e028
MD5 571e05b79d30685ccd791684bd8cbaf5
BLAKE2b-256 cab73dd75210323c0729b810f9a4f6cefad207512ae2f2b0d36c07da9d5d684d

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for quicksectx-0.4.0-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 68fc1af2027ffdf72ff6b77a446d28f01161b523a94879748cf6e589c30d8ada
MD5 5da3da978f93ca41fda3a9f8437ab06d
BLAKE2b-256 89a9a20978b3128220eb9ba07999667a9201bbf1a7196f18f23770309cac4c48

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp311-cp311-macosx_10_9_universal2.whl.

File metadata

File hashes

Hashes for quicksectx-0.4.0-cp311-cp311-macosx_10_9_universal2.whl
Algorithm Hash digest
SHA256 d40aaec345f47192b2c9e2e1235835560a85a3aed5b61b661e8e74c5cecaca33
MD5 1d38badd69ef00a942e7308eeb8e9e77
BLAKE2b-256 a2f82c07b96f891091defc28fdfab794942a8966e9ee83113173fdb4a0b742d0

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp310-cp310-win_amd64.whl.

File metadata

File hashes

Hashes for quicksectx-0.4.0-cp310-cp310-win_amd64.whl
Algorithm Hash digest
SHA256 dd73fd822e50d7a938a9296098e73e6bd8c61d4ade14c18c5ca0457d30130dcf
MD5 7095231bc04c28866a028b532b31dab9
BLAKE2b-256 a4c9e01386e44eb06aa65707a1fc47020e65a1666c03363ac738778afba83b84

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for quicksectx-0.4.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 8a9b1d936bc90199c0591974a1282d913a937cfe2f50e0ca235746c96f34e23c
MD5 b6cc93200a7a81840538d4614abad13b
BLAKE2b-256 e90560089ad762b82d67d7bf05e39e10d5da05ccb1f3e0ba3df1a9ef2c91f81f

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp310-cp310-macosx_10_9_universal2.whl.

File metadata

File hashes

Hashes for quicksectx-0.4.0-cp310-cp310-macosx_10_9_universal2.whl
Algorithm Hash digest
SHA256 2800f23a6d89bea42f9bd0f3ee589818cd6769333e2dd139bb73e9eba2dac295
MD5 a3d973f380b9ebce822ec5948355522c
BLAKE2b-256 67d60d03bf14032a3c162cdc1044df313086e1d8048914506d5f7156588d07f1

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp39-cp39-win_amd64.whl.

File metadata

  • Download URL: quicksectx-0.4.0-cp39-cp39-win_amd64.whl
  • Upload date:
  • Size: 356.3 kB
  • Tags: CPython 3.9, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.1.1 CPython/3.8.18

File hashes

Hashes for quicksectx-0.4.0-cp39-cp39-win_amd64.whl
Algorithm Hash digest
SHA256 de3870f8208aef9218ac3fd92201dab1ed76ecd338fcaeb1137031ab7e673342
MD5 6d9ae4f3e20dd08c3d971b4b9660b4eb
BLAKE2b-256 6730da4b208042512666d2aa74bf67a5c066c1513a28792040dfe29c9aade709

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for quicksectx-0.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 3566af75a1b0a4efee8b86be1f4de361cd4cb35c3a7729261a88c566171f52ea
MD5 a8f4a9692bf2f94221d3562ba7731064
BLAKE2b-256 9a6d020e430173990cedf91a4470772fd1fbe51614198b6861e74da93e864e5f

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp39-cp39-macosx_10_9_universal2.whl.

File metadata

File hashes

Hashes for quicksectx-0.4.0-cp39-cp39-macosx_10_9_universal2.whl
Algorithm Hash digest
SHA256 5349c40c1ca0883f9c32c653d45a06f3c56c6521c9111a290122bee42a3be30d
MD5 e303e4e3c4f1a1f1ce6c33f234d45c51
BLAKE2b-256 0bb311c928a843eee0cf23d071a0e2925eabf38edf9ad01f2da19359d79fb992

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp38-cp38-win_amd64.whl.

File metadata

  • Download URL: quicksectx-0.4.0-cp38-cp38-win_amd64.whl
  • Upload date:
  • Size: 356.8 kB
  • Tags: CPython 3.8, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.1.1 CPython/3.8.18

File hashes

Hashes for quicksectx-0.4.0-cp38-cp38-win_amd64.whl
Algorithm Hash digest
SHA256 6e4b4c4a7dc72b15afa582c41a94d8cc4d4d5b8729985315b3b2c3bd5b210f4d
MD5 9eda4968733ca93a445630b31c327266
BLAKE2b-256 fee7caa580f7b79cedeac884ff6463d3f9451ee0315e17b4e36cd51db9a5b7c0

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for quicksectx-0.4.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 260a6bf40ab5f812e4b679153e8bd24cd16906a9e302afb830aa2cbf798cd56d
MD5 c23bd41ca13000bee259b229dfb98b31
BLAKE2b-256 d5330d6e7004ccf62f6944a4fd3a69a16b6bd46db5d6456d5527044a3ce378fc

See more details on using hashes here.

File details

Details for the file quicksectx-0.4.0-cp38-cp38-macosx_10_9_universal2.whl.

File metadata

File hashes

Hashes for quicksectx-0.4.0-cp38-cp38-macosx_10_9_universal2.whl
Algorithm Hash digest
SHA256 ba25fb2a893192f2fb77c79d5c4617880b4a4b630ffc2a1bb30a329c68ac3626
MD5 7199bcc8bc5ae8151546006ef159521b
BLAKE2b-256 363ec9c266981504954cfedfa32af20a1e9643fa25f017e6679849410ddea485

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page