abstracthashedmap.java

rule engine drools-2.0-beta-18

package org.drools.util;
/*
 *  Copyright 2003-2004 The Apache Software Foundation
 *
 *  Licensed 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.
 */

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * An abstract implementation of a hash-based map which provides numerous points
 * for subclasses to override.
 * <p>
 * This class implements all the features necessary for a subclass hash-based
 * map. Key-value entries are stored in instances of the <code>HashEntry</code>
 * class, which can be overridden and replaced. The iterators can similarly be
 * replaced, without the need to replace the KeySet, EntrySet and Values view
 * classes.
 * <p>
 * Overridable methods are provided to change the default hashing behaviour, and
 * to change how entries are added to and removed from the map. Hopefully, all
 * you need for unusual subclasses is here.
 * <p>
 * NOTE: From Commons Collections 3.1 this class extends AbstractMap. This is to
 * provide backwards compatibility for ReferenceMap between v3.0 and v3.1. This
 * extends clause will be removed in v4.0.
 *
 * @since Commons Collections 3.0
 * @version $Revision: 1.3 $ $Date: 2004/11/22 02:38:39 $
 *
 * @author java util HashMap
 * @author Stephen Colebourne
 */
public class AbstractHashedMap extends AbstractMap
{

    protected static final String NO_NEXT_ENTRY = "No next() entry in the iteration";
    protected static final String NO_PREVIOUS_ENTRY = "No previous() entry in the iteration";
    protected static final String REMOVE_INVALID = "remove() can only be called once after next()";
    protected static final String GETKEY_INVALID = "getKey() can only be called after next() and before remove()";
    protected static final String GETVALUE_INVALID = "getValue() can only be called after next() and before remove()";
    protected static final String SETVALUE_INVALID = "setValue() can only be called after next() and before remove()";

    /** The default capacity to use */
    protected static final int DEFAULT_CAPACITY = 16;
    /** The default threshold to use */
    protected static final int DEFAULT_THRESHOLD = 12;
    /** The default load factor to use */
    protected static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /** The maximum capacity allowed */
    protected static final int MAXIMUM_CAPACITY = 1 << 30;
    /** An object for masking null */
    protected static final Object NULL = new Object( );

    /** Load factor, normally 0.75 */
    protected transient float loadFactor;
    /** The size of the map */
    protected transient int size;
    /** Map entries */
    protected transient HashEntry[] data;
    /** Size at which to rehash */
    protected transient int threshold;
    /** Modification count for iterators */
    protected transient int modCount;
    /** Entry set */
    protected transient EntrySet entrySet;
    /** Key set */
    protected transient KeySet keySet;
    /** Values */
    protected transient Values values;

    /**
     * Constructor only used in deserialization, do not use otherwise.
     */
    protected AbstractHashedMap()
    {
        super( );
    }

    /**
     * Constructor which performs no validation on the passed in parameters.
     *
     * @param initialCapacity
     *            the initial capacity, must be a power of two
     * @param loadFactor
     *            the load factor, must be &gt; 0.0f and generally &lt; 1.0f
     * @param threshold
     *            the threshold, must be sensible
     */
    protected AbstractHashedMap(int initialCapacity,
                                float loadFactor,
                                int threshold)
    {
        super( );
        this.loadFactor = loadFactor;
        this.data = new HashEntry[initialCapacity];
        this.threshold = threshold;
        init( );
    }

    /**
     * Constructs a new, empty map with the specified initial capacity and
     * default load factor.
     *
     * @param initialCapacity
     *            the initial capacity
     * @throws IllegalArgumentException
     *             if the initial capacity is less than one
     */
    protected AbstractHashedMap(int initialCapacity)
    {
        this( initialCapacity,
              DEFAULT_LOAD_FACTOR );
    }

    /**
     * Constructs a new, empty map with the specified initial capacity and load
     * factor.
     *
     * @param initialCapacity
     *            the initial capacity
     * @param loadFactor
     *            the load factor
     * @throws IllegalArgumentException
     *             if the initial capacity is less than one
     * @throws IllegalArgumentException
     *             if the load factor is less than or equal to zero
     */
    protected AbstractHashedMap(int initialCapacity,
                                float loadFactor)
    {
        super( );
        if ( initialCapacity < 1 )
        {
            throw new IllegalArgumentException( "Initial capacity must be greater than 0" );
        }
        if ( loadFactor <= 0.0f || Float.isNaN( loadFactor ) )
        {
            throw new IllegalArgumentException( "Load factor must be greater than 0" );
        }
        this.loadFactor = loadFactor;
        this.threshold = calculateThreshold( initialCapacity,
                                             loadFactor );
        initialCapacity = calculateNewCapacity( initialCapacity );
        this.data = new HashEntry[initialCapacity];
        init( );
    }

    /**
     * Constructor copying elements from another map.
     *
     * @param map
     *            the map to copy
     * @throws NullPointerException
     *             if the map is null
     */
    protected AbstractHashedMap(Map map)
    {
        this( Math.max( 2 * map.size( ),
                        DEFAULT_CAPACITY ),
              DEFAULT_LOAD_FACTOR );
        putAll( map );
    }

    /**
     * Initialise subclasses during construction, cloning or deserialization.
     */
    protected void init()
    {
    }

    // -----------------------------------------------------------------------
    /**
     * Gets the value mapped to the key specified.
     *
     * @param key
     *            the key
     * @return the mapped value, null if no match
     */
    public Object get(Object key)
    {
        key = convertKey( key );
        int hashCode = hash( key );
        HashEntry entry = data[hashIndex( hashCode,
                                          data.length )]; // no local for hash
                                                            // index
        while ( entry != null )
        {
            if ( entry.hashCode == hashCode && isEqualKey( key,
                                                           entry.key ) )
            {
                return entry.getValue( );
            }
            entry = entry.next;
        }
        return null;
    }

    /**
     * Gets the size of the map.
     *
     * @return the size
     */
    public int size()
    {
        return size;
    }

    /**
     * Checks whether the map is currently empty.
     *
     * @return true if the map is currently size zero
     */
    public boolean isEmpty()
    {
        return (size == 0);
    }

    // -----------------------------------------------------------------------
    /**
     * Checks whether the map contains the specified key.
     *
     * @param key
     *            the key to search for
     * @return true if the map contains the key
     */
    public boolean containsKey(Object key)
    {
        key = convertKey( key );
        int hashCode = hash( key );
        HashEntry entry = data[hashIndex( hashCode,
                                          data.length )]; // no local for hash
                                                            // index
        while ( entry != null )
        {
            if ( entry.hashCode == hashCode && isEqualKey( key,
                                                           entry.key ) )
            {
                return true;
            }
            entry = entry.next;
        }
        return false;
    }

    /**
     * Checks whether the map contains the specified value.
     *
     * @param value
     *            the value to search for
     * @return true if the map contains the value
     */
    public boolean containsValue(Object value)
    {
        if ( value == null )
        {
            for ( int i = 0, isize = data.length; i < isize; i++ )
            {
                HashEntry entry = data[i];
                while ( entry != null )
                {
                    if ( entry.getValue( ) == null )
                    {
                        return true;
                    }
                    entry = entry.next;
                }
            }
        }
        else
        {
            for ( int i = 0, isize = data.length; i < isize; i++ )
            {
                HashEntry entry = data[i];
                while ( entry != null )
                {
                    if ( isEqualValue( value,
                                       entry.getValue( ) ) )
                    {
                        return true;
                    }
                    entry = entry.next;
                }
            }
        }
        return false;
    }

    // -----------------------------------------------------------------------
    /**
     * Puts a key-value mapping into this map.
     *
     * @param key
     *            the key to add
     * @param value
     *            the value to add
     * @return the value previously mapped to this key, null if none
     */
    public Object put(Object key,
                      Object value)
    {
        key = convertKey( key );
        int hashCode = hash( key );
        int index = hashIndex( hashCode,
                               data.length );
        HashEntry entry = data[index];
        while ( entry != null )
        {
            if ( entry.hashCode == hashCode && isEqualKey( key,
                                                           entry.key ) )
            {
                Object oldValue = entry.getValue( );
                updateEntry( entry,
                             value );
                return oldValue;
            }
            entry = entry.next;
        }

        addMapping( index,
                    hashCode,
                    key,
                    value );
        return null;
    }

    /**
     * Puts all the values from the specified map into this map.
     * <p>
     * This implementation iterates around the specified map and uses
     * {@link #put(Object, Object)}.
     *
     * @param map
     *            the map to add
     * @throws NullPointerException
     *             if the map is null
     */
    public void putAll(Map map)
    {
        int mapSize = map.size( );
        if ( mapSize == 0 )
        {
            return;
        }
        int newSize = (int) ((size + mapSize) / loadFactor + 1);
        ensureCapacity( calculateNewCapacity( newSize ) );
        for ( Iterator it = map.entrySet( ).iterator( ); it.hasNext( ); )
        {
            Map.Entry entry = (Map.Entry) it.next( );
            put( entry.getKey( ),
                 entry.getValue( ) );
        }
    }

    /**
     * Removes the specified mapping from this map.
     *
     * @param key
     *            the mapping to remove
     * @return the value mapped to the removed key, null if key not in map
     */
    public Object remove(Object key)
    {
        key = convertKey( key );
        int hashCode = hash( key );
        int index = hashIndex( hashCode,
                               data.length );
        HashEntry entry = data[index];
        HashEntry previous = null;
        while ( entry != null )
        {
            if ( entry.hashCode == hashCode && isEqualKey( key,
                                                           entry.key ) )
            {
                Object oldValue = entry.getValue( );
                removeMapping( entry,
                               index,
                               previous );
                return oldValue;
            }
            previous = entry;
            entry = entry.next;
        }
        return null;
    }

    /**
     * Clears the map, resetting the size to zero and nullifying references to
     * avoid garbage collection issues.
     */
    public void clear()