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

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

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.

    [email protected]

Latest Posts

Related Stories