001package squidpony.squidmath;
002
003/**
004 * Based on <a href="http://extremelearning.com.au/isotropic-blue-noise-point-sets/">Martin Roberts' blog post about
005 * blue noise point sets</a>, this class generates "balanced" permutations of a specific size with good performance.
006 */
007public class BalancedPermutations {
008        public final int size;
009        private final int halfSize;
010        private final int[] delta, targets;
011        /**
012         * Can be any long.
013         */
014        private long stateA;
015        /**
016         * Must be odd.
017         */
018        private long stateB;
019
020        public BalancedPermutations(){
021                this(16,
022                                (long) ((Math.random() - 0.5) * 0x10000000000000L)
023                                                ^ (long) (((Math.random() - 0.5) * 2.0) * 0x8000000000000000L),
024                                (long) ((Math.random() - 0.5) * 0x10000000000000L)
025                                                ^ (long) (((Math.random() - 0.5) * 2.0) * 0x8000000000000000L));
026        }
027        public BalancedPermutations(int size, long stateA, long stateB)
028        {
029                this.size = size;
030                this.halfSize = size >>> 1;
031                delta = new int[size];
032                targets = new int[size];
033                this.stateA = stateA;
034                this.stateB = stateB | 1;
035        }
036
037        /**
038         * It's a weird RNG. Returns a slightly-biased pseudo-random int between 0 inclusive and bound exclusive. The bias comes from
039         * not completely implementing Daniel Lemire's fastrange algorithm, but it should only be relevant for huge bounds. The number
040         * generator itself passes PractRand without anomalies, has a state size of 127 bits, and a period of 2 to the 127.
041         * This generator will probably be added to SquidLib as "GearRNG."
042         * @param bound upper exclusive bound
043         * @return an int between 0 (inclusive) and bound (exclusive)
044         */
045        private int nextIntBounded (int bound) {
046                final long s = (stateA += 0xC6BC279692B5C323L);
047                final long z = ((s < 0x800000006F17146DL) ? stateB : (stateB += 0x9479D2858AF899E6L)) * (s ^ s >>> 31);
048                return (int)(bound * ((z ^ z >>> 25) & 0xFFFFFFFFL) >>> 32);
049        }
050
051        private static void swap(int[] arr, int pos1, int pos2) {
052                final int tmp = arr[pos1];
053                arr[pos1] = arr[pos2];
054                arr[pos2] = tmp;
055        }
056
057        /**
058         * Fisher-Yates and/or Knuth shuffle, done in-place on an int array.
059         * @param elements will be modified in-place by a relatively fair shuffle
060         */
061        private void shuffleInPlace(int[] elements) {
062                final int size = elements.length;
063                for (int i = size; i > 1; i--) {
064                        swap(elements, i - 1, nextIntBounded(i));
065                }
066        }
067
068        /**
069         * Fills {@code items} with a balanced permutation from 0 to {@code size - 1}. The length of {@code items} must be
070         * at least {@code size}. This may take a while if size is large; half a second is reasonable for when size is 48,
071         * with smaller sizes taking much less time and larger ones taking much more.
072         * @param items an int array which will be modified in-place
073         */
074        public void fill(final int[] items) {
075                if(items == null || items.length < size) return;
076                BIG_LOOP:
077                while (true) {
078                        for (int i = 0; i < halfSize; i++) {
079                                delta[i] = i + 1;
080                                delta[i + halfSize] = ~i;
081                        }
082                        shuffleInPlace(delta);
083                        for (int i = 0; i < size; i++) {
084                                targets[i] = i;
085                        }
086                        targets[items[0] = nextIntBounded(size)] = -1;
087                        for (int i = 1; i < size; i++) {
088                                int d = 0;
089                                for (int j = 0; j < size; j++) {
090                                        d = delta[j];
091                                        if (d == 0) continue;
092                                        int t = items[i - 1] + d;
093                                        if (t >= 0 && t < size && targets[t] != -1) {
094                                                items[i] = t;
095                                                targets[t] = -1;
096                                                delta[j] = 0;
097                                                break;
098                                        } else d = 0;
099                                }
100                                if (d == 0) continue BIG_LOOP;
101                        }
102                        int d = items[0] - items[size - 1];
103                        for (int j = 0; j < size; j++) {
104                                if (d == delta[j]) {
105                                        return; // found a valid balanced permutation
106                                }
107                        }
108                }
109        }
110        
111        public GreasedRegion rotatedGrid(){
112                int size2 = size * size;
113                GreasedRegion region = new GreasedRegion(size2, size2);
114                int px, py = 0;
115                for (int x = 0; x < size; x++) {
116                        px = size - 1 + x * size;
117                        for (int y = 0; y < size; y++) {
118                                region.insert(px--, py + y * size);
119                        }
120                        py++;
121                }
122                return region;
123        }
124
125        public GreasedRegion shuffledGrid(){
126                int[] xPerm = new int[size], yPerm = new int[size];
127                fill(xPerm);
128                fill(yPerm);
129                int size2 = size * size;
130                GreasedRegion region = new GreasedRegion(size2, size2);
131                int px, py;
132                for (int x = 0; x < size; x++) {
133                        px = size - 1;
134                        py = yPerm[x];
135                        for (int y = 0; y < size; y++) {
136                                region.insert(px - xPerm[y] + xPerm[x] * size, py + yPerm[y] * size);
137                        }
138                }
139                return region;
140        }
141
142        public GreasedRegion shuffledGridMultiple(int repeats){
143                int[] xPerm = new int[size], yPerm = new int[size], rxPerm = new int[size], ryPerm = new int[size];
144                repeats = (repeats + size - 1) % size;
145                fill(xPerm);
146                fill(yPerm);
147                fill(rxPerm);
148                fill(ryPerm);
149                int size2 = size * size;
150                GreasedRegion region = new GreasedRegion(size2, size2);
151                int px, py, rx, ry;
152                for (int r = 0; r <= repeats; r++) {
153                        rx = rxPerm[r];
154                        ry = ryPerm[r];
155                        for (int x = 0; x < size; x++) {
156                                px = size - 1;
157                                py = yPerm[x];
158                                for (int y = 0; y < size; y++) {
159                                        region.insert(px - xPerm[y] + xPerm[(x + rx) % size] * size, py + yPerm[(y + ry) % size] * size);
160                                }
161                        }
162                }
163                return region;
164        }
165}