TreeSet CompareTo not giving desirable result

Question

I am trying to create a set of all letters in all the words in a dictionary.

I am using a TreeSet for that as I have to do lot's of compare operations.

public class main {

    public static void main(String[] args) {

        Set<String> lines = new TreeSet<>();
        lines.add("ba");
        DictAwareSolver myGuesser = new DictAwareSolver(lines);
        myGuesser.makeGuess();
    }
}

This is my class which is operating on the set

package solver;

import sun.reflect.generics.tree.Tree;

import java.util.*;
import java.lang.System;

public class DictAwareSolver extends HangmanSolver
{

    private Set<String> dict;


    TreeSet<Node> myTree = new TreeSet<>();


    //getters

    public Set<String> getDict() {
        return dict;
    }
    


    // methods

    public DictAwareSolver(Set<String> dictionary) {
        this.dict = dictionary;
        // Implement me!
    } // end of DictAwareSolver()


    @Override
    public void newGame(int[] wordLengths, int maxIncorrectGuesses)
    {
        // Implement me!
    } // end of newGame()


    @Override
    public char makeGuess() {
        Set<String> guessDict = getDict();

        Iterator dictItr = guessDict.iterator();

        while (dictItr.hasNext())
        {
            String word = (String) dictItr.next();

            for (int i = 0; i<word.length(); i++)
            {
                Node temp = new Node(word.charAt(i));
                myTree.add(temp);
            }
        }

        Iterator treeItr = myTree.iterator();

        while (treeItr.hasNext())
        {
            Node n = (Node) treeItr.next();
            System.out.println(n.getLetter() + "-->"+n.getFrequency());
        }
        // TODO: This is a placeholder, replace with appropriate return value.
        return '\0';
    } // end of makeGuess()


    @Override
    public void guessFeedback(char c, Boolean bGuess, ArrayList< ArrayList<Integer> > lPositions)
    {
        // Implement me!
    } // end of guessFeedback()

} // end of class DictAwareSolver

class Node implements Comparable<Node>{
    private char letter;
    private int frequency;

    public Node(char letter)
    {
        this.letter = letter;
        this.frequency = 1;
    }

    public void countIncrementer()
    {
        int newCount = getFrequency()+1;
        setFrequency(newCount);
    }

    // getters

    public char getLetter() {
        return letter;
    }

    public int getFrequency() {
        return frequency;
    }

    // setters


    public void setFrequency(int frequency) {
        this.frequency = frequency;
    }

    @Override
    public int compareTo(Node o) {
        if (getLetter() == o.letter)
        {
            o.countIncrementer();
            return 0;
        }
        else if (getLetter() > o.getLetter())
        {
            return 1;
        }
        else
        {
            return -1;
        }
    }
}

When I am running this whatever I am adding 1st is giving a count of 2. As in this case output is

a-->1 b-->2

but I am expecting

a-->1 b-->1

It will be really helpful if you can point out what is the problem. From what I can think of it should be something in my o.countIncrementer(); in my compareTo method. I am new to java.

Answer 1

The code is making the assumption that the TreeSet will only call the comparator against an equal element if one already exists in the set, and if it does such a comparison, it will only do it exactly once. However, this is not how TreeSet is implemented. Looking at the API documentation for TreeSet, there are no guarantees as to how the comparisons will occur or with what frequency. Since this is not a documented part of the API, the authors of TreeSet are free to implement this functionality in any reasonable manner they wish, so long as it meets the documented API. In fact, they are also allowed to change how it's implemented between versions (e.g. Java 6 & Java 7), or between different implementations (e.g. Oracle vs. IBM).

In short, if the documentation does not guarantee a behavior, your code should not rely on that behavior.

To go into the specific behavior you're seeing, the first element added to a TreeSet (in the versions of Java you're using) is compared against itself. While this is perhaps surprising, it is not disallowed by the API. There may or may not be a good reason for this (I believe the check was added in Java 7 to force a NullPointerException to be thrown when a null is added as the first element to a TreeSet that disallows nulls per this bug). However, in the end, the reason for the check shouldn't matter to users of the API, since it's not disallowed in the API.

public static void main(String[] args) {
    System.out.printf("Java vendor & version: %s %s\n", System.getProperty("java.vendor"), Runtime.version());

    TreeSet<Character> set = new TreeSet<>(new LoggingComparator<>());
    set.add('a');
}

private static class LoggingComparator<T extends Comparable<? super T>> implements Comparator<T> {
    @Override
    public int compare(T o1, T o2) {
        System.out.println(o1 + " <=> " + o2);
        return o1.compareTo(o2);
    }
}

Java vendor & version: Oracle Corporation 11.0.4+10-LTS
a <=> a