правильность реализации итерации poset - PullRequest
Новая
       16

правильность реализации итерации poset

0 голосов
/ 23 марта 2012

Я написал собственный класс итераторов, который выполняет итерацию по набору чисел, найденных в 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 - массив пар (пара: класс, который я создалдля хранения отношений в PoSet требуется 2 дюйма (param).

Есть ли способ решить эту проблему?Спасибо

1 Ответ

2 голосов
/ 23 марта 2012

Ваш метод next всегда вызывает i.next() и возвращает одну из двух вещей:

  • значение, которое i.next() вернуло
  • некоторое значение, которое меньше этого значения.

Это означает, что если ваш набор содержит {1,2,3,4} и использует естественный порядок целых чисел, а i.next() возвращает 4, то либо вы возвращаете 4 , теперь (из-за 1 , 2 и 3 уже были возвращены), или вы никогда не вернете 4 (потому что это не меньше, чем любое будущее значение).

Причина, по которой вы получаете дубликаты, состоит в том, что вы возвращаете одно значение для каждого значения i.next(), и есть некоторые значения, которые никогда не возвращаются (см. Предыдущий абзац), поэтому, естественно, есть некоторые значения, которые возвращаются несколько раз в компенсацию. Обратите внимание, что вы никогда не проверяете, возвращалось ли ранее значение, возвращенное из i.next(), вашим методом next(), поэтому, если элемент в наборе не больше, чем любой другой элемент, то когда i.next() возвращает этот элемент, ваш * Метод 1023 * автоматически вернет его, даже если он ранее его возвратил.

Я думаю, что единственное разумное решение для этого - полностью изменить ваш подход; Я не думаю, что ваш нынешний подход можно легко заставить работать. Я думаю, что конструктор вашего итератора должен скопировать все элементы poset в приемлемо упорядоченный список, а затем метод next() просто вернет следующий элемент этого списка. Или, в качестве альтернативы, поскольку ваш текущий подход уже требует итерации по R при каждом вызове next() , в любом случае , возможно, имеет больше смысла основывать ваш итератор на итераторе по R. (Я предполагаю, что R уже упорядочен с использованием самого себя; если это не так, тогда ваш цикл for не имеет никакого смысла и будет по существу возвращать случайно выбранные элементы.)

Если вы действительно хотите придерживаться своего подхода, то вам нужно отслеживать не только элементы, которые ваш next() метод возвратил , но также и элементы, которые i.next() возвращено, но ваш next() метод не return; вам нужно будет вернуть эти элементы позже.

Кроме того, ваш цикл for (Pair p : R) не делает то, что вы хотите & mdash; он автоматически возвращает n, как только находит любой элемент , который меньше, чем n, который уже был возвращен, , даже если есть другие элементы, отличные от n, которые не были вернулся еще . (Это если R уже заказан, используя себя. Если это не , то у этого цикла есть еще большие проблемы.)

...