java - How can I prevent mutation of a list of iterators?

Question

I would like to avoid the mutation of the input list of iterators tests by others. I only want others to run on a deep copy of tests.

How can this be achieved in Java?

Here is an example showing the effect of the mutation on tests. Both of the two parts are sorting the input. But the second part has nothing to be sorted since the mutation from the first part iterated the iterators to the end.

You can run the following example online here: https://onlinegdb.com/NC4WzLzmt

import java.util.*;

public class ImmutableExample {
    public static void main(String[] args) {

        System.out.println("sort on demand");

        List<Iterator<Integer>> mutableTests = Arrays.asList(
                Arrays.asList(1, 2).iterator(),
                Arrays.asList(0).iterator(),
                Collections.emptyIterator()
        );

        List<Iterator<Integer>> tests = Collections.unmodifiableList(mutableTests);

        MergingIterator mergingIterator = new MergingIterator(tests);
        while (mergingIterator.hasNext()) {
            System.out.println(mergingIterator.next());
        }

        System.out.println("sort all at once");

        /*       uncomment the following will see the same result:*/
//        tests = Arrays.asList(
//                Arrays.asList(1, 2).iterator(),
//                Arrays.asList(0).iterator(),
//                Collections.emptyIterator()
//        );

        MergeKSortedIterators sol = new MergeKSortedIterators();
        Iterable<Integer> result = sol.mergeKSortedIterators(tests);

        for (Integer num : result) {
            System.out.println(num);
        }


    }
}

class PeekingIterator implements Iterator<Integer>, Comparable<PeekingIterator> {
    Iterator<Integer> iterator;
    Integer peekedElement;
    boolean hasPeeked;

    public PeekingIterator(Iterator<Integer> iterator) {
        this.iterator = iterator;
    }


    public boolean hasNext() {
        return hasPeeked || iterator.hasNext();
    }

    public Integer next() {
        int nextElem = hasPeeked ? peekedElement : iterator.next();
        hasPeeked = false;
        return nextElem;
    }

    public Integer peek() {
        peekedElement = hasPeeked ? peekedElement : iterator.next();
        hasPeeked = true;
        return peekedElement;
    }

    @Override
    public int compareTo(PeekingIterator that) {
        return this.peek() - that.peek();
    }


}


class MergingIterator implements Iterator<Integer> {
    Queue<PeekingIterator> minHeap;

    public MergingIterator(List<Iterator<Integer>> iterators) {
//        minHeap = new PriorityQueue<>((x, y) -> x.peek().compareTo(y.peek()));
        minHeap = new PriorityQueue<>();
        for (Iterator<Integer> iterator : iterators) {
            if (iterator.hasNext()) {
                minHeap.offer(new PeekingIterator(iterator));
            }
        }
    }

    public boolean hasNext() {
        return !minHeap.isEmpty();
    }

    public Integer next() {
        PeekingIterator nextIter = minHeap.poll();
        Integer next = nextIter.next();
        if (nextIter.hasNext()) {
            minHeap.offer(nextIter);
        }
        return next;
    }
}

class MergeKSortedIterators {


    public Iterable<Integer> mergeKSortedIterators(List<Iterator<Integer>> iteratorList) {
        List<Integer> result = new ArrayList<>();
        if (iteratorList.isEmpty()) {
            return result;
        }

        PriorityQueue<PeekingIterator> pq = new PriorityQueue<>();

        for (Iterator<Integer> iterator : iteratorList) {
            if (iterator.hasNext()) {
                pq.add(new PeekingIterator(iterator));
            }
        }

        while (!pq.isEmpty()) {
            PeekingIterator curr = pq.poll();
//            result.add(curr.peek());
// cannot use this one as hasNext() checks on `hasPeeked`
            result.add(curr.next());
            if (curr.hasNext()) {
                pq.add(curr);
            }
        }

        return result;
    }


}

Answer 1

This question seems to be based on a misunderstanding ... or two.

How can I prevent mutation of a list of iterators?

You need to distinguish between the mutability of a list, and the mutability of the items in the list. I think you are actually asking about the latter. (And as such, the list is not really relevant to the question. As we shall see.)

I would like to avoid the mutation of the input list of iterators tests by others.

Again, you appear to be asking about the list, but I think you actually mean to ask about the iterators.

I only want others to run on a deep copy of tests.

This implies you want the iterators to be immutable.

Here's the problem:

• An Iterator is an inherently stateful / mutable object. Indeed, there is no way to implement next() without mutating the iterator object.

• Iterator objects are typically not deep copyable. They typically don't support clone() or public constructors, and they typically do not implement Serializable. (Indeed, if they were serializable, the semantics of serialize / deserialize would be problematic.)

So basically, your idea of a list of immutable iterators or a list that (somehow) produces deep copies of iterators is not practical.

---

You commented:

So List<Iterator<Integer>> tests = Collections.unmodifiableList(mutableTests); cannot produce an unmodifiable list for List<Iterator<Integer>>?

Well, yes it can. But that doesn't solve the problem. You need a list of unmodifiable iterators rather than an unmodifiable list of iterators.

---

Possible solutions:

1. You could just recreate the list of iterators from their base collections for each test run.

2. Use Iterable instead of Iterator. The collection types you are using all implement Iterable, and the third iterator could be created from an empty list.

   List<Iterable<Integer>> tests = Arrays.asList(
           Arrays.asList(1, 2),
           Arrays.asList(0),
           Collections.emptyList()
   );
   
   // to use them ...
   
   for (Iterable<Integer> iterable : tests) {
       Iterator<Integer> iterator = iterable.iterator();
       // etc ...
   }
   

3. If your iterators could not be recreated (for example, if you were iterating a source that couldn't be created or "rewound"), you could conceivably implement a caching iterator wrapper that remembered all of the elements in the iteration sequence and could either reset to the start of the sequence, or generate a new iterator to replay the sequence. (But that would be overkill here.)