public class Node {
	private int where;
	private String key;
	public Node leftChild;
	public Node rightChild;
	public int getWhere;

	public Node(String k, int w) {
		key = new String(k);
		where = w;
	}

	public int compareTo(String k) {
		return key.compareTo(k);
	}

	public String toString(){
		return key + where;
	}

	public int getWhere(){
		return where;
	}

}


import java.util.Stack;

public class Tree {
	private Node root;

	public Tree() {
		root = null;
	}

	public int find(String key) {
		Node current = root;
		while (current.compareTo(key) != 0) {
			if (current.compareTo(key) < 0)
				current = current.leftChild;
			else
				current = current.rightChild;
			if (current == null)
				return -1;
		}
		return current.getWhere;
	}

	public void insert(String key, int where) {
		Node newNode = new Node(key,where);
		if (root == null)
			root = newNode;
		else {
			Node current = root;
			Node parent;
			while (true) {
				parent = current;
				if (current.compareTo(key) < 0) {
					current = current.leftChild;
					if (current == null) {
						parent.leftChild = newNode;
						return;
					}
				} else {
					current = current.rightChild;
					if (current == null) {
						parent.rightChild = newNode;
						return;
					}
				}
			}
		}
	}

	public boolean delete(String key) {
		Node current = root;
		Node parent = root;
		boolean isLeftChild = true;

		while (current.compareTo(key) != 0) {
			parent = current;
			if (current.compareTo(key) < 0) {
				isLeftChild = true;
				current = current.leftChild;
			} else {
				isLeftChild = false;
				current = current.rightChild;
			}
			if (current == null)
				return false;
		}

		if (current.leftChild == null && current.rightChild == null) {
			if (current == root)
				root = null;
			else if (isLeftChild)
				parent.leftChild = null;
			else
				parent.rightChild = null;
		} else if (current.rightChild == null)
			if (current == root)
				root = current.leftChild;
			else if (isLeftChild)
				parent.leftChild = current.rightChild;
			else
				parent.rightChild = current.leftChild;
		else if (current.leftChild == null)
			if (current == root)
				root = current.rightChild;
			else if (isLeftChild)
				parent.rightChild = current.rightChild;
			else
				parent.rightChild = current.rightChild;
		else {
			Node successor = getSuccessor(current);
			if (current == root)
				root = successor;
			else if (isLeftChild)
				parent.leftChild = successor;
			else
				parent.rightChild = successor;
			successor.leftChild = current.leftChild;
		}
		return true;
	}

	private Node getSuccessor(Node delNode) {
		Node successorParent = delNode;
		Node successor = delNode;
		Node current = delNode.rightChild;
		while (current != null) {
			successorParent = successor;
			successor = current;
			current = current.leftChild;
		}
		if(successor != delNode.rightChild){
			successorParent.leftChild = successor.rightChild;
			successor.rightChild = delNode.rightChild;
		}
		return successor;
	}
	public void traverse(int traverseType, DataBaseArray DBA){
		switch(traverseType){
		case 0: descendingOrder(root, DBA);break;
		case 1: ascendingOrder(root,DBA);break;
	}
		System.out.println();
	}

	private void ascendingOrder(Node localRoot, DataBaseArray DBA){
		if(localRoot != null){
			ascendingOrder(localRoot.leftChild, DBA);
			System.out.println(DBA.toString(localRoot.getWhere()));
			ascendingOrder(localRoot.rightChild,DBA);
		}
	}

	private void descendingOrder(Node localRoot, DataBaseArray DBA){
		if(localRoot != null){
			descendingOrder(localRoot.rightChild,DBA);
			System.out.println(DBA.toString(localRoot.getWhere()));
			descendingOrder(localRoot.leftChild,DBA);
		}
	}
}


/*Austin Thornton - E01401657
 * Programming Project Two
 * COSC 311 - Winter 2017
 * DUE:3/8/17
 */

import java.io.*;
import java.util.Scanner;

public class DataBase {
	// Declaring necessary variables
	private final int numElements = 100;
	private DataBaseArray DBA;
	private Tree id, first, last;
	private IndexRecord tempStorage;

	Scanner scan = new Scanner(System.in);

	// Constructor to initialize the variables
	public DataBase() {
		DBA = new DataBaseArray(numElements);
		id = new Tree();
		first = new Tree();
		last = new Tree();
	}

	// AddIt method to add new students to the database
	public void addIt() {
		// Declaring variables
		String studentID = null;
		String studentLast, studentFirst = null;
		boolean continueLoop = true;
		int idIndex = 0;
		// While loop to loop through and ask for the user to enter ID's
		while (continueLoop) {
			System.out.println("Enter a new ID: ");
			studentID = scan.next();
			idIndex = id.find(studentID);
			// If the index is >=0 that means the ID number is already in use,
			// and user is prompted to enter a different ID
			if (idIndex >= 0) {
				System.out.println("The ID is already in use, please try again");
			} else {
				continueLoop = false;
			}
		}
		// Prompting the user to enter the student's first and last name
		System.out.print("Enter a first name: ");
		studentFirst = scan.next();
		System.out.println("Enter a last Name: ");
		studentLast = scan.next();
		// Finally inserting the student into the database
		insertRecord(studentLast, studentFirst, studentID);
	}

	public void findIt() {
		// Declaring variables
		String studentID = null;
		int where = 0;
		System.out.print("Please enter the ID you would like to find");
		studentID = scan.next();
		// Finding the student's ID
		where = id.find(studentID);
		if (where < 0) {
			System.out.println("ID not found");
		} else {
			DBA.printRecord(where);
		}
	}

	// DeleteIt method to delete a student
	public void deleteIt() {
		// Declaring variables
		String studentID, studentLast, studentFirst = null;
		boolean delete, delete2, delete3 = true;
		int where = 0;
		// Print statement prompting user for the student's ID to be deleted
		System.out.println("Please enter the ID you would like to delete");
		studentID = scan.next();
		// storing the student and finding them
		where = id.find(studentID);
		if (where >= 0) {
			// Getting the location of the student's first and last name and
			// removing them
			studentFirst = DBA.getFirst(where);
			studentLast = DBA.getLast(where);
			delete = id.delete(studentID);
			delete2 = first.delete(studentFirst);
			delete3 = last.delete(studentLast);
			if (delete && delete2 && delete3 == true) {
				DBA.printRecord(where);
			} else {
				System.out.println("ID not found");
			}
		} else {
			System.out.println("ID not found");
		}
	}

	// InsertRecord method to insert new students into the database
	public boolean insertRecord(String studentLast, String studentFirst, String studentID) {

		int index = DBA.getRecCount();
		// Checking to see if the database is full
		if (index == numElements) {
			System.out.println("Database full");
			return false;
		}
		// Inserting data into the database
		DBA.insertRecord(studentLast, studentFirst, studentID);
		id.insert(studentID, index);
		first.insert(studentFirst, index);
		last.insert(studentLast, index);
		return true;
	}

	// Find method to find students within the database

	// OutputList method to iterate through the data and print in different
	// orders
	public void displayList(Tree tree, int x) {
		tree.traverse(x,DBA);
	}

	// Methods to print in various orders
	public void ListByFirstAscending() {
		displayList(first, 0);
	}

	public void ListByLastAscending() {
		displayList(last, 0);
	}

	public void ListByIDAscending() {
		displayList(id, 0);
	}

	public void ListByFirstDescending() {
		displayList(first, 1);
	}

	public void ListByLastDescending() {
		displayList(last, 1);
	}

	public void ListByIDDescending() {
		displayList(id, 1);
	}

}

/*Austin Thornton - E01401657
 * Programming Project Two
 * COSC 311 - Winter 2017
 * DUE:3/8/17
 */

public class DataBaseArray {
	// Declaring necessary variables
	private DataBaseRecord[] DBRA;
	private int numRecords = 0;

	// Constructor to set records
	DataBaseArray(int s) {
		DBRA = new DataBaseRecord[s];
	}

	// InsertRecord method to insert a record into the array
	public void insertRecord(String studentLast, String studentFirst, String studentID) {
		DBRA[numRecords] = new DataBaseRecord(studentLast, studentFirst, studentID);
		numRecords++;
	}

	// UpdateRecord method to update the array with the new empty location from
	// the stack
	public void updateRecord(int emptyLocation, String studentLast, String studentFirst, String studentID) {
		DBRA[emptyLocation] = new DataBaseRecord(studentLast, studentFirst, studentID);
		return;
	}

	// PrintRecord method to print a record
	public void printRecord(int x) {
		DBRA[x].printArray();
	}

	// PrintArray method to print
	public void printArray() {
		for (int x = 0; x < numRecords + 1; x++) {
			DBRA[x].printArray();
		}
	}

	// "Getters" to get the first/last name and ID
	public String getID(int x) {
		String temp;
		temp = DBRA[x].getID();
		return temp;
	}

	public String getFirst(int x) {
		String temp;
		temp = DBRA[x].getFirst();
		return temp;
	}

	public String getLast(int x) {
		String temp;
		temp = DBRA[x].getLast();
		return temp;
	}

	// Getting the number of records
	public int getRecCount() {
		return numRecords;
	}

	// ToString method to convert the array to a string
	public String toString(int x) {
		String temp;
		temp = DBRA[x].toString();
		return temp;
	}

	// Length method to get the length of the array
	public int length() {
		return DBRA.length;
	}

}


/*Austin Thornton - E01401657
 * Programming Project Two
 * COSC 311 - Winter 2017
 * DUE:3/8/17
 */

public class DataBaseRecord {
	// Declaring necessary variables
	private String ID;
	private String fName;
	private String lName;

	// Constructor to set the variables
	public DataBaseRecord(String i, String f, String l) {
		ID = new String(i);
		fName = new String(f);
		lName = new String(l);
	}

	// UpdateRecord method to set the student's first/last name and ID
	public void updateRecord(String i, String f, String l) {
		ID = new String(i);
		fName = new String(f);
		lName = new String(l);
	}

	// PrintArray method to print the student's first/last name and ID
	public void printArray() {
		System.out.println(lName + " " + fName + " " + ID);
	}

	// "Getters" to get the ID/first/last name
	public String getID() {
		return ID;
	}

	public String getFirst() {
		return fName;
	}

	public String getLast() {
		return lName;
	}

	// ToString method to convert the data into a string
	public String toString() {
		return lName + " " + fName + " " + ID;
	}

	// CompareTo method to compare 2 students
	public int compareTo(DataBaseRecord otherStudent) {
		return (lName.compareTo(otherStudent.lName));
	}

}


/*Austin Thornton - E01401657
 * Programming Project Two
 * COSC 311 - Winter 2017
 * DUE:3/8/17
 */

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;

import java.util.*;

public class Driver {

	public static void main(String[] args) {
		// Declaring necessary variables
		DataBase d = new DataBase();
		int response;
		Scanner keyboard = new Scanner(System.in);
		// Try/catch to setup the file read and write into the database
		try {
			Scanner fileScanner = new Scanner(new FileInputStream(new File("data.txt")));
			while (fileScanner.hasNext()) {
				String last = fileScanner.next();
				String first = fileScanner.next();
				String id = fileScanner.next();

				d.insertRecord(last, first, id);
			}

		} catch (FileNotFoundException f) {
			System.out.println(f.getMessage() + "File not found");
			System.exit(0);
		}

		// The menu for the user to select their action
		do {
			System.out.println(" 1 Add a new student");
			System.out.println(" 2 Delete a student");
			System.out.println(" 3 Find a student by ID");
			System.out.println(" 4 List students by ID increasing");
			System.out.println(" 5 List students by first name increasing");
			System.out.println(" 6 List students by last name increasing");
			System.out.println(" 7 List students by ID decreasing");
			System.out.println(" 8 List students by first name decreasing");
			System.out.println(" 9 List students by last name decreasing");
			System.out.println(" ");
			System.out.println(" 0 End");

			response = keyboard.nextInt();

			switch (response) {
			case 1:
				d.addIt(); // Note: if the user enters an ID already in use,
							// issue a warning and return to the menu
				break;
			case 2:
				d.deleteIt(); // Note: output either "Deleted" or "ID not Found"
								// and return to menu
				break;
			case 3:
				d.findIt(); // Note: output the entire record or the message
							// "ID not Found" and return to menu
				break;
			case 4:
				d.ListByIDAscending();
				break;
			case 5:
				d.ListByFirstAscending();
				break;
			case 6:
				d.ListByLastAscending();
				break;
			case 7:
				d.ListByIDDescending();
				break;
			case 8:
				d.ListByFirstDescending();
				break;
			case 9:
				d.ListByLastDescending();
				break;
			default:
			}

		} while (response != 0);
	}
}

/*Austin Thornton - E01401657
 * Programming Project Two
 * COSC 311 - Winter 2017
 * DUE:3/8/17
 */

public class IndexRecord {
	// Declaring necessary variables
	private String key;
	private int position;
	public IndexRecord next;
	public IndexRecord previous;

	// Constructor to set the variables
	public IndexRecord(String k, int p) {
		key = k;
		position = p;
	}

	// CompareTo method to compare records
	public int compareTo(String k) {
		return key.compareTo(k);
	}

	// ToString method to print the key and position of a record
	public String toString() {
		return key + " " + position;
	}

	// GetWhere method to get the position
	public int getWhere() {
		return position;
	}

	// DisplayLink method to display a link of the linked list
	public void displayLink() {
		System.out.println(toString());
	}

}

Dunn Sean  	        31111
Duong Geoffrey  	29922
Fazekas  Nicholas  	31100
Prezioso Stefano 	 22223
Puvvada Mohana 	     11224
Ravikumar Rakhi 	  11226
Salyers Matthew      11227
Gillespie William  	49587
Hess Caleb           29282
Armatis Jared   34512
Beckman Allan  	35176
Wang Zhen 	        22113
Wingett Jordan  	1234
Belt Keith  	34987
Bixler Tyler 	22234
Chambers Quentin  	22567
Chinni Adithya 	    28456
Donheiser Michael  	28456
Kondrashov Mikhail   33331
Kraus Laura          33332
Krupp Phillip        49888
Maass John           44112
McCarty Amanda       44223
Moldovan Gregory     44335
Oshiyoye Adekunle   44556
Pagalos Frank  	     33112
Perski Zackery       33221
Saunders Jordan       77556
Simpson Ashlynne     77665
Szalai Kyle  	    33112
Witting Robert  	21354