/**
 * A class containing list of records with insert/delete
 * and search funcionality.
 * 
 * @author Vivek Rane. TA for 22C:21, Spring 2006
 * Modified by Sriram Pemmaraju, Jan 17th 2007
 * Modified by Sriram Pemmaraju again on Aug 31st2007
 */
public class RecordDB {

	private static int maxRecords = 200;
	private int numRecords = 0;
	private Record recordList[] = new Record[maxRecords];
	
	/**
	 * Inserts a record into the ordered array in a sorted fashion.
	 * @param rec - The record to be inserted.
	 */
	public void insert (Record rec) {

		// Check for overflow; if overflow, then don't insert
		if (numRecords == maxRecords-1) {
			return;	
		}

		// Find the position to insert in, by scanning the array
		// left-to-right until a large ssn is located
		// It is a bit silly not to be using binary serach for this as well
		int i;
		for (i = 0; i < numRecords; i++) {
			if ((recordList[i].ssn).compareTo(rec.ssn) > 0)
				break;
		}
		
		// Shift all records one space down
		for (int j=numRecords-1; j>=i; j--) {
			recordList[j+1] = recordList[j];
		}
		
		// Insert the new record
		recordList[i] = rec;

		// Increment current number of employees in the list
		numRecords++;
		
		// This is here just for testing; should be commented
		// out eventually
		printAll();
	}
	
	/**
	 * Deletes a record from the list based on the key (ssn).
         * Performs a linear scan of the array of records until
         * a record is found with the given ssn
	 * @param ssn
	 */
	public void delete (String newSSN) {
		// Scan the array searching for the record containing newSSN
		// Again, it is a bit silly not to use binary search for this
		int i;
		for (i = 0; i < numRecords; i++) {
			
			// SSN found in slot i
			if (newSSN.compareTo(recordList[i].ssn) == 0) {
				break;
			}
		}
		
		// Shift all records that are beyond slot i, 
 		// to the left by one slot
		for (int j = i; j < numRecords-1; j++) {
			recordList[j] = recordList[j+1];
		}
		
		numRecords--;

		// This is here just for testing; should be commented
		// out eventually
		printAll();
	}
	
	/**
	 * Search for the record with the given SSN
	 * @param newSSN
	 * @return
	 */
			
	public Record search (String newSSN) {
		
		// This is here just for testing; should be commented
		// out eventually
		printAll();
		int first=0, last=numRecords-1;
		
		// main while-loop
		while (first <= last) {
			int mid = (first+last)/2;
			
			// Is newSSN at mid?
			if (newSSN.compareTo(recordList[mid].ssn) == 0) 
				return new Record(recordList[mid].ssn, 
					          recordList[mid].name, 
						  recordList[mid].pay);

			// Is newSSN before mid?
			if (newSSN.compareTo(recordList[mid].ssn) < 0)
				last = mid-1;

			// Is newSSN after mid?
			else if (newSSN.compareTo(recordList[mid].ssn) > 0) 
				first = mid+1;
		} // end of while-loop
		return null;
	
	} // end of search function
	
	/**
	 * Prints the list of records to the standard output;
	 */
	private void printAll() {
		System.out.println("---------------------------");
		for (int i=0; i<numRecords; i++) {
			System.out.println(""+i+" "+recordList[i].ssn);
		}
	}

	/**
	 * Main method - adds and deletes records and searches for some.
	 * @param args
	 */
	public static void main(String[] args) {
		RecordDB recDB = new RecordDB();
		
		recDB.insert(new Record("3", "John", 500));
		recDB.insert(new Record("22", "Mike", 2500));
		recDB.insert(new Record("13", "Mark", 1760));
		recDB.insert(new Record("19", "Bob", 500));
		recDB.insert(new Record("7", "Cathy", 500));
		
		Record r  = recDB.search("22");
		if(r == null)
			System.out.println("Not found");
		else 
			System.out.println("Found");

		r = recDB.search("34");
		if(r == null)
			System.out.println("Not found");
		else 
			System.out.println("Found");
		
		recDB.delete("19");
		recDB.delete("7");
		recDB.delete("3");
		recDB.delete("13");
		recDB.delete("21");
		recDB.delete("22");
		recDB.delete("3");
	}
}