Source code

001/*
002 * Copyright (C) 2002-2015 Sebastiano Vigna
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 *     http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License. 
015 */
016package squidpony.squidmath;
017
018import squidpony.annotation.GwtIncompatible;
019
020import java.util.*;
021
022/**
023 * A generic unordered hash set with with a fast implementation, based on {@link OrderedSet} in this library, which is
024 * based on the fastutil library's ObjectLinkedOpenHashSet class; the ordering and indexed access have been removed to
025 * potentially reduce the time cost of insertion and removal at the expense of increasing time cost for access by index.
026 * This does support optional hash strategies for array (and other) keys, which fastutil's collections can do in a
027 * different way, and has better support than {@link HashSet} for construction with an array of items or construction
028 * with a Collection of items (this also helps {@link #addAll(Object[])}).
029 * <p>
030 * Instances of this class use a hash table to represent a set. The table is
031 * filled up to a specified <em>load factor</em>, and then doubled in size to
032 * accommodate new entries. If the table is emptied below <em>one fourth</em> of
033 * the load factor, it is halved in size. However, halving is not performed when
034 * deleting entries from an iterator, as it would interfere with the iteration
035 * process.
036 * </p>
037 * <p>
038 * Note that {@link #clear()} does not modify the hash table size. Rather, a
039 * family of {@linkplain #trim() trimming methods} lets you control the size of
040 * the table; this is particularly useful if you reuse instances of this class.
041 * </p>
042 * <p>
043 * This class implements the interface of a Set, not a SortedSet.
044 * <p>
045 * <p>
046 * You can pass an {@link CrossHash.IHasher} instance such as {@link CrossHash#generalHasher} as an extra parameter to
047 * most of this class' constructors, which allows the OrderedSet to use arrays (usually primitive arrays) as items. If
048 * you expect only one type of array, you can use an instance like {@link CrossHash#intHasher} to hash int arrays, or
049 * the aforementioned generalHasher to hash most kinds of arrays (it can't handle most multi-dimensional arrays well).
050 * If you aren't using array items, you don't need to give an IHasher to the constructor and can ignore this feature.
051 * </p>
052 * <br>
053 * Thank you, Sebastiano Vigna, for making FastUtil available to the public with such high quality.
054 * <br>
055 * See https://github.com/vigna/fastutil for the original library.
056 *
057 * @author Sebastiano Vigna (responsible for all the hard parts)
058 * @author Tommy Ettinger (mostly responsible for squashing several layers of parent classes into one monster class)
059 */
060public class UnorderedSet<K> implements Set<K>, java.io.Serializable, Cloneable {
061    private static final long serialVersionUID = 0L;
062    /**
063     * The array of keys.
064     */
065    protected K[] key;
066    /*
067      The array of values.
068     */
069    //protected V[] value;
070    /**
071     * The mask for wrapping a position counter.
072     */
073    protected int mask;
074    /**
075     * Whether this set contains the key zero.
076     */
077    protected boolean containsNull;
078    /**
079     * The current table size.
080     */
081    protected int n;
082    /**
083     * Threshold after which we rehash. It must be the table size times {@link #f}.
084     */
085    protected int maxFill;
086    /**
087     * Number of entries in the set (including the key zero, if present).
088     */
089    protected int size;
090    /**
091     * The acceptable load factor.
092     */
093    public final float f;
094
095    /**
096     * The initial default size of a hash table.
097     */
098    public static final int DEFAULT_INITIAL_SIZE = 16;
099    /**
100     * The default load factor of a hash table.
101     */
102    public static final float DEFAULT_LOAD_FACTOR = .25f; // .1875f; // .75f;
103    /**
104     * The load factor for a (usually small) table that is meant to be particularly fast.
105     */
106    public static final float FAST_LOAD_FACTOR = .5f;
107    /**
108     * The load factor for a (usually very small) table that is meant to be extremely fast.
109     */
110    public static final float VERY_FAST_LOAD_FACTOR = .25f;
111
112    protected final CrossHash.IHasher hasher;
113
114    /**
115     * Creates a new hash map.
116     * <p>
117     * <p>The actual table size will be the least power of two greater than <code>expected</code>/<code>f</code>.
118     *
119     * @param expected the expected number of elements in the hash set.
120     * @param f        the load factor.
121     */
122
123    @SuppressWarnings("unchecked")
124    public UnorderedSet(final int expected, final float f) {
125        if (f <= 0 || f > 1)
126            throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than or equal to 1");
127        if (expected < 0) throw new IllegalArgumentException("The expected number of elements must be nonnegative");
128        this.f = f;
129        n = arraySize(expected, f);
130        mask = n - 1;
131        maxFill = maxFill(n, f);
132        key = (K[]) new Object[n + 1];
133        hasher = CrossHash.mildHasher;
134    }
135
136    /**
137     * Creates a new hash set with {@link #DEFAULT_LOAD_FACTOR} as load
138     * factor.
139     *
140     * @param expected the expected number of elements in the hash set.
141     */
142    public UnorderedSet(final int expected) {
143        this(expected, DEFAULT_LOAD_FACTOR);
144    }
145
146    /**
147     * Creates a new hash set with initial expected
148     * {@link #DEFAULT_INITIAL_SIZE} elements and
149     * {@link #DEFAULT_LOAD_FACTOR} as load factor.
150     */
151    public UnorderedSet() {
152        this(DEFAULT_INITIAL_SIZE, DEFAULT_LOAD_FACTOR);
153    }
154
155    /**
156     * Creates a new hash set copying a given collection.
157     *
158     * @param c a {@link Collection} to be copied into the new hash set.
159     * @param f the load factor.
160     */
161    public UnorderedSet(final Collection<? extends K> c,
162                        final float f) {
163        this(c.size(), f, (c instanceof UnorderedSet) ? ((UnorderedSet) c).hasher : CrossHash.mildHasher);
164        addAll(c);
165    }
166
167    /**
168     * Creates a new hash set with {@link #DEFAULT_LOAD_FACTOR} as load
169     * factor copying a given collection.
170     *
171     * @param c a {@link Collection} to be copied into the new hash set.
172     */
173    public UnorderedSet(final Collection<? extends K> c) {
174        this(c, (c instanceof UnorderedSet) ? ((UnorderedSet) c).f : DEFAULT_LOAD_FACTOR, (c instanceof UnorderedSet) ? ((UnorderedSet) c).hasher : CrossHash.mildHasher);
175    }
176
177    /**
178     * Creates a new hash set using elements provided by a type-specific
179     * iterator.
180     *
181     * @param i a type-specific iterator whose elements will fill the set.
182     * @param f the load factor.
183     */
184    public UnorderedSet(final Iterator<? extends K> i, final float f) {
185        this(DEFAULT_INITIAL_SIZE, f);
186        while (i.hasNext())
187            add(i.next());
188    }
189
190    /**
191     * Creates a new hash set with {@link #DEFAULT_LOAD_FACTOR} as load
192     * factor using elements provided by a type-specific iterator.
193     *
194     * @param i a type-specific iterator whose elements will fill the set.
195     */
196    public UnorderedSet(final Iterator<? extends K> i) {
197        this(i, DEFAULT_LOAD_FACTOR);
198    }
199
200    /**
201     * Creates a new hash set and fills it with the elements of a given array.
202     *
203     * @param a      an array whose elements will be used to fill the set.
204     * @param offset the first element to use.
205     * @param length the number of elements to use.
206     * @param f      the load factor.
207     */
208    public UnorderedSet(final K[] a, final int offset,
209                        final int length, final float f) {
210        this(Math.max(length, 0), f);
211        if (a == null) throw new NullPointerException("Array passed to OrderedSet constructor cannot be null");
212        if (offset < 0) throw new ArrayIndexOutOfBoundsException("Offset (" + offset + ") is negative");
213        if (length < 0) throw new IllegalArgumentException("Length (" + length + ") is negative");
214        if (offset + length > a.length) {
215            throw new ArrayIndexOutOfBoundsException(
216                    "Last index (" + (offset + length) + ") is greater than array length (" + a.length + ")");
217        }
218        for (int i = 0; i < length; i++)
219            add(a[offset + i]);
220    }
221
222    /**
223     * Creates a new hash set with {@link #DEFAULT_LOAD_FACTOR} as load
224     * factor and fills it with the elements of a given array.
225     *
226     * @param a      an array whose elements will be used to fill the set.
227     * @param offset the first element to use.
228     * @param length the number of elements to use.
229     */
230    public UnorderedSet(final K[] a, final int offset,
231                        final int length) {
232        this(a, offset, length, DEFAULT_LOAD_FACTOR);
233    }
234
235    /**
236     * Creates a new hash set copying the elements of an array.
237     *
238     * @param a an array to be copied into the new hash set.
239     * @param f the load factor.
240     */
241    public UnorderedSet(final K[] a, final float f) {
242        this(a, 0, a.length, f);
243    }
244
245    /**
246     * Creates a new hash set with {@link #DEFAULT_LOAD_FACTOR} as load
247     * factor copying the elements of an array.
248     *
249     * @param a an array to be copied into the new hash set.
250     */
251    public UnorderedSet(final K[] a) {
252        this(a, DEFAULT_LOAD_FACTOR);
253    }
254
255    /**
256     * Creates a new hash map.
257     * <p>
258     * <p>The actual table size will be the least power of two greater than <code>expected</code>/<code>f</code>.
259     *
260     * @param expected the expected number of elements in the hash set.
261     * @param f        the load factor.
262     * @param hasher   used to hash items; typically only needed when K is an array, where CrossHash has implementations
263     */
264    @SuppressWarnings("unchecked")
265    public UnorderedSet(final int expected, final float f, CrossHash.IHasher hasher) {
266        if (f <= 0 || f > 1)
267            throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than or equal to 1");
268        if (expected < 0) throw new IllegalArgumentException("The expected number of elements must be nonnegative");
269        this.f = f;
270        n = arraySize(expected, f);
271        mask = n - 1;
272        maxFill = maxFill(n, f);
273        key = (K[]) new Object[n + 1];
274        this.hasher = hasher == null ? CrossHash.mildHasher : hasher;
275    }
276
277    /**
278     * Creates a new hash set with {@link #DEFAULT_LOAD_FACTOR} as load
279     * factor.
280     *
281     * @param hasher used to hash items; typically only needed when K is an array, where CrossHash has implementations
282     */
283    public UnorderedSet(CrossHash.IHasher hasher) {
284        this(DEFAULT_INITIAL_SIZE, DEFAULT_LOAD_FACTOR, hasher);
285    }
286
287    /**
288     * Creates a new hash set with {@link #DEFAULT_LOAD_FACTOR} as load
289     * factor.
290     *
291     * @param hasher used to hash items; typically only needed when K is an array, where CrossHash has implementations
292     */
293    public UnorderedSet(final int expected, CrossHash.IHasher hasher) {
294        this(expected, DEFAULT_LOAD_FACTOR, hasher);
295    }
296
297    /**
298     * Creates a new hash set copying a given collection.
299     *
300     * @param c      a {@link Collection} to be copied into the new hash set.
301     * @param f      the load factor.
302     * @param hasher used to hash items; typically only needed when K is an array, where CrossHash has implementations
303     */
304    public UnorderedSet(final Collection<? extends K> c,
305                        final float f, CrossHash.IHasher hasher) {
306        this(c.size(), f, hasher);
307        addAll(c);
308    }
309
310    /**
311     * Creates a new hash set with {@link #DEFAULT_LOAD_FACTOR} as load
312     * factor copying a given collection.
313     *
314     * @param c      a {@link Collection} to be copied into the new hash set.
315     * @param hasher used to hash items; typically only needed when K is an array, where CrossHash has implementations
316     */
317    public UnorderedSet(final Collection<? extends K> c, CrossHash.IHasher hasher) {
318        this(c, DEFAULT_LOAD_FACTOR, hasher);
319    }
320
321    /**
322     * Creates a new hash set and fills it with the elements of a given array.
323     *
324     * @param a      an array whose elements will be used to fill the set.
325     * @param offset the first element to use.
326     * @param length the number of elements to use.
327     * @param f      the load factor.
328     */
329    public UnorderedSet(final K[] a, final int offset,
330                        final int length, final float f, CrossHash.IHasher hasher) {
331        this(Math.max(length, 0), f, hasher);
332        if (a == null) throw new NullPointerException("Array passed to OrderedSet constructor cannot be null");
333        if (offset < 0) throw new ArrayIndexOutOfBoundsException("Offset (" + offset + ") is negative");
334        if (length < 0) throw new IllegalArgumentException("Length (" + length + ") is negative");
335        if (offset + length > a.length) {
336            throw new ArrayIndexOutOfBoundsException(
337                    "Last index (" + (offset + length) + ") is greater than array length (" + a.length + ")");
338        }
339        for (int i = 0; i < length; i++)
340            add(a[offset + i]);
341    }
342
343    /**
344     * Creates a new hash set with {@link #DEFAULT_LOAD_FACTOR} as load
345     * factor and fills it with the elements of a given array.
346     *
347     * @param a      an array whose elements will be used to fill the set.
348     * @param offset the first element to use.
349     * @param length the number of elements to use.
350     */
351    public UnorderedSet(final K[] a, final int offset,
352                        final int length, CrossHash.IHasher hasher) {
353        this(a, offset, length, DEFAULT_LOAD_FACTOR, hasher);
354    }
355
356    /**
357     * Creates a new hash set copying the elements of an array.
358     *
359     * @param a an array to be copied into the new hash set.
360     * @param f the load factor.
361     */
362    public UnorderedSet(final K[] a, final float f, CrossHash.IHasher hasher) {
363        this(a, 0, a.length, f, hasher);
364    }
365
366    /**
367     * Creates a new hash set with {@link #DEFAULT_LOAD_FACTOR} as load
368     * factor copying the elements of an array.
369     *
370     * @param a an array to be copied into the new hash set.
371     */
372    public UnorderedSet(final K[] a, CrossHash.IHasher hasher) {
373        this(a, DEFAULT_LOAD_FACTOR, hasher);
374    }
375
376    private int realSize() {
377        return containsNull ? size - 1 : size;
378    }
379
380    private void ensureCapacity(final int capacity) {
381        final int needed = arraySize(capacity, f);
382        if (needed > n)
383            rehash(needed);
384    }
385
386    private void tryCapacity(final long capacity) {
387        final int needed = (int) Math.min(
388                1 << 30,
389                Math.max(2, HashCommon.nextPowerOfTwo((long) Math.ceil(capacity
390                        / f))));
391        if (needed > n)
392            rehash(needed);
393    }
394
395    public boolean addAll(Collection<? extends K> c) {
396        int n = c.size();
397        // The resulting collection will be at least c.size() big
398        if (f <= .5)
399            ensureCapacity(n); // The resulting collection will be sized
400            // for c.size() elements
401        else
402            tryCapacity(size + n); // The resulting collection will be
403        // tentatively sized for size() + c.size() elements
404        boolean retVal = false;
405        final Iterator<? extends K> i = c.iterator();
406        while (n-- != 0)
407            if (add(i.next()))
408                retVal = true;
409        return retVal;
410    }
411
412    public boolean addAll(K[] a) {
413        if(a == null)
414            return false;
415        int n = a.length;
416        // The resulting collection will be at least a.length big
417        if (f <= .5)
418            ensureCapacity(n); // The resulting collection will be sized
419            // for a.length elements
420        else
421            tryCapacity(size + n); // The resulting collection will be
422        // tentatively sized for size() + a.length elements
423        boolean retVal = false;
424        for (int i = 0; i < n; i++) {
425            if(add(a[i]))
426                retVal = true;
427        }
428        return retVal;
429    }
430
431
432    public boolean add(final K k) {
433        int pos;
434        if (k == null) {
435            if (containsNull)
436                return false;
437            containsNull = true;
438        } else {
439            K curr;
440            final K[] key = this.key;
441            // The starting point.
442            if (!((curr = key[pos = (hasher.hash(k)) & mask]) == null)) {
443                if (hasher.areEqual(curr, k))
444                    return false;
445                while (!((curr = key[pos = pos + 1 & mask]) == null))
446                    if (hasher.areEqual(curr, k))
447                        return false;
448            }
449            key[pos] = k;
450        }
451        if (size++ >= maxFill)
452            rehash(arraySize(size + 1, f));
453        return true;
454    }
455
456    /**
457     * Add a random element if not present, get the existing value if already
458     * present.
459     * <p>
460     * This is equivalent to (but faster than) doing a:
461     * <p>
462     * <pre>
463     * K exist = set.get(k);
464     * if (exist == null) {
465     *  set.add(k);
466     *  exist = k;
467     * }
468     * </pre>
469     */
470    public K addOrGet(final K k) {
471        int pos;
472        if (k == null) {
473            if (containsNull)
474                return key[n];
475            containsNull = true;
476        } else {
477            K curr;
478            final K[] key = this.key;
479            // The starting point.
480            if (!((curr = key[pos = (hasher.hash(k)) & mask]) == null)) {
481                if (hasher.areEqual(curr, k))
482                    return curr;
483                while (!((curr = key[pos = pos + 1 & mask]) == null))
484                    if (hasher.areEqual(curr, k))
485                        return curr;
486            }
487            key[pos] = k;
488        }
489        if (size++ >= maxFill)
490            rehash(arraySize(size + 1, f));
491        return k;
492    }
493
494    /**
495     * Shifts left entries with the specified hash code, starting at the
496     * specified position, and empties the resulting free entry.
497     *
498     * @param pos a starting position.
499     */
500    protected final void shiftKeys(int pos) {
501        // Shift entries with the same hash.
502        int last, slot;
503        K curr;
504        final K[] key = this.key;
505        for (; ; ) {
506            pos = (last = pos) + 1 & mask;
507            for (; ; ) {
508                if ((curr = key[pos]) == null) {
509                    key[last] = null;
510                    return;
511                }
512                slot = (hasher.hash(curr))
513                        & mask;
514                if (last <= pos ? last >= slot || slot > pos : last >= slot
515                        && slot > pos)
516                    break;
517                pos = pos + 1 & mask;
518            }
519            key[last] = curr;
520        }
521    }
522
523    private boolean removeEntry(final int pos) {
524        size--;
525        shiftKeys(pos);
526        if (size < maxFill / 4 && n > DEFAULT_INITIAL_SIZE)
527            rehash(n / 2);
528        return true;
529    }
530
531    private boolean removeNullEntry() {
532        containsNull = false;
533        key[n] = null;
534        size--;
535        if (size < maxFill / 4 && n > DEFAULT_INITIAL_SIZE)
536            rehash(n / 2);
537        return true;
538    }
539
540    @Override
541    public boolean remove(final Object k) {
542        if (k == null)
543            return containsNull && removeNullEntry();
544        K curr;
545        final K[] key = this.key;
546        int pos;
547        // The starting point.
548        if ((curr = key[pos = (hasher.hash(k)) & mask]) == null)
549            return false;
550        if (hasher.areEqual(k, curr))
551            return removeEntry(pos);
552        while (true) {
553            if ((curr = key[pos = pos + 1 & mask]) == null)
554                return false;
555            if (hasher.areEqual(k, curr))
556                return removeEntry(pos);
557        }
558    }
559
560    /**
561     * Returns the element of this set that is equal to the given key, or
562     * <code>null</code>.
563     *
564     * @return the element of this set that is equal to the given key, or
565     * <code>null</code>.
566     */
567    public K get(final Object k) {
568        if (k == null)
569            return key[n]; // This is correct independently of the value of
570        // containsNull and of the map being custom
571        K curr;
572        final K[] key = this.key;
573        int pos;
574        // The starting point.
575        if ((curr = key[pos = (hasher.hash(k)) & mask]) == null)
576            return null;
577        if (hasher.areEqual(k, curr))
578            return curr;
579        // There's always an unused entry.
580        while (true) {
581            if ((curr = key[pos = pos + 1 & mask]) == null)
582                return null;
583            if (hasher.areEqual(k, curr))
584                return curr;
585        }
586    }
587
588    public boolean contains(final Object k) {
589        if (k == null)
590            return containsNull;
591        K curr;
592        final K[] key = this.key;
593        int pos;
594        // The starting point.
595        if ((curr = key[pos = (hasher.hash(k)) & mask]) == null)
596            return false;
597        if (hasher.areEqual(k, curr))
598            return true;
599        // There's always an unused entry.
600        while (true) {
601            if ((curr = key[pos = pos + 1 & mask]) == null)
602                return false;
603            if (hasher.areEqual(k, curr))
604                return true;
605        }
606    }
607
608    protected int positionOf(final Object k) {
609        if (k == null)
610        {
611            if(containsNull)
612                return n;
613            else
614                return -1;
615        }
616        K curr;
617        final K[] key = this.key;
618        int pos;
619        // The starting point.
620        if ((curr = key[pos = (hasher.hash(k)) & mask]) == null)
621            return -1;
622        if (hasher.areEqual(k, curr))
623            return pos;
624        // There's always an unused entry.
625        while (true) {
626            if ((curr = key[pos = pos + 1 & mask]) == null)
627                return -1;
628            if (hasher.areEqual(k, curr))
629                return pos;
630        }
631    }
632
633    /*
634     * Removes all elements from this set.
635     *
636     * <P>To increase object reuse, this method does not change the table size.
637     * If you want to reduce the table size, you must use {@link #trim()}.
638     */
639    public void clear() {
640        if (size == 0)
641            return;
642        size = 0;
643        containsNull = false;
644        Arrays.fill(key, null);
645    }
646
647    public int size() {
648        return size;
649    }
650
651    /**
652     * Checks whether this collection contains all elements from the given
653     * collection.
654     *
655     * @param c a collection.
656     * @return <code>true</code> if this collection contains all elements of the
657     * argument.
658     */
659    public boolean containsAll(Collection<?> c) {
660        int n = c.size();
661        final Iterator<?> i = c.iterator();
662        while (n-- != 0)
663            if (!contains(i.next()))
664                return false;
665        return true;
666    }
667
668    /**
669     * Retains in this collection only elements from the given collection.
670     *
671     * @param c a collection.
672     * @return <code>true</code> if this collection changed as a result of the
673     * call.
674     */
675    public boolean retainAll(Collection<?> c) {
676        boolean retVal = false;
677        int n = size;
678        final Iterator<?> i = iterator();
679        while (n-- != 0) {
680            if (!c.contains(i.next())) {
681                i.remove();
682                retVal = true;
683            }
684        }
685        return retVal;
686    }
687
688    /**
689     * Remove from this collection all elements in the given collection. If the
690     * collection is an instance of this class, it uses faster iterators.
691     *
692     * @param c a collection.
693     * @return <code>true</code> if this collection changed as a result of the
694     * call.
695     */
696    public boolean removeAll(Collection<?> c) {
697        boolean retVal = false;
698        int n = c.size();
699        final Iterator<?> i = c.iterator();
700        while (n-- != 0)
701            if (remove(i.next()))
702                retVal = true;
703        return retVal;
704    }
705
706    public boolean isEmpty() {
707        return size == 0;
708    }
709
710
711    /*
712     * A list iterator over a set.
713     * <p>
714     * <p>
715     * This class provides a list iterator over a hash set. The
716     * constructor takes constant time.
717     */
718    private class SetIterator implements Iterator <K> {
719        /** The index of the last entry returned, if positive or zero; initially, {@link #n}. If negative, the last
720         element returned was that of index {@code - pos - 1} from the {@link #wrapped} list. */
721        int pos = n;
722        /** The index of the last entry that has been returned (more precisely, the value of {@link #pos} if {@link #pos} is positive,
723         or {@link Integer#MIN_VALUE} if {@link #pos} is negative). It is -1 if either
724         we did not return an entry yet, or the last returned entry has been removed. */
725        int last = -1;
726        /** A downward counter measuring how many entries must still be returned. */
727        int c = size;
728        /** A boolean telling us whether we should return the null key. */
729        boolean mustReturnNull = UnorderedSet.this.containsNull;
730        /** A lazily allocated list containing elements that have wrapped around the table because of removals. */
731        ArrayList <K> wrapped;
732        public boolean hasNext() {
733            return c != 0;
734        }
735        public K next() {
736            if ( ! hasNext() ) throw new NoSuchElementException();
737            c--;
738            if ( mustReturnNull ) {
739                mustReturnNull = false;
740                last = n;
741                return key[ n ];
742            }
743            final K[] key = UnorderedSet.this.key;
744            for(;;) {
745                if ( --pos < 0 ) {
746                    // We are just enumerating elements from the wrapped list.
747                    last = Integer.MIN_VALUE;
748                    return wrapped.get( - pos - 1 );
749                }
750                if ( ! ( (key[ pos ]) == null ) ) return key[ last = pos ];
751            }
752        }
753        /** Shifts left entries with the specified hash code, starting at the specified position,
754         * and empties the resulting free entry.
755         *
756         * @param pos a starting position.
757         */
758        private void shiftKeys(int pos ) {
759            // Shift entries with the same hash.
760            int last, slot;
761            K current;
762            final K[] key = UnorderedSet.this.key;
763            for(;;) {
764                pos = ( ( last = pos ) + 1 ) & mask;
765                for(;;) {
766                    if ( ( (current = key[ pos ]) == null ) ) {
767                        key[ last ] = (null);
768                        return;
769                    }
770                    slot = ( (hasher.hash(current)) ) & mask;
771                    if ( last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos ) break;
772                    pos = ( pos + 1 ) & mask;
773                }
774                if ( pos < last ) { // Wrapped entry.
775                    if ( wrapped == null ) wrapped = new ArrayList<K>( 2 );
776                    wrapped.add( key[ pos ] );
777                }
778                key[ last ] = current;
779            }
780        }
781        public void remove() {
782            if ( last == -1 ) throw new IllegalStateException();
783            if ( last == n ) {
784                UnorderedSet.this.containsNull = false;
785                UnorderedSet.this.key[ n ] = (null);
786            }
787            else if ( pos >= 0 ) shiftKeys( last );
788            else {
789                // We're removing wrapped entries.
790                UnorderedSet.this.remove( wrapped.set( - pos - 1, null ) );
791                last = -1; // Note that we must not decrement size
792                return;
793            }
794            size--;
795            last = -1; // You can no longer remove this entry.
796        }
797        /** This method just iterates the type-specific version of {@link #next()} for at most
798         * <code>n</code> times, stopping if {@link #hasNext()} becomes false.*/
799        public int skip( final int n ) {
800            int i = n;
801            while( i-- != 0 && hasNext() ) next();
802            return n - i - 1;
803        }
804    }
805
806    public Iterator<K> iterator() {
807        return new SetIterator();
808    }
809
810    /**
811     * Rehashes the map, making the table as small as possible.
812     * <p>
813     * <P>This method rehashes the table to the smallest size satisfying the load factor. It can be used when the set will not be changed anymore, so to optimize access speed and size.
814     * <p>
815     * <P>If the table size is already the minimum possible, this method does nothing.
816     *
817     * @return true if there was enough memory to trim the map.
818     * @see #trim(int)
819     */
820    public boolean trim() {
821        final int l = arraySize(size, f);
822        if (l >= n || size > maxFill(l, f)) return true;
823        try {
824            rehash(l);
825        } catch (Exception cantDoIt) {
826            return false;
827        }
828        return true;
829    }
830
831    /**
832     * Rehashes this map if the table is too large.
833     * <p>
834     * <P>Let <var>N</var> be the smallest table size that can hold <code>max(n,{@link #size()})</code> entries, still satisfying the load factor. If the current table size is smaller than or equal to
835     * <var>N</var>, this method does nothing. Otherwise, it rehashes this map in a table of size <var>N</var>.
836     * <p>
837     * <P>This method is useful when reusing maps. {@linkplain #clear() Clearing a map} leaves the table size untouched. If you are reusing a map many times, you can call this method with a typical
838     * size to avoid keeping around a very large table just because of a few large transient maps.
839     *
840     * @param n the threshold for the trimming.
841     * @return true if there was enough memory to trim the map.
842     * @see #trim()
843     */
844    public boolean trim(final int n) {
845        final int l = HashCommon.nextPowerOfTwo((int) Math.ceil(n / f));
846        if (l >= n || size > maxFill(l, f)) return true;
847        try {
848            rehash(l);
849        } catch (Exception cantDoIt) {
850            return false;
851        }
852        return true;
853    }
854
855    /**
856     * Given a hash position, this finds the next position that contains an item, or -1 if none remain.
857     * To scan from the start, give this -1 for position.
858     * @param position a hash-based masked position in the K array
859     * @return the next position after the given one
860     */
861    private int scanNext(int position)
862    {
863        int h = position;
864        while (++h < n)
865        {
866            if(key[h] != null)
867            {
868                return h;
869            }
870        }
871        if(containsNull)
872            return n;
873        return -1;
874    }
875
876    /**
877     * Rehashes the map.
878     * <p>
879     * <p>
880     * This method implements the basic rehashing strategy, and may be overriden
881     * by subclasses implementing different rehashing strategies (e.g.,
882     * disk-based rehashing). However, you should not override this method
883     * unless you understand the internal workings of this class.
884     *
885     * @param newN the new size
886     */
887    @SuppressWarnings("unchecked")
888    protected void rehash(final int newN) {
889        final K[] key = this.key;
890        final int mask = newN - 1;
891        final K[] newKey = (K[]) new Object[newN + 1];
892        K k;
893        int i = -1, pos, sz = size;
894        for (int q = 0; q < sz; q++) {
895            i = scanNext(i);
896            if ((k = key[i]) == null)
897                pos = newN;
898            else {
899                pos = (hasher.hash(k)) & mask;
900                while (!(newKey[pos] == null))
901                    pos = pos + 1 & mask;
902            }
903            newKey[pos] = k;
904        }
905        n = newN;
906        this.mask = mask;
907        maxFill = maxFill(n, f);
908        this.key = newKey;
909    }
910
911    /**
912     * Returns a deep copy of this map.
913     * <p>
914     * <p>
915     * This method performs a deep copy of this hash map; the data stored in the
916     * map, however, is not cloned. Note that this makes a difference only for
917     * object keys.
918     *
919     * @return a deep copy of this map.
920     */
921    @SuppressWarnings("unchecked")
922    @GwtIncompatible
923    public Object clone() {
924        UnorderedSet<K> c;
925        try {
926            c = new UnorderedSet<>(hasher);
927            c.key = (K[]) new Object[n + 1];
928            System.arraycopy(key, 0, c.key, 0, n + 1);
929            return c;
930        } catch (Exception cantHappen) {
931            throw new UnsupportedOperationException(cantHappen + (cantHappen.getMessage() != null ?
932                    "; " + cantHappen.getMessage() : ""));
933        }
934    }
935
936    /**
937     * Returns a hash code for this set.
938     * <p>
939     * This method overrides the generic method provided by the superclass.
940     * Since <code>equals()</code> is not overriden, it is important that the
941     * value returned by this method is the same value as the one returned by
942     * the overriden method.
943     *
944     * @return a hash code for this set.
945     */
946    public int hashCode() {
947        int h = 0;
948        for (int j = realSize(), i = 0; j-- != 0; ) {
949            while (key[i] == null)
950                i++;
951            if (this != key[i])
952                h += hasher.hash(key[i]);
953            i++;
954        }
955        // Zero / null have hash zero.
956        return h;
957    }
958
959    public long hash64()
960    {
961        return 31L * size + CrossHash.hash64(key);
962    }
963
964    /**
965     * Returns the maximum number of entries that can be filled before rehashing.
966     *
967     * @param n the size of the backing array.
968     * @param f the load factor.
969     * @return the maximum number of entries before rehashing.
970     */
971    public static int maxFill(final int n, final float f) {
972        /* We must guarantee that there is always at least
973                 * one free entry (even with pathological load factors). */
974        return Math.min((int) Math.ceil(n * f), n - 1);
975    }
976
977    /**
978     * Returns the maximum number of entries that can be filled before rehashing.
979     *
980     * @param n the size of the backing array.
981     * @param f the load factor.
982     * @return the maximum number of entries before rehashing.
983     */
984    public static long maxFill(final long n, final float f) {
985                /* We must guarantee that there is always at least
986                 * one free entry (even with pathological load factors). */
987        return Math.min((long) Math.ceil(n * f), n - 1);
988    }
989
990    /**
991     * Returns the least power of two smaller than or equal to 2<sup>30</sup> and larger than or equal to <code>Math.ceil( expected / f )</code>.
992     *
993     * @param expected the expected number of elements in a hash table.
994     * @param f        the load factor.
995     * @return the minimum possible size for a backing array.
996     * @throws IllegalArgumentException if the necessary size is larger than 2<sup>30</sup>.
997     */
998    public static int arraySize(final int expected, final float f) {
999        final long s = Math.max(2, HashCommon.nextPowerOfTwo((long) Math.ceil(expected / f)));
1000        if (s > 1 << 30)
1001            throw new IllegalArgumentException("Too large (" + expected + " expected elements with load factor " + f + ")");
1002        return (int) s;
1003    }
1004
1005    @Override
1006    public Object[] toArray() {
1007        final Object[] a = new Object[size];
1008        objectUnwrap(iterator(), a);
1009        return a;
1010    }
1011
1012    @Override
1013    public <T> T[] toArray(T[] a) {
1014        final int size = this.size;
1015        objectUnwrap(iterator(), a);
1016        if (size < a.length)
1017            a[size] = null;
1018        return a;
1019    }
1020
1021
1022    /**
1023     * Unwraps an iterator into an array starting at a given offset for a given number of elements.
1024     * <p>
1025     * <P>This method iterates over the given type-specific iterator and stores the elements returned, up to a maximum of <code>length</code>, in the given array starting at <code>offset</code>. The
1026     * number of actually unwrapped elements is returned (it may be less than <code>max</code> if the iterator emits less than <code>max</code> elements).
1027     *
1028     * @param i      a type-specific iterator.
1029     * @param array  an array to contain the output of the iterator.
1030     * @param offset the first element of the array to be returned.
1031     * @param max    the maximum number of elements to unwrap.
1032     * @return the number of elements unwrapped.
1033     */
1034    private static <K> int objectUnwrap(final Iterator<? extends K> i, final K[] array, int offset, final int max) {
1035        if (max < 0) throw new IllegalArgumentException("The maximum number of elements (" + max + ") is negative");
1036        if (offset < 0 || offset + max > array.length) throw new IllegalArgumentException();
1037        int j = max;
1038        while (j-- != 0 && i.hasNext())
1039            array[offset++] = i.next();
1040        return max - j - 1;
1041    }
1042
1043    /**
1044     * Unwraps an iterator into an array.
1045     * <p>
1046     * <P>This method iterates over the given type-specific iterator and stores the elements returned in the given array. The iteration will stop when the iterator has no more elements or when the end
1047     * of the array has been reached.
1048     *
1049     * @param i     a type-specific iterator.
1050     * @param array an array to contain the output of the iterator.
1051     * @return the number of elements unwrapped.
1052     */
1053    private static <K> int objectUnwrap(final Iterator<? extends K> i, final K[] array) {
1054        return objectUnwrap(i, array, 0, array.length);
1055    }
1056
1057    @Override
1058    public String toString() {
1059        final StringBuilder s = new StringBuilder();
1060        int i = scanNext(-1);
1061        boolean first = true;
1062        s.append("OrderedSet{");
1063        while (i != -1) {
1064            if (first) first = false;
1065            else s.append(", ");
1066            s.append(key[i]);
1067            i = scanNext(i);
1068        }
1069        s.append("}");
1070        return s.toString();
1071    }
1072
1073    @Override
1074    public boolean equals(final Object o) {
1075        if (o == this)
1076            return true;
1077        if (!(o instanceof Set))
1078            return false;
1079        Set<?> s = (Set<?>) o;
1080        if (s.size() != size)
1081            return false;
1082        return containsAll(s);
1083    }
1084
1085    @GwtIncompatible
1086    private void writeObject(java.io.ObjectOutputStream s)
1087            throws java.io.IOException {
1088        final Iterator<K> i = iterator();
1089        s.defaultWriteObject();
1090        for (int j = size; j-- != 0; )
1091            s.writeObject(i.next());
1092    }
1093
1094    @GwtIncompatible
1095    @SuppressWarnings("unchecked")
1096    private void readObject(java.io.ObjectInputStream s)
1097            throws java.io.IOException, ClassNotFoundException {
1098        s.defaultReadObject();
1099        n = arraySize(size, f);
1100        maxFill = maxFill(n, f);
1101        mask = n - 1;
1102        final K[] key = this.key = (K[]) new Object[n + 1];
1103        K k;
1104        for (int i = size, pos; i-- != 0; ) {
1105            k = (K) s.readObject();
1106            if (k == null) {
1107                pos = n;
1108                containsNull = true;
1109            } else {
1110                if (!(key[pos = (hasher.hash(k)) & mask] == null))
1111                    while (!(key[pos = pos + 1 & mask] == null)) ;
1112            }
1113            key[pos] = k;
1114        }
1115    }
1116}