Java Tutorial: Comparable Interface

Chapters

• Comparable Interface
• compareTo() Method
• Implementing Our Own Comparable Interface

Comparable Interface

Comparable imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method. This interface allows objects of a class to be sorted automatically.

Lists (and arrays) of objects that implement this interface can be sorted automatically by Collections.sort (and Arrays.sort). Objects that implement this interface can be used as keys in a sorted map or as elements in a sorted set, without the need to specify a Comparator. Comparator is similar to Comparable. Although, Comparator has several methods that provide additional functionalities for sorting.

Natural ordering is an order that java follows by default. For example, Strings are sorted in alphabetical order. Numbers are sorted from lowest to highest, just like the natural arrangement of natural numbers. Natural comparison is a comparison of both objects ordered by natural ordering. Here's a table that lists natural ordering of some classes that implement Comparable. I got this table from this article.

Class                     Natural Ordering

Byte, Long, Integer,      
Short, Double, Float,     Signed Numerical
BigInteger, BigDecimal

Character                 Unsigned Numerical

Boolean                   Boolean.FALSE < Boolean.TRUE

File                      System-dependent lexicographic 
                          on path name

String                    Lexicographic

Date                      Chronological

CollationKey              Locale-specific lexicographic

Note: lexicographic order is also known as dictionary order.
      Dictionary order arranges words in alphabetical order.
      However, in lexicographic order, uppercase letters
      preceed lowercase letters.

Virtually all Java core classes that implement Comparable have natural orderings that are consistent with equals. One exception is BigDecimal, whose natural ordering equates BigDecimal objects with equal numerical values and different representations (such as 4.0 and 4.00). For BigDecimal.equals() to return true, the representation and numerical value of the two BigDecimal objects must be the same.

This example demonstrates sorting objects that implement the Comparable interface.

import java.util.Arrays;

public class SampleClass{

  public static void main(String[] args){
  
    String[] strings = {"Dog","Wolf","Alligator",
                        "Horse", "Zebra","Lion"};
    
    System.out.println("Unsorted");
    for(String str : strings)
       System.out.print(str + " ");
    
    Arrays.sort(strings);
    
    System.out.println();
    System.out.println("Sorted");
    for(String str : strings)
       System.out.print(str + " ");
  }
}

Result
Unsorted
Dog Wolf Alligator Horse Zebra Lion
Sorted
Alligator Wolf 

Next, let's try sorting numbers using natural ordering.

import java.util.Arrays;

public class SampleClass{

  public static void main(String[] args){
  
    Integer[] ints = {77,-22,99,-66,88,44};
    
    System.out.println("Unsorted");
    for(Integer i : ints)
       System.out.print(i + " ");
    
    Arrays.sort(ints);
    
    System.out.println();
    System.out.println("Sorted");
    for(Integer i : ints)
       System.out.print(i + " ");
  }
}

Result
Unsorted
77 -22 99 -66 88 44
Sorted
-66 -22 44 77 88 99

Next, let's try sorting files. The natural ordering of File object, as describe on the table above, is system-dependent. So, result in this example may vary.

import java.util.Arrays;
import java.io.File;
import java.io.IOException;

public class SampleClass{

  public static void main(String[] args)
                          throws IOException{
  
    File[] files = {new File("C:\\test\\poem.txt"),
                    new File("C:\\test\\bounty.txt"),
                    new File("C:\\test\\todo.txt"),
                    new File("C:\\test\\script.txt")
                    };
    
    System.out.println("Unsorted");
    for(File file : files)
       System.out.print(file.getName() + " ");
    
    Arrays.sort(files);
    
    System.out.println();
    System.out.println("Sorted");
    for(File file : files)
       System.out.print(file.getName() + " ");
  }
}
Unsorted
poem.txt bounty.txt todo.txt script.txt
Sorted
bounty.txt poem.txt script.txt todo.txt

compareTo() Method

This method compares objects for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object. "this" object refers to the object that calling this method. the specified object is the object in the method parameter: compareTo(T o)
"T" in the parameter is generic type.

This method is responsible for sorting objects. Everytime we call Collections.sort() or Arrays.sort(), this method will be invoked implicitly. Some objects have different impelementation of this method. For example, let's discuss the String implementation of compareTo().

This is the source code of compareTo() in String class. This source code is extracted from this article.

public int compareTo(String anotherString) {

  int len1 = value.length;

  int len2 = anotherString.value.length;

  int lim = Math.min(len1, len2);

  char v1[] = value;

  char v2[] = anotherString.value;


  int k = 0;

  while (k < lim) {

    char c1 = v1[k];

    char c2 = v2[k];

    if (c1 != c2) {

      return c1 - c2;

    }

    k++;

  }

  return len1 - len2;

}

First off, the code above gets the length of two String objects; finds the string with the shortest length and assigns it as a "limit"; assigns the String objects to char array. Then, each numerical representation of characters of both Strings is compared. If "this" string character is not equal to "another" string character, subtract both characters' numberical representations.

If "this" string character is greater than "another" string character, return a positive integer. Otherwise, return a negative integer. If "this" string character is equal to "another" string character, continue the loop until there are unequal characters or the loop reaches the "limit".

If both strings have equal characters and length. This method returns 0. If both string have equal characters but have unequal length; returns a negative integer if "this" string length is less than "another" string length; returns a positive integer if "this" string length is greater than "another" string length.

Java decides which string comes first before another string based on the return value of compareTo(). For example, we have two Strings in a String array:
String[] arr = {"apples", "apple"};
Then, we call Arrays.sort(arr);
Then, compareTo() will be implicitly invoked.

So, "apples".compareTo("apple") returns a positive integer because "apples" has more characters than "apple" even though the first five letters of both strings are equal. Now, "apple" is considered to be less than "apples"; "apple" will be placed at the lower index(0); "apples" will be placed at the higher index(1).

Remember that the natural ordering for numbers is sorted from lowest to highest. That's why "apple" is placed at the lower index and "apples" is placed at the higher index because we're comparing their length which is numerical value. The sorted result is: {"apple","apples"}

Let's try sorting this array in natural ordering:
String[] arr = {"Apple", "apple"};
Call Arrays.sort(arr), Invoke "Apple".compareTo("apple") and it returns a negative integer. Assuming that the charset we're using here is ASCII or charset derived from ASCII, the numerical representation of "A" which is 65 is less than the numerical representation of "a" which is 97.

Now, "apple" is considered as greater than "Apple". Thus, "apple" stays at the higher index(1) and "Apple" stays at the lower index(0). Thus, the sorted result is: {"Apple","apple"}

Let's try sorting this array in natural ordering:
String[] arr = {"apple", "apple"};
When "apple".compareTo("apple") is invoked, it returns 0 because "apple" String that calls compareTo() and "apple" String argument are equal. They are not less than nor greater than to each other. Thus, they stay at their respective indexes.

If we want to get the return value of compareTo() for some reason,we can explicity invoke the method. This example demonstrates invoking compareTo() explicitly.

public class SampleClass{

  public static void main(String[] args){
  
    String str1 = "Apple";
    String str2 = "apple";
    String str3 = "apples";
    String str4 = str2;
    
    System.out.println("Output1: " + str2.compareTo(str3));
    System.out.println("Output2: " + str1.compareTo(str2));
    System.out.println("Output3: " + str2.compareTo(str4));
  }
}

Result
Output1: -1
Output2: -32
Output3: 0

Default charset is used in the example above. The default charset of my system as the time of this writing is similarly equivalent to ASCII. In the first output, the result is -1 because compareTo() returns the difference of length between str2 and str3. In the second output, the result is -32 because compareTo() returns the difference of the "A" and "a".

"A" = 65 and "a" = 97. So, 65 - 97 = -32. In the third output, the result is 0 because str2 and str4 are equal in terms of length and characters.

Implementing Our Own Comparable Interface

We can override Comparable and implement our own sorting algorithm with natural ordering. When we override Comparable, compareTo() should be consistent with equals(). In other words:
if e1.compareTo(e2) == 0 then e1.equals(e2) == true
if e1.compareTo(e2) != 0 then e1.equals(e2) == false

In the documentation, there's a statement regarding natural orderings that we should keep in mind when overriding Comparable:

It is strongly recommended (though not required) that natural orderings be consistent with equals. This is so because sorted sets (and sorted maps) without explicit comparators behave "strangely" when they are used with elements (or keys) whose natural ordering is inconsistent with equals. In particular, such a sorted set (or sorted map) violates the general contract for set (or map), which is defined in terms of the equals method.

This example demonstrates on how to override Comparable Interface.

import java.io.File;
import java.io.IOException;
import java.util.Arrays;

public class SampleClass{

  public static void main(String[] args)
                          throws IOException{
  
    File f1 = new File("C:\\test\\test1.txt");
    File f2 = new File("C:\\testing\\testing1.txt");
    File f3 = new File("C:\\test\\test2.txt");
    File f4 = new File("C:\\testing\\testing2.txt");
    
    FileContainer fc1 = new FileContainer(f1);
    FileContainer fc2 = new FileContainer(f2);
    FileContainer fc3 = new FileContainer(f3);
    FileContainer fc4 = new FileContainer(f4);
    
    FileContainer[] files = {fc1,fc2,fc3,fc4};
    
    System.out.println("Unsorted");
    for(FileContainer fc : files)
      System.out.println(fc.getTruePath());
    
    Arrays.sort(files);
    System.out.println();
    System.out.println("Sorted");
    for(FileContainer fc : files)
      System.out.println(fc.getTruePath());
  }
}

class FileContainer implements Comparable<FileContainer>{

  private File file;
  
  FileContainer(File file){
    //Throw NullPointerException
    //immediately if file is null
    //we don't want the global
    //variable file to have null value
    //to minimize unexpected exceptions
    //due to null values
    if(file == null)
      throw new NullPointerException();
    
    this.file = file;
  }
  
  //Override compareTo()
  @Override
  public int compareTo(FileContainer anotherFile){
    int result = 0;
    
    String thisName = file.getName();
    String thisParent = file.getParentFile().getName();
    String anotherName = anotherFile.getFile().getName();
    String anotherParent = anotherFile.getFile().
                           getParentFile().getName();
    
    int parentCmp = thisParent.compareTo(anotherParent);
    int nameCmp = thisName.compareTo(anotherName);
    result = (parentCmp != 0) ? parentCmp : nameCmp;
    
    return result;
  }
  
  //Override equals()
  @Override
  public boolean equals(Object obj){
  
    if(obj instanceof FileContainer){
      FileContainer anotherFile = (FileContainer) obj;
      
      String thisName = file.getName();
      String thisParent = file.getParentFile().getName();
      String anotherName = anotherFile.getFile().getName();
      String anotherParent = anotherFile.getFile().getParentFile().
                             getName();
                             
      return thisName.equals(anotherName) &&
             thisParent.equals(anotherParent);
    }
    else return false;
  }
  
  @Override
  public String toString(){
    return file.getParentFile().getName() +
           File.separator + file.getName();
  }
  
  public String getTruePath()
                throws IOException{
    return file.getCanonicalPath();
  }
  
  public File getFile(){
    return file;
  }
}

Result
Unsorted
C:\\test\\test1.txt
C:\\testing\\testing1.txt
C:\\test\\test2.txt
C:\\testing\\testing2.txt

Sorted
C:\\test\\test1.txt
C:\\test\\test2.txt
C:\\testing\\testing1.txt
C:\\testing\\testing2.txt

In the example above, we sorted files based on their names and parent names. We can also see above that I overrode compareTo() and equals(). compareTo() and equals() are also consistent with each other because compareTo() will return 0 if and only if the name and parent name of "this" FileContainer are equal to "another" FileContainer's name and parent name in terms of length and characters.

In equals(), equals() will return true if and only if the name and parent name of "this" FileContainer are equal to "another" FileContainer's name and parent name in terms of length and characters.

I also overrode toString(). Everytime a FileContainer calls toString(), it returns the parent name plus the name of the file in FileContainer.