CIS300 Fall 2000: Assignment 2

You are asked to modify class Database in the following three ways:

1. Write this new method and insert it into class Database:

   /** sort  compresses the database and sorts its records so that
     *  the records are ordered by their keys.  */
   public void sort()
   

   To help understand how to write the method, consider the following:
   • The database's insert method inserts a new record into the first empty space it finds.
   • When the database's delete method deletes a record, it leaves an empty space (a null value) in the array; this creates ``gaps.''
   So, when sort is invoked, it must do two things:
   1. It must compress the records in the database, moving them to the left so that there are no ``gaps.''
   2. It must implement a standard sorting algorithm.

2. Modify the private locationOf method so that it uses binary search to find the element for which it is searching.

   Of course, binary search can only be employed on a sorted database. So, if the database contains ``gaps'' or is unsorted, then locationOf must invoke sort before it conducts its binary search.

3. For testing purposes, write this method:

   /** retrieveAllKeys  extracts from the database the keys of all
     *  the records stored therein.
     * @return an array holding the (addresses of) the keys of all the
     *  the records in the database.  The keys are listed in the array
     *  in the same order as the records are stored in the database. */
   public Key[] retrieveAllKeys()
   

   Use this method to help write testing programs that exercise your modifications.

You are not required to insert the modified class Database into any new application---indeed, the modified class Database should work just fine with the MemoApplication you wrote last week! But, to test your modifications, you should write some tester programs of your own design to see if the methods operate properly under all circumstances.

Here is an example of a tester program that tests some, but not all, features of the new methods:

import Database.*;   // this is your modified  package Database
import TestTheDatabase.*;  // this is the demo program from two weeks ago
/** TestDatabase tests the database's methods. */
public class TestDatabase
{ public static void main(String[] args)
  { Database d = new Database(5);  // holds 5 records

    // see the TestTheDatabase package for classes BasicPerson and IntegerKey:
    IntegerKey k1 = new IntegerKey(1);
    IntegerKey k2 = new IntegerKey(2);
    IntegerKey k3 = new IntegerKey(3);
    BasicPerson fred = new BasicPerson("Fred", k3); 
    BasicPerson lucy = new BasicPerson("Lucy", k1);
    BasicPerson ricky = new BasicPerson("Ricky", k2);

    d.insert(fred);
    d.insert(lucy);
    d.insert(ricky);
    Key[] keys = d.retrieveAllKeys();
    printKeys(keys); // see below for  printKeys  method; should print 3 1 2

    d.sort();
    printKeys(d.retrieveAllKeys());  // should print 1 2 3
    d.delete(k2);
    printKeys(d.retrieveAllKeys());  // should print 1 3
  }

  /** printKeys prints the integer keys held in its array parameter,  k  */
  private static printKeys(Key[] k)
  { for ( int i = 0;  i != k.length;  i=i+1 )
        { if ( k[i] == null )  // a ``safety check''
               { System.out.print("null "); }
          else { IntegerKey key = (IntegerKey)(k[i]);
                 System.out.print(key.valOf() + " ");
               }
        }
    System.out.println();
  }          
}

What to submit

Next, create the .jar file, Assign2.jar. (See the instructions at http://www.cis.ksu.edu/classes/300/Assign/how.to.jar.html for instructions for preparing .jar files.) Use the submission page at http://www.cis.ksu.edu/classes/300/Assign/submit.html to submit Assign2.jar.