| /* |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you 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.directory.shared.ldap.util; |
| |
| |
| 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.Collections; |
| 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.KeyValue; |
| import org.apache.directory.shared.i18n.I18n; |
| |
| |
| /** |
| * 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. |
| * |
| * @since Commons Collections 2.0 |
| * @version $Revision$ $Date$ |
| * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</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, 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; |
| } |
| |
| |
| /** |
| * Compute the instance's hash code |
| * @return the instance's hash code |
| */ |
| 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()}. |
| * @return the instance's hash code |
| */ |
| 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( I18n.err( I18n.ERR_04425, 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( I18n.err( I18n.ERR_04426 ) ); |
| } |
| 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>< 0</code> or |
| * <code>></code> the size of the map. |
| */ |
| private Map.Entry getEntry( int index ) |
| { |
| Entry pos = sentinel; |
| |
| if ( index < 0 ) |
| { |
| throw new ArrayIndexOutOfBoundsException( I18n.err( I18n.ERR_04427, index ) ); |
| } |
| |
| // 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( I18n.err( I18n.ERR_04428, 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>< 0</code> or |
| * <code>></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>< 0</code> or |
| * <code>></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>< 0</code> or |
| * <code>></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; |
| |
| } |
