package edu.princeton.cs.algs4.growingtree.demos;
import java.awt.Color;
import java.util.Random;

import edu.princeton.cs.algs4.growingtree.interfaces.IAlgorithmNode;
import edu.princeton.cs.algs4.growingtree.interfaces.IInsertOperator;
import edu.princeton.cs.algs4.growingtree.interfaces.IInsertingNode;
import edu.princeton.cs.algs4.growingtree.interfaces.INode;

/**
 * Left-Leaning Red Black Tree Insertion Operators
 * @author Josh Israel
 */

public class LLRBInsertion<P extends RBNodeProperties> extends LLRBOperator<P> implements IInsertOperator<P> {
	
	// Required for IInsertOperator<P>
	public void doInsert(IInsertingNode<P> root, INode<P> newNode) {
		if (newNode == null) { // inserting into an empty tree
			root.getNodeProperties().setColor(RBNodeProperties.BLACK);
			return;
		}
		
		insert(root, newNode); // recursive call that does the insertion work
		root.getRoot().getNodeProperties().setColor(RBNodeProperties.BLACK);
	}
	
	private void insert(IInsertingNode<P> pathNode,
									 INode<P> newNode) { 
		
        int cmp = newNode.compareTo(pathNode);
        if (cmp < 0) {
        	if (pathNode.getLeft() == null) {
        		newNode.getNodeProperties().setColor(RBNodeProperties.BLACK);
        		pathNode.insertLeft(newNode);
        		newNode.getNodeProperties().setColor(RBNodeProperties.RED);
        	}
        	else                     		insert(pathNode.getLeft(), newNode);
        }
        else if (cmp > 0) {
        	if (pathNode.getRight() == null) {
        		newNode.getNodeProperties().setColor(RBNodeProperties.BLACK);
        		pathNode.insertRight(newNode);
        		newNode.getNodeProperties().setColor(RBNodeProperties.RED);
        	}
        	else { insert(pathNode.getRight(), newNode); }
        }
        else { return; }
        
        IAlgorithmNode<P> h = pathNode;
        if (isRed(h.getRight()) && !isRed(h.getLeft()))  h = rotateLeft(h);
        if (isRed(h.getLeft()) && isRed(h.getLeft().getLeft())) h = rotateRight(h);
        if (isRed(h.getLeft()) && isRed(h.getRight())){
        	flipColors(h);
        }
        
        return;
    }
}