package ua.nure.jfn.task4;

public class Tree<E extends Comparable<E>> {
	private Node<E> root;
	private int size;

	public Tree() {
		root = null;
		size = 0;
	}

	public boolean add(E element) {
		if (element == null) {
			return false;
		}

		int oldSize = size;
		root = addRecursive(root, element);
		return size > oldSize;
	}

	private Node<E> addRecursive(Node<E> node, E element) {
		if (node == null) {
			size++;
			return new Node<>(element);
		}

		int comparison = element.compareTo(node.data);

		if (comparison < 0) {
			node.left = addRecursive(node.left, element);
		} else if (comparison > 0) {
			node.right = addRecursive(node.right, element);
		}

		return node;
	}

	public void add(E[] elements) {
		if (elements == null) {
			throw new IllegalArgumentException("Array cannot be null");
		}
		for (E e : elements) {
			if (e != null) {
				add(e);
			}
		}
	}

	public boolean remove(E element) {
		if (element == null) {
			return false;
		}

		int oldSize = size;
		root = removeRecursive(root, element);
		return size < oldSize;
	}

	private Node<E> removeRecursive(Node<E> node, E element) {
		if (node == null) {
			return null;
		}

		int comparison = element.compareTo(node.data);

		if (comparison < 0) {
			node.left = removeRecursive(node.left, element);
		} else if (comparison > 0) {
			node.right = removeRecursive(node.right, element);
		} else {
			size--;

			if (node.left == null && node.right == null) {
				return null;
			}

			if (node.left == null) {
				return node.right;
			}

			if (node.right == null) {
				return node.left;
			}

			Node<E> successor = findMin(node.right);
			node.data = successor.data;
			node.right = removeRecursive(node.right, successor.data);
			size++;
		}

		return node;
	}

	private Node<E> findMin(Node<E> node) {
		while (node.left != null) {
			node = node.left;
		}
		return node;
	}

	public boolean contains(E element) {
		if (element == null) {
			return false;
		}
		return containsRecursive(root, element);
	}

	private boolean containsRecursive(Node<E> node, E element) {
		if (node == null) {
			return false;
		}

		int comparison = element.compareTo(node.data);

		if (comparison == 0) {
			return true;
		} else if (comparison < 0) {
			return containsRecursive(node.left, element);
		} else {
			return containsRecursive(node.right, element);
		}
	}

	public int size() {
		return size;
	}

	public void clear() {
		root = null;
		size = 0;
	}

	public void print() {
		if (root == null) {
			return;
		}

		String pad = " ".repeat(root.width());

		if (root.left != null) {
			root.left.print(pad, "┌", false);
		}

		System.out.printf("%s%s\n", root.data, root.pointer());

		if (root.right != null) {
			root.right.print(pad, "└", true);
		}
	}

	private static class Node<E> {
		E data;
		Node<E> left;
		Node<E> right;

		Node(E data) {
			this.data = data;
			this.left = null;
			this.right = null;
		}

		int width() {
			return data.toString().length();
		}

		String pointer() {
			if (right != null && left != null) {
				return "┤";
			} else if (right != null) {
				return "┐";
			} else if (left != null) {
				return "┘";
			} else {
				return "";
			}
		}

		public void print(String prev, String handle, boolean nested) {
			String pad = " ".repeat(width());
			String ptr = pointer();

			if (left != null) {
				left.print(prev + (nested ? "│" : " ") + pad, "┌", false);
			}

			System.out.printf("%s%s%s%s\n", prev, handle, data, ptr);

			if (right != null) {
				right.print(prev + (!nested ? "│" : " ") + pad, "└", true);
			}
		}
	}
}
