dj5 dj5 - 1 month ago 16
Java Question

Merging Lists with a PushbackIterator?

I have to use a

PushbackIterator
which uses a
pushback(E)
method.

So if the value in
aIter
is less than the value in
bIter
,
aIter
is returned, while the value in
bIter
is put into the
pushback(E)
method, and vice versa.

If the original lists are


(1, 4, 5) and (2, 3, 6)


then the result list would be


(1, 2, 3, 4, 5, 6)


.

I believe that I need to determine if an iterator has no values left. So if bIter has no more elements, I get an element from aIter and add it to the result list.

How would I determine if an iterator has no more values?

public static<E extends Comparable<E>> List<E> mergeSortedLists(List<E> a, List<E> b) {
List<E> result = new ArrayList<E>();

PushbackIterator<E> aIter = new PushbackIterator<E>(a.iterator());
PushbackIterator<E> bIter = new PushbackIterator<E>(b.iterator());

while (aIter.hasNext() && bIter.hasNext()) {
if (aIter.next().compareTo(bIter.next()) < 0) {
result.add(aIter.next());
aIter.pushback(bIter.next());
}
if (aIter.next().compareTo(bIter.next()) > 0)
result.add(bIter.next());
bIter.pushback(aIter.next());
}

return result;
}

Answer

The while terminates if one of the iterators has no more elements, thus afterwards you can just add the remaining elements of the iterators:

while (aIter.hasNext()) {
    result.add(aIter.next());
}
while (bIter.hasNext()) {
    result.add(bIter.next());
}

Btw, your code has some flaws since you call .next() multiple times before adding an element. Because of this you will skip elements. Try this:

public static<E extends Comparable<E>> List<E> mergeSortedLists(List<E> a, List<E> b) {
    List<E> result = new ArrayList<E>();

    PushbackIterator<E> aIter = new PushbackIterator<E>(a.iterator());
    PushbackIterator<E> bIter = new PushbackIterator<E>(b.iterator());

    while (aIter.hasNext() && bIter.hasNext()) {
        E aElem = aIter.next();
        E bElem = bIter.next();
        if (aElem.compareTo(bElem) <= 0) {
            result.add(aElem);
            bIter.pushback(bElem);
        } else {
            result.add(bElem);
            aIter.pushback(aElem);
        }
    }

    while (aIter.hasNext()) {
        result.add(aIter.next());
    }
    while (bIter.hasNext()) {
        result.add(bIter.next());
    }

    return result;
}