Skip to main content
Warning: You are using the test version of PyPI. This is a pre-production deployment of Warehouse. Changes made here affect the production instance of TestPyPI (testpypi.python.org).
Help us improve Python packaging - Donate today!

Editable interval tree data structure for Python 2 and 3

Project Description

A mutable, self-balancing interval tree for Python 2 and 3. Queries may be by point, by range overlap, or by range envelopment.

This library was designed to allow tagging text and time intervals, where the intervals include the lower bound but not the upper bound.

Installing

pip install intervaltree

Features

  • Supports Python 2.6+ and Python 3.2+
  • Initialize blank or from an iterable of Intervals in O(n * log n).
  • Insertions
    • tree[begin:end] = data
    • tree.add(interval)
    • tree.addi(begin, end, data)
    • tree.extend(list_of_interval_objs)
  • Deletions
    • tree.remove(interval) (raises ValueError if not present)
    • tree.discard(interval) (quiet if not present)
    • tree.removei(begin, end, data) (short for tree.remove(Interval(begin, end, data)))
    • tree.discardi(begin, end, data) (short for tree.discard(Interval(begin, end, data)))
    • tree.remove_overlap(point)
    • tree.remove_overlap(begin, end) (removes all overlapping the range)
    • tree.remove_envelop(begin, end) (removes all enveloped in the range)
  • Overlap queries:
    • tree[point]
    • tree[begin, end]
    • tree.search(point)
    • tree.search(begin, end)
  • Envelop queries:
    • tree.search(begin, end, strict=True)
  • Membership queries:
    • interval_obj in tree (this is fastest, O(1))
    • tree.containsi(begin, end, data)
    • tree.overlaps(point)
    • tree.overlaps(begin, end)
  • Iterable:
    • for interval_obj in tree:
    • tree.items()
  • Sizing:
    • len(tree)
    • tree.is_empty()
    • not tree
    • tree.begin() (the begin coordinate of the leftmost interval)
    • tree.end() (the end coordinate of the rightmost interval)
  • Restructuring
    • split_overlaps()
  • Copy- and typecast-able:
    • IntervalTree(tree) (Interval objects are same as those in tree)
    • tree.copy() (Interval objects are shallow copies of those in tree)
    • set(tree) (can later be fed into IntervalTree())
    • list(tree) (ditto)
  • Equal-able
  • Pickle-friendly
  • Automatic AVL balancing

Examples

  • Getting started

    from intervaltree import Interval, IntervalTree
    t = IntervalTree()
    
  • Adding intervals - any object works!

    t[1:2] = "1-2"
    t[4:7] = (4, 7)
    t[5:9] = {5: 9}
    
  • Query by point

    ivs = t[6]            # set([Interval(4, 7, (4, 7)), Interval(5, 9, {5: 9})])
    iv = sorted(ivs)[0]   # Interval(4, 7, (4, 7))
    
  • Accessing an Interval object

    iv.begin  # 4
    iv.end    # 7
    iv.data   # (4, 7)
    
  • Query by range

    Note that ranges are inclusive of the lower limit, but non-inclusive of the upper limit. So:

    t[2:4]    # set()
    

    But:

    t[1:5]    # set([Interval(1, 2, '1-2'), Interval(4, 7, (4, 7))])
    
  • Constructing from lists of Intervals

    We could have made a similar tree this way:

    ivs = [(1, 2), (4, 7), (5, 9)]
    t = IntervalTree(
        Interval(begin, end, "%d-%d" % (begin, end)) for begin, end in ivs
    )
    

    Or, if we don’t need the data fields:

    t = IntervalTree(Interval(*iv) for iv in ivs)
    
  • Removing intervals

    t.remove( Interval(1, 2, "1-2") )
    list(t)     # [Interval(4, 7, '4-7'), Interval(5, 9, '5-9')]
    
    t.remove( Interval(500, 1000, "Doesn't exist")) # raises ValueError
    t.discard(Interval(500, 1000, "Doesn't exist")) # quietly does nothing
    
    t.remove_overlap(5)
    list(t)     # []
    

    We could also empty a tree by removing all intervals, from the lowest bound to the highest bound of the IntervalTree:

    t.remove_overlap(t.begin(), t.end())
    

Future improvements

See the issue tracker on GitHub.

Based on

  • Eternally Confuzzled’s AVL tree
  • Wikipedia’s Interval Tree
  • Heavily modified from Tyler Kahn’s Interval Tree implementation in Python (GitHub project)
  • Incorporates modifications by konstantint
Release History

Release History

History Node

2.0.4b36

History Node

2.0.4b34

This version
History Node

1.0.3

History Node

1.0.2

History Node

1.0.1

History Node

1.0.0

History Node

2.0.3-3-g5651ad9-2.0.4

History Node

2.0.2-9-g672aa50-2.0.3

History Node

2.0.2-8-gb14792c-2.0.3

History Node

2.0.2-6-g5d3f86f-2.0.3

History Node

1.1.0-5-g9d55fd5-2.0.0

History Node

1.1.0-3-g469319a-1.1.1

Download Files

Download Files

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

File Name & Checksum SHA256 Checksum Help Version File Type Upload Date
intervaltree-1.0.3.tar.gz (23.9 kB) Copy SHA256 Checksum SHA256 Source Dec 10, 2014

Supported By

WebFaction WebFaction Technical Writing Elastic Elastic Search Pingdom Pingdom Monitoring Dyn Dyn DNS Sentry Sentry Error Logging CloudAMQP CloudAMQP RabbitMQ Heroku Heroku PaaS Kabu Creative Kabu Creative UX & Design Fastly Fastly CDN DigiCert DigiCert EV Certificate Rackspace Rackspace Cloud Servers DreamHost DreamHost Log Hosting