import java.lang.*;

class Collection{
	//Collection has the following attributes:

	//pseudo-root, key value -infinity, right pointer to root
	private Node header;
	//global variables used for top-down deletion to keep track of history
	private static Node great;
	private static Node grand;
	private static Node parent;
	private static Node current;
	//pseudo-node to mark the end of the tree
	private static Node NullNode;
	//define negative infinity
	private static final int neg_inf = (int)( Double.NEGATIVE_INFINITY );

/* constructor for Collection 
PostCondition: 		Collection != null;
			returns a object - the empty collection 
*/
public Collection(){
	//NullNode is black and it's children points back to itself
	NullNode = new Node( false );
	NullNode.SetLeft(NullNode);
	NullNode.SetRight(NullNode);
	//header is a black node with data negative infinity, right pointer to real root
	header = new Node(new CompInt(neg_inf));
	header.SetColorBlack();
	header.SetRight(NullNode);
	header.SetLeft(NullNode);	
	//global pointers set to null	
	great = grand = parent = current = null;
}


/* Find an item in a collection
PreCondition:		object operating on is a valid collection 
			created by the constructor(new Collection);
			data != null;
PostCondition:		returns the Comparable object identified by "data" if one exists
			otherwise returns null;
*/
public Comparable FindInCollection( Comparable data ){
	Node x;
	x = FindNode(data);
	if (x != null)
	return x.Data();
	else return null;
	}

/* Add an item to a Collection
PreCondition:		object operating on is a valid collection 
			created by the constructor(new Collection);
			data != null;
PostCondition: 		item has been added to the collection;
			return true;
			otherwise out of memory space, return false;
*/
public boolean AddToCollection( Comparable data ){
	if(InsertNode( data ))
		return true;
	else return false;
}


/* Delete an item from a collection
PreCondition:		object operating on is a valid collection 
			created by the constructor(new Collection);
			data != null;
PostCondition:		if item is found in collection, it has been deleted 
			successfully and returning true; 
			otherwise return false; 
*/
public boolean DeleteFromCollection( Comparable data ){
	Node x;
	x = FindNode( data );
	if (x==null){	
		return false;
	}
	DeleteNode(x);
	return true;
}


/* Find Node containding data */
/* used by FindInCollection, otherwise mainly used for debugging purposes, 
	when we need to find out various elements associated with a node 
PreCondition:		object operating on is a valid collection 
			created by the constructor(new Collection);
			data != null;
PostCondition:		returns the node containing "data" if one exists
			otherwise returns null
*/
public Node FindNode(Comparable data){
	current = header;
	while(current != NullNode)
	{
		if (current.Data().Compare(data) == 0)
			return (current);
		else 
			if(current.Data().Compare(data) == 1)
				current = current.Left();
			else 	current = current.Right();
	} 	
	return null;
}



/* obtain the blackheight of the tree */
/* made public for debugging purposes 
PreCondition:		object operating on is a valid collection 
			created by the constructor(new Collection);
PostCondition:		returns the number of black nodes on the right most path
*/
public int BlackHeight(){
	Node x;
	int height = 0;
	
	x = header.Right();
	while (x != NullNode){
 		x = x.Right();
		if (x.IsBlack()) height++;

	}
	return height; 	
}


/* made public for debugging purposes 
PreCondition:		object operating on is a valid collection 
			created by the constructor(new Collection);
PostCondition:		returns the number of red nodes on the right most path
*/
public int RedCount(){
        Node x;
        int redct = 0;

        x = header.Right();
        while (x != NullNode){
                x = x.Right();
                if (x.IsRed()) redct++;

        }
        return redct;
}


/* made public for debugging purposes 
PreCondition:		object operating on is a valid collection 
			created by the constructor(new Collection);
			x != null;
PostCondition:		prints out various information about the particular node
			such as:
				data
				color
				left child
				right child
				parent
				whether it is the root or not
*/
public void PrintNode(Node x){
        if (x == NullNode) System.out.println("x is a sentinel node.");
        else{
              	System.out.print("Node has data: "); 
		System.out.println(x.Data().toString());
		System.out.print("Color: ");
		if(x.IsBlack()) System.out.println("Black");
		else System.out.println("Red");
 
                System.out.print("Left child:  ");
               	if (x.Left() == NullNode) System.out.println(" is a sentinel node.");
		else System.out.println(x.Left().Data().toString());
		System.out.print("Color: ");
                if(x.Left().IsBlack()) System.out.println("Black");
                else System.out.println("Red");		

		System.out.print("Right child:  ");
		if (x.Right() == NullNode) System.out.println(" is a sentinel node.");
                else System.out.println(x.Right().Data().toString());
		System.out.print("Color: ");            
                if(x.Right().IsBlack()) System.out.println("Black");
                else System.out.println("Red");

		System.out.print("Parent:  ");
		if(x.Parent() != header){
		
                	if (x.Parent() == NullNode) System.out.println(" is a sentinel node.");
                	else System.out.println(x.Parent().Data().toString());
			System.out.print("Color: ");            
                	if(x.Parent().IsBlack()) System.out.println("Black");
                	else System.out.println("Red");
		}	
		else System.out.println("Null parent ie. root reached!");
        }
}



/*////////////////////////PRIVATE METHODS //////////////////////////*/

/* allocate node for data and insert in tree */
// top-down insertion
private boolean InsertNode(Comparable data){
	
	/* find where node belong */
	current = great = grand = parent = header;
	NullNode.SetData(data);

	while (current.Data().Compare(data)!=0 ){
		great = grand;
		grand = parent;
		parent = current;
		if (data.Compare( current.Data()) == -1) current = current.Left();
		else current = current.Right();
		//check if two red children; fix if so
		if( current.Left().IsRed()  && current.Right().IsRed() )
			HandleReorient( data );
		}
	
	if (current!=NullNode) return true;	
	/* setup new node */
	current = new Node(data);
	
	if (current == null) return false; 	
	current.SetLeft(NullNode);
	current.SetRight(NullNode);
	current.SetParent(parent);

	/* insert node in tree */
	if (parent!=header){
		if (data.Compare( parent.Data()) == -1)
			parent.SetLeft(current);
		else parent.SetRight(current);
	}
	else header.SetRight(current);
	HandleReorient( data );
	return (true);

}


//private routine that is called during an insertion
//if a node has two red children
private void HandleReorient(Comparable data){
	//do the color flip
	current.SetColorRed();
	current.Left().SetColorBlack();
	current.Right().SetColorBlack();
	
	if(parent.IsRed()){		//have to rotate
		grand.SetColorRed();
		if((data.Compare(grand.Data())==-1)!=(data.Compare(parent.Data())==-1))
			parent = Rotate( data, grand );
		current = Rotate( data, great );
		current.SetColorBlack();
	}
	header.Right().SetColorBlack();		//make root black
}

//routine to choose and perform 1 of 4 types of rotations
private Node Rotate( Comparable data, Node parent ){
	Node x;

	if (data.Compare(parent.Data())==-1){
		if( data.Compare(parent.Left().Data())==-1){
			x = RotateWithLeft(parent.Left());
			parent.SetLeft(x);
			return x;
		}
		else{
			x = RotateWithRight(parent.Left());
			parent.SetLeft(x);
			return x;
		}
	}
	else{ 
		if(data.Compare(parent.Right().Data())==-1){
			x = RotateWithLeft(parent.Right());
			parent.SetRight(x);
			return x;
		}
		else{
			x = RotateWithRight(parent.Right());
			parent.SetRight(x);
			return x;
		}
	}
}		

//rotations needed for top-down insertion
private Node RotateWithLeft(Node x){
	Node y = x.Left();
	x.SetLeft(y.Right());
	if (y.Right() != NullNode)
		y.Right().SetParent(x);

	/* establish y.parent link */
        if (y != NullNode) y.SetParent(x.Parent());
        if (x.Parent() != header){
                if (x == x.Parent().Right())
                        x.Parent().SetRight(y);
                else
                        x.Parent().SetLeft(y);
        }
        else header.SetRight(y);


        /* link x and y */
        y.SetRight(x);
        if (x != NullNode) x.SetParent(y);
	return y;
}


private Node RotateWithRight(Node x){
	Node y = x.Right();
	x.SetRight(y.Left());
	if (y.Left() != NullNode)
		y.Left().SetParent(x);
		
	/* establish y.parent link */
	if (y != NullNode) y.SetParent(x.Parent());
	if (x.Parent() != header){
		if (x == x.Parent().Left())
			x.Parent().SetLeft(y);
		else 
			x.Parent().SetRight(y);
	}
	else header.SetRight(y);

	
	/* link x and y */
	y.SetLeft(x);
	if (x != NullNode) x.SetParent(y);	
	return y;
}


/* delete node z from tree */
private void DeleteNode(Node z){

	Node x;
	Node y;
	
	if ( z == NullNode) return;
	
	if ( z.Left() == NullNode || z.Right() == NullNode){
		/* y has a sentinel node as a child */
		y = z;
	}
	else{
		/* find tree successor with a sentinel node as a child */
		y = z.Right();
		while ( y.Left() != NullNode) y = y.Left();
	}
	
	/* x is y's only child */
	if (y.Left() != NullNode)
		x = y.Left();
	else x = y.Right();

	/* remove y from the parent chain */
	x.SetParent(y.Parent());
	if (y.Parent() != header){
		if (y == y.Parent().Left())
			y.Parent().SetLeft(x);
		else y.Parent().SetRight(x);
	}
	else header.SetRight(x);
	
	if (y != z) z.SetData(y.Data());
	
	if (y.IsBlack()) DeleteFixup(x);
	
}


//rotations needed for deletefixup - normal bottom up deletion
/* Rotate node x to left */
private void RotateLeft(Node x){
	
	Node y = x.Right();
	
	/* establish x.right link */
	x.SetRight(y.Left());
	if (y.Left() != NullNode)
		y.Left().SetParent(x);
		
	/* establish y.parent link */
	if (y != NullNode) y.SetParent(x.Parent());
	if (x.Parent() != header){
		if (x == x.Parent().Left())
			x.Parent().SetLeft(y);
		else 
			x.Parent().SetRight(y);
	}
	else header.SetRight(y);

	
	/* link x and y */
	y.SetLeft(x);
	if (x != NullNode) x.SetParent(y);
}

/* Rotate node x to right */
private void RotateRight(Node x){

	Node y = x.Left();
	
	/* establish x.left link */
	x.SetLeft(y.Right());
	if (y.Right() != NullNode)
		y.Right().SetParent(x);

	/* establish y.parent link */
        if (y != NullNode) y.SetParent(x.Parent());
        if (x.Parent() != header){
                if (x == x.Parent().Right())
                        x.Parent().SetRight(y);
                else
                        x.Parent().SetLeft(y);
        }
        else header.SetRight(y);


        /* link x and y */
        y.SetRight(x);
        if (x != NullNode) x.SetParent(y);

}

/* maintain red-black tree balance after deleting node x */
private void DeleteFixup(Node x){

        while (x != header.Right() && x.IsBlack()){	
                if (x == x.Parent().Left()){
                        Node w = x.Parent().Right();
                        if (w.IsRed()){
				w.SetColorBlack();
                                x.Parent().SetColorRed();
                       		RotateLeft(x.Parent());
				w = x.Parent().Right();
			}
                        if (w.Left().IsBlack() && w.Right().IsBlack()){
				w.SetColorRed();
				x = x.Parent();
			}
			else{
                                if (w.Right().IsBlack()){
                                       	w.Left().SetColorBlack();
					w.SetColorRed();
					RotateRight(w);
					w = x.Parent().Right();
                                }
               			
				if (x.Parent().IsBlack()){
					w.SetColorBlack();
				}
				else {
					w.SetColorRed();
				}	
				x.Parent().SetColorBlack();
				w.Right().SetColorBlack();
				RotateLeft(x.Parent());
				x = header.Right();
		        }
                }
                else{
       			Node w = x.Parent().Left();
                        if (w.IsRed()){
                                w.SetColorBlack();
                                x.Parent().SetColorRed();
                                RotateRight(x.Parent());
                                w = x.Parent().Left();
                        }
                        if (w.Right().IsBlack() && w.Left().IsBlack()){
                                w.SetColorRed();        
                                x = x.Parent(); 
			}       
                        else{   
                                if (w.Left().IsBlack()){
                                        w.Right().SetColorBlack();
                                        w.SetColorRed();
                                        RotateLeft(w);
                                        w = x.Parent().Left();
				}
                                
                                if (x.Parent().IsBlack()){
					w.SetColorBlack();
				}
                                else {
					w.SetColorRed();
				}
				x.Parent().SetColorBlack();
                                w.Left().SetColorBlack();
                                RotateRight(x.Parent());
                                x = header.Right();
                        }
		}
 
        }
        x.SetColorBlack();

}




}