/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You 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.apache.commons.collections;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.lang.ref.Reference;
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.Map;
import java.util.NoSuchElementException;
import java.util.Set;

import org.apache.commons.collections.keyvalue.DefaultMapEntry;

/**
 *  Hash-based {@link Map} implementation that allows
 *  mappings to be removed by the garbage collector.<p>
 *
 *  When you construct a <code>ReferenceMap</code>, you can 
 *  specify what kind of references are used to store the
 *  map's keys and values.  If non-hard references are 
 *  used, then the garbage collector can remove mappings
 *  if a key or value becomes unreachable, or if the 
 *  JVM's memory is running low.  For information on how
 *  the different reference types behave, see
 *  {@link Reference}.<p>
 *
 *  Different types of references can be specified for keys
 *  and values.  The keys can be configured to be weak but
 *  the values hard, in which case this class will behave
 *  like a <a href="http://java.sun.com/j2se/1.4/docs/api/java/util/WeakHashMap.html">
 *  <code>WeakHashMap</code></a>.  However, you
 *  can also specify hard keys and weak values, or any other
 *  combination.  The default constructor uses hard keys
 *  and soft values, providing a memory-sensitive cache.<p>
 *
 *  The algorithms used are basically the same as those
 *  in {@link java.util.HashMap}.  In particular, you 
 *  can specify a load factor and capacity to suit your
 *  needs.  All optional {@link Map} operations are 
 *  supported.<p>
 *
 *  However, this {@link Map} implementation does <I>not</I>
 *  allow null elements.  Attempting to add a null key or
 *  or a null value to the map will raise a 
 *  <code>NullPointerException</code>.<p>
 *
 *  As usual, this implementation is not synchronized.  You
 *  can use {@link java.util.Collections#synchronizedMap} to 
 *  provide synchronized access to a <code>ReferenceMap</code>.
 *
 * @see java.lang.ref.Reference
 * 
 * @deprecated Moved to map subpackage. Due to be removed in v4.0.
 * @since Commons Collections 2.1
 * @version $Revision: 438363 $ $Date: 2006-08-30 05:48:00 +0100 (Wed, 30 Aug 2006) $
 * 
 * @author Paul Jack
 */
public class ReferenceMap extends AbstractMap {

    /**
     *  For serialization.
     */
    final private static long serialVersionUID = -3370601314380922368L;


    /**
     *  Constant indicating that hard references should be used.
     */
    final public static int HARD = 0;


    /**
     *  Constant indicating that soft references should be used.
     */
    final public static int SOFT = 1;


    /**
     *  Constant indicating that weak references should be used.
     */
    final public static int WEAK = 2;


    // --- serialized instance variables:


    /**
     *  The reference type for keys.  Must be HARD, SOFT, WEAK.
     *  Note: I originally marked this field as final, but then this class
     *   didn't compile under JDK1.2.2.
     *  @serial
     */
    private int keyType;


    /**
     *  The reference type for values.  Must be HARD, SOFT, WEAK.
     *  Note: I originally marked this field as final, but then this class
     *   didn't compile under JDK1.2.2.
     *  @serial
     */
    private int valueType;


    /**
     *  The threshold variable is calculated by multiplying
     *  table.length and loadFactor.  
     *  Note: I originally marked this field as final, but then this class
     *   didn't compile under JDK1.2.2.
     *  @serial
     */
    private float loadFactor;
    
    /**
     * Should the value be automatically purged when the associated key has been collected?
     */
    private boolean purgeValues = false;


    // -- Non-serialized instance variables

    /**
     *  ReferenceQueue used to eliminate stale mappings.
     *  See purge.
     */
    private transient ReferenceQueue queue = new ReferenceQueue();


    /**
     *  The hash table.  Its length is always a power of two.  
     */
    private transient Entry[] table;


    /**
     *  Number of mappings in this map.
     */
    private transient int size;


    /**
     *  When size reaches threshold, the map is resized.  
     *  See resize().
     */
    private transient int threshold;


    /**
     *  Number of times this map has been modified.
     */
    private transient volatile int modCount;


    /**
     *  Cached key set.  May be null if key set is never accessed.
     */
    private transient Set keySet;


    /**
     *  Cached entry set.  May be null if entry set is never accessed.
     */
    private transient Set entrySet;


    /**
     *  Cached values.  May be null if values() is never accessed.
     */
    private transient Collection values;


    /**
     *  Constructs a new <code>ReferenceMap</code> that will
     *  use hard references to keys and soft references to values.
     */
    public ReferenceMap() {
        this(HARD, SOFT);
    }

    /**
     *  Constructs a new <code>ReferenceMap</code> that will
     *  use the specified types of references.
     *
     *  @param keyType  the type of reference to use for keys;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     *  @param valueType  the type of reference to use for values;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     *  @param purgeValues should the value be automatically purged when the 
     *   key is garbage collected 
     */
    public ReferenceMap(int keyType, int valueType, boolean purgeValues) {
        this(keyType, valueType);
        this.purgeValues = purgeValues;
    }

    /**
     *  Constructs a new <code>ReferenceMap</code> that will
     *  use the specified types of references.
     *
     *  @param keyType  the type of reference to use for keys;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     *  @param valueType  the type of reference to use for values;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     */
    public ReferenceMap(int keyType, int valueType) {
        this(keyType, valueType, 16, 0.75f);
    }

    /**
     *  Constructs a new <code>ReferenceMap</code> with the
     *  specified reference types, load factor and initial
     *  capacity.
     *
     *  @param keyType  the type of reference to use for keys;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     *  @param valueType  the type of reference to use for values;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     *  @param capacity  the initial capacity for the map
     *  @param loadFactor  the load factor for the map
     *  @param purgeValues should the value be automatically purged when the 
     *   key is garbage collected 
     */
    public ReferenceMap(
                        int keyType, 
                        int valueType, 
                        int capacity, 
                        float loadFactor, 
                        boolean purgeValues) {
        this(keyType, valueType, capacity, loadFactor);
        this.purgeValues = purgeValues;
    }

    /**
     *  Constructs a new <code>ReferenceMap</code> with the
     *  specified reference types, load factor and initial
     *  capacity.
     *
     *  @param keyType  the type of reference to use for keys;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     *  @param valueType  the type of reference to use for values;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     *  @param capacity  the initial capacity for the map
     *  @param loadFactor  the load factor for the map
     */
    public ReferenceMap(int keyType, int valueType, int capacity, float loadFactor) {
        super();

        verify("keyType", keyType);
        verify("valueType", valueType);

        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity must be positive");
        }
        if ((loadFactor <= 0.0f) || (loadFactor >= 1.0f)) {
            throw new IllegalArgumentException("Load factor must be greater than 0 and less than 1.");
        }

        this.keyType = keyType;
        this.valueType = valueType;

        int v = 1;
        while (v < capacity) v *= 2;

        this.table = new Entry[v];
        this.loadFactor = loadFactor;
        this.threshold = (int)(v * loadFactor);
    }


    // used by constructor
    private static void verify(String name, int type) {
        if ((type < HARD) || (type > WEAK)) {
            throw new IllegalArgumentException(name + 
               " must be HARD, SOFT, WEAK.");
        }
    }


    /**
     *  Writes this object to the given output stream.
     *
     *  @param out  the output stream to write to
     *  @throws IOException  if the stream raises it
     */
    private void writeObject(ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
        out.writeInt(table.length);

        // Have to use null-terminated list because size might shrink
        // during iteration

        for (Iterator iter = entrySet().iterator(); iter.hasNext();) {
            Map.Entry entry = (Map.Entry)iter.next();
            out.writeObject(entry.getKey());
            out.writeObject(entry.getValue());
        }
        out.writeObject(null);
    }


    /**
     *  Reads the contents of this object from the given input stream.
     *
     *  @param inp  the input stream to read from
     *  @throws IOException  if the stream raises it
     *  @throws ClassNotFoundException  if the stream raises it
     */
    private void readObject(ObjectInputStream inp) throws IOException, ClassNotFoundException {
        inp.defaultReadObject();
        table = new Entry[inp.readInt()];
        threshold = (int)(table.length * loadFactor);
        queue = new ReferenceQueue();
        Object key = inp.readObject();
        while (key != null) {
            Object value = inp.readObject();
            put(key, value);
            key = inp.readObject();
        }
    }


    /**
     *  Constructs a reference of the given type to the given 
     *  referent.  The reference is registered with the queue
     *  for later purging.
     *
     *  @param type  HARD, SOFT or WEAK
     *  @param referent  the object to refer to
     *  @param hash  the hash code of the <I>key</I> of the mapping;
     *    this number might be different from referent.hashCode() if
     *    the referent represents a value and not a key
     */
    private Object toReference(int type, Object referent, int hash) {
        switch (type) {
            case HARD: return referent;
            case SOFT: return new SoftRef(hash, referent, queue);
            case WEAK: return new WeakRef(hash, referent, queue);
            default: throw new Error();
        }
    }


    /**
     *  Returns the entry associated with the given key.
     *
     *  @param key  the key of the entry to look up
     *  @return  the entry associated with that key, or null
     *    if the key is not in this map
     */
    private Entry getEntry(Object key) {
        if (key == null) return null;
        int hash = key.hashCode();
        int index = indexFor(hash);
        for (Entry entry = table[index]; entry != null; entry = entry.next) {
            if ((entry.hash == hash) && key.equals(entry.getKey())) {
                return entry;
            }
        }
        return null;
    }


    /**
     *  Converts the given hash code into an index into the
     *  hash table.
     */
    private int indexFor(int hash) {
        // mix the bits to avoid bucket collisions...
        hash += ~(hash << 15);
        hash ^= (hash >>> 10);
        hash += (hash << 3);
        hash ^= (hash >>> 6);
        hash += ~(hash << 11);
        hash ^= (hash >>> 16);
        return hash & (table.length - 1);
    }



    /**
     *  Resizes this hash table by doubling its capacity.
     *  This is an expensive operation, as entries must
     *  be copied from the old smaller table to the new 
     *  bigger table.
     */
    private void resize() {
        Entry[] old = table;
        table = new Entry[old.length * 2];

        for (int i = 0; i < old.length; i++) {
            Entry next = old[i];
            while (next != null) {
                Entry entry = next;
                next = next.next;
                int index = indexFor(entry.hash);
                entry.next = table[index];
                table[index] = entry;
            }
            old[i] = null;
        }
        threshold = (int)(table.length * loadFactor);
    }



    /**
     * Purges stale mappings from this map.
     * <p>
     * Ordinarily, stale mappings are only removed during
     * a write operation, although this method is called for both
     * read and write operations to maintain a consistent state.
     * <p>
     * Note that this method is not synchronized!  Special
     * care must be taken if, for instance, you want stale
     * mappings to be removed on a periodic basis by some
     * background thread.
     */
    private void purge() {
        Reference ref = queue.poll();
        while (ref != null) {
            purge(ref);
            ref = queue.poll();
        }
    }


    private void purge(Reference ref) {
        // The hashCode of the reference is the hashCode of the
        // mapping key, even if the reference refers to the 
        // mapping value...
        int hash = ref.hashCode();
        int index = indexFor(hash);
        Entry previous = null;
        Entry entry = table[index];
        while (entry != null) {
            if (entry.purge(ref)) {
                if (previous == null) table[index] = entry.next;
                else previous.next = entry.next;
                this.size--;
                return;
            }
            previous = entry;
            entry = entry.next;
        }

    }


    /**
     *  Returns the size of this map.
     *
     *  @return  the size of this map
     */