Now, we know that if you want a collections framework that
arranges the elements within itself, we need to use trees. So, if we would like
our elements to have a natural order, we need to either use TreeSet or TreeMap.
In this tutorial, we are going to focus on TreeSet, although what we learn
about TreeSet is pretty much applicable to TreeMap. Now in the past tutorials,
we learnt how to use TreeSet and TreeMap with Java’s inbuilt datatypes.
We saw
that for strings, Java will order the elements in alphabetical order while for
numerical elements, Java will use the ascending order as the natural order.
Now, a problem arises when we want to use our own custom
objects as elements of a set or as keys to a map. You see, Java doesn’t know
what natural order you want to apply to your elements. In fact, if you try to
add your objects to a TreeMap or a TreeSet without defining a natural order,
Java will return an error.
For example, let us create a class Bird, give it String
instance variable name and an int instance variable tagNumber. We will create a
constructor that allows us to instantiate the Bird objects as we create them
and we will also give the class a toString() method for a user-friendly output
to the console. Finally, we will create a TreeSet and add a couple of Bird
objects to it.
public class Bird {
private int
tagNumber;
private
String name;
public
Bird(int tagNumber, String name) {
this.tagNumber
= tagNumber;
this.name
= name;
}
public
String toString () {
return
“tagNumber is: ” + tagNumber + “ name is: ” + name;
}
public
static void main(String[] args) {
Set<Bird>
birds = new TreeSet<Bird>();
birds.add(new
Bird(1, “hawk”);
birds.add(new
Bird(5, “pigeon”);
birds.add(new
Bird(7, “owl”);
birds.add(new
Bird(1, “hawk”);
}
}
Java will not allow you to run the above program because you
are trying to add items to a TreeSet, which implements a natural order, with
objects of a class that hasn’t defined a natural order. So, how can we define a
natural order for the class Bird? Well, we have to go to the first line where
we create the line and implement an interface called Comparable. Then, we need
to tell Java which objects should be compared to objects of the current class.
So in our case, we are comparing Bird objects with other Bird objects. As such,
the class definition will look like this:
public class Bird implements Comparable<Bird> {
private int
tagNumber;
private
String name;
public
Bird(int tagNumber, String name) {
this.tagNumber
= tagNumber;
this.name
= name;
}
public
String toString () {
return
“tagNumber is: ” + tagNumber + “ name is: ” + name;
}
public
static void main(String[] args) {
Set<Bird>
birds = new TreeSet<Bird>();
birds.add(new
Bird(1, “hawk”);
birds.add(new
Bird(5, “pigeon”);
birds.add(new
Bird(7, “owl”);
birds.add(new
Bird(1, “hawk”);
}
}
Now, remember that in the tutorial on interfaces, we learnt
that when a class implements an interface, it has to define all the methods
listed within that interface. The Comparable interface has only one method
called compareTo(). So, we have to implement it in the class like this:
public class Bird implements Comparable<Bird> {
private Integer
tagNumber;
private
String name;
public
Bird(Integer tagNumber, String name) {
this.tagNumber = tagNumber;
this.name
= name;
}
public
String toString () {
return
“tagNumber is: ” + tagNumber + “ name is: ” + name;
}
@Override
public int
compareTo(Bird bird) {
return
0;
}
public
static void main(String[] args) {
Set<Bird>
birds = new TreeSet<Bird>();
birds.add(new
Bird(1, “hawk”);
birds.add(new
Bird(5, “pigeon”);
birds.add(new
Bird(7, “owl”);
birds.add(new
Bird(1, “hawk”);
}
}
The compareTo Method
So the compareTo() method looks like this:
@Override
public int compareTo(Bird bird) {
return
0;
}
Now pay very close attention. In the compareTo() method:
We want to return -1 if the class object is less than the
object in the method’s parameter.
We want to return +1 if the class object is greater than the
object in the method’s parameter.
We want to return 0 if the class object is equal to the
object in the method’s parameter.
Now, what we want to do is to have the Bird objects to be
sorted by their tagNumber in numerical order. Since tagNumber is an Integer, it
already has a defined natural order, just like strings have a defined natural
order. So we are going to define the method like this:
@Override
public int compareTo(Bird bird) {
return
tagNumber.compareTo(bird.tagNumber);
}
Defining the hashCode() and equals() methods
If you want to add items to a set, and have Java consider
them as unique, and if you want to add elements to a map and have Java consider
the keys unique, you need to define a hashCodeYou can get your IDE to generate
the hashCode() and equals() methods for you. In Eclipse, right-click the class
file, go to Source, then click on “Generate hashCode() and equals()”.
When you have done all the above steps, you will find that
your TreeSet will sort in numerical order based on the tagNumber. If you want a
reverse numerical order or a descending order, you just place a negative(-)
sign in front of the tagNumber.compareTo(bird.tagNumber); statement like this:
@Override
public int compareTo(Bird bird) {
return
-tagNumber.compareTo(bird.tagNumber);
}
That’s all for this tutorial. In case you have any questions
or comments, please leave them in the comments section below and I will address
them.
In the next tutorial, we look at Queues.
Until next time, take care.
No comments:
Post a Comment