Java TreeSet contains() gives false results

I am trying to code a little bit of math with java. What I am trying to do, is to put cyclotomic cosets to the TreeSet. A coset has an index and a set of integer numbers. A coset is equal to other coset if the set has the same elements. If sets differ, then coset is ordered by its index.

For example:

C1 = [1, 2, 4, 8]
C3 = [3, 6, 9, 12]
C9 = [3, 6, 9, 12]

C1 is le开发者_StackOverflowss than C3
C3 is equal to C9

Well enough math. I chose to put cosets to TreeSet because I do not need duplicate elements and I need to have them sorted by index.

The problem is even TreeSet.contains() returns false, I can still find one element in the TreeSet which is equal when using compareTo() and equals() methods.

This is the actual printout of the program:

cosets = [C0, C1, C3, C5, C7]
cosets.contains(C9) = false
C0.compareTo(C9) = -1, C0.equals(C9) = false
C1.compareTo(C9) = -1, C1.equals(C9) = false
C3.compareTo(C9) = 0, C3.equals(C9) = true
C5.compareTo(C9) = -1, C5.equals(C9) = false
C7.compareTo(C9) = -1, C7.equals(C9) = false

I am attaching the code below. I did not want to make code any simplier, because I found that it does some magic. If you change MAGIC_INDEX value to 7 or less in the code, it starts to work. It seems like a JVM bug to me.

http://2m.lt/files/Main.java

http://2m.lt/files/Coset.java

Any suggestions?

---

As I often say, if you have a bug in your program, use a debugger. This showed me your problem very quickly.

TreeSet is a binary tree. When searching it navigates down the tree based on whether the element you are looking for is before or after (or the same) as the one it is examining. If you add the following to you compareTo()

System.out.println("Comparing, "+this+" to "+c);

it will print out

Comparing, C9 to C1
Comparing, C9 to C5
Comparing, C9 to C7

The problem is that C9 is after every element which it doesn't match. So when it gets to C5 on the tree, your compareTo to says it is after it, when actually it needs to look before (to get to C3) and the search goes down the wrong path of the tree.

---

Your compareTo() and equals() methods are not consistent, and therfore the TreeSet cannot work correctly with them.

From the API doc:

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

---

Your Comparable implementation in Coset does not provide a total ordering.

Looks like you should define an order on the value TreeSet. Either before or after checking index.