package eg.edu.alexu.csd.filestructure.avl;

public class AVLTree<T extends Comparable<T>> implements IAVLTree<T> {
	private Node<T> root;

	public AVLTree() {
		root = new Node<T>(null, null);
	}

	@Override
	public void insert(T key) {

		Node<T> cursor = null; // y
		Node<T> current = root; // x
		Node<T> newNode = new Node<T>(key, null); // z
		while (current != null && current.getValue() != null) {
			cursor = current;
			try {
				if (newNode.getValue().compareTo(current.getValue()) <= 0) {
					current = (Node<T>) current.getLeftChild();
				} else if (newNode.getValue().compareTo(current.getValue()) > 0) {
					current = (Node<T>) current.getRightChild();
				}
			} catch (NullPointerException ex) {
				break;
			}
		}

		newNode.setParent(cursor);
		if (cursor == null) {
			root = newNode;
		} else if (newNode.getValue().compareTo(cursor.getValue()) <= 0) {
			cursor.setLeftChild(newNode);
			// reBalance((Node<T>) cursor.getLeftChild());
		} else if (newNode.getValue().compareTo(cursor.getValue()) > 0) {
			cursor.setRightChild(newNode);
			// reBalance((Node<T>) cursor.getRightChild());
		}

	}

	// public void reBalance(Node<T> t) {
	// Node<T> parent = null; // up
	// Node<T> check = t;
	// Node<T> child = t;
	// boolean checkIsTheRoot = false;
	// while (check.hasParent()) {
	// child = check;
	// check = (Node<T>) check.getParent();
	// // parent = (Node<T>) check.getParent();
	//
	// int balanceFactor = check.getBalanceFactor();
	// if (balanceFactor == 2) {
	// if (check.hasParent())
	// parent = (Node<T>) check.getParent();
	// else
	// checkIsTheRoot = true;
	// if (child.getBalanceFactor() == 1) {
	// leftLeft(check, child, parent);
	// break;
	// } else if (child.getBalanceFactor() == -1) {
	// leftRight(check, child, parent);
	// break;
	// }
	// } else if (balanceFactor == -2) {
	// if (check.hasParent())
	// parent = (Node<T>) check.getParent();
	// else
	// checkIsTheRoot = true;
	// if (child.getBalanceFactor() == 1) {
	// rightLeft(check, child, parent);
	// break;
	// } else if (child.getBalanceFactor() == -1) {
	// rightRight(check, child, parent);
	// break;
	//
	// }
	// }
	// }
	// }
	//
	private void rightRight(Node<T> check, Node<T> child, Node<T> parent) {
		boolean right = false, noParent = false;
		check.setRightChild(null);
		child.setParent(null);
		if (parent == null)
			noParent = true;
		else if (parent.getValue().compareTo(check.getValue()) < 0)
			right = true;

		if (!noParent) {
			if (right)
				parent.setRightChild(child);
			else
				parent.setLeftChild(child);
		}
		if (child.hasLeftChild())
			check.setRightChild((Node<T>) child.getLeftChild());
		child.setLeftChild(check);
		check.setParent(child);
		if (check == root)
			root = child;
	}

	private void rightLeft(Node<T> check, Node<T> child, Node<T> parent) {
		Node<T> n = (Node<T>) child.getLeftChild();
		boolean right = false, noParent = false;
		if (parent == null)
			noParent = true;
		else if (parent.getValue().compareTo(check.getValue()) < 0)
			right = true;

		if (!noParent) {
			if (right)
				parent.setRightChild(n);
			else
				parent.setLeftChild(n);
		}
		n.setLeftChild(check);
		n.setRightChild(child);
	}

	private void leftRight(Node<T> check, Node<T> child, Node<T> parent) {
		Node<T> n = (Node<T>) child.getRightChild();
		boolean right = false, noParent = false;
		if (parent == null)
			noParent = true;
		else if (parent.getValue().compareTo(check.getValue()) < 0)
			right = true;

		if (!noParent) {
			if (right)
				parent.setRightChild(n);
			else
				parent.setLeftChild(n);
		}
		n.setLeftChild(child);
		n.setRightChild(check);
	}

	private void leftLeft(Node<T> check, Node<T> child, Node<T> parent) {
		boolean right = false, noParent = false;
		if (parent == null)
			noParent = true;
		else if (parent.getValue().compareTo(check.getValue()) < 0)
			// check is bigger than Parent
			right = true;
		if (!noParent) {
			if (right)
				parent.setRightChild(child);
			else
				parent.setLeftChild(child);
		}
		check.setLeftChild((Node<T>) child.getRightChild());
		child.setRightChild(check);
	}

	public Node<T> getNodes() {
		return this.root;
	}

	public void inOrder(Node root) {

		if (root != null) {
			inOrder((Node<T>) root.getLeftChild());
			System.out.println(root.getValue());
			inOrder((Node) root.getRightChild());
		}
	}

	private Node<T> minimum(Node<T> node) {
		if (!node.hasLeftChild())
			return node;
		return minimum((Node<T>) node.getLeftChild());

	}

	// private Node<T> getMySuccessor(Node<T> node) {
	// if (node.hasRightChild()) {
	// return this.minimum((Node<T>) node.getRightChild());
	// } else {
	// Node<T> carry = (Node<T>) node.getParent();
	// while (carry != null && ((Node<T>) node).equals((Node<T>)
	// carry.getRightChild())) {
	// node = carry;
	// carry = (Node<T>) node.getParent();
	// }
	// return carry;
	// }
	//
	// }

	private void transplant(Node<T> toBeRemoved, Node<T> toBePlanted) {
		Node<T> toBeRemovedParent = (Node<T>) toBeRemoved.getParent();
		if (!toBeRemoved.hasParent()) {
			root = toBePlanted;
			// reBalance(toBePlantedParent);
		} else if (toBeRemoved.equals(toBeRemovedParent.getLeftChild())) {
			toBeRemovedParent.setLeftChild(toBePlanted);
			// toBeRemoved.setLeftChild(null);

		} else {
			toBeRemovedParent.setRightChild(toBePlanted);
			// toBeRemoved.setRightChild(null);

		}
		toBeRemoved.setParent(null);
		if (toBePlanted != null) {
			Node<T> toBePlantedParent = (Node<T>) toBePlanted.getParent();

			if (toBePlantedParent.hasLeftChild() && toBePlantedParent.getLeftChild().equals(toBePlanted))
				toBePlantedParent.setLeftChild(null);
			else if (toBePlantedParent.hasRightChild())
				toBePlantedParent.setRightChild(null);
			toBePlanted.setParent(toBeRemovedParent);
			if (toBeRemoved.hasLeftChild()) {
				Node<T> leftOfToBeRemoved = ((Node<T>) toBeRemoved.getLeftChild());
				toBePlanted.setLeftChild(leftOfToBeRemoved);
				leftOfToBeRemoved.setParent(toBePlanted);
			}
			if (toBeRemoved.hasRightChild()) {
				Node<T> rightOfToBeRemoved = ((Node<T>) toBeRemoved.getRightChild());
				toBePlanted.setRightChild(rightOfToBeRemoved);
				rightOfToBeRemoved.setParent(toBePlanted);
			}
		}

	}

	@Override
	public boolean delete(T key) {
		if (!search(key))
			return false;

		Node<T> toBeDeleted = searchReturnsNode(key);
		if (!toBeDeleted.hasLeftChild()) {
			this.transplant(toBeDeleted, (Node<T>) toBeDeleted.getRightChild());
		} else if (!toBeDeleted.hasRightChild()) {
			this.transplant(toBeDeleted, (Node<T>) toBeDeleted.getLeftChild());
		} else {
			Node<T> node = minimum((Node<T>) toBeDeleted.getRightChild());
				this.transplant(toBeDeleted, node);
		}

		return true;
	}

	private Node<T> searchReturnsNode(T key, Node<T> node) {
		if (key.compareTo(node.getValue()) == 0)
			return node;
		if (key.compareTo(node.getValue()) < 0)
			return searchReturnsNode(key, (Node<T>) node.getLeftChild());
		else
			return searchReturnsNode(key, (Node<T>) node.getRightChild());

	}

	public Node<T> searchReturnsNode(T key) {
		return this.searchReturnsNode(key, root);
	}

	private boolean search(T key, Node<T> node) {
		if (node != null) {
			if (key.compareTo(node.getValue()) == 0)
				return true;
			if (key.compareTo(node.getValue()) < 0)
				return search(key, (Node<T>) node.getLeftChild());
			else
				return search(key, (Node<T>) node.getRightChild());
		}
		return false;

	}

	@Override
	public boolean search(T key) {
		return this.search(key, root);
	}

	@Override
	public int height() {
		if (root.getValue() == null) {
			return -1;
		} else {
			/*
			 * int leftH = root.getLeftHeight(); int rightH =
			 * root.getRightHeight(); if (leftH > rightH) return leftH; else
			 * return rightH;
			 */
			return Math.max(root.getLeftHeight(), root.getLeftHeight());
		}
	}

	@Override
	public INode<T> getTree() {
		return root;
	}

}