directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: rev 47523 - in incubator/directory/ldap/trunk/common: . src/java/org/apache/ldap/common/util
Date Thu, 30 Sep 2004 01:15:35 GMT
Author: akarasulu
Date: Wed Sep 29 18:15:33 2004
New Revision: 47523

Added:
   incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/util/KeyValue.java
   incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/util/LRUMap.java
   incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/util/SequencedHashMap.java
Modified:
   incubator/directory/ldap/trunk/common/jakarta-commons-forks.txt
Log:
removing a dependency on commons-collections

Modified: incubator/directory/ldap/trunk/common/jakarta-commons-forks.txt
==============================================================================
--- incubator/directory/ldap/trunk/common/jakarta-commons-forks.txt	(original)
+++ incubator/directory/ldap/trunk/common/jakarta-commons-forks.txt	Wed Sep 29 18:15:33 2004
@@ -30,6 +30,12 @@
 src/java/org/apache/ldap/common/util/ReflectionToStringBuilder.java
 src/java/org/apache/ldap/common/util/Nestable.java
 
+These here is forked from collections:
+
+src/java/org/apache/ldap/common/util/LRUMap.java
+src/java/org/apache/ldap/common/util/KeyValue.java
+src/java/org/apache/ldap/common/util/SequencedHashMap.java
+
 At this point we only have two runtime dependencies.  Regexp and the
 antlr runtime.  Eventually as changes are made to the backend we will
 move away from using Regexp to using the regular expressions packaged

Added: incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/util/KeyValue.java
==============================================================================
--- (empty file)
+++ incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/util/KeyValue.java
Wed Sep 29 18:15:33 2004
@@ -0,0 +1,46 @@
+/*
+ *  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.
+ */
+package org.apache.ldap.common.util;
+
+/**
+ * Defines a simple key value pair.
+ * <p>
+ * A Map Entry has considerable additional semantics over and above a simple
+ * key-value pair. This interface defines the minimum key value, with just the
+ * two get methods.
+ *
+ * @since Commons Collections 3.0
+ * @version $Revision: 1.4 $ $Date: 2004/02/18 01:15:42 $
+ * 
+ * @author Stephen Colebourne
+ */
+public interface KeyValue {
+
+    /**
+     * Gets the key from the pair.
+     *
+     * @return the key 
+     */
+    Object getKey();
+
+    /**
+     * Gets the value from the pair.
+     *
+     * @return the value
+     */
+    Object getValue();
+
+}

Added: incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/util/LRUMap.java
==============================================================================
--- (empty file)
+++ incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/util/LRUMap.java
Wed Sep 29 18:15:33 2004
@@ -0,0 +1,206 @@
+/*
+ *  Copyright 2001-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.ldap.common.util;
+
+import java.io.Externalizable;
+import java.io.IOException;
+import java.io.ObjectInput;
+import java.io.ObjectOutput;
+import java.util.Iterator;
+
+/**
+ * <p>
+ * An implementation of a Map which has a maximum size and uses a Least Recently Used
+ * algorithm to remove items from the Map when the maximum size is reached and new items
are added.
+ * </p>
+ * 
+ * <p>
+ * A synchronized version can be obtained with:
+ * <code>Collections.synchronizedMap( theMapToSynchronize )</code>
+ * If it will be accessed by multiple threads, you _must_ synchronize access
+ * to this Map.  Even concurrent get(Object) operations produce indeterminate
+ * behaviour.
+ * </p>
+ * 
+ * <p>
+ * Unlike the Collections 1.0 version, this version of LRUMap does use a true
+ * LRU algorithm.  The keys for all gets and puts are moved to the front of
+ * the list.  LRUMap is now a subclass of SequencedHashMap, and the "LRU"
+ * key is now equivalent to LRUMap.getFirst().
+ * </p>
+ * 
+ * @deprecated Moved to map subpackage. Due to be removed in v4.0.
+ * @since Commons Collections 1.0
+ * @version $Revision: 1.23 $ $Date: 2004/02/18 01:15:42 $
+ * 
+ * @author <a href="mailto:jstrachan@apache.org">James Strachan</a>
+ * @author <a href="mailto:morgand@apache.org">Morgan Delagrange</a>
+ */
+public class LRUMap extends SequencedHashMap implements Externalizable {
+        
+    private int maximumSize = 0;
+
+    /**
+     * Default constructor, primarily for the purpose of
+     * de-externalization.  This constructors sets a default
+     * LRU limit of 100 keys, but this value may be overridden
+     * internally as a result of de-externalization.
+     */
+    public LRUMap() {
+        this( 100 );
+    }
+
+    /**
+     * Create a new LRUMap with a maximum capacity of <i>i</i>.
+     * Once <i>i</i> capacity is achieved, subsequent gets
+     * and puts will push keys out of the map.  See .
+     * 
+     * @param i      Maximum capacity of the LRUMap
+     */
+    public LRUMap(int i) {
+        super( i );
+        maximumSize = i;
+    }
+
+    /**
+     * <p>Get the value for a key from the Map.  The key
+     * will be promoted to the Most Recently Used position.
+     * Note that get(Object) operations will modify
+     * the underlying Collection.  Calling get(Object)
+     * inside of an iteration over keys, values, etc. is
+     * currently unsupported.</p>
+     * 
+     * @param key    Key to retrieve
+     * @return Returns the value.  Returns null if the key has a
+     *         null value <i>or</i> if the key has no value.
+     */
+    public Object get(Object key) {
+        if(!containsKey(key)) return null;
+
+        Object value = remove(key);
+        super.put(key,value);
+        return value;
+    }
+
+     /**
+      * <p>Removes the key and its Object from the Map.</p>
+      * 
+      * <p>(Note: this may result in the "Least Recently Used"
+      * object being removed from the Map.  In that case,
+      * the removeLRU() method is called.  See javadoc for
+      * removeLRU() for more details.)</p>
+      * 
+      * @param key    Key of the Object to add.
+      * @param value  Object to add
+      * @return Former value of the key
+      */    
+    public Object put( Object key, Object value ) {
+
+        int mapSize = size();
+        Object retval = null;
+
+        if ( mapSize >= maximumSize ) {
+
+            // don't retire LRU if you are just
+            // updating an existing key
+            if (!containsKey(key)) {
+                // lets retire the least recently used item in the cache
+                removeLRU();
+            }
+        }
+
+        retval = super.put(key,value);
+
+        return retval;
+    }
+
+    /**
+     * This method is used internally by the class for 
+     * finding and removing the LRU Object.
+     */
+    protected void removeLRU() {
+        Object key = getFirstKey();
+        // be sure to call super.get(key), or you're likely to 
+        // get infinite promotion recursion
+        Object value = super.get(key);
+        
+        remove(key);
+
+        processRemovedLRU(key,value);
+    }
+
+    /**
+     * Subclasses of LRUMap may hook into this method to
+     * provide specialized actions whenever an Object is
+     * automatically removed from the cache.  By default,
+     * this method does nothing.
+     * 
+     * @param key    key that was removed
+     * @param value  value of that key (can be null)
+     */
+    protected void processRemovedLRU(Object key, Object value) {
+    }
+ 
+    // Externalizable interface
+    //-------------------------------------------------------------------------        
+    public void readExternal( ObjectInput in )  throws IOException, ClassNotFoundException
{
+        maximumSize = in.readInt();
+        int size = in.readInt();
+        
+        for( int i = 0; i < size; i++ )  {
+            Object key = in.readObject();
+            Object value = in.readObject();
+            put(key,value);
+        }
+    }
+
+    public void writeExternal( ObjectOutput out ) throws IOException {
+        out.writeInt( maximumSize );
+        out.writeInt( size() );
+        for( Iterator iterator = keySet().iterator(); iterator.hasNext(); ) {
+            Object key = iterator.next();
+            out.writeObject( key );
+            // be sure to call super.get(key), or you're likely to 
+            // get infinite promotion recursion
+            Object value = super.get( key );
+            out.writeObject( value );
+        }
+    }
+    
+    
+    // Properties
+    //-------------------------------------------------------------------------        
+    /** Getter for property maximumSize.
+     * @return Value of property maximumSize.
+     */
+    public int getMaximumSize() {
+        return maximumSize;
+    }
+    /** Setter for property maximumSize.
+     * @param maximumSize New value of property maximumSize.
+     */
+    public void setMaximumSize(int maximumSize) {
+        this.maximumSize = maximumSize;
+        while (size() > maximumSize) {
+            removeLRU();
+        }
+    }
+
+
+    // 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 = 2197433140769957051L;
+}

Added: incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/util/SequencedHashMap.java
==============================================================================
--- (empty file)
+++ incubator/directory/ldap/trunk/common/src/java/org/apache/ldap/common/util/SequencedHashMap.java
Wed Sep 29 18:15:33 2004
@@ -0,0 +1,1003 @@
+/*
+ *  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.ldap.common.util;
+
+import java.io.Externalizable;
+import java.io.IOException;
+import java.io.ObjectInput;
+import java.io.ObjectOutput;
+import java.util.*;
+
+
+/**
+ * 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.
+ * @since Commons Collections 2.0
+ * @version $Revision: 1.28 $ $Date: 2004/02/18 01:15:42 $
+ * 
+ * @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.
+     */
+    public Object getFirstValue() {
+        // sentinel.next points to the "first" element of the sequence -- the head
+        // of the list -- and the requisite value 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 value,
+        // 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.getValue();
+    }
+
+    /**
+     *  Return the entry for the "newest" 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.  The behavior is equivalent to:
+     *
+     *  <pre>
+     *    Object obj = null;
+     *    Iterator iter = entrySet().iterator();
+     *    while(iter.hasNext()) {
+     *      obj = iter.next();
+     *    }
+     *    return (Map.Entry)obj;
+     *  </pre>
+     *
+     *  However, the implementation of this method ensures an O(1) lookup of the
+     *  last key rather than O(n).
+     *
+     *  @return The last entry in the sequence, or <code>null</code> if the map
+     *  is empty.
+     */
+    public Map.Entry getLast() {
+        // sentinel.prev points to the "last" element of the sequence -- the tail
+        // 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.prev;
+    }
+
+    /**
+     *  Return the key for the "newest" mapping.  That is, return the key for the
+     *  mapping that was last put into the map when compared to all the other
+     *  objects in the map.  This behavior is equivalent to using
+     *  <code>getLast().getKey()</code>, but this method provides a slightly
+     *  optimized implementation.
+     *
+     *  @return The last key in the sequence, or <code>null</code> if the map
is
+     *  empty.
+     */
+    public Object getLastKey() {
+        // sentinel.prev points to the "last" element of the sequence -- the tail
+        // 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.prev 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.prev.getKey();
+    }
+
+    /**
+     *  Return the value for the "newest" mapping.  That is, return the value for
+     *  the mapping that was last put into the map when compared to all the other
+     *  objects in the map.  This behavior is equivalent to using
+     *  <code>getLast().getValue()</code>, but this method provides a slightly
+     *  optimized implementation.
+     *
+     *  @return The last value in the sequence, or <code>null</code> if the map
+     *  is empty.
+     */
+    public Object getLastValue() {
+        // sentinel.prev points to the "last" element of the sequence -- the tail
+        // of the list -- and the requisite value is returned from it.  An empty
+        // list does not need to be tested.  In cases where the list is empty,
+        // sentinel.prev will point to the sentinel itself which has a null value,
+        // 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.prev.getValue();
+    }
+
+    /**
+     *  Implements {@link Map#put(Object, Object)}.
+     */
+    public Object put(Object key, Object value) {
+        modCount++;
+
+        Object oldValue = null;
+
+        // lookup the entry for the specified key
+        Entry e = (Entry) entries.get(key);
+
+        // check to see if it already exists
+        if (e != null) {
+            // remove from list so the entry gets "moved" to the end of list
+            removeEntry(e);
+
+            // update value in map
+            oldValue = e.setValue(value);
+
+            // Note: We do not update the key here because its unnecessary.  We only
+            // do comparisons using equals(Object) and we know the specified key and
+            // that in the map are equal in that sense.  This may cause a problem if
+            // someone does not implement their hashCode() and/or equals(Object)
+            // method properly and then use it as a key in this map.  
+        } else {
+            // add new entry
+            e = new Entry(key, value);
+            entries.put(key, e);
+        }
+        // assert(entry in map, but not list)
+
+        // add to list
+        insertEntry(e);
+
+        return oldValue;
+    }
+
+    /**
+     *  Implements {@link Map#remove(Object)}.
+     */
+    public Object remove(Object key) {
+        Entry e = removeImpl(key);
+        return (e == null) ? null : e.getValue();
+    }
+
+    /**
+     *  Fully remove an entry from the map, returning the old entry or null if
+     *  there was no such entry with the specified key.
+     */
+    private Entry removeImpl(Object key) {
+        Entry e = (Entry) entries.remove(key);
+        if (e == null)
+            return null;
+        modCount++;
+        removeEntry(e);
+        return e;
+    }
+
+    /**
+     *  Adds all the mappings in the specified map to this map, replacing any
+     *  mappings that already exist (as per {@link Map#putAll(Map)}).  The order
+     *  in which the entries are added is determined by the iterator returned
+     *  from {@link Map#entrySet()} for the specified map.
+     *
+     *  @param t the mappings that should be added to this map.
+     *
+     *  @throws NullPointerException if <code>t</code> is <code>null</code>
+     */
+    public void putAll(Map t) {
+        Iterator iter = t.entrySet().iterator();
+        while (iter.hasNext()) {
+            Map.Entry entry = (Map.Entry) iter.next();
+            put(entry.getKey(), entry.getValue());
+        }
+    }
+
+    /**
+     *  Implements {@link Map#clear()}.
+     */
+    public void clear() {
+        modCount++;
+
+        // remove all from the underlying map
+        entries.clear();
+
+        // and the list
+        sentinel.next = sentinel;
+        sentinel.prev = sentinel;
+    }
+
+    /**
+     *  Implements {@link Map#equals(Object)}.
+     */
+    public boolean equals(Object obj) {
+        if (obj == null)
+            return false;
+        if (obj == this)
+            return true;
+
+        if (!(obj instanceof Map))
+            return false;
+
+        return entrySet().equals(((Map) obj).entrySet());
+    }
+
+    /**
+     *  Implements {@link Map#hashCode()}.
+     */
+    public int hashCode() {
+        return entrySet().hashCode();
+    }
+
+    /**
+     *  Provides a string representation of the entries within the map.  The
+     *  format of the returned string may change with different releases, so this
+     *  method is suitable for debugging purposes only.  If a specific format is
+     *  required, use {@link #entrySet()}.{@link Set#iterator() iterator()} and
+     *  iterate over the entries in the map formatting them as appropriate.
+     */
+    public String toString() {
+        StringBuffer buf = new StringBuffer();
+        buf.append('[');
+        for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
+            buf.append(pos.getKey());
+            buf.append('=');
+            buf.append(pos.getValue());
+            if (pos.next != sentinel) {
+                buf.append(',');
+            }
+        }
+        buf.append(']');
+
+        return buf.toString();
+    }
+
+    /**
+     *  Implements {@link Map#keySet()}.
+     */
+    public Set keySet() {
+        return new AbstractSet() {
+
+            // required impls
+            public Iterator iterator() {
+                return new OrderedIterator(KEY);
+            }
+            public boolean remove(Object o) {
+                Entry e = SequencedHashMap.this.removeImpl(o);
+                return (e != null);
+            }
+
+            // more efficient impls than abstract set
+            public void clear() {
+                SequencedHashMap.this.clear();
+            }
+            public int size() {
+                return SequencedHashMap.this.size();
+            }
+            public boolean isEmpty() {
+                return SequencedHashMap.this.isEmpty();
+            }
+            public boolean contains(Object o) {
+                return SequencedHashMap.this.containsKey(o);
+            }
+
+        };
+    }
+
+    /**
+     *  Implements {@link Map#values()}.
+     */
+    public Collection values() {
+        return new AbstractCollection() {
+            // required impl
+            public Iterator iterator() {
+                return new OrderedIterator(VALUE);
+            }
+            public boolean remove(Object value) {
+                // 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) {
+                            SequencedHashMap.this.removeImpl(pos.getKey());
+                            return true;
+                        }
+                    }
+                } else {
+                    for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
+                        if (value.equals(pos.getValue())) {
+                            SequencedHashMap.this.removeImpl(pos.getKey());
+                            return true;
+                        }
+                    }
+                }
+
+                return false;
+            }
+
+            // more efficient impls than abstract collection
+            public void clear() {
+                SequencedHashMap.this.clear();
+            }
+            public int size() {
+                return SequencedHashMap.this.size();
+            }
+            public boolean isEmpty() {
+                return SequencedHashMap.this.isEmpty();
+            }
+            public boolean contains(Object o) {
+                return SequencedHashMap.this.containsValue(o);
+            }
+        };
+    }
+
+    /**
+     *  Implements {@link Map#entrySet()}.
+     */
+    public Set entrySet() {
+        return new AbstractSet() {
+            // helper
+            private Entry findEntry(Object o) {
+                if (o == null)
+                    return null;
+                if (!(o instanceof Map.Entry))
+                    return null;
+
+                Map.Entry e = (Map.Entry) o;
+                Entry entry = (Entry) entries.get(e.getKey());
+                if (entry != null && entry.equals(e))
+                    return entry;
+                else
+                    return null;
+            }
+
+            // required impl
+            public Iterator iterator() {
+                return new OrderedIterator(ENTRY);
+            }
+            public boolean remove(Object o) {
+                Entry e = findEntry(o);
+                if (e == null)
+                    return false;
+
+                return SequencedHashMap.this.removeImpl(e.getKey()) != null;
+            }
+
+            // more efficient impls than abstract collection
+            public void clear() {
+                SequencedHashMap.this.clear();
+            }
+            public int size() {
+                return SequencedHashMap.this.size();
+            }
+            public boolean isEmpty() {
+                return SequencedHashMap.this.isEmpty();
+            }
+            public boolean contains(Object o) {
+                return findEntry(o) != null;
+            }
+        };
+    }
+
+    // constants to define what the iterator should return on "next"
+    private static final int KEY = 0;
+    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 KEY, VALUE, or 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.  Essentially, if this value is negative (i.e. the
+         *  bit specified by 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 KEY, VALUE, or 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.
+         *
+         *  @throws NoSuchElementException if there are no more elements in the
+         *  iterator.
+         *
+         *  @throws 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.
+         *
+         *  @throws 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.
+         *
+         *  @throws 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.  
+     *
+     * @throws 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
+     *
+     *  @throws 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;
+    }
+
+    /**
+     * Gets the key at the specified index.
+     *
+     * @param index  the index to retrieve
+     * @return the key at the specified index, or null
+     * @throws 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();
+    }
+
+    /**
+     * Gets the value at the specified index.
+     *
+     * @param index  the index to retrieve
+     * @return the value at the specified index, or null
+     * @throws 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();
+    }
+
+    /**
+     * Gets the index of the specified key.
+     * 
+     * @param key  the key to find the index of
+     * @return the index, or -1 if not found
+     */
+    public int indexOf(Object key) {
+        Entry e = (Entry) entries.get(key);
+        if (e == null) {
+            return -1;
+        }
+        int pos = 0;
+        while (e.prev != sentinel) {
+            pos++;
+            e = e.prev;
+        }
+        return pos;
+    }
+
+    /**
+     * Gets an iterator over the keys.
+     * 
+     * @return an iterator over the keys
+     */
+    public Iterator iterator() {
+        return keySet().iterator();
+    }
+
+    /**
+     * Gets the last index of the specified key.
+     * 
+     * @param key  the key to find the index of
+     * @return the index, or -1 if not found
+     */
+    public int lastIndexOf(Object key) {
+        // keys in a map are guaranteed 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 corresponding the <code>key</code>, or
+     *              <code>null</code> if none existed.
+     *
+     * @throws 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;
+
+}

Mime
View raw message