Re: [Pika-dev] fsplay_delete is b0rked

[Tom Lord]

    > From: Tom Lord <address@hidden>

    >     > 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 :-)


Ugh.  It's worse than that.

I realized when I woke up this morning that we need an "insert subtree
that has children" operation anyway -- for "insert substring".

I _think_ that's can be done no better than a combination of a raise
and two simple inserts.  E.g. to insert:




                T1
              /    \
            _T1L    _T1R


on the right of the root in:


                T2
              /    \
            _T2L   _T2R


it's:

        tmp =     T2'
                /    \
              _T2L    T1
                    /    \
                  _T1L   _T1R


        tmp2 = raise_rightmost (tmp)

             ==         _T2R_last
                       /        \
               {_T2L .. _T2R-1} nil


        answer =      _T2R_last'
                     /        \
           {_T2L .. _T2R-1}    _T1R


-t