java - 部分有序集的 Poset 迭代顺序/自定义迭代器实现

Question

我正在创建一个部分有序集作为java中的抽象数据类型，并且我必须创建该数字集的迭代器版本以及关系的迭代器。现在对于元素，我使用了整数的 HashSet，对于关系，我使用了对的 ArrayList(对是我创建的一个类，它采用 2 个整数作为参数，基本上类似于 (x, y))。我需要创建 2 个迭代器，一个用于 s，一个用于 r，但它们必须遵循一定的顺序， 1. 如果(x, y)属于R，那么s的迭代器应该在返回y之前返回x 2. 如果(x, y)和(y, z)属于R，那么r的迭代器应该在返回(y, z)之前返回(x, y)

我创建了一个辅助方法，首先检查集合中的元素 n 是否是一对中的第一个元素，然后返回它，但我似乎无法检查它是否是第二个元素，如何检查第一个元素是否返回？

这是我的代码:

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


        public IntGenerator () {
            i = S.iterator();
        }

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

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

            for (Pair p : R) {
                if (isInFirstElmPair(p,  n)) return n;
                else (isInSecondElmPair(p, n)) {
                                    // should check for the first element
                                    // if it was returned or not
                }
            }
        }

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

我真的很感激这段代码中的任何帮助或提示。 谢谢

编辑:

好的，在添加一个新的集合来保存返回的元素后，我已经编写了代码，这就是我写的:

Set<Integer> returnedNumbers = new HashSet<Integer> ();
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{
                    returnedNumbers.add(n);
                    return n;
                }
            }
        }

这段代码正确吗？另外，Eclipse 似乎给了我一个错误，告诉我需要在循环之外返回一个值，但我已经在每种情况下返回了内部，为什么还需要更多？ 感谢帮助

Answer 1

好吧，要检查之前是否返回了某个值，您当然需要跟踪之前返回的所有值。

所以在你的迭代器中，你可以定义

Set<Integer> previouslyReturned = new HashSet<Integer>();

然后，在将其返回到 for 循环中之前，将其添加到此处:

if (isInFirstElmPair(p,  n)) {
    previouslyReturned.add(n);
    return n;
}
else (isInSecondElmPair(p, n)) {
    if (previouslyReturned.contains(n) {
        // do one thing
    } else {
        // do another thing
    }
}

但是，通过这种方式，您可以按照迭代器内返回的顺序构造一组 s。创建一次(考虑一个 LinkedHashSet)，将其保存在其他地方并迭代它是有意义的。

一般来说，我不确定这种方法是否会达到您想要的效果。你知道S和R中元素的顺序吗？如果迭代顺序是任意的(即因为关系是以不可预测的顺序添加的)，则迭代器将首先返回第一个关系对的前半部分，即使该元素位于另一关系对的后半部分中。您必须使用元素HashSet和关系列表吗？