BirthDate which extended the type
Date by adding a name field. The following
is the declaration for a type Person which seems very similar:
1 class Person
2 {
3 protected String name;
4 protected Date dateOfBirth;
5
6 public Person(int d,int m,int y,String n) throws PersonException
7 {
8 try
9 {
10 name=n;
11 dateOfBirth = new Date(d,m,y);
12 }
13 catch(DateException e)
14 {
15 throw new PersonException("Invalid date-of-birth: "+
16 e.getMessage()+" for "+n);
17 }
18 }
19
20 public String toString()
21 {
22 return "Name: "+name+"\nDate of birth: "+dateOfBirth+"\n";
23 }
24
25 public boolean older(Person p)
26 {
27 return dateOfBirth.lessThan(p.dateOfBirth);
28 }
29
30 public boolean beforeAlphabetically(Person p)
31 {
32 return name.compareTo(p.name)<0;
33 }
34 }
Objects of both type BirthDate and type Person
store a date and a name. However, whereas a BirthDate object
is an extended Date object, a Person object is
not a form of Date object, rather it has a Date
object as one of its fields (declared on line 4). The two different
relationships are known as IS-A and HAS-A relationships.
A BirthDate object IS-A Date object, but a
Person object HAS-A Date object as part of it.
In general, it only makes sense to use inheritance when you are developing
type T2 from existing type T1 if it makes sense to
say a T2 "is a" T1. So a BirthDate is
a Date, because we were thinking of it just as a date with the
extra information of a person's name added to it. However, you cannot say
"a person is a date", though you can say "a person has a (birth) date".
The class Person has a toString method which means
when you print an object of type Person you will get something
that looks like:
Name: Fred Date of Birth: 5/6/78It has two methods which allow objects of type
Person to be
compared, older which compares them by their date of birth,
and beforeAlphabetically which compares them according to
how their names are in alphabetical ordering. The method older
makes use of the method lessThan which was provided with the
class Date we developed, while the method
beforeAlphabetically makes use of the compareTo
method which is built into the String class. Note that
compareTo returns an integer, not a boolean. The integer is
negative if the string the method is attached to comes before the
string given as its argument alphabetically, positive if it comes after,
and zero if the two strings are composed of identical letters in the same
order.
The class Person has its own exception which is thrown if
the arguments provided to create a new Person object are
invalid. As the class is given, the only way they could be invalid is if
the separate arguments which go to form the person's dat of birth form an
invalid date. This would cause a DateException to be thrown
given our previous development of the Date class, but lines
13-17 catch the DateException and throw a
PersonException in its place. The code for
PersonException is simply:
class PersonException extends Exception
{
PersonException(String s)
{
super(s);
}
1 import java.io.*;
2
3 class People1
4 {
5 // Read a number of Person records from a file, store them in an array
6 // Sort them by age.
7
8 static final int MAXPEOPLE=100;
9
10 public static void main(String[] args) throws IOException
11 {
12 String filename;
13 Person [] data;
14 int count=0;
15 BufferedReader in = Text.open(System.in),inFile;
16 for(;;) try
17 {
18 System.out.print("\nEnter file name to read from: ");
19 filename=Text.readString(in);
20 inFile=Text.open(filename);
21 break;
22 }
23 catch(FileNotFoundException e)
24 {
25 System.out.println("No file of that name found");
26 }
27 data = new Person[MAXPEOPLE];
28 try
29 {
30 for(;;) try
31 {
32 data[count++] = readPerson(inFile);
33 }
34 catch(PersonException e)
35 {
36 System.out.println(e.getMessage());
37 count--;
38 }
39 }
40 catch(IOException e)
41 {
42 }
43 catch(ArrayIndexOutOfBoundsException e)
44 {
45 System.out.print("Maximum number of people ("+MAXPEOPLE);
46 System.out.println(") exceeded");
47 }
48 count--;
49 System.out.println("\nThe records (sorted by age) are:\n");
50 PeopleSorterByAge.sort(data,count);
51 for(int i=0;i<count;i++)
52 System.out.println(data[i]);
53 }
54
55 public static Person readPerson(BufferedReader reader)
56 throws IOException,PersonException
57 {
58 int d,m,y;
59 String n;
60 d=Text.readInt(reader);
61 m=Text.readInt(reader);
62 y=Text.readInt(reader);
63 n=Text.readString(reader);
64 return new Person(d,m,y,n);
65 }
66
67 }
As a slight innovation, lines 16-26 and lines 30-37 might at first
glance seem to introduce a new sort of statement, but it is just a
different layout. The layout
for(;;) try
{
statements0
}
catch(Exception1 e)
{
statements1
}
is just a for-loop whose body is the try statement. It can be read as
meaning "repeat doing statements0 and statements1
when an Exception1 occurs, until an exception which is not
an Exception1 occurs". With a break added:
for(;;) try
{
statements0;
break;
}
catch(Exception1 e)
{
statements1
}
it can be read as "repeat doing statements0 followed by
statements1 until statements0 has been executed
without an Exception1 occurring".
On lines 55-65, the readPerson method reads a date followed
by a name from a file, and so can in fact use the same files as were used
for the BirthDate examples, as these were also read in the date
then name order. Where in the BirthDate
examples we called a method sort from a class
DateSorter to sort the array of BirthDate
objects, here (on line 50) we call a method sort from a class
PeopleSorterByAge to sort the array of BirthDate
objects in order of age. Here is the code for the class
PeopleSorterByAge:
1 class PeopleSorterByAge
2 {
3
4 public static void sort(Person [] a,int n)
5 // Sort (in place) the first n people in array a.
6 // Uses selection sort, sorts by age
7 {
8 int sorted,minPos;
9 for(sorted=0;sorted<n;sorted++)
10 {
11 minPos=indexOldest(a,sorted,n);
12 swap(a,sorted,minPos);
13 }
14 }
15
16 private static void swap(Person [] a,int pos1,int pos2)
17 // Swap the people at index pos1 and pos2 in array a
18 {
19 Person temp;
20 temp=a[pos1];
21 a[pos1]=a[pos2];
22 a[pos2]=temp;
23 }
24
25 private static int indexOldest(Person [] a,int pos1,int pos2)
26 // Return the index of the oldest person in the portion
27 // of array a starting at index pos1 and up to but not
28 // including index pos2.
29 {
30 int i,pos=pos1;
31 for(i=pos1+1; i<pos2; i++)
32 if(a[i].older(a[pos]))
33 pos=i;
34 return pos;
35 }
36
37 }
As you can see, it's very similar to the code for DateSorter.
Do note that since the aim of the discussion here is not to look at ways
of sorting but rather to look at aspects of object-orientation, no attempt
has been made to introduce an efficient sort algorithm. In order to focus
attention on the main points, the inefficient but easy to program selection
sort method is used; this is not a recommendation to use it in general.
The sort method is one which sorts in place - the array it takes is actually
changed by repositioning the objects within it to put them in age sorted
order.
If we are sorting a collection of objects where each object has a number
of fields, we have to specify which field we're using for sorting. We
could decide to sort the Person records not in order of age,
but in alphabetical order of name. To do that, we could write a new
sort class called, say, PeopleSorterByName. Then all we need
do is change line 50 in People1 from
PeopleSorterByAge.sort(data,count);to
PeopleSorterByName.sort(data,count)This is actually done in the file
People2.java. The file
PeopleSorterByName.java could look exactly like the file
PeopleSorterByAge.java except that line 32 would be:
if(a[i].beforeAlphabetically(a[pos]))It would help keep the program names meaningful to change the name of the private method
indexOldest to something like
indexFirstAlphabetically, but to Java itself the name used
doesn't matter.
However, in doing this we are not really following the re-use principle of
object-oriented programming. Re-use does not mean we actually take a file
of code, copy it, and change the copied version. It should mean we can make
direct use of code we have already written. So, for example, we made calls
to existing methods rather than copied the code which did something from one
place to another. We inherited from an existing class rather than copy
the code for the class and modify it. Ideally what is wanted here is some
general sorting code that could be re-used in any situation where we need
to sort an array of objects. One very nice consequence of this would be that if
we decided to change our sort algorithm from selection sort to something
more efficient, we could just change and recompile the one general sort file,
and then all the programs that make use of it would automatically change
their way of sorting to the more efficient one. Obviously this would be much
easier to deal with than going through PeopleSortByAge.java,
PeopleSorterByName.java and other files which sort
Person objects changing each one to sort using the new
algorithm.
Person objects by age or by name with
a general call to some ordering object that does the comparison. If the
ordering object is one that compares by name, the whole sort will be by
name, if the ordering object is one that compares by age, the whole sort will
be by age. Code which is generalised in this way is called generic
code. Here is a generic sorting class for arrays of Person
objects:
1 class PeopleSorter
2 {
3
4 PeopleOrder myOrder;
5
6 public PeopleSorter(PeopleOrder order)
7 {
8 myOrder=order;
9 }
10
11 public void sort(Person [] a,int n)
12 // Sort (in place) the first n people in array a.
13 // Uses selection sort, sorts by PeopleOrder object
14 {
15 int sorted,minPos;
16 for(sorted=0;sorted<n;sorted++)
17 {
18 minPos=indexFirst(a,sorted,n);
19 swap(a,sorted,minPos);
20 }
21 }
22
23 private static void swap(Person [] a,int pos1,int pos2)
24 // Swap the people at index pos1 and pos2 in array a
25 {
26 Person temp;
27 temp=a[pos1];
28 a[pos1]=a[pos2];
29 a[pos2]=temp;
30 }
31
32 private int indexFirst(Person [] a,int pos1,int pos2)
33 // Return the index of the first person in the portion
34 // of array a starting at index pos1 and up to but not
35 // including index pos2.
36 {
37 int i,pos=pos1;
38 for(i=pos1+1; i<pos2; i++)
39 if(myOrder.before(a[i],a[pos]))
40 pos=i;
41 return pos;
42 }
43
44 }
Line 38 uses an object called myOrder which has a method
called before to compare two Person objects at
different positions in the array. Where PeopleSorterByAge and
PeopleSorterByName were classes with only static methods,
PeopleSorter has non-static methods. That means that
individual PeopleSorter objects are created, and methods
are attached to them, rather than attached to the class. myOrder
is in fact a field which each PeopleSorter object has. You
can create a version of PeopleSorter which sorts by age by
creating a new PeopleSorter object whose myOrder
field is an object that compares people by age. You can create a version of
PeopleSorter which sorts by name by creating a new
PeopleSorter object whose myOrder field is an object
that compares people by age. Lines 6-9 are the constructor used to create
new PeopleSorter objects. Line 4 is where the myOrder
field is declared, this field has type PeopleOrder which we
shall describe later. The method swap in PeopleSorter
(on lines 23-30) remains static because it does not depend on the value
of myOrder so can be used unchanged in any
PeopleSorter object.
So, if comp is a comparer object, of type PeopleOrder,
a new object which can be used to sort arrays according to the comparison
method in comp can be created by:
sorter = new PeopleSorter(comp);where
sorter is a variable of type PeopleSorter.
Of course, it is possible to declare such a variable and create a value
for it at the same time:
PeopleSort sorter = new PeopleSorter(comp);Having done this,
sorter.sort(data,count);sorts the
Person objects in the array data,
assuming that the first count cells in the array are actually
in use to store data.
The code for PeopleOrder is as follows:
interface PeopleOrder
{
public boolean before(Person p1,Person p2);
}
That's it. What this means is that an object of type PeopleOrder
has to have a method before which takes two Person
objects as arguments and returns a boolean. It is an example of an
interface.
An interface is like a class, but does not provide the details of the
methods and fields within it. So in the PeopleOrder
example, the interface simply gives the header for the method
before, but no body, that is it doesn't say how the result
is calculated. Note also the use of the Java keyword interface
in the place of class. The idea of an interface is that the
details are filled in by a form of inheritance. For example, here is the code
for PeopleOrderByAge which fills in the details for
PeopleOrder, giving one way of doing the before
operation:
class PeopleOrderByAge implements PeopleOrder
{
public boolean before(Person p1,Person p2)
{
return p1.older(p2);
}
}
Note the use of the Java keyword implements rather than the
words extends used for standard inheritance. When a class
implements an interface, it has to give a method for every method in
the interface. This is different from inheritance where if a method is not
mentioned it is inherited from the superclass, but if a method from the
superclass is mentioned (with the same argument types) the result is to
give a new method which overrides the old one. Or another way to put it is
that a class which implements an interface has to override every
method in the interface, since otherwise there would be methods with no
body. Another point about interfaces is that whereas in Java a class may
only extend one other class, it may implement more than one interface.
So a field or variable of type PeopleOrder can be filled with
any object of any class so long as that class implements
PeopleOrder. Dynamic binding means that a before
call attached to an object declared to be of type PeopleOrder
will in fact be carried out by whatever before method is in
the class of that object. So, for example, an object which has a
before method that compares people by age may be declared
with name comp and created by:
PeopleOrderByAge comp = new PeopleOrderByAge();Then that object can be used to fill the
myOrder field
in a PeopleSorter object, as shown above. That will make the
PeopleSorter object one that sorts by age. The whole thing
could be done in one step:
PeopleSort ageSorter = new PeopleSorter(new PeopleOrderByAge());A sorter that sorts people by name could be declared and created by:
PeopleSort nameSorter = new PeopleSorter(new PeopleOrderByName());Here we need a class which we have called
PeopleOrderByName
which implements PeopleOrder, and has a before
method which compares two people by name. Here it is:
class PeopleOrderByName implements PeopleOrder
{
public boolean before(Person p1,Person p2)
{
return p1.beforeAlphabetically(p2);
}
}
With these two declarations, if we were to call
ageSorter.sort(data,count);it would cause the data in array
data to be sorted by age,
while if we were to call
nameSorter.sort(data,count);it would sort it by alphabetical order of name. The files
People3.java and People4.java show this. It is
possible to compress things even further by not explicitly naming the object
which does the sorting. For example, if line 50 in People1.java
were replaced by
new PeopleSorter(new PeopleOrderByAge()).sort(data,count);the data would be sorted by age, whereas if it were replaced by
new PeopleSorter(new PeopleOrderByName()).sort(data,count);it would be sorted by name. In both cases a new
PeopleSorter
object is created and used just the once for its sort method,
when it is created it has to be specialised by giving it a new comparer
object, either a PeopleOrderByAge or a
PeopleOrderByName object. Note that when an object is
created but is no longer used by anything, it is automatically destroyed.
This is referred to as garbage collection. In other languages,
such as C, you have to write a command to destroy an object, otherwise it
never disappears (and the computer memory it takes up is wasted) until the
program terminates.
1 import java.io.*;
2
3 class People6
4 {
5 // Read a number of Person records from a file, store them in an array
6 // Filter them to give all those older than a given date
7
8 static final int MAXPEOPLE=100;
9
10 public static void main(String[] args) throws IOException
11 {
12 String filename;
13 Person [] data;
14 int count=0;
15 int day,month,year;
16 Date dDay;
17 BufferedReader in = Text.open(System.in),inFile;
18 for(;;)
19 try
20 {
21 System.out.print("\nEnter file name to read from: ");
22 filename=Text.readString(in);
23 inFile=Text.open(filename);
24 break;
25 }
26 catch(FileNotFoundException e)
27 {
28 System.out.println("No file of that name found");
29 }
30 data = new Person[MAXPEOPLE];
31 try
32 {
33 for(;;)
34 try
35 {
36 data[count++] = readPerson(inFile);
37 }
38 catch(PersonException e)
39 {
40 System.out.println(e.getMessage());
41 count--;
42 }
43 }
44 catch(IOException e)
45 {
46 }
47 catch(ArrayIndexOutOfBoundsException e)
48 {
49 System.out.print("Maximum number of people ("+MAXPEOPLE);
50 System.out.println(") exceeded");
51 }
52 count--;
53 System.out.println("\nThe records are:\n");
54 for(int i=0;i<count;i++)
55 System.out.println(data[i]);
56 for(;;)
57 try
58 {
59 System.out.print("Enter day: ");
60 day=Text.readInt(in);
61 System.out.print("Enter month: ");
62 month=Text.readInt(in);
63 System.out.print("Enter year: ");
64 year=Text.readInt(in);
65 dDay=new Date(day,month,year);
66 break;
67 }
68 catch(DateException e)
69 {
70 System.out.println("Invalid date: "+e.getMessage());
71 }
72 count=PeopleFilterByAge.oldFilter(data,count,dDay);
73 System.out.println("The records of those older than this date are:")
;
74 for(int i=0;i<count;i++)
75 System.out.println(data[i]);
76 }
77
78 public static Person readPerson(BufferedReader reader)
79 throws IOException,PersonException
80 {
81 int d,m,y;
82 String n;
83 d=Text.readInt(reader);
84 m=Text.readInt(reader);
85 y=Text.readInt(reader);
86 n=Text.readString(reader);
87 return new Person(d,m,y,n);
88 }
89
90 }
Here we use, on line 72, a special class which filters an array of people
by age. This is the code for it:
1 class PeopleFilterByAge
2 {
3
4 public static int oldFilter(Person [] a,int n,Date d)
5 {
6 int count=0;
7 for(int i=0;i<n;i++)
8 if(a[i].older(d))
9 a[count++]=a[i];
10 return count;
11 }
12
13 public static int youngFilter(Person [] a,int n,Date d)
14 {
15 int count=0;
16 for(int i=0;i<n;i++)
17 if(!a[i].older(d))
18 a[count++]=a[i];
19 return count;
20 }
21
22 }
It has two methods, one for giving those older than a date passed in
as an argument, one for giving those younger. The methods work by changing
the data in the array they take as input, using i as an
index to go through the array, and count as an index which
goes through the array but is increased only when a new record which
fits the test is found. Since i is always greater than or
equal count we can safely copy the value from cell i
of the array into cell count without losing any data. The methods
return as their output the value of count after this operation,
which is the number of records in the new filtered data.
Note that in order to deal with this, we need to introduce a new method
into the class Person. Here it is:
public boolean older(Date d)
{
return dateOfBirth.lessThan(d);
}
You will see that it has the same name, older as a previous
method, but takes a different argument, a Date rather than
a Person. This is allowed in Java, and the actual code used when
a call to older is made will depend on the argument to that
call: if it is a Person object, the older method
for Person object arguments given previously will be used, if it
is a Date object, this new method will be used.
However, the code is not very general, as it can only filter by age. A generic version would involve a general filtering object which takes as its argument an object which chooses between individuals. Here is Java code for such a generic filtering class:
1 class PeopleFilter
2 {
3
4 PersonChoose myChoose;
5
6 public PeopleFilter(PersonChoose chooser)
7 {
8 myChoose=chooser;
9 }
10
11 public int filter(Person [] a,int n)
12 {
13 int count=0;
14 for(int i=0;i<n;i++)
15 if(myChoose.choose(a[i]))
16 a[count++]=a[i];
17 return count;
18 }
19
20 }
Just as PeopleSorter was a generic class for sorters,
with each PeopleSorter object having its own ordering
object when it is created, so PeopleFilter enables
filtering objects to be created, each taking its own chooser object
which decides whether someone is to be chosen or not in the filtering.
Just as the type PeopleOrder was just an interface, giving
the header of a single before method, so PersonChoose
is just an interface giving the header for a single choose
method:
1 interface PersonChoose
2 {
3 public boolean choose(Person p);
4 }
Here is a class for choosing people by their age which implements
PersonChoose:
1 class PersonChooseByOldAge implements PersonChoose
2 {
3 Date myDate;
4
5 public PersonChooseByOldAge(Date d)
6 {
7 myDate=d;
8 }
9
10 public boolean choose(Person p)
11 {
12 return p.older(myDate);
13 }
14
15 }
It is slightly more complex than the PeopleOrderByAge class
because each PersonChooseByOldAge object has to have its
own Date object, which is set when the object is constructed.
With this, we can replace line 72 in the previous People6
program by:
PeopleFilter myFilter = new PeopleFilter(new PersonChooseByOldAge(dDay));and it will work exactly the same. The advantage of doing it this way is that we can choose to put other chooser objects in the place of the
PersonChooseByOldAge(dDay) objects to filter on any other basis
we require.
Note: if you want to see some more notes on a similar theme to the notes here, I found the following example of notes on sorting, interfaces and polymorphism which you may find useful.
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: 8 Feb 2000