package ua.nure.rozdaybeda.Practice6.part5;

import java.util.Arrays;

/**
 * Implements binary tree
 * @author Oleg
 *
 * @param <E> specifies type of stored data in the tree has to support comperison.
 */
public class Tree<E extends Comparable<E>> {

	/**
	 * Indent between levels of tree in string representation
	 */
	private static final String INDENT = "   ";

	/**
	 * Root node of tree
	 */
	private Node<E> root = null;

	/**
	 * Max size of string representation of element in tree
	 */
	private int elSize = 0;

	/**
	 * Adds element to the tree
	 * @param e element
	 * @return true if element successfully added, false if the element is already exists in the tree
	 */
	public boolean add(E e) {
		int l = e.toString().length();
		if(l > elSize) {
			elSize = l;
		}
		if(root == null) {
			root = new Node<E>(e);
			return true;
		}
		return addRec(e, root);
	}
	/**
	 * Recursively bypasses the tree and finds the place to add new element
	 * @param e element
	 * @param node current node
	 * @return true if element successfully added, false if the element is already exists in the tree
	 */
	private boolean addRec(E e, Node<E> node) {
		int compResult = e.compareTo(node.data);
		if(compResult == 0) {
			return false;
		}
		if(compResult < 0) {
			if(node.left == null) {
				createAndAppendNode(e, node, LEFT);
				return true;
			} else {
				return addRec(e, node.left);
			}
		} else {
			if(node.right == null) {
				createAndAppendNode(e, node, RIGHT);
				return true;
			} else {
				return addRec(e, node.right);
			}
		}
	}

	/**
	 * Left branch of node
	 */
	private static final int LEFT = -1;
	/**
	 * Right branch of node
	 */
	private static final int RIGHT = 1;

	/**
	 * Creates new node and appends it to another specifien node
	 * @param e element
	 * @param parent parent node
	 * @param side side of parrent node to attach new node
	 */
	private void createAndAppendNode(E e, Node<E> parent, int side) {
		if(side == LEFT) {
			parent.left = new Node<E>(e);
		} else {
			parent.right = new Node<E>(e);
		}
	}

	/**
	 * Adds elements of array to tree one by one
	 * @param elements the array
	 */
	public void add(E[] elements) {
		for(E e : elements) {
			add(e);
		}
	}

	/**
	 * Removes element from tree keeping the binary property of tree
	 * @param e element to remove
	 * @return true if element found, false if element is not in the tree
	 */
	public boolean remove(E e) {
		if(root == null) {
			return false;
		}
		if(root.data.compareTo(e) == 0) {
			root = null;
			return true;
		}

		return removeRec(e, root);
	}

	/**
	 * Recursively bypasses the tree and finds a node with equal data to remove the node
	 * @param e element
	 * @param node current node
	 * @return true if element found, false if element is not in the tree
	 */
	private boolean removeRec(E e, Node<E> node) {
		int compResult = e.compareTo(node.data);

		if(compResult < 0) {
			if(node.left == null) {
				return false;
			} else {
				if(e.compareTo(node.left.data) == 0) {
					removeChildNode(node, LEFT);
					return true;
				} else {
					return removeRec(e, node.left);
				}
			}
		} else {
			if(node.right == null) {
				return false;
			} else {
				if(e.compareTo(node.right.data) == 0) {
					removeChildNode(node, RIGHT);
					return true;
				} else {
					return removeRec(e, node.right);
				}
			}
		}
	}

	/**
	 * Removes child node in specified side of parent node
	 * @param parent parent node
	 * @param side side of parent node with node will be deleted
	 */
	private void removeChildNode(Node<E> parent, int side) {
		Node<E> child;
		if(side == LEFT) {
			child = parent.left;
		} else {
			child = parent.right;
		}
		if(child.left == null && child.right == null) {
			setSide(parent, side, null);
			return;
		}
		if(child.left == null ^ child.right == null) {
			if(child.left != null) {
				setSide(parent, side, child.left);
			} else {
				setSide(parent, side, child.right);
			}
			return;
		}
		if(child.left != null && child.right != null) {
			if(child.left.right == null) {
				replaceSide(parent, side, child.left);
				removeChildNode(child, LEFT);
				return;
			}
			Node<E> rightestParent = getParentOfRightest(child.left);
			replaceSide(parent, side, rightestParent.right);
			removeChildNode(rightestParent, RIGHT);
		}
	}
	/**
	 * Returns parent node of node which doesn`t have right node
	 * @param parent initial node
	 * @return parent node of node which doesn`t have right node
	 */
	private Node<E> getParentOfRightest(Node<E> parent){
		while(parent.right.right != null) {
			parent = parent.right;
		}
		return parent;
	}

	/**
	 * Sets specifeid node to specifien side of node
	 * @param parent parent node
	 * @param side side of parent node
	 * @param newChild node will be appended to parent node
	 */
	private void setSide(Node<E> parent, int side, Node<E> newChild) {
		if(side == LEFT) {
			parent.left = newChild;
		} else {
			parent.right = newChild;
		}
	}
	/**
	 * Replaces data of one node with data of other node
	 * @param parent node which child`s data will be repleced
	 * @param side side with child node
	 * @param newNode node with new data
	 */
	private void replaceSide(Node<E> parent, int side, Node<E> newNode) {
		if(side == LEFT) {
			parent.left.data = newNode.data;
		} else {
			parent.right.data = newNode.data;
		}
	}
	/**
	 * Calculates heigth of the tree
	 * @return height of the tree
	 */
	public int getHeight() {
		if(root == null)
			return 0;
		return calcHeight(root);
	}

	/**
	 * Recursively calculates height of tree. Counts height of each node from leaves to root
	 * @param node current node
	 * @return height of current node
	 */
	private int calcHeight(Node<E> node) {
		if(node == null)
			return 0;
		int result = 1;

		if(node.left != null) {
			result = calcHeight(node.left) + 1;
		}

		if(node.right != null) {
			int temp = calcHeight(node.right) + 1;
			if(temp > result)
				result = temp;
		}

		return result;
	}
	/**
	 * Prints string representation of tree to standart output stream
	 */
	public void print() {
		System.out.println(toString());
	}

	@Override
	public String toString() {
		int height = calcHeight(root);
		if(height == 0) {
			return "";
		}
		if(height == 1) {
			return root.toString();
		}

		return new TreeToString<E>(height, root, elSize).represent();
	}

	/**
	 * Implements node of tree
	 * @author Oleg
	 *
	 * @param <E> type of stored data in node. Equal to tree`s type
	 */
	private static class Node<E> {
		/**
		 * Reference to left node
		 */
		Node<E> left;
		/**
		 * Reference to right node
		 */
		Node<E> right;
		/**
		 * Data of this node
		 */
		E data;

		/**
		 * Constructor
		 * @param data data of current node
		 */
		Node(E data){
			this.data = data;
		}

		@Override
		public String toString() {
			return data.toString();
		}
	}
	/**
	 * Makes string representation of the tree
	 * @author Oleg
	 *
	 * @param <E> type of stored data in the tree.
	 */
	private static class TreeToString<E> {
		/**
		 * Height of tree
		 */
		private int height;
		/**
		 * Reference to root node of tree
		 */
		private Node<E> root;
		/**
		 * Buffer storage of string representation
		 */
		private StringBuilder result;
		/**
		 * Max size of string representation of element in tree
		 */
		int elSize;
		/**
		 * Length of line in buffer
		 */
		int resultLineLength;
		/**
		 * Count of lines in buffer
		 */
		int resultLinesCount;
		/**
		 * Registers amount of visited nodes in each level of tree
		 */
		int nodeVisited[];
		/**
		 * Vertical indent bettween two elements for each level
		 */
		int verticalOffsets[];

		/**
		 * Constructor
		 * @param height height
		 * @param root root
		 * @param elSize elSize
		 */
		private TreeToString(int height, Node<E> root, int elSize) {
			this.height = height;
			this.root = root;
			this.elSize = elSize;

			resultLineLength = elSize + (height - 1) * (elSize + INDENT.length()) + System.lineSeparator().length();
			resultLinesCount = ((int) Math.pow(2, height)) - 1;

			result = new StringBuilder(resultLineLength * resultLinesCount);

//			String spacesStr = createEmptyLine(resultLineLength - System.lineSeparator().length());
			for(int i = 0; i < resultLinesCount; i++) {
				result.append(createEmptyLine(resultLineLength - System.lineSeparator().length()));
			}

			nodeVisited = new int[height];

			verticalOffsets = new int[height + 1];
			verticalOffsets[height - 1] = 1;
			for(int i = height - 2; i >= 0; i--) {
				verticalOffsets[i] = (verticalOffsets[i + 1] * 2) + 1;
			}
		}

		/**
		 * Creates string representation of tree
		 * @return string representation of tree
		 */
		private String represent() {
			out.println("height = " + height + " resultLineLength " + resultLineLength + " resultLinesCount " + resultLinesCount);
			out.println(Arrays.toString(verticalOffsets));
			traversal(root, 0);

			return result.toString();
		}
		/**
		 * Recursively bypasses the tree node by node and makes appropriate changes to the buffer
		 * @param node current node
		 * @param currentLevel current level
		 */
		private void traversal(Node<E> node, int currentLevel) {
			int horOffset = 1 + currentLevel * (INDENT.length() + elSize);
			int vertOffset = verticalOffsets[currentLevel + 1] /*+ 1*/ + nodeVisited[currentLevel] * (verticalOffsets[currentLevel] + 1);

			int pos = vertOffset * resultLineLength + horOffset;
			String str = node.toString();
			out.println("node.toString " + str + " currentLevel " + currentLevel);
			out.println("replacePos " + pos + " horOffset " + horOffset + " vertOffset " + vertOffset);
			result.replace(pos, pos + str.length(), str);

			if(node.right == null) {
				changeNodeVisited(currentLevel + 1);
			} else {
				traversal(node.right, currentLevel + 1);
			}
			if(node.left == null) {
				changeNodeVisited(currentLevel + 1);
			} else {
				traversal(node.left, currentLevel + 1);
			}

			nodeVisited[currentLevel]++;
		}

		/**
		 * Is called to change {@link #nodeVisited nodeVisited} due to null nodes
		 * @param currentLevel start level for changers
		 */
		private void changeNodeVisited(int currentLevel) {
			out.println("START changeNodeVisited");
			if(currentLevel == height) {
				out.println("END changeNodeVisited");
				return;
			}
			for(int summand = 1; currentLevel < height; currentLevel++, summand *= 2) {
				out.println("[changeNodeVisited] currentLevel " + currentLevel + " summand " + summand);
				nodeVisited[currentLevel] += summand;
			}
			out.println("END changeNodeVisited");
		}
		/**
		 * Creates line with spaces and system-independent line separator int the end of line
		 * @param spaces count of spaces
		 * @return created line
		 */
		private String createEmptyLine(int spaces) {
			StringBuilder result = new StringBuilder(spaces + System.lineSeparator().length());
			for(int i = 0; i < spaces; i++) {
				result.append(" ");
			}
			result.append(System.lineSeparator());
			return result.toString();
		}

	}

	final static DebugOut out = new DebugOut();
	static boolean debug = false;
	static class DebugOut{
		public void println(String data) {
			if(debug == true) {
				System.out.println(data);
			}
		}
	}

}