/**
 * 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 Fang Yang, TA for 22C:21, Fall 07
 * Modified again by Sriram Pemmaraju, Aug 31st, 2007
 */
public class DynamicRecordDB {

	//change 1
	private int maxRecords = 1;
	private int numRecords = 0;
	private Record[] recordList;

	//change 2
	/**
	* allocates an array of size 1
	*/
	DynamicRecordDB(){
		recordList = new Record[maxRecords];
	}

	/**
	*allocate an array of size n
	*/
	DynamicRecordDB(int n){
		maxRecords = n;
		recordList = new Record[maxRecords];
	}


	/**
	* Inserts a record into the ordered array in a sorted fashion.
	* Double the size of the array, if overflow may occur.
	* @param rec - The record to be inserted.
	*/
	public void insert (Record rec) {
		int i;
		//change 3
		// Check for overflow.
		// Double the size, if overflow occurs.
		if (numRecords == maxRecords-1) {

			//create of new array of double size.
			Record[] tempRecord = new Record[2*maxRecords];

			// Copy contents of recordList into tempRecord
			for(i = 0; i < maxRecords; i++)
				tempRecord[i] = recordList[i];

	        // Make recordList point to tempRecord
	        recordList = tempRecord;
	        //Change maxRecords to the new value
	        maxRecords = 2*maxRecords;
		}

		// Find the position to insert in
                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("----------maxRecords = "+maxRecords+"----------------");
		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) {

		long startTime, stopTime, runTime;
		DynamicRecordDB recDB = new DynamicRecordDB();

		//test n=10000, 10500,...,20000
		int insertNum = 10000;

		while(insertNum <= 20000){
			
			int totalRunTime = 0;

			for(int rpt = 0; rpt < 10; rpt++)
			{
			
				startTime = System.currentTimeMillis();
		
				// Create an empty record data base
				recDB = new DynamicRecordDB();

				//insert the records
				for(int i=0; i < insertNum; i++)
					recDB.insert(new Record(Integer.toString(i), Integer.toString(i), i));

				stopTime = System.currentTimeMillis();

				//run time for this repetition of the experiment 
				runTime = stopTime - startTime;

				// accumulated run time over all repetition of this experiment
				totalRunTime += runTime;
			}

			System.out.print("numRecords="+recDB.numRecords);
			System.out.println(";maxRecords="+recDB.maxRecords);
			System.out.println(totalRunTime*1.0/10);
			System.out.println("Per operation run time: " + totalRunTime*1.0/(10*insertNum));
			
			insertNum += 500;
		}

	}

}