/*
* J.A.D.E. Java(TM) Addition to Default Environment.
* Latest release available at http://jade.dautelle.com/
* This class is public domain (not copyrighted).
*
* This class was added from J.A.D.E. directly to avoid adding the jade.jar
* which was causing a conflict with parsing XML menus in FreeHep for some reason
*/
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
/**
* This class represents a Map collection with real-time
* behavior. Unless the map's size exceeds its current capacity,
* no dynamic memory allocation is ever performed and response time is
* extremely fast and consistent.
*
* Our benchmark
* indicates that {@link FastMap#put FastMap.put(key, value)} is up to
* 5x faster than java.util.HashMap.put(key, value).
* This difference is mostly due to the cost of the Map.Entry
* allocations that {@link FastMap} avoids by recycling its entries
* (see note below).
*
* {@link FastMap} has a predictable iteration order, which is the order
* in which keys were inserted into the map (similar to
* java.util.LinkedHashMap collection class).
* A bi-directional list iterator over the map entries is also
* {@link #fastIterator provided}, this iterator can be moved
* to the {@link FastIterator#toFirst first} or to the
* {@link FastIterator#toLast last} entry for unlimited reuse.
*
* Applications may change the resizing policy of {@link FastMap}
* by overriding the {@link #sizeChanged} method. For example, to reduce
* memory footprint, the map's capacity could be maitained at ±50% of
* the current map's size.
*
* This implementation is not synchronized. Multiple threads accessing
* or modifying the collection must be synchronized externally.
*
* Note: To avoid dynamic memory allocations, {@link FastMap}
* maintains an internal pool of Map.Entry objects. The size
* of the pool is determined by the map's capacity. When an entry is
* removed from the map, it is automatically restored to the pool.
*
* This class is public domain (not copyrighted).
*
* @author Jean-Marie Dautelle
* @version 6.0, January 18 2004
*/
public class FastMap implements Map, Cloneable, Serializable {
/**
* Holds the map's hash table.
*/
private transient EntryImpl[] _entries;
/**
* Holds the map's current capacity.
*/
private transient int _capacity;
/**
* Holds the hash code mask.
*/
private transient int _mask;
/**
* Holds the first pool entry (linked list).
*/
private transient EntryImpl _poolFirst;
/**
* Holds the first map entry (linked list).
*/
private transient EntryImpl _mapFirst;
/**
* Holds the last map entry (linked list).
*/
private transient EntryImpl _mapLast;
/**
* Holds the current size.
*/
private transient int _size;
/**
* Creates a {@link FastMap} with a capacity of 16 entries.
*/
public FastMap() {
initialize(16);
}
/**
* Creates a {@link FastMap}, copy of the specified Map.
* If the specified map is not an instance of {@link FastMap}, the
* newly created map has a capacity set to the specified map's size.
* The copy has the same order as the original, regardless of the original
* map's implementation:
* TreeMap dictionary = ...;
* FastMap dictionaryLookup = new FastMap(dictionary);
*
*
* @param map the map whose mappings are to be placed in this map.
*/
public FastMap(Map map) {
int capacity = (map instanceof FastMap) ?
((FastMap)map).capacity() : map.size();
initialize(capacity);
putAll(map);
}
/**
* Creates a {@link FastMap} with the specified capacity. Unless the
* capacity is exceeded, operations on this map do not allocate entries.
* For optimum performance, the capacity should be of the same order
* of magnitude or larger than the expected map's size.
*
* @param capacity the number of buckets in the hash table; it also
* defines the number of pre-allocated entries.
*/
public FastMap(int capacity) {
initialize(capacity);
}
/**
* Returns the number of key-value mappings in this {@link FastMap}.
*
* @return this map's size.
*/
public int size() {
return _size;
}
/**
* Returns the capacity of this {@link FastMap}. The capacity defines
* the number of buckets in the hash table, as well as the maximum number
* of entries the map may contain without allocating memory.
*
* @return this map's capacity.
*/
public int capacity() {
return _capacity;
}
/**
* Indicates if this {@link FastMap} contains no key-value mappings.
*
* @return true if this map contains no key-value mappings;
* false otherwise.
*/
public boolean isEmpty() {
return _size == 0;
}
/**
* Indicates if this {@link FastMap} contains a mapping for the specified
* key.
*
* @param key the key whose presence in this map is to be tested.
* @return true if this map contains a mapping for the
* specified key; false otherwise.
* @throws NullPointerException if the key is null.
*/
public boolean containsKey(Object key) {
EntryImpl entry = _entries[keyHash(key) & _mask];
while (entry != null) {
if (key.equals(entry._key) ) {
return true;
}
entry = entry._next;
}
return false;
}
/**
* Indicates if this {@link FastMap} maps one or more keys to the
* specified value.
*
* @param value the value whose presence in this map is to be tested.
* @return true if this map maps one or more keys to the
* specified value.
* @throws NullPointerException if the key is null.
*/
public boolean containsValue(Object value) {
EntryImpl entry = _mapFirst;
while (entry != null) {
if (value.equals(entry._value) ) {
return true;
}
entry = entry._after;
}
return false;
}
/**
* Returns the value to which this {@link FastMap} maps the specified key.
*
* @param key the key whose associated value is to be returned.
* @return the value to which this map maps the specified key,
* or null if there is no mapping for the key.
* @throws NullPointerException if key is null.
*/
public Object get(Object key) {
EntryImpl entry = _entries[keyHash(key) & _mask];
while (entry != null) {
if (key.equals(entry._key) ) {
return entry._value;
}
entry = entry._next;
}
return null;
}
/**
* Returns the entry with the specified key.
*
* @param key the key whose associated entry is to be returned.
* @return the entry for the specified key or null if none.
*/
public Entry getEntry(Object key) {
EntryImpl entry = _entries[keyHash(key) & _mask];
while (entry != null) {
if (key.equals(entry._key)) {
return entry;
}
entry = entry._next;
}
return null;
}
/**
* Associates the specified value with the specified key in this
* {@link FastMap}. If the {@link FastMap} previously contained a mapping
* for this key, the old value is replaced.
*
* @param key the key with which the specified value is to be associated.
* @param value the value to be associated with the specified key.
* @return the previous value associated with specified key,
* or null if there was no mapping for key.
* A null return can also indicate that the map
* previously associated null with the specified key.
* @throws NullPointerException if the key is null.
*/
public Object put(Object key, Object value) {
EntryImpl entry = _entries[keyHash(key) & _mask];
while (entry != null) {
if (key.equals(entry._key) ) {
Object prevValue = entry._value;
entry._value = value;
return prevValue;
}
entry = entry._next;
}
// No previous mapping.
addEntry(key, value);
return null;
}
/**
* Returns a reusable {@link FastIterator} over this {@link FastMap} entries
* (unique instance per map). For example:
* // Iteration without memory allocation!
* for (FastIterator i=map.fastIterator().toFirst(); i.hasNext();) {
* Entry entry = i.nextEntry();
* ...
* }
*
* @return an iterator which can be reset for reuse over and over.
* @see FastMap.FastIterator
*/
public FastIterator fastIterator() {
return _fastIterator;
}
private final FastIterator _fastIterator = new FastIterator();
/**
* Copies all of the mappings from the specified map to this
* {@link FastMap}.
*
* @param map the mappings to be stored in this map.
* @throws NullPointerException the specified map is null, or
* the specified map contains null keys.
*/
public void putAll(Map map) {
for (Iterator i = map.entrySet().iterator(); i.hasNext(); ) {
Entry e = (Entry) i.next();
addEntry(e.getKey(), e.getValue());
}
}
/**
* Removes the mapping for this key from this {@link FastMap} if present.
*
* @param key the key whose mapping is to be removed from the map.
* @return previous value associated with specified key,
* or null if there was no mapping for key.
* A null return can also indicate that the map
* previously associated null with the specified key.
* @throws NullPointerException if the key is null.
*/
public Object remove(Object key) {
EntryImpl entry = _entries[keyHash(key) & _mask];
while (entry != null) {
if (key.equals(entry._key) ) {
Object prevValue = entry._value;
removeEntry(entry);
return prevValue;
}
entry = entry._next;
}
return null;
}
/**
* Removes all mappings from this {@link FastMap}.
*/
public void clear() {
// Clears all keys, values and buckets linked lists.
for (EntryImpl entry = _mapFirst; entry != null; entry = entry._after) {
entry._key = null;
entry._value = null;
entry._before = null;
entry._next = null;
if (entry._previous == null) { // First in bucket.
_entries[entry._index] = null;
} else {
entry._previous = null;
}
}
// Recycles all entries.
if (_mapLast != null) {
_mapLast._after = _poolFirst; // Connects to pool.
_poolFirst = _mapFirst;
_mapFirst = null;
_mapLast = null;
_size = 0;
sizeChanged();
}
}
/**
* Changes the current capacity of this {@link FastMap}. If the capacity
* is increased, new entries are allocated and added to the pool.
* If the capacity is decreased, entries from the pool are deallocated
* (and are garbage collected eventually). The capacity also determined
* the number of buckets for the hash table.
*
* @param newCapacity the new capacity of this map.
*/
public void setCapacity(int newCapacity) {
if (newCapacity > _capacity) { // Capacity increases.
for (int i = _capacity; i < newCapacity; i++) {
EntryImpl entry = new EntryImpl();
entry._after = _poolFirst;
_poolFirst = entry;
}
} else if (newCapacity < _capacity) { // Capacity decreases.
for ( int i = newCapacity;
(i < _capacity) && (_poolFirst != null); i++) {
// Disconnects the entry for gc to do its work.
EntryImpl entry = _poolFirst;
_poolFirst = entry._after;
entry._after = null; // All pointers are now null!
}
}
// Find a power of 2 >= capacity
int tableLength = 16;
while (tableLength < newCapacity) {
tableLength <<= 1;
}
// Checks if the hash table has to be re-sized.
if (_entries.length != tableLength) {
_entries = new EntryImpl[tableLength];
_mask = tableLength - 1;
// Repopulates the hash table.
EntryImpl entry = _mapFirst;
while (entry != null) {
int index = keyHash(entry._key) & _mask;
entry._index = index;
// Connects to bucket.
entry._previous = null; // Resets previous.
EntryImpl next = _entries[index];
entry._next = next;
if (next != null) {
next._previous = entry;
}
_entries[index] = entry;
entry = entry._after;
}
}
_capacity = newCapacity;
}
/**
* Returns a shallow copy of this {@link FastMap}. The keys and
* the values themselves are not cloned.
*
* @return a shallow copy of this map.
*/
public Object clone() {
try {
FastMap clone = (FastMap) super.clone();
clone.initialize(_capacity);
clone.putAll(this);
return clone;
} catch (CloneNotSupportedException e) {
// Should not happen, since we are Cloneable.
throw new InternalError();
}
}
/**
* Compares the specified object with this {@link FastMap} for equality.
* Returns true if the given object is also a map and the two
* maps represent the same mappings (regardless of collection iteration
* order).
*
* @param obj the object to be compared for equality with this map.
* @return true if the specified object is equal to this map;
* false otherwise.
*/
public boolean equals(Object obj) {
if (obj == this) {
return true;
} else if (obj instanceof Map) {
Map that = (Map) obj;
if (this.size() == that.size()) {
EntryImpl entry = _mapFirst;
while (entry != null) {
if (!that.entrySet().contains(entry)) {
return false;
}
entry = entry._after;
}
return true;
} else {
return false;
}
} else {
return false;
}
}
/**
* Returns the hash code value for this {@link FastMap}.
*
* @return the hash code value for this map.
*/
public int hashCode() {
int code = 0;
EntryImpl entry = _mapFirst;
while (entry != null) {
code += entry.hashCode();
entry = entry._after;
}
return code;
}
/**
* Returns a String representation of this {@link FastMap}.
*
* @return this.entrySet().toString();
*/
public String toString() {
return entrySet().toString();
}
/**
* Returns a collection view of the values contained in this
* {@link FastMap}. The collection is backed by the map, so changes to
* the map are reflected in the collection, and vice-versa.
* The collection supports element removal, which removes the corresponding
* mapping from this map, via the
* Iterator.remove, Collection.remove,
* removeAll, retainAll,
* and clear operations. It does not support the
* add or addAll operations.
*
* @return a collection view of the values contained in this map.
*/
public Collection values() {
return _values;
}
private transient Values _values;
private class Values extends AbstractCollection {
public Iterator iterator() {
return new Iterator() {
EntryImpl after = _mapFirst;
EntryImpl before;
public void remove() {
if (before != null) {
removeEntry(before);
} else {
throw new IllegalStateException();
}
}
public boolean hasNext() {
return after != null;
}
public Object next() {
if (after != null) {
before = after;
after = after._after;
return before._value;
} else {
throw new NoSuchElementException();
}
}
};
}
public int size() {
return _size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
FastMap.this.clear();
}
}
/**
* Returns a collection view of the mappings contained in this
* {@link FastMap}. Each element in the returned collection is a
* Map.Entry. The collection is backed by the map,
* so changes to the map are reflected in the collection, and vice-versa.
* The collection supports element removal, which removes the corresponding
* mapping from this map, via the
* Iterator.remove, Collection.remove,
* removeAll, retainAll,
* and clear operations. It does not support the
* add or addAll operations.
*
* @return a collection view of the mappings contained in this map.
*/
public Set entrySet() {
return _entrySet;
}
private transient EntrySet _entrySet;
private class EntrySet extends AbstractSet {
public Iterator iterator() {
return new Iterator() {
EntryImpl after = _mapFirst;
EntryImpl before;
public void remove() {
if (before != null) {
removeEntry(before);
} else {
throw new IllegalStateException();
}
}
public boolean hasNext() {
return after != null;
}
public Object next() {
if (after != null) {
before = after;
after = after._after;
return before;
} else {
throw new NoSuchElementException();
}
}
};
}
public int size() {
return _size;
}
public boolean contains(Object obj) { // Optimization.
if (obj instanceof Entry) {
Entry entry = (Entry) obj;
Entry mapEntry = getEntry(entry.getKey());
return entry.equals(mapEntry);
} else {
return false;
}
}
public boolean remove(Object obj) { // Optimization.
if (obj instanceof Entry) {
Entry entry = (Entry)obj;
EntryImpl mapEntry = (EntryImpl) getEntry(entry.getKey());
if ((mapEntry != null) &&
(entry.getValue()).equals(mapEntry._value)) {
removeEntry(mapEntry);
return true;
}
}
return false;
}
}
/**
* Returns a set view of the keys contained in this {@link FastMap}.
* The set is backed by the map, so changes to the map are reflected
* in the set, and vice-versa. The set supports element removal,
* which removes the corresponding mapping from this map, via the
* Iterator.remove, Collection.remove,
* removeAll, retainAll,
* and clear operations. It does not support the
* add or addAll operations.
*
* @return a set view of the keys contained in this map.
*/
public Set keySet() {
return _keySet;
}
private transient KeySet _keySet;
private class KeySet extends AbstractSet {
public Iterator iterator() {
return new Iterator() {
EntryImpl after = _mapFirst;
EntryImpl before;
public void remove() {
if (before != null) {
removeEntry(before);
} else {
throw new IllegalStateException();
}
}
public boolean hasNext() {
return after != null;
}
public Object next() {
if (after != null) {
before = after;
after = after._after;
return before._key;
} else {
throw new NoSuchElementException();
}
}
};
}
public int size() {
return _size;
}
public boolean contains(Object obj) { // Optimization.
return FastMap.this.containsKey(obj);
}
public boolean remove(Object obj) { // Optimization.
return FastMap.this.remove(obj) != null;
}
public void clear() { // Optimization.
FastMap.this.clear();
}
}
/**
* This methods is being called when the size of this {@link FastMap}
* has changed. The default behavior is to double the map's capacity
* when the map's size exceeds the current map's capacity.
* Sub-class may override this method to implement custom resizing
* policies or to disable automatic resizing. For example:
* Map fixedCapacityMap = new FastMap(256) {
* protected sizeChanged() {
* // Do nothing, automatic resizing disabled.
* }
* };
* @see #setCapacity
*/
protected void sizeChanged() {
if (size() > capacity()) {
setCapacity(capacity() * 2);
}
}
/**
* Returns the hash code for the specified key. The formula being used
* is identical to the formula used by java.util.HashMap
* (ensures similar behavior for ill-conditioned hashcode keys).
*
* @param key the key to calculate the hashcode for.
* @return the hash code for the specified key.
*/
private static int keyHash(Object key) {
// From HashMap.hash(Object) function.
int hashCode = key.hashCode();
hashCode += ~(hashCode << 9);
hashCode ^= (hashCode >>> 14);
hashCode += (hashCode << 4);
hashCode ^= (hashCode >>> 10);
return hashCode;
}
/**
* Adds a new entry for the specified key and value.
* @param key the entry's key.
* @param value the entry's value.
*/
private void addEntry(Object key, Object value) {
EntryImpl entry = _poolFirst;
if (entry != null) {
_poolFirst = entry._after;
entry._after = null;
} else { // Pool empty.
entry = new EntryImpl();
}
// Setup entry parameters.
entry._key = key;
entry._value = value;
int index = keyHash(key) & _mask;
entry._index = index;
// Connects to bucket.
EntryImpl next = _entries[index];
entry._next = next;
if (next != null) {
next._previous = entry;
}
_entries[index] = entry;
// Connects to collection.
if (_mapLast != null) {
entry._before = _mapLast;
_mapLast._after = entry;
} else {
_mapFirst = entry;
}
_mapLast = entry;
// Updates size.
_size++;
sizeChanged();
}
/**
* Removes the specified entry from the map.
*
* @param entry the entry to be removed.
*/
private void removeEntry(EntryImpl entry) {
// Removes from bucket.
EntryImpl previous = entry._previous;
EntryImpl next = entry._next;
if (previous != null) {
previous._next = next;
entry._previous = null;
} else { // First in bucket.
_entries[entry._index] = next;
}
if (next != null) {
next._previous = previous;
entry._next = null;
} // Else do nothing, no last pointer.
// Removes from collection.
EntryImpl before = entry._before;
EntryImpl after = entry._after;
if (before != null) {
before._after = after;
entry._before = null;
} else { // First in collection.
_mapFirst = after;
}
if (after != null) {
after._before = before;
} else { // Last in collection.
_mapLast = before;
}
// Clears value and key.
entry._key = null;
entry._value = null;
// Recycles.
entry._after = _poolFirst;
_poolFirst = entry;
// Updates size.
_size--;
sizeChanged();
}
/**
* Initializes this instance for the specified capacity.
* Once initialized, operations on this map should not create new objects
* (unless the map's size exceeds the specified capacity).
*
* @param capacity the initial capacity.
*/
private void initialize(int capacity) {
// Find a power of 2 >= capacity
int tableLength = 16;
while (tableLength < capacity) {
tableLength <<= 1;
}
// Allocates hash table.
_entries = new EntryImpl[tableLength];
_mask = tableLength - 1;
_capacity = capacity;
_size = 0;
// Allocates views.
_values = new Values();
_entrySet = new EntrySet();
_keySet = new KeySet();
// Resets pointers.
_poolFirst = null;
_mapFirst = null;
_mapLast = null;
// Allocates entries.
for (int i=0; i < capacity; i++) {
EntryImpl entry = new EntryImpl();
entry._after = _poolFirst;
_poolFirst = entry;
}
}
/**
* Requires special handling during de-serialization process.
*
* @param stream the object input stream.
* @throws IOException if an I/O error occurs.
* @throws ClassNotFoundException if the class for the object de-serialized
* is not found.
*/
private void readObject(ObjectInputStream stream)
throws IOException, ClassNotFoundException {
int capacity = stream.readInt();
initialize(capacity);
int size = stream.readInt();
for (int i=0; i < size; i++) {
Object key = stream.readObject();
Object value = stream.readObject();
addEntry(key, value);
}
}
/**
* Requires special handling during serialization process.
*
* @param stream the object output stream.
* @throws IOException if an I/O error occurs.
*/
private void writeObject(ObjectOutputStream stream) throws IOException {
stream.writeInt(_capacity);
stream.writeInt(_size);
int count = 0;
EntryImpl entry = _mapFirst;
while (entry != null) {
stream.writeObject(entry._key);
stream.writeObject(entry._value);
count++;
entry = entry._after;
}
if (count != _size) {
throw new IOException("FastMap Corrupted");
}
}
/**
* This inner class represents a reusable list iterator over
* {@link FastMap} entries. This iterator is bi-directional and can be
* directly moved to the {@link #toFirst first} or {@link #toLast last}
* entry. For example:
* for (FastIterator i=map.fastIterator().toFirst(); i.hasNext();) {
* Entry entry = i.nextEntry();
* ...
* }
* {@link #set setting} or {@link #add adding} new entries is not
* supported.
*/
public final class FastIterator implements ListIterator {
EntryImpl after = _mapFirst;
EntryImpl before;
int nextIndex = 0;
public FastIterator toFirst() {
after = _mapFirst;
before = null;
nextIndex = 0;
return this;
}
public FastIterator toLast() {
after = null;
before = _mapLast;
nextIndex = _size;
return this;
}
public boolean hasNext() {
return after != null;
}
public Entry nextEntry() {
if (after != null) {
nextIndex++;
before = after;
after = after._after;
return before;
} else {
throw new NoSuchElementException();
}
}
public Object next() {
return nextEntry();
}
public boolean hasPrevious() {
return before != null;
}
public Entry previousEntry() {
if (before != null) {
nextIndex--;
after = before;
before = before._after;
return after;
} else {
throw new NoSuchElementException();
}
}
public Object previous() {
return previousEntry();
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
if (before != null) {
removeEntry(before);
} else {
throw new IllegalStateException();
}
}
public void set(Object o) {
throw new UnsupportedOperationException();
}
public void add(Object o) {
throw new UnsupportedOperationException();
}
}
/**
* This class represents a {@link FastMap} entry.
*/
private static final class EntryImpl implements Entry {
/**
* Holds the entry key (null when in pool).
*/
private Object _key;
/**
* Holds the entry value (null when in pool).
*/
private Object _value;
/**
* Holds the bucket index (undefined when in pool).
*/
private int _index;
/**
* Holds the previous entry in the same bucket (null when in pool).
*/
private EntryImpl _previous;
/**
* Holds the next entry in the same bucket (null when in pool).
*/
private EntryImpl _next;
/**
* Holds the entry added before this entry (null when in pool).
*/
private EntryImpl _before;
/**
* Holds the entry added after this entry
* or the next available entry when in pool.
*/
private EntryImpl _after;
/**
* Returns the key for this entry.
*
* @return the entry's key.
*/
public Object getKey() {
return _key;
}
/**
* Returns the value for this entry.
*
* @return the entry's value.
*/
public Object getValue() {
return _value;
}
/**
* Sets the value for this entry.
*
* @param value the new value.
* @return the previous value.
*/
public Object setValue(Object value) {
Object old = _value;
_value = value;
return old;
}
/**
* Indicates if this entry is considered equals to the specified
* entry.
*
* @param that the object to test for equality.
* @return true if both entry are considered equal;
* false otherwise.
*/
public boolean equals(Object that) {
if (that instanceof Entry) {
Entry entry = (Entry) that;
return (_key.equals(entry.getKey())) &&
((_value != null) ?
_value.equals(entry.getValue()) :
(entry.getValue() == null));
} else {
return false;
}
}
/**
* Returns the hash code for this entry.
*
* @return this entry's hash code.
*/
public int hashCode() {
return _key.hashCode() ^ ((_value != null) ? _value.hashCode() : 0);
}
/**
* Returns the text representation of this entry.
*
* @return this entry's textual representation.
*/
public String toString() {
return _key + "=" + _value;
}
}
}