0

TreeSet ( sortedNodes) 和 ArrayList ( nodes) 有一个奇怪的问题。在我的程序中，我有一个从事件调度线程（来自ActionListener）调用的方法，这些行：

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

问题是，在某些集合上sortedNodes.size()返回的数字低于nodes.size()（在这 3 行上，因此 的内容没有变化nodes）。然后，当我打印 的内容时sortedNodes，除了不包含它应该包含的所有对象之外，它甚至都没有排序。奇怪的是 - 如果我再次调用整个方法，它会解决问题。我不明白 - 在相同的集合上执行相同的代码，但第一次不起作用，第二次起作用。有任何想法吗？

编辑：如果我的问题不是很清楚，这应该会有所帮助

exportTree();
exportTree();

在输出上打印：

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]

比较器：

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

节点：

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;
}
}

整体方法：

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);
}

我还更改了程序，因此每次创建/删除 NodeShape 时，也会将 Node 添加/删除到新集合中，我在 exportTree() 中使用这个新集合而不是 nodeShapes - 但它的工作原理相同，所以 nodeShapes 没有问题. 它只是 TreeSet .. 当我不使用它时，一切正常（但我没有对节点进行排序）。

4

4 回答 4

5

TreeSet 遵循 Set 语义，因此不允许重复。ArrayList 确实允许重复，因此如果您多次添加节点，它可能具有比 TreeSet 更多的节点。

TreeSet 使用 Comparable 语义进行排序。您的节点可比吗？您是否通过 Comparator 告诉它如何排序？你应该。

TreeSet 可以自然地工作，无需您为原语、字符串和任何其他可比较的东西付出任何努力。

也许这些解释了您正在观察的一些行为。

于 2010-01-06T02:59:22.783 回答
1

这就是为什么我要求提供代码... :) :) :)

在将节点添加到集合之后但在打印出值之前，您可能会更改节点的标签。标签是用于集合等价的。一方面，由于您的节点提供的结果不一致，因此您严重破坏了集合的内部工作......但这并不是真正的问题。

我怀疑正在发生的事情是，当将节点添加到集合中时，节点会在 ArrayList 中显示诸如“a”、“b”、“c”之类的标签......然后将它们更正为具有它们的“a1”， “b1”等标签之后（但在打印之前）。这就是第二次调用有效的原因，因为标签都已“修复”。在第一次调用中，它们在第一次添加到集合时可能确实是重复的。

...提供更好的“控制”数据的早期调试程序会揭示这一点。

编辑以澄清：

您从一个包含 7 个节点的 ArrayList 开始，但其中 3 个节点与其他节点具有相同的标签，因此只有 4 个唯一标签。

您将所有 7 个元素添加到一个 Set 中，并且只得到 4 个元素，因为只有 4 个唯一标签。

然后修改节点的标签（例如更改“b”->“b1”）。

当您再次运行该方法时，一切正常，因为已经设置了标签。

关于早期“控制”调试的评论是建议在修改节点之前转储数组列表和集合的内容......即：在你看到奇怪的结果之后而不是在改变“调试”的条件之后测试。

于 2010-01-06T22:27:56.817 回答
0

在你的行之后你有很多代码：

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

在它下面完成的事情可能是修改你的节点对象，这导致 exportTree() 方法第二次按预期运行。如果可以，请注释掉这些行并查看您的方法在第二次调用时是否按预期工作。

于 2010-01-06T13:15:58.617 回答
0

尽管我没有看到线程的痕迹，但这对我来说确实是线程问题。您是否尝试使用同步集合来检查行为是否相同？

于 2010-01-06T13:44:28.490 回答