偏序集迭代实现的正确性

Question

我编写了一个自定义迭代器类，它遍历在PoSet中找到的一组数字，下面是我的代码：

private class IntGenerator implements Iterator {
        private Iterator<Integer> i;
        private Set<Integer> returnedNumbers;


        public IntGenerator () {
            returnedNumbers = new HashSet<Integer> ();
            i = S.iterator();
        }

        public boolean hasNext() {
            return i.hasNext();
        }

        public Object next() {
            int n = i.next();

            for (Pair p : R) {
                if (isInSecondElmPair(p, n)) {
                    if (returnedNumbers.contains(p.getFirstElm())) {
                        returnedNumbers.add(n);
                        return n;
                    }else{
                        returnedNumbers.add(p.getFirstElm());
                        return p.getFirstElm();
                    }
                }else if (isInFirstElmPair(p, n)){
                    returnedNumbers.add(n);
                    return n;
                }
            }
            return n;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

问题是，当返回一个数字时，我应该遵守偏序规则，即: 1.如果(x，y)属于R，那么x应该在y之前返回

然而，上面的代码似乎遵循这种顺序，但它正在创建重复的代码，我如何修复我的代码以不允许它？

注意:在我的代码中，S是PoSet中的一组数字，它是一个HashSet，R是一个数组列表(pair:我创建的一个以2个整数为参数的类)来保存PoSet中的关系。

有没有办法解决这个问题？谢谢

Answer 1

您的next方法始终调用i.next()，并返回以下两种情况之一：

• i.next()返回的值
• 某个小于该值的值。

这意味着如果您的偏序集包含{ 1，2，3,4}并使用整数的自然排序，并且i.next()返回4，则要么现在返回4(由于已经返回1、2和3)，要么永远不会返回4(因为它不小于任何未来的值)。

你得到重复的原因是你为i.next()的每个值返回一个值，并且有一些值永远不会被返回(参见上一段)，所以自然会有一些值在补偿中多次返回。请注意，您从不检查从i.next()返回的值以前是否已由next()方法返回，因此如果偏序集中的某个元素不大于任何其他元素，那么当i.next()返回该元素时，next()方法将自动返回该元素，即使它以前已经返回过该元素。

我认为唯一明智的解决方法是彻底改变您的方法；我不认为您当前的方法可以很容易地工作。我认为迭代器的构造函数需要将偏序集的所有元素复制到一个可接受的有序列表中，然后next()方法将简单地返回该列表的下一个元素。或者，由于您当前的方法已经要求在每次调用next()时遍历R，因此将迭代器建立在R上的迭代器上可能更有意义。(我在这里假设R已经使用自身进行了排序；如果没有这样做，那么for循环就没有任何意义，实际上将返回随机选择的元素。)

如果您确实想坚持自己的方法，那么不仅需要跟踪next()方法返回的元素，还需要跟踪i.next()返回但next()方法没有返回的元素；您需要能够在以后返回这些元素。

此外，您的for (Pair p : R)循环不会执行您想要的操作-一旦找到任何小于已返回的n的元素，它就会自动返回n，即使还有其他小于n的元素尚未返回。(这是如果R已经使用自身订购的话。如果不是，那么这个循环就会有更大的问题。)