You will rewrite class Database so that it stores its records in sorted order and uses binary search to do lookups, and you will test your variant with the TestTheDatabase application.
It is all too common for a company to release multiple versions of the ``same'' software product --- all the versions are supposed to ``do the same thing,'' but some versions have error repairs, others have faster implementations, extra features, and so on. People become attached to one version or another of the software product, so the multiple versions remain in use for a long time (E.g., consider Windows 98, 2000, NT, XP, etc.)
What does it mean for related pieces of software to ``do the same thing''? One answer is stated as a Java interface --- for example, what is a database supposed to ``do''? Here is a Java interface that describes a database's behavior:
package Database;
/** interface Database defines the methods associated with a database
* data structure */
public interface Database
{ /** find locates a record in the database based on a key
* @param key - the key of the desired record
* @return (the address of) the desired record;
* return null if record not found. */
public Record find(Key k);
/** insert inserts a new record into the database.
* @param r - the record
* @return true, if record added; return false if record not added */
public boolean insert(Record r);
/** delete removes a record in the database based on a key
* @param key - the record's key (identification)
* @return true, if record is found and deleted; return false otherwise */
public boolean delete(Key k);
}
Now, any class that we write that has the three methods listed above ---
that
implements Database --- will do just fine
as a ``database.''
Frankly, interface Database should have been used along with
the interfaces for Record and Key,
but perhaps this would have been too much to swallow all at once.
But now it is time.
At http://www.cis.ksu.edu/~schmidt/300s05/Assign/Assn3 is a new version of package Database. The new package uses the above-stated interface Database, plus a class, class DatabaseVersion1, which implements interface Database. Class DatabaseVersion1 is, in fact, the same coding of class Database that we studied during the lectures.
In the same package is a class DatabaseVersion2, which also implements Database, but has different codings of the insert, retrieval, and delete methods. Either ``version'' of database will work just fine with the TestTheDatabase application.
Also found in http://www.cis.ksu.edu/~schmidt/300s05/Assign/Assn3 is a copy of the TestTheDatabase package. TestTheDatabase is modified to use interface Database so that we can ``plug in'' whichever version of database we wish. Significantly, the application is identical to that used in Week 2 of lectures except for one phrase only in class Start:
package TestTheDatabase;
import Database.*;
public class Start
{ public static void main(String[] args)
{ Database d = new DatabaseVersion2(10); // We change only this one line!
TestFrame f = new TestFrame();
InsertController c1 = new InsertController(d,f);
FindController c2 = new FindController(d,f);
DeleteController c3 = new DeleteController(d,f);
}
}
This trick emphasizes that there is little difference
in Java
between data types (of objects) and interfaces (to objects) ---
a Java object is ``code+interface,'' and a Java interface is ``interface but no code yet.''
We learned that arrays of objects-with-keys are searched efficiently if the objects are sorted by ascending key value. Your assignment is to write a class DatabaseVersion3 implements Database whose insertion method maintains an array whose objects are sorted by ascending key value and whose lookup method utilizes binary search.
You must employ DatabaseVersion3 with the TestTheDatabase application, and you must also implement the latter's DELETE button so that the user can delete records.
Unfortunately, the current version of BlueJ will not build the jar file as required, so you must build the jar file using the jar command, which you type into a command-prompt window. To learn how to do this, please read the information posted on the CIS300 web page: http://www.cis.ksu.edu/~schmidt/300s05/bluej.packages.html
If you have problems constructing the jar file, please contact the CIS300 TAs or the instructor.
Finally, use the submission page at http://www.cis.ksu.edu/~schmidt/300s05/Assign/submit.html to submit Assign3.jar.