/*
 * Redberry: symbolic tensor computations.
 *
 * Copyright (c) 2010-2015:
 *   Stanislav Poslavsky   
 *   Bolotin Dmitriy       
 *
 * This file is part of Redberry.
 *
 * Redberry is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * Redberry is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Redberry. If not, see .
 */
package cc.redberry.core.combinatorics;

import cc.redberry.core.utils.BitArray;

import java.util.Arrays;

/**
 * This class represents an iterator (implemented in the output port pattern) over all distinct N-tuples, which can be
 * chosen from {@code N} sets of integers. More formally, for {@code N} integer arrays: array1,
 * array2,...,arrayN, this class allows to iterate over all possible integer arrays
 * of the form [i1, i2,...,iN], where all numbers numbers ij are different
 * and i1 is chosen from array1, i2 is chosen from array2 and
 * so on.
 
 
Consider the example:
 * 
 * int[] a1 = {1, 2, 3};
 * int[] a2 = {2, 3};
 * DistinctCombinationsPort dcp = new DistinctCombinationsPort(a1, a2);
 * int[] tuple;
 * while ((tuple = dcp.take()) != null)
 *      System.out.println(Arrays.toString(tuple));
 * 
 * This code will produce the following sequence:
 * 
 * [1, 2]
 * [1, 3]
 * [2, 3]
 * [3, 2]
 * 
 * 
 
 
This class is implemented via output port pattern and the calculation of the next tuple occurs only on
 * the invocation of {@link #take()}.
 
 
Note: method {@link #take()} returns the same reference on each
 * invocation. So, if it is needed not only to obtain the information from {@link #take()}, but also save the result, it
 * is necessary to clone the returned array.
 *
 * @author Dmitry Bolotin
 * @author Stanislav Poslavsky
 * @since 1.0
 */
public class IntDistinctTuplesPort implements IntCombinatorialPort {
    private final BitArray previousMask;
    private final BitArray[] setMasks;
    private final int[] combination;
    private final BitArray temp;
    private byte state = -1;

    public IntDistinctTuplesPort(int[]... sets) {
        int maxIndex = 0;
        for (int[] set : sets) {
            if (set.length == 0)
                continue;
            Arrays.sort(set);
            if (maxIndex < set[set.length - 1])
                maxIndex = set[set.length - 1];
        }
        ++maxIndex;
        previousMask = new BitArray(maxIndex);
        temp = new BitArray(maxIndex);

        setMasks = new BitArray[sets.length];
        for (int i = 0; i < sets.length; ++i) {
            setMasks[i] = new BitArray(maxIndex);
            for (int j : sets[i])
                setMasks[i].set(j);
        }
        combination = new int[sets.length];
        previousMask.setAll();
        init();
    }

    private void init() {
        int i = 0, nextBit;
        while (i < setMasks.length) {

            temp.loadValueFrom(setMasks[i]);
            temp.and(previousMask);

            nextBit = temp.nextBit(combination[i]);
            if (nextBit != -1) {
                combination[i] = nextBit;
                previousMask.clear(nextBit);
            } else {
                if (i == 0) {
                    state = 1;
                    return;
                }
                combination[i] = 0;
                previousMask.set(combination[--i]);
                ++combination[i];
                continue;
            }
            ++i;
        }
    }

    /**
     * Calculates and returns the next tuple, or {@code null} if no more distinct tuples exist.
     *
     * @return the next tuple, or {@code null} if no more distinct tuples exist
     */
    @Override
    public int[] take() {
        if (state == 1)
            return null;

        if (state == -1) {
            state = 0;
            return combination;
        }
        previousMask.set(combination[setMasks.length - 1]++);

        int i = setMasks.length - 1, nextBit;
        while (i < setMasks.length) {

            temp.loadValueFrom(setMasks[i]);
            temp.and(previousMask);

            nextBit = temp.nextBit(combination[i]);
            if (nextBit != -1) {
                combination[i] = nextBit;
                previousMask.clear(nextBit);
            } else {
                if (i == 0) {
                    state = 1;
                    return null;
                }
                combination[i] = 0;
                previousMask.set(combination[--i]);
                ++combination[i];
                continue;
            }
            ++i;
        }

        return combination;
    }

    @Override
    public void reset() {
        state = -1;
        Arrays.fill(combination, 0);
        previousMask.setAll();
        init();
    }

    @Override
    public int[] getReference() {
        return combination;
    }
}