/*
 * Written by Dawid Kurzyniec and released to the public domain, as explained
 * at http://creativecommons.org/licenses/publicdomain
 */

package edu.emory.mathcs.util.collections;

import java.util.*;
import java.lang.ref.*;

/**
 * Wrapper for a map that refers to values via weak references, thus not
 * keeping them from garbage collection. After a value becomes unreferenced
 * and collected, all the corresponding map entries are removed. (The cleanup
 * is not asynchronous but piggybacks on other map operations). This class
 * is a companion to {@link java.util.WeakHashMap}.
 * <p>
 * It is required that the backing map passed to the constructor is empty, and
 * that it is not used directly after this map is created.
 * <p>
 * Note: the values stored in this map keep strong references to their keys.
 * Therefore, using a WeakHashMap as a backing map will NOT yield a map
 * with both weak keys and weak values.
 *
 * @author Dawid Kurzyniec
 * @version 1.0
 */
class WeakValueMap extends AbstractMap implements Map {

    private final Map map;
    transient Set entrySet;

    private final ReferenceQueue rqueue = new ReferenceQueue();

    /**
     * Creates new WeakValueMap using java.util.HashMap as the backing storage.
     */
    public WeakValueMap() {
        this(new HashMap());
    }

    /**
     * Creates new WeakValueMap using the specified map as the backing storage.
     */
    public WeakValueMap(Map map) {
        if (!map.isEmpty()) throw new IllegalStateException("Backing map is not empty");
        this.map = map;
    }

    public int size() {
        // try to avoid synchronization
        if (map.isEmpty()) return 0;
        prune();
        return map.size();
    }

    public void clear() {
        map.clear();
    }

    public boolean isEmpty() {
        // try to avoid synchronization
        if (map.isEmpty()) return true;
        prune();
        return map.isEmpty();
    }

    public boolean containsKey(Object key) {
        // make sure that containsKey returns false if get has returned null
        return get(key) != null;
    }

    public boolean containsValue(Object value) {
        if (map.isEmpty()) return false;
        prune();
        return (value == null) ? false : map.containsValue(new CompareRef(value));
    }

    public void putAll(Map t) {
        if (!map.isEmpty()) prune();
        for (Iterator itr = t.entrySet().iterator(); itr.hasNext();) {
            Map.Entry e = (Map.Entry)itr.next();
            Object key = e.getKey();
            map.put(key, wrapValue(key, e.getValue(), rqueue));
        }
    }

    public Set entrySet() {
        if (entrySet == null) entrySet = new EntrySetView();
        return entrySet;
    }

    public Object get(Object key) {
        if (map.isEmpty()) return null;
        prune();
        return unwrapValue(map.get(key));
    }

    public Object remove(Object key) {
        if (map.isEmpty()) return null;
        prune();
        return detachValue(map.remove(key));
    }

    public Object put(Object key, Object value) {
        Object ref = wrapValue(key, value, rqueue);
        if (map.isEmpty()) {
            map.put(key, ref);
            return null;
        }
        else {
            prune();
            return detachValue(map.put(key, wrapValue(key, value, rqueue)));
        }
    }

    private static class ValueRef extends WeakReference {
        final Object key;
        ValueRef(Object key, Object val, ReferenceQueue rqueue) {
            super(val, rqueue);
            this.key = key;
        }
        public Object getKey() {
            return key;
        }
        public Object getValue() {
            return get();
        }
        public int hashCode() {
            Object val = getValue();
            return (val == null) ? 0 : val.hashCode();
        }
        public boolean equals(Object other) {
            if (other == this) return true;
            else if (other instanceof ValueRef) {
                return eqNonNull(this.getValue(), ((ValueRef)other).getValue());
            }
            else if (other instanceof CompareRef) {
                return eqNonNull(this.getValue(), ((CompareRef)other).getValue());
            }
            else return false;
        }
    }

    private static class CompareRef {
        final Object val;
        CompareRef(Object val) { this.val = val; }
        public Object getValue() { return val; }
        public int hashCode() { return val.hashCode(); }
        public boolean equals(Object other) {
            if (other == this) return true;
            if (other instanceof ValueRef) {
                return eqNonNull(this.getValue(), ((ValueRef)other).getValue());
            }
            else return false;
        }
    }

    private void prune() {
        ValueRef ref;
        while ((ref = (ValueRef)rqueue.poll()) != null) {
            Object key = ref.getKey();
            // make sure that not overwritten already
            if (map.get(key) == ref) {
                map.remove(key);
            }
        }
    }

    private static boolean eqNonNull(Object o1, Object o2) {
        return (o1 == null) ? false : o1.equals(o2);
    }

    private class EntrySetView extends AbstractSet {
        EntrySetView() {}

        public int size() {
            if (map.isEmpty()) return 0;
            prune();
            return map.size();
        }

        public void clear() {
            map.clear();
        }
        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry)) return false;
            Map.Entry e = (Map.Entry)o;
            Object val = e.getValue();
            if (val == null) return false;
            return eqNonNull(unwrapValue(map.get(e.getKey())), val);
        }

        public boolean isEmpty() {
            if (map.isEmpty()) return true;
            prune();
            return map.isEmpty();
        }

        public boolean remove(Object o) {
            if (map.isEmpty()) return false;
            prune();
            if (!(o instanceof Map.Entry)) return false;
            Map.Entry e = (Map.Entry)o;
            Object key = e.getKey();
            Object val = e.getValue();
            if (val == null) return false;
            ValueRef ref = (ValueRef)map.get(key);
            if (ref == null || !val.equals(ref.getValue())) return false;

            map.remove(key);
            return true;
        }

        public Iterator iterator() {
            return new EntryIterator(map.entrySet().iterator());
        }
    }

    private class EntryIterator implements Iterator {
        final Iterator itr;
        EntryWrapper cursor;
        EntryWrapper lastRet;
        EntryIterator(Iterator itr) {
            this.itr = itr;
            this.cursor = fetchNext();
        }
        public boolean hasNext() { return cursor != null; }
        public Object next() {
            if (!hasNext()) throw new NoSuchElementException();
            lastRet = cursor;
            cursor = fetchNext();
            return lastRet;
        }
        public void remove() {
            if (lastRet == null) throw new IllegalStateException();
            lastRet.clear();
            lastRet = null;
        }
        private EntryWrapper fetchNext() {
            while (itr.hasNext()) {
                Map.Entry e = (Map.Entry)itr.next();
                Object val = unwrapValue(e.getValue());
                if (val != null) {
                    return new EntryWrapper(e, val);
                }
            }
            return null;
        }
    }

    private class EntryWrapper implements Map.Entry {
        final Map.Entry entry;
        Object val; // prevent GC
        EntryWrapper(Map.Entry entry, Object val) {
            this.entry = entry;
            this.val = val;
        }
        public Object getKey()             { return entry.getKey(); }
        public Object getValue()           { return val; }

        public Object setValue(Object val) {
            Object old = this.val;
            entry.setValue(wrapValue(entry.getKey(), val, rqueue));
            this.val = val;
            return old;
        }

        // effectively removes the mapping, but without messing up
        // iterators in progress that have passed through this entry already
        void clear() {
            ValueRef val = (ValueRef)entry.getValue();
            val.clear();
            val.enqueue();
        }

        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry)) return false;
            Map.Entry e = (Map.Entry)o;
            return eq(entry.getKey(), e.getKey()) && val.equals(e.getValue());
        }

        public int hashCode() {
            Object key = entry.getKey();
            return ((key == null) ? 0 : key.hashCode()) ^ val.hashCode();
        }

        public String toString() {
            return entry.getKey() + "=" + val;
        }

    }

    private static ValueRef wrapValue(Object key, Object value, ReferenceQueue rqueue) {
        return new ValueRef(key, value, rqueue);
    }

    private static Object unwrapValue(Object value) {
        return (value == null) ? null : ((ValueRef)value).getValue();
    }

    private static Object detachValue(Object value) {
        if (value == null) return null;
        ValueRef ref = (ValueRef)value;
        Object val = ref.getValue();
        // detach -> no need to enqueue
        ref.clear();
        return val;
    }

    private static boolean eq(Object o1, Object o2) {
        return (o1 == null ? o2 == null : o1.equals(o2));
    }
}
