Student and the use of an array to store a
collection of student records. In general, if we are maintaining a database
we need not only to store records, but to update the database by adding
and deleting records. We would also want to be able to look up individual
records. Here is a program which provides the "front end" to a student
database:
1 import java.io.*;
2 import java.util.*;
3
4 class StudentDatabaseUse
5 {
6 // Read a number of Student records from a file, store them in a
7 // database, and perform operations on them.
8 // The file is given as a command line operator
9
10 public static void main(String[] args) throws IOException
11 {
12 Database database=null;
13 Student newStudent,foundStudent;
14 BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
15 BufferedReader inFile;
16 String surname,command;
17 char ch;
18 int i;
19 if(args.length==0)
20 {
21 System.out.println("File name should be given as command-line argument");
22 System.exit(1);
23 }
24 try
25 {
26 inFile = new BufferedReader(new FileReader(args[0]));
27 database = new StudentDatabase1();
28 for(;;)
29 try
30 {
31 newStudent=Student.read(inFile);
32 database.insert(newStudent);
33 }
34 catch(PersonException e)
35 {
36 System.out.println(e.getMessage()+"\n");
37 }
38 }
39 catch(FullUpException e)
40 {
41 System.out.println("No room for any more records");
42 }
43 catch(FileNotFoundException e)
44 {
45 System.out.println("No file '"+args[0]+"' found");
46 System.exit(2);
47 }
48 catch(IOException e)
49 {
50 }
51 ch='l';
52 while(ch!='q')
53 {
54 switch(ch)
55 {
56 case 'l': database.list(); break;
57 case 'd': System.out.print("Enter surname of student to be deleted: ");
58 surname=in.readLine();
59 try {
60 database.delete(surname);
61 System.out.println("Record deleted\n");
62 }
63 catch(NotFoundException e)
64 {
65 System.out.println("No record found for "+surname+"\n");
66 }
67 break;
68 case 'r': System.out.print("Enter surname of student: ");
69 surname=in.readLine();
70 try {
71 foundStudent=(Student)database.retrieve(surname);
72 System.out.println("\nFull record is:\n");
73 System.out.println(foundStudent);
74 }
75 catch(NotFoundException e)
76 {
77 System.out.println("No record found for "+surname+"\n");
78 }
79 break;
80 case 'i': try {
81 newStudent=Student.promptedRead(in);
82 database.insert(newStudent);
83 System.out.println("Record inserted\n");
84 }
85 catch(PersonException e)
86 {
87 System.out.println(e.getMessage()+"\n");
88 }
89 catch(FullUpException e)
90 {
91 System.out.println("No room for any more records\n");
92 }
93 break;
94 case 'q': break;
95 default: System.out.println("Not a valid command");
96
97 }
98 do {
99 do {
100 System.out.print("Enter command: ");
101 command=in.readLine();
102 }
103 while(command.length!=0);
104 i=0;
105 do {
106 ch=command.charAt(i++);
107 }
108 while(ch==' '&&i<command.length());
109 }
110 while(ch==' ');
111 }
112 }
The program is designed to read a list of student records from a file, and
store them in a database. In this case, the file is given as as a command
line argument, so to run the program taking the data from a file called
mystudents you would have to type the Linux command:
% java StudentDatabaseUse1 mystudentsLine 26 is where the command line argument, which in the above case would store the string
"mystudents" is accessed as
args[0]. If the file named "mystudents" is not found
then a FileNotFoundException is created, this is caught on line
43, the System.exit(2) command on line 46 then causes the program
to halt right away. In general, System.exit(n) where
n is an integer causes program execution to halt. The
convention is that n is 0 if the program halts normally,
some other value if it is halting due to some error. In this case an
error code 2 is produced. The error code can be used in Linux, but you need
not be concerned with it at present - it will be ignored if the program is
just run normally.
The complex code on lines 98-109 is designed to make sure the program behaves sensibly no matter what the user enters in response to the prompt for a new command. It has to be able to read past blanks and newlines until it gets to a character which is treated as a command.
The database is declared on line 12, the initialisation to the special
value null here just indicates explicitly that it is not
referencing any object. It starts referencing an object on line 27 when a new
object of class StudentDatabase1 is created. The important thing
is that a completely object-oriented approach to the database is taken.
The database is only operated on through its methods: insert
on lines 32 and 82, list on line 56, delete on
line 60 and retrieve on line 71. Compare this with the example
in the Students page where there was no
separate class for a student database, it was just represented as an array
which could be accessed or modified by any array operation.
The importance of the separate object for the database is that now it does
not matter how the database is stored. We have only seen arrays at this
point for storing collections of objects, but there are other ways. We could
change the way we represented a database without having to change the
StudentDatabaseUse1 class, because that class does not depend
on any particular representation. This is what we referred to as
data hiding in the Dates: Part 3
examples. Just as in those examples we avoided being able to arbitarily
change the components of dates, which could result in invalid dates, so
here we avoid arbitary changing of the components of the database. As the
only way the database can be changed is through its methods, it can ensure
that these methods are written in such a way as to maintain its
consistency.
database
is declared to be of type Database whereas on line 27 it
is set to a new object of type StudentDatabase1. This can be
done if StudentDatabase1 is a subclass (i.e. inherits from)
Database, or implements it. In this case, Database
is just an interface (see the People example where
the idea of a Java interface is first introduced) which says what
the methods on a database are, but does not say how they are implemented. Here
is the code for it:
1 interface Database
2 {
3 public void insert(Object obj) throws FullUpException;
4 public void delete(String key) throws NotFoundException;
5 public Object retrieve(String key) throws NotFoundException;
6 public void list();
7 }
As you can see, it does not even mention Students. In fact this
is an interface for a general database which can store objects
of any sort. In Java the type Object means an object of any
sort. In fact any class which does not inherit from another class is treated
as automatically having Object as the superclass it inherits
from. The method insert inserts the object it takes as
its argument into the database (thus Database is a mutable
type as objects of that type can be changed by methods on them). The
method delete takes a string and deletes an object which
this string refers to. In the student database example, the string is the
surname of the student, so this operation is used to delete a student with a
given surname (for simplicity we will ignore the complexities caused by
more than one student having the same surname). Again, this is a mutating
operation. The method retrieve returns the object in the
database associated with a given string but does not change the database,
so it is non-mutating. The method list lists the entire
database. If a string is given as argument to delete or
retrieve but no object is found associated with that string
an exception is thrown. The exception is not one that is built into Java,
so a class for it is needed:
1 class NotFoundException extends Exception
2 {
3 NotFoundException(String s)
4 {
5 super(s);
6 }
7 }
Another exception, again not built-in, is thrown if there is not enough room
to store a new object in the database:
1 class FullUpException extends Exception
2 {
3 }
As a new FullUpException has no arguments, no more is needed
than that. A new NotFoundException has one argument (the string
which was used as reference) so a constructor method for it is necessary.
DatabaseDatabase interface, may implement that interface. Here is the
code for StudentDatabase1 which implements it using an
unordered array:
1 class StudentDatabase1 implements Database
2 {
3 // Implemented with an unordered array
4
5 private static final int MaxStudents=100;
6 private Student[] array;
7 private int numStudents;
8
9 public StudentDatabase1()
10 {
11 numStudents=0;
12 array = new Student[MaxStudents];
13 }
14
15 public void insert(Object obj) throws FullUpException
16 {
17 if(numStudents<MaxStudents)
18 array[numStudents++]=(Student)obj;
19 else
20 throw new FullUpException();
21 }
22
23 public void delete(String key) throws NotFoundException
24 {
25 int i;
26 for(i=0;i<numStudents;i++)
27 if(array[i].equalKey(key))
28 break;
29 if(i==numStudents)
30 throw new NotFoundException(key);
31 for(int j=i+1;j<numStudents;j++)
32 array[j-1]=array[j];
33 numStudents--;
34 }
35
36 public Object retrieve(String key) throws NotFoundException
37 {
38 int i;
39 for(i=0;i<numStudents;i++)
40 if(array[i].equalKey(key))
41 break;
42 if(i==numStudents)
43 throw new NotFoundException(key);
44 return array[i];
45 }
46
47 public void list()
48 {
49 for(int i=0; i<numStudents; i++)
50 System.out.println(array[i]);
51 }
52
53 }
Note that in order to assign a value of type Object to a
variable of type Student it is necessary to use type
conversion. This is done on line 71 of StudentDatabaseUse1
where the object retrieved from the database is converted from the
general Object type which is the return type of
retrieve to the specific Student type. It
is also done on line 15 of StudentDatabase1. Although the
database in StudentDatabase1 is meant to store
Student objects, the type of the argument to
insert and the return value of retrieve have
to be Object in order for it to implement Database.
Although StudentDatabase1 stores student records in an array,
the array is private so only a StudentDatabase1 object can
access it either to look at or alter its content. StudentDatabase1
objects also have a private NumStudents field giving the
number of students, which is also the portion of the array which is actually
in use. When a new StudentDatabase1 object is created, the
array is created, but numStudents is set to 0
indicating that none of the array is in use in a newly created database.
The length of the array in a StudentDatabase1 object is
declared as a static final variable, meaning there is just
one copy of it shared by all objects of type StudentDatabase1
and its value may not be changed by any of them. These declarations and the
constructor method for creating new StudentDatabase1 objects
are given on lines 5-13.
Inserting a new student record (done using method
The
As we have made quite a few changes to the class
The method used to retrieve a student record from the array of records
ordered by name, as given above is very inefficient. Suppose we were looking
for a name in a telephone directory. The way that
This leads us naturally onto a recursive way of locating a record with a given
name in an array ordered by name. We generalise the problem to locating the
position between two limits (equivalent to searching just one chunk of pages
in a telephone directory). We look at the midpoint - if the record we are
looking for happens to be there, we have found it. Otherwise we apply the
operation recursively, changing the limits to limit search to either those
places in the array below the midpoint or those places above it. If the limits
become equal then we have nowhere left to search, so no object with the
given name occurs in the array, and a
Here is a version of the student database class using binary search to locate
records in the array:
These notes were produced as part of the course
Introduction to Programming as it was given in the
Department of Computer Science at
Queen Mary, University of London
during the academic years 1998-2001.
Last modified: 1 Dec 1998
insert on lines
15-21 of StudentDatabase1) is easy - it is just put in the next
unused space in the array, the one indexed by numStudents, and
numStudents is increased by one. The only difficulty is that since
the array is of fixed length, attempting to store more student records than
its length could cause problems. If an unchecked attempt was made to store more
student records than the maximum set by MaxStudents, an
ArrayIndexOutOfBoundsException would be caused. However, in
this example before that happens, a FullUpException is
produced and thrown. This is caught on line 89 of the "front-end" class,
StudentDatabaseUse1 and an appropriate error message is printed.
delete and retrieve methods (lines 23-34 and
36-45 respectively) both go through the array one element at a time using a
for-loop, breaking if an element is found on which the equalKey
method with the string supplied as its argument returns true. It
is assumed that with student records, if S is of type
Student then S.equalKey(nm) will return
true if the surname of the student is equal to key,
false otherwise. If the loop in delete or
retrieve finishes without break being executed,
it can only have done so if no student with the given name has been found,
in which case a new NotFoundException is created and thrown.
In the case of delete, a further loop (lines 31-32) is needed
to move all the student records after the deleted one back one space in the
array in order not to leave a "hole". This is one of the major inefficiencies
of this method of representing the database (note however that since all
objects are actually references, "moving" a student record involves copying
only a reference to the data, not the data itself). Another source of
inefficiency is the need to look through all the records to find one for
a particular name. It would obviously be more convenient if the records
were stored in alphabetic order.
Student in
a piecemeal fashion, here is the version used now:
1 import java.util.*;
2 import java.io.*;
3
4 class Student extends Person
5 {
6 protected static int count=10000;
7 protected static final int MAXMARKS=30;
8 protected int numSubjects,studentNum;
9 protected int[] marks;
10 protected String firstNames;
11
12 public Student(int d,int m, int y,String n1,String n2,int num,int marks [])
13 throws PersonException
14 {
15 super(d,m,y,n1);
16 numSubjects=num;
17 this.marks=marks;
18 firstNames=n2;
19 studentNum=++count;
20 }
21
22 public static Student read(BufferedReader reader)
23 throws IOException,PersonException
24 {
25 int day,month,year,numMarks;
26 String name,marksString,dateString,nameString,firstNames;
27 StringTokenizer tokens;
28 int[] marks;
29 nameString=reader.readLine();
30 if(nameString==null)
31 throw new IOException();
32 tokens = new StringTokenizer(nameString);
33 firstNames = tokens.nextToken();
34 name=tokens.nextToken();
35 while(tokens.hasMoreTokens())
36 {
37 firstNames+=" "+name;
38 name=tokens.nextToken();
39 }
40 dateString=reader.readLine();
41 tokens = new StringTokenizer(dateString,"/");
42 day=Integer.parseInt(tokens.nextToken());
43 month=Integer.parseInt(tokens.nextToken());
44 year=Integer.parseInt(tokens.nextToken());
45 marks = new int[MAXMARKS];
46 marksString=reader.readLine();
47 tokens = new StringTokenizer(marksString);
48 numMarks=0;
49 while(tokens.hasMoreTokens())
50 marks[numMarks++]=Integer.parseInt(tokens.nextToken());
51 return new Student(day,month,year,name,firstNames,numMarks,marks);
52 }
53
54 public static Student promptedRead(BufferedReader reader)
55 throws IOException,PersonException
56 {
57 int day,month,year,numMarks;
58 String name,marksString,dateString,nameString,firstNames;
59 StringTokenizer tokens;
60 int[] marks;
61 System.out.println("Enter name (first names followed by surname on one line):");
62 nameString=reader.readLine();
63 if(nameString==null)
64 throw new IOException();
65 tokens = new StringTokenizer(nameString);
66 firstNames = tokens.nextToken();
67 name=tokens.nextToken();
68 while(tokens.hasMoreTokens())
69 {
70 firstNames+=" "+name;
71 name=tokens.nextToken();
72 }
73 System.out.println("Enter date of birth (in dd/mm/yy format):");
74 dateString=reader.readLine();
75 tokens = new StringTokenizer(dateString,"/");
76 day=Integer.parseInt(tokens.nextToken());
77 month=Integer.parseInt(tokens.nextToken());
78 year=Integer.parseInt(tokens.nextToken());
79 marks = new int[MAXMARKS];
80 System.out.println("Enter marks (all one one line):");
81 marksString=reader.readLine();
82 tokens = new StringTokenizer(marksString);
83 numMarks=0;
84 while(tokens.hasMoreTokens())
85 marks[numMarks++]=Integer.parseInt(tokens.nextToken());
86 return new Student(day,month,year,name,firstNames,numMarks,marks);
87 }
88
89 public String toString()
90 {
91 String marksString="";
92 for(int i=0;i<numSubjects;i++)
93 marksString+=" "+marks[i];
94 return "Name: "+firstNames+" "+name+
95 "\nDate of birth: "+dateOfBirth+
96 "\nStudent number: "+studentNum+
97 "\nMarks: "+marksString+"\n";
98 }
99
100 public int totalMarks()
101 {
102 int myMarks=0;
103 for(int i=0;i<numSubjects;i++)
104 myMarks+=marks[i];
105 return myMarks;
106 }
107
108 public double averageMark()
109 {
110 return (double)totalMarks()/numSubjects;
111 }
112
113 public boolean lowerTotalMarksThan(Student s)
114 {
115 return (totalMarks()<s.totalMarks());
116 }
117
118 public boolean lowerTotalMarksThan(int n)
119 {
120 return (totalMarks()<n);
121 }
122
123 public boolean lowerAverageMarkThan(Student s)
124 {
125 return (averageMark()<s.averageMark());
126 }
127
128 public boolean lowerAverageMarkThan(double d)
129 {
130 return (averageMark()<d);
131 }
132
133 public boolean equalKey(String key)
134 {
135 return name.equals(key);
136 }
137
138 }
Note there are two methods for reading a student record. One, called
read, on lines 22-52 is intended for reading the records from
a file, and so issues no prompts. The other is intended for reading a
student record as entered by the user of the program, so prompts for
each separate piece of information. This second method, called
promptedRead is on lines 54-87.
An implementation of
Here is another implementation of the Database using an ordered arrayDatabase interface,
still using an array, but this time storing the student records in
alphabetical order of name:
1 class StudentDatabase2 implements Database
2 {
3 // Implemented with an array ordered by name
4
5 private static final int MaxStudents=100;
6 private Student[] array;
7 private int numStudents;
8
9 public StudentDatabase2()
10 {
11 numStudents=0;
12 array = new Student[MaxStudents];
13 }
14
15 public void insert(Object obj) throws FullUpException
16 {
17 Student student=(Student)obj;
18 int i,j;
19 if(numStudents==MaxStudents)
20 throw new FullUpException();
21 else
22 {
23 for(i=0;i<numStudents&&array[i].beforeAlphabetically(student);i++);
24 for(j=numStudents;j>i;j--)
25 array[j]=array[j-1];
26 array[i]=student;
27 numStudents++;
28 }
29 }
30
31 public void delete(String key) throws NotFoundException
32 {
33 int i;
34 for(i=0;i<numStudents&&array[i].name.compareTo(key)<0;i++);
35 if(i==numStudents||array[i].name.compareTo(key)>0)
36 throw new NotFoundException(key);
37 for(int j=i+1;j<numStudents;j++)
38 array[j-1]=array[j];
39 numStudents--;
40 }
41
42 public Object retrieve(String key) throws NotFoundException
43 {
44 int i;
45 for(i=0;i<numStudents&&array[i].name.compareTo(key)<0;i++)
46 if(i==numStudents||array[i].name.compareTo(key)>0)
47 throw new NotFoundException(key);
48 return array[i];
49 }
50
51 public void list()
52 {
53 for(int i=0; i<numStudents; i++)
54 System.out.println(array[i]);
55 }
56
57 }
This time, since student records can't be inserted just after all the other
records, but instead have to be put in their correct space in the array,
the insert method has to move all records after the point
where the new one is inserted up a place. The delete method has
to move them down a place still. When we are retrieving or deleting a record,
we know that if we have passed the place where it would be in the alphabetic
ordering it can't be there, so we throw a NotFoundException
without looking further. The StudentDatabaseUse
program can be modified to use the ordered rather than the unordered array
representation simply by replacing line 27 with:
database = new StudentDatabase2();
The only difference that will be noted in the running of the program if this
change is made is what happens when the student records are listed. Both
implementations print the students in the order they are in the array, so
you will see that replacing the database implementation will change the
order in which the student records are printed from the order in which they
were inserted to the alphabetical order. For comparison, the file
StudentDatabase3.java gives a version in which the student
records are ordered by age. Inserting a student record has to ensure it is
put in the right place, but as the records aren't ordered by name,
retrieving and deleting a record involves looking through the whole array, until
we have found it or got to the end of the data.
retrieve does it
in StudentDatabase2 is like looking at the first name in the
telephone directory and then looking at every name in turn until we either
find the one we are looking for, or go past where it would be in
alphabetical ordering. However, the more usual way to find a name in
a telephone directory is to open it somewhere in the middle. If the name
we are looking for comes before the point we have opened, we concentrate
on the pages on the left-hand side, if it comes after we concentrate on
the pages on the right-hand side. Then we repeat the operation with the
pages we have in our hand, picking a place in the middle, and cutting the
pages in half, down until we have just the right page.
NotFoundException is
thrown. Instead of going through the array one at a time so on average looking
at half the records in the array to find the one being searched for, this
way (known as binary search) cuts the array in half each time. It is
easy to see this means looking at far fewer records to find the one being
searched for, in fact the maximum will be the logarithm to the base 2 of
the number of records in the array (consider, for example that 2 to the power
of 10 is 1024, so the logarithm of 1024 to the base 2 is 10, or in other words,
you can cut 1024 in half ten times to get to one element, so at most you would
need to look at 10 records to find the one you are looking for given a name
and the records ordered by name).
1 class StudentDatabase4 implements Database
2 {
3 // Implemented with an array ordered by name
4
5 private static final int MaxStudents=100;
6 private Student[] array;
7 private int numStudents;
8
9 public StudentDatabase4()
10 {
11 numStudents=0;
12 array = new Student[MaxStudents];
13 }
14
15 public void insert(Object obj) throws FullUpException
16 // Insert an object in the array, keeping it ordered alphabetically by name
17 {
18 Student student=(Student)obj;
19 int i,j;
20 if(numStudents==MaxStudents)
21 throw new FullUpException();
22 else
23 {
24 for(i=0;i<numStudents&&array[i].beforeAlphabetically(student);i++) ;
25 for(j=numStudents;j>i;j--)
26 array[j]=array[j-1];
27 array[i]=student;
28 numStudents++;
29 }
30 }
31
32 public void delete(String key) throws NotFoundException
33 // Delete an object in the array whose name is equal to key
34 {
35 int i = locate(key,0,numStudents);
36 for(int j=i+1;j<numStudents;j++)
37 array[j-1]=array[j];
38 numStudents--;
39 }
40
41 public Object retrieve(String key) throws NotFoundException
42 // Return an object in the array whose name is equal to key
43 {
44 return array[locate(key,0,numStudents)];
45 }
46
47 public void list()
48 // Print the entire contents of the database
49 {
50 for(int i=0; i<numStudents; i++)
51 System.out.println(array[i]);
52 }
53
54 private int locate(String key,int from,int before) throws NotFoundException
55 // Locate the position of an object with name field equal to key
56 // in the array locations starting at from and up to but not including
57 // before.
58 {
59 int mid,compare;
60 if(from>=before)
61 throw new NotFoundException(key);
62 mid=(from+before)/2;
63 compare=array[mid].name.compareTo(key);
64 if(compare==0)
65 return mid;
66 else if(compare>0)
67 return locate(key,from,mid);
68 else
69 return locate(key,mid+1,before);
70 }
71
72 }
Again, simply changing line 27 in the StudentDatabaseUse
program will cause this version of the database to be used. Note that the
method locate is private, so it can be used within class
StudentDatabase4, called by delete on line
35, and retrieve on line 44, but it may not be used by methods
in any other class.
Matthew Huntbach