abstracthashedmap.java

jboss规则引擎

package org.drools.util;

/*
 * Copyright 2005 JBoss Inc
 * 
 * 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.1 $ $Date: 2005/07/26 01:06:32 $
 * 
 * @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(final int initialCapacity,
                                final float loadFactor,
                                final 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(final int initialCapacity) {
        this( initialCapacity,
              AbstractHashedMap.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,
                                final 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(final Map map) {
        this( Math.max( 2 * map.size(),
                        AbstractHashedMap.DEFAULT_CAPACITY ),
              AbstractHashedMap.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 );
        final int hashCode = hash( key );
        HashEntry entry = this.data[hashIndex( hashCode,
                                               this.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 this.size;
    }

    /**
     * Checks whether the map is currently empty.
     * 
     * @return true if the map is currently size zero
     */
    public boolean isEmpty() {
        return (this.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 );
        final int hashCode = hash( key );
        HashEntry entry = this.data[hashIndex( hashCode,
                                               this.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(final Object value) {
        if ( value == null ) {
            for ( int i = 0, isize = this.data.length; i < isize; i++ ) {
                HashEntry entry = this.data[i];
                while ( entry != null ) {
                    if ( entry.getValue() == null ) {
                        return true;
                    }
                    entry = entry.next;
                }
            }
        } else {
            for ( int i = 0, isize = this.data.length; i < isize; i++ ) {
                HashEntry entry = this.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,
                      final Object value) {
        key = convertKey( key );
        final int hashCode = hash( key );
        final int index = hashIndex( hashCode,
                                     this.data.length );
        HashEntry entry = this.data[index];
        while ( entry != null ) {
            if ( entry.hashCode == hashCode && isEqualKey( key,
                                                           entry.key ) ) {
                final 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(final Map map) {
        final int mapSize = map.size();
        if ( mapSize == 0 ) {
            return;
        }
        final int newSize = (int) ((this.size + mapSize) / this.loadFactor + 1);
        ensureCapacity( calculateNewCapacity( newSize ) );
        for ( final Iterator it = map.entrySet().iterator(); it.hasNext(); ) {
            final 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 );
        final int hashCode = hash( key );
        final int index = hashIndex( hashCode,
                                     this.data.length );
        HashEntry entry = this.data[index];
        HashEntry previous = null;
        while ( entry != null ) {
            if ( entry.hashCode == hashCode && isEqualKey( key,
                                                           entry.key ) ) {
                final Object oldValue = entry.getValue();
                removeMapping( entry,
                               index,
                               previous );