October 21, 2014
Hot Topics:
RSS RSS feed Download our iPhone app

Data Structures in Java: Part 8, The Comparable Interface, Part 2

  • July 26, 2001
  • By Richard G. Baldwin
  • Send Email »
  • More Articles »

Java Programming, Lecture Notes #1364

  • Preface
  • Preview
  • Discussion and Sample Programs
  • Summary
  • What's Next

  • Preface

    This is the eighth lesson in a miniseries on Java data structures and the Java Collections Framework.  The first lesson in the miniseries was entitled Data Structures in Java: Part 1, Getting Started.  The previous lesson was entitled Data Structures in Java: Part 7, The Comparable Interface, Part 1.

    The purpose of this miniseries is to help you learn the essential features of Object-Oriented data structures in Java using the Collections Framework.

    This is also the second and final lesson in a sub-series on the Comparable interface.  The purpose of the lessons in the sub-series is to teach you about the interactions between the Comparable interface and the Collections Framework, particularly with respect to the Set, SortedSet, and SortedMap interfaces of the Collections Framework.  This lesson discusses Set and SortedSet.  A discussion of SortedMap will be deferred for inclusion in a subsequent lesson.

    Viewing tip

    You may find it useful to open another copy of this lesson in a separate browser window.  That will make it easier for you to scroll back and forth among the different listings while you are reading about them.

    Supplementary material

    I recommend that you also study the other lessons in my extensive collection of online Java tutorials.  You will find those lessons published at Gamelan.com.  However, as of the date of this writing, Gamelan doesn't maintain a consolidated index of my Java tutorial lessons, and sometimes they are difficult to locate there.  You will find a consolidated index at Baldwin's Java Programming Tutorials.

    Preview

    In this lesson, I will teach you why the elements stored in a TreeSet collection need to be references to objects instantiated from a class that implements the Comparable interface.  (In a subsequent lesson, I will teach you about an alternative approach that makes use of the Comparator interface.)

    I will provide an example of implementing the Comparable interface for a new class definition, and will teach you about the natural ordering of the elements for a class.

    I will teach you the meaning of the consistent with equals requirement and show you how to satisfy that requirement for a new class definition.

    Finally, I will show you how to define a new class whose objects are eligible for inclusion in a TreeSet collection.

    Discussion and Sample Programs

    Beginning with a quiz

    Let's begin with a little quiz to test your prior knowledge of the Collections Framework.

    What output is produced by the program shown in Listing 1?

    • A.  Compiler Error
    • B.  Runtime Error
    • C.  44321
    • D.  4321
    • E.  1234
    • F.  12344
    • G.  None of the above.
    //File Comparable04.java
    
    import java.util.*;
    
    public class Comparable04{
      public static void main(
                            String args[]){
        new Worker().doIt();
      }//end main()
    }//end class Comparable04
    
    class Worker{
      public void doIt(){
        Iterator iter;
        Collection ref;
       
        ref = new TreeSet();
        Populator.fillIt(ref);
        iter = ref.iterator();
        while(iter.hasNext()){
          System.out.print(iter.next());
        }//end while loop
        System.out.println();
    
      }//end doIt()
    }// end class Worker
    
    class Populator{
      public static void fillIt(
                           Collection ref){
        ref.add(new MyClass(4));
        ref.add(new MyClass(4));
        ref.add(new MyClass(3));
        ref.add(new MyClass(2));
        ref.add(new MyClass(1));
      }//end fillIt()
    }//end class Populator
    
    class MyClass{
      int data;
      
      MyClass(){
        data = 0;
      }//end noarg constructor
      
      MyClass(int data){
        this.data = data;
      }//end parameterized constructor
      
      public String toString(){
        return "" + data;
      }//end overridden toString()
    
    }//end MyClass
    
    Listing 1

    If your answer was B.  Runtime Error, you were correct.

    What caused the runtime error?

    The runtime error was caused by the code shown in Listing 2.
     

    class Populator{
      public static void fillIt(
                           Collection ref){
        ref.add(new MyClass(4));
    
    Listing 2

    Why did this code produce a runtime error?

    This code produced a runtime error for the reasons described in the following paragraphs.

    The incoming parameter of the fillIt method is a reference to an object of type TreeSet.  The TreeSet class implements the Collection, Set, and SortedSet interfaces.  In this lesson, we will be primarily interested in the Set and SortedSet interfaces.

    The contract for the add method of the Set interface reads partially as follows:

    "Adds the specified element to this set if it is not already present ... If this set already contains the specified element, the call leaves this set unchanged and returns false. ... this ensures that sets never contain duplicate elements."
    What does this mean?

    This means that whenever the add method is invoked on a Set object, the add method must have a way of determining if the element being added is a duplicate of an element that already exists in the collection.  This means that it must be possible for the add method to compare the new element with all of the existing elements to determine if the new element is a duplicate of any of the existing elements.

    The compareTo method

    The documentation for the TreeSet class states the following:

    "... the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all key comparisons using its compareTo (or compare) method ..."
    What this means is that insofar as the handling of duplicate elements is concerned, (with the possible exception given below involving a Comparator), in order for a reference to an object to be included in a TreeSet collection, the class from which that object is instantiated must implement the Comparable interface.

    A possible exception

    Note that one of the constructors for the TreeSet class makes it possible to instantiate a new object by passing a parameter that is a reference to an object that implements the Comparator interface.

    The Comparator interface declares a method named compare, which compares its two arguments for order.  The text in the above excerpt from the Sun documentation suggests that when this parameterized constructor is used, it may not be necessary for the objects included in the TreeSet collection to implement the Comparable interface.

    I won't discuss that possibility in this lesson, but I will discuss it in a subsequent lesson that discusses the use of the Comparator interface.  For purposes of this lesson, I will concentrate on the use of a TreeSet collection that does not receive a reference to a Comparator object when it is instantiated.

    The SortedSet interface

    The TreeSet class also implements the SortedSet interface.  The documentation for the SortedSet interface states the following:

    "A set that further guarantees that its iterator will traverse the set in ascending element order, sorted according to the natural ordering of its elements (see Comparable), or by a Comparator provided at sorted set creation time."
    Natural ordering of the elements

    The key term to note in the above quotation is the term natural ordering of its elements.  This takes us back to the Comparable interface, for which the documentation states:

    "This interface 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."
    Conclusion

    The conclusion is, in order for the iterator to be able to traverse the set according to the natural ordering of its elements, the elements stored in an object that implements the SortedSet interface must be instantiated from a class that implements the Comparable interface (unless a Comparator is provided when the SortedSet object is instantiated.)

    The bottom line

    The bottom line is, because the class named MyClass in Listing 1 does not implement the Comparable interface, objects of that class are not eligible for use with a TreeSet collection (unless a Comparator is provided when the TreeSet object is instantiated).

    A Comparator was not provided when the TreeSet object was instantiated in Listing 1.

    Therefore, the attempt in Listing 2, to add a MyClass object to the TreeSet collection resulted in a ClassCastException being thrown at runtime.

    The solution

    To solve this problem, we must modify the definition of the class named MyClass to make it implement the Comparable interface (assuming that we don't provide a Comparator when the TreeSet object is instantiated).

    This is accomplished in the modified version of the program shown in Listing 3.
     

    //File Comparable05.java
    import java.util.*;
    
    public class Comparable05{
      public static void main(
                            String args[]){
        new Worker().doIt();
      }//end main()
    }//end class Comparable05
    
    class Worker{
      public void doIt(){
        Iterator iter;
        Collection ref;
       
        ref = new TreeSet();
        Populator.fillIt(ref);
        iter = ref.iterator();
        while(iter.hasNext()){
          System.out.print(iter.next());
        }//end while loop
        System.out.println();
    
      }//end doIt()
    }// end class Worker
    
    class Populator{
      public static void fillIt(
                           Collection ref){
        ref.add(new MyClass(4));
        ref.add(new MyClass(4));
        ref.add(new MyClass(3));
        ref.add(new MyClass(2));
        ref.add(new MyClass(1));
      }//end fillIt()
    }//end class Populator
    
    class MyClass implements Comparable{
      int data;
      
      MyClass(){
        data = 0;
      }//end noarg constructor
      
      MyClass(int data){
        this.data = data;
      }//end parameterized constructor
      
      public String toString(){
        return "" + data;
      }//end overridden toString()
        
      public int compareTo(Object o){
        if(!(o instanceof MyClass))
            throw new ClassCastException();
        if(((MyClass)o).data < data) 
          return 1;
        if(((MyClass)o).data > data) 
          return -1;
        else return 0;
      }//end compareTo()
        
      public boolean equals(Object o){
        if(!(o instanceof MyClass))
            return false;
        if(((MyClass)o).data == data) 
          return true;
        else return false;
      }//end overridden equals()
    }//end MyClass
    
    Listing 3

    The corrected code

    The important code to note in this modified version of the program is the new definition of the class named MyClass.  The other code in the program is essentially the same as in the previous version of the program.

    The beginning portion of the new definition for MyClass is shown in Listing 4.
     

    class MyClass implements Comparable{
      int data;
      
      MyClass(){
        data = 0;
      }//end noarg constructor
      
      MyClass(int data){
        this.data = data;
      }//end parameterized constructor
      
      public String toString(){
        return "" + data;
      }//end overridden toString()
    
    Listing 4

    The code shown in Listing 4 is identical to the code in the previous version with one major exception.  This version of the class definition implements the Comparable interface.  That means that this class must provide a concrete definition for the following method, which is the only method declared in the Comparable interface:

    public int compareTo(Object o)

    The compareTo method

    The description of the compareTo method in the Sun documentation begins as follows:

    "Compares this object with the specified object 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."

    Beyond this, there are a number of additional stipulations that I won't repeat here.  You can view them in the Sun documentation if you are interested in that level of detail.

    Listing 5 shows my implementation of the compareTo method.  Although this implementation satisfies the general description given above, I haven't taken the time to test it fully to confirm that it meets all of the additional stipulations provided by Sun.
     

      public int compareTo(Object o){
        if(!(o instanceof MyClass))
            throw new ClassCastException();
        if(((MyClass)o).data < data) 
          return 1;
        if(((MyClass)o).data > data) 
          return -1;
        else return 0;
      }//end compareTo()
    
    Listing 5

    Consistent with equals

    The Sun documentation strongly emphasizes the need to make certain that a class' natural ordering is consistent with equals, and provides the rules for meeting that requirement.

    Further, the documentation for the TreeSet class reads partially as follows:

    "Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. ..."
    Meeting the consistent with equals requirement

    In order to satisfy the rules and to cause the natural ordering of the MyClass class to be consistent with equals, it was necessary to override the equals method inherited from the Object class.  My overridden version of the equals method is shown in Listing 6.
     

        
      public boolean equals(Object o){
        if(!(o instanceof MyClass))
            return false;
        if(((MyClass)o).data == data) 
          return true;
        else return false;
      }//end overridden equals()
    }//end MyClass
    
    Listing 6

    As was the case in defining the compareTo method, there are also a large number of stipulations involved in properly overriding the equals method.  I will simply refer you to the Sun documentation if you are interested in reading about those stipulations.

    The program output

    Given all of the above, this program compiles and executes correctly, producing the following output.

    1234

    Note that duplicate elements were eliminated, and the iterator traversed the set in ascending element order, sorted according to the natural ordering of the elements, as required for a SortedSet collection.

    Summary

    I explained why the elements stored in a TreeSet collection need to be references to objects instantiated from a class that implements the Comparable interface.  (In a subsequent lesson, I will teach you about an alternative approach that makes use of the Comparator interface.)

    I provided an example of implementing the Comparable interface for a new class definition, and I taught you about the natural ordering of the elements for a class.

    I taught you the meaning of the consistent with equals requirement and showed you how to satisfy that requirement for a new class definition.

    I showed you how to define a new class whose objects are eligible for inclusion in a TreeSet collection.

    What's Next?

    In the next lesson, I will discuss the use of the Comparator interface in order to achieve a sorting order that is different from the natural ordering of the elements in a sorted collection.

    About the author

    Richard Baldwin is a college professor and private consultant whose primary focus is a combination of Java and XML. In addition to the many platform-independent benefits of Java applications, he believes that a combination of Java and XML will become the primary driving force in the delivery of structured information on the Web.

    Richard has participated in numerous consulting projects involving Java, XML, or a combination of the two.  He frequently provides onsite Java and/or XML training at the high-tech companies located in and around Austin, Texas.  He is the author of Baldwin's Java Programming Tutorials, which has gained a worldwide following among experienced and aspiring Java programmers. He has also published articles on Java Programming in Java Pro magazine.

    Richard holds an MSEE degree from Southern Methodist University and has many years of experience in the application of computer technology to real-world problems.

    baldwin.richard@iname.com






    Comment and Contribute

     


    (Maximum characters: 1200). You have characters left.

     

     


Sitemap | Contact Us

Rocket Fuel