Poset iteration order / custom iterator implementation for a partially ordered set

Question

I am creating a partially ordered set as an abstract data type in java, and I have to make an iterator version of the set of numbers, and an iterator for the relations. Now for the elements, I've used HashSet of integer, and for the relations, I've used an ArrayList of pairs (pairs is a class I created that takes 2 ints as parameter which basically is like (x, y)). I need to make 2 iterators, one for s and one for r, but they have to follow a certain ordering, 1. if (x, y) belong to R, then the iterator of s should return x before it returns y 2. if (x, y) and (y, z) belong to R, then iterator of r should return (x, y) before it returns (y, z)

I made a helper method that check first for to check if the element n in the set is the first element in a pair then it returns it, but I cant seem to check if it is second element, how can I check for the first element if it is returned or not?

Here is my code:

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

I would really appreciate any kind of help, or hint in this code. Thanks

EDIT:

Okay, I've wrote the code to it after adding a new set which will hold the returned elements, and this is what I wrote:

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

Is this code correct? Also, eclipse seems to give me an error telling me I need to return a value outside the loop, but I already returned inside for every case why does it need more? Appreciate the help

Answer 1

Well, to check if a value was previously returned, you of course need to keep track of all values that were returned previously.

So in your iterator, you could define

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

and then, before returning it in your for loop, add it there:

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

This way, however, you are constructing a set of s in the order in which it shall be returned inside the iterator. It would make sense to create this once (consider a LinkedHashSet), keep it somewhere else and iterate over it.

Generally I am not sure that this approach will lead to what you want. Do you know anything about theorder of elements in S and R? If the iteration order is arbitrary (i.e. because relations were added in unpredictable order) then the iterator will first return the first half of the first relation pair, even if that element is in the second half of another pair. Do you have to use an element HashSet and a relation List?