Problem with Treeset.contains ()

Question

So, I’ve been struggling with the problem for some time, I thought that I could ask for help here.

I am adding Ticket objects to the TreeSet, Ticket implements Comparable and has overridden methods equals (), hashCode () and CompareTo (). I need to check if an object is in a TreeSet using contains (). Now, adding 2 elements to the set, all this is perfectly checked, but after adding the third one he got messed up.

running this little piece of code after adding the third element to the TreeSet, Ticket temp2 is the object I am checking (verkoopLijst).

Ticket temp2 = new Ticket(boeking, TicketType.STANDAARD, 1,1); System.out.println(verkoop.getVerkoopLijst().first().hashCode()); System.out.println(temp2.hashCode()); System.out.println(verkoop.getVerkoopLijst().first().equals(temp2)); System.out.println(verkoop.getVerkoopLijst().first().compareTo(temp2)); System.out.println(verkoop.getVerkoopLijst().contains(temp2)); 

returns this:

 22106622 22106622 true 0 false 

Now my question will be how is this possible?

Edit:

 public class Ticket implements Comparable{ private int rijNr, stoelNr; private TicketType ticketType; private Boeking boeking; public Ticket(Boeking boeking, TicketType ticketType, int rijNr, int stoelNr){ //setters } @Override public int hashCode(){ return boeking.getBoekingDatum().hashCode(); } @Override @SuppressWarnings("EqualsWhichDoesntCheckParameterClass") public boolean equals(Object o){ Ticket t = (Ticket) o; if(this.boeking.equals(t.getBoeking()) && this.rijNr == t.getRijNr() && this.stoelNr == t.getStoelNr() && this.ticketType.equals(t.getTicketType())) { return true; } else return false; } /*I adjusted compareTo this way because I need to make sure there are no duplicate Tickets in my treeset. Treeset seems to call CompareTo() to check for equality before adding an object to the set, instead of equals(). */ @Override public int compareTo(Object o) { int output = 0; if (boeking.compareTo(((Ticket) o).getBoeking())==0) { if(this.equals(o)) { return output; } else return 1; } else output = boeking.compareTo(((Ticket) o).getBoeking()); return output; } //Getters & Setters 

Answer 1

The compareTo contract

The problem is in your compareTo . Here is an excerpt from the documentation :

The sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) must provide sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y .

The original code is reproduced here for reference:

 // original compareTo implementation with bug marked @Override public int compareTo(Object o) { int output = 0; if (boeking.compareTo(((Ticket) o).getBoeking())==0) { if(this.equals(o)) { return output; } else return 1; // BUG!!!! See explanation below! } else output = boeking.compareTo(((Ticket) o).getBoeking()); return output; } 

Why error return 1; ? Consider the following scenario:

• Given Ticket t1, t2
• Given t1.boeking.compareTo(t2.boeking) == 0
• Provided by t1.equals(t2) return false
• Now we have one of the following:
  • t1.compareTo(t2) returns 1
  • t2.compareTo(t1) returns 1

The final consequence of a contract violation is compareTo .

---

Problem fixing

First of all, you should take advantage of the fact that Comparable<T> is a parameterizable generic type. That is, instead of:

 // original declaration; uses raw type! public class Ticket implements Comparable 

it would be much more appropriate to declare something like this instead:

 // improved declaration! uses parameterized Comparable<T> public class Ticket implements Comparable<Ticket> 

Now we can write our compareTo(Ticket) (not compareTo(Object) anymore). There are many ways to rewrite this, but here is quite simplified:

 @Override public int compareTo(Ticket t) { int v; v = this.boeking.compareTo(t.boeking); if (v != 0) return v; v = compareInt(this.rijNr, t.rijNr); if (v != 0) return v; v = compareInt(this.stoelNr, t.stoelNr); if (v != 0) return v; v = compareInt(this.ticketType, t.ticketType); if (v != 0) return v; return 0; } private static int compareInt(int i1, int i2) { if (i1 < i2) { return -1; } else if (i1 > i2) { return +1; } else { return 0; } } 

Now we can also define equals(Object) in terms of compareTo(Ticket) instead of another:

 @Override public boolean equals(Object o) { return (o instanceof Ticket) && (this.compareTo((Ticket) o) == 0); } 

Pay attention to the compareTo structure: it contains several return , but in fact the logic flow is quite readable. Notice also how the priority of the sorting criteria is explicit and easily reordered if you have different priorities.

Related Questions

• What is a raw type and why shouldn't we use it?
• How to sort an array or ArrayList ASC first with x and then with y?
• If a function has only one return statement?

Answer 2

This can happen if the compareTo method is incompatible. That is, if a.compareTo(b) > 0 , then b.compareTo(a) should be <0. And if a.compareTo(b) > 0 and b.compareTo(c) > 0 , then a.compareTo(c) must be> 0. If this is not the case, the TreeSet may get confused.

Answer 3

First, if you use a TreeSet , the actual behavior of your hashCode methods will not affect the results. TreeSet does not rely on hashing.

Indeed, we need to see more code; for example, the actual implementations of the equals and compareTo methods, as well as the code that creates the TreeSet instance.

However, if I were to guess, it would be that you overloaded the equals method by declaring it the signature boolean equals(Ticket other) . This will lead to the behavior you see. To get the required behavior, you must override the method; eg.

 @Override public boolean equals(Object other) { ... 

(It's a good idea to add @Override to the annotation @Override that it is clear that the method overrides the method in the superclass or implements the method in the interface. If your method is not an override, then you will get a compilation error ... which would be nice.)

EDIT

Based on the code you added to the question, the problem is not overloading and overriding. (As I said, I only wondered ...)

It is likely that compareTo and equals are incorrect. It is still not entirely clear where the error is, because the semantics of both methods depend on the compareTo and equals methods of the Boeking class.

The first if Ticket.compareTo statement looks very suspicious. It seems like return 1; might call t1.compareTo(t2) and t2.compareTo(t1) to return 1 for some tickets t1 and t2 ... and that would definitely be a mistake.