sequencedhashmap.java

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

  private static final int VALUE = 1;
  private static final int ENTRY = 2;
  private static final int REMOVED_MASK = 0x80000000;

  private class OrderedIterator implements Iterator {
    /** 
     *  Holds the type that should be returned from the iterator.  The value
     *  should be either {@link #KEY}, {@link #VALUE}, or {@link #ENTRY}.  To
     *  save a tiny bit of memory, this field is also used as a marker for when
     *  remove has been called on the current object to prevent a second remove
     *  on the same element.  Essientially, if this value is negative (i.e. the
     *  bit specified by {@link #REMOVED_MASK} is set), the current position
     *  has been removed.  If positive, remove can still be called.
     **/
    private int returnType;

    /**
     *  Holds the "current" position in the iterator.  When pos.next is the
     *  sentinel, we've reached the end of the list.
     **/
    private Entry pos = sentinel;

    /**
     *  Holds the expected modification count.  If the actual modification
     *  count of the map differs from this value, then a concurrent
     *  modification has occurred.
     **/
    private transient long expectedModCount = modCount;
    
    /**
     *  Construct an iterator over the sequenced elements in the order in which
     *  they were added.  The {@link #next()} method returns the type specified
     *  by <code>returnType</code> which must be either {@link #KEY}, {@link
     *  #VALUE}, or {@link #ENTRY}.
     **/
    public OrderedIterator(int returnType) {
      //// Since this is a private inner class, nothing else should have
      //// access to the constructor.  Since we know the rest of the outer
      //// class uses the iterator correctly, we can leave of the following
      //// check:
      //if(returnType >= 0 && returnType <= 2) {
      //  throw new IllegalArgumentException("Invalid iterator type");
      //}

      // Set the "removed" bit so that the iterator starts in a state where
      // "next" must be called before "remove" will succeed.
      this.returnType = returnType | REMOVED_MASK;
    }

    /**
     *  Returns whether there is any additional elements in the iterator to be
     *  returned.
     *
     *  @return <code>true</code> if there are more elements left to be
     *  returned from the iterator; <code>false</code> otherwise.
     **/
    public boolean hasNext() {
      return pos.next != sentinel;
    }

    /**
     *  Returns the next element from the iterator.
     *
     *  @return the next element from the iterator.
     *
     *  @exception NoSuchElementException if there are no more elements in the
     *  iterator.
     *
     *  @exception ConcurrentModificationException if a modification occurs in
     *  the underlying map.
     **/
    public Object next() {
      if(modCount != expectedModCount) {
        throw new ConcurrentModificationException();
      }
      if(pos.next == sentinel) {
        throw new NoSuchElementException();
      }

      // clear the "removed" flag
      returnType = returnType & ~REMOVED_MASK;

      pos = pos.next;
      switch(returnType) {
      case KEY:
        return pos.getKey();
      case VALUE:
        return pos.getValue();
      case ENTRY:
        return pos;
      default:
        // should never happen
        throw new Error("bad iterator type: " + returnType);
      }

    }
    
    /**
     *  Removes the last element returned from the {@link #next()} method from
     *  the sequenced map.
     *
     *  @exception IllegalStateException if there isn't a "last element" to be
     *  removed.  That is, if {@link #next()} has never been called, or if
     *  {@link #remove()} was already called on the element.
     *
     *  @exception ConcurrentModificationException if a modification occurs in
     *  the underlying map.
     **/
    public void remove() {
      if((returnType & REMOVED_MASK) != 0) {
        throw new IllegalStateException("remove() must follow next()");
      }
      if(modCount != expectedModCount) {
        throw new ConcurrentModificationException();
      }

      SequencedHashMap.this.removeImpl(pos.getKey());

      // update the expected mod count for the remove operation
      expectedModCount++;

      // set the removed flag
      returnType = returnType | REMOVED_MASK;
    }
  }

  // APIs maintained from previous version of SequencedHashMap for backwards
  // compatibility

  /**
   * Creates a shallow copy of this object, preserving the internal structure
   * by copying only references.  The keys and values themselves are not
   * <code>clone()</code>'d.  The cloned object maintains the same sequence.
   *
   * @return A clone of this instance.  
   *
   * @exception CloneNotSupportedException if clone is not supported by a
   * subclass.
   */
  public Object clone () throws CloneNotSupportedException {
    // yes, calling super.clone() silly since we're just blowing away all
    // the stuff that super might be doing anyway, but for motivations on
    // this, see:
    // http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html
    SequencedHashMap map = (SequencedHashMap)super.clone();

    // create new, empty sentinel
    map.sentinel = createSentinel();

    // create a new, empty entry map
    // note: this does not preserve the initial capacity and load factor.
    map.entries = new HashMap();
      
    // add all the mappings
    map.putAll(this);

    // Note: We cannot just clone the hashmap and sentinel because we must
    // duplicate our internal structures.  Cloning those two will not clone all
    // the other entries they reference, and so the cloned hash map will not be
    // able to maintain internal consistency because there are two objects with
    // the same entries.  See discussion in the Entry implementation on why we
    // cannot implement a clone of the Entry (and thus why we need to recreate
    // everything).

    return map;
  }

  /**
   *  Returns the Map.Entry at the specified index
   *
   *  @exception ArrayIndexOutOfBoundsException if the specified index is
   *  <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
   **/
  private Map.Entry getEntry(int index) {
    Entry pos = sentinel;

    if(index < 0) {
      throw new ArrayIndexOutOfBoundsException(index + " < 0");
    }

    // loop to one before the position
    int i = -1;
    while(i < (index-1) && pos.next != sentinel) {
      i++;
      pos = pos.next;
    }
    // pos.next is the requested position
    
    // if sentinel is next, past end of list
    if(pos.next == sentinel) {
      throw new ArrayIndexOutOfBoundsException(index + " >= " + (i + 1));
    }

    return pos.next;
  }

  /**
   * Returns the key at the specified index.
   *
   *  @exception ArrayIndexOutOfBoundsException if the <code>index</code> is
   *  <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
   */
  public Object get (int index)
  {
    return getEntry(index).getKey();
  }

  /**
   * Returns the value at the specified index.
   *
   *  @exception ArrayIndexOutOfBoundsException if the <code>index</code> is
   *  <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
   */
  public Object getValue (int index)
  {
    return getEntry(index).getValue();
  }

  /**
   * Returns the index of the specified key.
   */
  public int indexOf (Object key)
  {
    Entry e = (Entry)entries.get(key);
    int pos = 0;
    while(e.prev != sentinel) {
      pos++;
      e = e.prev;
    }
    return pos;
  }

  /**
   * Returns a key iterator.
   */
  public Iterator iterator ()
  {
    return keySet().iterator();
  }

  /**
   * Returns the last index of the specified key.
   */
  public int lastIndexOf (Object key)
  {
    // keys in a map are guarunteed to be unique
    return indexOf(key);
  }

  /**
   * Returns a List view of the keys rather than a set view.  The returned
   * list is unmodifiable.  This is required because changes to the values of
   * the list (using {@link java.util.ListIterator#set(Object)}) will
   * effectively remove the value from the list and reinsert that value at
   * the end of the list, which is an unexpected side effect of changing the
   * value of a list.  This occurs because changing the key, changes when the
   * mapping is added to the map and thus where it appears in the list.
   *
   * <P>An alternative to this method is to use {@link #keySet()}
   *
   * @see #keySet()
   * @return The ordered list of keys.  
   */
  public List sequence()
  {
    List l = new ArrayList(size());
    Iterator iter = keySet().iterator();
    while(iter.hasNext()) {
      l.add(iter.next());
    }
      
    return Collections.unmodifiableList(l);
  }

  /**
   * Removes the element at the specified index.
   *
   * @param index The index of the object to remove.
   * @return      The previous value coressponding the <code>key</code>, or
   *              <code>null</code> if none existed.
   *
   * @exception ArrayIndexOutOfBoundsException if the <code>index</code> is
   * <code>&lt; 0</code> or <code>&gt;</code> the size of the map.
   */
  public Object remove (int index)
  {
    return remove(get(index));
  }

  // per Externalizable.readExternal(ObjectInput)

  /**
   *  Deserializes this map from the given stream.
   *
   *  @param in the stream to deserialize from
   *  @throws IOException if the stream raises it
   *  @throws ClassNotFoundException if the stream raises it
   */
  public void readExternal( ObjectInput in ) 
    throws IOException, ClassNotFoundException 
  {
    int size = in.readInt();    
    for(int i = 0; i < size; i++)  {
      Object key = in.readObject();
      Object value = in.readObject();
      put(key, value);
    }
  }
  
  /**
   *  Serializes this map to the given stream.
   *
   *  @param out  the stream to serialize to
   *  @throws IOException  if the stream raises it
   */
  public void writeExternal( ObjectOutput out ) throws IOException {
    out.writeInt(size());
    for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
      out.writeObject(pos.getKey());
      out.writeObject(pos.getValue());
    }
  }

  // add a serial version uid, so that if we change things in the future
  // without changing the format, we can still deserialize properly.
  private static final long serialVersionUID = 3380552487888102930L;

}