TreeSet with comparable sorted by recursive dependency

Question

I have a set of objects which have a name (a) and dependecies (b). I want to order the objects in a way where all previous dependecies are resolved. So I have this code:

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class Foo {
    static class TestOrder implements Comparable<TestOrder> {
        private final String a;
        private final Set<String> b;

        public TestOrder(String a, Set<String> b) {
            this.a = a;
            this.b = b;
          }

        public int compareTo(TestOrder o) {
            if (o.b.contains(a)) 
              return -1;
            else
              return 1;
        }

        @Override
        public int hashCode() {
            return a.hashCode();
        }

        @Override
        public boolean equals(Object obj) {
            return a.equals(obj);
        }

        public String toString() {
            return a + " - " + b.toString();
        }
    }

    public static void main(String[] args) {
        Set<TestOrder> tos = new TreeSet<>();
        tos.add(new Foo.TestOrder("a", new HashSet<String>() {{
            add("b");
            add("c");
        }}));

        tos.add(new Foo.TestOrder("e", new HashSet<String>() {{
            add("a");
        }}));

        tos.add(new Foo.TestOrder("b", new HashSet<String>() {{
            add("d");
            add("c");
        }}));

        tos.add(new Foo.TestOrder("c", new HashSet<String>() {{ }}));
        tos.add(new Foo.TestOrder("d", new HashSet<String>() {{ }}));

        for (TestOrder to : tos) {
            System.out.println(to.toString());
        }
    }
}

which results in:

c - []
b - [d, c]
a - [b, c]
e - [a]
d - []

but - since b depends on d - the expected result would be:

c - []
d - []
b - [d, c]
a - [b, c]
e - [a]

What am I missing?

Answer 1

If someone is interested, this is how it works - finally (thanks to dasblinkenlight):

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Krusty
 */
public class Foo {
    static class TestOrder implements Comparable<TestOrder> {
        private final String a;
        private final Set<String> b;

        public TestOrder(String a, Set<String> b) {
            this.a = a;
            this.b = b;
          }

        public int compareTo(TestOrder o) {
            if (o.b.contains(a)) {
                return -1;
            } else {
                if (o.b.isEmpty() && b.isEmpty()) {
                    return a.compareTo(o.a);
                } else
                if (o.b.isEmpty() || b.isEmpty()) {
                    return b.isEmpty() ? -1 : 1;
                } else {
                    return 1;
                }
            }
        }

        @Override
        public int hashCode() {
            return a.hashCode();
        }

        @Override
        public boolean equals(Object obj) {
            return a.equals(obj);
        }

        public String toString() {
            return a + " - " + b.toString();
        }
    }

    public static void main(String[] args) {
        Set<TestOrder> tos = new TreeSet<>();
        tos.add(new Foo.TestOrder("a", new HashSet<String>() {{
            add("b");
            add("c");
        }}));

        tos.add(new Foo.TestOrder("e", new HashSet<String>() {{
            add("a");
        }}));

        // Cycle
        /*
        tos.add(new Foo.TestOrder("a", new HashSet<String>() {{
            add("e");
        }}));
        */
        tos.add(new Foo.TestOrder("b", new HashSet<String>() {{
            add("d");
            add("c");
        }}));

        tos.add(new Foo.TestOrder("c", new HashSet<String>() {{ }}));
        tos.add(new Foo.TestOrder("d", new HashSet<String>() {{ }}));

        /*
        for (TestOrder to : tos) {
            System.out.println(to.toString());
        }*/

        for (TestOrder to : sort(tos)) {
            System.out.println(to.toString());
        }
    }

    public static Set<TestOrder> sort(Set<TestOrder> tos) {
        Set<TestOrder> sorted = new LinkedHashSet<>();
        Set<String> cache = new LinkedHashSet<>();
        Set<TestOrder> cycles = new LinkedHashSet<>();
        Set<String> cycache = new LinkedHashSet<>();

        Iterator<TestOrder> it;
        while ((it = tos.iterator()).hasNext()) {
            TestOrder to = it.next();
            if (to.b.isEmpty())  {
                sorted.add(to);
                cache.add(to.a);
                it.remove();
            } else if (cache.containsAll(to.b)) {
                sorted.add(to);
                cache.add(to.a);
                it.remove();
            } else if (cycache.containsAll(to.b)) {
                cycles.add(to);
                cycache.add(to.a);
                it.remove();
            } else {
                cycles.add(to);
                cycache.add(to.a);
                it.remove();
            }
        }

        System.err.println("cycles");
        for (TestOrder to : cycles) {
            System.err.println(to.toString());
        }

        return sorted;
    }
}

Answer 2

Your compare method does not differ between an empty Set and a Set that does not contain the String "a". This compare method

    public int compareTo(TestOrder o) {
        if (o.b.contains(a)) {
            return -1;
        } else {
            if (o.b.isEmpty() && b.isEmpty()) {
                return a.compareTo(o.a);
            } else
            if (o.b.isEmpty() || b.isEmpty()) {
                return b.isEmpty() ? -1 : 1;
            } else {
                return 1;
            }
        }
    }

will give the result

c - []
d - []
b - [d, c]
a - [b, c]
e - [a]

Answer 3

You are missing several things (in the harder-to-fix order, starting with the easier ones):

1. Your comparator never returns zero, even if the same object is passed to it,
2. When neither object depends on the other one, there is no definitive tie-breaker,
3. At the time of object insertion in the tree set, not all items are available; however, insertion of a single new item may change relative ordering of other items.
4. The ordering considers only immediate dependencies.

You can fix the first two relatively easily by checking the dependency of this on o before returning 1, and using a.compareTo(o.a) for tie-breaking.

public int compareTo(TestOrder o) {
    if (o.b.contains(a)) 
      return -1;
    else if (b.contains(o.a))
      return 1;
    else
      return a.compareTo(o.a);
}

The third one could be fixed by switching to an array, and sorting it only after all the insertions have been made.

The last one, however, is very bad: in order to fix it, each item needs to know about the rest of the collection. I do not see a good way out of this, so I suggest using a traditional topological sorting algorithm to order your dependencies, rather than trying to shoehorn that problem in the framework of Java collections.