split ( p : like first_place;
	  before, after : BOX [ like Current ] ) is
    require
      nonvoid : p /= Void and before /= Void and after /= Void
    local
      q, r, s : like first_place
      rnk, next_rnk : INTEGER
      low, high, subtree : like Current
      left, right : like first_place
      p_less, next_p_less : BOOLEAN
    do
      calculate the rank of p
      initialise low and high using make_with_root
	on left and right subtrees at p.  Make_with_root
	ensures the new roots are black, adjusting rb-rank
	if necessary.

      Work up the tree from p.parent.  You must always
      test whether the current node q on the path is less
      than or greater than p.  Say r is on the path and q
      its parent.  If r is a left child then p is left of
      q, so q's right subtree toes to `high.'  Otherwise
      q's left subtree goes to `low.'  Computing the rank
      of these subtrees is tricky.
      
---- finally
      setroot (Void, 0)
      before.put ( low )
      after.put ( high )
    end