bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful

[Gerd Möllmann]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> Phew.  I'm not sure but I get the feeling that makes implementing a
>> successor function, let's say, challenging.
>
> I don't think it makes any difference in that respect, no.

The reason I find it challenging, and I'm sure now, is that I've written
the following code, and failed :-).

/* FIXME: This assumption is wrong.  Nodes on the left of P are <=,
   and nodes on the right are >=.  */

/* Value is the successor of interval node X in ascending order.  It
   is assumed that the tree is organized so that nodes < X are in
   X->left and nodes in X->right are >= X.  */

static struct interval_node *
in_order_successor (struct interval_node *x)
{
  if (x->right != ITREE_NULL)
    {
      /* X has a right child, which means X's right subtree has
         elements >= X.  Proceed to the left-most child in the right
         subtree, which is the smallest in that subtree.  */
      x = x->right;
      while (x->left != 0)
        x = x->left;
    }
  else
    {
      /* X's left subtree is uninteresting, because everything there
         is < X.  Therefore follow the parent chain.  If X is the
         parent's right child, this means the parent is < X,  We are
         looking for a parent that is >=.  */
      struct interval_node *y = x->parent;
      while (x == y->right)
        {
          x = y;
          y = y->parent;
        }

      /* If we found a parent that's >=, the parent is what we sought.
         Otherwise, X has arrived at the null node, whose right child
         is the sentinel node itself.  */
      if (x->right != y)
        x = y;
    }

  return x;
}

I tried to change the comments and/or modify the code for a tree like we
have (left subtree <=, right >=), and couldn't explain why it works,
but I also couldn't produce a counter-example that the existing tree
code actually can produce.  IOW, I couldn't prove anything.

P.S.

With the "all over the place" I indented to hint at the fact that the
tree is not a "normal" BST.  I should probably have said that directly,
sorry.