package bst;

import java.util.Arrays;

public class BST {

	protected BSTNode root;
	protected int size;

	public boolean isEmpty() {
		return root == null;
	}

	public void insert(int data) {
		if (this.isEmpty()) {
			this.root = new BSTNode(data);
		} else {
			this.insert(this.root, data);
		}
		this.size++;
	}

	private void insert(BSTNode actual, int data) {
		if (data >= actual.data) {
			if (actual.right == null) {
				actual.right = new BSTNode(data);
				actual.right.parent = actual;
			} else {
				this.insert(actual.right, data);
			}
		} else {
			if (actual.left == null) {
				actual.left = new BSTNode(data);
				actual.left.parent = actual;
			} else {
				this.insert(actual.left, data);
			}
		}
	}

	public int[] preOrder() {
		int[] array = new int[this.size];
		int[] idx = new int[] { 0 };

		if (!this.isEmpty()) {
			this.preOrderSteps(this.root, array, idx);
		}

		return array;
	}

	private void preOrderSteps(BSTNode actual, int[] array, int[] idx) {
		array[idx[0]++] = actual.data;

		if (actual.left != null) {
			this.preOrderSteps(actual.left, array, idx);
		}

		if (actual.right != null) {
			this.preOrderSteps(actual.right, array, idx);
		}
	}

	public void simpleBalance() {
		if (this.root.left != null && this.root.right != null) {
			System.out.println("balanceada");
		} else if (this.root.right != null) {
			if (this.root.right.right != null) {
				this.leftRotation(this.root);
			} else if (this.root.right.left != null) {
				this.rightRotation(this.root.right);
				this.leftRotation(this.root);
			}
		} else if (this.root.left != null) {
			if (this.root.left.left != null) {
				this.rightRotation(this.root);
			} else if (this.root.left.right != null) {
				this.leftRotation(this.root.left);
				this.rightRotation(this.root);
			}
		}
	}

	private void leftRotation(BSTNode node) {
		System.out.println("rot_esq(" + node.data + ")");

		if (node == this.root) {
			this.root = node.right;
			node.right.parent = null;
		} else {
			if (node.parent.right == node) {
				node.parent.right = node.right;
			} else {
				node.parent.left = node.right;
			}
			node.right.parent = node.parent;
		}

		node.parent = node.right;
		node.right = node.parent.left;
		node.parent.left = node;

		if (node.right != null) {
			node.right.parent = node;
		}

		System.out.println(this);
	}

	private void rightRotation(BSTNode node) {
		System.out.println("rot_dir(" + node.data + ")");

		if (node == this.root) {
			this.root = node.left;
			node.left.parent = null;
		} else {
			if (node.parent.left == node) {
				node.parent.left = node.left;
			} else {
				node.parent.right = node.left;
			}
			node.left.parent = node.parent;
		}

		node.parent = node.left;
		node.left = node.parent.right;
		node.parent.right = node;

		if (node.left != null) {
			node.left.parent = node;
		}

		System.out.println(this);
	}

	@Override
	public String toString() {
		return Arrays.toString(this.preOrder());
	}

}