/* 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 deleteGraduates() {
		deleteGraduates(root);
	}

	private void deleteGraduates(BSTNode r) {
		if (r != null) {
			deleteGraduates(r.getLeft());
			if (r.getData().status == 2)
				delete(r.getData().code);
			deleteGraduates(r.getRight());
		}
	}

	public void insertByClassAndName(BST temp, int classId) {
		insertByClassAndName(root, temp, classId);
	}

	private void insertByClassAndName(BSTNode r, BST temp, int classId) {
		if (r != null) {
			insertByClassAndName(r.getLeft(), temp, classId);
			if (r.getData().classId == classId)
				temp.insertByName(r.getData());
			insertByClassAndName(r.getRight(), temp, classId);
		}
	}

	///////////////////////////
	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 createTreeByName(BST temp) {
		createTreeByName(root, temp);
	}

	private void createTreeByName(BSTNode r, BST temp) {
		if (r != null) {
			createTreeByName(r.getLeft(), temp);
			temp.insertByName(r.getData());
			createTreeByName(r.getRight(), temp);
		}
	}

	/////////////
	public void listGraduate() {
		listGraduate(root);
	}

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

	//////////////////
	public void listUndergradsByClassAndName() {
		listUndergradsByClassAndName(root);
	}

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

	//////////////////
	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().birthDate + ", "
					+ r.getData().address + ", " + r.getData().classId + ", " + r.getData().status);
			writeToFile(r.getRight(), file);
		}


	BST bstName;
	int classId;
	System.out.println("Binary Search Tree Test\n");
	char ch;
	/* Perform tree operations */
	do
	{
		System.out.println("\nBinary Search Tree Operations\n");
		System.out.println("1. insert student ");
		System.out.println("2. Find a student by its code ");
		System.out.println("3. List students in alphabetical order of their names for a specific class ");
		System.out.println("4. List students in alphabetical order of their names ");
		System.out.println("5. List all graduated students ");
		System.out.println("6. List all undergrads for a specific class in alphabetical order of their names ");
		System.out.println("7. Delete a student given by its code ");
		System.out.println("8. Delete all graduates");
		System.out.println("9. Save stock in file stock.data");
		int choice = scan.nextInt();
		switch (choice) {
		case 1:
			System.out.println("Enter student Code");
			element.code = scan.nextInt();
			System.out.println("Enter student Name");
			element.name = scan.nextLine();
			System.out.println("Enter student birth date");
			next = scan.next("[0-9]{2}/[0-9]{2}/[0-9]{4}");
			try {
				element.birthDate = new SimpleDateFormat("dd/MM/yyyy").parse(next);
			} catch (ParseException e) {
				e.printStackTrace();
			}
			System.out.println("Enter student address");
			element.address = scan.nextLine();
			System.out.println("Enter class Id");
			element.classId = scan.nextInt();
			System.out.println("Enter student enrollment date");
			next = scan.next("[0-9]{2}/[0-9]{2}/[0-9]{4}");
			try {
				element.enrollmentDate = new SimpleDateFormat("dd/MM/yyyy").parse(next);
			} catch (ParseException e) {
				e.printStackTrace();
			}
			System.out.println("Enter Item status (undergrad = 1, graduate = 2)");
			element.classId = scan.nextByte();
			bst.insert(element);
			break;
		case 2:
			System.out.println("Enter student code to search");
			BSTNode temp = bst.search(scan.nextInt());
			if (temp == null)
				System.out.println("Not found");
			else {
				System.out.println("Student Information = " + temp.getData());
				System.out.println("Do you want to modify the student information(Y/N)");
				if (scan.next().charAt(0) == 'Y') {
					System.out.println("Enter student Code");
					element.code = scan.nextInt();
					System.out.println("Enter student Name");
					element.name = scan.next();
					System.out.println("Enter student birth date");
					next = scan.next("[0-9]{2}/[0-9]{2}/[0-9]{4}");
					try {
						element.birthDate = new SimpleDateFormat("dd/MM/yyyy").parse(next);
					} catch (ParseException e) {
						e.printStackTrace();
					}
					System.out.println("Enter student address");
					element.address = scan.next();
					System.out.println("Enter class Id");
					element.classId = scan.nextInt();
					System.out.println("Enter student enrollment date");
					next = scan.next("[0-9]{2}/[0-9]{2}/[0-9]{4}");
					try {
						element.enrollmentDate = new SimpleDateFormat("dd/MM/yyyy").parse(next);
					} catch (ParseException e) {
						e.printStackTrace();
					}
					System.out.println("Enter Item status (undergrad = 1, graduate = 2)");
					element.status = scan.nextByte();
					temp.data = element;
				}
			}
			break;
		case 3:
			System.out.println("Enter class Id");
			classId = scan.nextInt();
			bstName = new BST();
			bst.insertByClassAndName(bstName, classId);
			bstName.inorder();
			break;
		case 4:
			bstName = new BST();
			bst.createTreeByName(bstName);
			bstName.inorder();
			break;
		case 5:
			bst.listGraduate();
			break;
		case 6:
			System.out.println("Enter class Id");
			classId = scan.nextInt();
			bstName = new BST();
			bst.insertByClassAndName(bstName, classId);
			bstName.listUndergradsByClassAndName();
			break;
		case 7:
			System.out.println("Enter student code to delete");
			bst.delete(scan.nextInt());
			break;
		case 8:
			bst.deleteGraduates();
			bst.inorder();
			break;
		case 9:
			bst.writeToFile("output.txt");
			break;
		default:
			System.out.println("Wrong Entry \n ");
			break;
		}
		System.out.println("\nDo you want to continue (Type y or n) \n");
		ch = scan.next().charAt(0);
	}while(ch=='Y'||ch=='y');
}

}