001
002/*******************************************************************************
003 * Copyright 2011 See AUTHORS file.
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * You may obtain a copy of the License at
008 *
009 *   http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 ******************************************************************************/
017
018package squidpony.squidmath;
019
020import java.io.Serializable;
021import java.util.NoSuchElementException;
022
023/** An unordered set that uses short keys. This implementation uses cuckoo hashing using 3 hashes, random walking, and a
024 * small stash for problematic keys. No allocation is done except when growing the table size. Used internally by
025 * CoordPacker, and unlikely to be used outside of it.
026 * <br>
027 * This set performs very fast contains and remove (typically O(1), worst case O(log(n))). Add may be a bit slower,
028 * depending on hash collisions. Load factors greater than 0.91 greatly increase the chances the set will have to rehash
029 * to the next higher POT size.
030 * @author Nathan Sweet
031 * Ported from libGDX by Tommy Ettinger on 10/19/2015.
032 */
033public class ShortSet implements Serializable{
034    private static final long serialVersionUID = -4390851800502156007L;
035
036    private static final int PRIME2 = 0xb4b82e39;
037    private static final int PRIME3 = 0xced1c241;
038    private static final short EMPTY = 0;
039
040    public int size;
041
042    short[] keyTable;
043    int capacity, stashSize;
044    boolean hasZeroValue;
045
046    private float loadFactor;
047    private int hashShift, threshold;
048    private int stashCapacity;
049    private int pushIterations;
050    private int mask;
051    private static LightRNG rng;
052
053    private ShortSetIterator iterator1, iterator2;
054
055    /** Creates a new sets with an initial capacity of 32 and a load factor of 0.8. This set will hold 25 items before growing the
056     * backing table. */
057    public ShortSet() {
058        this(32, 0.8f);
059    }
060
061    /** Creates a new set with a load factor of 0.8. This set will hold initialCapacity * 0.8 items before growing the backing
062     * table. */
063    public ShortSet(int initialCapacity) {
064        this(initialCapacity, 0.8f);
065    }
066
067    /** Creates a new set with the specified initial capacity and load factor. This set will hold initialCapacity * loadFactor items
068     * before growing the backing table. */
069    public ShortSet(int initialCapacity, float loadFactor) {
070        if (initialCapacity < 0) throw new IllegalArgumentException("initialCapacity must be >= 0: " + initialCapacity);
071        if (initialCapacity > 1 << 30) throw new IllegalArgumentException("initialCapacity is too large: " + initialCapacity);
072        capacity = nextPowerOfTwo(initialCapacity);
073
074        rng = new LightRNG();
075
076        if (loadFactor <= 0) throw new IllegalArgumentException("loadFactor must be > 0: " + loadFactor);
077        this.loadFactor = loadFactor;
078
079        threshold = (int)(capacity * loadFactor);
080        mask = capacity - 1;
081        hashShift = 31 - Integer.numberOfTrailingZeros(capacity);
082        stashCapacity = Math.max(3, (int)Math.ceil(Math.log(capacity)) * 2);
083        pushIterations = Math.max(Math.min(capacity, 8), (int)Math.sqrt(capacity) / 8);
084
085        keyTable = new short[capacity + stashCapacity];
086    }
087
088    /** Creates a new map identical to the specified map. */
089    public ShortSet(ShortSet map) {
090        this(map.capacity, map.loadFactor);
091        stashSize = map.stashSize;
092        System.arraycopy(map.keyTable, 0, keyTable, 0, map.keyTable.length);
093        size = map.size;
094        hasZeroValue = map.hasZeroValue;
095    }
096
097    /** Returns true if the key was not already in the set. */
098    public boolean add (short key) {
099        if (key == 0) {
100            if (hasZeroValue) return false;
101            hasZeroValue = true;
102            size++;
103            return true;
104        }
105
106        short[] keyTable = this.keyTable;
107
108        // Check for existing keys.
109        int index1 = key & mask;
110        short key1 = keyTable[index1];
111        if (key1 == key) return false;
112
113        int index2 = hash2(key);
114        short key2 = keyTable[index2];
115        if (key2 == key) return false;
116
117        int index3 = hash3(key);
118        short key3 = keyTable[index3];
119        if (key3 == key) return false;
120
121        // Find key in the stash.
122        for (int i = capacity, n = i + stashSize; i < n; i++)
123            if (keyTable[i] == key) return false;
124
125        // Check for empty buckets.
126        if (key1 == EMPTY) {
127            keyTable[index1] = key;
128            if (size++ >= threshold) resize(capacity << 1);
129            return true;
130        }
131
132        if (key2 == EMPTY) {
133            keyTable[index2] = key;
134            if (size++ >= threshold) resize(capacity << 1);
135            return true;
136        }
137
138        if (key3 == EMPTY) {
139            keyTable[index3] = key;
140            if (size++ >= threshold) resize(capacity << 1);
141            return true;
142        }
143
144        push(key, index1, key1, index2, key2, index3, key3);
145        return true;
146    }
147
148    public void addAll (ShortVLA array) {
149        addAll(array, 0, array.size);
150    }
151
152    public void addAll (ShortVLA array, int offset, int length) {
153        if (offset + length > array.size)
154            throw new IllegalArgumentException("offset + length must be <= size: " + offset + " + " + length + " <= " + array.size);
155        addAll(array.items, offset, length);
156    }
157
158    public void addAll (short... array) {
159        addAll(array, 0, array.length);
160    }
161
162    public void addAll (short[] array, int offset, int length) {
163        ensureCapacity(length);
164        for (int i = offset, n = i + length; i < n; i++)
165            add(array[i]);
166    }
167
168    public void addAll (ShortSet set) {
169        ensureCapacity(set.size);
170        ShortSetIterator iterator = set.iterator();
171        while (iterator.hasNext)
172            add(iterator.next());
173    }
174
175    /** Skips checks for existing keys. */
176    private void addResize (short key) {
177        if (key == 0) {
178            hasZeroValue = true;
179            return;
180        }
181
182        // Check for empty buckets.
183        int index1 = key & mask;
184        short key1 = keyTable[index1];
185        if (key1 == EMPTY) {
186            keyTable[index1] = key;
187            if (size++ >= threshold) resize(capacity << 1);
188            return;
189        }
190
191        int index2 = hash2(key);
192        short key2 = keyTable[index2];
193        if (key2 == EMPTY) {
194            keyTable[index2] = key;
195            if (size++ >= threshold) resize(capacity << 1);
196            return;
197        }
198
199        int index3 = hash3(key);
200        short key3 = keyTable[index3];
201        if (key3 == EMPTY) {
202            keyTable[index3] = key;
203            if (size++ >= threshold) resize(capacity << 1);
204            return;
205        }
206
207        push(key, index1, key1, index2, key2, index3, key3);
208    }
209
210    private void push (short insertKey, int index1, short key1, int index2, short key2, int index3, short key3) {
211        short[] keyTable = this.keyTable;
212
213        int mask = this.mask;
214
215        // Push keys until an empty bucket is found.
216        short evictedKey;
217        int i = 0, pushIterations = this.pushIterations;
218        do {
219            // Replace the key and value for one of the hashes.
220            switch (rng.nextInt(2)) {
221                case 0:
222                    evictedKey = key1;
223                    keyTable[index1] = insertKey;
224                    break;
225                case 1:
226                    evictedKey = key2;
227                    keyTable[index2] = insertKey;
228                    break;
229                default:
230                    evictedKey = key3;
231                    keyTable[index3] = insertKey;
232                    break;
233            }
234
235            // If the evicted key hashes to an empty bucket, put it there and stop.
236            index1 = evictedKey & mask;
237            key1 = keyTable[index1];
238            if (key1 == EMPTY) {
239                keyTable[index1] = evictedKey;
240                if (size++ >= threshold) resize(capacity << 1);
241                return;
242            }
243
244            index2 = hash2(evictedKey);
245            key2 = keyTable[index2];
246            if (key2 == EMPTY) {
247                keyTable[index2] = evictedKey;
248                if (size++ >= threshold) resize(capacity << 1);
249                return;
250            }
251
252            index3 = hash3(evictedKey);
253            key3 = keyTable[index3];
254            if (key3 == EMPTY) {
255                keyTable[index3] = evictedKey;
256                if (size++ >= threshold) resize(capacity << 1);
257                return;
258            }
259
260            if (++i == pushIterations) break;
261
262            insertKey = evictedKey;
263        } while (true);
264
265        addStash(evictedKey);
266    }
267
268    private void addStash (short key) {
269        if (stashSize == stashCapacity) {
270            // Too many pushes occurred and the stash is full, increase the table size.
271            resize(capacity << 1);
272            add(key);
273            return;
274        }
275        // Store key in the stash.
276        int index = capacity + stashSize;
277        keyTable[index] = key;
278        stashSize++;
279        size++;
280    }
281
282    /** Returns true if the key was removed. */
283    public boolean remove (short key) {
284        if (key == 0) {
285            if (!hasZeroValue) return false;
286            hasZeroValue = false;
287            size--;
288            return true;
289        }
290
291        int index = key & mask;
292        if (keyTable[index] == key) {
293            keyTable[index] = EMPTY;
294            size--;
295            return true;
296        }
297
298        index = hash2(key);
299        if (keyTable[index] == key) {
300            keyTable[index] = EMPTY;
301            size--;
302            return true;
303        }
304
305        index = hash3(key);
306        if (keyTable[index] == key) {
307            keyTable[index] = EMPTY;
308            size--;
309            return true;
310        }
311
312        return removeStash(key);
313    }
314
315    boolean removeStash (short key) {
316        short[] keyTable = this.keyTable;
317        for (int i = capacity, n = i + stashSize; i < n; i++) {
318            if (keyTable[i] == key) {
319                removeStashIndex(i);
320                size--;
321                return true;
322            }
323        }
324        return false;
325    }
326
327    void removeStashIndex (int index) {
328        // If the removed location was not last, move the last tuple to the removed location.
329        stashSize--;
330        int lastIndex = capacity + stashSize;
331        if (index < lastIndex) keyTable[index] = keyTable[lastIndex];
332    }
333
334    /** Reduces the size of the backing arrays to be the specified capacity or less. If the capacity is already less, nothing is
335     * done. If the set contains more items than the specified capacity, the next highest power of two capacity is used instead. */
336    public void shrink (int maximumCapacity) {
337        if (maximumCapacity < 0) throw new IllegalArgumentException("maximumCapacity must be >= 0: " + maximumCapacity);
338        if (size > maximumCapacity) maximumCapacity = size;
339        if (capacity <= maximumCapacity) return;
340        maximumCapacity = nextPowerOfTwo(maximumCapacity);
341
342        resize(maximumCapacity);
343    }
344
345    /** Clears the map and reduces the size of the backing arrays to be the specified capacity if they are larger. */
346    public void clear (int maximumCapacity) {
347        if (capacity <= maximumCapacity) {
348            clear();
349            return;
350        }
351        hasZeroValue = false;
352        size = 0;
353        resize(maximumCapacity);
354    }
355
356    public void clear () {
357        if (size == 0) return;
358        short[] keyTable = this.keyTable;
359        for (int i = capacity + stashSize; i-- > 0;)
360            keyTable[i] = EMPTY;
361        size = 0;
362        stashSize = 0;
363        hasZeroValue = false;
364    }
365
366    public boolean contains (short key) {
367        if (key == 0) return hasZeroValue;
368        int index = key & mask;
369        if (keyTable[index] != key) {
370            index = hash2(key);
371            if (keyTable[index] != key) {
372                index = hash3(key);
373                if (keyTable[index] != key) return containsKeyStash(key);
374            }
375        }
376        return true;
377    }
378
379    private boolean containsKeyStash (short key) {
380        short[] keyTable = this.keyTable;
381        for (int i = capacity, n = i + stashSize; i < n; i++)
382            if (keyTable[i] == key) return true;
383        return false;
384    }
385
386    public int first () {
387        if (hasZeroValue) return 0;
388        short[] keyTable = this.keyTable;
389        for (int i = 0, n = capacity + stashSize; i < n; i++)
390            if (keyTable[i] != EMPTY) return keyTable[i];
391        throw new IllegalStateException("IntSet is empty.");
392    }
393
394    /** Increases the size of the backing array to accommodate the specified number of additional items. Useful before adding many
395     * items to avoid multiple backing array resizes. */
396    public void ensureCapacity (int additionalCapacity) {
397        int sizeNeeded = size + additionalCapacity;
398        if (sizeNeeded >= threshold) resize(nextPowerOfTwo((int)(sizeNeeded / loadFactor)));
399    }
400
401    private void resize (int newSize) {
402        int oldEndIndex = capacity + stashSize;
403
404        capacity = newSize;
405        threshold = (int)(newSize * loadFactor);
406        mask = newSize - 1;
407        hashShift = 31 - Integer.numberOfTrailingZeros(newSize);
408        stashCapacity = Math.max(3, (int)Math.ceil(Math.log(newSize)) * 2);
409        pushIterations = Math.max(Math.min(newSize, 8), (int)Math.sqrt(newSize) / 8);
410
411        short[] oldKeyTable = keyTable;
412
413        keyTable = new short[newSize + stashCapacity];
414
415        int oldSize = size;
416        size = hasZeroValue ? 1 : 0;
417        stashSize = 0;
418        if (oldSize > 0) {
419            for (int i = 0; i < oldEndIndex; i++) {
420                short key = oldKeyTable[i];
421                if (key != EMPTY) addResize(key);
422            }
423        }
424    }
425
426    private int hash2 (int h) {
427        h *= PRIME2;
428        return (h ^ h >>> hashShift) & mask;
429    }
430
431    private int hash3 (int h) {
432        h *= PRIME3;
433        return (h ^ h >>> hashShift) & mask;
434    }
435
436    @Override
437        public int hashCode () {
438        int h = 0;
439        for (int i = 0, n = capacity + stashSize; i < n; i++)
440            if (keyTable[i] != EMPTY) h += keyTable[i];
441        return h;
442    }
443
444    @Override
445        public boolean equals (Object obj) {
446        if (!(obj instanceof ShortSet)) return false;
447        ShortSet other = (ShortSet)obj;
448        if (other.size != size) return false;
449        if (other.hasZeroValue != hasZeroValue) return false;
450        for (int i = 0, n = capacity + stashSize; i < n; i++)
451            if (keyTable[i] != EMPTY && !other.contains(keyTable[i])) return false;
452        return true;
453    }
454
455    @Override
456        public String toString () {
457        if (size == 0) return "[]";
458        StringBuilder buffer = new StringBuilder(32);
459        buffer.append('[');
460        short[] keyTable = this.keyTable;
461        int i = keyTable.length;
462        if (hasZeroValue)
463            buffer.append("0");
464        else {
465            while (i-- > 0) {
466                int key = keyTable[i];
467                if (key == EMPTY) continue;
468                buffer.append(key);
469                break;
470            }
471        }
472        while (i-- > 0) {
473            int key = keyTable[i];
474            if (key == EMPTY) continue;
475            buffer.append(", ");
476            buffer.append(key);
477        }
478        buffer.append(']');
479        return buffer.toString();
480    }
481
482    private static int nextPowerOfTwo(int n)
483    {
484        int highest = Integer.highestOneBit(n);
485        return  (highest == Integer.lowestOneBit(n)) ? highest : highest << 1;
486    }
487
488    /** Returns an iterator for the keys in the set. Remove is supported. Note that the same iterator instance is returned each time
489     * this method is called. Use the {@link ShortSetIterator} constructor for nested or multithreaded iteration. */
490    public ShortSetIterator iterator () {
491        if (iterator1 == null) {
492            iterator1 = new ShortSetIterator(this);
493            iterator2 = new ShortSetIterator(this);
494        }
495        if (!iterator1.valid) {
496            iterator1.reset();
497            iterator1.valid = true;
498            iterator2.valid = false;
499            return iterator1;
500        }
501        iterator2.reset();
502        iterator2.valid = true;
503        iterator1.valid = false;
504        return iterator2;
505    }
506
507    public static ShortSet with (short... array) {
508        ShortSet set = new ShortSet();
509        set.addAll(array);
510        return set;
511    }
512
513    public static class ShortSetIterator {
514        static final int INDEX_ILLEGAL = -2;
515        static final int INDEX_ZERO = -1;
516
517        public boolean hasNext;
518
519        final ShortSet set;
520        int nextIndex, currentIndex;
521        boolean valid = true;
522
523        public ShortSetIterator(ShortSet set) {
524            this.set = set;
525            reset();
526        }
527
528        public void reset () {
529            currentIndex = INDEX_ILLEGAL;
530            nextIndex = INDEX_ZERO;
531            if (set.hasZeroValue)
532                hasNext = true;
533            else
534                findNextIndex();
535        }
536
537        void findNextIndex () {
538            hasNext = false;
539            short[] keyTable = set.keyTable;
540            for (int n = set.capacity + set.stashSize; ++nextIndex < n;) {
541                if (keyTable[nextIndex] != EMPTY) {
542                    hasNext = true;
543                    break;
544                }
545            }
546        }
547
548        public void remove () {
549            if (currentIndex == INDEX_ZERO && set.hasZeroValue) {
550                set.hasZeroValue = false;
551            } else if (currentIndex < 0) {
552                throw new IllegalStateException("next must be called before remove.");
553            } else if (currentIndex >= set.capacity) {
554                set.removeStashIndex(currentIndex);
555                nextIndex = currentIndex - 1;
556                findNextIndex();
557            } else {
558                set.keyTable[currentIndex] = EMPTY;
559            }
560            currentIndex = INDEX_ILLEGAL;
561            set.size--;
562        }
563
564        public short next () {
565            if (!hasNext) throw new NoSuchElementException();
566            if (!valid) throw new RuntimeException("ShortSetIterator cannot be used nested.");
567            short key = nextIndex == INDEX_ZERO ? 0 : set.keyTable[nextIndex];
568            currentIndex = nextIndex;
569            findNextIndex();
570            return key;
571        }
572
573        /** Returns a new array containing the remaining keys. */
574        public ShortVLA toArray () {
575            ShortVLA array = new ShortVLA(true, set.size);
576            while (hasNext)
577                array.add(next());
578            return array;
579        }
580    }
581}