javacollectionsedt

TreeSet acting weird

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

Solution

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