Damn! I just can’t get that linkedlist to sort! What did I ever do to deserve this? Why god why!!!!!!! Ok, maybe I am being a bit over dramatic and lets face it, I think I have only gotten to the point where God and I were sharing code frustrations only a few times in my entire life. When code is not cooperating and deadlines are looming, you and the big man upstairs can get pretty close. But anyways what about this linkedlist? How do we go about sorting it and even in reverse order? We could always yank it out of the list into an array and hammer out a sort on it there, dumping it back in. Java makes it pretty easy to do that, but it also offers us a way to sort it based a Comparator. Razaac has been looking for something like this, but with a twist. We will uncover this twist and how to solve it using a comparator on this entry of the Programming Underground!
To start off I will tell you a bit about Razaac’s project. He wanted to create a high score list that could be used for video games and such. Nothing complicated, just a list of names and their score. The twist is, he has to use a linkedlist and sort by the score, not by the name in descending order. Ahhh the plot thickens. Now granted he probably could have broken it out of a linkedlist into something like a multi-dimensional array, but that wouldn’t be using the linkedlist to the fullest. After all, DIC is about coding to the max! So how is it done? The answer is using a comparator.
A comparator is an interface used for comparing objects. This interface has one method which you must override if you wish to compare objects. Like all interfaces, you must override the functions it specifies. You can think of interfaces as a contract saying that if my object uses this interface, it is guaranteed to implement methods x…y…z. That way the programmer, and compiler, knows that the object supports certain functionality and can even group it with other objects that also support the interface. See the java documentation for more information on interfaces.
As I mentioned, this interface has a method we must override. This method is called compare() and it takes in two objects and returns an integer. Like many of you other programmers out there may have seen in your language of choice, this function compares objects and returns -1, 0, 1 depending on if they are less than, equal, or greater than one another. That is nice and dandy, but how are we going to use it with the linkedlist? Well one of the sort methods of a collection is a sort method which takes the collection to be sorted and an object which implements the comparator interface. It takes two items from the collection and gives them to the comparator to compare (which is why the compare method takes two objects) and compares them, then returns an integer describing the relationship which the sort then uses for sorting. So during the process of the sort it is going to call this comparator several times to determine how to sort them.
I guess the best way to see this is to show you an example. This example is a modified version of Razaac’s original score keeping program. So hats off to him for providing the source!
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Collections;
import java.util.Comparator;
public class highscore
{
// Define our inner class called score
// It holds the players name, score and an implementation of toString() which returns the name.
private class score {
public String name;
public int score;
public String toString() { return name; }
}
// Public method to create an instance of our private score class.
public score score() {
return new score();
}
public static void main( String args[] )
{
Scanner input = new Scanner( System.in);
LinkedList playerName = new LinkedList();
String command;
do
{
System.out.println( "Welcome to the score-keeping program, please choose your command. Press A to add a name, L to show the list, and Q to quit." );
command = input.nextLine();
if ( command.equalsIgnoreCase( "A" ) )
{
// Prompt for the name and the score
System.out.println( "WOW! Nice Score! Please enter your name!" );
String name = input.nextLine();
System.out.println( "Please enter your score!" );
String score = input.nextLine();
// Create an instance of our inner class and set its properties.
// In a language like C++ this would have been a struct
highscore highs = new highscore();
highscore.score p = highs.new score();
p.name = name;
p.score = Integer.parseInt(score);
// Adding the name here boxes it up into an "object"
playerName.add( p );
}
if ( command.equalsIgnoreCase( "L" ) )
{
// Sort using our comparator defined below. Passing it objects in our linkedlist.
Collections.sort(playerName,MakeComparator);
for ( Object nameAgain : playerName )
{
score player = (score) nameAgain;
System.out.printf( "\n%s" , player.name + " " + player.score );
}
System.out.println();
}
}
while ( !command.equalsIgnoreCase( "Q" ) );
}
// Implement our comparator using an inline function. Here we override the compare method and tell
// java how to compare our two objects (using their score).
public static Comparator MakeComparator = new Comparator() {
public int compare(Object a, Object b){
// We unbox them from objects back to score objects and get their scores
Integer aval = ((score)a).score;
Integer bval = ((score)b).score;
// Using a negative sign we flip from ascending to decending by reversing the natural sort order
return -aval.compareTo(bval);
}
};
}
Linkedlists are great for handling full objects. .NET does this as well for their listboxes and such. So what we did was create a “score” class which will keep the name and score of the player on the list. Now in other languages we probably would have made this a struct since we only use one method (toString) and the rest is public fields but in Java, it is just a really simple class. We also provide a public method for getting access to the private inner class. This is a great way to do it because we can then control how the class is accessed and maybe even do some preparation on the class before we return it to the caller. Just like how a public accessor method can control access to private data members.
The user starts the program and types “A” to add a name and a score. We create an instance of our score class and populate it with the values put in by the user. Then we just dump it in the linked list. When we do this we are doing what is called “boxing” which is the process of taking our object and storing it in a generic instance of “object”. Since all classes come from object, this is perfectly fine. Our score class is an implicit derived class of Object. So it “is a” object. As far as the linked list is concerned, it holds just generic objects.
So now we add all the names and their scores to the linkedlist and then we go to list them by typing “L”. This is where the magic happens. Our first line uses the static sort method of “collections” to take our linkedlist and sort it using our comparator to determine how to do that. You will notice I declared a comparator which defines a new comparator interface and uses an inline function to define our compare() method. Remember we have to override that if we are going to use this interface. In the method I tell it to take our two objects and cast them back to score objects. After all, we know that the list holds nothing but score objects… even if the linkedlist itself only knows them as objects. We then pull out the scores of the two players and compare them. Normally we would compare to put them in ascending order, so we slap on a negative sign to flip the sort. So if -1 is returned it will now be 1 and if 1 is returned it will now be -1.
We return the comparison value back to the sort method of the collections object which sorts the list in descending order based on the score. Lastly, we go and list the contents of the linkedlist which is now sorted. Notice how I cast it back to “score” before displaying. This is “unboxing” the object. We do this before we attempt to access the score class’ public data members. That is all there is to it!
Whoa, what a wild ride that was. But as you step through the play by play you can see the chain of events. Add items -> List Items -> Sort calls comparator function which is defined inline, giving it two items to compare -> Comparator compares the two and tells sort the relationship -> Sort sorts based on what comparator told it to do -> List the now sorted items.
Comparators can sort items based on complex criteria or business rules setup by your company. You could use several of them to sort the same list in multiple different ways and display their output in several linkedlists. Maybe one comparator sorts it normal, one in reverse, one in natural order, maybe one based completely on some other logic. It is great for things like sort headers in a windows explorer type application where you click the header to sort by date or by filename or by file size etc.
I want to thank Razaac again for providing the basis of this code and I hope this solution not only teaches everyone out there how to use Java Comparators, but also helps Razaac with his project.
NOTE: If you are using a more modern version of Java you are going to see 2 unchecked warnings which talks about the Comparator and its use of object. This is because the comparator in the modern versions use generics in their definition because it is safer with the conversion. So if you have the modern versions (1.5.0+) and want to change it using generics, be my guest. I wrote it this way to also show those running prior to the generics era how to go about using it. This way will work on all versions of Java that have the comparator interface. The modern version will just show the unchecked warnings but will compile find because we control the casting.
Enjoy! 🙂
