package edu.princeton.cs.algs4.growingtree.demos;

/**
 * Utility functions for AVL Tree Operators
 * @author Josh Israel
 */

import edu.princeton.cs.algs4.growingtree.framework.NodeProperties;
import edu.princeton.cs.algs4.growingtree.interfaces.IAlgorithmNode;

public class AVLOperator<P extends AVLNodeProperties> {
	/* This is the "balance factor" -- the maximum allowed height difference
     * between siblings.  Setting it to larger values, increases the worst-case
     * depth of the tree, but reduces the amount of rebalancing that happens.
     */
    private int B;
	
    public AVLOperator() {
    	this(1);
    }
    
    public AVLOperator(int balFactor) {
    	B = balFactor;
    }
    
	protected static <P extends NodeProperties> int height(IAlgorithmNode<P> n) {
		if (n == null) return NodeProperties.NULL_HEIGHT;
		else return n.getNodeProperties().getHeight();
	}
    
	protected IAlgorithmNode<P> bal(IAlgorithmNode<P> t) {
        IAlgorithmNode<P> l = t.getLeft();
        IAlgorithmNode<P> r = t.getRight();
        int hl = height(l);
        int hr = height(r);
        if (hl > hr + B) {
            if (height(l.getLeft()) >= height(l.getRight())) {
            	t.rotateRight();
                return l;
            } else {
            	IAlgorithmNode<P> lr = l.getRight();
            	l.rotateLeft();
            	t.rotateRight();
                return lr;
            }
        } else if (hr > hl + B) {
            if (height(r.getRight()) >= height(r.getLeft())) {
                t.rotateLeft();
                return r;
            } else {
            	IAlgorithmNode<P> rl = r.getLeft();
            	r.rotateRight();
            	t.rotateLeft();
                return rl;
            }
        } else {
            return t;
        }
    }
}