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}