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 less 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.
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.