1
\$\begingroup\$

The VisitedCollection is a collection wrapper for setting and tracking if elements were visited (removed in terms of the wrapper)

I have concerns regarding:

  • should equals and hashCode throw ConcurrentModificationException is underlying collection is changed
  • is it ok that visiting is performed by Iterator.remove() method? Another option might be to introduce a new VisitedIterator interface with a special method for visiting (e.g. VisitedIterator.setVisited()).
  • current implementation allows "removing" an element multiple times without throwing any errors. Does it break the Iterator contract?
  • is the name VisitedCollection self-explanatory enough :-)
package io.github.hextriclosan.algorithm.collections;

import java.io.Serializable;
import java.util.AbstractCollection;
import java.util.Arrays;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Objects;

public class VisitedCollection<E> extends AbstractCollection<E> implements Serializable {

    private static final long serialVersionUID = -1308309959111972266L;
    private static final int SIZE = Long.SIZE;

    private final Collection<? extends E> collection;
    private final long[] index;
    private int visitedCount;
    private final int underlyingCollectionExpectedSize;

    public VisitedCollection(Collection<? extends E> collection) {
        Objects.requireNonNull(collection, "collection");
        this.collection = collection;
        this.index = new long[(collection.size() + SIZE - 1) / SIZE];
        underlyingCollectionExpectedSize = collection.size();
    }

    @Override
    public int size() {
        checkConsistency();
        return collection.size() - visitedCount;
    }

    @Override
    public boolean isEmpty() {
        checkConsistency();
        return visitedCount == collection.size();
    }

    @Override
    public Iterator<E> iterator() {
        checkConsistency();
        return new Itr();
    }

    @Override
    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }

        if (o == null || getClass() != o.getClass()) {
            return false;
        }

        VisitedCollection<?> that = (VisitedCollection<?>) o;
        return collection.equals(that.collection) && Arrays.equals(index, that.index);
    }

    @Override
    public int hashCode() {
        int result = Objects.hash(collection);
        result = 31 * result + Arrays.hashCode(index);

        return result;
    }

    private void setVisited(int pos) {
        int i = pos / SIZE;
        int offset = pos % SIZE;

        index[i] |= 1L << offset;
        ++visitedCount;
        checkConsistency();
    }

    private boolean isVisited(int pos) {
        int i = pos / SIZE;
        int offset = pos % SIZE;

        checkConsistency();
        return (index[i] & (1L << offset)) != 0;
    }

    private void checkConsistency() {
        if (underlyingCollectionExpectedSize != collection.size()) {
            throw new ConcurrentModificationException();
        }
    }

    private class Itr implements Iterator<E> {

        final Iterator<? extends E> it;
        E element;
        int counter;
        int lastReturnedPos = -1;
        int expectedVisitedCount = visitedCount;

        Itr() {
            it = collection.iterator();
            computeNext();
        }

        @Override
        public boolean hasNext() {
            return element != null;
        }

        @Override
        public E next() {
            checkForComodification();
            lastReturnedPos = counter - 1;
            final E current = element;
            computeNext();

            return current;
        }

        @Override
        public void remove() {
            if (lastReturnedPos < 0) {
                throw new IllegalStateException();
            }
            checkForComodification();


            VisitedCollection.this.setVisited(lastReturnedPos);
            expectedVisitedCount = visitedCount;
        }

        private void computeNext() {
            while (it.hasNext()) {
                E next = it.next();
                if (!VisitedCollection.this.isVisited(counter++)) {
                    element = next;
                    return;
                }
            }

            element = null;
        }

        final void checkForComodification() {
            if (visitedCount != expectedVisitedCount) {
                throw new ConcurrentModificationException();
            }
        }
    }

}

ADDED

VisitedCollection is an auxiliary class for SamplingIterator. On each iteration, this iterator randomly selects n elements from the collection preserving stable order until the entire collection is processed.

package io.github.hextriclosan.algorithm.iterators;

import io.github.hextriclosan.algorithm.collections.VisitedCollection;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;
import java.util.Random;

public class SamplingIterator<E> implements Iterator<List<E>> {

    private final Collection<? extends E> collection;
    private final int sampleSize;
    private final Random random;

    private List<E> nextSample;

    public SamplingIterator(Collection<? extends E> collection, int sampleSize, Random random) {
        validate(collection, sampleSize, random);
        this.collection = new VisitedCollection<>(collection);
        this.sampleSize = sampleSize;
        this.random = random;

        sample();
    }

    @Override
    public boolean hasNext() {
        return nextSample != null && !nextSample.isEmpty();
    }

    @Override
    public List<E> next() {
        final List<E> result = nextSample;
        sample();

        return result;
    }

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

    private void sample() {
        Iterator<? extends E> iterator = collection.iterator();
        int size = collection.size();
        int n = Math.min(sampleSize, collection.size());
        ArrayList<E> arrayList = new ArrayList<>(n);
        while (n > 0 && iterator.hasNext()) {
            int r = random.nextInt(size--);
            E next = iterator.next();
            if (r < n) {
                arrayList.add(next);
                iterator.remove();
                --n;
            }
        }

        nextSample = arrayList;
    }

    private void validate(Collection<? extends E> collection, int sampleSize, Random random) {
        Objects.requireNonNull(collection, "collection");
        Objects.requireNonNull(random, "random");
        if (sampleSize <= 0) {
            throw new IllegalArgumentException();
        }
    }
}

Possible usage:

var samplingIterator = 
    new SamplingIterator<>(List.of('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'), 3, new Random());
samplingIterator.forEachRemaining(System.out::println);
// prints out, for instance
// [B, C, H]
// [E, F, G]
// [A, D]
\$\endgroup\$
4
  • \$\begingroup\$ What is the point of this? The underlying collection is expected to not change. You want multiple passes through a collection using an iterator, and only processing some elements each pass? Why not just use a Set to track what has already been processed? \$\endgroup\$
    – Eric Stein
    Sep 11, 2022 at 17:37
  • \$\begingroup\$ And yes, this code is clearly breaking the contract of Iterator#remove. "Removes from the underlying collection the last element returned by this iterator". \$\endgroup\$
    – Eric Stein
    Sep 11, 2022 at 17:40
  • \$\begingroup\$ I don't think this is reviewable without more context - specifically, what are the requirements for this code - what specific problem is it trying to solve. Perhaps show us some expected usages? \$\endgroup\$
    – Eric Stein
    Sep 11, 2022 at 17:54
  • \$\begingroup\$ @EricStein thank you for your comments. I've added more context with usage example \$\endgroup\$
    – triclosan
    Sep 12, 2022 at 13:55

1 Answer 1

2
\$\begingroup\$

Ok, I'm going to review SamplingIterator instead, because I think that VisitedCollection is a bad path to be on. It appears to exist only to vend its iterator, which is broken in a few ways (incorrectly implements the interface, doesn't properly check consistency) and is a very convoluted way of shuffling a collection and iterating over the results.

The validate method is small enough to be folded back into the constructor. It's easier on the reader to see the validation inline instead of having to jump someplace else to see the invariants.

The sample method is effectively locating a random element in the underlying collection. The VisitedCollection class is intended to prevent sampling an element more than once. This work is not necessary, because we already have a data structure (a List with the order randomized) which will give you these properties.

I feel like this code is toeing the line in terms of whether it honors the intent of the Iterator contract. I do not think Iterators are intended to change the type of the collection they're iterating over (E -> List). I would consider a helper method, or perhaps a classSampledCollection.

I don't see the value in making SamplingIterator blow up with a ConcurrentModificationException if the underlying collection changes. I think it would be preferable to just take a snapshot of a collection and build a sampling from that.

If the code were reworked to replace VisitedCollection with a shuffled list, it might look more like:

public final class SamplingIterator<E> implements Iterator<List<E>> {

    private final List<? extends E> shuffledCollection;
    private final int sampleSize;

    public SamplingIterator(Collection<? extends E> collection, int sampleSize, Random random) {
        Objects.requireNonNull(collection, "collection");
        Objects.requireNonNull(random, "random");
        if (sampleSize <= 0) {
            throw new IllegalArgumentException();
        }
        
        this.shuffledCollection = new ArrayList<>(collection);
        Collections.shuffle(shuffledCollection, random);
        this.sampleSize = sampleSize;
    }

    @Override
    public boolean hasNext() {
        return !shuffledCollection.isEmpty();
    }

    @Override
    public List<E> next() {
        if (shuffledCollection.isEmpty()) {
            throw new NoSuchElementException();
        }
            
        List<E> result = new ArrayList<>();
        int resultSize = Math.min(sampleSize, shuffledCollection.size());
        for (int i = 0; i < resultSize; i++) {
            result.add(shuffledCollection.remove(0));
        }

        return result;
    }

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

A static factory version might look like:

public final class Sampling {


    public static <E> List<List<E>> of(Collection<? extends E> collection, int sampleSize, Random random) {
        Objects.requireNonNull(collection, "collection");
        Objects.requireNonNull(random, "random");
        if (sampleSize <= 0) {
            throw new IllegalArgumentException();
        }
        
        List<List<E>> resultList = new ArrayList<>();
        List<? extends E> shuffledCollection = new ArrayList<>(collection);
        Collections.shuffle(shuffledCollection, random);
        
        while (!shuffledCollection.isEmpty()) {
            List<E> result = new ArrayList<>();
            int resultSize = Math.min(sampleSize, shuffledCollection.size());
            for (int i = 0; i < resultSize; i++) {
                result.add(shuffledCollection.remove(0));
            }
            resultList.add(result);  
        }
        
        return resultList;
    }
}

Depending on what other properties and methods a Sampling might have, it could also make sense to make a single Sample be its own class, and to instead be generating a List<Sample<E>> .

\$\endgroup\$
3
  • \$\begingroup\$ ArrayList.remove(0) is expensive. You could instead track the index of the last used value and work with that. \$\endgroup\$
    – janos
    Sep 15, 2022 at 14:33
  • \$\begingroup\$ @janos I think as written it's easier to read, which I usually prefer. Given that this is apparently a library class with external clients, I agree that either indexing or a LinkedList would be preferable. \$\endgroup\$
    – Eric Stein
    Sep 15, 2022 at 23:11
  • \$\begingroup\$ Thank you for the review. I also considered the approach you propose but choose another in the favor of making iterator lazy \$\endgroup\$
    – triclosan
    Sep 16, 2022 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.