<commit_before>==============
PyIntervalTree
==============

    NB: This is a straight fork of `PyIntervalTree by <NAME> <https://github.com/MusashiAharon/PyIntervalTree>`_.
    This fork adds some tests and registers the package at PyPI as `PyIntervalTree <https://pypi.python.org/PyIntervalTree>`_. Some further maintenance or updates might still be possible, and eventually the fork could merge into the original (depending on the original author's opinion).
    
A mutable, self-balancing interval tree. 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.


Installation
------------

The easiest way to install most Python packages is via ``easy_install`` or ``pip``::

    $ pip install PyIntervalTree

Features
--------

* 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)``
  * ``tree.discardi(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()``
  * ``tree.end()``

* 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
* Hashable
* Pickle-friendly
* Automatic AVL balancing
    
Examples
--------

* Getting started::

        from intervaltree import Interval, IntervalTree
        t = IntervalTree()

* Adding intervals - you don't have to use strings!::

        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 ``Interval``'s:

  We could have made the same tree this way::

        ivs = [ [1,2], [4,7], [5,9] ]
        ivs = map( lambda begin,end: Interval(begin, end, "%d-%d" % (begin,end), 
                   *zip(*ivs) )
  
        t = IntervalTree(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())

Based on
--------

  * Eternally Confuzzled's `AVL tree <http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx>`_
  * Wikipedia's `Interval Tree <http://en.wikipedia.org/wiki/Interval_tree>`_
  * Heavily modified from Tyler Kahn's `Interval Tree implementation in Python <http://forrst.com/posts/Interval_Tree_implementation_in_python-e0K>`_ (`GitHub project <https://github.com/tylerkahn/intervaltree-python>`_)

Copyright
---------

  * `<NAME> <https://github.com/MusashiAharon/PyIntervalTree>`_
  * This particular fork by `<NAME> <https://github.com/konstantint/PyIntervalTree>`_ so far introduces purely cosmetic modifications.<commit_msg>Commit to trigger Travis build<commit_after>==============
PyIntervalTree
==============

    NB: This is a straight fork of `PyIntervalTree by Chaim-<NAME> <https://github.com/MusashiAharon/PyIntervalTree>`_.
    This fork adds some tests and registers the package at PyPI as `PyIntervalTree <https://pypi.python.org/PyIntervalTree>`_. Some further maintenance or updates might still be possible, and eventually the fork could merge into the original (depending on the original author's opinion).
    
A mutable, self-balancing interval tree. 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.


Installation
------------

The easiest way to install most Python packages is via ``easy_install`` or ``pip``::

    $ pip install PyIntervalTree

Features
--------

* 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)``
  * ``tree.discardi(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()``
  * ``tree.end()``

* 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
* Hashable
* Pickle-friendly
* Automatic AVL balancing
    
Examples
--------

* Getting started::

        from intervaltree import Interval, IntervalTree
        t = IntervalTree()

* Adding intervals - you don't have to use strings!::

        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 ``Interval``'s:

  We could have made the same tree this way::

        ivs = [ [1,2], [4,7], [5,9] ]
        ivs = map( lambda begin,end: Interval(begin, end, "%d-%d" % (begin,end), 
                   *zip(*ivs) )
  
        t = IntervalTree(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())

Based on
--------

  * Eternally Confuzzled's `AVL tree <http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx>`_
  * Wikipedia's `Interval Tree <http://en.wikipedia.org/wiki/Interval_tree>`_
  * Heavily modified from <NAME>'s `Interval Tree implementation in Python <http://forrst.com/posts/Interval_Tree_implementation_in_python-e0K>`_ (`GitHub project <https://github.com/tylerkahn/intervaltree-python>`_)

Copyright
---------

  * `<NAME> <https://github.com/MusashiAharon/PyIntervalTree>`_
  * This particular fork by `<NAME> <https://github.com/konstantint/PyIntervalTree>`_. See changes in CHANGELOG.txt.
{'fraction_non_alphanumeric': 0.16570347798676052, 'fraction_numerical': 0.016181569822423032, 'mean_word_length': 3.0143399409531844, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 26, 'https://': 10, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '39995', 'n_tokens_mistral': 3328, 'n_tokens_neox': 3160, 'n_words': 888}