{"id":9834,"library":"intervaltree","title":"IntervalTree","description":"IntervalTree is an editable, robust, and fast interval tree data structure for Python 2 and 3. It efficiently stores collections of intervals and allows for quick querying of overlapping or encompassing intervals. The current version is 3.2.1, with releases typically occurring a few times a year, focusing on bug fixes, performance improvements, and Python version compatibility.","status":"active","version":"3.2.1","language":"en","source_language":"en","source_url":"https://github.com/chaimleib/intervaltree","tags":["interval","tree","data structure","range","overlap","spatial"],"install":[{"cmd":"pip install intervaltree","lang":"bash","label":"Install stable version"}],"dependencies":[{"reason":"Used for efficient interval storage and retrieval within the tree structure.","package":"sortedcontainers","optional":false}],"imports":[{"note":"While 'import intervaltree' works, direct import is idiomatic and clearer.","wrong":"import intervaltree; t = intervaltree.IntervalTree()","symbol":"IntervalTree","correct":"from intervaltree import IntervalTree"},{"note":"The Interval class is exposed directly under the top-level package.","wrong":"from intervaltree.interval import Interval","symbol":"Interval","correct":"from intervaltree import Interval"}],"quickstart":{"code":"from intervaltree import Interval, IntervalTree\n\n# Create an empty interval tree\ntree = IntervalTree()\n\n# Add intervals. You can assign data or just add the interval.\n# Using slice notation for convenience (requires data assignment)\ntree[0:10] = \"first_interval\"\ntree[5:15] = \"second_interval\"\n\n# Or add Interval objects explicitly\ntree.add(Interval(12, 18, \"third_interval\"))\n\nprint(f\"Tree size: {len(tree)}\")\n\n# Querying intervals\n# Find all intervals overlapping a point\nintervals_at_point = tree[7] # Using slice notation for point query\nprint(f\"Intervals at point 7: {intervals_at_point}\")\n\n# Find all intervals overlapping a range\noverlapping_intervals = tree.overlap(6, 13)\nprint(f\"Intervals overlapping [6, 13): {overlapping_intervals}\")\n\n# Find all intervals that fully envelop another interval\nenveloping_intervals = tree.envelop(4, 8)\nprint(f\"Intervals enveloping [4, 8): {enveloping_intervals}\")\n\n# Remove an interval\ninterval_to_remove = Interval(0, 10, \"first_interval\")\ntree.remove(interval_to_remove)\nprint(f\"Tree size after removal: {len(tree)}\")\n","lang":"python","description":"This quickstart demonstrates how to create an IntervalTree, add intervals using both slice notation and explicit `Interval` objects, and perform common queries like finding intervals at a point, overlapping a range, or enveloping another range. It also shows how to remove an interval."},"warnings":[{"fix":"Migrate your code to use `tree.at(point)`, `tree.overlap(begin, end)`, `tree.envelop(begin, end)` for queries and `tree.update(items)` for adding multiple intervals.","message":"Version 3.0.0 introduced significant API changes for querying methods. The `search(begin, end, strict)` method was removed and replaced by `at(point)`, `overlap(begin, end)`, and `envelop(begin, end)`. The `extend(items)` method was also replaced by `update(items)`.","severity":"breaking","affected_versions":">=3.0.0"},{"fix":"Review existing calls to methods that previously implied `strict=False` or did not specify it, and explicitly set `strict=False` if the old inclusive boundary behavior is desired.","message":"The default behavior of `strict` arguments in methods was changed to consistently default to `True` in version 3.0.0. This might alter results for edge cases where interval boundaries are inclusive.","severity":"breaking","affected_versions":">=3.0.0"},{"fix":"Upgrade to version 3.2.1 or newer, which fixed this packaging issue. Alternatively, manually install `pip install sortedcontainers`.","message":"Version 3.2.0 had a bug where the `sortedcontainers` dependency was missing from the wheel, leading to `ModuleNotFoundError` on installation or runtime.","severity":"gotcha","affected_versions":"3.2.0"},{"fix":"Ensure your project uses Python 2.7.18 (if on Python 2) or Python 3.5+ (preferably 3.8+) to be compatible with recent versions of `intervaltree`.","message":"Support for Python 2.6, 3.2, and 3.3 was dropped in version 3.0.0. Support for Python 3.4 was dropped in 3.1.0.","severity":"breaking","affected_versions":">=3.0.0, >=3.1.0"}],"env_vars":null,"last_verified":"2026-04-17T00:00:00.000Z","next_check":"2026-07-16T00:00:00.000Z","problems":[{"fix":"Replace `tree.search(begin, end)` with `tree.overlap(begin, end)`. For point queries, use `tree.at(point)`.","cause":"Attempting to use the `search` method which was removed in version 3.0.0.","error":"AttributeError: 'IntervalTree' object has no attribute 'search'"},{"fix":"Upgrade `intervaltree` to version 3.2.1 or higher (`pip install --upgrade intervaltree`). If on 3.2.0, you can manually install the dependency: `pip install sortedcontainers`.","cause":"The `sortedcontainers` package, a required dependency, was not installed. This was a known packaging bug in version 3.2.0.","error":"ModuleNotFoundError: No module named 'sortedcontainers'"},{"fix":"Ensure `tree.add()` is called with a single `Interval` object (e.g., `tree.add(Interval(1, 2))`). If adding multiple intervals, use `tree.update(iterable_of_intervals)`.","cause":"This can happen if you pass multiple arguments to `tree.add()` or if you try to use `tree.extend()` (which was removed) expecting it to accept multiple `Interval` objects directly without an iterable.","error":"TypeError: 'int' object is not iterable"}]}