/*
 * @(#)RedBlackTree.java	1.0 2004/06/09
 */

import java.io.*;
   
/**
 * A red-black tree class that implements the Indexable interface.
 * @see Indexable
 */
public abstract class RedBlackTree implements Indexable, Serializable {
	
	/** A dummy node representing the special value NIL */
	protected final RedBlackNode NIL = new RedBlackNode(null, RedBlackNode.BLACK);

	/**
	 * The root of the tree. It should never be
	 * null. root = NIL when the tree is empty.
	 */
	protected RedBlackNode root = NIL;

	/** Checks if the tree is empty */
	public boolean isEmpty() {
		return root == NIL;
	}
	
	/** Returns the size of the tree. */
	public long size() {
		return recordCount();
	}
	
	/** Returns the number of records in the tree */
	public long recordCount() {
		return nodeCount(root);
	}
	
	/** Returns the number of nodes in the tree */
	public int nodeCount() {
		return nodeCount(root);
	}
	
	/** Returns the number of nodes in the tree rooted at r */
	public int nodeCount(RedBlackNode r) {
		if (r == null)
			throw new NullPointerException("There is a non-NIL terminal node.");
		System.out.println(r.toString());
		return ((r == NIL) ? 0:1 + nodeCount(r.leftChild)
			+ nodeCount(r.rightChild));
			
	      /* alternatively, you can also use:
		return ((getRecordKey(r.record) == null) ? 0:1 + nodeCount(r.leftChild)
			+ nodeCount(r.rightChild));
		*/
	}

	/**
	 * Inserts Object x into the tree. If x is
	 * already in the tree, the existing data is updated by
	 * replacing it with x.
	 *
	 * @exception throws a ClassCastException if
	 *            validateRecord(x) is false.
	 */
	public void insert(Object x) throws ClassCastException {
		if (!validateRecordClass(x))
			throw new ClassCastException("Wrong record type");
			
		RedBlackNode n = new RedBlackNode(x, RedBlackNode.RED);
		insert(n);
	}
	
	/** Insert node n into the tree */
	public void insert(RedBlackNode n) {
		// add your code here
	}

	/**
	 * Deletes x from the container, where getRecordKey(x) = key.
	 *
	 * @return The object that was deleted from the container.
	 * @exception throws an IndexOutOfBoundsException if
	 *            the specified record is not in the container.
	 *	      NOTE: the exception's message MUST explain
	 *            the reason for throwing the excpetion. e.g.,
	 *            "Key = NNN is not in the tree."
	 */
	public Object delete(Comparable key) throws IndexOutOfBoundsException {
		// add your code here
		// MUST throw IndexOutOfBoundsException if the record
		// is not in the tree!
		
		// Must return the deleted object!
		return new Object();
	}
	
	/** 
	 * Returns an node n such that getRecordKey(n.record) = key 
	 * or null if there is no such a node. 
	 */
	protected RedBlackNode searchNode(Comparable key) {
		// add your code here
		return null;
	}

	/** 
	 * Returns an Object x such that getRecordKey(x) = key 
	 * or null if there is no such a node.
	 */
	public Object search(Comparable key) {
		RedBlackNode n = searchNode(key);
		return (n != null) ? n.record:null;
	}

	/**
	 * Provides a text version of the elements stored in the tree.
	 * It traverses the tree in PREORDER (i.e. current node first,
	 * then left sub-tree, then right sub-tree)
	 */
	public void printTree() {
		printSubtree(root, 0);
	}

	/**
	 * Prints the subtree rooted at 'r' in PREORDER
	 * @param r Root of the subtree.
	 * @param level Level of identation (left whit spaces).
	 */
	public void printSubtree(RedBlackNode r, int level) {
		if (r != null) {				
			for (int i = 0; i < level; i++)
				System.out.print("  ");
			
			System.out.println(r);
			printSubtree(r.leftChild, level + 1);
			printSubtree(r.rightChild, level + 1);
		}
	}

	/** Returns true if the tree is a valid red-black tree */
	public boolean isRedBlackTree() {
		return isRedBlackTree(root);
	}

	/** Returns true if the tree rooted at t is a valid red-black tree */
	public boolean isRedBlackTree(RedBlackNode t) {
        final int RED = RedBlackNode.RED;
        final int BLACK = RedBlackNode.BLACK;

        // A null tree is a red-black tree
        if (t == null)
			return true;

        // A tree with only one NIL node (ie, one with null key)
        // is a red-black tree
        if (getRecordKey(t.record) == null) {
			t.blackHeight = 0; // base case of recursion
			return true;
        }

        // A not NIL node that has no left or right children
        // is not a red-black tree
        if (t.leftChild == null || t.rightChild == null)
			return false;

        // We check the color configuration of the node and its children
        if (t.getColor() == RED &&
			(t.leftChild.getColor() != BLACK ||
				t.rightChild.getColor() != BLACK)) {
			return false;
        }

        // Recursively check left children
        if (!isRedBlackTree(t.leftChild))
			return false;

        // Recursively check right children
        if (!isRedBlackTree(t.rightChild))
			return false;

        // Use the blackHeight member variable in the RedBlackNode
        // to check the tree structure
        int leftBlackHeight, rightBlackHeight;

        if (t.leftChild.getColor() == BLACK)
			leftBlackHeight = t.leftChild.blackHeight + 1;
        else
			leftBlackHeight = t.leftChild.blackHeight;

        if (t.rightChild.getColor() == BLACK)
			rightBlackHeight = t.rightChild.blackHeight + 1;
        else
			rightBlackHeight = t.rightChild.blackHeight;

        if (leftBlackHeight == rightBlackHeight) {
			t.blackHeight = leftBlackHeight;
			return true;
        }

        return false;
   }


}