package jdsl.tree;

import jdsl.Position;
import jdsl.InvalidPositionException;
import jdsl.tree.BinaryTree;

public class LinkedBinaryTree implements BinaryTree {

    class Node implements Position {

	InternalNode parent = null;

	Object element      = null;
	Object container    = null;

	public Object element( ) {
	    return element;
	}

	public Object container( ) {
	    return container;
	}
    }

    class InternalNode extends Node {
	
	Node left   = null;
	Node right  = null;
    }

    class ExternalNode extends Node {
    }


    Node root;

    public LinkedBinaryTree( ) {
	root = new ExternalNode( );
    }


    public boolean isRoot(Position pos) throws
        InvalidPositionException {

	try {
	    return ((Node) pos) == root;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException( );
	}
    }

    public boolean isInternal(Position pos) throws
	InvalidPositionException {

	try {
	    return ((Node) pos) instanceof InternalNode;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException( );
	}
    }

    public boolean isExternal(Position pos) throws
	InvalidPositionException {

	try {
	    return ((Node) pos) instanceof ExternalNode;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException( );
	}
    }


    public Position root( ) {
	return root;
    }

    public  Position parent(Position pos) throws
	InvalidPositionException {

	try {
	    return ((Node) pos).parent;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException ( );
	}
    }

    public Position leftChild(Position pos) throws 
	InvalidPositionException {

	try {
	    return ((InternalNode) pos).left;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException ( );
	}
    }

    public Position rightChild(Position pos) throws
	InvalidPositionException {

	try {
	    return ((InternalNode) pos).right;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException ( );
	}
    }


    public Position sibling(Position pos) throws
        InvalidPositionException {

	try {
	    InternalNode parent = ((InternalNode) pos).parent;

	    return (parent.left == pos) ? parent.right : parent.left;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException( );
	}
	catch (NullPointerException e) {
	    throw new InvalidPositionException("sibling( ) called on root");
	}
    }


    public void swap(Position one, Position two) throws
	InvalidPositionException {

	try {
	    Object tmp           = ((Node) one).element;
	    ((Node) one).element = ((Node) two).element;
	    ((Node) two).element = tmp;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException( );
	}
	catch (NullPointerException e) {
	    throw new InvalidPositionException("Null Position");
        }
    }

    public Object replace(Position pos, Object item) throws
	InvalidPositionException {

	try {
	    Object ret           = ((Node) pos).element;
	    ((Node) pos).element = item;

	    return ret;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException ( );
	}
    }

    public Position expandExternal(Position pos) throws
	InvalidPositionException {

	try {
	    ExternalNode left = (ExternalNode) pos;
	    InternalNode centr = new InternalNode( );
	    ExternalNode right = new ExternalNode( );

	    centr.parent = left.parent;
	    centr.left   = left;
	    centr.right  = right;

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

	    return centr;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException("Not an External Node");
	}
    }

    public Object removeAboveExternal(Position pos) throws
	InvalidPositionException {

	try {
	    ExternalNode child = (ExternalNode) pos;
	    InternalNode paren =  child.parent;
	    Node         siblg = (paren.left == child) ? 
		paren.right : 
		paren.left  ;

	    siblg.parent = paren.parent;

	    if (siblg.parent != null) {
		if (siblg.parent.left == paren)
		    siblg.parent.left  = siblg;
		else
		    siblg.parent.right = siblg;
	    }
	    else
		root = siblg;

	    child.parent = null;

	    paren.parent = null;
	    paren.left   = null;
	    paren.right  = null;
	    
	    return paren.element;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException("Not an External Node");
	}
	catch (NullPointerException e) {
	    throw new InvalidPositionException(
		"removeAboveExternal( ) called on root" );
	}
    }
}