001package squidpony.squidmath;
002
003import java.util.Objects;
004
005/**
006 * Code used internally for hashing OrderedMap, OrderedSet, IntDoubleOrderedMap, Arrangement, and so on.
007 * Has some methods and constants that may be useful in other kinds of code.
008 * Created by Tommy Ettinger on 7/28/2017.
009 */
010public class HashCommon {
011    public static class EnumHasher implements CrossHash.IHasher
012    {
013        @Override
014        public int hash(Object data) {
015            return (data instanceof Enum) ? ((Enum)data).ordinal() : -1;
016        }
017
018        @Override
019        public boolean areEqual(Object left, Object right) {
020            return Objects.equals(left, right);
021        }
022    }
023    public static final EnumHasher enumHasher = new EnumHasher();
024
025    private HashCommon() {
026    }
027
028    /**
029     * 2<sup>32</sup> &middot; &phi;, &phi; = (&#x221A;5 &minus; 1)/2.
030     */
031    public static final int INT_PHI = 0x9E3779B9;
032    /**
033     * The reciprocal of {@link #INT_PHI} modulo 2<sup>32</sup>.
034     */
035    public static final int INV_INT_PHI = 0x144cbc89;
036    /**
037     * 2<sup>64</sup> &middot; &phi;, &phi; = (&#x221A;5 &minus; 1)/2.
038     */
039    public static final long LONG_PHI = 0x9E3779B97F4A7C15L;
040    /**
041     * The reciprocal of {@link #LONG_PHI} modulo 2<sup>64</sup>.
042     */
043    public static final long INV_LONG_PHI = 0xf1de83e19937733dL;
044
045    /**
046     * Quickly mixes the bits of an integer.
047     * <br>This method mixes the bits of the argument by multiplying by the golden ratio and
048     * xorshifting the result. It is borrowed from <a href="https://github.com/OpenHFT/Koloboke">Koloboke</a>, and
049     * it has slightly worse behaviour than MurmurHash3 (in open-addressing hash tables the average number of probes
050     * is slightly larger), but it's much faster.
051     *
052     * @param x an integer.
053     * @return a hash value obtained by mixing the bits of {@code x}.
054     //* @see #invMix(int)
055     */
056    static int mixOriginal(final int x) {
057        final int h = x * INT_PHI;
058        return h ^ (h >>> 16);
059    }
060    /**
061     * Thoroughly mixes the bits of an integer.
062     * <br>
063     * This method mixes the bits of the argument using a multiplication by a smaller int (19 bits) followed by XOR with
064     * two different rotations of the earlier product; it should work well even on GWT, where overflow can't be relied
065     * on without bitwise operations being used. The previous mix(int) method would lose precision rather than
066     * overflowing on GWT, which could have serious effects on the performance of a hash table (where lost precision
067     * means more collisions). This is a little slower than {@link #mix(int)}, and does almost exactly as well at
068     * avoiding collisions on most input, so mix() is preferred.
069     *
070     * @param x an integer.
071     * @return a hash value obtained by mixing the bits of {@code x}.
072     */
073    public static int mixOther(int x)
074    {
075//        x = ((x *= 0x62BD5) ^ x >>> 13) * ((x & 0xFFFF8) ^ 0xCD7B5);
076//        return ((x << 21) | (x >>> 11)) ^ (((x << 7) | (x >>> 25)) * 0x62BD5);
077        return (x *= 0x62BD5) ^ ((x << 17) | (x >>> 15)) ^ ((x << 9) | (x >>> 23));
078    }
079    /**
080     * Thoroughly mixes the bits of an integer.
081     * <br>
082     * This method acts like {@link #mixOriginal(int)} (which is used by Koloboke and Fastutil), but doesn't multiply by
083     * any too-large numbers to ease compatibility with GWT. Specifically, it multiplies {@code n} by {@code 0x9E375}
084     * (found using the golden ratio times 2 to the 20, minus 2 to improve quality slightly) then xors that with itself
085     * unsigned-right-shifted by 16 before returning. It tends to have less pathologically-bad cases than using an
086     * unmixed integer in a hash table, but will still often have more collisions than an unmixed integer if that hash
087     * table is filled with numbers that vary in their lower bits. The value of this is that when ints are given that
088     * only differ in their upper bits, if you didn't mix a hash code you would have 95% or higher collision rates in
089     * some cases. This acts as a safeguard for that kind of scenario.
090     * <br>
091     * This replaces {@link #mixOther(int)}, which is also GWT-compatible but is a little slower without offering any
092     * improvement in collision rates.
093     * <br>
094     * This is used in {@link IntDoubleOrderedMap} and {@link IntIntOrderedMap}, at the least. The algorithm this uses
095     * is also used by {@link CrossHash#defaultHasher}.
096     * @param n an integer.
097     * @return a hash value obtained by mixing the bits of {@code x}.
098     */
099    public static int mix(final int n){
100        final int h = n * 0x9E375;
101        return h ^ (h >>> 16);
102    }
103
104//    /**
105//     * The inverse of {@link #mix(int)}. This method is mainly useful to create unit tests.
106//     *
107//     * @param x an integer.
108//     * @return a value that passed through {@link #mix(int)} would give {@code x}.
109//     */
110//    static int invMix(final int x) {
111//        return (x ^ x >>> 16) * INV_INT_PHI;
112//    }
113
114    /**
115     * Quickly mixes the bits of a long integer.
116     * <br>This method mixes the bits of the argument by multiplying by the golden ratio and
117     * xorshifting twice the result. It is borrowed from <a href="https://github.com/OpenHFT/Koloboke">Koloboke</a>, and
118     * it has slightly worse behaviour than MurmurHash3 (in open-addressing hash tables the average number of probes
119     * is slightly larger), but it's much faster.
120     *
121     * @param x a long integer.
122     * @return a hash value obtained by mixing the bits of {@code x}.
123     * @see #invMix(long)
124     */
125    public static long mix(final long x) {
126        long h = x * LONG_PHI;
127        h ^= h >>> 32;
128        return h ^ (h >>> 16);
129    }
130
131    /**
132     * The inverse of {@link #mix(long)}. This method is mainly useful to create unit tests.
133     *
134     * @param x a long integer.
135     * @return a value that passed through {@link #mix(long)} would give {@code x}.
136     */
137    static long invMix(long x) {
138        x ^= x >>> 32;
139        x ^= x >>> 16;
140        return (x ^ x >>> 32) * INV_LONG_PHI;
141    }
142
143    /**
144     * Return the least power of two greater than or equal to the specified value.
145     * <br>
146     * Note that this function will return 1 when the argument is 0.
147     * <br>
148     * This is a cleaned-up Java version of <a href="https://jameshfisher.com/2018/03/30/round-up-power-2/">this C code</a>.
149     * @param x a non-negative int.
150     * @return the least power of two greater than or equal to the specified value.
151     */
152    public static int nextPowerOfTwo(final int x) {
153        return 1 << -Integer.numberOfLeadingZeros(x - 1);
154    }
155
156    /**
157     * Return the least power of two greater than or equal to the specified value.
158     * <br>
159     * Note that this function will return 1 when the argument is 0.
160     * <br>
161     * This is a cleaned-up Java version of <a href="https://jameshfisher.com/2018/03/30/round-up-power-2/">this C code</a>.
162     * @param x a non-negative long.
163     * @return the least power of two greater than or equal to the specified value.
164     */
165    public static long nextPowerOfTwo(final long x) {
166        return 1L << -Long.numberOfLeadingZeros(x - 1);
167    }
168}