CODEWITHSUNDEEP
javasortingtreeset
Aaron Brock
Aaron Brock

Reputation: 4536

TreeSet ignoring values

I am trying to create a class that is given pairs of strings & told one is 'greater" than the other then keeps a running order of all known strings.

To do this I keep a Map<String, Set<String>> that maps a given String to all the values it's greater than, then I created a TreeSet with a comparator that uses that data to compare two strings.

Here's my class:

public class StringSorter {

    private Map<String, Set<String>> greaterThan = new HashMap<>();
    private SortedSet<String> order;

    public StringSorter() {
        order = new TreeSet<>((o1, o2) -> {
            if (greaterThan.getOrDefault(o1, Collections.emptySet()).contains(o2))
                return 1;
            else if (greaterThan.getOrDefault(o2, Collections.emptySet()).contains(o1))
                return -1;
            return 0;
        });
    }

    public void addRule(String bigger, String smaller) {

        if (!greaterThan.containsKey(bigger))
            greaterThan.put(bigger, new HashSet<>());
        greaterThan.get(bigger).add(smaller);

        order.add(bigger);
        order.add(smaller);
    }

    public SortedSet<String> getOrder() {
        return order;
    }
}

However, for some reason, the TreeSet seems to just ignore many of the values added to it.

Example:

StringSorter sorter = new StringSorter();
sorter.addRule("one", "two");
sorter.addRule("two", "three");
sorter.addRule("three", "four");
System.out.println(sorter.getOrder());

Output:

[two, one]

What happened to the strings three & four?

Upvotes: 2

Views: 415

Answers (2)

mykolivy
mykolivy

Reputation: 76

The problem is that set collections keep unique values. After debugging your comparator you will see that "three" was evaluated as equal to "one", thus forbidding it to be added to the set.

Consider this modification:

public StringSorter() {
    order = new TreeSet<>((o1, o2) -> {
        if (greaterThan.getOrDefault(o1, Collections.emptySet()).contains(o2))
            return 1;
        else if (greaterThan.getOrDefault(o2, Collections.emptySet()).contains(o1))
            return -1;
        else if(o1.equals(o2)) return 0;
        else return -1; //or 1, or o1.compareTo(o2)
    });
}

Instead of just returning 0 we first check if objects are equal, if not than the comparison itself is irrelevant and result may be arbitrary.

Here is the output when using updated comparator:

[four, three, two, one]

[Edit]

I would consider changing internal representation of rules to custom oriented tree data structure, represented by sparse adjacency matrix.

Upvotes: 1

VGR
VGR

Reputation: 44328

You can answer this yourself by adding this line to your Comparator.compare lambda:

System.out.printf("(%s, %s)%n", o1, o2);

As you’ll see, there is no guarantee that adjacent values are passed to the Comparator. When o1 is "three" and o2 is "one", the comparison falls back to returning zero, which tells the TreeSet that the two values are equal, and obviously it won’t add a value it perceives as equal to a value that’s already in the set.

You would need to make your traversal of greaterThan transitive. I’m pretty sure it will require recursion:

private boolean isGreater(String o1,
                          String o2,
                          Set<String> keysTried) {
    Set<String> greaterSet = greaterThan.get(o1);
    if (greaterSet == null) {
        return false;
    }

    if (greaterSet.contains(o2)) {
        return true;
    }

    for (String g : greaterSet) {
        if (keysTried.add(g) && isGreater(g, o2, keysTried)) {
            return true;
        }
    }

    return false;
}

public StringSorter() {
    order = new TreeSet<>((o1, o2) -> {
        if (isGreater(o1, o2, new HashSet<>())) {
            return 1;
        } else if (isGreater(o2, o1, new HashSet<>())) {
            return -1;
        } else {
            return 0;
        }
    });
}

The purpose of keysTried is to prevent infinite recursion. (In theory, that should never happen anyway, if greaterThan is a directed graph.)

Upvotes: 1

Related Questions