/* Class BST */
import java.util.Date;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.io.IOException;

class BST {
	private BSTNode root;

	/* Constructor */
	public BST() {
		root = null;
	}

	/* Function to check if tree is empty */
	public boolean isEmpty() {
		return root == null;
	}

	/* Functions to insert data */
	public void insert(Item data) {
		root = insert(root, data);
	}

	/* Function to insert data recursively */
	private BSTNode insert(BSTNode node, Item data) {
		if (node == null)
			node = new BSTNode(data);
		else {
			if (data.code <= node.getData().code)
				node.left = insert(node.left, data);
			else
				node.right = insert(node.right, data);
		}
		return node;
	}

	/* Functions to delete data */
	public void delete(int k) {
		if (isEmpty())
			System.out.println("Tree Empty");
		else if (search(k) == null)
			System.out.println("Sorry " + k + " is not present");
		else {
			root = delete(root, k);
			System.out.println(k + " deleted from the tree");
		}
	}

	private BSTNode delete(BSTNode root, int k) {
		BSTNode p, p2, n;

		if (root.getData().code == k) {
			BSTNode lt, rt;
			lt = root.getLeft();
			rt = root.getRight();
			if (lt == null && rt == null)
				return null;
			else if (lt == null) {
				p = rt;
				return p;
			} else if (rt == null) {
				p = lt;
				return p;
			} else {
				p2 = rt;
				p = rt;
				while (p.getLeft() != null)
					p = p.getLeft();
				p.setLeft(lt);
				return p2;
			}
		}
		if (k < root.getData().code) {
			n = delete(root.getLeft(), k);
			root.setLeft(n);
		} else {
			n = delete(root.getRight(), k);
			root.setRight(n);
		}
		return root;
	}

	/* Functions to count number of nodes */
	public int countNodes() {
		return countNodes(root);
	}

	/* Function to count number of nodes recursively */
	private int countNodes(BSTNode r) {
		if (r == null)
			return 0;
		else {
			int l = 1;
			l += countNodes(r.getLeft());
			l += countNodes(r.getRight());
			return l;
		}

	}/* Functions to search for an element */

	public BSTNode search(int val) {
		return search(root, val);
	}

	/* Function to search for an element recursively */
	private BSTNode search(BSTNode r, int val) {
		while (r != null) {
			if (val < r.getData().code)
				return search(r.getLeft(), val);
			else if (val > r.getData().code)
				return search(r.getRight(), val);
			else
				return r;
		}
		return null;
	}

	/* Function for inorder traversal */
	public void inorder() {
		inorder(root);
	}

	private void inorder(BSTNode r) {
		if (r != null) {
			inorder(r.getLeft());
			System.out.print(r.getData() + "\n");
			inorder(r.getRight());
		}
	}

	/* Function for preorder traversal */
	public void preorder() {
		preorder(root);
	}

	private void preorder(BSTNode r) {
		if (r != null) {
			System.out.print(r.getData() + "\n");
			preorder(r.getLeft());
			preorder(r.getRight());
		}
	}

	/* Function for postorder traversal */
	public void postorder() {
		postorder(root);
	}

	private void postorder(BSTNode r) {
		if (r != null) {
			postorder(r.getLeft());
			postorder(r.getRight());
			System.out.print(r.getData() + "\n");
		}
	}

	public void deleteExpiredDate() {
		deleteExpiredDate(root);
	}

	private void deleteExpiredDate(BSTNode r) {
		if (r != null) {
			deleteExpiredDate(r.getLeft());
			if (r.getData().expirationDate.compareTo(new Date()) < 0)
				delete(r.getData().code);
			deleteExpiredDate(r.getRight());
		}
	}

	public void createExpiredDateTree(BST temp) {
		createExpiredDateTree(root, temp);
	}

	private void createExpiredDateTree(BSTNode r, BST temp) {
		if (r != null) {
			createExpiredDateTree(r.getLeft(), temp);
			if (r.getData().expirationDate.compareTo(new Date()) < 0)
				temp.insert(r.getData());
			createExpiredDateTree(r.getRight(), temp);
		}
	}

	public void insertByName(Item data) {
		root = insertByName(root, data);
	}

	/* Function to insert data recursively */
	private BSTNode insertByName(BSTNode node, Item data) {
		if (node == null)
			node = new BSTNode(data);
		else {
			if (data.name.compareTo(node.getData().name) <= 0)
				node.left = insert(node.left, data);
			else
				node.right = insert(node.right, data);
		}
		return node;
	}

	public void createValidSortedByNameTree(BST temp) {
		createValidSortedByNameTree(root, temp);
	}

	private void createValidSortedByNameTree(BSTNode r, BST temp) {
		if (r != null) {
			createValidSortedByNameTree(r.getLeft(), temp);
			if (r.getData().expirationDate.compareTo(new Date()) >= 0)
				temp.insertByName(r.getData());
			createValidSortedByNameTree(r.getRight(), temp);
		}
	}

	public void createInValidSortedByNameTree(BST temp) {
		createInValidSortedByNameTree(root, temp);
	}

	private void createInValidSortedByNameTree(BSTNode r, BST temp) {
		if (r != null) {
			createInValidSortedByNameTree(r.getLeft(), temp);
			if (r.getData().expirationDate.compareTo(new Date()) < 0)
				temp.insertByName(r.getData());
			createInValidSortedByNameTree(r.getRight(), temp);
		}
	}

	public void writeToFile(String fileName) throws IOException {
		FileWriter write = new FileWriter(fileName, false);
		PrintWriter printLine = new PrintWriter(write);
		writeToFile(root, printLine);
		printLine.close();
	}

	private void writeToFile(BSTNode r, PrintWriter file) {
		if (r != null) {
			writeToFile(r.getLeft(), file);
			file.printf("%s" + "%n", r.getData().code + ", " + r.getData().name + ", " + r.getData().price + ", "
					+ r.getData().amount + ", " + r.getData().expirationDate + ", " + r.getData().expirationDate);
			writeToFile(r.getRight(), file);
		}
	}
}