Lazy Cartesian Product

CartesianProduct.java

package org.zuchini.examples.parallel;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

import static java.util.Arrays.asList;

public final class CartesianProduct<T> implements Iterable<List<Object>> {

    static class CartesianProductIterator implements Iterator<List<Object>> {
        private final Object[][] dimensions;
        private final int length;
        private final int[] indizes;

        private boolean reachedMax;

        CartesianProductIterator(final Object[][] dimensions) {
            this.dimensions = dimensions;
            this.length = dimensions.length;
            this.indizes = new int[length];
        }

        private void increment(final int index) {
            if (index >= length) {
                reachedMax = true;
            } else {
                indizes[index]++;
                if (indizes[index] == dimensions[index].length) {
                    indizes[index] = 0;
                    increment(index + 1);
                }
            }
        }

        private void increment() {
            increment(0);
        }

        @Override
        public List<Object> next() {
            if (reachedMax) {
                throw new NoSuchElementException();
            } else {
                List<Object> list = new ArrayList<>();
                for (int i = 0; i < length; i++) {
                    list.add(dimensions[i][indizes[i]]);
                }

                increment();

                return Collections.unmodifiableList(list);
            }
        }

        @Override
        public boolean hasNext() {
            return !reachedMax;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Remove not supported");
        }

    }

    private final Object[][] dimensions;
    private final long size;

    private CartesianProduct(final List<Set<T>> axes) {
        Object[][] dimensions = new Object[axes.size()][];
        long size = dimensions.length == 0 ? 0 : 1;
        for (int i = 0; i < axes.size(); i++) {
            dimensions[i] = axes.get(i).toArray();
            size *= dimensions[i].length;
        }
        this.dimensions = dimensions;
        this.size = size;
    }

    public static <T> Iterable<List<Object>> cartesianProduct(final List<Set<T>> axes) {
        return new CartesianProduct<>(axes);
    }

    public static <T> Stream<List<Object>> cartesianProductStream(final List<Set<T>> axes) {
        return new CartesianProduct<>(axes).stream();
    }

    @Override
    public Iterator<List<Object>> iterator() {
        if (size == 0) {
            return Collections.emptyListIterator();
        }

        return new CartesianProductIterator(dimensions);
    }

    public Stream<List<Object>> stream() {
        int characteristics = Spliterator.ORDERED | Spliterator.SIZED | Spliterator.IMMUTABLE;
        return StreamSupport.stream(Spliterators.spliterator(iterator(), size, characteristics), false);
    }

    @SafeVarargs
    private static <E> Set<E> asSet(E... args) {
        return new LinkedHashSet<>(asList(args));
    }

    public static void main(String[] args) {
        for (List<Object> objects : cartesianProduct(asList(
                asSet("1", "2", "3"),
                asSet("a", "b", "c"),
                asSet("A", "B", "C")))) {
            System.out.println(objects);
        }

        System.out.println();
        System.out.println();

        cartesianProductStream(asList(
                asSet("1", "2", "3"),
                asSet("a", "b", "c"),
                asSet("A", "B", "C"))).forEach(System.out::println);
    }

}