package jdsl.tree;

import jdsl.Position;
import jdsl.InvalidPositionException;

import jdsl.tree.LinkedBinaryTree;
import jdsl.tree.RestructurableBinaryTree;


public class RestructurableLinkedBinaryTree extends LinkedBinaryTree 
    implements RestructurableBinaryTree {

    public RestructurableLinkedBinaryTree( ) {
	super( );
    }

    protected Position doubleRotate(InternalNode c_node,
				    InternalNode l_node,
				    InternalNode r_node,
				    InternalNode parent,
				    InternalNode child ) {

	r_node.left         = c_node.right;
	r_node.left.parent  = r_node;

	l_node.right        = c_node.left;
	l_node.right.parent = l_node;

	c_node.parent = parent;

	if (c_node.parent != null) {
	    if (c_node.parent.left == child)
		c_node.parent.left  = c_node;
	    else 
		c_node.parent.right = c_node;
	}
	else 
	    root = c_node;

	c_node.left   = l_node;
	l_node.parent = c_node;
	c_node.right  = r_node;
	r_node.parent = c_node;

	return c_node;
    }

    public Position restructure(Position pos) throws
        InvalidPositionException {

	try {
	    InternalNode a = (InternalNode) pos;
	    InternalNode b = a.parent;
	    InternalNode c = b.parent;

	    if      (c.right == b && b.left  == a) 
		return doubleRotate(a, c, b, c.parent, c);

	    else if (c.left  == b && b.right == a) 
		return doubleRotate(a, b, c, c.parent, c);

	    else {

		if (c.right == b && b.right == a) {
		    c.right        = b.left;
		    b.left.parent  = c;
		    b.left         = c;
		}
		else {
		    c.left         = b.right;
		    b.right.parent = c;
		    b.right        = c;
		}

		b.parent = c.parent;
		c.parent = b;

		if (b.parent != null) {
		    if (b.parent.left == c)
			b.parent.left  = b;
		    else
			b.parent.right = b;
		}
		else 
		    root = b;

		return b;
	    }
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException("Not an Internal Node");
	}
	catch (NullPointerException e) {
	    throw new InvalidPositionException( );
	}
    }
}