{
    "info": {
        "author": "Bob Zimmermann",
        "author_email": "robert.zimmermann@univie.ac.at",
        "bugtrack_url": null,
        "classifiers": [
            "Development Status :: 3 - Alpha",
            "Intended Audience :: Developers",
            "Intended Audience :: Information Technology",
            "Intended Audience :: Science/Research",
            "License :: OSI Approved :: MIT License",
            "Operating System :: OS Independent",
            "Programming Language :: Python :: 3",
            "Programming Language :: Python :: Implementation :: PyPy",
            "Topic :: Scientific/Engineering :: Bio-Informatics"
        ],
        "description": "[![Build Status](https://travis-ci.com/nijibabulu/itree.svg?branch=master)](https://travis-ci.com/nijibabulu/itree)\n[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)\n[![Coverage Status](https://coveralls.io/repos/github/nijibabulu/itree/badge.svg)](https://coveralls.io/github/nijibabulu/itree)\n\n# itree\n\n`itree` is an interval tree data structure based on a self-balancing AVL binary search tree. \nSuitable for use with sequence features in bioinformatics.\n\n## Why `itree`?\n\n* **`itree` is fast**\n\n`itree` implements an augmented search tree optmized for searching sets of intervals. The following benchmarks the performance of inserting, removing and searching for random intervals taken from the human chromosome 12 Gencode genes[[1]](#notes):\n\n<img src=\"https://raw.githubusercontent.com/nijibabulu/itree/master/benchmarking/benchmarking.png\" alt=\"benchmarking\" width=\"500\" />\n\n* **`itree` is convenient**\n\n`itree` has a second-level interface for groups of objects (e.g. chromosomes):\n\n```python\n>>> import itree, collections\n>>> bed_records = [tuple(l.split()[:3]) for l in open('gencode.bed')] \n>>> i = collections.namedtuple('MyInterval', ['chrom','start','end'])\n>>> t = itree.GroupedITree('chrom', [i(f[0], int(f[1]), int(f[2])) for f in bed_records])\n>>> t.search(i('chr15', 45167200, 45167300)) \n[MyInterval(chrom='chr15', start=45167213, end=45187956),\n MyInterval(chrom='chr15', start=45167250, end=45187952),\n MyInterval(chrom='chr15', start=45167213, end=45201175),\n MyInterval(chrom='chr15', start=45152663, end=45167526)]\n```\n\n## Getting Started\n\n* **Construction**\n\nCreating an interval tree object:\n\n```python\n>>> import itree\n>>> t = itree.ITree()\n```\n\n* **Insertion**\n\nAny item inserted into an interval tree must contain \"start\" and \"end\" attributes as integers. \n\n```python\n>>> import collections\n>>> i = collections.namedtuple('MyInterval', ['start','end'])\n>>> t.insert(i(1,15))\n>>> t.insert(i(3,20))\n>>> t.insert(i(4,20))\n>>> t.insert(i(5,15))\n>>> t.insert(i(6,7))\n```\n\n* **Search**\n\nSearch for all intervals overlapping a given interval\n\n```python \n>>> t.search(i(1,4)) \n[MyInterval(start=3, end=20), MyInterval(start=4, end=20), MyInterval(start=1, end=15)]\n```\n\n* **Removal**\n\nRemove an interval exactly matching the given interval by its `start` and `end` attributes (but not necessarily the \nsame object).\n\n```python\n>>> t.pstring()\n      \u250c\u2013(1,15)\n\u2013(3,20)\n            \u250c\u2013(4,20)\n      \u2514\u2013(5,15)\n            \u2514\u2013(6,7)\n\n>>> t.remove(i(1,15))\n>>> t.pstring()\n      \u250c\u2013(3,20)\n            \u2514\u2013(4,20)\n\u2013(5,15)\n      \u2514\u2013(6,7)\n``` \n\nThe `pstring` method is mostly for debugging, but here we illustrate the rebalancing of the tree.\n\n* **Grouping**\n\nA second-level `itree` object, `GroupedITree`, works as a proxy to `itree` objects which can be grouped by any hashable attribute or function:\n\n```python\n>>> import itree, collections\n>>> i = collections.namedtuple('Appointment', ['day','start','end'])\n>>> appts = [i('Monday', 9, 13), i('Monday', 16, 17), i('Tuesday', 14, 15)]\n>>> t = itree.GroupedITree(key='day', intervals=appts)\n>>> t.search(i('Monday', 11, 12))\n[Appointment(day='Monday', start=9, end=13)]\n>>> t.search(i('Monday', 14, 15))\n[]\n```\n\nYou may also use any arbitrary hashable value returned from a function as a key:\n\n```python\n>>> i = collections.namedtuple('Appointment', ['day','month','start','end'])\n>>> date_key = lambda appt: \"{} {}\".format(appt.day, appt.month)\n>>> appts = [i(5, 'Jan', 9, 13), i(6, 'Jan', 16, 17), i(5, 'Feb', 14, 15)]\n>>> t = itree.GroupedITree(key=date_key, intervals=appts)\n>>> t.search(i(5, 'Jan', 16, 17))   \n[]\n```\n\n## Notes\n[1]. generated with `python3 scripts/benchmarking.py scripts/gencode.chr12.bed 500 10000 500 > benchmarking.txt`.\n\n\n",
        "description_content_type": "text/markdown",
        "docs_url": null,
        "download_url": "",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "",
        "keywords": "",
        "license": "MIT",
        "maintainer": "",
        "maintainer_email": "",
        "name": "itree",
        "package_url": "https://pypi.org/project/itree/",
        "platform": "",
        "project_url": "https://pypi.org/project/itree/",
        "project_urls": null,
        "release_url": "https://pypi.org/project/itree/0.0.5/",
        "requires_dist": null,
        "requires_python": "",
        "summary": "An interval tree data structure",
        "version": "0.0.5"
    },
    "last_serial": 4677780,
    "releases": {
        "0.0.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "9030aa32de026e7b05901742aec3dd5e",
                    "sha256": "6f4f9b525801b051beb18619e507dcde53b0b1ff9ca8c95dd9625d195a0bf658"
                },
                "downloads": -1,
                "filename": "itree-0.0.1-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "9030aa32de026e7b05901742aec3dd5e",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 7437,
                "upload_time": "2019-01-04T17:23:13",
                "url": "https://files.pythonhosted.org/packages/4c/53/ec4421babb8d2044ce3e041770b5fb2d5498ce977a942d604a061a2d4a02/itree-0.0.1-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "1fbdb0b967a792b35dbe65236255bc49",
                    "sha256": "5b117221c5ea67e0389b14f0c85f480d8771ca24df0991a35557b1a82d06989e"
                },
                "downloads": -1,
                "filename": "itree-0.0.1.tar.gz",
                "has_sig": false,
                "md5_digest": "1fbdb0b967a792b35dbe65236255bc49",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 6279,
                "upload_time": "2019-01-04T17:23:15",
                "url": "https://files.pythonhosted.org/packages/88/62/276fb10f7df1b8c2f4696be87b4425e954937ecdbc2a0cc043a361f02f03/itree-0.0.1.tar.gz"
            }
        ],
        "0.0.2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "a65738e3a791df914c2b8e7363df2652",
                    "sha256": "3787a1294c5f3df5a40e3bb73872733d10e1d402873b8a9989cfe6451f97c63b"
                },
                "downloads": -1,
                "filename": "itree-0.0.2-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "a65738e3a791df914c2b8e7363df2652",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 7987,
                "upload_time": "2019-01-04T17:27:16",
                "url": "https://files.pythonhosted.org/packages/1e/48/aa409559cca42e98fd4e0de8e6fd8ba39209f94108a817fe653151bc8ebe/itree-0.0.2-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "dc4cddefa66e4fe1cc47b750b00606fd",
                    "sha256": "ca75c5a2151ba51d85d2ea47c96f74e375de0de459caaf2849f0f6156a460cb7"
                },
                "downloads": -1,
                "filename": "itree-0.0.2.tar.gz",
                "has_sig": false,
                "md5_digest": "dc4cddefa66e4fe1cc47b750b00606fd",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 6467,
                "upload_time": "2019-01-04T17:27:18",
                "url": "https://files.pythonhosted.org/packages/57/ba/a112a77617aae28bd207615f1fcd1920782fafdc3336203eea581a017080/itree-0.0.2.tar.gz"
            }
        ],
        "0.0.3": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "a5be4a076022f9ebaec9e4ced572c29c",
                    "sha256": "f3280f2bf61c754b05f20dea7bc09f73244246c964d8212f8fb9f20a082de2f2"
                },
                "downloads": -1,
                "filename": "itree-0.0.3-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "a5be4a076022f9ebaec9e4ced572c29c",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 8013,
                "upload_time": "2019-01-04T17:28:23",
                "url": "https://files.pythonhosted.org/packages/77/bf/4439dc321153eb12046a584118a5d4c5718d03b238578250fc9548501338/itree-0.0.3-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "5131826948d17ac477832275a8f99e8f",
                    "sha256": "0b7fee9c4ee62c34d7998bc7f57258fcdd589e7306bea5b4ac519dee3af16816"
                },
                "downloads": -1,
                "filename": "itree-0.0.3.tar.gz",
                "has_sig": false,
                "md5_digest": "5131826948d17ac477832275a8f99e8f",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 6508,
                "upload_time": "2019-01-04T17:28:24",
                "url": "https://files.pythonhosted.org/packages/7e/ba/410d561d1c47af52d3ad0ea9e728ab279046c1705ce3da032c24a1a7c414/itree-0.0.3.tar.gz"
            }
        ],
        "0.0.4": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "62294d84a4406c5e212bac846014c367",
                    "sha256": "8a767b01271aaab9751027b557d5523c622b944a8110a376bb5da1a68b2dc1b1"
                },
                "downloads": -1,
                "filename": "itree-0.0.4-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "62294d84a4406c5e212bac846014c367",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 9040,
                "upload_time": "2019-01-09T17:13:27",
                "url": "https://files.pythonhosted.org/packages/eb/35/78967c9807887dd742527f33bb63188dcd0c42e32d20420eae5ce725e296/itree-0.0.4-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "656455539a2956fed0933cd3f1b9d6b9",
                    "sha256": "b3d3a0a6ed53e0740a2d35042b42caaeb27a82c32f8ca1f089e4512f29a3caed"
                },
                "downloads": -1,
                "filename": "itree-0.0.4.tar.gz",
                "has_sig": false,
                "md5_digest": "656455539a2956fed0933cd3f1b9d6b9",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 7692,
                "upload_time": "2019-01-09T17:13:29",
                "url": "https://files.pythonhosted.org/packages/4c/38/b8e857c6eced63c3dbdc3b9504601fac7fb98ff5deeaa587e94a1b37a558/itree-0.0.4.tar.gz"
            }
        ],
        "0.0.5": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "b4919df9fc585db8e02327d279364e84",
                    "sha256": "713db41a2e5270f8f5964cbab406d89576b542b363b834e1fe4a40e8e3b37a80"
                },
                "downloads": -1,
                "filename": "itree-0.0.5-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "b4919df9fc585db8e02327d279364e84",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 8148,
                "upload_time": "2019-01-09T17:45:05",
                "url": "https://files.pythonhosted.org/packages/61/de/3999aa179241a30bb2cc4c63ac49f877cfbcbd618946409db2b7ede427b3/itree-0.0.5-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "f334663aa253daddc12e18237976e3cd",
                    "sha256": "78a3ece4eb5aad76326914419c7922b96fface8ad3a1ae44d7a217ce73095679"
                },
                "downloads": -1,
                "filename": "itree-0.0.5.tar.gz",
                "has_sig": false,
                "md5_digest": "f334663aa253daddc12e18237976e3cd",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 7200,
                "upload_time": "2019-01-09T17:45:07",
                "url": "https://files.pythonhosted.org/packages/44/b6/149dae09305a66eeb13e7bea0fb9bdff7a318bb9567d6215bcf4909ffbf6/itree-0.0.5.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "b4919df9fc585db8e02327d279364e84",
                "sha256": "713db41a2e5270f8f5964cbab406d89576b542b363b834e1fe4a40e8e3b37a80"
            },
            "downloads": -1,
            "filename": "itree-0.0.5-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "b4919df9fc585db8e02327d279364e84",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": null,
            "size": 8148,
            "upload_time": "2019-01-09T17:45:05",
            "url": "https://files.pythonhosted.org/packages/61/de/3999aa179241a30bb2cc4c63ac49f877cfbcbd618946409db2b7ede427b3/itree-0.0.5-py3-none-any.whl"
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "f334663aa253daddc12e18237976e3cd",
                "sha256": "78a3ece4eb5aad76326914419c7922b96fface8ad3a1ae44d7a217ce73095679"
            },
            "downloads": -1,
            "filename": "itree-0.0.5.tar.gz",
            "has_sig": false,
            "md5_digest": "f334663aa253daddc12e18237976e3cd",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 7200,
            "upload_time": "2019-01-09T17:45:07",
            "url": "https://files.pythonhosted.org/packages/44/b6/149dae09305a66eeb13e7bea0fb9bdff7a318bb9567d6215bcf4909ffbf6/itree-0.0.5.tar.gz"
        }
    ]
}