Interval removal breaks this tree

[escalonn]

I ran chop on a few thousand IntervalTrees, and found that it crashed on several of them. Looking at the library code showed that remove failed to find Intervals where they were supposed to be. I tested until I found something more consistent.

Here, I add 9 intervals to an empty tree (in sorted order, so I could have used an iterable). Then, I remove the interval in the root node, leaving the tree with a broken node. Trying to remove one of the intervals left under that node then raises a KeyError.

>>> from intervaltree import IntervalTree
>>> t = IntervalTree()
>>> t.addi(860, 917, 1)
>>> t.addi(860, 917, 2)
>>> t.addi(860, 917, 3)
>>> t.addi(860, 917, 4)
>>> t.addi(871, 917, 1)
>>> t.addi(871, 917, 2)
>>> t.addi(871, 917, 3)
>>> t.addi(961, 986, 1)
>>> t.addi(1047, 1064, 1)
>>> t.addi(1047, 1064, 2)
>>> t.removei(961, 986, 1) # remove root node. t.verify() would fail now
>>> t.removei(871, 917, 3)
Node<871, depth=2, balance=0>
 Interval(860, 917, 1)
 Interval(860, 917, 2)
 Interval(860, 917, 3)
 Interval(860, 917, 4)
<:  Node<871, depth=1, balance=0>
     Interval(871, 917, 1)
     Interval(871, 917, 2)
     Interval(871, 917, 3)
>:  Node<1047, depth=1, balance=0>
     Interval(1047, 1064, 1)
     Interval(1047, 1064, 2)

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python2.7/site-packages/intervaltree/intervaltree.py", line 372, in removei
    return self.remove(Interval(begin, end, data))
  File "/usr/lib/python2.7/site-packages/intervaltree/intervaltree.py", line 361, in remove
    self.top_node = self.top_node.remove(interval)
  File "/usr/lib/python2.7/site-packages/intervaltree/node.py", line 211, in remove
    return self.remove_interval_helper(interval, done, should_raise_error=True)
  File "/usr/lib/python2.7/site-packages/intervaltree/node.py", line 248, in remove_interval_helper
    raise KeyError(interval)
KeyError: Interval(871, 917, 3)

That's with Python 2.7; the same behavior exists in Python 3.4.

[escalonn]

The problem seems to be with Node.pop_greatest_child.

When (961, 986, 1) is removed, the root node needs to be pruned. So the left subtree is asked for a replacement node with pop_greatest_child:

Node<961, depth=2, balance=0> # empty node, must be pruned
<:  Node<871, depth=1, balance=0> # this node provides its greatest child
     Interval(860, 917, 1)
     Interval(860, 917, 2)
     Interval(860, 917, 3)
     Interval(860, 917, 4)
     Interval(871, 917, 1)
     Interval(871, 917, 2)
     Interval(871, 917, 3)
>:  Node<1047, depth=1, balance=0>
     Interval(1047, 1064, 1)
     Interval(1047, 1064, 2)

This is what that method incorrectly returns as the greatest child node. See how the node's x_center is 871 while the intervals in its right subtree all overlap 871:

Node<871, depth=2, balance=1>
 Interval(860, 917, 1)
 Interval(860, 917, 2)
 Interval(860, 917, 3)
 Interval(860, 917, 4)
>:  Node<871, depth=1, balance=0>
     Interval(871, 917, 1)
     Interval(871, 917, 2)
     Interval(871, 917, 3)

Why? To create the greatest child node, it computes an expected x_center, and passes all intervals overlapping it to Node.from_intervals.[1] In the following few lines it appears to assume that the created node will have no children. But in our situation, the created node does have a child on the right, so changing its x_center on line 379 (from 860 to 871) is dangerous and in this case it breaks the node's invariants.

I'm not sure what the fix is. My best guess so far is that pop_greatest_child should not call Node.from_intervals, and instead simply initialize the node like this: child = Node(new_x_center, get_new_s_center()). I don't fully understand the implications of that change but I'll try and get the tests running and explore it.

[pkerpedjiev]

Is this fix going to be merged into a future release?

[pkerpedjiev]

Unfortunately, this issue doesn't seem to be completely fixed. I've attached a test file that yields another of the same error (based on @escalonn 's fix fork)

issue41a_test.txt

(The above file is actually python code but github won't allow me to upload it as such so I had to rename it to txt)

[escalonn]

Yes, even with my fork I’ve recently run into problems presenting in the same way (some trees failing in bulk chops). I haven’t spent the time to narrow down why.

[chaimleib]

fixed on dev and master branches

[PavelNovikov]

I encounter something similar with the new version. Apparently after rotation in pop_greatest_child()
new child's that intersects x_center is missed.
example.txt