001package squidpony.squidmath;
002
003import java.io.Serializable;
004import java.util.ArrayList;
005import java.util.Collection;
006import java.util.Iterator;
007
008/**
009 * Meant to take a fixed-size set of items and produce a shuffled stream of them such that an element is never chosen in
010 * quick succession; that is, there should always be a gap between the same item's occurrences. This is an Iterable of
011 * T, not a Collection, because it can iterate without stopping, infinitely, unless you break out of a foreach loop that
012 * iterates through one of these, or call the iterator's next() method only a limited number of times. Collections have
013 * a size that can be checked, but Iterables can be infinite (and in this case, this one is).
014 * Created by Tommy Ettinger on 5/21/2016.
015 * @param <T> the type of items to iterate over; ideally, the items are unique
016 */
017public class GapShuffler<T> implements Iterable<T>, Serializable {
018    private static final long serialVersionUID = 1277543974688106290L;
019    public RNG rng;
020    private ArrayList<T> elements;
021    private int size, index;
022    private int[][] indexSections;
023    private GapShuffler() {}
024
025    /**
026     * Constructor that takes any Collection of T, shuffles it with an unseeded RNG, and can then iterate infinitely
027     * through mostly-random shuffles of the given collection. These shuffles are spaced so that a single element should
028     * always have a large amount of "gap" in order between one appearance and the next. It helps to keep the appearance
029     * of a gap if every item in elements is unique, but that is not necessary and does not affect how this works.
030     * @param elements a Collection of T that will not be modified
031     */
032    public GapShuffler(Collection<T> elements)
033    {
034        rng = new RNG(new LongPeriodRNG());
035        this.elements = rng.shuffle(elements);
036        size = this.elements.size();
037        double sz2 = size;
038        index = 0;
039        int portionSize = Math.min(20, Math.max(1, size / 2));
040        int minSection = Math.min(5, size / 2 + 1);
041        while (size % portionSize < minSection && portionSize > 2)
042            portionSize--;
043        indexSections = new int[(int)Math.ceil(sz2 / portionSize)][];
044        for (int i = 0; i < indexSections.length - 1; i++) {
045            indexSections[i] = PermutationGenerator.decodePermutation(
046                    rng.nextLong(PermutationGenerator.getTotalPermutations(portionSize)), portionSize, i * portionSize);
047            sz2 -= portionSize;
048        }
049        indexSections[indexSections.length - 1] = PermutationGenerator.decodePermutation(
050                rng.nextLong(PermutationGenerator.getTotalPermutations((int)sz2)),
051                (int)sz2, (indexSections.length - 1) * portionSize);
052    }
053
054    /**
055     * Constructor that takes any Collection of T, shuffles it with the given RNG, and can then iterate infinitely
056     * through mostly-random shuffles of the given collection. These shuffles are spaced so that a single element should
057     * always have a large amount of "gap" in order between one appearance and the next. It helps to keep the appearance
058     * of a gap if every item in elements is unique, but that is not necessary and does not affect how this works. The
059     * rng parameter is used directly (not copied), and is also used whenever the iterator needs to re-shuffle the
060     * internal ordering of elements. I suggest that the RNG should use LongPeriodRNG as its RandomnessSource, since it
061     * is in general a good choice for shuffling, but since this class mostly delegates its unique-shuffling code to
062     * PermutationGenerator and looks up at most 20 elements' permutation at once (allowing it to use a single random
063     * long to generate the permutation), there probably won't be problems if you use any other RandomnessSource.
064     * @param elements a Collection of T that will not be modified
065     * @param rng an RNG that can be pre-seeded; will be directly used and not copied
066     */
067    public GapShuffler(Collection<T> elements, RNG rng)
068    {
069        this.rng = rng;
070        this.elements = rng.shuffle(elements);
071        size = this.elements.size();
072        double sz2 = size;
073        index = 0;
074        int portionSize = Math.min(20, Math.max(1, size / 2));
075        int minSection = Math.min(5, size / 2 + 1);
076        while (size % portionSize < minSection && portionSize > 2)
077            portionSize--;
078        indexSections = new int[(int)Math.ceil(sz2 / portionSize)][];
079        for (int i = 0; i < indexSections.length - 1; i++) {
080            indexSections[i] = PermutationGenerator.decodePermutation(
081                    rng.nextLong(PermutationGenerator.getTotalPermutations(portionSize)), portionSize, i * portionSize);
082            sz2 -= portionSize;
083        }
084        indexSections[indexSections.length - 1] = PermutationGenerator.decodePermutation(
085                rng.nextLong(PermutationGenerator.getTotalPermutations((int)sz2)),
086                (int)sz2, (indexSections.length - 1) * portionSize);
087    }
088
089    /**
090     * Returns an <b>infinite</b> iterator over elements of type {@code T}. You should be prepared to break out of any
091     * for loops that use this once you've gotten enough elements!
092     *
093     * @return an infinite Iterator over elements of type T.
094     */
095    @Override
096    public Iterator<T> iterator() {
097        return new GapIterator();
098    }
099
100    /**
101     *
102     */
103    public class GapIterator implements Iterator<T>, Serializable
104    {
105        private static final long serialVersionUID = 3167045364623458470L;
106        GapIterator() {}
107        /**
108         * Returns {@code true} if the iteration has more elements.
109         * This is always the case for this Iterator.
110         *
111         * @return {@code true} always
112         */
113        @Override
114        public boolean hasNext() {
115            return true;
116        }
117
118        /**
119         * Returns the next element in the iteration.
120         *
121         * @return the next element in the iteration
122         */
123        @Override
124        public T next() {
125            if(index >= size)
126            {
127                index = 0;
128                int build = 0, inner, rotated;
129                for (int i = 0; i < indexSections.length; i++) {
130                    rotated = (indexSections.length + 1 - i) % indexSections.length;
131                    inner = indexSections[rotated].length;
132                    indexSections[rotated] =
133                            PermutationGenerator.decodePermutation(
134                            rng.nextLong(PermutationGenerator.getTotalPermutations(inner)),
135                            inner,
136                            build);
137                    build += inner;
138                }
139            }
140            int ilen = indexSections[0].length, ii = index / ilen, ij = index - ilen * ii;
141            ++index;
142            return elements.get(indexSections[ii][ij]);
143        }
144
145        /**
146         * Not supported.
147         *
148         * @throws UnsupportedOperationException always throws this exception
149         */
150        @Override
151        public void remove() {
152            throw new UnsupportedOperationException("remove() is not supported");
153        }
154    }
155}