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}