/**
 * 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
 */
public class RecordDB {

	private static int maxRecords = 20;
	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 (numRecords == maxRecords-1) {
			return;	// Increase the size of the array maybe
		}

		// Find the position to insert in
		int i;
		for (i=0; i<numRecords; i++) {
			if (recordList[i].ssn > rec.ssn)
				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++;
		
		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 (long ssn) {
		int i;
		for (i=0; i<numRecords; i++) {
			
			// SSN not found
			if (recordList[i].ssn > ssn) {
				System.out.println("Record not found: " + ssn);
				return;
			}
			
			// SSN found in slot i
			if (recordList[i].ssn == ssn) {
				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--;

		printAll();
	}
	
	/**
	 * Binary search for the record with the given SSN
	 * @param ssn
	 * @return
	 */
			
	public Record search (long ssn) {
		
		printAll();
		int first=0, last=numRecords-1;
		
		while (true) {
			int current = (first+last)/2;
			
			if (recordList[current].ssn == ssn) {
				System.out.println("Found at number " + current);
				return recordList[current];
			}
			
			if (last==first) {
				System.out.println("Record not found: " + ssn);
				return null;
			}
			
			if (recordList[current].ssn > ssn) {
				last = current-1;
				continue;
			}
			
			if (recordList[current].ssn < ssn) {
				first = current+1;
				continue;
			}
		}
	}
	
	/**
	 * 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));
		
		recDB.search(22);
		recDB.search(34);
		
		recDB.delete(19);
		recDB.delete(7);
		recDB.delete(3);
		recDB.delete(13);
		recDB.delete(21);
		recDB.delete(22);
		recDB.delete(3);
	}
}