1. Comparable Interface

Objects of a class that implements the Comparable interface can be arranged into a particular order. For example, objects of class String, which implements Comparable, can be arranged into alphabetical order. Numeric classes such as Integer or Double implement Comparable and their objects can be arranged into numeric order.

Objects of a class that implements Comparable can be compared to each other to determine which comes first when the objects are arranged in order.

Chapter Topics:

• The Comparable Interface
  
• compareTo() method
  
• natural order
  
• collating sequence
  
• sorting
  
• binary search
  

Question 1:
Arrange these strings in order: "orange", "apple", "plum".

Source: Bradley Kjell, https://chortle.ccsu.edu/Java5/Notes/chap53B/ch53B_1.html
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 License.

2. Comparable <T> Interface

Answer:
"apple", "orange", "plum".
This is the order that compareTo() would place the strings.

Comparable<T> Interface

An interface consists of constants and method declarations. The Comparable<T> interface consists of just one method (and no constants):

int compareTo( T obj )                        
Compare the object running
                obj, which 
 is of type T. Return a 
 negative integer, zero, or a 
 positive integer, when he 
 object running the method is 
 less than, equal, or greater 
 than obj.

T stands for the type of the objects. If the objects are Strings, then T is String. Strings implement the Comparable<String> interface.

If an object is of a class that implements Comparable, then that object is less than, equal, or greater than any object of that class. compareTo() returns an integer to show which of these three relations hold.

Question 2:
Does compartTo() tell us enough?
If any two objects can be compared, and the result is less than, equal, or greater 
than is this enough to put a collection of objects in order?

3. This is enough to put a collection in order.

Answer:
"apple", "orange", "plum".
This is the order that compareTo() would place the strings.

Comparable<String> Interface

StringA is regarded as less than StringB if StringA would be proceed StringB in a dictionary. For example,

Only the sign of the returned integer matters if the return value is not zero. The magnitude of a returned integer does not signify anything.

Memory Aide: think of this as subtraction.

Question 3:
Examine the following:
String myPet = "Fido" ;
String stray = "Rex" ;

if ( myPet.compareTo( stray ) < 0 )
  System.out.println( "Good Dog" );
else
  System.out.println( "Bad Dog" );
What is printed?

4. Integer

Answer:
Good Dog

Integer

Integer minusTen = new Integer( -10 );
Integer minusFive = new Integer( -5 );
Integer five = new Integer( 5 );
Integer ten = new Integer( 10 );
Integer fifteen = new Integer( 15 );

Question 4:
Examine the following:
Integer five = 5 ;
Integer ten = 10 ;
What is the value of:
five.compareTo( ten )

5. Natural Order

Answer:
five.compareTo( ten ) is negative.
The declaration of the two Integer variables looks wrong, but they are actually correct. 
Autoboxing automatically constructs Integer objects for the two primitive integers.

Natural Order

objectA.compareTo(objectB)

Question 5:
What is "grape".compareTo( "banana" );

6. Rules for compareTo()

Answer:
positive

Rules for compareTo()

If A.compareTo(B) > 0 and B.compareTo(C) > 0 then A.compareTo(C) > 0.

If A.compareTo(B) == 0 then A.compareTo(Z) and B.compareTo(Z) gives the same result, no matter what Z is.

Question 6:
Say that X.compareTo(Y)==0.
Is it then true that X.equals(Y)?

7. Consistency with equals()

Answer:
For most classes that implement both methods this is true. But it is possible that it is 
not true, so check the documentation.
The compareTo() method might look only at some instance variables of an 
object and ignore others. The equals() method might look at different instance variables.

Consistency with equals()

class TestCompareTo
{
  public static void main ( String[] args )
  {
    String appleA = new String("apple"); // these are two distinct objects 
    String appleB = new String("apple"); // these are two distinct objects
    String berry  = new String("berry");
    String cherry = new String("cherry");
    String A, B;
    
    A = appleA; B = appleB;
    System.out.print(  A + ".compareTo(" + B + ") returns ");
    if ( A.compareTo(B) == 0) System.out.println("Zero");
    if ( A.compareTo(B) < 0 ) System.out.println("Negative");
    if ( A.compareTo(B) > 0 ) System.out.println("Positive");
    System.out.println(  A + ".equals(" + B + ") is " + A.equals(B) );
    System.out.println();
    
    A = appleA; B = berry;
    System.out.print(  A + ".compareTo(" + B + ") returns ");
    if ( A.compareTo(B) == 0) System.out.println("Zero");
    if ( A.compareTo(B) < 0 ) System.out.println("Negative");
    if ( A.compareTo(B) > 0 ) System.out.println("Positive");
    System.out.println(  A + ".equals(" + B + ") is " + A.equals(B) );
    System.out.println();
    
    A = berry; B = appleA;
    System.out.print(  A + ".compareTo(" + B + ") returns ");
    if ( A.compareTo(B) == 0) System.out.println("Zero");
    if ( A.compareTo(B) < 0 ) System.out.println("Negative");
    if ( A.compareTo(B) > 0 ) System.out.println("Positive");
    System.out.println(  A + ".equals(" + B + ") is " + A.equals(B) );
 }
}

apple.compareTo(apple) returns Zero
apple.equals(apple) is true

apple.compareTo(berry) returns Negative
apple.equals(berry) is false

berry.compareTo(apple) returns Positive
berry.equals(apple) is false

Question 7:
(Thought Question: ) Do you think that "APPLE".compareTo("apple") returns zero?

8. Comparing Strings

Answer:
No. Upper and lower case matter.

Comparing Strings

Question 8:
Decide which strings, when used with compareTo() return zero.
Comparison
Zero or Not Zero
"bugbear"
.compareTo
("bugbear")
"bugbear"
.compareTo
("Bugbear")
"Zorba"
.compareTo
("Zorba!")
"mushroom"
.compareTo
("mush room")
"TOAD"
.compareTo
("TOAD")

9. Nearly Same Strings, but Different Lengths

Answer:
"bugbear"
.compareTo
("bugbear")
zero
"bugbear"
.compareTo
("Bugbear")
NOT zero
"Zorba"
.compareTo
("Zorba!")
NOT zero
"mushroom"
.compareTo
("mush room")
NOT zero
"TOAD"
.compareTo
("TOAD")
zero

Nearly Same Strings, but Different Lengths

"bat".compareTo("batcave") < 0
"apple".compareTo("applesauce") < 0
"BAT".compareTo("BATCAVE") < 0
"batcave".compareTo("bat") > 0
"applesauce".compareTo("apples") > 0
"BATCAVE".compareTo("BAT") > 0

Question 9:
Decide on the value returned by compareTo():
Comparison
Zero, Negative, or Positive
"bugbear"
.compareTo
("bugbear")
"bug"
.compareTo
("bugbear")
"pepper"
.compareTo
("peppermint")
"toadstool"
.compareTo
("toad")
"cat"
.compareTo
("caterpillar")

10. First Differing Pair of Characters

Answer:
"bugbear"
.compareTo
("bugbear")
zero
"bug"
.compareTo
("bugbear")
negative
"pepper"
.compareTo
("peppermint")
negative
"toadstool"
.compareTo
("toad")
positive
"cat"
.compareTo
("caterpillar")
negative

First Differing Pair of Characters

first differing characters are 'a' and 'e'
beat       
  |              
beet 

first differing characters are 'r' and 'h'   
bear rug
     |          
bear hug

first differing characters are 'c' and 'm'
batcave
   ||||          
batmobile

first differing characters are 'b' and 'B'
baseball bat
    |    |       
baseBall hat

Question 10:
Decide on the following:
Comparison
Zero, Positive, or Negative
"bugbear"
.compareTo
("Bugbear")
"rugrat"
.compareTo
("rugRat")
"ant"
.compareTo
("turtle")
"toadstool"
.compareTo
("total")
"ABCDEFG"
.compareTo
("ABcD")
"roadrunner"
.compareTo
("roadkill")

11. All the Rules

Answer:
"bugbear"
.compareTo
("Bugbear")
positive
"rugrat"
.compareTo
("rugRat")
positive
"ant"
.compareTo
("turtle")
negative
"toadstool"
.compareTo
("total")
negative
"ABCDEFG"
.compareTo
("ABcD")
negative
"roadrunner"
.compareTo
("roadkill")
positive

All the Rules

Question 11:
Of course, you would like to practice this:
Comparison
Which Rule?
Zero, Negative, or Positive
"turtle"
.compareTo
("turtledove")
"polarbear"
.compareTo
("polarbear")
"freezing point"
.compareTo
("freezing")
"Power"
.compareTo
("power")
"FORTRAN"
.compareTo
("fortran")

12. Collating Sequence

Answer:
"turtle"
.compareTo
("turtledove")
negative
"polarbear"
.compareTo
("polarbear")
zero
"freezing point"
.compareTo
("freezing")
positive
"Power"
.compareTo
("power")
negative
"FORTRAN"
.compareTo
("fortran")
negative

Collating Sequence

sp ! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ?
@  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _
`  a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~

A < K
0 < Z
Z < a
% < + 
@ < {
z < ~

" hello".compareTo("hello")

Question 12:
More practice. Compare digit-containing strings like "23.5" using character-by-
character string comparison, not arithmetic comparison.
Comparison
Zero, Negative, or Positive
" 9999"
.compareTo
("023")
"(rat)"
.compareTo
("[cat]")
"23.5"
.compareTo
("23,7")
"More Cheese?"
.compareTo
("More Cheese!")
"cobol"
.compareTo
("cobalt")

13. Ordered Array

Answer:
Comparison
Zero, Negative, or Positive
" 9999"
.compareTo
("023")
negative
"(rat)"
.compareTo
("[cat]")
negative
"23.5"
.compareTo
("23,7")
positive
"More Cheese?"
.compareTo
("More Cheese!")
positive
"cobol"
.compareTo
("cobalt")
positive

Ordered Array

// Sort the array into ascending order
static void sort( array )

Question 13:
Would a dictionary be useful if its definitions were not in sorted order?

14. Integer Sorting Program

Answer:
No

Integer Sorting Program

import java.util.Arrays;

class ArrayDemoOne
{
  public static void main ( String[] args )
  {
    int[] scramble = {148, -23, 67, 110, -17, 44, 103, -12, -8, 91, -12, 43, 0, 9, 80, 34, 21, 44, 15, 11};
    
    System.out.print("Scrambled array:  ");
    for ( int j=0; j < scramble.length; j++ )
      System.out.print( scramble[j] + " ");
      
    System.out.println();
    
    Arrays.sort( scramble );
    
    System.out.print("Sorted    array:  ");
    for ( int j=0; j < scramble.length; j++ )
      System.out.print( scramble[j] + " ");
      
    System.out.println();
       
  }
}

Scrambled array:  148 -23 67 110 -17 44 103 -12 -8 91 -12 43 0 9 80 34 21 44 15 11
Sorted    array:  -23 -17 -12 -12 -8 0 9 11 15 21 34 43 44 44 67 80 91 103 110 148

Question 14:
Could compareTo() be used to decide on the order for an array of String references?

15. Integer Sorting Program

Answer:
Yes.

Integer Sorting Program

static void sort( Object[] a )   
// Sorts the array a into ascending order,
// as determined by the values compareTo() returns.
// Each cell of the array must refer to an object
// (must not be null).

static void sort( Object[] a, 
                  int fromIndex, int toIndex )   

// Sorts the array a into ascending order,
// as determined by the values compareTo() returns.
//
// Only the cells between the two indexes are sorted.
// Each of those cells  must refer to an object.

Question 15:
Does String implement Comparable?

16. String Sorting Program

Answer:
Yes. So an array of String references can be sorted.

String Sorting Program

Scrambled array:  bat fox gnu eel ant dog fox gnat
Sorted    array:  ant bat dog eel fox fox gnat gnu

import java.util.Arrays;

class ArrayDemoTwo
{
  public static void main ( String[] args )
  {
    String[] animals = {"bat", "fox", "gnu", "eel", "ant", "dog", "fox", "gnat" };
    
    System.out.print("Scrambled array:  ");
    for ( String anm : animals )
      System.out.print( anm + " ");
      
    System.out.println();
    
    Arrays.sort( animals );
    
    System.out.print("Sorted    array:  ");
    for ( String anm : animals )
      System.out.print( anm + " ");
      
    System.out.println();
       
  }
}

Question 16:
To use sort() with a class that you define, what interface must that class implement?

17. Dictionary Entry

Answer:
The class must implement Comparable.

class Entry implements Comparable<Entry>
{
  private String word;
  private String definition;
  
  public Entry ( String word, String definition )
  {
    this.word = word;
    this.definition = definition;
  }
  
  public String getWord()
  {
    return word;
  }

  public String getDefinition()
  {
    return definition;
  }
  
  public String toString()
  {
    return getWord() + "\t" + getDefinition();
  }
  
  public int compareTo( Entry other )
  {
   return  ;
  }
  
}

Question 17:
When the entries of a dictionary are put in order, does the order depend on the definition?
Should the compareTo() method depend on the definition?
Fill in the blank to complete the compareTo() method.
Hint: use the compareTo() method of the String.

18. Entry Testing Program

Answer:
When the entries of a dictionary are put in order, does the order depend on the definition? No.
Should the compareTo() method depend on the definition? No.
Fill in the blank to complete the compareTo() method.
  public int compareTo( Entry other )
  {
   return getWord().compareTo( other.getWord() );
  }
Another solution is:
  public int compareTo( Entry other )
  {
   return word.compareTo( other.word );
  }

import java.util.Arrays;

class Entry implements Comparable<Entry>
{
  .  .  .
}

class EntryTester
{
  
  public static void main ( String[] args )
  {
    Entry[] wordList = new Entry[10];
    
    wordList[0] = new Entry( "WWW", "World Wide Web" );
    wordList[1] = new Entry( "HTTP","Hypertext Transport Protocol" );
    wordList[2] = new Entry( "DNS", "Domain Name System" );
    wordList[3] = new Entry( "AWT", "Application Windowing Toolkit" );
    wordList[4] = new Entry( "CPU", "Central Processing Unit" );
    wordList[5] = new Entry( "RAM", "Random Access Memory" );
    wordList[6] = new Entry( "URL", "Uniform Resource Locator" );
    wordList[7] = new Entry( "GUI", "Graphical User Interface" );
    wordList[8] = new Entry( "API", "Application Programming Interface" );
    wordList[9] = new Entry( "ROM", "Read-only Memory" );
    
    Arrays.sort( wordList );
    
    for ( int j=0; j<wordList.length; j++ )
      System.out.println( wordList[j].toString() );
  }  

}

API     Application Programming Interface
AWT     Application Windowing Toolkit
DNS     Domain Name System
CPU     Central Processing Unit
GUI     Graphical User Interface
ROM     Read-only Memory
HTTP    Hypertext Transport Protocol
RAM     Random Access Memory
URL     Uniform Resource Locator
WWW     World Wide Web

Question 18:
Must an array be in sorted order for it to be searched?

19. Binary Search

Answer:
No. Linear search can be used to look through the entries one-by-one starting with the first entry.

static int binarySearch( Object[] array, Object key )

Question 19:
With a dictionary of just 10 entries, does it make much difference how fast searching is?

20. Tiny Dictionary

Answer:
No... but you should know that binary search exists in case you need it in a large 
application. With large amounts of data, binary search is very much faster than linear search.

import java.util.Arrays;
import java.util.Scanner;

class TinyDictionary
{
  
  public static void main ( String[] args )
  {
    Entry[] wordList = new Entry[10];
    
    wordList[0] = new Entry( "WWW", "World Wide Web" );
    wordList[1] = new Entry( "HTTP","Hypertext Transport Protocol" );
    wordList[2] = new Entry( "DNS", "Domain Name System" );
    wordList[3] = new Entry( "AWT", "Application Windowing Toolkit" );
    wordList[4] = new Entry( "CPU", "Central Processing Unit" );
    wordList[5] = new Entry( "RAM", "Random Access Memory" );
    wordList[6] = new Entry( "URL", "Uniform Resource Locator" );
    wordList[7] = new Entry( "GUI", "Graphical User Interface" );
    wordList[8] = new Entry( "API", "Application Programming Interface" );
    wordList[9] = new Entry( "ROM", "Read-only Memory" );
    
    Arrays.sort( wordList );
    
    Scanner scan = new Scanner( System.in );
    String key = "";
    int location;

    System.out.print("Word: ");
    key = scan.next();
    
    while ( !key.equals("quit") && !key.equals("q") )
    {      
      location = Arrays.binarySearch( wordList, new Entry( key, "" ) );
      
      if ( location < 0 )
        System.out.println("Not in the dictionary");
      else
        System.out.println( wordList[location]  );

      System.out.print("Word: ");
      key = scan.next();
    }
    
  }  

}           

new Entry( key, "" )

Word: URL
URL     Uniform Resource Locator
Word: WWW
WWW     World Wide Web
Word: quit

Question 20:
Must all the cells of the array be non-null to use Arrays.binarySearch()?

21. Monster Object

Answer:
Yes.

class Monster implements 
{
  private int hitPoints, strength, age;
  private String name;
  
  public Monster( int hp, int str, int age, String nm )
  {
    hitPoints = hp; strength = str; this.age = age; name = nm;
  }
  
  public int getHitPoints() { return hitPoints; }
  
  public int getStrength()  { return strength; }
  
  public int getAge() { return age; }
  
  public String getName() { return name; }
  
  public String toString() 
  { 
    return "HP: " + getHitPoints() + " \tStr: " + getStrength() + "\t" + getName();
  }
  
  public int compareTo(  )
  {
  
     .... more goes here ...
  }
}

Question 21:
Fill in the blanks.

22. Use only some Instance Variables

Answer:
See Below

                
class Monster implements Comparable<Monster>
{

  . . . 
  
  public int compareTo( Monster other )
  {
  
     .... more goes here ...
  }
}

 public int compareTo( Monster other )
  {
    int hitDifference = getHitPoints()-other.getHitPoints();
    
    if (  )
      return hitDifference;
      
    else
      return  ;
      
  }

Question 22:
Fill in the blanks.

23. End of Chapter

Answer:

    

        

        
        

            
             
public int compareTo( Monster other )
  {
    int hitDifference = getHitPoints()-other.getHitPoints();
    
    if ( hitDifference != 0 )
      return hitDifference;     
    else
      return getStrength()-other.getStrength();
      
  }       
        
    

You have reached the end of the chapter. You may wish to search this list for something that interests you.

• The compareTo() compareTo() method.
• natural order natural order
• lexicographic order lexicographic order
• collating sequence collating sequence
• ordered array ordered array and the sort() method
• sort(), objects sort() method with reference values.
• binary search binary search