sequencedhashmap.java

初级java程序员如果想要更深一步提高自己的实力

/*
 *  Copyright 2002-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.
 */
package org.apache.commons.collections;

import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

import org.apache.commons.collections.list.UnmodifiableList;

/**
 * A map of objects whose mapping entries are sequenced based on the order in
 * which they were added.  This data structure has fast <i>O(1)</i> search
 * time, deletion time, and insertion time.
 * <p>
 * Although this map is sequenced, it cannot implement
 * {@link java.util.List} because of incompatible interface definitions.
 * The remove methods in List and Map have different return values 
 * (see: {@link java.util.List#remove(Object)} and {@link java.util.Map#remove(Object)}).
 * <p>
 * This class is not thread safe.  When a thread safe implementation is
 * required, use {@link java.util.Collections#synchronizedMap(Map)} as it is documented,
 * or use explicit synchronization controls.
 *
 * @deprecated Replaced by LinkedMap and ListOrderedMap in map subpackage. Due to be removed in v4.0.
 * @see org.apache.commons.collections.map.LinkedMap
 * @see org.apache.commons.collections.map.ListOrderedMap
 * @since Commons Collections 2.0
 * @version $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
 * 
 * @author Michael A. Smith
 * @author Daniel Rall
 * @author Henning P. Schmiedehausen
 * @author Stephen Colebourne
 */
public class SequencedHashMap implements Map, Cloneable, Externalizable {

    /**
     * {@link java.util.Map.Entry} that doubles as a node in the linked list
     * of sequenced mappings.  
     */
    private static class Entry implements Map.Entry, KeyValue {
        // Note: This class cannot easily be made clonable.  While the actual
        // implementation of a clone would be simple, defining the semantics is
        // difficult.  If a shallow clone is implemented, then entry.next.prev !=
        // entry, which is unintuitive and probably breaks all sorts of assumptions
        // in code that uses this implementation.  If a deep clone is
        // implemented, then what happens when the linked list is cyclical (as is
        // the case with SequencedHashMap)?  It's impossible to know in the clone
        // when to stop cloning, and thus you end up in a recursive loop,
        // continuously cloning the "next" in the list.

        private final Object key;
        private Object value;

        // package private to allow the SequencedHashMap to access and manipulate
        // them.
        Entry next = null;
        Entry prev = null;

        public Entry(Object key, Object value) {
            this.key = key;
            this.value = value;
        }

        // per Map.Entry.getKey()
        public Object getKey() {
            return this.key;
        }

        // per Map.Entry.getValue()
        public Object getValue() {
            return this.value;
        }

        // per Map.Entry.setValue()
        public Object setValue(Object value) {
            Object oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        public int hashCode() {
            // implemented per api docs for Map.Entry.hashCode()
            return ((getKey() == null ? 0 : getKey().hashCode()) ^ (getValue() == null ? 0 : getValue().hashCode()));
        }

        public boolean equals(Object obj) {
            if (obj == null)
                return false;
            if (obj == this)
                return true;
            if (!(obj instanceof Map.Entry))
                return false;

            Map.Entry other = (Map.Entry) obj;

            // implemented per api docs for Map.Entry.equals(Object) 
            return (
                (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey()))
                    && (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue())));
        }
        public String toString() {
            return "[" + getKey() + "=" + getValue() + "]";
        }
    }

    /**
     *  Construct an empty sentinel used to hold the head (sentinel.next) and the
     *  tail (sentinel.prev) of the list.  The sentinel has a <code>null</code>
     *  key and value.
     */
    private static final Entry createSentinel() {
        Entry s = new Entry(null, null);
        s.prev = s;
        s.next = s;
        return s;
    }

    /**
     *  Sentinel used to hold the head and tail of the list of entries.
     */
    private Entry sentinel;

    /**
     *  Map of keys to entries
     */
    private HashMap entries;

    /**
     *  Holds the number of modifications that have occurred to the map,
     *  excluding modifications made through a collection view's iterator
     *  (e.g. entrySet().iterator().remove()).  This is used to create a
     *  fail-fast behavior with the iterators.
     */
    private transient long modCount = 0;

    /**
     *  Construct a new sequenced hash map with default initial size and load
     *  factor.
     */
    public SequencedHashMap() {
        sentinel = createSentinel();
        entries = new HashMap();
    }

    /**
     *  Construct a new sequenced hash map with the specified initial size and
     *  default load factor.
     *
     *  @param initialSize the initial size for the hash table 
     *
     *  @see HashMap#HashMap(int)
     */
    public SequencedHashMap(int initialSize) {
        sentinel = createSentinel();
        entries = new HashMap(initialSize);
    }

    /**
     *  Construct a new sequenced hash map with the specified initial size and
     *  load factor.
     *
     *  @param initialSize the initial size for the hash table 
     *
     *  @param loadFactor the load factor for the hash table.
     *
     *  @see HashMap#HashMap(int,float)
     */
    public SequencedHashMap(int initialSize, float loadFactor) {
        sentinel = createSentinel();
        entries = new HashMap(initialSize, loadFactor);
    }

    /**
     *  Construct a new sequenced hash map and add all the elements in the
     *  specified map.  The order in which the mappings in the specified map are
     *  added is defined by {@link #putAll(Map)}.  
     */
    public SequencedHashMap(Map m) {
        this();
        putAll(m);
    }

    /**
     *  Removes an internal entry from the linked list.  This does not remove
     *  it from the underlying map.
     */
    private void removeEntry(Entry entry) {
        entry.next.prev = entry.prev;
        entry.prev.next = entry.next;
    }

    /**
     *  Inserts a new internal entry to the tail of the linked list.  This does
     *  not add the entry to the underlying map.
     */
    private void insertEntry(Entry entry) {
        entry.next = sentinel;
        entry.prev = sentinel.prev;
        sentinel.prev.next = entry;
        sentinel.prev = entry;
    }

    // per Map.size()

    /**
     *  Implements {@link Map#size()}.
     */
    public int size() {
        // use the underlying Map's size since size is not maintained here.
        return entries.size();
    }

    /**
     *  Implements {@link Map#isEmpty()}.
     */
    public boolean isEmpty() {
        // for quick check whether the map is entry, we can check the linked list
        // and see if there's anything in it.
        return sentinel.next == sentinel;
    }

    /**
     *  Implements {@link Map#containsKey(Object)}.
     */
    public boolean containsKey(Object key) {
        // pass on to underlying map implementation
        return entries.containsKey(key);
    }

    /**
     *  Implements {@link Map#containsValue(Object)}.
     */
    public boolean containsValue(Object value) {
        // unfortunately, we cannot just pass this call to the underlying map
        // because we are mapping keys to entries, not keys to values.  The
        // underlying map doesn't have an efficient implementation anyway, so this
        // isn't a big deal.

        // do null comparison outside loop so we only need to do it once.  This
        // provides a tighter, more efficient loop at the expense of slight
        // code duplication.
        if (value == null) {
            for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
                if (pos.getValue() == null)
                    return true;
            }
        } else {
            for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
                if (value.equals(pos.getValue()))
                    return true;
            }
        }
        return false;
    }

    /**
     *  Implements {@link Map#get(Object)}.
     */
    public Object get(Object o) {
        // find entry for the specified key object
        Entry entry = (Entry) entries.get(o);
        if (entry == null)
            return null;

        return entry.getValue();
    }

    /**
     *  Return the entry for the "oldest" mapping.  That is, return the Map.Entry
     *  for the key-value pair that was first put into the map when compared to
     *  all the other pairings in the map.  This behavior is equivalent to using
     *  <code>entrySet().iterator().next()</code>, but this method provides an
     *  optimized implementation.
     *
     *  @return The first entry in the sequence, or <code>null</code> if the
     *  map is empty.
     */
    public Map.Entry getFirst() {
        // sentinel.next points to the "first" element of the sequence -- the head
        // of the list, which is exactly the entry we need to return.  We must test
        // for an empty list though because we don't want to return the sentinel!
        return (isEmpty()) ? null : sentinel.next;
    }

    /**
     *  Return the key for the "oldest" mapping.  That is, return the key for the
     *  mapping that was first put into the map when compared to all the other
     *  objects in the map.  This behavior is equivalent to using
     *  <code>getFirst().getKey()</code>, but this method provides a slightly
     *  optimized implementation.
     *
     *  @return The first key in the sequence, or <code>null</code> if the
     *  map is empty.
     */
    public Object getFirstKey() {
        // sentinel.next points to the "first" element of the sequence -- the head
        // of the list -- and the requisite key is returned from it.  An empty list
        // does not need to be tested.  In cases where the list is empty,
        // sentinel.next will point to the sentinel itself which has a null key,
        // which is exactly what we would want to return if the list is empty (a
        // nice convenient way to avoid test for an empty list)
        return sentinel.next.getKey();
    }

    /**
     *  Return the value for the "oldest" mapping.  That is, return the value for
     *  the mapping that was first put into the map when compared to all the
     *  other objects in the map.  This behavior is equivalent to using
     *  <code>getFirst().getValue()</code>, but this method provides a slightly
     *  optimized implementation.
     *
     *  @return The first value in the sequence, or <code>null</code> if the
     *  map is empty.