/**
 * 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
 * Modified by Sriram Pemmaraju again on Sept 22nd 2007
 */
public class optimizedRecordDB {

	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;	
		}

		
		// search for where rec should go by using binarySearch
                int location = binarySearch(rec.ssn);

                // if newSSN already exists then do nothing
                if ((rec.ssn).compareTo(recordList[location].ssn) == 0)
                        return;

		// Shift all records one space down
		for (int j=numRecords-1; j>=location; j--) {
			recordList[j+1] = recordList[j];
		}
		
		// Insert the new record
		recordList[location] = 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) {
		
		// search for newSSN by calling binarySearch
                int location = binarySearch(newSSN);

                // if newSSN is not found, nothing needs to be done
                if (newSSN.compareTo(recordList[location].ssn) != 0)
                        return;

		// Shift all records that are beyond slot i, 
 		// to the left by one slot
		for (int j = location; 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 int
	 * This is a utility function that will be used by other methods
	 * such as insert, delete, and search
	 */
        private  int binarySearch (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 mid;

                        // 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

		// if newSSN is not found, then eventually first will point to first
		// record with a ssn larger than newSSN
                return first;

        } // end of search function

	
	/**
	 * 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();

		// search for newSSN by calling binarySearch
		int location = binarySearch(newSSN);

		// if newSSN exists then location will point to it
		if (newSSN.compareTo(recordList[location].ssn) == 0) 
			return new Record(recordList[location].ssn, recordList[location].name, recordList[location].pay);
		else
			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");
	}
}