Skip to main content

A Interval Tree Library

Project description

🌳 iTree - an Interval Tree library

itree

In computer science, an interval tree is a tree data structure to hold intervals. Every node in itree has a start and an end value.

Installation

itree supports Linux, MacOS and Windows operating systems.

Installation With pip

You can install itree by running:

  pip install py-itree

Build From Source With cmake

🍀 For MacOS with M1 Chip, some Windows OS, embedded systems, or different python versions where the method above doesn't work, please use the following workaround.

  • Install cmake (version>3.4)
  • Run the following command to build it locally:
pip install https://github.com/juncongmoo/itree/archive/refs/tags/v0.0.18.tar.gz

Quick Start

  • Symbol For Node And Tree
  🟢  - normal node; 
  🔵  - zero interval node; 
  🍁  - leaf node, which means no child node
  🌳  - a tree
  • Create Some Nodes
  >>> import itree
  >>> itree.Node('fruit', 0, 40)
  [🍁 n=fruit,s=0.00,e=40.00,x=0,c=0]
  >>> itree.Node('fruit')
  [🔵 n=fruit]
  >>> a=itree.Node('fruit', 0, 200)
  >>> b=itree.Node('apple', 10, 20)
  >>> print(a)
  [🍁 n=fruit,s=0.00,e=40.00,x=0,c=0]
  >>> a.append(b)
  >>> print(a)
  [🟢 n=fruit,s=0.00,e=200.00,x=0,c=1]
  >>> print(b)
  [🍁 n=apple,s=10.00,e=20.00,x=0,c=0]
  >>> print(a.nodes)
  [[🍁 n=apple,s=10.00,e=20.00,x=0,c=0]]
  >>> 
  • Create And Render A Tree
  >>> from itree import Tree
  >>> def demo_tree():
        t = Tree(tid="123", extra={"img": "1241241313.png"})
        t.start("root", 1, {"name": "itree"})
        t.start("math", 2, {"age": 10})
        t.start("music", 3, {"location": [1, 2, 3]})
        t.end("music", 4, {"price": 12.3})
        t.end("math", 16284000, {"memory": (1, 2, 3)})
        t.start("music", 122840057.8713503)
        t.end("music", 1228400500)
        t.start("music", 32840057.8713503)
        t.start("egg", 3284.8713503)
        t.start("icecream", 32843.8713503)
        t.start("pizza", 32843.8713503)
        t.end("pizza", 62845003)
        t.end("icecream", 62845003)
        t.end("egg", 6284500)
        t.end("music", 628400500)
        t.start("piggy", 3284.8713503)
        t.start("unicorn", 32843.8713503)
        t.start("monkey", 32843.8713503)
        t.end("monkey", 62845003)
        t.end("unicorn", 62845003)
        t.end("piggy", 6284500)
        t.end("root", 1628400570.8713503)
        print(f"{t.count},{t.depth}")
        t.consolidate()
        img_path = t.to_img()
        return img_path, t
  >>> img_path, t = demo_tree()
  >>> t
  (🌳 id=123,c=11,x=1,d=6,m=0,o=1)

Run the demo_tree() function, a tree digraph will be generated:

demo_tree

The green circle node is a virtual node. The yellow record box is the node with the longest interval.

A virtual node is a conceptual node which could have many subnodes/subtrees.

vnode

Development

Turn on local build to ON in itree/CMakeLists.txt:

option(LOCAL_BUILD "build locally" OFF)
  • Test
$python -m unittest discover
...............
----------------------------------------------------------------------
Ran 15 tests in 1.209s

OK
  • Format
find itree -path itree/pybind11 -prune -o -iname *.h -o -iname *.cpp | xargs clang-format -i
black -S . --exclude '(\.history|\.vscode|\.git|\.VSCodeCounter|venv|workspace|pybind11)'
  • Build
rm -fr itree/build/ && ./release.sh && yes | cp itree/build/_itree.* itree/
pip install --editable .

License

Tree is licensed under the Apache 2.0 License.

Project details


Download files

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

Source Distributions

No source distribution files available for this release.See tutorial on generating distribution archives.

Built Distributions

py_itree-0.0.19-pp39-pypy39_pp73-win_amd64.whl (411.3 kB view hashes)

Uploaded PyPy Windows x86-64

py_itree-0.0.19-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (239.3 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

py_itree-0.0.19-pp39-pypy39_pp73-manylinux_2_17_i686.manylinux2014_i686.whl (253.3 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686

py_itree-0.0.19-pp39-pypy39_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (223.8 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

py_itree-0.0.19-pp39-pypy39_pp73-macosx_10_9_x86_64.whl (189.6 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

py_itree-0.0.19-pp38-pypy38_pp73-win_amd64.whl (411.4 kB view hashes)

Uploaded PyPy Windows x86-64

py_itree-0.0.19-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (240.0 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

py_itree-0.0.19-pp38-pypy38_pp73-manylinux_2_17_i686.manylinux2014_i686.whl (253.4 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686

py_itree-0.0.19-pp38-pypy38_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (224.4 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

py_itree-0.0.19-pp38-pypy38_pp73-macosx_10_9_x86_64.whl (189.7 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

py_itree-0.0.19-pp37-pypy37_pp73-win_amd64.whl (411.4 kB view hashes)

Uploaded PyPy Windows x86-64

py_itree-0.0.19-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (240.0 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

py_itree-0.0.19-pp37-pypy37_pp73-manylinux_2_17_i686.manylinux2014_i686.whl (254.0 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686

py_itree-0.0.19-pp37-pypy37_pp73-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (224.6 kB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ ARM64

py_itree-0.0.19-pp37-pypy37_pp73-macosx_10_9_x86_64.whl (189.5 kB view hashes)

Uploaded PyPy macOS 10.9+ x86-64

py_itree-0.0.19-cp311-cp311-win_amd64.whl (412.7 kB view hashes)

Uploaded CPython 3.11 Windows x86-64

py_itree-0.0.19-cp311-cp311-win32.whl (412.7 kB view hashes)

Uploaded CPython 3.11 Windows x86

py_itree-0.0.19-cp311-cp311-musllinux_1_1_x86_64.whl (752.6 kB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ x86-64

py_itree-0.0.19-cp311-cp311-musllinux_1_1_i686.whl (819.9 kB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ i686

py_itree-0.0.19-cp311-cp311-musllinux_1_1_aarch64.whl (728.4 kB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ ARM64

py_itree-0.0.19-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (242.7 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64

py_itree-0.0.19-cp311-cp311-manylinux_2_17_i686.manylinux2014_i686.whl (256.2 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ i686

py_itree-0.0.19-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (227.7 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ ARM64

py_itree-0.0.19-cp311-cp311-macosx_11_0_arm64.whl (192.2 kB view hashes)

Uploaded CPython 3.11 macOS 11.0+ ARM64

py_itree-0.0.19-cp311-cp311-macosx_10_9_x86_64.whl (192.4 kB view hashes)

Uploaded CPython 3.11 macOS 10.9+ x86-64

py_itree-0.0.19-cp311-cp311-macosx_10_9_universal2.whl (192.4 kB view hashes)

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

py_itree-0.0.19-cp310-cp310-win_amd64.whl (412.4 kB view hashes)

Uploaded CPython 3.10 Windows x86-64

py_itree-0.0.19-cp310-cp310-win32.whl (412.4 kB view hashes)

Uploaded CPython 3.10 Windows x86

py_itree-0.0.19-cp310-cp310-musllinux_1_1_x86_64.whl (752.8 kB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ x86-64

py_itree-0.0.19-cp310-cp310-musllinux_1_1_i686.whl (820.1 kB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ i686

py_itree-0.0.19-cp310-cp310-musllinux_1_1_aarch64.whl (728.7 kB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ ARM64

py_itree-0.0.19-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (242.3 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64

py_itree-0.0.19-cp310-cp310-manylinux_2_17_i686.manylinux2014_i686.whl (256.5 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ i686

py_itree-0.0.19-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (227.9 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ ARM64

py_itree-0.0.19-cp310-cp310-macosx_11_0_arm64.whl (191.9 kB view hashes)

Uploaded CPython 3.10 macOS 11.0+ ARM64

py_itree-0.0.19-cp310-cp310-macosx_10_9_x86_64.whl (192.1 kB view hashes)

Uploaded CPython 3.10 macOS 10.9+ x86-64

py_itree-0.0.19-cp310-cp310-macosx_10_9_universal2.whl (192.1 kB view hashes)

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

py_itree-0.0.19-cp39-cp39-win_amd64.whl (412.5 kB view hashes)

Uploaded CPython 3.9 Windows x86-64

py_itree-0.0.19-cp39-cp39-win32.whl (412.5 kB view hashes)

Uploaded CPython 3.9 Windows x86

py_itree-0.0.19-cp39-cp39-musllinux_1_1_x86_64.whl (753.2 kB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ x86-64

py_itree-0.0.19-cp39-cp39-musllinux_1_1_i686.whl (819.7 kB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ i686

py_itree-0.0.19-cp39-cp39-musllinux_1_1_aarch64.whl (728.4 kB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ ARM64

py_itree-0.0.19-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (242.5 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64

py_itree-0.0.19-cp39-cp39-manylinux_2_17_i686.manylinux2014_i686.whl (256.9 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ i686

py_itree-0.0.19-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (228.3 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ ARM64

py_itree-0.0.19-cp39-cp39-macosx_11_0_arm64.whl (192.1 kB view hashes)

Uploaded CPython 3.9 macOS 11.0+ ARM64

py_itree-0.0.19-cp39-cp39-macosx_10_9_x86_64.whl (192.2 kB view hashes)

Uploaded CPython 3.9 macOS 10.9+ x86-64

py_itree-0.0.19-cp39-cp39-macosx_10_9_universal2.whl (192.2 kB view hashes)

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

py_itree-0.0.19-cp38-cp38-win_amd64.whl (412.1 kB view hashes)

Uploaded CPython 3.8 Windows x86-64

py_itree-0.0.19-cp38-cp38-win32.whl (412.0 kB view hashes)

Uploaded CPython 3.8 Windows x86

py_itree-0.0.19-cp38-cp38-musllinux_1_1_x86_64.whl (752.4 kB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ x86-64

py_itree-0.0.19-cp38-cp38-musllinux_1_1_i686.whl (819.5 kB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ i686

py_itree-0.0.19-cp38-cp38-musllinux_1_1_aarch64.whl (728.1 kB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ ARM64

py_itree-0.0.19-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (241.7 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64

py_itree-0.0.19-cp38-cp38-manylinux_2_17_i686.manylinux2014_i686.whl (256.3 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ i686

py_itree-0.0.19-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (227.6 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ ARM64

py_itree-0.0.19-cp38-cp38-macosx_11_0_arm64.whl (191.9 kB view hashes)

Uploaded CPython 3.8 macOS 11.0+ ARM64

py_itree-0.0.19-cp38-cp38-macosx_10_9_x86_64.whl (192.1 kB view hashes)

Uploaded CPython 3.8 macOS 10.9+ x86-64

py_itree-0.0.19-cp38-cp38-macosx_10_9_universal2.whl (192.1 kB view hashes)

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

py_itree-0.0.19-cp37-cp37m-win_amd64.whl (410.7 kB view hashes)

Uploaded CPython 3.7m Windows x86-64

py_itree-0.0.19-cp37-cp37m-win32.whl (410.7 kB view hashes)

Uploaded CPython 3.7m Windows x86

py_itree-0.0.19-cp37-cp37m-musllinux_1_1_x86_64.whl (757.1 kB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.1+ x86-64

py_itree-0.0.19-cp37-cp37m-musllinux_1_1_i686.whl (824.7 kB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.1+ i686

py_itree-0.0.19-cp37-cp37m-musllinux_1_1_aarch64.whl (734.8 kB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.1+ ARM64

py_itree-0.0.19-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (245.4 kB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ x86-64

py_itree-0.0.19-cp37-cp37m-manylinux_2_17_i686.manylinux2014_i686.whl (261.3 kB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ i686

py_itree-0.0.19-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (230.8 kB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ ARM64

py_itree-0.0.19-cp37-cp37m-macosx_10_9_x86_64.whl (189.3 kB view hashes)

Uploaded CPython 3.7m macOS 10.9+ x86-64

py_itree-0.0.19-cp36-cp36m-win_amd64.whl (410.5 kB view hashes)

Uploaded CPython 3.6m Windows x86-64

py_itree-0.0.19-cp36-cp36m-win32.whl (410.4 kB view hashes)

Uploaded CPython 3.6m Windows x86

py_itree-0.0.19-cp36-cp36m-musllinux_1_1_x86_64.whl (757.2 kB view hashes)

Uploaded CPython 3.6m musllinux: musl 1.1+ x86-64

py_itree-0.0.19-cp36-cp36m-musllinux_1_1_i686.whl (825.4 kB view hashes)

Uploaded CPython 3.6m musllinux: musl 1.1+ i686

py_itree-0.0.19-cp36-cp36m-musllinux_1_1_aarch64.whl (734.9 kB view hashes)

Uploaded CPython 3.6m musllinux: musl 1.1+ ARM64

py_itree-0.0.19-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (245.3 kB view hashes)

Uploaded CPython 3.6m manylinux: glibc 2.17+ x86-64

py_itree-0.0.19-cp36-cp36m-manylinux_2_17_i686.manylinux2014_i686.whl (261.0 kB view hashes)

Uploaded CPython 3.6m manylinux: glibc 2.17+ i686

py_itree-0.0.19-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (230.7 kB view hashes)

Uploaded CPython 3.6m manylinux: glibc 2.17+ ARM64

py_itree-0.0.19-cp36-cp36m-macosx_10_9_x86_64.whl (189.2 kB view hashes)

Uploaded CPython 3.6m macOS 10.9+ x86-64

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