Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 10 of 10

Thread: Understanding the Comparable Interface

  1. #1
    Junior Member
    Join Date
    Sep 2011
    Posts
    21
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Understanding the Comparable Interface

    I am a new programmer learning about interfaces, and I was wondering if someone could explain how exactly the Comparable interface works. For example, I have two classes, one which implements Comparable and the other which uses Collections.sort to sort a collection of items using the compareTo method overridden in my class which implements Comparable. First off, why does calling Collections.sort ultimately result in the compareTo method being called? And how does the compareTo method work with only one argument? More specifically, when comparing this.price to temp.price, what is "this" referring to (I know it refers to the current object, but where is the object coming from?), and how does this end up sorting all elements in the list?

    Class 1: Defines characteristics of each Item
    package Item;
     
    import java.util.*;
     
    public class Item implements Comparable {
    	private String id;
    	private String name;
    	private double retail;
    	private int quantity;
    	private double price;
     
    	Item(String idIn, String nameIn, String retailIn, String quanIn) {
    		id = idIn;
    		name = nameIn;
    		retail = Double.parseDouble(retailIn);
    		quantity = Integer.parseInt(quanIn);
     
    		if(quantity>400)
    			price = retail*.5D;
    		else if(quantity>200)
    			price = retail *.6D;
    		else
    			price = retail*.7D;
    		price = Math.floor(price*100+.5)/100;
    	}
     
    	public int compareTo(Object obj) {
    		Item temp = (Item)obj;
    		if(this.price < temp.price)
    			return 1;
    		else if(this.price > temp.price)
    			return -1;
    		return 0;
    	}
     
    	public String getId() { return id; }
    	public String getName() {return name; }
    	public double getRetail() {return retail;}
    	public int getQuantity() {return quantity;}
    	public double getPrice() {return price;}
     
    }

    Class 2: Catalogs each item in a LinkedList
    package Item;
     
    import java.util.*; //includes class Collections with method sort which implements Comparable
     
    public class Storefront {
    	private LinkedList catalog = new LinkedList();
     
    	public void addItem(String id, String name, String price, String quant) {
    		Item it = new Item(id, name, price, quant);
    		catalog.add(it);
    	}
     
    	public Item getItem(int i) {return (Item)catalog.get(i);}
    	public int getSize() {return catalog.size();}
    	public void sort() {Collections.sort(catalog);}
    }

    I didn't include my main class which just adds a few items then calls the sort() method in Storefront


  2. #2
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,653
    Thanks
    25
    Thanked 325 Times in 302 Posts

    Default Re: Understanding the Comparable Interface

    1. Collections.sort() results in the compareTo() method being called due to inheritance. The Collections.sort() method accepts a List of objects that implement the Comparable Interface (or extend classes that implement the Comparable Interface), and calls the Comparable.compareTo(Comparable) method on each object in the List. Due to the way inheritance works, it will use the implementation of the compareTo() method that the object being invoked upon has created, which is why an implementation of the compareTo() method is required when you implement the Comparable Interface.
    2. The compareTo() method works with only one object because it is comparing the object you sent as an argument to the object you invoked the compareTo() method on.
    3. "this" is a keyword that refers to an instance of the object. "this.price" refers to the global price variable for the object you invoked the compareTo() method on. If there are no problems with scope (you have not declared any other variables named "price"), you don't even need the keyword "this". "temp.price" refers to the global price variable for the object you sent as the argument.

    Your confusions seem to be more about how Object Oriented Programming works, instead of how the compareTo() method works.
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  3. #3
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,297
    Thanks
    180
    Thanked 824 Times in 767 Posts
    Blog Entries
    5

    Default Re: Understanding the Comparable Interface

    First off, why does calling Collections.sort ultimately result in the compareTo method being called? And how does the compareTo method work with only one argument? More specifically, when comparing this.price to temp.price, what is "this" referring to (I know it refers to the current object, but where is the object coming from?), and how does this end up sorting all elements in the list?

    Interfaces can hide how some behavior is implemented. In the case of sorting, imagine for a moment if you wrote a Sorting algorithm that sorted Integers....you'd then have to rewrite the algorithm for each class type (String, Double, etc...), and doing so doesn't provide any way to sort any other class type without re-implementing the algorithm. But all the sorting algorithm needs to know is whether an object is less than, equal to, or greater than another...it should not care what it's sorting (String, Double, Integer, etc...) Enter the Comparable interface, which defines the behavior for comparing one object to another. Written in this way, the sorting algorithm can be written once to compare objects, so long as the class types being sorted implement the appropriate interface (Comparable). From the standpoint of the class that implements the interface (Comparable) - it uses its available data to compare itself to another as appropriate (the sorting algorithm never directly sees this). IMO this is one of the major concept to understand about interfaces - it abstracts algorithms so you can write them once rather than several times for each type of input data.

  4. #4
    Junior Member
    Join Date
    Sep 2011
    Posts
    21
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Understanding the Comparable Interface

    Thanks, but I still don't totally understand how Collections.sort() results in compareTo() being called. Could you be more detailed than "due to inheritance"? I'm looking at the Oracle Docs and I just don't get how Collections.sort(list) "jumps" to compareTo() being called for each item in the list. I get that each item in the list must implement the Comparable interface, but how does that cause the compareTo() method being called? What is the exact process going on here?

  5. #5
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,297
    Thanks
    180
    Thanked 824 Times in 767 Posts
    Blog Entries
    5

    Default Re: Understanding the Comparable Interface

    A quick, dirty, and simple (and somewhat poor) example to demonstrate an interface in this context:

    /**
    * Interface defining an object that contains a value
    */
    public interface Value{
        public int getValue();
    }
    /**
    * Implementation of the Value interface that is based upon an Integer
    */
    public class IntegerValue implements Value{
     
        private final int value;
        public IntegerValue(int val){
            this.value = val;
        }
     
        @Override
        public int getValue(){
            return value;
        }
    }
    /**
    * Defines a value of 2, for demonstration
    */
    public class TwoValue implements Value{
        @Override
        public int getValue(){
            return 2;
        }
    }
     
    public class AddUtil{
        /**
        * Adds all the values in the parameter List
        */
        public static int addValues(List<Value> adders){
            int added = 0;
            for ( Value add : adders ){
                added += add.getValue();
            }
            return added;
        }
     
        public static void main(String[] args){
             List<Value> adders = new ArrayList<Value>();
             adders.add(new TwoValue());
             adders.add(new IntegerValue(1));
             adders.add(new TwoValue());
             adders.add(new IntegerValue(10));
             System.out.println(AddUtil.addValues(adders));
        }
    }

    Should compile (although I didn't test). The point is that a) the AddUtil.addValues method doesn't care about implementation b) You can implement the Value interface any way you want - so long as it abides by the contract of the interface. To make an analogy to Collections.sort - Collections.sort is to AdderUtil.addValues as the Comparable interface is to the Value interface.

  6. #6
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    939
    Thanks
    6
    Thanked 202 Times in 178 Posts

    Default Re: Understanding the Comparable Interface

    Thanks, but I still don't totally understand how Collections.sort() results in compareTo() being called.
    Generally when some type of thing is comparable with others of its kind (say people by age, or beer glasses by volume) it is often the case that some outside agency does the comparing: the barman might decide that a customer is old enough to buy beer, the customer that they want a pint.

    In Java code comparisons are done by calling the compareTo() method of an instance using a reference to some other instance as an argument. The interface definition ensures that compareTo() is there able to be used. So it is the Comparable instance that actually does the comparing. It is as if the barman doesn't compare the customer's age with some standard but, instead, asks "How does your age compare to 20?". An odd way of doing things, perhaps. But effective.

    Sorting a collection involves a whole lot of comparisons. (You can test that by actually sorting a bunch of things and noticing how you do it. In any case, it *can* be done using a whole bunch of comparisons.) These comparisons are done not by putting the things alongside one another and comparing, but after the fashion of the barman, asking "are you bigger, lesser or equal to that?" to the various elements of the collection. Being instances of Comparable they all implement the compareTo() method and, so, can answer such questions.

    If you look at the source code for Collections.sort() you will see that this method does actually call the compareTo() method of the collection elements.
    Last edited by pbrockway2; July 3rd, 2012 at 02:24 AM.

  7. #7
    Junior Member
    Join Date
    Sep 2011
    Posts
    21
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: Understanding the Comparable Interface

    If you look at the source code for Collections.sort() you will see that this method does actually call the compareTo() method of the collection elements.
    This is what I was trying to do before I replied, and I still can't find it. Here is the code for Collections.sort():

    public static <T extends Comparable<? super T>> void sort(List<T> list) {
                 Object[] a = list.toArray();
                 Arrays.sort(a);
                 ListIterator<T> i = list.listIterator();
                 for (int j=0; j<a.length; j++) {
                     i.next();
                     i.set((T)a[j]);
                 }
    }

    No compareTo() call here, but maybe it's called in Arrays.sort(a). Here's the code from java.util.Arrays:

    public static void sort(Object[] a) 
            sort(a, 0, a.length, NATURAL_ORDER);
       }

    This is where I get stuck. NATURAL_ORDER seems to be a variable of type Comparator<Object>, but I can find no other sort method in Arrays that takes this set of arguments. While I understand the answers to my previous question, there is obviously something else going on here that I don't quite understand. If someone could find and describe the full path from Collections.sort() to compareTo() then that would be pretty awesome

  8. #8
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,297
    Thanks
    180
    Thanked 824 Times in 767 Posts
    Blog Entries
    5

    Default Re: Understanding the Comparable Interface

    See the mergeSort method of Arrays in the source: java.util: Arrays.java directly calling compareTo method, which provides you with the stack trace path to where compareTo can be called (I say can, because the source shows multiple sort methods that could be called). See post #5 (which you seem to have completely ignored) if you wish to understand the concept in a more simplified manner

  9. #9
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    939
    Thanks
    6
    Thanked 202 Times in 178 Posts

    Default Re: Understanding the Comparable Interface

    I only have the 1.7 source on this machine. But, commented out, is the definition of NATURAL_ORDER:

    private static final Comparator<Object> NATURAL_ORDER = new Comparator<Object>() {
        @SuppressWarnings("unchecked")
        public int compare(Object first, Object second) {
            return ((Comparable<Object>)first).compareTo(second);
        }
    };

    A Comparator instance is what I was referring to before as an "outside agency" that might do the comparing. It is declared to have compare() method that takes two arguments which it compares. The NATURAL_ORDER comparator is used to do the sorting with "sort(a, 0, a.length, NATURAL_ORDER);"

    The array elements being sorted are actually instances of Comparable and, as that piece of code shows, the NATURAL_ORDER comparator indeed uses the comparable's compareTo() to implement its own compare() method.

  10. #10
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    939
    Thanks
    6
    Thanked 202 Times in 178 Posts

    Default Re: Understanding the Comparable Interface

    Schematically compareTo() is used to sort a list of comparable things as follows:

    (1) Sorting the list is turned into sorting an array of comparable things by the Collections method
    Then, in Arrays:
    (2) A suitable Comparator instance is created which will use compareTo() to implement compare()
    (3) The comparator's compare() - and hence the comparables' compareTo() - is called lots of times to effect the array sort
    Back in Collections:
    (4) The sorted array is used to repopulate the list

Similar Threads

  1. When to use Comparator and Comparable Interface in java
    By diyaots in forum Java Theory & Questions
    Replies: 7
    Last Post: October 26th, 2012, 09:35 AM
  2. Comparable is implemented, but still " java.lang.Comparable" error appears
    By knowNothing23 in forum What's Wrong With My Code?
    Replies: 14
    Last Post: June 20th, 2012, 04:32 PM
  3. Need more help, this time requiring the Comparable interface
    By Mellowhype in forum What's Wrong With My Code?
    Replies: 4
    Last Post: November 14th, 2011, 10:58 PM
  4. Help with Comparable interface.
    By novice564 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: October 19th, 2011, 08:39 AM
  5. Comparable Interface
    By yelrubk in forum What's Wrong With My Code?
    Replies: 1
    Last Post: April 28th, 2010, 09:08 AM

Tags for this Thread