|
Commons Collections example source code file (SequencedHashMap.java)
The Commons Collections SequencedHashMap.java source code/* * 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.commons.collections; import java.io.Externalizable; import java.io.IOException; import java.io.ObjectInput; import java.io.ObjectOutput; import java.util.AbstractCollection; import java.util.AbstractSet; import java.util.ArrayList; import java.util.Collection; import java.util.ConcurrentModificationException; import java.util.HashMap; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; import org.apache.commons.collections.list.UnmodifiableList; /** * A map of objects whose mapping entries are sequenced based on the order in * which they were added. This data structure has fast <i>O(1) search * time, deletion time, and insertion time. * <p> * Although this map is sequenced, it cannot implement * {@link java.util.List} because of incompatible interface definitions. * The remove methods in List and Map have different return values * (see: {@link java.util.List#remove(Object)} and {@link java.util.Map#remove(Object)}). * <p> * This class is not thread safe. When a thread safe implementation is * required, use {@link java.util.Collections#synchronizedMap(Map)} as it is documented, * or use explicit synchronization controls. * * @deprecated Replaced by LinkedMap and ListOrderedMap in map subpackage. Due to be removed in v4.0. * @see org.apache.commons.collections.map.LinkedMap * @see org.apache.commons.collections.map.ListOrderedMap * @since Commons Collections 2.0 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ * * @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 * 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(), but this method provides an * optimized implementation. * * @return The first entry in the sequence, or <code>null 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(), but this method provides a slightly * optimized implementation. * * @return The first key in the sequence, or <code>null 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(), but this method provides a slightly * optimized implementation. * * @return The first value in the sequence, or <code>null 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 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(), but this method provides a slightly * optimized implementation. * * @return The last key in the sequence, or <code>null 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(), but this method provides a slightly * optimized implementation. * * @return The last value in the sequence, or <code>null 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 is Other Commons Collections examples (source code examples)Here is a short list of links related to this Commons Collections SequencedHashMap.java source code file: |
... this post is sponsored by my books ... | |
#1 New Release! |
FP Best Seller |
Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.
A percentage of advertising revenue from
pages under the /java/jwarehouse
URI on this website is
paid back to open source projects.