package bjc.utils.funcdata.bst;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.function.Predicate;

import bjc.utils.funcdata.bst.ITreePart.TreeLinearizationMethod;

/**
 * A binary search tree, with some mild support for functional traversal.
 * 
 * @author ben
 *
 * @param <T> The data type stored in the node.
 */
public class BinarySearchTree<T> {
	private Comparator<T>	comp;
	private int				nCount;
	private ITreePart<T>	root;

	/**
	 * Create a new tree using the specified way to compare elements.
	 * @param cmp
	 */
	public BinarySearchTree(Comparator<T> cmp) {
		nCount = 0;
		comp = cmp;
	}

	/**
	 * Add a node to the binary search tree.
	 * @param dat The data to add to the binary search tree.
	 */
	public void addNode(T dat) {
		nCount++;
		if (root == null) {
			root = new TreeNode<T>(dat, null, null);
		} else {
			root.add(dat, comp);
		}
	}

	/**
	 * Balance the tree, and remove soft-deleted nodes for free.
	 * 		Takes O(N) time, but also O(N) space.
	 */
	public void balance() {
		ArrayList<T> elms = new ArrayList<>(nCount);
		
		root.forEach(TreeLinearizationMethod.INORDER, e -> elms.add(e));
		
		root = null;
		
		int piv = elms.size() / 2;
		int adj = 0;
		
		while((piv - adj) >= 0 && (piv + adj) < elms.size()) {
			if(root == null) {
				root = new TreeNode<T>(elms.get(piv), null, null);
			} else {
				root.add(elms.get(piv + adj), comp);
				root.add(elms.get(piv - adj), comp);
			}
			
			adj++;
		}
		
		if((piv - adj) >= 0) {
			root.add(elms.get(piv - adj), comp);
		} else if((piv + adj) < elms.size()) {
			root.add(elms.get(piv + adj), comp);
		}
	}

	/**
	 * Get the root of the tree.
	 * @return The root of the tree.
	 */
	public ITreePart<T> getRoot() {
		return root;
	}
	
	/**
	 * Soft-delete a node from the tree.
	 * 		Soft-deleted nodes stay in the tree until trim()/balance() is invoked,
	 * 		and are not included in traversals/finds.
	 * @param dat
	 */
	public void deleteNode(T dat) {
		nCount--;
		root.delete(dat, comp);
	}

	/**
	 * Check if a node is in the tree
	 * @param dat The node to check the presence of for the tree.
	 * @return Whether or not the node is in the tree.
	 */
	public boolean isInTree(T dat) {
		return root.contains(dat, comp);
	}

	/**
	 * Traverse the tree in a specified way until the function fails
	 * @param tlm The way to linearize the tree for traversal
	 * @param p The function to use until it fails
	 */
	public void traverse(TreeLinearizationMethod tlm, Predicate<T> p) {
		root.forEach(tlm, p);
	}

	/**
	 * Remove all soft-deleted nodes from the tree.
	 */
	public void trim() {
		List<T> nds = new ArrayList<>(nCount);

		traverse(TreeLinearizationMethod.PREORDER, d -> {
			nds.add(d);
			return true;
		});

		root = null;

		nds.forEach(d -> addNode(d));
	}
}