How can I use a custom class in a TreeSet?

java treeset

12,519

Solution 1

It's not going to be able to sort it without you implementing Comparable<Node>, and it won't really be an appropriate for set operations until you override equals() and hashCode(). (You don't have to override equals and hashCode for TreeSet to work, but it would make sense to do so.)

Something like this:

final class Node implements Comparable<Node> {

  private final int x;
  private final int y;

  Node(int x, int y) {
    this.x = x;
    this.y = y;
  }

  @Override public boolean equals(Object other) {
    if (!(other instanceof Node)) {
      return false;
    }
    Node otherNode = (Node) other;
    return x == otherNode.x && y == otherNode.y;
  }

  @Override public int hashCode() {
    return x * 31 + y * 17; // For example...
  }

  @Override public int compareTo(Node other) {
    // As of Java 7, this can be replaced with
    // return x != other.x ? Integer.compare(x, other.x) 
    //     : Integer.compare(y, other.y);

    if (x < other.x || (x == other.x && y < other.y)) {
      return -1;
    }
    return x == other.x && y == other.y ? 0 : 1;
  }
}

(Note that by convention the class name would be Node, not node.)

Solution 2

Node needs to implement a Comparable or you need to pass a custom Comparator which can compare two Node objects. Also, any hash based collection relies on the object suitably overriding equals() and hashcode() method.

Solution 3

You have to specify equals, hashCode and implement the Comparable interface

12,519

Author by

SNpn

Updated on August 03, 2022

Comments

SNpn almost 2 years
If I was using a Set similar to this:
```
Set<node> s=new TreeSet<node>();

class node {

  private int x;
  private int y;

}
```
Would this be acceptable, and since it's a TreeSet, would it also sort it?
Bohemian almost 13 years

That's not actually correct. Just Comparable is enough. You should implement equals(), but the default Object.equals() and Object.hashcode() is sufficient to "work" - there's no "have to" about it.
Bohemian almost 13 years

FYI, TreeSet is not hash-based.
Scorpion almost 13 years

@Bohemian yes you are right, TreeSet or TreeMap specifically doesn't use hashing.
mohdajami almost 13 years

what is the reason of making it final class?
Jon Skeet almost 13 years

@medopal: Equality and other things become harder to implement correctly (when there even is an idea of correctness) when inheritance is involved. Likewise when I know there are no subclasses, I know it's immutable. Basically I subscribe to "design for inheritance or prohibit it".
Scorpion almost 13 years

or "depending on the use case" use guava or apache commons to avoid the branching in your code and the let the library implement the hashcode and equals method.
Jon Skeet almost 13 years

@Carlos: No, hence the sentence stating "You don't have to override equals and hashCode for TreeSet to work, but it would make sense to do so." I find it much easier to reason about code when comparable implementations also obey natural equality.
Brett almost 13 years

"Note that null is not an instance of any class, and e.compareTo(null) should throw a NullPointerException even though e.equals(null) returns false." Drop the first if statement.
Brett almost 13 years

@since 1.7 return x != other.x ? Integer.compare(x, other.x) : Integer.compare(y, other.y);
Jon Skeet almost 13 years

@Tom: Thanks, removed the "if" check. Will add a comment for the Integer.compare (good to see that's finally there...)
SNpn almost 13 years

@Jon what does hashCode do and why do I have to override it?
Jon Skeet almost 13 years

@SNpn: That's a far bigger question than can be answered easily in comments - I suggest you look at the documentation in java.lang.Object to start with, and then ask another question if it doesn't explain everything. In this case as TreeSet only cares about ordering, you don't have to do it - but you'd get odd results if you used a HashSet instead.
SNpn almost 13 years

@Jon one more question, how come when I try to override the compareTo function it says it doesnt need to be overriden. Also just by overriding the equals operation, does that make the treeset's sorting ability work?
Jon Skeet almost 13 years

@SNpn: Using @Override for interface methods is a nice way of communicating that you're providing the implementation of a method originally declared elsewhere. It's not necessary, and in Java 5 it's not permitted IIRC, but in Java 6+ I still prefer it. And no, just overriding equals won't let TreeSet sort the values - how would it be able to tell which value should come before the other?