TreeSet acting weird

Question

I'm having a weird problem with TreeSet (sortedNodes) and ArrayList (nodes). In my program, I have in a method called from Event Dispatch Thread (from ActionListener) these lines:

        System.out.println("nodes: "+nodes.size());
        sortedNodes.addAll(nodes);
        System.out.println("sortedNodes: "+sortedNodes.size());

Problem is, on some collections sortedNodes.size() returns lower number than nodes.size() (on these 3 lines, so there is no change in content of nodes). When I then print content of sortedNodes , it's not even sorted in addition to not containing all the objects it should. Weird thing is - if I call the whole method again, it fixes the issue. I don't get it - same code is executed, on same collections, but first time it doesn't work and 2nd time it does. Any ideas?

EDIT: If my problem is not very clear, this should help

exportTree();
exportTree();

pritns on output this:

nodes: 7
sortedNodes: 4
b2[23,57]a[46,97]b[65,77]c[43,43]

nodes: 7
sortedNodes: 7
a[46,97]b[65,77]b1[55,89]b2[23,57]b3[20,20]c[43,43]c1[99,88]

Comparator:

public class NodeComparator implements Comparator<Node>{
    public int compare(Node o1, Node o2) {
        return o1.getLabel().compareTo(o2.getLabel());
    }
}

Node:

public class Node {

private int order;
private String label;
private Integer[] keys;
private Node[] pointers;
private Node parent;

public Node(int order, String label, Integer[] keys, Node[] pointers) {
    this.order = order;
    this.label = label;
    this.parent = null;
    if (pointers == null) {
        this.pointers = new Node[order+1];
    } else {
        this.pointers = pointers;
    }
    if (keys == null) {
        this.keys = new Integer[order];
    } else {
        this.keys = keys;
    }
}

public Node getParent() {
    return parent;
}

public void setParent(Node parent) {
    this.parent = parent;
}

public Integer[] getKeys() {
    return keys;
}

public void setKeys(Integer[] keys) {
    this.keys = keys;
}

public String getLabel() {
    return label;
}

public void setLabel(String label) {
    this.label = label;
}

public int getOrder() {
    return order;
}

public void setOrder(int order) {
    this.order = order;
}

public Node[] getPointers() {
    return pointers;
}

public void setPointers(Node[] pointers) {
    this.pointers = pointers;
}

public Node getPointer(int i) {
    return pointers[i];
}

public void setPointer(int i, Node node) {
    pointers[i] = node;
}

public Integer getKey(int i) {
    return keys[i];
}

public void setKey(int i, Integer key) {
    keys[i] = key;
}
}

Whole method:

public void exportTree() {
    String graphInText = "";
    if (nodeShapes.isEmpty()) {
        graphInText = "empty";
    } else {
        char c = 'a';
        ArrayList<Node> nodes = new ArrayList<Node>();
        sortedNodes.clear();
        System.out.println("nodeShapes: " + nodeShapes.size());
        // populate the collection of nodes from their 2d representation(nodeShapes)
        // and label every root with different character
        for (NodeShape n : nodeShapes) {
            nodes.add(n.getNode());
            if (n.getParentLink() == null) {
                n.getNode().setLabel(c + "");
                c++;
            }
        }
        System.out.println("nodes: " + nodes.size());
        // copy all the nodes (currently every node except roots has label "0")
        sortedNodes.addAll(nodes);
        System.out.println("sortedNodes: " + sortedNodes.size());
        // check labels of every node; if it contains any of the characters
        // that were assigned to roots, use this label for every child of
        // this node and add number of the pointer at the end of the string;
        // when this is done, remove those nodes, which children have been 
        // labeled;
        // repeat whole procedure while there is no node left - and this will
        // happen, since every node is connected to a root or is a root;            
        while (!nodes.isEmpty()) {
            ArrayList<Node> nodesToBeRemoved = new ArrayList<Node>();
            for (Node n : nodes) {
                for (char c2 = 'a'; c2 <= c; c2++) {
                    if (n.getLabel().contains(c2 + "")) {
                        for (int i = 1; i <= n.getOrder(); i++) {
                            Node child = n.getPointer(i);
                            if (child != null) {
                                child.setLabel(n.getLabel() + i);
                            }
                        }
                        nodesToBeRemoved.add(n);
                    }
                }
            }
            if (!nodesToBeRemoved.isEmpty()) {
                nodes.removeAll(nodesToBeRemoved);
            }
        }
        Node[] nodesA = sortedNodes.toArray(new Node[sortedNodes.size()]);
        for (Node n : nodesA) {
            String nodeInText;
            nodeInText = n.getLabel() + "[";
            for (int i = 1; i < n.getOrder() - 1; i++) {
                nodeInText += n.getKey(i) + ",";
            }
            nodeInText += n.getKey(n.getOrder() - 1) + "]";
            graphInText += nodeInText;
        }

    }
    System.out.println(graphInText);
    label.setText(graphInText);
}

I also altered the program so every time I create/remove NodeShape, also Node is added/removed to new collection and I used this new collection in exportTree() instead of nodeShapes - but it works the same, so there is no problem with nodeShapes. It's just the TreeSet.. when I don't use it, everything works okay (but I don't get my nodes sorted).

Answer 1

TreeSet follows Set semantics, so no duplicates are allowed. ArrayList does allow duplicates, so it could have more nodes than TreeSet if you add Nodes more than once.

TreeSet sorts using Comparable semantics. Is your Node Comparable? Do you pass a Comparator to tell it how to sort? You should.

TreeSet works naturally without any effort on your part for primitives, Strings, and anything else that is Comparable.

Perhaps those explain some of the behavior you're observing.

Answer 2

You've got a lot of code after your line:

System.out.println("sortedNodes: " + sortedNodes.size());

Something that's done beneath it may could be modifying your nodes object which causes the exportTree() method to behave as expected the second time around. If you can, comment out the lines and see if your method works as expected on the second call.

Answer 3

Even though I see no traces of threading, this indeed sounds like a threading issue to me. Did you try using a Synchronized collection to check if the behaviour is the same?

Answer 4

And this is why I asked for the code... :) :) :)

You are potentially changing the label of the node after adding it to the set but before printing out the values. The label is what is used for set equivalence. For one thing, you are badly mucking around the internal workings of the set since your nodes are providing inconsistent results... but that's not really the problem here.

What I suspect is happening is that the nodes are presenting labels like "a", "b", "c" right out of the ArrayList when adding them to the set... and then they are corrected to have their "a1", "b1", etc. labels afterwards (but before printing). This is why the second call works because the labels have all been "fixed". In the first call, they probably really are duplicates the first time they are added to the set.

...earlier debugging routines that provide better "control" data would reveal this.

Edit to clarify:

You start with an ArrayList of seven nodes but 3 of them have the same label as some of the others so that there are only 4 unique labels.

You add all 7 of those to a Set and only get 4 elements in the set because there were only 4 unique labels.

You then modify the labels of the nodes (for example changing "b" -> "b1").

When you run the method again then everything works because the labels have already been setup.

The comment about earlier "control" debugging was a suggestion to dump the contents of the array list and the set prior to modifying the nodes... ie: right after you see your strange results and not after altering the conditions of the "debug" testing.