/*

 * @(#)WeakHashMap.java 1.5 98/09/30

 *

 * Copyright 1998 by Sun Microsystems, Inc.,

 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.

 * All rights reserved.

 *

 * This software is the confidential and proprietary information

 * of Sun Microsystems, Inc. ("Confidential Information").  You

 * shall not disclose such Confidential Information and shall use

 * it only in accordance with the terms of the license agreement

 * you entered into with Sun.

 */

// From https://github.com/mernst/plume-lib/blob/df0bfafc3c16848d88f4ea0ef3c8bf3367ae085e/java/src/plume/WeakHasherMap.java

static final class WeakHasherMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {

    private Hasher hasher = null;

    /*@Pure*/

    private boolean keyEquals(Object k1, Object k2) {

  return (hasher==null ? k1.equals(k2)

           : hasher.equals(k1, k2));

    }

    /*@Pure*/

    private int keyHashCode(Object k1) {

  return (hasher==null ? k1.hashCode()

           : hasher.hashCode(k1));

    }

    // The WeakKey class can't be static because it depends on the hasher.

    // That in turn means that its methods can't be static.

    // However, I need to be able to call the methods such as create() that

    // were static in the original version of this code.

    // This finesses that.

    private /*@Nullable*/ WeakKey WeakKeyCreate(K k) {

  if (k == null) return null;

  else return new WeakKey(k);

    }

    private /*@Nullable*/ WeakKey WeakKeyCreate(K k, ReferenceQueue<? super K> q) {

  if (k == null) return null;

  else return new WeakKey(k, q);

    }

    // Cannot be a static class: uses keyHashCode() and keyEquals()

    private final class WeakKey extends WeakReference<K> {

  private int hash; /* Hashcode of key, stored here since the key

           may be tossed by the GC */

  private WeakKey(K k) {

      super(k);

      hash = keyHashCode(k);

  }

  private /*@Nullable*/ WeakKey create(K k) {

      if (k == null) return null;

      else return new WeakKey(k);

  }

  private WeakKey(K k, ReferenceQueue<? super K> q) {

      super(k, q);

      hash = keyHashCode(k);

  }

  private /*@Nullable*/ WeakKey create(K k, ReferenceQueue<? super K> q) {

      if (k == null) return null;

      else return new WeakKey(k, q);

  }

        /* A WeakKey is equal to another WeakKey iff they both refer to objects

     that are, in turn, equal according to their own equals methods */

  /*@Pure*/

  @Override

  public boolean equals(/*@Nullable*/ Object o) {

            if (o == null) return false; // never happens

      if (this == o) return true;

            // This test is illegal because WeakKey is a generic type,

            // so use the getClass hack below instead.

      // if (!(o instanceof WeakKey)) return false;

            if (!(o.getClass().equals(WeakKey.class))) return false;

      Object t = this.get();

            @SuppressWarnings("unchecked")

      Object u = ((WeakKey)o).get();

      if ((t == null) || (u == null)) return false;

      if (t == u) return true;

      return keyEquals(t, u);

  }

  /*@Pure*/

  @Override

  public int hashCode() {

      return hash;

  }

    }

    /* Hash table mapping WeakKeys to values */

    private HashMap<WeakKey,V> hash;

    /* Reference queue for cleared WeakKeys */

    private ReferenceQueue<? super K> queue = new ReferenceQueue<K>();

    /* Remove all invalidated entries from the map, that is, remove all entries

       whose keys have been discarded.  This method should be invoked once by

       each public mutator in this class.  We don't invoke this method in

       public accessors because that can lead to surprising

       ConcurrentModificationExceptions. */

    @SuppressWarnings("unchecked")

    private void processQueue() {

  WeakKey wk;

  while ((wk = (WeakKey)queue.poll()) != null) { // unchecked cast

      hash.remove(wk);

  }

    }

    /* -- Constructors -- */

    /**

     * Constructs a new, empty <code>WeakHashMap</code> with the given

     * initial capacity and the given load factor.

     *

     * @param  initialCapacity  the initial capacity of the

     *                          <code>WeakHashMap</code>

     *

     * @param  loadFactor       the load factor of the <code>WeakHashMap</code>

     *

     * @throws IllegalArgumentException  If the initial capacity is less than

     *                                   zero, or if the load factor is

     *                                   nonpositive

     */

    public WeakHasherMap(int initialCapacity, float loadFactor) {

  hash = new HashMap<WeakKey,V>(initialCapacity, loadFactor);

    }

    /**

     * Constructs a new, empty <code>WeakHashMap</code> with the given

     * initial capacity and the default load factor, which is

     * <code>0.75</code>.

     *

     * @param  initialCapacity  the initial capacity of the

     *                          <code>WeakHashMap</code>

     *

     * @throws IllegalArgumentException  If the initial capacity is less than

     *                                   zero

     */

    public WeakHasherMap(int initialCapacity) {

  hash = new HashMap<WeakKey,V>(initialCapacity);

    }

    /**

     * Constructs a new, empty <code>WeakHashMap</code> with the default

     * capacity and the default load factor, which is <code>0.75</code>.

     */

    public WeakHasherMap() {

  hash = new HashMap<WeakKey,V>();

    }

    /**

     * Constructs a new, empty <code>WeakHashMap</code> with the default

     * capacity and the default load factor, which is <code>0.75</code>.

     * The <code>WeakHashMap</code> uses the specified hasher for hashing

     * keys and comparing them for equality.

     * @param h the Hasher to use when hashing values for this map

     */

    public WeakHasherMap(Hasher h) {

  hash = new HashMap<WeakKey,V>();

  hasher = h;

    }

    /* -- Simple queries -- */

    /**

     * Returns the number of key-value mappings in this map.

     * <strong>Note:</strong> <em>In contrast to most implementations of the

     * <code>Map</code> interface, the time required by this operation is

     * linear in the size of the map.</em>

     */

    /*@Pure*/

    @Override

    public int size() {

  return entrySet().size();

    }

    /**

     * Returns <code>true</code> if this map contains no key-value mappings.

     */

    /*@Pure*/

    @Override

    public boolean isEmpty() {

  return entrySet().isEmpty();

    }

    /**

     * Returns <code>true</code> if this map contains a mapping for the

     * specified key.

     *

     * @param   key   the key whose presence in this map is to be tested

     */

    /*@Pure*/

    @Override

    public boolean containsKey(Object key) {

        @SuppressWarnings("unchecked")

        K kkey = (K) key;

  return hash.containsKey(WeakKeyCreate(kkey));

    }

    /* -- Lookup and modification operations -- */

    /**

     * Returns the value to which this map maps the specified <code>key</code>.

     * If this map does not contain a value for this key, then return

     * <code>null</code>.

     *

     * @param  key  the key whose associated value, if any, is to be returned

     */

    /*@Pure*/

    @Override

    public /*@Nullable*/ V get(Object key) {  // type of argument is Object, not K

        @SuppressWarnings("unchecked")

        K kkey = (K) key;

  return hash.get(WeakKeyCreate(kkey));

    }

    /**

     * Updates this map so that the given <code>key</code> maps to the given

     * <code>value</code>.  If the map previously contained a mapping for

     * <code>key</code> then that mapping is replaced and the previous value is

     * returned.

     *

     * @param  key    the key that is to be mapped to the given

     *                <code>value</code>

     * @param  value  the value to which the given <code>key</code> is to be

     *                mapped

     *

     * @return  the previous value to which this key was mapped, or

     *          <code>null</code> if if there was no mapping for the key

     */

    @Override

    public V put(K key, V value) {

  processQueue();

  return hash.put(WeakKeyCreate(key, queue), value);

    }

    /**

     * Removes the mapping for the given <code>key</code> from this map, if

     * present.

     *

     * @param  key  the key whose mapping is to be removed

     *

     * @return  the value to which this key was mapped, or <code>null</code> if

     *          there was no mapping for the key

     */

    @Override

    public V remove(Object key) { // type of argument is Object, not K

  processQueue();

        @SuppressWarnings("unchecked")

        K kkey = (K) key;

  return hash.remove(WeakKeyCreate(kkey));

    }

    /**

     * Removes all mappings from this map.

     */

    @Override

    public void clear() {

  processQueue();

  hash.clear();

    }

    /* -- Views -- */

    /* Internal class for entries */

    // This can't be static, again because of dependence on hasher.

    @SuppressWarnings("TypeParameterShadowing")

    private final class Entry<K,V> implements Map.Entry<K,V> {

  private Map.Entry<WeakKey,V> ent;

  private K key;  /* Strong reference to key, so that the GC

           will leave it alone as long as this Entry

           exists */

  Entry(Map.Entry<WeakKey,V> ent, K key) {

      this.ent = ent;

      this.key = key;

  }

  /*@Pure*/

  @Override

  public K getKey() {

      return key;

  }

  /*@Pure*/

  @Override

  public V getValue() {

      return ent.getValue();

  }

  @Override

  public V setValue(V value) {

      return ent.setValue(value);

  }

        /*@Pure*/

        private boolean keyvalEquals(K o1, K o2) {

      return (o1 == null) ? (o2 == null) : keyEquals(o1, o2);

  }

        /*@Pure*/

        private boolean valEquals(V o1, V o2) {

      return (o1 == null) ? (o2 == null) : o1.equals(o2);

  }

        /*@Pure*/

        @SuppressWarnings("NonOverridingEquals")

        public boolean equals(Map.Entry<K,V> e /* Object o*/) {

            // if (! (o instanceof Map.Entry)) return false;

            // Map.Entry<K,V> e = (Map.Entry<K,V>)o;

      return (keyvalEquals(key, e.getKey())

        && valEquals(getValue(), e.getValue()));

  }

  /*@Pure*/

  @Override

  public int hashCode() {

      V v;

      return (((key == null) ? 0 : keyHashCode(key))

        ^ (((v = getValue()) == null) ? 0 : v.hashCode()));

  }

    }

    /* Internal class for entry sets */

    private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {

  Set<Map.Entry<WeakKey,V>> hashEntrySet = hash.entrySet();

  @Override

  public Iterator<Map.Entry<K,V>> iterator() {

      return new Iterator<Map.Entry<K,V>>() {

    Iterator<Map.Entry<WeakKey,V>> hashIterator = hashEntrySet.iterator();

    Map.Entry<K,V> next = null;

    @Override

    public boolean hasNext() {

        while (hashIterator.hasNext()) {

      Map.Entry<WeakKey,V> ent = hashIterator.next();

      WeakKey wk = ent.getKey();

      K k = null;

      if ((wk != null) && ((k = wk.get()) == null)) {

          /* Weak key has been cleared by GC */

          continue;

      }

      next = new Entry<K,V>(ent, k);

      return true;

        }

        return false;

    }

    @Override

    public Map.Entry<K,V> next() {

        if ((next == null) && !hasNext())

      throw new NoSuchElementException();

        Map.Entry<K,V> e = next;

        next = null;

        return e;

    }

    @Override

    public void remove() {

        hashIterator.remove();

    }

      };

  }

  /*@Pure*/

  @Override

  public boolean isEmpty() {

      return !(iterator().hasNext());

  }

  /*@Pure*/

  @Override

  public int size() {

      int j = 0;

      for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); i.next()) j++;

      return j;

  }

  @Override

  public boolean remove(Object o) {

      processQueue();

      if (!(o instanceof Map.Entry<?,?>)) return false;

            @SuppressWarnings("unchecked")

      Map.Entry<K,V> e = (Map.Entry<K,V>)o; // unchecked cast

      Object ev = e.getValue();

      WeakKey wk = WeakKeyCreate(e.getKey());

      Object hv = hash.get(wk);

      if ((hv == null)

    ? ((ev == null) && hash.containsKey(wk)) : hv.equals(ev)) {

    hash.remove(wk);

    return true;

      }

      return false;

  }

  /*@Pure*/

  @Override

  public int hashCode() {

      int h = 0;

      for (Iterator<Map.Entry<WeakKey,V>> i = hashEntrySet.iterator(); i.hasNext(); ) {

    Map.Entry<WeakKey,V> ent = i.next();

    WeakKey wk = ent.getKey();

    Object v;

    if (wk == null) continue;

    h += (wk.hashCode()

          ^ (((v = ent.getValue()) == null) ? 0 : v.hashCode()));

      }

      return h;

  }

    }

    private /*@Nullable*/ Set<Map.Entry<K,V>> entrySet = null;

    /**

     * Returns a <code>Set</code> view of the mappings in this map.

     */

    /*@SideEffectFree*/

    @Override

    public Set<Map.Entry<K,V>> entrySet() {

  if (entrySet == null) entrySet = new EntrySet();

  return entrySet;

    }

    // find matching key

    K findKey(O key) {

      processQueue();

      K kkey = (K) key;

      // TODO: use replacement for HashMap to avoid reflection

      WeakKey wkey = WeakKeyCreate(kkey);

      WeakKey found = hashMap_findKey(hash, wkey);

      ret found == null ? null : found.get();

    }

}