You will rewrite class Database so that it stores its records in sorted order and uses binary search to do lookups, and you will use your variant with the TestTheDatabase application presented in Week 2 of lectures.
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. There are many other examples.)
What does it mean for related pieces of software to ``do the same thing''? One answer is stated as a Java interface: Reconsider the database example from the first two weeks of lecture --- what is a database supposed to ``do''? Here is a Java interface that describes a database structure'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 in Week 2,
but perhaps this would have been too much to swallow all at once.
But now it is time.
To illustrate this idea, at http://www.cis.ksu.edu/~schmidt/300f04/Assign/Assn2 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 Week2.
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. Which one do you like? Which one is faster? Simpler?
Also found in http://www.cis.ksu.edu/~schmidt/300f04/Assign/Assn2 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)
{ // construct and assemble the components:
Database d = new DatabaseVersion2(10); // We changed only this one line!
TestFrame f = new TestFrame(d);
}
}
This trick emphasizes that there is almost no difference
in Java
between data types (of objects) and interfaces (of objects)!
If you remember this idea, you will do well at ``plug-and-play''-style
programming.
We learned that arrays of objects-with-keys are searched search most efficiently if the objects are sorted by ascending key value. Your assignment is to write a class DatabaseVersion3 implements Database that maintains an array whose objects are sorted by ascending key value and that utilizes binary search.
You must employ DatabaseVersion3 with the TestTheDatabase application, and you must implement the latter's DELETE button so that the user can delete records.