package org.codehaus.plexus.util;

/*
 * J.A.D.E. Java(TM) Addition to Default Environment.
 * Latest release available at http://jade.dautelle.com/
 * This class is public domain (not copyrighted).
 */

import java.util.Collection;
import java.util.Collections;
import java.util.Map;
import java.util.Set;

/**
 * <p>
 * This class provides cache access to <code>Map</code> collections.
 * </p>
 * <p>
 * Instance of this class can be used as "proxy" for any collection implementing the <code>java.util.Map</code>
 * interface.
 * </p>
 * <p>
 * Typically, {@link CachedMap} are used to accelerate access to large collections when the access to the collection is
 * not evenly distributed (associative cache). The performance gain is about 50% for the fastest hash map collections
 * (e.g. {@link FastMap}). For slower collections such as <code>java.util.TreeMap</code>, non-resizable {@link FastMap}
 * (real-time) or database access, performance can be of several orders of magnitude.
 * </p>
 * <p>
 * <b>Note:</b> The keys used to access elements of a {@link CachedMap} do not need to be immutable as they are not
 * stored in the cache (only keys specified by the {@link #put} method are). In other words, access can be performed
 * using mutable keys as long as these keys can be compared for equality with the real map's keys (e.g. same
 * <code>hashCode</code> values).
 * </p>
 * <p>
 * This implementation is not synchronized. Multiple threads accessing or modifying the collection must be synchronized
 * externally.
 * </p>
 * <p>
 * <i> This class is <b>public domain</b> (not copyrighted).</i>
 * </p>
 *
 * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
 * @version 5.3, October 30, 2003
 */
public final class CachedMap implements Map {

    /**
     * Holds the FastMap backing this collection (<code>null</code> if generic backing map).
     */
    private final FastMap _backingFastMap;

    /**
     * Holds the generic map backing this collection.
     */
    private final Map _backingMap;

    /**
     * Holds the keys of the backing map (key-to-key mapping). (<code>null</code> if FastMap backing map).
     */
    private final FastMap _keysMap;

    /**
     * Holds the cache's mask (capacity - 1).
     */
    private final int _mask;

    /**
     * Holds the keys being cached.
     */
    private final Object[] _keys;

    /**
     * Holds the values being cached.
     */
    private final Object[] _values;

    /**
     * Creates a cached map backed by a {@link FastMap}. The default cache size and map capacity is set to
     * <code>256</code> entries.
     */
    public CachedMap() {
        this(256, new FastMap());
    }

    /**
     * Creates a cached map backed by a {@link FastMap} and having the specified cache size.
     *
     * @param cacheSize the cache size, the actual cache size is the first power of 2 greater or equal to
     *            <code>cacheSize</code>. This is also the initial capacity of the backing map.
     */
    public CachedMap(int cacheSize) {
        this(cacheSize, new FastMap(cacheSize));
    }

    /**
     * Creates a cached map backed by the specified map and having the specified cache size. In order to maintain cache
     * veracity, it is critical that <b>all</b> update to the backing map is accomplished through the {@link CachedMap}
     * instance; otherwise {@link #flush} has to be called.
     *
     * @param cacheSize the cache size, the actual cache size is the first power of 2 greater or equal to
     *            <code>cacheSize</code>.
     * @param backingMap the backing map to be "wrapped" in a cached map.
     */
    public CachedMap(int cacheSize, Map backingMap) {

        // Find a power of 2 >= minimalCache
        int actualCacheSize = 1;
        while (actualCacheSize < cacheSize) {
            actualCacheSize <<= 1;
        }

        // Sets up cache.
        _keys = new Object[actualCacheSize];
        _values = new Object[actualCacheSize];
        _mask = actualCacheSize - 1;

        // Sets backing map references.
        if (backingMap instanceof FastMap) {
            _backingFastMap = (FastMap) backingMap;
            _backingMap = _backingFastMap;
            _keysMap = null;
        } else {
            _backingFastMap = null;
            _backingMap = backingMap;
            _keysMap = new FastMap(backingMap.size());
            for (Object key : backingMap.keySet()) {
                _keysMap.put(key, key);
            }
        }
    }

    /**
     * Returns the actual cache size.
     *
     * @return the cache size (power of 2).
     */
    public int getCacheSize() {
        return _keys.length;
    }

    /**
     * Returns the backing map. If the backing map is modified directly, this {@link CachedMap} has to be flushed.
     *
     * @return the backing map.
     * @see #flush
     */
    public Map getBackingMap() {
        return (_backingFastMap != null) ? _backingFastMap : _backingMap;
    }

    /**
     * Flushes the key/value pairs being cached. This method should be called if the backing map is externally modified.
     */
    public void flush() {
        for (int i = 0; i < _keys.length; i++) {
            _keys[i] = null;
            _values[i] = null;
        }

        if (_keysMap != null) {
            // Re-populates keys from backing map.
            for (Object key : _backingMap.keySet()) {
                _keysMap.put(key, key);
            }
        }
    }

    /**
     * Returns the value to which this map maps the specified key. First, the cache is being checked, then if the cache
     * does not contains the specified key, the backing map is accessed and the key/value pair is stored in the cache.
     *
     * @param key the key whose associated value is to be returned.
     * @return the value to which this map maps the specified key, or <code>null</code> if the map contains no mapping
     *         for this key.
     * @throws ClassCastException if the key is of an inappropriate type for the backing map (optional).
     * @throws NullPointerException if the key is <code>null</code>.
     */
    @Override
    public Object get(Object key) {
        int index = key.hashCode() & _mask;
        return key.equals(_keys[index]) ? _values[index] : getCacheMissed(key, index);
    }

    private Object getCacheMissed(Object key, int index) {
        if (_backingFastMap != null) {
            Map.Entry entry = _backingFastMap.getEntry(key);
            if (entry != null) {
                _keys[index] = entry.getKey();
                Object value = entry.getValue();
                _values[index] = value;
                return value;
            } else {
                return null;
            }
        } else { // Generic backing map.
            Object mapKey = _keysMap.get(key);
            if (mapKey != null) {
                _keys[index] = mapKey;
                Object value = _backingMap.get(key);
                _values[index] = value;
                return value;
            } else {
                return null;
            }
        }
    }

    /**
     * Associates the specified value with the specified key in this map.
     *
     * @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 specified key, or <code>null</code> if there was no mapping for the
     *         key.
     * @throws UnsupportedOperationException if the <code>put</code> operation is not supported by the backing map.
     * @throws ClassCastException if the class of the specified key or value prevents it from being stored in this map.
     * @throws IllegalArgumentException if some aspect of this key or value prevents it from being stored in this map.
     * @throws NullPointerException if the key is <code>null</code>.
     */
    @Override
    public Object put(Object key, Object value) {
        // Updates the cache.
        int index = key.hashCode() & _mask;
        if (key.equals(_keys[index])) {
            _values[index] = value;
        } else if (_keysMap != null) { // Possibly a new key.
            _keysMap.put(key, key);
        }

        // Updates the backing map.
        return _backingMap.put(key, value);
    }

    /**
     * Removes the mapping for this key from this map if it is present.
     *
     * @param key key whose mapping is to be removed from the map.
     * @return previous value associated with specified key, or <code>null</code> if there was no mapping for key.
     * @throws ClassCastException if the key is of an inappropriate type for the backing map (optional).
     * @throws NullPointerException if the key is <code>null</code>.
     * @throws UnsupportedOperationException if the <code>remove</code> method is not supported by the backing map.
     */
    @Override
    public Object remove(Object key) {
        // Removes from cache.
        int index = key.hashCode() & _mask;
        if (key.equals(_keys[index])) {
            _keys[index] = null;
        }
        // Removes from key map.
        if (_keysMap != null) {
            _keysMap.remove(key);
        }
        // Removes from backing map.
        return _backingMap.remove(key);
    }

    /**
     * Indicates 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</code> if this map contains a mapping for the specified key; <code>false</code> otherwise.
     */
    @Override
    public boolean containsKey(Object key) {
        // Checks the cache.
        int index = key.hashCode() & _mask;
        if (key.equals(_keys[index])) {
            return true;
        } else { // Checks the backing map.
            return _backingMap.containsKey(key);
        }
    }

    /**
     * Returns the number of key-value mappings in this map. If the map contains more than
     * <code>Integer.MAX_VALUE</code> elements, returns <code>Integer.MAX_VALUE</code>.
     *
     * @return the number of key-value mappings in this map.
     */
    @Override
    public int size() {
        return _backingMap.size();
    }

    /**
     * Returns <code>true</code> if this map contains no key-value mappings.
     *
     * @return <code>true</code> if this map contains no key-value mappings.
     */
    @Override
    public boolean isEmpty() {
        return _backingMap.isEmpty();
    }

    /**
     * Returns <code>true</code> if this map maps one or more keys to the specified value.
     *
     * @param value value whose presence in this map is to be tested.
     * @return <code>true</code> if this map maps one or more keys to the specified value.
     * @throws ClassCastException if the value is of an inappropriate type for the backing map (optional).
     * @throws NullPointerException if the value is <code>null</code> and the backing map does not not permit
     *             <code>null</code> values.
     */
    @Override
    public boolean containsValue(Object value) {
        return _backingMap.containsValue(value);
    }

    /**
     * Copies all of the mappings from the specified map to this map (optional operation). This method automatically
     * flushes the cache.
     *
     * @param map the mappings to be stored in this map.
     * @throws UnsupportedOperationException if the <code>putAll</code> method is not supported by the backing map.
     * @throws ClassCastException if the class of a key or value in the specified map prevents it from being stored in
     *             this map.
     * @throws IllegalArgumentException some aspect of a key or value in the specified map prevents it from being stored
     *             in this map.
     * @throws NullPointerException the specified map is <code>null</code>, or if the backing map does not permit
     *             <code>null</code> keys or values, and the specified map contains <code>null</code> keys or values.
     */
    @Override
    public void putAll(Map map) {
        _backingMap.putAll(map);
        flush();
    }

    /**
     * Removes all mappings from this map (optional operation). This method automatically flushes the cache.
     *
     * @throws UnsupportedOperationException if clear is not supported by the backing map.
     */
    @Override
    public void clear() {
        _backingMap.clear();
        flush();
    }

    /**
     * Returns an <b>unmodifiable</b> view of the keys contained in this map.
     *
     * @return an unmodifiable view of the keys contained in this map.
     */
    @Override
    public Set keySet() {
        return Collections.unmodifiableSet(_backingMap.keySet());
    }

    /**
     * Returns an <b>unmodifiable</b> view of the values contained in this map.
     *
     * @return an unmodifiable view of the values contained in this map.
     */
    @Override
    public Collection values() {
        return Collections.unmodifiableCollection(_backingMap.values());
    }

    /**
     * Returns an <b>unmodifiable</b> view of the mappings contained in this map. Each element in the returned set is a
     * <code>Map.Entry</code>.
     *
     * @return an unmodifiable view of the mappings contained in this map.
     */
    @Override
    public Set entrySet() {
        return Collections.unmodifiableSet(_backingMap.entrySet());
    }

    /**
     * Compares the specified object with this map for equality. Returns <code>true</code> if the given object is also a map
     * and the two Maps represent the same mappings.
     *
     * @param o object to be compared for equality with this map.
     * @return <code>true</code> if the specified object is equal to this map.
     */
    @Override
    public boolean equals(Object o) {
        return _backingMap.equals(o);
    }

    /**
     * Returns the hash code value for this map.
     *
     * @return the hash code value for this map.
     */
    @Override
    public int hashCode() {
        return _backingMap.hashCode();
    }
}
