Add the Comparable flavor, and taste the feeling.
Looking for something? Here?s the latest albums.
What?s The Problem?
If you have collection items; a list of rows in a table, files in your directory, or songs in a music library, and you want to compare between them, without revealing the implementation.
The intent for comparison might be to sort, search for an item, see which item has higher priority than the other, and so forth.
And if you are going to compare, you want to compare without knowing any information about their data types, whether they are rows, files, songs, or any kind of objects.
In Java, the secret lies in ?Comparable? & ?Comparator? Interfaces.
Comparable Interfaces
The Comparable Interface has a method called compareTo. It compares between two objects of the implementing class.
Now, to show an example on how to use Comparable Interface, we will use Files as an example. But, you can apply the same steps on whatever collection of items you have.
How To Make A File Comparable?
First, we need to see how a File class may look like.
public class File { public int name; public Date date; public String type; public int size; // …}
1. Implement Comparable Interface
The File class should implement Comparable Interface. Now, we can say that the File class provides a way of comparing it?s objects.
public class File implements Comparable<File> { // …}
Notice that Comparable and Comparator are both generic interfaces.
2. Override compareTo Method
The compareTo method defines the natural order; the default way for ordering objects of a class.
It should return a negative integer(usually -1), if the current triggering object is less than the passed one, and positive integer (usually +1) if greater than, and 0 if equal.
public int compareTo(File b){ if(this.name > b.name) return 1; if(this.name < b.name) return -1; else return 0;}
compareTo method should throws an exception if the passed object has incompatible type or null.
Sorting Comparable Objects
Till now, we have objects, plugged-in with comparison capability, without revealing the implementation. The next step is do something useful with these Comparable objects. So, let?s sort them.
In your sorting method, it should take an argument of Comparable array type, and it will trigger compareTo method on each object in the array.
This is how sorting methods compare between objects, without the need to know any information about their data types.
public static void sort(Comparable a){ int n = a.length; for (int i = 0; i < n; i++) { for (int j = i; j > 0; j–) { if(a[j].compareTo(a[j-1]) < 0) swap(a, j, j-1); else break; } }}
To use the sort method, you just need to pass an array of Comparable objects, and let the magic happen.
File files = File.listFiles(directory);sort(files);
Comparator Interfaces
So far so good? Now, what if you want to extend the comparison capability, and you want to compare between files based on other properties, like their date of creation, type, size, or based on any other comparison logic it might sound reasonable for you.
Now, you need different ways to compare between File objects. This can be done by implementing the Comparator Interface.
1. Implement Comparator Interface
Define an inner static class that implements the Comparator Interface.
Each inner class represents a property, or a logic you want to compare accordingly. So, we may compare by name, by size, and so on.
public class File { // … private static class ByName implements Comparator<File> { } private static class BySize implements Comparator<File> { }}
It?s perfectly valid to implement these inner classes outside the File Class.
2. Override compare Method
It works the same way as compareTo in Comparable Interface.
Now, you can explicitly define how to compare between two File objects based on their names, or size. All what you need to do is to return an integer, positive if first argument is greater, negative if less than, and 0 if equal.
public class File { // … private static class ByName implements Comparator<File> { public int compare(File v, File w){ // v.name is a String, and a String object is Comparable return v.name.compareTo(w.name); } } private static class BySize implements Comparator<File> { public int compare(File v, File w){ return v.size – w.size; } }}
compare method should throws an exception if the passed object has incompatible type or null(same as compareTo method).
3. Use Comparator Objects
The last step is to define static variables within your class, each references a Comparator object, which will be used to trigger compare method.
public class File { public static final Comparator<File> BY_NAME = new ByName(); public static final Comparator<File> BY_SIZE = new BySize(); // …}
Sorting Using A Comparator Object
For the sorting method to work with Comparator object, you?ll need to make some tweaks.
First, it should take an argument of ?Object? array type instead of Comparable. Second, pass a Comparator object, which you will use to compare.
public static void sort(Object a, Comparator c){ int n = a.length; for (int i = 0; i < n; i++) { for (int j = i; j > 0; j–) { if(c.compare(a[j], a[j-1]) < 0) swap(a, j, j-1); else break; } }}
To use the sort method, you just need to pass an array of Comparable objects, and let the magic happen again!.
File files = File.listFiles(directory);sort(files, File.BY_NAME);sort(files, File.BY_SIZE);
Sorting With Respect To Another Object
You can compare two object with respect to another object.
As an example, you can compare points on a plane by calculating the slope they make with another given point. And to do this, we need to define a Comparator object for each point object.
So, define a non-static instance variable in the class, which references a Comparator object, along with the non-static inner class that implements the Comparator Interface.
This instance variable can be used to compare between two points with respect to the current point object.
public class Point { public final Comparator<Point> SLOPE_ORDER = new SlopeOrder(); private final x, y; private class SlopeOrder implements Comparator<Point> { public int compare(Point p1, Point p2) { // Point.this references the current point object Point current = Point.this; double d = current.slopeTo(p1) – current.slopeTo(p2); if(d > 0) return 1; else if(d < 0) return -1; else return 0; } }}
To sort the points by the slope they make with a given point object P, you just need to pass the instance variable we?ve defined of P, and let the magic happen again, and again!.
Point pointP = new Point(x, y);sort(points, pointP.SLOPE_ORDER);
Helper Methods
There are some helper methods you might use if you are comparing between objects frequently. These methods are less and swap.
? less
The less method compare between two given objects, and return true if the first argument is less than, and false otherwise.
// for Comparable objectsprivate static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0;}// support Comparator objectprivate static boolean less(Object v, Object w, Comparator c) { return c.compare(v, w) < 0;}
? swap
The swap method exchange between two objects in the given array.
private static void swap(Object a, int i, int j) { Object swap = a[i]; a[i] = a[j]; a[j] = swap;}
Comparator & Comparable Interfaces Support
In your class, You can use both; A class can implement the Comparable Interface, and so we can call compareTo method and compare according to their natural(default) order. Also, you can use Comparator Interface to define custom ordering(s).
On the other hand, your sort method should be compatible. Whether the objects are Comparable, or you want to sort based on a given Comparator object.
Hence, you can have two sorting methods, one supports Comparable objects with one argument, and another overloaded method with two arguments that supports Comparator object.
// supports Comparable objectssort(Comparable a){ ? }// supports Comparator objectsort(Object a, Comparator c){ ? }
Java?s Arrays.sort() Method
- It has a different method for each primitive type.
- It has a method for data types that implements Comparable.
String a = { … };// Sort by the natural order given Comparable objectsArrays.sort(a);
- It has a method that uses Comparator.
String a = { … };// Sort ignoring case sensitivity using the given Comparator objectArrays.sort(a, String.CASE_INSENSITIVE_ORDER);
