package com.oracle.util;

import java.lang.ref.ReferenceQueue;
import java.lang.ref.SoftReference;
import java.lang.ref.WeakReference;
import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Set;

import static sun.misc.Hashing.randomHashSeed;

/**
 * Hash table based implementation of the {@code Map} interface,
 * which allows to use weak or soft references for keys and values.
 * An entry in a {@code Cache} will automatically be removed
 * when its key or value is no longer in ordinary use.
 *
 * @author Sergey Malenkov
 * @see java.util.WeakHashMap
 * @since 1.8
 */
public final class Cache<K, V> extends AbstractMap<K, V> implements Map<K, V> {

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor for the hash table used by default.
     */
    private static final float LOAD_FACTOR = 0.75f;

    /**
     * A reference kind for the cache keys.
     */
    private final Kind keyKind;

    /**
     * A reference kind for the cache values.
     */
    private final Kind valueKind;

    /**
     * This variable defines whether the identity comparison is used.
     */
    private final boolean identity;

    /**
     * A randomizing value associated with this instance
     * that is applied to hash code of keys
     * to make hash collisions harder to find.
     */
    private final int hashSeed = randomHashSeed(this);

    /**
     * The reference queue for cleared references.
     */
    private final ReferenceQueue<Object> queue;

    /**
     * The hash table, resized as necessary.
     * Its length must always be a power of two.
     */
    private CacheEntry<K, V>[] table = newTable(8);

    /**
     * The number of key-value mappings contained in this map.
     */
    private int size;

    /**
     * The next size value at which to resize (capacity * load factor).
     */
    private int threshold = (int) (this.table.length * LOAD_FACTOR);

    /**
     * The number of times this map has been structurally modified.
     * Structural modifications are those that change the number of
     * mappings in the map or otherwise modify its internal structure
     * (e.g., rehash).  This field is used to make iterators on
     * Collection-views of the map fail-fast.
     *
     * @see ConcurrentModificationException
     */
    int modification;

    /**
     * The {@link Set} view of the mappings contained in this map.
     */
    private transient volatile Set<Map.Entry<K, V>> entries;

    /**
     * The {@link Set} view of the keys contained in this map.
     */
    private transient volatile Set<K> keys;

    /**
     * The {@link Collection} view of the values contained in this map.
     */
    private transient volatile Collection<V> values;

    public Cache(Kind keyKind, Kind valueKind) {
        this(keyKind, valueKind, false);
    }

    /**
     * Constructs an empty {@code Cache}
     * with the default initial capacity (8)
     * and the default load factor (0.75).
     *
     * @param keyKind   a reference kind for keys
     * @param valueKind a reference kind for values
     * @param identity  defines whether reference-equality is used
     *                  in place of object-equality
     * @throws NullPointerException if {@code keyKind} or {@code valueKind} are {@code null}
     */
    public Cache(Kind keyKind, Kind valueKind, boolean identity) {
        Objects.requireNonNull(keyKind, "keyKind must not be null");
        Objects.requireNonNull(valueKind, "valueKind must not be null");
        this.keyKind = keyKind;
        this.valueKind = valueKind;
        this.identity = identity;
        this.queue = ((keyKind != Kind.STRONG) || (valueKind != Kind.STRONG))
                ? new ReferenceQueue<>()
                : null;
    }

    /**
     * Returns the number of key-value mappings in this map.
     * This result is a snapshot, and may not reflect unprocessed entries
     * that will be removed before next attempted access
     * because they are no longer referenced.
     */
    public int size() {
        if (this.size == 0) {
            return 0;
        }
        removeStaleEntries(this.table);
        return this.size;
    }

    /**
     * Returns {@code true} if this map contains no key-value mappings.
     * This result is a snapshot, and may not reflect unprocessed entries
     * that will be removed before next attempted access
     * because they are no longer referenced.
     */
    public boolean isEmpty() {
        return 0 == size();
    }

    /**
     * Returns {@code true} if this map contains a mapping
     * for the specified key.
     *
     * @param key the key whose presence in this map is to be tested
     * @return {@code true} if there is a mapping for {@code key};
     *         {@code false} otherwise
     */
    public boolean containsKey(Object key) {
        return null != getEntry(key);
    }

    /**
     * Returns {@code true} if this map maps one or more keys
     * to the specified value.
     *
     * @param value the value whose presence in this map is to be tested
     * @return {@code true} if there is a mapping for {@code value};
     *         {@code false} otherwise
     */
    public boolean containsValue(Object value) {
        CacheEntry<K, V>[] table = getTable();
        int index = table.length;
        while (0 < index--) {
            for (CacheEntry<K, V> entry = table[index]; entry != null; entry = entry.next) {
                if (entry.matches(value)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if there is no mapping for the key.
     * <p/>
     * <p>More formally, if this map contains
     * a mapping from a key {@code k} to a value {@code v}
     * such that {@code k} equals to {@code key},
     * then this method returns {@code v};
     * otherwise it returns {@code null}.
     * There can contain at most one such mapping.
     * <p/>
     * <p>A return value of {@code null} does not necessarily indicate
     * that this map contains no mapping for the key; it's also possible
     * that this map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @return a value to which the specified key is mapped,
     *         or {@code null} if there is no mapping for {@code key}
     * @see #put(Object, Object)
     * @see #containsKey(Object)
     */
    public V get(Object key) {
        CacheEntry<K, V> entry = getEntry(key);
        return (entry == null) ? null : entry.value.getReferent();
    }

    /**
     * Returns the entry associated with the specified key in this map.
     * Returns null if this map contains no mapping for the key.
     */
    private CacheEntry<K, V> getEntry(Object key) {
        CacheEntry<K, V>[] table = getTable();
        int hash = hash(key);
        int index = index(hash, table);
        for (CacheEntry<K, V> entry = table[index]; entry != null; entry = entry.next) {
            if (entry.matches(hash, key)) {
                return entry;
            }
        }
        return null;
    }

    /**
     * Associates the specified value with the specified key in this map.
     * If this map previously contained a mapping for the key,
     * the old value is replaced.
     *
     * @param key   the key with which the specified value is to be associated
     * @param value the value to be associated with the specified key
     * @return the previous value associated with the specified key
     *         or {@code null} if there was no mapping for {@code key}
     *         (a {@code null} return can also indicate that the map
     *         previously associated {@code null} with {@code key})
     */
    public V put(K key, V value) {
        return put(key, value, true);
    }

    /**
     * Associates the specified value with the specified key in this map,
     * if the key is not already associated with the value.
     * This is equivalent to
     * <pre>
     *  if (!map.containsKey(key))
     *      return map.put(key, value);
     *  else
     *      return map.get(key);</pre>
     *
     * @param key   the key with which the specified value is to be associated
     * @param value the value to be associated with the specified key
     * @return the previous value associated with the specified key,
     *         or {@code null} if there was no mapping for {@code key}
     *         (a {@code null} return can also indicate that the map
     *         previously associated {@code null} with {@code key})
     */
    public V putIfAbsent(K key, V value) {
        return put(key, value, false);
    }

    private V put(K key, V value, boolean replace) {
        CacheEntry<K, V>[] table = getTable();
        int hash = hash(key);
        int index = index(hash, table);
        for (CacheEntry<K, V> entry = table[index]; entry != null; entry = entry.next) {
            if (entry.matches(hash, key)) {
                return replace
                        ? entry.replace(value)
                        : entry.value.getReferent();
            }
        }
        this.modification++;
        table[index] = new CacheEntry<>(this, hash, key, value, table[index]);
        if (++this.size >= this.threshold) {
            resize(table.length << 1);
        }
        return null;
    }

    /**
     * Copies all of the mappings from the specified map to this map.
     * These mappings will replace any mappings that this map had
     * for any of the keys currently in the specified map.
     *
     * @param map the mappings to be stored in this map
     * @throws NullPointerException if the specified map is {@code null}
     */
    public void putAll(Map<? extends K, ? extends V> map) {
        int size = map.size();
        if (size > 0) {
            // Expand the map if the map if the number of mappings to be added
            // is greater than or equal to threshold.  This is conservative;
            // the obvious condition is (m.size() + size) >= threshold,
            // but this condition could result in a map with twice the appropriate capacity,
            // if the keys to be added overlap with the keys already in this map.
            // By using the conservative calculation,
            // we subject ourselves to at most one extra resize.
            if (size > this.threshold) {
                int expected = (int) (1 + size / LOAD_FACTOR);
                if (expected > this.table.length) {
                    if (expected < MAXIMUM_CAPACITY) {
                        int capacity = 1;
                        while (capacity < expected) {
                            capacity <<= 1;
                        }
                        resize(capacity);
                    }
                    else {
                        resize(MAXIMUM_CAPACITY);
                    }
                }
            }
            for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
                put(entry.getKey(), entry.getValue());
            }
        }
    }

    /**
     * Removes the mapping for the specified key from this map
     * if it is present.
     * <p/>
     * <p>More formally, if this map contains
     * a mapping from a key {@code k} to a value {@code v}
     * such that {@code k} equals to {@code key},
     * that mapping is removed.
     * There can contain at most one such mapping
     * This map will not contain a mapping for the specified key
     * once the call returns.
     * <p/>
     * <p>A return value of {@code null} does not necessarily indicate
     * that this map contains no mapping for the key; it's also possible
     * that this map explicitly maps the key to {@code null}.
     *
     * @param key the key whose mapping is to be removed from this map
     * @return the previous value associated with the specified key,
     *         or {@code null} if there was no mapping for {@code key}
     *         (a {@code null} return can also indicate that the map
     *         previously associated {@code null} with {@code key})
     */
    public V remove(Object key) {
        Ref<V> value = removeEntry(key);
        return (value == null) ? null : value.getReferent();
    }

    /**
     * Removes the mapping for the specified key from this map
     * if it is present.
     * <p/>
     * <p>More formally, if this map contains
     * a mapping from a key {@code k} to a value {@code v}
     * such that {@code k} equals to {@code key}
     * and {@code v} equals to {@code value},
     * that mapping is removed.
     * There can contain at most one such mapping.
     * This map will not contain a mapping for the specified key
     * once the call returns.
     * <p/>
     * <p>A return value of {@code null} does not necessarily indicate
     * that this map contains no mapping for the key; it's also possible
     * that this map explicitly maps the key to {@code null}.
     *
     * @param key   the key whose mapping is to be removed from this map
     * @param value the value expected to be associated with the specified key
     * @return {@code true} if the mapping was removed
     */
    public boolean remove(Object key, Object value) {
        CacheEntry<K, V>[] table = getTable();
        int hash = hash(key);
        int index = index(hash, table);

        CacheEntry<K, V> prev = table[index];
        CacheEntry<K, V> cur = prev;
        while (cur != null) {
            CacheEntry<K, V> next = cur.next;
            if (cur.matches(hash, key) && cur.matches(value)) {
                this.modification++;
                this.size--;
                if (prev == cur) {
                    table[index] = next;
                }
                else {
                    prev.next = next;
                }
                return true;
            }
            prev = cur;
            cur = next;
        }
        return false;
    }

    /**
     * Replaces the entry for the specified key
     * only if currently mapped to some value.
     * This is equivalent to
     * <pre>
     *  if (map.containsKey(key))
     *      return map.put(key, value);
     *  else
     *      return null;</pre>
     *
     * @param key   the key whose mapping is to be removed from this map
     * @param value the value to be associated with the specified key
     * @return the previous value associated with the specified key,
     *         or {@code null} if there was no mapping for {@code key}
     *         (a {@code null} return can also indicate that the map
     *         previously associated {@code null} with {@code key})
     */
    public V replace(K key, V value) {
        CacheEntry<K, V> entry = getEntry(key);
        if (entry != null) {
            return entry.replace(value);
        }
        return null;
    }

    /**
     * Replaces the entry for the specified key
     * only if currently mapped to the specified value.
     * This is equivalent to
     * <pre>
     *  if (map.containsKey(key) &amp;&amp; map.get(key).equals(oldValue)) {
     *      map.put(key, newValue);
     *      return true;
     *  } else
     *      return false;</pre>
     *
     * @param key      the key whose mapping is to be removed from this map
     * @param oldValue the value expected to be associated with the specified key
     * @param newValue the value to be associated with the specified key
     * @return {@code true} if the value was replaced
     */
    public boolean replace(K key, V oldValue, V newValue) {
        CacheEntry<K, V> entry = getEntry(key);
        if ((entry != null) && entry.matches(oldValue)) {
            entry.replace(newValue);
            return true;
        }
        return false;
    }

    /**
     * Removes all of the mappings from this map.
     * This map will be empty after this call returns.
     */
    public void clear() {
        if (this.queue != null) {
            while (null != this.queue.poll()) {
                // clear out ref queue. We don't need to expunge entries
                // since table is getting cleared.
            }
        }
        this.modification++;
        Arrays.fill(this.table, null); // remove references ?
        this.size = 0;

        if (this.queue != null) {
            while (null != this.queue.poll()) {
                // Allocation of array may have caused GC,
                // which may have caused additional entries to go stale.
                // Removing these entries from the reference queue
                // will make them eligible for reclamation.
            }
        }
    }

    /**
     * Returns a {@link Set} view of the mappings contained in this map.
     * The set is backed by the map, so changes to the map are
     * reflected in the set, and vice-versa.  If the map is modified
     * while an iteration over the set is in progress (except through
     * the iterator's own {@code remove} operation, or through the
     * {@code setValue} operation on a map entry returned by the
     * iterator) the results of the iteration are undefined.  The set
     * supports element removal, which removes the corresponding
     * mapping from the map, via the {@code Iterator.remove},
     * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
     * {@code clear} operations.  It does not support the
     * {@code add} or {@code addAll} operations.
     *
     * @return a set of the mappings contained in this map
     */
    public Set<Map.Entry<K, V>> entrySet() {
        if (this.entries == null) {
            this.entries = new AbstractSet<Map.Entry<K, V>>() {
                public Iterator<Map.Entry<K, V>> iterator() {
                    return new AbstractIterator<Map.Entry<K, V>>() {
                        public Map.Entry<K, V> next() {
                            return nextEntry();
                        }
                    };
                }

                public int size() {
                    return Cache.this.size();
                }

                public void clear() {
                    Cache.this.clear();
                }

                public boolean contains(Object object) {
                    if (object instanceof Map.Entry) {
                        Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
                        CacheEntry<K, V> candidate = Cache.this.getEntry(entry.getKey());
                        return (candidate != null) && candidate.matches(entry.getValue());
                    }
                    return false;
                }

                public boolean remove(Object object) {
                    if (object instanceof Map.Entry) {
                        Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
                        return Cache.this.remove(entry.getKey(), entry.getValue());
                    }
                    return false;
                }

                public Object[] toArray() {
                    return toList().toArray();
                }

                public <T> T[] toArray(T[] array) {
                    return toList().toArray(array);
                }

                private List<Map.Entry> toList() {
                    List<Map.Entry> list = new ArrayList<>(size());
                    for (Map.Entry entry : this) {
                        list.add(entry);
                    }
                    return list;
                }
            };
        }
        return this.entries;
    }

    /**
     * Returns a {@link Set} view of the keys contained in this map.
     * The set is backed by the map, so changes to the map are
     * reflected in the set, and vice-versa.  If the map is modified
     * while an iteration over the set is in progress (except through
     * the iterator's own {@code remove} operation), the results of
     * the iteration are undefined.  The set supports element removal,
     * which removes the corresponding mapping from the map, via the
     * {@code Iterator.remove}, {@code Set.remove},
     * {@code removeAll}, {@code retainAll}, and {@code clear}
     * operations.  It does not support the {@code add} or {@code addAll}
     * operations.
     *
     * @return a set of the keys contained in this map
     */
    public Set<K> keySet() {
        if (this.keys == null) {
            this.keys = new AbstractSet<K>() {
                public Iterator<K> iterator() {
                    return new AbstractIterator<K>() {
                        public K next() {
                            return nextEntry().getKey();
                        }
                    };
                }

                public int size() {
                    return Cache.this.size();
                }

                public void clear() {
                    Cache.this.clear();
                }

                public boolean contains(Object key) {
                    return Cache.this.containsKey(key);
                }

                public boolean remove(Object key) {
                    return null != Cache.this.removeEntry(key);
                }
            };
        }
        return this.keys;
    }

    /**
     * Returns a {@link Collection} view of the values contained in this map.
     * The collection is backed by the map, so changes to the map are
     * reflected in the collection, and vice-versa.  If the map is
     * modified while an iteration over the collection is in progress
     * (except through the iterator's own {@code remove} operation),
     * the results of the iteration are undefined.  The collection
     * supports element removal, which removes the corresponding
     * mapping from the map, via the {@code Iterator.remove},
     * {@code Collection.remove}, {@code removeAll},
     * {@code retainAll} and {@code clear} operations.  It does not
     * support the {@code add} or {@code addAll} operations.
     *
     * @return a collection of the values contained in this map
     */
    public Collection<V> values() {
        if (this.values == null) {
            this.values = new AbstractCollection<V>() {
                public Iterator<V> iterator() {
                    return new AbstractIterator<V>() {
                        public V next() {
                            return nextEntry().getValue();
                        }
                    };
                }

                public int size() {
                    return Cache.this.size();
                }

                public void clear() {
                    Cache.this.clear();
                }

                public boolean contains(Object value) {
                    return Cache.this.containsValue(value);
                }
            };
        }
        return this.values;
    }

    /**
     * Retrieves object hash code and applies a supplemental hash function
     * to the result hash, which defends against poor quality hash functions.
     * This is critical because Cache uses power-of-two length hash tables,
     * that otherwise encounter collisions for hashCodes that do not differ
     * in lower bits.
     *
     * @param key the object which hash code is to be calculated
     * @return a hash code value for the specified object
     */
    private int hash(Object key) {
        if (key == null) {
            return this.hashSeed;
        }
        if (this.identity) {
            int hash = System.identityHashCode(key);
            return (hash << 1) - (hash << 8);
        }
        int hash = this.hashSeed ^ key.hashCode();
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        hash ^= (hash >>> 20) ^ (hash >>> 12);
        return hash ^ (hash >>> 7) ^ (hash >>> 4);
    }

    /**
     * Returns index of the specified hash code in the given table.
     * Note that the table size must be a power of two.
     *
     * @param hash  the hash code
     * @param table the table
     * @return an index of the specified hash code in the given table
     */
    private static int index(int hash, Object[] table) {
        return hash & (table.length - 1);
    }

    /**
     * Expunges stale entries and returns the table then.
     *
     * @return the table after first expunging stale entries
     */
    private CacheEntry<K, V>[] getTable() {
        CacheEntry<K, V>[] table = this.table;
        removeStaleEntries(table);
        return table;
    }

    @SuppressWarnings("unchecked")
    private CacheEntry<K, V>[] newTable(int size) {
        return (CacheEntry<K, V>[]) new CacheEntry[size];
    }

    private Ref<V> removeEntry(Object key) {
        CacheEntry<K, V>[] table = getTable();
        int hash = hash(key);
        int index = index(hash, table);

        CacheEntry<K, V> prev = table[index];
        CacheEntry<K, V> cur = prev;
        while (cur != null) {
            CacheEntry<K, V> next = cur.next;
            if (cur.matches(hash, key)) {
                this.modification++;
                this.size--;
                if (prev == cur) {
                    table[index] = next;
                }
                else {
                    prev.next = next;
                }
                Ref<V> value = cur.value;
                cur.key = null;
                cur.value = null;
                cur.next = null;
                return value;
            }
            prev = cur;
            cur = next;
        }
        return null;
    }

    private void removeStaleEntries(CacheEntry<K, V>[] table) {
        if (this.queue != null) {
            for (Object reference = this.queue.poll(); reference != null; reference = this.queue.poll()) {
                if (reference instanceof Ref) {
                    Ref ref = (Ref) reference;
                    @SuppressWarnings("unchecked")
                    CacheEntry<K, V> entry = (CacheEntry<K, V>) ref.getOwner();
                    if ((ref == entry.key) || (ref == entry.value)) {
                        int index = index(entry.hash, table);

                        CacheEntry<K, V> prev = table[index];
                        CacheEntry<K, V> cur = prev;
                        while (cur != null) {
                            CacheEntry<K, V> next = cur.next;
                            if (cur == entry) {
                                // not needed for stale entries: this.modification++;
                                this.size--;
                                if (prev == cur) {
                                    table[index] = next;
                                }
                                else {
                                    prev.next = next;
                                }
                                entry.key = null;
                                entry.value = null;
                                // entry.next = null;
                                // stale entry may be in use by a HashIterator
                                break;
                            }
                            prev = cur;
                            cur = next;
                        }
                    }
                }
            }
        }
    }

    /**
     * Rehashes the contents of this map into a new array with a
     * larger capacity.  This method is called automatically when the
     * number of keys in this map reaches its threshold.
     * <p/>
     * If current capacity is MAXIMUM_CAPACITY, this method does not
     * resize the map, but sets threshold to Integer.MAX_VALUE.
     * This has the effect of preventing future calls.
     *
     * @param capacity the new capacity, MUST be a power of two;
     *                 must be greater than current capacity unless current
     *                 capacity is MAXIMUM_CAPACITY (in which case value
     *                 is irrelevant).
     */
    private void resize(int capacity) {
        CacheEntry<K, V>[] oldTable = getTable();
        if (oldTable.length == MAXIMUM_CAPACITY) {
            this.threshold = Integer.MAX_VALUE;
        }
        else {
            CacheEntry<K, V>[] newTable = newTable(capacity);
            moveEntries(oldTable, newTable);
            // If ignoring null elements and processing ref queue
            // caused massive shrinkage, then restore old table.
            // This should be rare, but avoids unbounded expansion
            // of garbage-filled tables.
            if (this.size >= this.threshold / 2) {
                this.table = newTable;
                this.threshold = (int) (this.table.length * LOAD_FACTOR);
                this.modification++;
            }
            else {
                removeStaleEntries(newTable);
                moveEntries(newTable, oldTable);
            }
        }
    }

    private void moveEntries(CacheEntry<K, V>[] oldTable, CacheEntry<K, V>[] newTable) {
        int oldIndex = oldTable.length;
        while (0 < oldIndex--) {
            CacheEntry<K, V> entry = oldTable[oldIndex];
            oldTable[oldIndex] = null;
            while (entry != null) {
                CacheEntry<K, V> next = entry.next;
                if (entry.key.isStale() || entry.value.isStale()) {
                    this.size--;
                    entry.key = null;
                    entry.value = null;
                    entry.next = null;
                }
                else {
                    int newIndex = index(entry.hash, newTable);
                    entry.next = newTable[newIndex];
                    newTable[newIndex] = entry;
                }
                entry = next;
            }
        }
    }

    /**
     * Basic interface for references.
     * It defines the operations common for the all kind of references.
     *
     * @param <T> the type of object to refer
     */
    private static interface Ref<T> {
        /**
         * Returns the object that possesses information about the reference.
         *
         * @return the owner of the reference or {@code null} if the owner is unknown
         */
        Object getOwner();

        /**
         * Returns the object to refer.
         *
         * @return the referred object or {@code null} if it was collected
         */
        T getReferent();

        /**
         * Determines whether the referred object was taken by the garbage collector or not.
         *
         * @return {@code true} if the referred object was collected
         */
        boolean isStale();
    }

    /**
     * Represents a reference kind.
     */
    public static enum Kind {
        STRONG {
            <T> Ref<T> create(Object owner, T value, ReferenceQueue<? super T> queue) {
                return new Strong<>(owner, value);
            }
        },
        SOFT {
            <T> Ref<T> create(Object owner, T referent, ReferenceQueue<? super T> queue) {
                return (referent == null)
                        ? new Strong<>(owner, referent)
                        : new Soft<>(owner, referent, queue);
            }
        },
        WEAK {
            <T> Ref<T> create(Object owner, T referent, ReferenceQueue<? super T> queue) {
                return (referent == null)
                        ? new Strong<>(owner, referent)
                        : new Weak<>(owner, referent, queue);
            }
        };

        /**
         * Creates a reference to the specified object.
         *
         * @param <T>      the type of object to refer
         * @param owner    the owner of the reference, if needed
         * @param referent the object to refer
         * @param queue    the queue to register the reference with,
         *                 or {@code null} if registration is not required
         * @return the reference to the specified object
         */
        abstract <T> Ref<T> create(Object owner, T referent, ReferenceQueue<? super T> queue);

        /**
         * This is an implementation of the {@link com.oracle.util.Cache.Ref} interface
         * that uses the strong references that prevent their referents
         * from being made finalizable, finalized, and then reclaimed.
         *
         * @param <T> the type of object to refer
         */
        private static final class Strong<T> implements Ref<T> {
            private final Object owner;
            private final T referent;

            /**
             * Creates a strong reference to the specified object.
             *
             * @param owner    the owner of the reference, if needed
             * @param referent the non-null object to refer
             */
            private Strong(Object owner, T referent) {
                this.owner = owner;
                this.referent = referent;
            }

            /**
             * Returns the object that possesses information about the reference.
             *
             * @return the owner of the reference or {@code null} if the owner is unknown
             */
            public Object getOwner() {
                return this.owner;
            }

            /**
             * Returns the object to refer.
             *
             * @return the referred object
             */
            public T getReferent() {
                return this.referent;
            }

            /**
             * Determines whether the referred object was taken by the garbage collector or not.
             *
             * @return {@code true} if the referred object was collected
             */
            public boolean isStale() {
                return false;
            }
        }

        /**
         * This is an implementation of the {@link com.oracle.util.Cache.Ref} interface
         * that uses the soft references that are cleared at the discretion
         * of the garbage collector in response to a memory request.
         *
         * @param <T> the type of object to refer
         * @see java.lang.ref.SoftReference
         */
        private static final class Soft<T> extends SoftReference<T> implements Ref<T> {
            private final Object owner;

            /**
             * Creates a soft reference to the specified object.
             *
             * @param owner    the owner of the reference, if needed
             * @param referent the non-null object to refer
             * @param queue    the queue to register the reference with,
             *                 or {@code null} if registration is not required
             */
            private Soft(Object owner, T referent, ReferenceQueue<? super T> queue) {
                super(referent, queue);
                this.owner = owner;
            }

            /**
             * Returns the object that possesses information about the reference.
             *
             * @return the owner of the reference or {@code null} if the owner is unknown
             */
            public Object getOwner() {
                return this.owner;
            }

            /**
             * Returns the object to refer.
             *
             * @return the referred object or {@code null} if it was collected
             */
            public T getReferent() {
                return get();
            }

            /**
             * Determines whether the referred object was taken by the garbage collector or not.
             *
             * @return {@code true} if the referred object was collected
             */
            public boolean isStale() {
                return null == get();
            }
        }

        /**
         * This is an implementation of the {@link com.oracle.util.Cache.Ref} interface
         * that uses the weak references that do not prevent their referents
         * from being made finalizable, finalized, and then reclaimed.
         *
         * @param <T> the type of object to refer
         * @see java.lang.ref.WeakReference
         */
        private static final class Weak<T> extends WeakReference<T> implements Ref<T> {
            private final Object owner;

            /**
             * Creates a weak reference to the specified object.
             *
             * @param owner    the owner of the reference, if needed
             * @param referent the non-null object to refer
             * @param queue    the queue to register the reference with,
             *                 or {@code null} if registration is not required
             */
            private Weak(Object owner, T referent, ReferenceQueue<? super T> queue) {
                super(referent, queue);
                this.owner = owner;
            }

            /**
             * Returns the object that possesses information about the reference.
             *
             * @return the owner of the reference or {@code null} if the owner is unknown
             */
            public Object getOwner() {
                return this.owner;
            }

            /**
             * Returns the object to refer.
             *
             * @return the referred object or {@code null} if it was collected
             */
            public T getReferent() {
                return get();
            }

            /**
             * Determines whether the referred object was taken by the garbage collector or not.
             *
             * @return {@code true} if the referred object was collected
             */
            public boolean isStale() {
                return null == get();
            }
        }
    }

    /**
     * Represents a cache entry (key-value pair).
     */
    private static final class CacheEntry<K, V> {
        private final Cache<K, V> cache;
        private final int hash;
        private Ref<K> key;
        private Ref<V> value;
        private CacheEntry<K, V> next;
        private WeakReference<Map.Entry<K, V>> entry;

        /**
         * Constructs an entry for the cache.
         *
         * @param hash  the hash code calculated for the entry key
         * @param key   the entry key
         * @param value the initial value of the entry
         * @param next  the next entry in a chain
         */
        private CacheEntry(Cache<K, V> cache, int hash, K key, V value, CacheEntry<K, V> next) {
            this.cache = cache;
            this.hash = hash;
            this.key = this.cache.keyKind.create(this, key, this.cache.queue);
            this.value = this.cache.valueKind.create(this, value, this.cache.queue);
            this.next = next;
        }

        /**
         * Determines whether the entry has the given key with the given hash code.
         *
         * @param hash an expected hash code
         * @param key  an object to be compared with the entry key
         * @return {@code true} if the entry has the given key with the given hash code;
         *         {@code false} otherwise
         */
        private boolean matches(int hash, Object key) {
            return (this.hash == hash) && equals(this.key.getReferent(), key);
        }

        /**
         * Determines whether the entry has the given value.
         *
         * @param value an object to be compared with the entry value
         * @return {@code true} if the entry has the given value;
         *         {@code false} otherwise
         */
        private boolean matches(Object value) {
            return equals(this.value.getReferent(), value);
        }

        /**
         * Ensures that both given objects are equal.
         * It uses reference-equality in place of object-equality
         * if {@code identity} is set to {@code true} in the Cache constructor.
         *
         * @param first  a first object
         * @param second a second object to be compared with the first object
         * @return {@code true} if the first object is equal to the second object;
         *         {@code false} otherwise
         * @see com.oracle.util.Cache#Cache(com.oracle.util.Cache.Kind, com.oracle.util.Cache.Kind, boolean)
         */
        private boolean equals(Object first, Object second) {
            return (first == second) || !this.cache.identity && (first != null) && first.equals(second);
        }

        /**
         * Replaces the entry value with the specified one.
         *
         * @param value new value to be stored in the entry
         * @return old value corresponding to the entry
         */
        private V replace(V value) {
            V old = this.value.getReferent();
            this.value = this.cache.valueKind.create(this, value, this.cache.queue);
            if (this.entry != null) {
                Map.Entry<K, V> proxy = this.entry.get();
                if (proxy != null) {
                    proxy.getValue(); // update strong reference if it exists
                }
            }
            return old;
        }

        /**
         * Creates a public view for the cache entry.
         * This view uses the strong references that prevent their referents
         * from being made finalizable, finalized, and then reclaimed.
         *
         * @return a custom implementation of the {@link java.util.Map.Entry} interface
         */
        private Map.Entry<K, V> getMapEntry() {
            if (this.entry != null) {
                Map.Entry<K, V> entry = this.entry.get();
                if (entry != null) {
                    return entry;
                }
            }
            Map.Entry<K, V> entry = new Map.Entry<K, V>() {
                private K key = CacheEntry.this.key.getReferent(); // strong reference
                private V value = CacheEntry.this.value.getReferent(); // strong reference

                /**
                 * Returns the key corresponding to the entry.
                 * Updates the strong reference to the key
                 * if the entry is not removed.
                 *
                 * @return the key corresponding to the entry
                 */
                public K getKey() {
                    if (CacheEntry.this.key != null) {
                        this.key = CacheEntry.this.key.getReferent();
                    }
                    return this.key;
                }

                /**
                 * Returns the value corresponding to the entry.
                 * Updates the strong reference to the value
                 * if the entry is not removed.
                 *
                 * @return the value corresponding to the entry
                 */
                public V getValue() {
                    if (CacheEntry.this.value != null) {
                        this.value = CacheEntry.this.value.getReferent();
                    }
                    return this.value;
                }

                /**
                 * Replaces the entry value with the specified one.
                 *
                 * @param value  new value to be stored in the entry
                 * @return old value corresponding to the entry
                 */
                public V setValue(V value) {
                    if (CacheEntry.this.value != null) {
                        return CacheEntry.this.replace(value);
                    }
                    V old = this.value;
                    this.value = value;
                    return old;
                }

                /**
                 * Compares the specified object with the entry.
                 * Returns {@code true} if the given object is a map entry
                 * and these two entries represent the same mapping,
                 * i.e. their keys are equal and their values are equal too.
                 * This ensures that this method works properly across
                 * different implementations of the {@link java.util.Map.Entry} interface.
                 *
                 * @param object  object to be compared with the entry
                 * @return {@code true} if the specified object is equal to the entry
                 */
                public boolean equals(Object object) {
                    if (object instanceof Map.Entry) {
                        Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
                        return CacheEntry.this.equals(this.key, entry.getKey())
                                && CacheEntry.this.equals(this.value, entry.getValue());
                    }
                    return false;
                }

                /**
                 * Returns the hash code value for the cache entry.
                 * This hash code is defined to be the exclusive disjunction
                 * of the corresponding key and value hash codes.
                 * This ensures that {@code e1.equals(e2)}
                 * implies that {@code e1.hashCode()==e2.hashCode()}
                 * for any two entries {@code e1} and {@code e2},
                 * as required by the general contract of {@link Object#hashCode()}.
                 *
                 * @return the hash code value for this map entry
                 */
                public int hashCode() {
                    return Objects.hashCode(this.key)
                            ^ Objects.hashCode(this.value);
                }

                /**
                 * Returns a string that is a textual representation of the entry.
                 * The result is "&lt;key&gt;=&lt;value&gt;", where
                 * &lt;key&gt; is a string representation of the key and
                 * &lt;value&gt; is a string representation of the value.
                 *
                 * @return a string representation of the entry
                 */
                public String toString() {
                    return this.key + "=" + this.value;
                }
            };
            this.entry = new WeakReference<>(entry);
            return entry;
        }
    }

    /**
     * An iterator over the cache entries.
     */
    private abstract class AbstractIterator<T> implements Iterator<T> {
        private CacheEntry<K, V>[] table;
        private int modification;
        private int index;
        private CacheEntry<K, V> entry;
        private Map.Entry<K, V> reference; // avoid disappearance between hasNext() and next()
        private Map.Entry<K, V> current; // avoid disappearance between nextEntry() and any use of the entry

        protected AbstractIterator() {
            this.table = Cache.this.getTable();
            this.modification = Cache.this.modification;
            this.index = Cache.this.isEmpty() ? 0 : this.table.length;
        }

        /**
         * Returns {@code true} if the iteration has more elements.
         * In other words, this method returns {@code true}
         * if {@link #nextEntry} would return an element
         * rather than throwing an exception.
         *
         * @return {@code true} if the iteration has more elements
         */
        public boolean hasNext() {
            while (this.reference == null) {
                CacheEntry<K, V> entry = this.entry;
                int index = this.index;
                while ((entry == null) && (index > 0)) {
                    entry = this.table[--index];
                }
                this.index = index;
                this.entry = entry;
                if (entry == null) {
                    return false;
                }
                this.reference = entry.getMapEntry(); // strong references
                if (entry.key.isStale() || entry.value.isStale()) {
                    this.reference = null;
                    this.entry = this.entry.next;
                }
            }
            return true;
        }

        /**
         * Removes from the cache the last element returned by this iterator.
         * This method can be called only once per call to {@link #nextEntry}.
         *
         * @throws IllegalStateException if the {@code next} method has not yet
         *                               been called, or the {@code remove} method has already
         *                               been called after the last call to the {@code next} method
         * @throws java.util.ConcurrentModificationException
         *                               if the underlying collection
         *                               is modified while the iteration is in progress in any way
         *                               other than by calling this method
         */
        public void remove() {
            if (this.current == null) {
                throw new IllegalStateException();
            }
            if (Cache.this.modification != this.modification) {
                throw new ConcurrentModificationException();
            }
            Cache.this.remove(this.current.getKey());
            this.modification = Cache.this.modification;
            this.current = null;
        }

        /**
         * Returns the next element in the iteration.
         *
         * @return the next element in the iteration
         * @throws java.util.NoSuchElementException
         *          if the iteration has no more elements
         */
        protected Map.Entry<K, V> nextEntry() {
            if (Cache.this.modification != this.modification) {
                throw new ConcurrentModificationException();
            }
            if (this.reference == null && !hasNext()) {
                throw new NoSuchElementException();
            }
            this.entry = this.entry.next;
            this.current = this.reference;
            this.reference = null;
            return this.current;
        }
    }
}