COSC 311
Programming Assignment #1
Database with Sorted Arrays as Indexes
Please Note: this assignment has been revised
You *MUST* demonstrate your
program to me on the day it is due or earlier. You should come to your demo with a laptop
and the program ready to execute or it should be runnable on a lab machine. Your well documented program listing
is due in class at the start of class (didn't put your name on it ? No comments?
Sloppy style
? You'll lose points). You will have 5 minutes to demo the
program to me and should expect me to ask you questions regarding the
program.
There will be a discussion in class about this assignment.
What to do:
Create a simple database with three fields : ID, LastName,
FirstName all as Strings. You should define a class called
DataBaseRecord with
three private String elements (the three fields), along with the
appropriate methods. Here's what mine looked like:
public class DataBaseRecord {
private String ID;
private String first;
private String second;
DataBaseRecord(String a,String b,String c)
{
ID=new String(a);
first=new String(b);
second=new String(c);
}
public String toString()
{
return ID+" "+first+" "+second;
}
}
You should also declare an object called DataBaseArray which is
an array of DatabaseRecords. Records of type DataBaseRecord should be
added at the end of the DataBaseArray. Create an IndexRecord class:
public class IndexRecord {
private String key;
private int where;
//other stuff here
}
Now create an IndexArray. This is an array of IndexRecord and is to be
implemented as an OrderedArray class like the one we developed in
class. That is, insertions must maintain the order in the array, where
order is maintained by the key value. Note that this means you need to
define a compareTo method in the IndexRecord object.
Iterators
Your IndexArray must implement an interator. An iterator is simply a
variable that maintains a current reference into the data structure. In
this instance, since IndexArray is a static array, the iterator is just
an integer; a pointer into the array. You should implement the
following methods:
void iteratorInitFront - set the iterator to zero
void iteratorInitBack - set the iterator to the last element in the array
boolean hasNext - returns true if iterator<= current last index in the array, false otherwise.
boolean hasPrevious - returns true if iterator>0 , false otherwise
int getNext - returns the where component of the IndexRecord referenced by iterator and then increments the iterator
int getPrevious - returns the where component of the IndexRecord referenced by iterator and then decrements the iterator
Finally, create an class called DataBase. Here's what mine looked like:
public class DataBase {
private DataBaseArray myDB;
private IndexArray ID , First , Last;
public DataBase()
{
myDB=new DataBaseArray(100);
ID = new IndexArray(100);
First=new IndexArray(100);
Last=new IndexArray(100);
}
//other stuff here
}
To get an idea of how the iterators work, here's the code I have for printing out the database in ascending order by first name:
public void ListByFirstAscending()
{
First.iteratorInitFront();
while(First.hasNext())
{
int temp=First.getNext();
System.out.println(myDB.retrieve(temp));
}
}
Here's the output from the following for my sample data set:
1234 alice jones
9988 dave bing
2244 ed smiley
6633 ellen nance
3234 mac edwards
6655 mary rogers
9999 mike adams
4234 roger morris
2233 sue charles
1235 zelda smith
My sample driver program (I used this
to test my data structures. Your actual driver program is more complex
and provided elsewhere):
public class UseIt {
public static void main(String[] args) {
// TODO Auto-generated method stub
DataBase d=new DataBase();
d.insertIt("1234", "alice", "jones");
d.insertIt("1235", "zelda", "smith");
d.insertIt("9999", "mike", "adams");
d.insertIt("9988", "dave", "bing");
d.insertIt("2233", "sue", "charles");
d.insertIt("2244", "ed", "smiley");
d.insertIt("6655", "mary", "rogers");
d.insertIt("6633", "ellen", "nance");
d.insertIt("4234", "roger", "morris");
d.insertIt("3234", "mac", "edwards");
d.ListByID();
System.out.println("****");
d.ListByFirst();
System.out.println("*************");
d.ListByLast();
}
}
But, what do I do about deleted records ?
Good question! Read CAREFULLY!
Make sure to explicitly state in a comment at the top of your program which option you are doing:
Option1) (extra 10% added to grade)
Deleted IDs, first names, and last names
should be deleted from their respective indexes (sorted arrays for this
assignment). In addition, the record number of the deleted record
should be pushed onto a statically declared stack called deleteStack.
When your program wants to add a new record to the database, it should
first check to see if deleteStack is empty. If deleteStack is empty,
just add the new record at the end of the large array (we assume you
are using an integer pointer to reference the end of the database
array). If deleteStack is not empty, pop the stack to get the record
number of where to insert the next element.
Option 2) (no bonus points)
Just delete from the three indexes. The records remain in the main
array, but since no index references this data, it will never be
printed out.
And yet another bonus:
Receive another bonus of 10% if you implement the IndexRecord as a
generic. That is , the parameter determines the type of the instance
variable key. You would instantiate the parameter in the DataBase class.
But be careful:
What will lose points: You should follow directiosn here closely. You will lose 50% of your grade for each of the following
- your IndexArray is not implemented as an OrderedArray.
- if you maintain order of your IndexArray by sorting the array
- if you implement the DataBaseArray as three arrays of String
- if you implement the IndexArray as two arrays: one of type String and the other as type int.
- if you do not use the driver program exactly as it is given