Re: [Pika-dev] fsplay_delete is b0rked

[Tom Lord]

    > From: Matthew Dempsky <address@hidden>

    >       /* delete
    >        * 
    >        * Have:
    >        * 
    >        *        T
    >        *     /     \
    >        *   _Tl     _Tr
    >        *
    >        * and want to remove T.
    >        * 
    >        * Removing T is the same as inserting _Tr after _Tl.
    >        */

    > Yes and no... it would be if insert_after preserved the children of
    > the node to be inserted, but it doesn't.  As it is, delete drops all
    > of Tr's children.

    > The two possible solutions to this are either to rewrite insert_after
    > (and insert_before for consistancy) to protect children from being
    > lost or add a new operation fsplay_join.  I'm leaning towards the
    > latter and plan on writing it unless someone thinks the
    > insert_(before|after) modification would be better.

Gah.  You're right.  I was (probably) being too cute there.  The
insert_* routines presume that the new tree is just a single node with
no children.

Please deal with it this way: spend a little time trying to figure out
what the generalization of the insert_* routines is (to deal with
children).  If it's simple, use that.  If it needs to call raise, then
screw it -- go with your current plan.  If we later discover you get
it wrong -- we'll force you to blush and then fix it :-)

-t