/*
 * Copyright 2014 the original author or authors.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.simantics.scl.runtime.chr;

import static java.util.Arrays.binarySearch;

import java.util.Arrays;

/**
 * This class is adapted from MutableQHashObjSetGO class generated by Koloboke library.
 * It is used by code generated by SCL compiler.
 */
public class CHRHashIndex {

    private static final double MIN_LOAD = 1.0 / 3.0;
    private static final double MAX_LOAD = 2.0 / 3.0;
    private static final double TARGET_LOAD = 0.5;
    private static final double GROWTH_FACTOR = 2.0;
    private static final int INITIAL_CAPACITY = 10;

    private static final Object REMOVED = new Object();
    private static final Object FREE = null;

    ////////////////////////////
    // Fields

    /** The current number of occupied slots in the hash. */
    private int size;

    private int maxSize;

    /** The current number of free slots in the hash. */
    private int freeSlots;

    private int minFreeSlots;

    private int removedSlots;

    private Object[] set;

    private static int mix(int hash) {
        return hash & Integer.MAX_VALUE;
    }

    private boolean noRemoved() {
        return removedSlots == 0;
    }

    /**
     * Creates data structures with a prime capacity at or near the minimum
     * needed to hold {@code size} elements without triggering a rehash.
     *
     * <p>Should be called only in constructors and externalization code.
     */
    private void init(int size) {
        this.size = 0;
        internalInit(targetCapacity(size));
    }

    private void internalInit(int capacity) {
        initSlotCounts(capacity);
        allocateArrays(capacity);
    }

    private void initSlotCounts(int capacity) {
        // No sense in trying to rehash after each insertion
        // if the capacity is already reached the limit.
        maxSize = !isMaxCapacity(capacity) ? maxSize(capacity) : capacity - 1;
        minFreeSlots = minFreeSlots(capacity, size, MAX_LOAD, maxSize);
        int freeSlots = this.freeSlots = capacity - size;
        // free could be less than minFreeSlots only in case when capacity
        // is not sufficient to comply load factor (due to saturation with
        // Java array size limit). Set minFreeSlots to a half of free to avoid
        // too often (instant) rehashing in this case.
        if (freeSlots < minFreeSlots) this.minFreeSlots = (freeSlots + 1) / 2;
        removedSlots = 0;
    }

    private static int minFreeSlots(int capacity, int size, double maxLoad, int maxSize) {
        double load = (double) size / (double) capacity;
        // See "Tombstones purge from hashtable: theory and practice" wiki page
        double rehashLoad =
                0.55 + 0.721 * load - 0.274 * load * load;

        int minFreeSlots;
        // minFreeSlots shouldn't be less than `capacity - maxSize`
        if (rehashLoad > maxLoad) {
            minFreeSlots = (int) ((double) capacity * (1.0 - rehashLoad));
        } else {
            minFreeSlots = capacity - maxSize;
        }
        // Need at least one free slot for open addressing
        return minFreeSlots > 0 ? minFreeSlots : 1;
    }

    /////////////////////////////
    // Modification hooks and rehash logic

    public boolean shrink() {
        int newCapacity = targetCapacity(size);
        if (removedSlots > 0 || newCapacity < set.length) {
            rehash(newCapacity);
            return true;
        } else {
            return false;
        }
    }

    private boolean tryRehashForExpansion(int newCapacity) {
        // No sense in rehashing for expansion if we already reached Java array
        // size limit.
        if (newCapacity > set.length || removedSlots > 0) {
            rehash(newCapacity);
            return true;
        } else {
            if (freeSlots < minFreeSlots)
                minFreeSlots = (freeSlots + 1) / 2;
            return false;
        }
    }

    public boolean ensureCapacity(long minSize) {
        int intMinSize = (int) Math.min(minSize, (long) Integer.MAX_VALUE);
        if (minSize < 0L)
            throw new IllegalArgumentException(
                    "Min size should be positive, " + minSize + " given.");
        int additionalSize = intMinSize - size;
        if (additionalSize <= 0)
            return false;
        if (intMinSize > maxSize || freeSlots - additionalSize < minFreeSlots) {
            return tryRehashForExpansion(targetCapacity(intMinSize));
        } else {
            return false;
        }
    }

    private void postRemoveHook() {
        size--;
        removedSlots++;
    }

    private void postFreeSlotInsertHook() {
        if (++size > maxSize) {
            if (tryRehashForExpansion(grownCapacity()))
                return;
        }
        if (--freeSlots < minFreeSlots) {
            if (!tryRehashIfTooFewFreeSlots() && freeSlots == 0) {
                throw new CHRHashOverflowException();
            }
        }
    }

    private void postRemovedSlotInsertHook() {
        if (++size > maxSize) {
            if (tryRehashForExpansion(grownCapacity()))
                return;
        }
        removedSlots--;
    }

    private boolean tryRehashIfTooFewFreeSlots() {
        if (removedSlots > 0) {
            rehash(targetCapacity(size));
            return true;
        } else {
            return tryRehashForExpansion(grownCapacity());
        }
    }

    /** For initial hash table construction and rehash to target load (shrink, tombstones purge). */
    private int targetCapacity(int size) {
        return capacity(size, targetLoadInverse.scaleUpper(size));
    }
    
    /** The highest qHash prime below Integer.MAX_VALUE (which is a qHash prime too). */
    private static final int MAX_INT_CAPACITY = 2147483587;


    private boolean isMaxCapacity(int capacity) {
        return capacity >= MAX_INT_CAPACITY;
    }

    private int grownCapacity() {
        return nearestGreaterCapacity(grow(set.length), size);
    }

    protected boolean keyEquals(Object a, Object b) {
        return a.equals(b);
    }

    protected int keyHashCode(Object key) {
        return key.hashCode();
    }


    public boolean contains(Object key) {
        return index(key) >= 0;
    }

    private int index(Object key) {
        // noinspection unchecked
        Object[] keys = set;
        int capacity, index;
        Object cur;
        if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) == key) {
            // key is present
            return index;
        } else {
            if (cur == FREE) {
                // key is absent, free slot
                return -1;
            } else {
                if (cur != REMOVED) {
                    if (keyEquals(key, cur)) {
                        // key is present
                        return index;
                    } else {
                        if (noRemoved()) {
                            int bIndex = index, fIndex = index, step = 1;
                            while (true) {
                                if ((bIndex -= step) < 0) bIndex += capacity;
                                if ((cur = keys[bIndex]) == key) {
                                    // key is present
                                    return bIndex;
                                } else if (cur == FREE) {
                                    // key is absent, free slot
                                    return -1;
                                }
                                else if (keyEquals(key, cur)) {
                                    // key is present
                                    return bIndex;
                                }
                                int t;
                                if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                                if ((cur = keys[fIndex]) == key) {
                                    // key is present
                                    return fIndex;
                                } else if (cur == FREE) {
                                    // key is absent, free slot
                                    return -1;
                                }
                                else if (keyEquals(key, cur)) {
                                    // key is present
                                    return fIndex;
                                }
                                step += 2;
                            }
                        }
                    }
                }
                int bIndex = index, fIndex = index, step = 1;
                while (true) {
                    if ((bIndex -= step) < 0) bIndex += capacity;
                    if ((cur = keys[bIndex]) == key) {
                        // key is present
                        return bIndex;
                    } else if (cur == FREE) {
                        // key is absent, free slot
                        return -1;
                    }
                    else if (cur != REMOVED && keyEquals(key, cur)) {
                        // key is present
                        return bIndex;
                    }
                    int t;
                    if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                    if ((cur = keys[fIndex]) == key) {
                        // key is present
                        return fIndex;
                    } else if (cur == FREE) {
                        // key is absent, free slot
                        return -1;
                    }
                    else if (cur != REMOVED && keyEquals(key, cur)) {
                        // key is present
                        return fIndex;
                    }
                    step += 2;
                }
            }
        }
    }

    private void allocateArrays(int capacity) {
        set = new Object[capacity];
        // not necessary because FREE = null
        // Arrays.fill(set, FREE);
    }


    public Object[] toArray() {
        Object[] result = new Object[size];
        if (size == 0)
            return result;
        int resultIndex = 0;
        Object[] keys = set;
        if (noRemoved()) {
            for (int i = keys.length - 1; i >= 0; i--) {
                Object key;
                // noinspection unchecked
                if ((key = keys[i]) != FREE) {
                    result[resultIndex++] = key;
                }
            }
        } else {
            for (int i = keys.length - 1; i >= 0; i--) {
                Object key;
                // noinspection unchecked
                if ((key = keys[i]) != FREE && key != REMOVED) {
                    result[resultIndex++] = key;
                }
            }
        }
        return result;
    }

    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size) {
            Class<?> elementType = a.getClass().getComponentType();
            a = (T[]) java.lang.reflect.Array.newInstance(elementType, size);
        }
        if (size == 0) {
            if (a.length > 0)
                a[0] = null;
            return a;
        }
        int resultIndex = 0;
        Object[] keys = set;
        if (noRemoved()) {
            for (int i = keys.length - 1; i >= 0; i--) {
                Object key;
                // noinspection unchecked
                if ((key = keys[i]) != FREE) {
                    a[resultIndex++] = (T) key;
                }
            }
        } else {
            for (int i = keys.length - 1; i >= 0; i--) {
                Object key;
                // noinspection unchecked
                if ((key = keys[i]) != FREE && key != REMOVED) {
                    a[resultIndex++] = (T) key;
                }
            }
        }
        if (a.length > resultIndex)
            a[resultIndex] = null;
        return a;
    }

    private void rehash(int newCapacity) {
        Object[] keys = set;
        int removedSlots = this.removedSlots;
        internalInit(newCapacity);
        Object[] newKeys = set;
        int capacity = newKeys.length;
        if (removedSlots == 0) {
            for (int i = keys.length - 1; i >= 0; i--) {
                Object key;
                // noinspection unchecked
                if ((key = keys[i]) != FREE) {
                    int index;
                    if (newKeys[index = mix(keyHashCode(key)) % capacity] != FREE) {
                        int bIndex = index, fIndex = index, step = 1;
                        while (true) {
                            if ((bIndex -= step) < 0) bIndex += capacity;
                            if (newKeys[bIndex] == FREE) {
                                index = bIndex;
                                break;
                            }
                            int t;
                            if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                            if (newKeys[fIndex] == FREE) {
                                index = fIndex;
                                break;
                            }
                            step += 2;
                        }
                    }
                    newKeys[index] = key;
                }
            }
        } else {
            for (int i = keys.length - 1; i >= 0; i--) {
                Object key;
                // noinspection unchecked
                if ((key = keys[i]) != FREE && key != REMOVED) {
                    int index;
                    if (newKeys[index = mix(keyHashCode(key)) % capacity] != FREE) {
                        int bIndex = index, fIndex = index, step = 1;
                        while (true) {
                            if ((bIndex -= step) < 0) bIndex += capacity;
                            if (newKeys[bIndex] == FREE) {
                                index = bIndex;
                                break;
                            }
                            int t;
                            if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                            if (newKeys[fIndex] == FREE) {
                                index = fIndex;
                                break;
                            }
                            step += 2;
                        }
                    }
                    newKeys[index] = key;
                }
            }
        }
    }

    public void clear() {
        size = 0;
        freeSlots = set.length;
        removedSlots = 0;
        Arrays.fill(set, FREE);
    }


    public CHRHashIndex() {
        init(INITIAL_CAPACITY);
    }

    public boolean add(Object key) {
        Object[] keys = set;
        int capacity, index;
        Object cur;
        keyAbsentFreeSlot:
            if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) != FREE) {
                if (cur == key) {
                    // key is present
                    return false;
                } else {
                    int firstRemoved;
                    if (cur != REMOVED) {
                        if (!keyEquals(key, cur)) {
                            if (noRemoved()) {
                                int bIndex = index, fIndex = index, step = 1;
                                while (true) {
                                    if ((bIndex -= step) < 0) bIndex += capacity;
                                    if ((cur = keys[bIndex]) == FREE) {
                                        index = bIndex;
                                        break keyAbsentFreeSlot;
                                    } else if (cur == key || (keyEquals(key, cur))) {
                                        // key is present
                                        return false;
                                    }
                                    int t;
                                    if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                                    if ((cur = keys[fIndex]) == FREE) {
                                        index = fIndex;
                                        break keyAbsentFreeSlot;
                                    } else if (cur == key || (keyEquals(key, cur))) {
                                        // key is present
                                        return false;
                                    }
                                    step += 2;
                                }
                            } else {
                                firstRemoved = -1;
                            }
                        } else {
                            // key is present
                            return false;
                        }
                    } else {
                        firstRemoved = index;
                    }
                    keyAbsentRemovedSlot: {
                        int bIndex = index, fIndex = index, step = 1;
                        while (true) {
                            if ((bIndex -= step) < 0) bIndex += capacity;
                            if ((cur = keys[bIndex]) == FREE) {
                                if (firstRemoved < 0) {
                                    index = bIndex;
                                    break keyAbsentFreeSlot;
                                } else {
                                    break keyAbsentRemovedSlot;
                                }
                            } else if (cur == key) {
                                // key is present
                                return false;
                            } else if (cur != REMOVED) {
                                if (keyEquals(key, cur)) {
                                    // key is present
                                    return false;
                                }
                            } else if (firstRemoved < 0) {
                                firstRemoved = bIndex;
                            }
                            int t;
                            if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                            if ((cur = keys[fIndex]) == FREE) {
                                if (firstRemoved < 0) {
                                    index = fIndex;
                                    break keyAbsentFreeSlot;
                                } else {
                                    break keyAbsentRemovedSlot;
                                }
                            } else if (cur == key) {
                                // key is present
                                return false;
                            } else if (cur != REMOVED) {
                                if (keyEquals(key, cur)) {
                                    // key is present
                                    return false;
                                }
                            } else if (firstRemoved < 0) {
                                firstRemoved = fIndex;
                            }
                            step += 2;
                        }
                    }
                    // key is absent, removed slot
                    keys[firstRemoved] = key;
                    postRemovedSlotInsertHook();
                    return true;
                }
            }
        // key is absent, free slot
        keys[index] = key;
        postFreeSlotInsertHook();
        return true;
    }

    /**
     * Assumes that the given value doesn't already exist in the index
     * (only optimized with this assumption, the method works correctly
     * even if the assumption does not hold).
     * Returns the old equal element that the given value replaces or
     * null if there is no such elements.
     */
    public Object addFreshAndReturnOld(Object key) {
        Object[] keys = set;
        int capacity, index;
        Object cur;
        keyAbsentFreeSlot: if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) != FREE) {
            int firstRemoved;
            if (cur != REMOVED) {
                if (!keyEquals(key, cur)) {
                    if (noRemoved()) {
                        int bIndex = index, fIndex = index, step = 1;
                        while (true) {
                            if ((bIndex -= step) < 0) bIndex += capacity;
                            if ((cur = keys[bIndex]) == FREE) {
                                index = bIndex;
                                break keyAbsentFreeSlot;
                            } else if (keyEquals(key, cur)) {
                                keys[bIndex] = key;
                                return cur;
                            }
                            int t;
                            if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                            if ((cur = keys[fIndex]) == FREE) {
                                index = fIndex;
                                break keyAbsentFreeSlot;
                            } else if (keyEquals(key, cur)) {
                                keys[fIndex] = key;
                                return cur;
                            }
                            step += 2;
                        }
                    } else {
                        firstRemoved = -1;
                    }
                } else {
                    keys[index] = key;
                    return cur;
                }
            } else {
                firstRemoved = index;
            }
            keyAbsentRemovedSlot: {
                int bIndex = index, fIndex = index, step = 1;
                while (true) {
                    if ((bIndex -= step) < 0) bIndex += capacity;
                    if ((cur = keys[bIndex]) == FREE) {
                        if (firstRemoved < 0) {
                            index = bIndex;
                            break keyAbsentFreeSlot;
                        } else {
                            break keyAbsentRemovedSlot;
                        }
                    } else if (cur != REMOVED) {
                        if (keyEquals(key, cur)) {
                            keys[bIndex] = key;
                            return cur;
                        }
                    } else if (firstRemoved < 0) {
                        firstRemoved = bIndex;
                    }
                    int t;
                    if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                    if ((cur = keys[fIndex]) == FREE) {
                        if (firstRemoved < 0) {
                            index = fIndex;
                            break keyAbsentFreeSlot;
                        } else {
                            break keyAbsentRemovedSlot;
                        }
                    } else if (cur != REMOVED) {
                        if (keyEquals(key, cur)) {
                            keys[fIndex] = key;
                            return cur;
                        }
                    } else if (firstRemoved < 0) {
                        firstRemoved = fIndex;
                    }
                    step += 2;
                }
            }
            // key is absent, removed slot
            keys[firstRemoved] = key;
            postRemovedSlotInsertHook();
            return null;
        }
        // key is absent, free slot
        keys[index] = key;
        postFreeSlotInsertHook();
        return null;
    }
    
    public Object addFreshAndReturnOldNoRemovals(Object key) {
        Object[] keys = set;
        int capacity, index;
        Object cur;
        keyAbsentFreeSlot: if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) != FREE) {
            if (!keyEquals(key, cur)) {
                int bIndex = index, fIndex = index, step = 1;
                while (true) {
                    if ((bIndex -= step) < 0) bIndex += capacity;
                    if ((cur = keys[bIndex]) == FREE) {
                        index = bIndex;
                        break keyAbsentFreeSlot;
                    } else if (keyEquals(key, cur)) {
                        keys[bIndex] = key;
                        return cur;
                    }
                    int t;
                    if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                    if ((cur = keys[fIndex]) == FREE) {
                        index = fIndex;
                        break keyAbsentFreeSlot;
                    } else if (keyEquals(key, cur)) {
                        keys[fIndex] = key;
                        return cur;
                    }
                    step += 2;
                }
            } else {
                keys[index] = key;
                return cur;
            }
        }
        // key is absent, free slot
        keys[index] = key;
        postFreeSlotInsertHook();
        return null;
    }

    public boolean remove(Object key) {
        // noinspection unchecked
        Object[] keys = set;
        int capacity, index;
        Object cur;
        keyPresent:
            if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) != key) {
                if (cur == FREE) {
                    // key is absent, free slot
                    return false;
                } else {
                    if (cur != REMOVED) {
                        if (keyEquals(key, cur)) {
                            break keyPresent;
                        } else {
                            if (noRemoved()) {
                                int bIndex = index, fIndex = index, step = 1;
                                while (true) {
                                    if ((bIndex -= step) < 0) bIndex += capacity;
                                    if ((cur = keys[bIndex]) == key) {
                                        index = bIndex;
                                        break keyPresent;
                                    } else if (cur == FREE) {
                                        // key is absent, free slot
                                        return false;
                                    }
                                    else if (keyEquals(key, cur)) {
                                        index = bIndex;
                                        break keyPresent;
                                    }
                                    int t;
                                    if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                                    if ((cur = keys[fIndex]) == key) {
                                        index = fIndex;
                                        break keyPresent;
                                    } else if (cur == FREE) {
                                        // key is absent, free slot
                                        return false;
                                    }
                                    else if (keyEquals(key, cur)) {
                                        index = fIndex;
                                        break keyPresent;
                                    }
                                    step += 2;
                                }
                            }
                        }
                    }
                    int bIndex = index, fIndex = index, step = 1;
                    while (true) {
                        if ((bIndex -= step) < 0) bIndex += capacity;
                        if ((cur = keys[bIndex]) == key) {
                            index = bIndex;
                            break keyPresent;
                        } else if (cur == FREE) {
                            // key is absent, free slot
                            return false;
                        }
                        else if (cur != REMOVED && keyEquals(key, cur)) {
                            index = bIndex;
                            break keyPresent;
                        }
                        int t;
                        if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                        if ((cur = keys[fIndex]) == key) {
                            index = fIndex;
                            break keyPresent;
                        } else if (cur == FREE) {
                            // key is absent, free slot
                            return false;
                        }
                        else if (cur != REMOVED && keyEquals(key, cur)) {
                            index = fIndex;
                            break keyPresent;
                        }
                        step += 2;
                    }
                }
            }
        // key is present
        keys[index] = REMOVED;
        postRemoveHook();
        return true;
    }
    
    /**
     * Assumes that the key exists in the index. Removes it.
     */
    public void removeKnownToExistKey(Object key) {
        Object[] keys = set;
        int capacity, index;
        keyPresent: if (keys[index = mix(keyHashCode(key)) % (capacity = keys.length)] != key) {
            int bIndex = index, fIndex = index, step = 1;
            while (true) {
                if ((bIndex -= step) < 0) bIndex += capacity;
                if (keys[bIndex] == key) {
                    index = bIndex;
                    break keyPresent;
                }
                int t;
                if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                if (keys[fIndex] == key) {
                    index = fIndex;
                    break keyPresent;
                }
                step += 2;
            }
        }
        keys[index] = REMOVED;
        postRemoveHook();
    }
    
    /**
     * Assumes that the key exists in the index. Replaces it with an equal key.
     */
    public void replaceKnownToExistKey(Object key, Object replacement) {
        Object[] keys = set;
        int capacity, index;
        keyPresent: if (keys[index = mix(keyHashCode(key)) % (capacity = keys.length)] != key) {
            int bIndex = index, fIndex = index, step = 1;
            while (true) {
                if ((bIndex -= step) < 0) bIndex += capacity;
                if (keys[bIndex] == key) {
                    index = bIndex;
                    break keyPresent;
                }
                int t;
                if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                if (keys[fIndex] == key) {
                    index = fIndex;
                    break keyPresent;
                }
                step += 2;
            }
        }
        keys[index] = replacement;
    }

    public Object getEqual(Object key) {
        // noinspection unchecked
        Object[] keys = set;
        int capacity, index;
        Object cur;
        if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) == FREE)
            return null;
        if (cur != REMOVED) {
            if (keyEquals(key, cur))
                return cur;
            if (noRemoved()) {
                int bIndex = index, fIndex = index, step = 1;
                while (true) {
                    if ((bIndex -= step) < 0) bIndex += capacity;
                    if ((cur = keys[bIndex]) == FREE)
                        return null;
                    else if (keyEquals(key, cur))
                        return cur;
                    int t;
                    if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
                    if ((cur = keys[fIndex]) == FREE)
                        return null;
                    else if (keyEquals(key, cur))
                        return cur;
                    step += 2;
                }
            }
        }
        int bIndex = index, fIndex = index, step = 1;
        while (true) {
            if ((bIndex -= step) < 0) bIndex += capacity;
            if ((cur = keys[bIndex]) == FREE)
                return null;
            else if (cur != REMOVED && keyEquals(key, cur))
                return cur;
            int t;
            if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
            if ((cur = keys[fIndex]) == FREE)
                return null;
            else if (cur != REMOVED && keyEquals(key, cur))
                return cur;
            step += 2;
        }
    }

    public Object getEqualNoRemovals(Object key) {
        Object[] keys = set;
        int capacity, index;
        Object cur;
        if ((cur = keys[index = mix(keyHashCode(key)) % (capacity = keys.length)]) == FREE)
            return null;
        if (keyEquals(key, cur))
            return cur;
        int bIndex = index, fIndex = index, step = 1;
        while (true) {
            if ((bIndex -= step) < 0) bIndex += capacity;
            if ((cur = keys[bIndex]) == FREE)
                return null;
            else if (keyEquals(key, cur))
                return cur;
            int t;
            if ((t = (fIndex += step) - capacity) >= 0) fIndex = t;
            if ((cur = keys[fIndex]) == FREE)
                return null;
            else if (keyEquals(key, cur))
                return cur;
            step += 2;
        }
    }
    
    private static final Scaler minLoadInverse = Scaler.by(1.0 / MIN_LOAD);
    private static final Scaler targetLoadInverse = Scaler.by(1.0 / TARGET_LOAD);
    private static final Scaler maxLoad = Scaler.by(MAX_LOAD);
    private static final Scaler maxLoadInverse = Scaler.by(1.0 / MAX_LOAD);
    private static final Scaler growthFactor = Scaler.by(GROWTH_FACTOR);

    /**
     * Computes hash table capacity for the given size and min load of this config.
     *
     * @param size size of the hash table to compute capacity for
     * @return if the given size is non-negative, returns the least int capacity such that
     *         size / capacity < {@code config().getMinLoad()}, or {@code Integer.MAX_VALUE}
     *         if there is no such capacity. If size is negative, result is undefined.
     */
    private static int maxCapacity(int size) {
        return minLoadInverse.scaleUpper(size);
    }

    /**
     * Computes hash table capacity for the given size and max load of this config.
     *
     * @param size size of the hash table to compute capacity for
     * @return if the given size is non-negative, returns the least int capacity such that
     *         size / capacity < {@code config().getMaxLoad()}, or {@code Integer.MAX_VALUE}
     *         if there is no such capacity. If size is negative, result is undefined.
     */
    private static int minCapacity(int size) {
        return maxLoadInverse.scaleUpper(size);
    }

    private static int maxSize(int capacity) {
        return maxLoad.scaleLower(capacity);
    }

    /**
     * Computes grown hash table capacity for the given capacity and growth factor of this config.
     *
     * @param capacity capacity of the hash table to grow
     * @return if the given capacity is non-negative, returns the least int capacity
     *         such that |new capacity - the given capacity * {@code config().getGrowthFactor()}| <
     *         1, or {@code Integer.MAX_VALUE} if there is no such capacity.
     *         If the given capacity is negative, result is undefined.
     */
    private static int grow(int capacity) {
        return growthFactor.scaleLower(capacity);
    }
    
    /**
     * Chooses lesser or greater capacity, which one is better for the given {@code size} and
     * hash config. (The {@code desiredCapacity} is just precomputed
     * {@code conf.targetCapacity(size)}).
     *
     * <p>Chooses the capacity which is closer to the {@code desiredCapacity} and conform min or
     * max capacity bounds for the given {@code size} and hash config.
     *
     * <p>If both {@code lesserCapacity} and {@code greaterCapacity} are out of these bounds,
     * {@code onFail} value is returned.
     *
     * @param conf the {@code HashConfigWrapper}
     * @param size should be non-negative
     * @param desiredCapacity precomputed {@code conf.targetCapacity(size)}
     * @param lesserCapacity should be greater than the {@code size} but lesser
     *        than the {@code desiredCapacity}
     * @param greaterCapacity should be greater than the {@code desiredCapacity}
     * @param onFail the value to return if both {@code lesserCapacity} and {@code greaterCapacity}
     *        are lesser than min size and greater than max size respectively
     *        for the given hash config and size
     * @return {@code lesserCapacity} or {@code greaterCapacity}
     * @see #chooseBetter(HashConfigWrapper, long, long, long, long, long)
     */
    private static int chooseBetter(int size,
            int desiredCapacity, int lesserCapacity, int greaterCapacity, int onFail) {
        assert 0 <= size;
        assert size < lesserCapacity && lesserCapacity < desiredCapacity;
        assert desiredCapacity < greaterCapacity;
        if (greaterCapacity - desiredCapacity <= desiredCapacity - lesserCapacity &&
                greaterCapacity <= maxCapacity(size)) {
            return greaterCapacity;
        }
        return lesserCapacity >= minCapacity(size) ? lesserCapacity : onFail;
    }
    
    private static int capacity(int size, int desiredCapacity) {
        int lesserCapacity, greaterCapacity;
        if (desiredCapacity <= MAX_LOOKUP_CAPACITY) {
            int smallTableIndex = SMALL_LOOKUP_TABLE_INDICES[desiredCapacity];
            greaterCapacity = SMALL_LOOKUP_TABLE_CAPACITIES[smallTableIndex];
            if (greaterCapacity == desiredCapacity || smallTableIndex == 0)
                return greaterCapacity;
            lesserCapacity = SMALL_LOOKUP_TABLE_CAPACITIES[smallTableIndex - 1];
        }
        else if (desiredCapacity <= MAX_REGULAR_CHAR_CAPACITY) {
            int capIndex = binarySearch(REGULAR_CHAR_CAPACITIES, (char) desiredCapacity);
            if (capIndex >= 0) // desiredCapacity is found in REGULAR_CHAR_CAPACITIES
                return desiredCapacity;
            capIndex = ~capIndex;
            lesserCapacity = capIndex > 0 ?
                    (int) REGULAR_CHAR_CAPACITIES[capIndex - 1] : MAX_LOOKUP_CAPACITY;
            greaterCapacity = REGULAR_CHAR_CAPACITIES[capIndex];
        }
        else if (desiredCapacity <= MAX_REGULAR_INT_CAPACITY) {
            int capIndex = binarySearch(REGULAR_INT_CAPACITIES, desiredCapacity);
            if (capIndex >= 0) // desiredCapacity is found in REGULAR_INT_CAPACITIES
                return desiredCapacity;
            capIndex = ~capIndex;
            lesserCapacity = capIndex > 0 ?
                    REGULAR_INT_CAPACITIES[capIndex - 1] : MAX_REGULAR_CHAR_CAPACITY;
            greaterCapacity = REGULAR_INT_CAPACITIES[capIndex];
        }
        else {
            // Since size could be virtual (expected), don't prematurely throw
            // HashOverflowException. If sizes near to Integer.MAX_VALUE is the case,
            // version accepting long size should be used.
            return MAX_INT_CAPACITY;
        }
        return chooseBetter(size, desiredCapacity, lesserCapacity, greaterCapacity,
                greaterCapacity);
    }

    /** For grow rehash. */
    private static int nearestGreaterCapacity(int desiredCapacity, int currentSize) {
        assert currentSize >= 0 : "currentSize must be non-negative";
        if (desiredCapacity <= MAX_LOOKUP_CAPACITY)
            return SMALL_LOOKUP_TABLE_CAPACITIES[SMALL_LOOKUP_TABLE_INDICES[desiredCapacity]];
        if (desiredCapacity <= MAX_REGULAR_CHAR_CAPACITY) {
            int capIndex = binarySearch(REGULAR_CHAR_CAPACITIES, (char) desiredCapacity);
            // capIndex >= 0 => desiredCapacity IS a regular capacity
            return capIndex < 0 ? REGULAR_CHAR_CAPACITIES[~capIndex] : desiredCapacity;
        }
        final boolean simpleArrays = true;
        if (desiredCapacity <= MAX_REGULAR_INT_CAPACITY) {
            int capIndex = binarySearch(REGULAR_INT_CAPACITIES, desiredCapacity);
            return capIndex < 0 ? REGULAR_INT_CAPACITIES[~capIndex] : desiredCapacity;
        }
        int maxCapacity = MAX_INT_CAPACITY;
        // overflow-aware
        if (currentSize - maxCapacity < 0)
            return maxCapacity;
        if (simpleArrays && currentSize - Integer.MAX_VALUE < 0) {
            // Integer.MAX_VALUE is also a qHash prime, but likely will cause OutOfMemoryError
            return Integer.MAX_VALUE;
        } else {
            // QHash must have at least 1 free slot
            throw new CHRHashOverflowException();
        }
    }

    private static final char[] SMALL_LOOKUP_TABLE_CAPACITIES = new char[] {
            7, 11, 19, 23, 31, 43, 47, 59, 67, 71,
            79, 83, 103, 107, 127, 131, 139, 151, 163, 167,
            179, 191, 199, 211, 223, 227, 239, 251, 263, 271,
            283, 307, 311, 331, 347, 359, 367, 379, 383, 419,
            431, 439, 443, 463, 467, 479, 487, 491, 499, 503,
            523, 547, 563, 571, 587, 599, 607, 619, 631, 643,
            647, 659, 683, 691, 719, 727, 739, 743, 751, 787,
            811, 823, 827, 839, 859, 863, 883, 887, 907, 911,
            919, 947, 967, 971, 983, 991, 1019
    };

    private static final byte[] SMALL_LOOKUP_TABLE_INDICES = new byte[] {
            0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
            1, 1, 2, 2, 2, 2, 2, 2, 2, 2,
            3, 3, 3, 3, 4, 4, 4, 4, 4, 4,
            4, 4, 5, 5, 5, 5, 5, 5, 5, 5,
            5, 5, 5, 5, 6, 6, 6, 6, 7, 7,
            7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
            8, 8, 8, 8, 8, 8, 8, 8, 9, 9,
            9, 9, 10, 10, 10, 10, 10, 10, 10, 10,
            11, 11, 11, 11, 12, 12, 12, 12, 12, 12,
            12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
            12, 12, 12, 12, 13, 13, 13, 13, 14, 14,
            14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
            14, 14, 14, 14, 14, 14, 14, 14, 15, 15,
            15, 15, 16, 16, 16, 16, 16, 16, 16, 16,
            17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
            17, 17, 18, 18, 18, 18, 18, 18, 18, 18,
            18, 18, 18, 18, 19, 19, 19, 19, 20, 20,
            20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
            21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
            21, 21, 22, 22, 22, 22, 22, 22, 22, 22,
            23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
            23, 23, 24, 24, 24, 24, 24, 24, 24, 24,
            24, 24, 24, 24, 25, 25, 25, 25, 26, 26,
            26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
            27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
            27, 27, 28, 28, 28, 28, 28, 28, 28, 28,
            28, 28, 28, 28, 29, 29, 29, 29, 29, 29,
            29, 29, 30, 30, 30, 30, 30, 30, 30, 30,
            30, 30, 30, 30, 31, 31, 31, 31, 31, 31,
            31, 31, 31, 31, 31, 31, 31, 31, 31, 31,
            31, 31, 31, 31, 31, 31, 31, 31, 32, 32,
            32, 32, 33, 33, 33, 33, 33, 33, 33, 33,
            33, 33, 33, 33, 33, 33, 33, 33, 33, 33,
            33, 33, 34, 34, 34, 34, 34, 34, 34, 34,
            34, 34, 34, 34, 34, 34, 34, 34, 35, 35,
            35, 35, 35, 35, 35, 35, 35, 35, 35, 35,
            36, 36, 36, 36, 36, 36, 36, 36, 37, 37,
            37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
            38, 38, 38, 38, 39, 39, 39, 39, 39, 39,
            39, 39, 39, 39, 39, 39, 39, 39, 39, 39,
            39, 39, 39, 39, 39, 39, 39, 39, 39, 39,
            39, 39, 39, 39, 39, 39, 39, 39, 39, 39,
            40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
            40, 40, 41, 41, 41, 41, 41, 41, 41, 41,
            42, 42, 42, 42, 43, 43, 43, 43, 43, 43,
            43, 43, 43, 43, 43, 43, 43, 43, 43, 43,
            43, 43, 43, 43, 44, 44, 44, 44, 45, 45,
            45, 45, 45, 45, 45, 45, 45, 45, 45, 45,
            46, 46, 46, 46, 46, 46, 46, 46, 47, 47,
            47, 47, 48, 48, 48, 48, 48, 48, 48, 48,
            49, 49, 49, 49, 50, 50, 50, 50, 50, 50,
            50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
            50, 50, 50, 50, 51, 51, 51, 51, 51, 51,
            51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
            51, 51, 51, 51, 51, 51, 51, 51, 52, 52,
            52, 52, 52, 52, 52, 52, 52, 52, 52, 52,
            52, 52, 52, 52, 53, 53, 53, 53, 53, 53,
            53, 53, 54, 54, 54, 54, 54, 54, 54, 54,
            54, 54, 54, 54, 54, 54, 54, 54, 55, 55,
            55, 55, 55, 55, 55, 55, 55, 55, 55, 55,
            56, 56, 56, 56, 56, 56, 56, 56, 57, 57,
            57, 57, 57, 57, 57, 57, 57, 57, 57, 57,
            58, 58, 58, 58, 58, 58, 58, 58, 58, 58,
            58, 58, 59, 59, 59, 59, 59, 59, 59, 59,
            59, 59, 59, 59, 60, 60, 60, 60, 61, 61,
            61, 61, 61, 61, 61, 61, 61, 61, 61, 61,
            62, 62, 62, 62, 62, 62, 62, 62, 62, 62,
            62, 62, 62, 62, 62, 62, 62, 62, 62, 62,
            62, 62, 62, 62, 63, 63, 63, 63, 63, 63,
            63, 63, 64, 64, 64, 64, 64, 64, 64, 64,
            64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
            64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
            65, 65, 65, 65, 65, 65, 65, 65, 66, 66,
            66, 66, 66, 66, 66, 66, 66, 66, 66, 66,
            67, 67, 67, 67, 68, 68, 68, 68, 68, 68,
            68, 68, 69, 69, 69, 69, 69, 69, 69, 69,
            69, 69, 69, 69, 69, 69, 69, 69, 69, 69,
            69, 69, 69, 69, 69, 69, 69, 69, 69, 69,
            69, 69, 69, 69, 69, 69, 69, 69, 70, 70,
            70, 70, 70, 70, 70, 70, 70, 70, 70, 70,
            70, 70, 70, 70, 70, 70, 70, 70, 70, 70,
            70, 70, 71, 71, 71, 71, 71, 71, 71, 71,
            71, 71, 71, 71, 72, 72, 72, 72, 73, 73,
            73, 73, 73, 73, 73, 73, 73, 73, 73, 73,
            74, 74, 74, 74, 74, 74, 74, 74, 74, 74,
            74, 74, 74, 74, 74, 74, 74, 74, 74, 74,
            75, 75, 75, 75, 76, 76, 76, 76, 76, 76,
            76, 76, 76, 76, 76, 76, 76, 76, 76, 76,
            76, 76, 76, 76, 77, 77, 77, 77, 78, 78,
            78, 78, 78, 78, 78, 78, 78, 78, 78, 78,
            78, 78, 78, 78, 78, 78, 78, 78, 79, 79,
            79, 79, 80, 80, 80, 80, 80, 80, 80, 80,
            81, 81, 81, 81, 81, 81, 81, 81, 81, 81,
            81, 81, 81, 81, 81, 81, 81, 81, 81, 81,
            81, 81, 81, 81, 81, 81, 81, 81, 82, 82,
            82, 82, 82, 82, 82, 82, 82, 82, 82, 82,
            82, 82, 82, 82, 82, 82, 82, 82, 83, 83,
            83, 83, 84, 84, 84, 84, 84, 84, 84, 84,
            84, 84, 84, 84, 85, 85, 85, 85, 85, 85,
            85, 85, 86, 86, 86, 86, 86, 86, 86, 86,
            86, 86, 86, 86, 86, 86, 86, 86, 86, 86,
            86, 86, 86, 86, 86, 86, 86, 86, 86, 86
    };

    /** Compile-time constant expression */
    private static final int MAX_LOOKUP_CAPACITY = 1019;
    static {
        if (MAX_LOOKUP_CAPACITY !=
                SMALL_LOOKUP_TABLE_CAPACITIES[SMALL_LOOKUP_TABLE_CAPACITIES.length - 1]) {
            throw new AssertionError();
        }
    }

    /**
     * These capacities and other regular capacities from {@link #REGULAR_INT_CAPACITIES}
     * and {@link #REGULAR_LONG_CAPACITIES} arrays are generated using a single command
     * {@code $ java QHashCapacities 40 0.005}, i. e. trying to keep 0.5% max difference between
     * neighbouring capacities.
     *
     * @see {@link #main(String[])}
     * @see {@link #generateRegularCapacities(long, double)}
     */
    private static final char[] REGULAR_CHAR_CAPACITIES = new char[] {
            1031, 1039,
            1051, 1063, 1087, 1091, 1103, 1123, 1151, 1163, 1171, 1187,
            1223, 1231, 1259, 1279, 1283, 1291, 1303, 1307, 1319, 1327,
            1367, 1399, 1423, 1427, 1439, 1447, 1451, 1459, 1471, 1483,
            1487, 1499, 1511, 1523, 1531, 1543, 1559, 1567, 1571, 1579,
            1583, 1607, 1619, 1627, 1663, 1667, 1699, 1723, 1747, 1759,
            1783, 1787, 1811, 1823, 1831, 1847, 1867, 1871, 1879, 1907,
            1931, 1951, 1979, 1987, 1999, 2003, 2011, 2027, 2039, 2063,
            2083, 2087, 2099, 2111, 2131, 2143, 2179, 2203, 2207, 2239,
            2243, 2251, 2267, 2287, 2311, 2339, 2347, 2351, 2371, 2383,
            2399, 2411, 2423, 2447, 2459, 2467, 2503, 2531, 2539, 2543,
            2551, 2579, 2591, 2647, 2659, 2663, 2671, 2683, 2687, 2699,
            2707, 2711, 2719, 2731, 2767, 2791, 2803, 2819, 2843, 2851,
            2879, 2887, 2903, 2927, 2939, 2963, 2971, 2999, 3011, 3019,
            3023, 3067, 3079, 3083, 3119, 3163, 3167, 3187, 3191, 3203,
            3251, 3259, 3271, 3299, 3307, 3319, 3323, 3331, 3343, 3347,
            3359, 3371, 3391, 3407, 3463, 3467, 3491, 3499, 3511, 3527,
            3539, 3547, 3559, 3571, 3583, 3607, 3623, 3631, 3643, 3659,
            3671, 3691, 3719, 3727, 3739, 3767, 3779, 3803, 3823, 3847,
            3851, 3863, 3907, 3911, 3919, 3923, 3931, 3943, 3947, 3967,
            4003, 4007, 4019, 4027, 4051, 4079, 4091, 4099, 4111, 4127,
            4139, 4159, 4211, 4219, 4231, 4243, 4259, 4271, 4283, 4327,
            4339, 4363, 4391, 4423, 4447, 4451, 4463, 4483, 4507, 4519,
            4523, 4547, 4567, 4583, 4591, 4603, 4639, 4643, 4651, 4663,
            4679, 4691, 4703, 4723, 4751, 4759, 4783, 4787, 4799, 4831,
            4871, 4903, 4919, 4931, 4943, 4951, 4967, 4987, 4999, 5003,
            5011, 5023, 5039, 5051, 5059, 5087, 5099, 5107, 5119, 5147,
            5167, 5171, 5179, 5227, 5231, 5279, 5303, 5323, 5347, 5351,
            5387, 5399, 5407, 5419, 5431, 5443, 5471, 5479, 5483, 5503,
            5507, 5519, 5527, 5531, 5563, 5591, 5623, 5639, 5647, 5651,
            5659, 5683, 5711, 5743, 5779, 5783, 5791, 5807, 5827, 5839,
            5843, 5851, 5867, 5879, 5903, 5923, 5927, 5939, 5987, 6007,
            6011, 6043, 6047, 6067, 6079, 6091, 6131, 6143, 6151, 6163,
            6199, 6203, 6211, 6247, 6263, 6271, 6287, 6299, 6311, 6323,
            6343, 6359, 6367, 6379, 6427, 6451, 6491, 6547, 6551, 6563,
            6571, 6599, 6607, 6619, 6659, 6679, 6691, 6703, 6719, 6763,
            6779, 6791, 6803, 6823, 6827, 6863, 6871, 6883, 6899, 6907,
            6911, 6947, 6959, 6967, 6971, 6983, 6991, 7019, 7027, 7039,
            7043, 7079, 7103, 7127, 7151, 7159, 7187, 7207, 7211, 7219,
            7243, 7247, 7283, 7307, 7331, 7351, 7411, 7451, 7459, 7487,
            7499, 7507, 7523, 7547, 7559, 7583, 7591, 7603, 7607, 7639,
            7643, 7687, 7691, 7699, 7703, 7723, 7727, 7759, 7823, 7867,
            7879, 7883, 7907, 7919, 7927, 7951, 7963, 8011, 8039, 8059,
            8087, 8111, 8123, 8147, 8167, 8171, 8179, 8191, 8219, 8231,
            8243, 8263, 8287, 8291, 8311, 8363, 8387, 8419, 8423, 8431,
            8443, 8447, 8467, 8527, 8539, 8543, 8563, 8599, 8623, 8627,
            8647, 8663, 8699, 8707, 8719, 8731, 8747, 8779, 8783, 8803,
            8807, 8819, 8831, 8839, 8863, 8867, 8887, 8923, 8951, 8963,
            8971, 8999, 9007, 9011, 9043, 9059, 9067, 9091, 9103, 9127,
            9151, 9187, 9199, 9203, 9227, 9239, 9283, 9311, 9319, 9323,
            9343, 9371, 9391, 9403, 9419, 9431, 9439, 9463, 9467, 9479,
            9491, 9511, 9539, 9547, 9551, 9587, 9619, 9623, 9631, 9643,
            9679, 9719, 9739, 9743, 9767, 9787, 9791, 9803, 9811, 9839,
            9851, 9859, 9871, 9883, 9887, 9907, 9923, 9931, 9967, 10007,
            10039, 10067, 10079, 10091, 10099, 10103, 10111, 10139, 10151, 10159,
            10163, 10211, 10223, 10243, 10247, 10259, 10267, 10271, 10303, 10331,
            10343, 10391, 10399, 10427, 10459, 10463, 10487, 10499, 10531, 10559,
            10567, 10607, 10627, 10631, 10639, 10651, 10663, 10667, 10687, 10691,
            10711, 10723, 10739, 10771, 10799, 10831, 10847, 10859, 10867, 10883,
            10891, 10903, 10939, 10979, 10987, 11003, 11027, 11047, 11059, 11071,
            11083, 11087, 11119, 11131, 11159, 11171, 11239, 11243, 11251, 11279,
            11287, 11299, 11311, 11351, 11383, 11399, 11411, 11423, 11443, 11447,
            11467, 11471, 11483, 11491, 11503, 11519, 11527, 11551, 11579, 11587,
            11699, 11719, 11731, 11743, 11779, 11783, 11807, 11827, 11831, 11839,
            11863, 11867, 11887, 11903, 11923, 11927, 11939, 11959, 11971, 11987,
            12007, 12011, 12043, 12071, 12107, 12119, 12143, 12163, 12203, 12211,
            12227, 12239, 12251, 12263, 12323, 12343, 12347, 12379, 12391, 12451,
            12479, 12487, 12491, 12503, 12511, 12527, 12539, 12547, 12583, 12611,
            12619, 12647, 12659, 12671, 12703, 12739, 12743, 12763, 12791, 12799,
            12823, 12899, 12919, 12979, 13043, 13099, 13159, 13219, 13259, 13291,
            13339, 13399, 13463, 13523, 13567, 13619, 13679, 13711, 13763, 13831,
            13879, 13931, 13999, 14051, 14083, 14143, 14207, 14243, 14303, 14323,
            14387, 14431, 14503, 14563, 14627, 14683, 14723, 14779, 14851, 14923,
            14983, 15031, 15083, 15131, 15187, 15259, 15307, 15383, 15439, 15511,
            15551, 15607, 15667, 15727, 15787, 15859, 15919, 15991, 16063, 16111,
            16187, 16267, 16339, 16411, 16427, 16487, 16547, 16619, 16691, 16747,
            16811, 16879, 16963, 17047, 17123, 17207, 17291, 17359, 17443, 17519,
            17579, 17659, 17747, 17807, 17891, 17959, 18043, 18119, 18199, 18287,
            18367, 18427, 18503, 18583, 18671, 18719, 18787, 18839, 18899, 18959,
            19051, 19139, 19231, 19319, 19379, 19423, 19507, 19603, 19687, 19751,
            19843, 19927, 20023, 20123, 20219, 20287, 20347, 20443, 20543, 20611,
            20707, 20807, 20879, 20939, 21011, 21107, 21179, 21283, 21379, 21467,
            21559, 21647, 21739, 21839, 21943, 22039, 22147, 22247, 22343, 22447,
            22531, 22639, 22751, 22859, 22943, 23027, 23131, 23227, 23339, 23447,
            23563, 23663, 23767, 23879, 23971, 24043, 24151, 24239, 24359, 24379,
            24499, 24571, 24683, 24799, 24907, 25031, 25111, 25219, 25339, 25463,
            25579, 25679, 25799, 25903, 25999, 26099, 26227, 26339, 26407, 26539,
            26627, 26759, 26879, 27011, 27143, 27271, 27407, 27527, 27631, 27751,
            27883, 28019, 28151, 28279, 28387, 28499, 28619, 28751, 28879, 29023,
            29167, 29303, 29443, 29587, 29723, 29851, 29983, 30119, 30259, 30391,
            30539, 30671, 30803, 30931, 31079, 31231, 31387, 31543, 31699, 31847,
            31963, 32099, 32251, 32371, 32531, 32687, 32839, 32887, 33023, 33179,
            33331, 33479, 33647, 33811, 33967, 34123, 34231, 34403, 34543, 34703,
            34871, 35023, 35171, 35339, 35507, 35671, 35803, 35951, 36131, 36299,
            36451, 36587, 36767, 36943, 37123, 37307, 37447, 37619, 37799, 37987,
            38167, 38351, 38543, 38671, 38851, 39043, 39227, 39419, 39607, 39779,
            39971, 40151, 40343, 40499, 40699, 40847, 41039, 41243, 41443, 41647,
            41843, 41983, 42179, 42359, 42571, 42743, 42943, 43151, 43331, 43543,
            43759, 43943, 44131, 44351, 44563, 44771, 44959, 45179, 45403, 45599,
            45823, 46051, 46271, 46471, 46687, 46919, 47111, 47339, 47563, 47791,
            48023, 48259, 48491, 48731, 48947, 49171, 49391, 49627, 49871, 50111,
            50359, 50587, 50839, 51031, 51263, 51511, 51767, 52027, 52259, 52511,
            52747, 53003, 53267, 53527, 53791, 54059, 54311, 54583, 54851, 55079,
            55331, 55579, 55843, 56123, 56383, 56659, 56911, 57191, 57467, 57719,
            57991, 58271, 58543, 58831, 59107, 59387, 59659, 59951, 60251, 60527,
            60811, 61091, 61379, 61687, 61991, 62299, 62591, 62903, 63179, 63487,
            63803, 64123, 64439, 64747, 65063, 65371
    };

    /** Compile-time constant expression */
    private static final int MAX_REGULAR_CHAR_CAPACITY = 65371;
    static {
        if (MAX_REGULAR_CHAR_CAPACITY !=
                REGULAR_CHAR_CAPACITIES[REGULAR_CHAR_CAPACITIES.length - 1])
            throw new AssertionError();
    }


    private static final int[] REGULAR_INT_CAPACITIES = new int[] {
            65687, 65827, 66103, 66431,
            66751, 67079, 67391, 67699, 68023, 68351, 68687, 69031, 69371, 69691,
            69991, 70327, 70627, 70979, 71327, 71647, 71947, 72271, 72623, 72931,
            73291, 73643, 73999, 74323, 74687, 75011, 75367, 75731, 76091, 76463,
            76819, 77167, 77527, 77899, 78259, 78607, 78979, 79319, 79687, 80039,
            80407, 80803, 81203, 81611, 82003, 82387, 82787, 83203, 83563, 83891,
            84299, 84691, 85103, 85523, 85931, 86351, 86783, 87211, 87643, 88079,
            88499, 88919, 89363, 89759, 90187, 90631, 91079, 91499, 91939, 92399,
            92863, 93307, 93763, 94219, 94687, 95131, 95603, 96059, 96527, 96979,
            97459, 97919, 98387, 98867, 99347, 99823, 100291, 100787, 101267, 101719,
            102191, 102667, 103171, 103687, 104207, 104707, 105227, 105751, 106279, 106787,
            107323, 107827, 108343, 108883, 109423, 109943, 110479, 111031, 111539, 112067,
            112603, 113159, 113719, 114259, 114799, 115363, 115931, 116491, 117071, 117659,
            118247, 118831, 119419, 119963, 120539, 121123, 121687, 122263, 122867, 123479,
            124067, 124643, 125243, 125863, 126443, 127031, 127607, 128239, 128879, 129499,
            130147, 130783, 131363, 131543, 132199, 132859, 133519, 134171, 134807, 135463,
            136139, 136811, 137491, 138179, 138863, 139511, 140191, 140891, 141587, 142271,
            142979, 143687, 144379, 145091, 145799, 146519, 147211, 147919, 148627, 149371,
            150107, 150847, 151603, 152363, 153107, 153871, 154619, 155371, 156119, 156887,
            157667, 158443, 159223, 160019, 160807, 161611, 162419, 163211, 164023, 164839,
            165667, 166487, 167311, 168151, 168991, 169823, 170647, 171491, 172331, 173183,
            174047, 174907, 175783, 176651, 177511, 178403, 179287, 180179, 181003, 181871,
            182779, 183691, 184607, 185519, 186451, 187367, 188291, 189199, 190147, 191047,
            192007, 192971, 193939, 194911, 195887, 196871, 197831, 198811, 199783, 200771,
            201743, 202751, 203767, 204751, 205759, 206779, 207799, 208843, 209887, 210907,
            211927, 212987, 214003, 215051, 216119, 217199, 218279, 219371, 220447, 221539,
            222587, 223667, 224683, 225751, 226819, 227947, 228983, 230123, 231271, 232391,
            233551, 234659, 235783, 236947, 238099, 239287, 240479, 241603, 242807, 244003,
            245171, 246371, 247607, 248851, 250091, 251323, 252559, 253787, 255043, 256307,
            257591, 258871, 260171, 261427, 262723, 263951, 265271, 266587, 267887, 269219,
            270563, 271919, 273271, 274579, 275911, 277223, 278591, 279967, 281363, 282767,
            284159, 285559, 286987, 288403, 289843, 291299, 292759, 294223, 295699, 297151,
            298631, 300119, 301579, 303091, 304559, 306083, 307583, 309091, 310643, 312199,
            313679, 315247, 316819, 318403, 319967, 321547, 323123, 324743, 326351, 327967,
            329587, 331231, 332887, 334547, 336199, 337859, 339467, 341171, 342871, 344587,
            346303, 348011, 349759, 351503, 353263, 355027, 356803, 358591, 360391, 362143,
            363959, 365779, 367603, 369407, 371227, 373091, 374939, 376787, 378667, 380563,
            382463, 384359, 386279, 388211, 390151, 392099, 394063, 396031, 398011, 399979,
            401939, 403951, 405947, 407923, 409967, 412019, 414083, 416147, 418199, 420263,
            422311, 424423, 426527, 428639, 430783, 432931, 435103, 437263, 439459, 441667,
            443867, 446087, 448303, 450479, 452731, 454991, 457267, 459523, 461803, 464119,
            466423, 468739, 471091, 473443, 475807, 478171, 480563, 482947, 485347, 487783,
            490207, 492647, 495119, 497587, 500083, 502543, 505067, 507599, 510127, 512663,
            515191, 517739, 520339, 522947, 525571, 528163, 530807, 533447, 536111, 538799,
            541483, 544199, 546919, 549623, 552379, 555143, 557927, 560719, 563503, 566311,
            569083, 571939, 574799, 577627, 580471, 583367, 586291, 589187, 592139, 595087,
            598051, 601031, 604031, 607043, 610063, 613099, 616171, 619247, 622331, 625451,
            628583, 631711, 634859, 638023, 641227, 644431, 647659, 650911, 654163, 657431,
            660727, 664043, 667363, 670711, 674059, 677387, 680783, 684191, 687623, 691051,
            694511, 697979, 701479, 704999, 708527, 712067, 715639, 719179, 722783, 726367,
            729991, 733651, 737327, 741007, 744727, 748463, 752183, 755959, 759719, 763523,
            767323, 771143, 775007, 778871, 782783, 786659, 790567, 794531, 798487, 802471,
            806503, 810539, 814579, 818659, 822763, 826879, 831023, 835123, 839303, 843503,
            847727, 851971, 856187, 860479, 864803, 869119, 873463, 877843, 882239, 886651,
            891103, 895571, 900019, 904531, 909071, 913639, 918199, 922807, 927403, 931999,
            936679, 941383, 946091, 950839, 955607, 960383, 965179, 970027, 974891, 979787,
            984703, 989623, 994559, 999491, 1004483, 1009483, 1014547, 1019639, 1024703, 1029823,
            1034983, 1040167, 1045391, 1050631, 1054171, 1059439, 1064743, 1070087, 1075463, 1080847,
            1086259, 1091711, 1097179, 1102691, 1108223, 1113787, 1119359, 1124983, 1130627, 1136299,
            1142003, 1147739, 1153487, 1159283, 1165103, 1170947, 1176827, 1182739, 1188667, 1194631,
            1200607, 1206619, 1212671, 1218727, 1224823, 1230967, 1237139, 1243343, 1249559, 1255811,
            1262119, 1268447, 1274803, 1281187, 1287623, 1294087, 1300571, 1307063, 1313623, 1320191,
            1326791, 1333411, 1340107, 1346827, 1353551, 1360327, 1367159, 1374007, 1380887, 1387783,
            1394747, 1401739, 1408763, 1415803, 1422899, 1430027, 1437199, 1444411, 1451603, 1458871,
            1466147, 1473503, 1480903, 1488343, 1495751, 1503247, 1510759, 1518343, 1525963, 1533583,
            1541251, 1548947, 1556719, 1564499, 1572359, 1580251, 1588159, 1596107, 1604123, 1612183,
            1620247, 1628383, 1636543, 1644691, 1652947, 1661243, 1669543, 1677899, 1686319, 1694767,
            1703267, 1711799, 1720399, 1729043, 1737691, 1746419, 1755179, 1763959, 1772819, 1781699,
            1790599, 1799591, 1808627, 1817663, 1826771, 1835923, 1845119, 1854379, 1863671, 1873019,
            1882403, 1891859, 1901359, 1910891, 1920487, 1930099, 1939787, 1949527, 1959283, 1969111,
            1978927, 1988839, 1998827, 2008807, 2018899, 2029003, 2039179, 2049419, 2059711, 2069959,
            2080339, 2090771, 2101259, 2106551, 2117119, 2127739, 2138387, 2149127, 2159923, 2170771,
            2181671, 2192623, 2203631, 2214691, 2225819, 2236987, 2248223, 2259503, 2270803, 2282207,
            2293567, 2305091, 2316667, 2328307, 2340007, 2351731, 2363507, 2375327, 2387243, 2399207,
            2411243, 2423359, 2435519, 2447743, 2460043, 2472403, 2484803, 2497259, 2509807, 2522407,
            2535059, 2547791, 2560583, 2573423, 2586343, 2599327, 2612383, 2625487, 2638651, 2651899,
            2665199, 2678551, 2692003, 2705519, 2719111, 2732759, 2746423, 2760223, 2774071, 2788007,
            2802011, 2816059, 2830151, 2844367, 2858623, 2872967, 2887363, 2901839, 2916383, 2930999,
            2945707, 2960467, 2975339, 2990279, 3005267, 3020351, 3035507, 3050759, 3066067, 3081443,
            3096911, 3112391, 3127979, 3143671, 3159439, 3175259, 3191099, 3207119, 3223223, 3239419,
            3255683, 3272039, 3288479, 3304991, 3321583, 3338263, 3355031, 3371867, 3388799, 3405791,
            3422807, 3439987, 3457271, 3474599, 3492043, 3509587, 3527219, 3544907, 3562711, 3580579,
            3598519, 3616583, 3634727, 3652991, 3671347, 3689771, 3708283, 3726911, 3745631, 3764443,
            3783343, 3802283, 3821327, 3840479, 3859759, 3879023, 3898483, 3918067, 3937751, 3957479,
            3977339, 3997307, 4017359, 4037531, 4057799, 4078187, 4098659, 4119239, 4139923, 4160711,
            4181579, 4202567, 4210807, 4231943, 4253203, 4274551, 4295999, 4317571, 4339207, 4361003,
            4382879, 4404899, 4426999, 4449227, 4471559, 4494019, 4516571, 4539247, 4562039, 4584959,
            4607987, 4631131, 4654399, 4677779, 4701239, 4724831, 4748563, 4772399, 4796371, 4820443,
            4844659, 4868999, 4893419, 4918007, 4942687, 4967491, 4992419, 5017447, 5042647, 5067967,
            5093423, 5119007, 5144707, 5170519, 5196467, 5222579, 5248787, 5275159, 5301623, 5328251,
            5355019, 5381927, 5408947, 5436127, 5463391, 5490787, 5518351, 5546071, 5573927, 5601907,
            5630039, 5658307, 5686739, 5715299, 5743987, 5772847, 5801843, 5830963, 5860243, 5889683,
            5919271, 5948939, 5978831, 6008867, 6038999, 6069311, 6099767, 6130391, 6161063, 6192023,
            6223099, 6254359, 6285787, 6317327, 6349043, 6380939, 6412999, 6445223, 6477599, 6510107,
            6542803, 6575671, 6608639, 6641839, 6675211, 6708739, 6742363, 6776207, 6810247, 6844447,
            6878803, 6913351, 6948079, 6982907, 7017979, 7053223, 7088611, 7124231, 7159987, 7195963,
            7232111, 7268423, 7304939, 7341647, 7378531, 7415599, 7452859, 7490303, 7527911, 7565627,
            7603627, 7641791, 7680191, 7718771, 7757543, 7796491, 7835647, 7874983, 7914551, 7954319,
            7994279, 8034451, 8074811, 8115383, 8156147, 8197099, 8238247, 8279627, 8321227, 8363023,
            8405003, 8419511, 8461787, 8504291, 8546999, 8589923, 8633063, 8676431, 8719987, 8763803,
            8807803, 8852059, 8896483, 8941171, 8986091, 9031207, 9076579, 9122143, 9167923, 9213979,
            9260263, 9306779, 9353483, 9400463, 9447667, 9495139, 9542843, 9590699, 9638891, 9687323,
            9735991, 9784903, 9834047, 9883463, 9933059, 9982939, 10033063, 10083443, 10134107, 10185011,
            10236179, 10287587, 10339267, 10391219, 10443431, 10495907, 10548623, 10601627, 10654871, 10708403,
            10762211, 10816271, 10870619, 10925227, 10980059, 11035223, 11090627, 11146279, 11202251, 11258483,
            11314987, 11371807, 11428931, 11486347, 11544047, 11602043, 11660339, 11718923, 11777791, 11836963,
            11896427, 11956199, 12016187, 12076567, 12137183, 12198139, 12259399, 12320983, 12382823, 12445039,
            12507559, 12570403, 12633559, 12697039, 12760843, 12824899, 12889339, 12954079, 13019143, 13084531,
            13150279, 13216331, 13282723, 13349411, 13416463, 13483751, 13551467, 13619563, 13687987, 13756739,
            13825831, 13895291, 13965103, 14035279, 14105759, 14176619, 14247847, 14319419, 14391359, 14463667,
            14536307, 14609351, 14682719, 14756491, 14830603, 14905123, 14980019, 15055259, 15130903, 15206899,
            15283291, 15360071, 15437239, 15514783, 15592739, 15671087, 15749819, 15828947, 15908423, 15988363,
            16068691, 16149431, 16230491, 16312039, 16394003, 16476371, 16559159, 16642343, 16725971, 16810007,
            16836587, 16921183, 17006167, 17091623, 17177507, 17263783, 17350519, 17437691, 17525243, 17613307,
            17701807, 17790739, 17880067, 17969911, 18060187, 18150911, 18242083, 18333703, 18425819, 18518363,
            18611419, 18704927, 18798907, 18893351, 18988267, 19083679, 19179551, 19275847, 19372699, 19470019,
            19567811, 19666123, 19764947, 19864267, 19964059, 20064371, 20165143, 20266391, 20368211, 20470547,
            20573411, 20676791, 20780659, 20885071, 20989967, 21095423, 21201347, 21307859, 21414923, 21522511,
            21630659, 21739351, 21848579, 21958367, 22068647, 22179511, 22290943, 22402951, 22515511, 22628651,
            22742303, 22856527, 22971259, 23086667, 23202643, 23319227, 23436407, 23554099, 23672459, 23791399,
            23910947, 24031087, 24151807, 24273163, 24395023, 24517607, 24640799, 24764611, 24889043, 25014071,
            25139767, 25266071, 25393031, 25520623, 25648867, 25777639, 25907143, 26037299, 26168099, 26299571,
            26431723, 26564507, 26697991, 26832139, 26966963, 27102419, 27238559, 27375419, 27512951, 27651191,
            27790127, 27929723, 28070071, 28211123, 28352887, 28495351, 28638539, 28782419, 28927039, 29072399,
            29218403, 29365207, 29512739, 29661043, 29810023, 29959819, 30110347, 30261643, 30413707, 30566519,
            30720119, 30874483, 31029587, 31185443, 31342139, 31499599, 31657783, 31816847, 31976723, 32137403,
            32298863, 32461159, 32624239, 32788099, 32952839, 33118391, 33284803, 33452047, 33619979, 33670103,
            33839243, 34009279, 34180163, 34351879, 34524491, 34697951, 34872283, 35047483, 35223599, 35400583,
            35578471, 35757247, 35936903, 36117467, 36298943, 36481343, 36664651, 36848891, 37033987, 37220047,
            37407059, 37595027, 37783927, 37973783, 38164571, 38356327, 38548999, 38742707, 38937319, 39132979,
            39329627, 39527123, 39725723, 39925339, 40125947, 40327571, 40530199, 40733867, 40938523, 41144203,
            41350943, 41558687, 41767483, 41977367, 42188287, 42400243, 42613303, 42827431, 43042631, 43258907,
            43476287, 43694747, 43914307, 44134931, 44356639, 44579503, 44803511, 45028639, 45254899, 45482291,
            45710831, 45940523, 46171351, 46403347, 46636519, 46870867, 47106379, 47343083, 47580983, 47820079,
            48060359, 48301867, 48544583, 48788503, 49033651, 49280003, 49527619, 49776479, 50026607, 50277979,
            50530619, 50784523, 51039683, 51296159, 51553903, 51812927, 52073279, 52334951, 52597891, 52862143,
            53127779, 53394727, 53663039, 53932651, 54203659, 54476027, 54749771, 55024859, 55301359, 55579243,
            55858459, 56139079, 56421151, 56704667, 56989571, 57275927, 57563699, 57852943, 58143583, 58435703,
            58729331, 59024443, 59321039, 59619127, 59918687, 60219779, 60522379, 60826511, 61132163, 61439239,
            61747963, 62058247, 62370079, 62683463, 62998451, 63314959, 63633079, 63952799, 64274159, 64597111,
            64921699, 65247907, 65575747, 65905267, 66236431, 66569267, 66903779, 67239967, 67338643, 67677007,
            68017067, 68358739, 68702143, 69047299, 69394219, 69742919, 70093327, 70445519, 70799507, 71155267,
            71512787, 71872127, 72233279, 72596243, 72961039, 73327651, 73696111, 74066411, 74438591, 74812651,
            75188591, 75566347, 75946067, 76327703, 76711231, 77096707, 77484083, 77873431, 78264727, 78657983,
            79053187, 79450363, 79849543, 80250763, 80654027, 81059287, 81466579, 81875951, 82287379, 82700791,
            83116367, 83534023, 83953763, 84375623, 84799619, 85225739, 85653947, 86084287, 86516863, 86951603,
            87388531, 87827647, 88268987, 88712527, 89158283, 89606287, 90056467, 90508987, 90963799, 91420867,
            91880263, 92341967, 92805983, 93272327, 93741019, 94212031, 94685419, 95161219, 95639387, 96119927,
            96602903, 97088339, 97576163, 98066491, 98559259, 99054523, 99552227, 100052467, 100555243, 101060539,
            101568287, 102078679, 102591631, 103107119, 103625239, 104145887, 104669179, 105195127, 105723743, 106254899,
            106788827, 107325451, 107864747, 108406763, 108951503, 109498943, 110049059, 110602031, 111157807, 111716383,
            112277699, 112841863, 113408767, 113978507, 114551263, 115126883, 115705351, 116286743, 116871091, 117458347,
            118048547, 118641739, 119237927, 119837059, 120439243, 121044431, 121652599, 122263903, 122878211, 123495683,
            124116191, 124739887, 125366567, 125996539, 126629663, 127265951, 127905443, 128548139, 129194083, 129843299,
            130495763, 131151491, 131810491, 132472831, 133138519, 133807547, 134479879, 134673607, 135350351, 136030471,
            136714027, 137400979, 138091427, 138785203, 139482599, 140183503, 140887919, 141595859, 142307287, 143022359,
            143741047, 144463339, 145189259, 145918711, 146651903, 147388823, 148129447, 148873787, 149621891, 150373759,
            151129399, 151888843, 152652103, 153419159, 154190087, 154964867, 155743583, 156526207, 157312763, 158103259,
            158897743, 159696211, 160498699, 161305211, 162115787, 162930419, 163749119, 164571971, 165398927, 166230007,
            167065303, 167904791, 168748499, 169596463, 170448683, 171305207, 172165991, 173031143, 173900563, 174774427,
            175652671, 176535311, 177422411, 178313951, 179209991, 180110471, 181015519, 181925111, 182839303, 183758039,
            184681411, 185609447, 186542099, 187479491, 188421539, 189368371, 190319959, 191276291, 192237431, 193203431,
            194174191, 195149939, 196130579, 197116159, 198106663, 199102151, 200102579, 201108043, 202118563, 203134123,
            204154859, 205180751, 206211799, 207248011, 208289351, 209336027, 210387907, 211445131, 212507651, 213575503,
            214648699, 215727247, 216811267, 217900763, 218995739, 220096183, 221202119, 222313643, 223430791, 224553523,
            225681923, 226815983, 227955727, 229101203, 230252411, 231409439, 232572299, 233740999, 234915539, 236095939,
            237282343, 238474711, 239672963, 240877339, 242087771, 243304219, 244526851, 245755619, 246990559, 248231707,
            249479099, 250732739, 251992667, 253258879, 254531507, 255810559, 257096039, 258387967, 259686391, 260991287,
            262302791, 263620879, 264945587, 266276947, 267614983, 268959767, 269344759, 270698227, 272058491, 273425591,
            274799579, 276180431, 277568219, 278963011, 280364803, 281773571, 283189499, 284612527, 286042723, 287480071,
            288924599, 290376451, 291835627, 293302123, 294775991, 296257271, 297745967, 299242171, 300745843, 302257051,
            303775919, 305302427, 306836599, 308378407, 309928027, 311485423, 313050587, 314623703, 316204703, 317793559,
            319390507, 320995471, 322608491, 324229639, 325858867, 327496339, 329142019, 330795991, 332458267, 334128887,
            335807831, 337495303, 339191227, 340895683, 342608719, 344330351, 346060571, 347799511, 349547071, 351303583,
            353068907, 354843119, 356626211, 358418243, 360219283, 362029403, 363848627, 365676923, 367514491, 369361231,
            371217299, 373082707, 374957483, 376841587, 378735251, 380638387, 382551083, 384473399, 386405387, 388347103,
            390298547, 392259767, 394230899, 396211903, 398202899, 400203871, 402214927, 404236087, 406267391, 408308899,
            410360539, 412422631, 414495091, 416577947, 418671283, 420775151, 422889583, 425014571, 427150247, 429296719,
            431453983, 433622011, 435800971, 437990923, 440191879, 442403887, 444627019, 446861267, 449106787, 451363571,
            453631727, 455911259, 458202211, 460504699, 462818767, 465144487, 467481851, 469831003, 472191851, 474564667,
            476949379, 479346103, 481754807, 484175663, 486608687, 489053951, 491511491, 493981363, 496463519, 498958307,
            501465563, 503985479, 506518063, 509063299, 511621387, 514192271, 516776131, 519372859, 521982751, 524605747,
            527241899, 529891199, 532553939, 535230083, 537919639, 538685971, 541392743, 544113239, 546847447, 549595367,
            552357139, 555132803, 557922367, 560725951, 563543663, 566375527, 569221603, 572081959, 574956703, 577845787,
            580749511, 583667831, 586600783, 589548499, 592511039, 595488451, 598480807, 601488211, 604510703, 607548371,
            610601371, 613669687, 616753427, 619852679, 622967503, 626097991, 629244167, 632406163, 635584031, 638777903,
            641987839, 645213847, 648456091, 651714607, 654989519, 658280863, 661588783, 664913323, 668254571, 671612587,
            674987507, 678379379, 681788203, 685214251, 688657483, 692117983, 695595931, 699091331, 702604327, 706134991,
            709683371, 713249591, 716833727, 720435851, 724056107, 727694531, 731351279, 735026371, 738719939, 742432063,
            746162863, 749912399, 753680731, 757468067, 761274403, 765099883, 768944587, 772808551, 776691959, 780594923,
            784517507, 788459759, 792421843, 796403831, 800405831, 804427927, 808470259, 812532911, 816615971, 820719539,
            824843651, 828988331, 833154031, 837340703, 841548427, 845777279, 850027351, 854298799, 858591751, 862906279,
            867242491, 871600487, 875980379, 880382287, 884806283, 889252471, 893721071, 898212083, 902725711, 907261963,
            911821051, 916403011, 921007907, 925636079, 930287503, 934962299, 939660587, 944382499, 949128119, 953897599,
            958691051, 963508519, 968350231, 973216267, 978106799, 983021807, 987961591, 992926211, 997915771, 1002930347,
            1007970143, 1013035271, 1018125743, 1023241907, 1028383823, 1033551523, 1038745151, 1043964947, 1049210831, 1054483151,
            1059782051, 1065107587, 1070459851, 1075839019, 1077368339, 1082782187, 1088223299, 1093691743, 1099187591, 1104711019,
            1110262327, 1115841499, 1121448739, 1127084059, 1132747771, 1138439959, 1144160711, 1149910183, 1155688603, 1161496079,
            1167332711, 1173198647, 1179094079, 1185019067, 1190973899, 1196958667, 1202973511, 1209018599, 1215094019, 1221199951,
            1227336631, 1233504079, 1239702463, 1245932059, 1252193003, 1258485419, 1264809463, 1271165167, 1277552923, 1283972759,
            1290424799, 1296909343, 1303426459, 1309976287, 1316559071, 1323174883, 1329823987, 1336506463, 1343222567, 1349972251,
            1356756031, 1363573879, 1370425967, 1377312463, 1384233491, 1391189419, 1398180307, 1405206307, 1412267611, 1419364259,
            1426496711, 1433664959, 1440869279, 1448109779, 1455386671, 1462700131, 1470050363, 1477437523, 1484861771, 1492323307,
            1499822383, 1507359151, 1514933747, 1522546447, 1530197423, 1537886851, 1545614899, 1553381771, 1561187699, 1569032827,
            1576917379, 1584841567, 1592805583, 1600809611, 1608853859, 1616938507, 1625063819, 1633229951, 1641437099, 1649685467,
            1657975307, 1666306819, 1674680207, 1683095671, 1691553427, 1700053627, 1708596587, 1717182347, 1725811267, 1734483643,
            1743199571, 1751959367, 1760763107, 1769611087, 1778503583, 1787440747, 1796422847, 1805449999, 1814522603, 1823640799,
            1832804767, 1842014791, 1851271043, 1860573907, 1869923411, 1879319999, 1888763743, 1898254999, 1907793931, 1917380807,
            1927015879, 1936699351, 1946431363, 1956212243, 1966042451, 1975922059, 1985851247, 1995830323, 2005859543, 2015939239,
            2026069559, 2036250751, 2046483151, 2056766983, 2067102431, 2077489807, 2087929451, 2098421519, 2108966287, 2119564099,
            2130215159, 2140919723,
    };


    // Compile-time constant expressions
    private static final int MAX_REGULAR_CAPACITY_FOR_DOUBLED_ARRAY = 107325451;
    private static final int MAX_REGULAR_INT_CAPACITY = 2140919723;
    static {
        if (MAX_REGULAR_INT_CAPACITY != REGULAR_INT_CAPACITIES[REGULAR_INT_CAPACITIES.length - 1] ||
                binarySearch(REGULAR_INT_CAPACITIES, MAX_REGULAR_CAPACITY_FOR_DOUBLED_ARRAY) < 0)
            throw new AssertionError();
    }
        
    /**
     * Class for precise and fast scaling non-negative integers by positive doubles.
     *
     * <p>Used in {@link com.koloboke.collect.impl.hash.HashConfigWrapper}.
     *
     * <p>Latencies of operations on floating stack, required for simple approach scaling
     * <pre>
     *                       Haswell  Steamroller
     * FILD (long -> double) 6        11
     * FMUL                  5        5
     * FDIV                  10-24    9-37
     * FIST (double -> long) 7        7
     * </pre>
     *
     * <p>In major cases {@code Scaler} allows to replace this
     * with megamorphic call cost + a few clock cycles.
     */
    private static class Scaler {

        public static Scaler by(double scale) {
            if (Double.isNaN(scale) || scale <= 0.0 || Double.isInfinite(scale))
                throw new IllegalArgumentException(
                        "Scale should be a finite positive number, " + scale + " is given");
            if (scale == 0.25) return BY_0_25;
            // Special "precise" BigDecimal forms for scales which are inversions of custom
            // scales are needed to preserve inversion consistency
            if (scale == 1.0 / 3.0) return BY_3_0_INVERSE;
            if (scale == 0.5) return BY_0_5;
            if (scale == 1 / 1.5) return BY_1_5_INVERSE;
            if (scale == 0.75) return BY_0_75;
            if (scale == 1.0) return BY_1_0;
            if (scale == 1.0 / 0.75) return BY_0_75_INVERSE;
            if (scale == 1.5) return BY_1_5;
            if (scale == 2.0) return BY_2_0;
            if (scale == 3.0) return BY_3_0;
            if (scale == 4.0) return BY_4_0;
            return new Scaler(scale);
        }

        static final Scaler BY_0_25 = new Scaler(0.25) {
            @Override public int  scaleUpper(int  n) { check(n); return (n >> 2) + 1 ; }
            @Override public int  scaleLower(int  n) { check(n); return  n >> 2      ; }
        };

        static final Scaler BY_3_0_INVERSE = new Scaler(1.0 / 3.0);

        static final Scaler BY_0_5 = new Scaler(0.5) {
            @Override public int  scaleUpper(int  n) { check(n); return (n >> 1) + 1 ; }
            @Override public int  scaleLower(int  n) { check(n); return  n >> 1      ; }
        };

        static final Scaler BY_1_5_INVERSE = new Scaler(1.0 / 1.5);

        static final Scaler BY_0_75 = new Scaler(0.75) {
            @Override public int  scaleUpper(int  n) { check(n); int  r = n - (n >> 2); return (n & 3 ) != 0 ? r      : r + 1 ; }
            @Override public int  scaleLower(int  n) { check(n); int  r = n - (n >> 2); return (n & 3 ) != 0 ? r - 1  : r     ; }
        };

        static final Scaler BY_1_0 = new Scaler(1.0) {
            @Override public int  scaleUpper(int  n) { check(n); return n < Integer.MAX_VALUE ? n + 1  : Integer.MAX_VALUE; }
            @Override public int  scaleLower(int  n) { check(n); return n                                                 ; }
        };

        static final Scaler BY_0_75_INVERSE = new Scaler(1.0 / 0.75);

        static final Scaler BY_1_5 = new Scaler(1.5) {
            @Override public int  scaleUpper(int  n) { check(n); return n <= 1431655764           ? n + (n >> 1) + 1  : Integer.MAX_VALUE; }
            @Override public int  scaleLower(int  n) { check(n); return n <= 1431655764           ? n + (n >> 1)      : Integer.MAX_VALUE; }
        };

        static final Scaler BY_2_0 = new Scaler(2.0) {
            @Override public int  scaleUpper(int  n) { check(n); return n < (1  << 30) ? (n << 1) + 1  : Integer.MAX_VALUE; }
            @Override public int  scaleLower(int  n) { check(n); return n < (1  << 30) ? (n << 1)      : Integer.MAX_VALUE; }
        };

        static final Scaler BY_3_0 = new Scaler(3.0) {
            @Override public int  scaleUpper(int  n) { check(n); return n <= 715827882            ? n + (n << 1) + 1  : Integer.MAX_VALUE; }
            @Override public int  scaleLower(int  n) { check(n); return n <= 715827882            ? n + (n << 1)      : Integer.MAX_VALUE; }
        };

        static final Scaler BY_4_0 = new Scaler(4.0) {
            @Override public int  scaleUpper(int  n) { check(n); return n < (1  << 29) ? (n << 2) + 1  : Integer.MAX_VALUE; }
            @Override public int  scaleLower(int  n) { check(n); return n < (1  << 29) ? (n << 2)      : Integer.MAX_VALUE; }
        };

        private static void check(int n) {
            assert n >= 0 : "n should be non-negative, otherwise result is undefined";
        }

        final double scale;

        private Scaler(double scale) {
            this.scale = scale;
        }

        public int scaleUpper(int n) {
            check(n);
            int lower = (int) ((double) n * scale);
            return lower < Integer.MAX_VALUE ? lower + 1 : Integer.MAX_VALUE;
        }

        public int scaleLower(int n) {
            check(n);
            return (int) ((double) n * scale);
        }
    }
}