Skip to main content
Added a link to the next iteration.
Source Link
coderodde
  • 31.9k
  • 15
  • 78
  • 204

(See the next iteration here.)

(See the next iteration here.)

Became Hot Network Question
Source Link
coderodde
  • 31.9k
  • 15
  • 78
  • 204

IndexTupleIterator.java: an iterator that generates index tuples in lexicographic order, Take III

(See the previous iteration here.)

This time, I have incorporated a nice answer from Simon Forsberg.

Now, my code looks like this:

package com.github.coderodde.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.function.Consumer;

/**
 * This class implements an iterator that generates index tuples in 
 * lexicographic order.
 * 
 * @version 1.0.0
 * @since 1.0.0
 */
public final class IndexTupleIterator implements Iterator<List<Integer>>{

    /**
     * The length of the index tuples.
     */
    private final int indexTupleLength;
    
    /**
     * The length of the list for which the indices are being generated.
     */
    private final int lengthOfTargetList;
    
    /**
     * The actual internal state containing the current index tuple.
     */
    private final List<Integer> indices;
    
    /**
     * The last index tuple to iterate.
     */
    private final List<Integer> lastIndexTuple;
    
    public IndexTupleIterator(final int indexTupleLength,
                              final int lengthOfTargetList) {
        checkArguments(indexTupleLength, 
                       lengthOfTargetList);
        
        this.indexTupleLength = indexTupleLength;
        this.lengthOfTargetList = lengthOfTargetList;
        this.indices = new ArrayList<>(indexTupleLength);
        this.lastIndexTuple = new ArrayList<>(indexTupleLength);
        
        initState();
    }

    @Override
    public boolean hasNext() {
        for (int i = 0; i < lastIndexTuple.size(); ++i) {
            final Integer index1 = indices.get(i);
            final Integer index2 = lastIndexTuple.get(i);
            
            if (!index1.equals(index2)) {
                return true;
            }
        }
        
        return false;
    }

    @Override
    public List<Integer> next() {
        if (!hasNext()) {
            throw new NoSuchElementException("Nothing to iterate.");
        }
        
        if (indices.get(indices.size() - 1) < lengthOfTargetList - 1) {
            indices.set(indices.size() - 1, 
                        indices.get(indices.size() - 1) + 1);
            
            return Collections.<Integer>unmodifiableList(indices);
        }
        
        for (int i = indices.size() - 2; i >= 0; --i) {
            final Integer a = indices.get(i);
            final Integer b = indices.get(i + 1);
            
            if (a < b - 1) {
                indices.set(i, indices.get(i) + 1);
                
                for (int j = i + 1; j < indices.size(); j++) {
                    indices.set(j, indices.get(j - 1) + 1);
                }
                
                return Collections.<Integer>unmodifiableList(indices);
            }
        }
        
        throw new IllegalStateException("Should not get here.");
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException(
                "remove() is not supported in IndexTupleIterator.");
    }

    @Override
    public void forEachRemaining(Consumer<? super List<Integer>> action) {
        throw new UnsupportedOperationException(
                "forEachRemainig() is not supported in IndexTupleIterator.");
    }
    
    public static void main(String[] args) {
        int lineNumber = 1;
        
        for (final List<Integer> list : new IndexTupleIterable(3, 6)) {
            System.out.printf("%2d: %s\n", lineNumber++, list);
        }
    }
    
    private void initState() {
        // Create the initial index tuple <0, 1, ..., indexTupleLength - 1>:
        for (int i = 0; i < indexTupleLength; ++i) {
            this.indices.add(i);
        }
        
        // Create the end index tuple <>:
        for (int i = 0; i < indexTupleLength; ++i) {
            this.lastIndexTuple.add(lengthOfTargetList - indexTupleLength + i);
        }
        
        // We need this in order to generate the first index tuple:
        this.indices.set(indexTupleLength - 1,
                         this.indices.get(indexTupleLength - 1) - 1);
    }
    
    /**
     * Checks that the input arguments are sensible.
     * 
     * @param indexTupleLength   the length of the index tuple.
     * @param lengthOfTargetList the length of the list being indexed.
     */
    private static void checkArguments(final int indexTupleLength,
                                       final int lengthOfTargetList) {
        if (indexTupleLength < 1) {
            final String exceptionMessage = 
                    String.format("indexTupleLength(%d) < 1",
                                  indexTupleLength);
            
            throw new IllegalArgumentException(exceptionMessage);
        }
        
        
        if (lengthOfTargetList < 1) {
            final String exceptionMessage = 
                    String.format("lengthOfTargetList(%d) < 1",
                                  lengthOfTargetList);
            
            throw new IllegalArgumentException(exceptionMessage);
        }
        
        if (indexTupleLength > lengthOfTargetList) {
            
            final String exceptionMessage = 
                    String.format(
                            "indexTupleLength(%d) > lengthOfTargetList(%d)",                            
                            indexTupleLength,
                            lengthOfTargetList);
            
            throw new IllegalArgumentException(exceptionMessage);
        }
    }
}

As always, I am eager to hear any commentary on my attempt.