• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

compareTo method

 
Ranch Hand
Posts: 69
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
 
Sheriff
Posts: 11343
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
  •  
    author and iconoclast
    Posts: 24207
    46
    Mac OS X Eclipse IDE Chrome
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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


     
    marc weber
    Sheriff
    Posts: 11343
    Mac Safari Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

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


    Indeed, that's true!
     
    Sheriff
    Posts: 22781
    131
    Eclipse IDE Spring VI Editor Chrome Java Windows
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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.
     
    Master Rancher
    Posts: 4796
    72
    • Likes 2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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
    Posts: 24207
    46
    Mac OS X Eclipse IDE Chrome
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    Posts: 69
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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
    Posts: 11343
    Mac Safari Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    Posts: 69
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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
    Posts: 11343
    Mac Safari Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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
    Posts: 69
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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!
     
    Consider Paul's rocket mass heater.
    reply
      Bookmark Topic Watch Topic
    • New Topic