aspose file tools*
The moose likes Beginning Java and the fly likes compareTo method Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "compareTo method" Watch "compareTo method" New topic
Author

compareTo method

Cheryl Scodario
Ranch Hand

Joined: Nov 28, 2009
Posts: 69
Hi all, I am learning Huffman encoding now. The following is a code that my teacher did. He made Huffman Data class and Huffman Tree class. However, I just have a question about the Huffman Data class.


So I mainly have trouble understanding the compareTo method on line 09. I don't get why the parameter is another object d? Is this method just comparing the frequency of each letter? So is each letter a Huffman Data object? Like if given A4, B6, C9, is each of them an individual object? Or all of them a one single Huffman Data object? Back to the parameter of compareTo, what is the object d? How does it work?
Thank you for clarification!
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

Note that each instance of HuffmanData has a char called "letter" and an int called "frequency." So yes, your examples of A4, B6, and C9 would each represent separate objects.

The compareTo method is intended to compare the current object (in this case, an instance of HuffmanData) with some other object (presumably of the same type). In other words, compare this instance of HuffmanData to Object d. The implementation in this example assumes that Object d is, in fact, an instance of HuffmanData. If it's not, then the the method will throw a runtime exception when it attempts the cast in line 11...

(HuffmanData)d

In the Comparable interface, the compareTo method was originally defined to take an Object as a parameter, and that's how it's being used here. However, since generics were introduced in Java 5, the preferred way of implementing this would be to specify HuffmanData as the type for Comparable, and use that type in the compareTo method (eliminating the need for an explicit cast)...

But either way, this compareTo method is basically just comparing the frequency value of the current object to the frequency value of the other object. It does this by converting the frequency int values to Integer instances, so it's comparing (Integer)frequency to (Integer)d.frequency. Then the actual comparison uses the compareTo method of the Integer class, which is why it's written...

((Integer)frequency).compareTo((Integer)d.frequency)

Personally, I don't see a reason for creating Integer objects here. I would just stick with ints, and:
  • return -1 if frequency < d.frequency; or
  • return 0 if frequency == d.frequency; or
  • return 1 if frequency > d.frequency.


  • "We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
    sscce.org
    Ernest Friedman-Hill
    author and iconoclast
    Marshal

    Joined: Jul 08, 2003
    Posts: 24187
        
      34

    marc weber wrote:
    Personally, I don't see a reason for creating Integer objects here. I would just stick with ints,


    Absolutely!


  • return -1 if frequency < d.frequency; or
  • return 0 if frequency == d.frequency; or
  • return 1 if frequency > d.frequency.


  • But compareTo() is only required to return negative or positive, not -1 or +1; therefore the fastest, cleanest, simplest implementation is actually just



    [Jess in Action][AskingGoodQuestions]
    marc weber
    Sheriff

    Joined: Aug 31, 2004
    Posts: 11343

    Ernest Friedman-Hill wrote:... compareTo() is only required to return negative or positive, not -1 or +1...

    Indeed, that's true!
    Rob Spoor
    Sheriff

    Joined: Oct 27, 2005
    Posts: 19761
        
      20

    Ernest Friedman-Hill wrote:But compareTo() is only required to return negative or positive, not -1 or +1; therefore the fastest, cleanest, simplest implementation is actually just



    Except that code will return an invalid value if the subtraction overflows. What if the first frequency is Integer.MIN_VALUE and the second one is 1? The result would be Integer.MAX_VALUE, so a value with the wrong sign is returned. That's why the < and > comparison is better. That's also used in Integer.compareTo:
    Using simple subtraction is always safe for byte, short and char only. It's only safe for int (and long) if the allowed values are limited enough to ensure no overflow will occur.


    SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
    How To Ask Questions How To Answer Questions
    Mike Simmons
    Ranch Hand

    Joined: Mar 05, 2008
    Posts: 3018
        
      10
    Rob Spoor wrote:Except that code will return an invalid value if the subtraction overflows. What if the first frequency is Integer.MIN_VALUE and the second one is 1?

    A valid concern in general. However "frequency" sounds to me like it represents the number of times a given character occurs. Can this ever be negative? And if it's never negative, can subtraction overflow ever occur? Using this trick is maybe worth a comment or assertion, however:
    Ernest Friedman-Hill
    author and iconoclast
    Marshal

    Joined: Jul 08, 2003
    Posts: 24187
        
      34

    Yes, that's true, the subtraction technique is technically only valid in certain circumstances. In practice, I find it's rather rare to want to order a collection using a signed integer as a key; you virtually always are using a size or count of some kind that can't meaningfully take a negative value.
    Cheryl Scodario
    Ranch Hand

    Joined: Nov 28, 2009
    Posts: 69
    marc weber wrote:Note that each instance of HuffmanData has a char called "letter" and an int called "frequency." So yes, your examples of A4, B6, and C9 would each represent separate objects.

    The compareTo method is intended to compare the current object (in this case, an instance of HuffmanData) with some other object (presumably of the same type). In other words, compare this instance of HuffmanData to Object d. The implementation in this example assumes that Object d is, in fact, an instance of HuffmanData.
    But either way, this compareTo method is basically just comparing the frequency value of the current object to the frequency value of the other object. It does this by converting the frequency int values to Integer instances, so it's comparing (Integer)frequency to (Integer)d.frequency. Then the actual comparison uses the compareTo method of the Integer class, which is why it's written...


    Thanks, marc. One question though, supposedly given A4, B6, C9, and the object for this class is HuffmanData data = new Huffman Data(A,4); so when I call the compareTo method on this object, which is data.compareTo (Object d); I am not sure what to put in the parameter. As you said, Object d is also an instance of HuffmanData. But do we need to declare it (new) in any way? I mean how does compiler know that Object d is B6? and then become C9?
    marc weber
    Sheriff

    Joined: Aug 31, 2004
    Posts: 11343

    You can create a new HuffmanData instance for each of your examples...

    "Object d" is only the argument list for the compareTo method. Nothing is assigned to d until that method is called, which you can do once you have references to these instances. For example...
    Cheryl Scodario
    Ranch Hand

    Joined: Nov 28, 2009
    Posts: 69
    marc weber wrote:You can create a new HuffmanData instance for each of your examples...

    "Object d" is only the argument list for the compareTo method. Nothing is assigned to d until that method is called, which you can do once you have references to these instances. For example...


    Thanks! This makes perfect sense. One question though, when we call the compareTo method, it just compares the frequencies of these different objects, but it doesn't actually DO anything. like it doesn't swap like what sorting would do. So what's the point of just comparing different frequencies? Would it make a difference if I didn't include compareTo method in my code?
    marc weber
    Sheriff

    Joined: Aug 31, 2004
    Posts: 11343

    Cheryl Scodario wrote:... Thanks! This makes perfect sense. One question though, when we call the compareTo method, it just compares the frequencies of these different objects, but it doesn't actually DO anything. like it doesn't swap like what sorting would do. So what's the point of just comparing different frequencies? Would it make a difference if I didn't include compareTo method in my code?

    Your class, HuffmanData, IS Comparable, meaning it implements the Comparable interface. The API documentation says, "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.

    So by declaring that HuffmanData IS Comparable, you are saying that instances of HuffmanData can be ordered in a way that makes sense for these instances. In particular, they are guaranteed to have a compareTo() method that behaves in a predefined way -- returning "a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object."

    This is important because instances of HuffmanData can now be used in other code that you know nothing about. For example, suppose you need to sort a huge array of HuffmanData instances. The class java.util.Arrays contains a sort() method that will do this for you! That sort() method requires only that all elements in the array implement Comparable, because that's what it will use for ordering.

    Note that the sort() method doesn't care what else these instances are -- whether they're Strings, Integers, HuffmanData, MyOwnWeirdObject, etc. -- as long as they are Comparable. After all, how would sort() know what "order" means for MyOwnWeirdObject? I need to describe that, and I do it in a way other code can understand: The CompareTo() method.

    This is why interfaces are sometimes described as "contracts." They don't "do" anything by themselves, but they guarantee that a class will implement the behavior described by the interface.
    Cheryl Scodario
    Ranch Hand

    Joined: Nov 28, 2009
    Posts: 69
    marc weber wrote:
    Cheryl Scodario wrote:... Thanks! This makes perfect sense. One question though, when we call the compareTo method, it just compares the frequencies of these different objects, but it doesn't actually DO anything. like it doesn't swap like what sorting would do. So what's the point of just comparing different frequencies? Would it make a difference if I didn't include compareTo method in my code?

    Your class, HuffmanData, IS Comparable, meaning it implements the Comparable interface. The API documentation says, "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.

    So by declaring that HuffmanData IS Comparable, you are saying that instances of HuffmanData can be ordered in a way that makes sense for these instances. In particular, they are guaranteed to have a compareTo() method that behaves in a predefined way -- returning "a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object."

    This is important because instances of HuffmanData can now be used in other code that you know nothing about. For example, suppose you need to sort a huge array of HuffmanData instances. The class java.util.Arrays contains a sort() method that will do this for you! That sort() method requires only that all elements in the array implement Comparable, because that's what it will use for ordering.

    Note that the sort() method doesn't care what else these instances are -- whether they're Strings, Integers, HuffmanData, MyOwnWeirdObject, etc. -- as long as they are Comparable. After all, how would sort() know what "order" means for MyOwnWeirdObject? I need to describe that, and I do it in a way other code can understand: The CompareTo() method.

    This is why interfaces are sometimes described as "contracts." They don't "do" anything by themselves, but they guarantee that a class will implement the behavior described by the interface.


    Thanks, Marc! I understand it now!
     
    It is sorta covered in the JavaRanch Style Guide.
     
    subject: compareTo method