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 copied so externally using it won't change the order this produces its values; the rng field is
060     * used whenever the iterator needs to re-shuffle the internal ordering of elements. I suggest that the RNG should
061     * use LongPeriodRNG as its RandomnessSource, since it is in general a good choice for shuffling, but since this
062     * class mostly delegates its unique-shuffling code to PermutationGenerator and looks up at most 20 elements'
063     * permutation at once (allowing it to use a single random long to generate the permutation), there probably won't
064     * be problems if you use any other RandomnessSource.
065     * @param elements a Collection of T that will not be modified
066     * @param rng an RNG that can be pre-seeded; will be copied and not used directly
067     */
068    public GapShuffler(Collection<T> elements, RNG rng)
069    {
070        this.rng = rng.copy();
071        this.elements = rng.shuffle(elements);
072        size = this.elements.size();
073        double sz2 = size;
074        index = 0;
075        int portionSize = Math.min(20, Math.max(1, size / 2));
076        int minSection = Math.min(5, size / 2 + 1);
077        while (size % portionSize < minSection && portionSize > 2)
078            portionSize--;
079        indexSections = new int[(int)Math.ceil(sz2 / portionSize)][];
080        for (int i = 0; i < indexSections.length - 1; i++) {
081            indexSections[i] = PermutationGenerator.decodePermutation(
082                    rng.nextLong(PermutationGenerator.getTotalPermutations(portionSize)), portionSize, i * portionSize);
083            sz2 -= portionSize;
084        }
085        indexSections[indexSections.length - 1] = PermutationGenerator.decodePermutation(
086                rng.nextLong(PermutationGenerator.getTotalPermutations((int)sz2)),
087                (int)sz2, (indexSections.length - 1) * portionSize);
088    }
089
090    /**
091     * Gets the next element of the infinite sequence of T this shuffles through. The same as calling next() on an
092     * iterator returned by this class' iterator() method.
093     * @return the next element in the infinite sequence
094     */
095    public T getNext() {
096        if(index >= size)
097        {
098            index = 0;
099            int build = 0, inner, rotated;
100            for (int i = 0; i < indexSections.length; i++) {
101                if(indexSections.length <= 2)
102                    rotated = (indexSections.length + 2 - i) % indexSections.length;
103                else
104                    rotated = (indexSections.length + 1 - i) % indexSections.length;
105                inner = indexSections[rotated].length;
106                indexSections[rotated] =
107                        PermutationGenerator.decodePermutation(
108                                rng.nextLong(PermutationGenerator.getTotalPermutations(inner)),
109                                inner,
110                                build);
111                build += inner;
112            }
113        }
114        int ilen = indexSections[0].length, ii = index / ilen, ij = index - ilen * ii;
115        ++index;
116        return elements.get(indexSections[ii][ij]);
117    }
118    /**
119     * Returns an <b>infinite</b> iterator over elements of type {@code T}. You should be prepared to break out of any
120     * for loops that use this once you've gotten enough elements! The remove() method is not supported by this iterator
121     * and hasNext() will always return true.
122     *
123     * @return an infinite Iterator over elements of type T.
124     */
125    @Override
126    public Iterator<T> iterator() {
127        return new GapIterator();
128    }
129
130    private class GapIterator implements Iterator<T>, Serializable
131    {
132        private static final long serialVersionUID = 3167045364623458470L;
133        private int innerIndex;
134        private RNG innerRNG;
135        GapIterator() {
136            innerIndex = 0;
137            innerRNG = rng.copy();
138        }
139        /**
140         * Returns {@code true} if the iteration has more elements.
141         * This is always the case for this Iterator.
142         *
143         * @return {@code true} always
144         */
145        @Override
146        public boolean hasNext() {
147            return true;
148        }
149
150        /**
151         * Returns the next element in the iteration.
152         *
153         * @return the next element in the iteration
154         */
155        @Override
156        public T next() {
157            if(innerIndex >= size)
158            {
159                innerIndex = 0;
160                int build = 0, inner, rotated;
161                for (int i = 0; i < indexSections.length; i++) {
162
163                    if(indexSections.length <= 2)
164                        rotated = (indexSections.length + 2 - i) % indexSections.length;
165                    else
166                        rotated = (indexSections.length + 1 - i) % indexSections.length;
167                    inner = indexSections[rotated].length;
168                    indexSections[rotated] =
169                            PermutationGenerator.decodePermutation(
170                                    innerRNG.nextLong(PermutationGenerator.getTotalPermutations(inner)),
171                                    inner,
172                                    build);
173                    build += inner;
174                }
175            }
176            int ilen = indexSections[0].length, ii = innerIndex / ilen, ij = innerIndex - ilen * ii;
177            ++innerIndex;
178            return elements.get(indexSections[ii][ij]);
179        }
180
181        /**
182         * Not supported.
183         *
184         * @throws UnsupportedOperationException always throws this exception
185         */
186        @Override
187        public void remove() {
188            throw new UnsupportedOperationException("remove() is not supported");
189        }
190    }
191}