Algorithms and Data Structures in an Object-Oriented Framework (“ADSOOF”)
Priced Objects and Comparable Objects
We have noted that classes in Java define types in terms of the methods
that may be called on an object of a particular apparent type, and also say
how those methods work in terms of what they do to the variables inside the
object. However, Java allows these two separate aspects to be separated out
through the use of the concept of an interface
. Please
note this is a specialist usage of the word “interface” to refer to an
aspect of Java programming, so do not confuse it with the more general use
of the word, for example when we talk about the “human computer interface”
meaning how programs interact with the human user.
An interface
in Java is like a class which only tells us what
methods may be called on objects of its type, it does not tell us how those
methods work. A Java interface
is written in a file like a
Java class, except that the word interface
is used instead of
the word class
, and methods are given only by their
headers. Here is a simple example:
interface PricedObject { public int getPrice(); }Just this is found in the file
PricedObject.java
in
the code directory for this section. What this means
is that if an object is of apparent type PricedObject
we can
call the zero-argument method getPrice
on it and it will
return an integer. Remember, as we saw
previously
that a Java object may have several types. No Java object may have as
its actual type a type given by a Java interface. But it could have as its
actual type a type which is a subtype of a Java interface. Its
apparent type would be an interface type if it is accessed through a
variable of that type.
We have already seen a class
DrinksMachine
where one of the methods is the zero-argument getPrice
.
However, for a DrinksMachine
object to be considered to
have type PricedObject
the class not only has to have
this method, but it also has to indicate that it implements
the interface PricedObject
. To do this, it just needs to have
the words implements PricedObject
added after the header
to the class, so it becomes:
import java.util.ArrayList; class DrinksMachine implements PricedObject { ...with everything else the same as before. Note that while a class can only extend one other class (using
extends
), it can implement (using
implements
) any number of Java interfaces. If a class
implements more than one interface, the interfaces it implements are
listed after the word implements
separated by commas.
Now let's consider another class which implements PricedObject
.
Below is a simple example, where objects represent words whose price is
determined by their Scrabble score
(Scrabble
is a game which involves putting letters togethers to make up words, with the
letters that are harder to use having higher scores). Here is the code:
class ScrabbleWord1 implements PricedObject { private String str; public static final int[] scores = {1,3,3,2,1,4,2,4,1,8,5,1,3,1,1,3,10,1,1,1,1,4,4,8,4,10}; public ScrabbleWord1(String s) { str = s; } public String getWord() { return str; } public int getPrice() { String str1 = str.toUpperCase(); int score = 0; for(int i=0; i<str1.length(); i++) score+=scores[str1.charAt(i)-'A']; return score; } public String toString() { return str; } }As you can see, the only thing this has in common with the
DrinksMachine
code is that it has a method with header
public int getPrice()
and that this is indicated by
having implements PricedObject
in the class header.
Note this is only given as an example, it is not a very efficient way
of implementing this concept since every time the method getPrice
is called, the Scrabble score has to be calculated again. A more
efficient implementation would calculate it just once and store the result
so it could be used again without recalculation (since Scrabble scores
are fixed, they do not change over time).
The way in which Scrabble scores are calculated here is worth considering.
There is an array of integers called scores
in which the first
item is the score of the letter 'A'
(1), the second the score of the
letter 'B'
(3), the third the score of 'C'
(3) and so on.
You can use characters as if they are integers, they are equivalent to their
ASCII representation. Where we have str1.charAt(i)-'A'
this is
the ASCII representation of the i
th character of str1
less the ASCII representation of 'A'
. So that gives us the position
of the i
th character of str1
, and we use that to
index the letter scores. Note that declaring the array scores
as static
means there is just one variable of this name shared
by all ScrabbleWord1
objects, and declaring it as final
means that its value cannot be changed.
The importance of the type PricedObject
is that it enables
us to write methods which take arguments where the only method we need
call on them is getPrice
returning an integer. This enables
us to write general code which can be applied to a variety of types of
object rather than write separate but near identical code for each
different type of object. For example, the following method:
public static PricedObject cheaper(PricedObject m1,PricedObject m2) { if(m1.getPrice()<m2.getPrice()) return m1; else return m2; }can be used to take two of any type of object and return whichever is the cheapest as given by its
getPrice
method. We can use it
to compare two DrinksMachine
objects or two
ScrabbleWord1
objects (and actually we can use it to compare
a DrinksMachine
object with a ScrabbleWord1
object).
The type given for the arguments
simply indicates that the objects compared must be ones which have a
getPrice
method (and which are declared as such by heading
them with implements PricedObject
). Suppose this method
is put in a class called PricedObjectOps
. As it is
a static method, the method is called on the class name, this is
one of those classes which is used to bring together a number of related
static methods rather than to define a type of object. Then the following
code shows the method used to compare two drinks machines:
import java.util.Scanner; class UseDrinksMachines7 { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.print("Enter an identifier for a drinks machine: "); String id = input.next(); System.out.print("Enter its price: "); int p = input.nextInt(); DrinksMachine mach1 = new DrinksMachine(id,p); System.out.print("Enter an identifier for another drinks machine: "); id = input.next(); System.out.print("Enter its price: "); p = input.nextInt(); DrinksMachine mach2 = new DrinksMachine(id,p); DrinksMachine mach3 = (DrinksMachine) PricedObjectOps.cheaper(mach1,mach2); System.out.println("The cheaper machine is "+mach3.getIdentity()); } }For convenience this is a slightly modified version of
DrinksMachine
that gives each DrinksMachine
object an identity set by its constructor,
which can be obtained by a call of the method getIdentity
(the code for it is
here).
This extra method is not a necessary aspect of implementing the interface PricedObject
, however.
The next code shows the same cheaper
method used to compare two Scrabble words:
import java.util.Scanner; class TestScrabble1 { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.print("Enter a word: "); ScrabbleWord1 word1 = new ScrabbleWord1(input.next()); System.out.print("Enter another word: "); ScrabbleWord1 word2 = new ScrabbleWord1(input.next()); if(PricedObjectOps.samePrice(word1,word2)) System.out.println("They have equal Scrabble scores"); else { ScrabbleWord1 word3 = (ScrabbleWord1) PricedObjectOps.cheaper(word1,word2); System.out.println("The word with lower Scrabble score is \""+word3+"\""); } } }This code also uses another method which is general to any object of a class which implements
PricedObject
:
public static boolean samePrice(PricedObject m1,PricedObject m2) { return m1.getPrice()==m2.getPrice(); }Here
return m1.getPrice()==m2.getPrice()
is just a more
concise way of writing if(m1.getPrice()==m2.getPrice()) return true;
else return false
. A similar method is:
public static boolean isCheaper(PricedObject m1,PricedObject m2) { return m1.getPrice()<m2.getPrice(); }Note the difference between this and the method
cheaper
given above. Both take two arguments of type PricedObject
,
but cheaper
returns a reference to whichever of these is the
cheaper, while isCheaper
just returns a boolean value,
true
if the first argument is cheaper than the second,
false
otherwise.
Above we saw that if we wrote a method which had parameters with type
PricedObject
, we could call that method with arguments
to match the parameter of any type which implements PricedObject
,
and we gave two types which did this, DrinksMachine
and
ScrabbleWord1
.
Now suppose we want to do something similar with a method which takes
an arrayList of objects and returns a reference to whichever of them
has the highest price according to their getPrice
method.
We might suppose the following code would work:
public static PricedObject mostExpensive(ArrayList<PricedObject> a) { PricedObject highestSoFar = a.get(0); for(int i=1; i<a.size(); i++) { PricedObject next = a.get(i); if(isCheaper(highestSoFar,next)) highestSoFar = next; } return highestSoFar; }where the parameter given as type
ArrayList<PricedObject>
could be matched against an arrayList whose actual type was either
ArrayList<DrinksMachine>
or
ArrayList<ScrabbleWord1>
, or an
arrayList of some other type which implements PricedObject
.
But this does not work in Java. Although a variable of type
PricedObject
may refer to an object of type DrinksMachine
or ScrabbleWord1
, a variable of type
ArrayList<PricedObject>
cannot refer to an object
of type ArrayList<DrinksMachine>
or
ArrayList<ScrabbleWord1>
.
In general terms, if Y
is a subclass of X
,
then a variable of type X
may refer to an object of type
Y
, but a variable of a type parameterised with X
may not refer to an object of the same type parameterised with Y
.
As a simple explanation of why this is the case, an object of type
ArrayList<PricedObject>
may have objects of type
ScrabbleWord1
and of type DrinksMachine
(and any other
type which implements PricedObject
) added to it. But an object
of type ArrayList<DrinksMachine>
should not have objects
of type ScrabbleWord1
added to it, and an object of type
ArrayList<ScrabbleWord1>
should not have objects
of type DrinksMachine
added to it. We would not be able to
protect against this if these arrayList objects were referred to by variables
of type ArrayList<PricedObject>
.
To get around this problem, Java introduces the idea of
bounded generic types. Here is how the code for the
method mostExpensive
should be written using this
concept:
public static <T extends PricedObject> T mostExpensive(ArrayList<T> a) { T highestSoFar = a.get(0); for(int i=1; i<a.size(); i++) { T next = a.get(i); if(isCheaper(highestSoFar,next)) highestSoFar = next; } return highestSoFar; }This is a method where
T
is a type parameter, but the
additional information is given that T
is of some type
which is a subtype of PricedObject
. So T
could
be DrinksMachine
or ScrabbleWord1
or it could
be PricedObject
itself (since any type is counted
as a subtype of itself). Which one is determined by the element type
of the arrayList passed to it as an argument. Since we know T
must be one of these types, we know we can call the method getPrice
on objects of type T
, and we know we can pass objects of
type T
to methods whose parameters are of type
PricedObject
.
Using the idea of bounded generic types, a better way of declaring the method
cheaper
we considered above is as follows:
public static <T extends PricedObject> T cheaper(T m1,T m2) { if(m1.getPrice()<m2.getPrice()) return m1; else return m2; }This means we no longer have to use casting for the result of a call to the method
cheaper
because when we have:
DrinksMachine mach3 = PricedObjectOps.cheaper(mach1,mach2);the type variable
T
will be set to DrinksMachine
, and when we have:
ScrabbleWord1 word3 = PricedObjectOps.cheaper(word1,word2);it will be set to
ScrabbleWord1
. What happens is that at compile time there
is a check that the two arguments are of the same specific type, and then the return
type will also be of that same type, so no need to cast the more general type
PricedObject
to that more specific type. It is also still possible to
compare a ScrabbleWord1
object and a DrinksMachine
object using
cheaper
, which would take the form:
PricedObject priced = PricedObjectOps.cheaper(word,mach);where
word
is a variable of type ScrabbleWord1
and mach
is a variable of type DrinksMachine
. Here the type variable T
gets set to PricedObject
because it has to be a type that applies to both
word
and mach
.
Comparable
The type PricedObject
was given here as just a
very simple example of the way Java uses interfaces to enable
general code to be written. Although this was devised just
as an illustration, the Java library has many interface types
which are predefined. One of the most widely used, and relevant
to this module, is Comparable
. If you had to write code
for Comparable.java
yourself, it would look like:
interface Comparable<T> { int compareTo(T item); }So, it is like our
PricedObject
interface in that
any class will be a subtype so long as it has the one method specified,
and the class header indicates that it implements the interface.
Here the one method in the interface is compareTo
,
while in PricedObject
it was getPrice
.
This compareTo
method is the one we have already seen
to compare objects of type String
and Integer
.
As we have seen, if we have two objects referenced by variables
obj1
and obj2
then obj1.compareTo(obj2)
returns a negative integer if obj1
is less than obj2
,
a positive integer if obj1
is greater than obj2
and
0
if they are equal in their natural ordering.
With strings, the natural ordering is alphabetic.
Where Comparable
differs from PricedObject
is that it is a parameterised type. So, just like ArrayList
and LispList
which we have seen earlier, it is a way of
constructing a type from a element type. The type
Comparable<String>
has the method
int compareTo(String item)
in it, the type
Comparable<Integer>
has the method
int compareTo(Integer item)
in it, and so on.
If you want a type Thing
to have its own version
of the compareTo
method, then you must give it the
class header:
class Thing implements Comparable<Thing>As an example, let us consider a better class for Scrabble words, which we will call just
ScrabbleWord
. This is better than
the class ScrabbleWord1
we gave earlier, because it defines
an ordering using the Comparable
interface, and so may be
used with all the built-in generic code in Java which uses that interface.
Here is the code for it:
class ScrabbleWord implements Comparable<ScrabbleWord> { private String str; private int score; public static final int[] scores = {1,3,3,2,1,4,2,4,1,8,5,1,3,1,1,3,10,1,1,1,1,4,4,8,4,10}; public ScrabbleWord(String s) { str = s; String str1 = str.toUpperCase(); score = 0; for(int i=0; i<str1.length(); i++) score+=scores[str1.charAt(i)-'A']; } public String getWord() { return str; } public int getScore() { return score; } public int compareTo(ScrabbleWord word) { return word.score-score; } public String toString() { return str+"("+score+")"; } }You can find this in the file
ScrabbleWord.java
in
the code folder.
Here the Scrabble scores are worked out when a new ScrabbleWord
object is created, and stored in a variable in the
ScrabbleWord
object called score
.
This class has its own compareTo
method, which provides
a natural ordering for objects of the class, which is the reverse
order of Scrabble scores. So, the higher the Scrabble score of a word,
the earlier it would come in any sorted collection of ScrabbleWord
objects.
The code for the method compareTo
here shows a feature of Java and similar
object-oriented languages which can seem odd, because we think of a variable declared as
private
in a class as being protected from interference by any other object
other than the one it is in. So when a method is called on an object, the code in that
method can use the private
variables of that object but those variables are
not otherwise not available for any other code to access directly. However, the code in a
method can also make direct use of the private
variables of any other
objects of that class which it has access to. In the code for compareTo
, the word
score
on its own means the score
variable of the ScrabbleWord
object which the method call to compareTo
was made on, while word.score
means the score
variable of the ScrabbleWord
object passed as an
argument through the parameter named word
, which can be accessed directly even though
it is private to that object.
The importance of defining ScrabbleWord
as implementing
Comparable<ScrabbleWord>
, and more generally of being
able to define any class as implementing Comparable<T>
with T
set to itself, is that we can now write generic code where the
same code can be used for any type of objects, so long as it
implements the Comparable
interface. Previously, we
had to write separate code to sort collections of strings, collections of
integers, and collections of any other type. But that is unnecessary.
Here, for example, is a class which provides a static method
to sort (using selection sort) any arrayList, so long as the objects
in the arrayList are of a class which implements the Comparable
interface:
import java.util.ArrayList; class SelSort { public static <T extends Comparable<T>> void sort(ArrayList<T> a) { for(int i=0; i<a.size()-1; i++) { int pos = findMinPos(a,i); swap(a,i,pos); } } private static <T extends Comparable<T>> int findMinPos(ArrayList<T> a,int pos) { for(int i=pos+1; i<a.size(); i++) if(a.get(i).compareTo(a.get(pos))<0) pos=i; return pos; } private static <T> void swap(ArrayList<T> a,int pos1,int pos2) { T temp = a.get(pos1); a.set(pos1,a.get(pos2)); a.set(pos2,temp); } }With this, the call
SelSort.sort(a)
will sort the arrayList
referred to by the variable a
in ascending numerical
order if it is an arrayList of integers, in alphabetic order if it is an
arrayList of strings, and in order of Scrabble score (highest scoring
words coming first) if it is an arrayList of ScrabbleWord
objects.
Here is some code you can use to test the above class to sort
an arrayList of ScrabbleWord
objects:
import java.util.*; class SortScrabble1 { public static void main(String[] args) throws Exception { Scanner input = new Scanner(System.in); System.out.println("Enter some words (all on one line):"); String line = input.nextLine(); String[] words = line.split(" "); ArrayList<ScrabbleWord> a = new ArrayList<ScrabbleWord>(); for(int i=0; i<words.length; i++) a.add(new ScrabbleWord(words[i])); SelSort.sort(a); System.out.println("The words in order of their Scrabble score are:\n"+a); } }and here is some code which uses it to sort an arrayList of integers:
import java.util.*; class SortIntegers1 { public static void main(String[] args) throws Exception { Scanner input = new Scanner(System.in); System.out.println("Enter some integers (all on one line):"); String line = input.nextLine(); String[] words = line.split(" "); ArrayList<Integer> a = new ArrayList<Integer>(); for(int i=0; i<words.length; i++) a.add(Integer.parseInt(words[i])); SelSort.sort(a); System.out.println("Sorting the integers gives:\n"+a); } }The code for the other sorting algorithms which we gave previously can also be generalised to sort an arrayList of any type of object (so long as it implements
Comparable
). All that needs
to be done is replace the specific type of object being sorted with
the type variable T
and then give the bound to
T
that it extends Comparable<T>
for those methods which call compareTo
on objects in
the arrayList, or which call other methods which do so. The
method compareTo
is the only method which the sort
code requires to be called on items in the arrayList being sorted,
so that is enough to completely generalise the code. Here is the
code for generalised quick sort:
import java.util.ArrayList; class QuickSort { public static <T extends Comparable<T>> void sort(ArrayList<T> a) { sort(a,0,a.size()); } private static <T extends Comparable<T>> void sort(ArrayList<T> a,int from,int to) { if(to>from+1) { T pivot = a.get(from); int low=from+1,high=to-1; while(low<high) { while(low<high&&a.get(low).compareTo(pivot)<0) low++; while(pivot.compareTo(a.get(high))<0) high--; if(low<high) { swap(a,high,low); low++; high--; } } while(pivot.compareTo(a.get(high))<0) high--; swap(a,from,high); sort(a,from,high); sort(a,high+1,to); } } private static <T> void swap(ArrayList<T> a,int pos1,int pos2) { T temp = a.get(pos1); a.set(pos1,a.get(pos2)); a.set(pos2,temp); } }So calling
QuickSort.sort(a)
where a
refers
to an arrayList will sort that arrayList, using quick sort, and sorting
it in the natural order given by the compareTo
method in
the class for the objects being sorted.
Java's built-in sort code uses the same generalisation. We saw that
the static method sort
taking an arrayList as an argument and
sorting that arrayList destructively is provided in the class
Collections
which is in the java.util
package.
So Collections.sort(a)
will sort the arrayList referred to by
a
according to its natural ordering. It will do this
even if the objects in the arrayList are ones we have defined
ourselves rather than of a class which is already provided by the
Java code library. All that is required, if they are of a type
we have defined ourselves, is that the class for that type is indicated
correctly as implementing the Comparable
interface.
One further requirement is needed for the code above to be completely general. Where we have written
<T extends Comparable<T>>to give a type parameter to methods and say this must be a type which extends
Comparable
with itself as element type,
it is more correct to write:
<T extends Comparable<? super T>>What this means is that
T
must implement the
interface Comparable
but possibly with a element type
which is a superclass of T
. To see why this is
so, consider the examples we gave
previously of a class
DrinksMachine
, and two extended versions of this
class, ExtDrinksMachine1
and ExtDrinksMachine2
.
If we want objects of type DrinksMachine
to be
able to be sorted by our generic sort code, we would put a method
with header int compareTo(DrinksMachine item)
into the class DrinksMachine
and add to the class
header implements Comparable<DrinksMachine>
.
This method would be inherited by ExtDrinksMachine1
and ExtDrinksMachine2
. So ExtDrinksMachine1
does not implement Comparable
with itself as element type,
rather it implements Comparable
with DrinksMachine
as element type, and the same applies to ExtDrinksMachine2
.
If all this seems rather complicated, you need not worry too much
about it. The main thing you need to know is that if you are writing code
for an algorithm which depends on items having some sort of ordering,
you can make the code general by using a type variable such as
T
for the type of the items, and then put
<T extends Comparable<? super T>>
in the headers for the methods of the code before the return type
of each method.
As an example, consider the code we used to sort Lisp lists using quick sort
previously. This
was written then as code to sort a Lisp list of integers. A generalised
version of this code which can sort a Lisp list of any element type (so long as
it is a type which implements Comparable
) is given below:
class QuickSortLispLists { public static <T extends Comparable<? super T>> LispList<T> sort(LispList<T> ls) { return sort(ls,LispList.<T>empty()); } private static <T extends Comparable<? super T>> LispList<T> sort(LispList<T> ls1,LispList<T> ls2) { if(ls1.isEmpty()) return ls2; T pivot = ls1.head(); ls1 = ls1.tail(); LispList<T> smaller = LispList.empty(); LispList<T> greater = LispList.empty(); for(; !ls1.isEmpty(); ls1=ls1.tail()) { T h = ls1.head(); if(h.compareTo(pivot)<0) smaller = smaller.cons(h); else greater = greater.cons(h); } greater = sort(greater,ls2); return sort(smaller,greater.cons(pivot)); } }With this, if
ls1
and ls2
are of type
LispList<String>
, the call ls2=QuickSortLispLists.sort(ls1)
will cause ls2
to refer to a new Lisp list which contains the strings
from ls1
sorted in alphabetic order. If ls1
and
ls2
are of type LispList<ScrabbleWord>
, the call
ls2=QuickSortLispLists.sort(ls1)
will cause ls2
to refer
to a new Lisp list which contains the words
from ls1
sorted in order of their Scrabble score. And so on for
Lisp lists of any element type which implements Comparable
.
Below is code which gives a front end so you can test this with Scrabble words:
import java.util.Scanner; class SortLispListScrabble { public static void main(String[] args) { Scanner in = new Scanner(System.in); LispListThe methodls1,ls2; System.out.print("Enter a list (of words): "); String str = in.nextLine(); ls1 = parseScrabbleLispList(str); System.out.println("The list you entered (with Scrabble scores) is: "); System.out.println(ls1); ls2 = QuickSortLispLists.sort(ls1); System.out.println("The list sorted is: "); System.out.println(ls2); } public static LispList<ScrabbleWord> parseScrabbleLispList(String str) { String line = str.trim(); String contents = line.substring(1,line.length()-1).trim(); if(contents.length()==0) return LispList.empty(); String[] words = contents.split(","); LispList<ScrabbleWord> list = LispList.empty(); for(int i=words.length-1; i>=0; i--) list = list.cons(new ScrabbleWord(words[i])); return list; } }
parseScrabbleLispList
is needed to convert
a string of words into a Lisp list of ScrabbleWord
objects.
It works similar to code we have seen before for constructing Lisp lists
from their text equivalent. It first strips off the opening and closing
square brackets, then splits the resulting string into individual words
using the comma as the separator, then creates ScrabbleWord
objects for each word and joins them to a list.
Last modified: 8 March 2019