sequencedhashmap.java

iBATIS似乎已远离众说纷纭的OR框架之列

/*
 * Copyright 1999-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.ObjectInput;
import java.io.ObjectOutput;
import java.io.IOException;

import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.NoSuchElementException;
import java.util.ConcurrentModificationException;

/**
 *  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 Collections#synchronizedMap(Map)} as it is documented,
 *  or use explicit synchronization controls.
 *
 *  @since 2.0
 *  @author <a href="mailto:[e-mail]">Michael A. Smith</A>
 * @author <a href="mailto:[e-mail]">Daniel Rall</a>
 * @author <a href="mailto:[e-mail]">Henning P. Schmiedehausen</a>
 */
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 {
    // 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
    // implementated, 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 sentinal 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 convient 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