Java/Collections Data Structure/Soft Map
A java.util.Map implementation with soft values
<source lang="java">
/*
* Copyright 2002-2006 (C) TJDO. * All rights reserved. * * This software is distributed under the terms of the TJDO License version 1.0. * See the terms of the TJDO License in the documentation provided with this software. * * $Id: ReferenceValueMap.java,v 1.8 2006/09/08 16:11:28 jackknifebarber Exp $ */
import java.lang.ref.Reference; import java.lang.ref.ReferenceQueue; import java.util.AbstractMap; import java.util.AbstractSet; import java.util.Collection; import java.util.Iterator; import java.util.Map; import java.util.Set; /*
* Copyright 2002-2006 (C) TJDO. * All rights reserved. * * This software is distributed under the terms of the TJDO License version 1.0. * See the terms of the TJDO License in the documentation provided with this software. * * $Id: SoftValueMap.java,v 1.5 2006/09/08 16:11:28 jackknifebarber Exp $ */
import java.lang.ref.Reference; import java.lang.ref.SoftReference; import java.util.HashMap; import java.util.Map;
/**
* A java.util.Map implementation with soft values.
*
* The values are stored as soft references.
* If map entry value object is not actively being used, i.e. no other object
* has a strong reference to it, it may become garbage collected at the
* discretion of the garbage collector (typically if the VM is low on memory).
* If this happens, the entry in the SoftValueMap corresponding to
* the value object will also be removed.
*
* @author
* @version $Revision: 1.8 $
*/
abstract class ReferenceValueMap extends AbstractMap
{
protected final ReferenceQueue refQueue = new ReferenceQueue();
/** Backing map. */
private final Map backing;
ReferenceValueMap(Map backing)
{
this.backing = backing;
}
/**
* Returns a new Reference object to be inserted into the map.
* Subclasses must implement this method to construct Reference
* objects of the desired type (e.g. SoftReference, etc.).
*
* @param value
* The associated value to be referenced.
*
* @return
* A new Reference object to be inserted into the map.
*/
protected abstract Reference newReference(Object value);
private void reap()
{
Reference ref;
while ((ref = refQueue.poll()) != null)
backing.values().remove(ref);
}
public Object put(Object key, Object value)
{
reap();
return backing.put(key, newReference(value));
}
public Object get(Object key)
{
reap();
Object v = backing.get(key);
return (v instanceof Reference) ? ((Reference)v).get() : v;
}
public int size()
{
reap();
return backing.size();
}
public boolean isEmpty()
{
reap();
return backing.isEmpty();
}
public boolean containsKey(Object key)
{
reap();
return backing.containsKey(key);
}
public boolean containsValue(Object value)
{
reap();
return super.containsValue(value);
}
public Set keySet()
{
reap();
return backing.keySet();
}
public Collection values()
{
reap();
return super.values();
}
public Set entrySet()
{
reap();
return new EntrySet();
}
public Object remove(Object key)
{
reap();
return backing.remove(key);
}
public int hashCode()
{
reap();
return super.hashCode();
}
public boolean equals(Object o)
{
reap();
return super.equals(o);
}
public String toString()
{
reap();
return super.toString();
}
static boolean eq(Object o1, Object o2)
{
return o1 == null ? o2 == null : o1.equals(o2);
}
private class EntrySet extends AbstractSet
{
/** Backing set. */
private final Set set = backing.entrySet();
public Iterator iterator()
{
return new Iterator()
{
private Iterator i = set.iterator();
public boolean hasNext()
{
return i.hasNext();
}
public void remove()
{
i.remove();
}
public Object next()
{
final Map.Entry ent = (Map.Entry)i.next();
return new Map.Entry()
{
public Object getKey()
{
return ent.getKey();
}
public Object getValue()
{
Object v = ent.getValue();
return (v instanceof Reference) ? ((Reference)v).get() : v;
}
public Object setValue(Object v)
{
Object oldVal = getValue();
ent.setValue(newReference(v));
return oldVal;
}
public boolean equals(Object o)
{
if (o == this)
return true;
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
return eq(ent.getKey(), e.getKey())
&& eq(ent.getValue(), e.getValue());
}
public int hashCode()
{
Object key = ent.getKey();
Object val = ent.getValue();
return (key == null ? 0 : key.hashCode())
^ (val == null ? 0 : val.hashCode());
}
public String toString()
{
return ent.getKey() + "=" + ent.getValue();
}
};
}
};
}
public int size()
{
reap();
return set.size();
}
public boolean isEmpty()
{
reap();
return set.isEmpty();
}
public boolean contains(Object o)
{
reap();
return super.contains(o);
}
public Object[] toArray()
{
reap();
return super.toArray();
}
public Object[] toArray(Object[] a)
{
reap();
return super.toArray(a);
}
public boolean remove(Object o)
{
reap();
return super.remove(o);
}
public boolean containsAll(Collection c)
{
reap();
return super.containsAll(c);
}
public boolean removeAll(Collection c)
{
reap();
return super.removeAll(c);
}
public boolean retainAll(Collection c)
{
reap();
return super.retainAll(c);
}
public void clear()
{
set.clear();
}
public String toString()
{
reap();
return super.toString();
}
}
}
</source>
Soft HashMap
<source lang="java">
/*
* dbXML - Native XML Database * Copyright (C) 1999-2004 The dbXML Group, L.L.C. * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version 2 * of the License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * * $Id: SoftHashMap.java,v 1.2 2004/02/12 00:17:58 bradford Exp $ */
import java.lang.ref.ReferenceQueue; import java.lang.ref.SoftReference; import java.util.AbstractMap; import java.util.HashMap; import java.util.Map; import java.util.Set; /**
* SoftHashMap */
public final class SoftHashMap extends AbstractMap {
private Map hash = new HashMap();
private final ReferenceQueue queue = new ReferenceQueue();
public SoftHashMap() {
}
public Object get(Object key) {
Object res = null;
SoftReference sr = (SoftReference)hash.get(key);
if ( sr != null ) {
res = sr.get();
if ( res == null )
hash.remove(key);
}
return res;
}
private void processQueue() {
for ( ;; ) {
SoftValue sv = (SoftValue)queue.poll();
if ( sv != null )
hash.remove(sv.key);
else
return;
}
}
public Object put(Object key, Object value) {
processQueue();
return hash.put(key, new SoftValue(value, key, queue));
}
public Object remove(Object key) {
processQueue();
return hash.remove(key);
}
public void clear() {
processQueue();
hash.clear();
}
public int size() {
processQueue();
return hash.size();
}
public Set entrySet() {
/** @todo Figure this out */
throw new UnsupportedOperationException();
}
/**
* SoftValue
*/
private static class SoftValue extends SoftReference {
private final Object key;
private SoftValue(Object k, Object key, ReferenceQueue q) {
super(k, q);
this.key = key;
}
}
}
</source>
Soft Valued HashMap
<source lang="java">
/*
* Copyright 2006 Brian S O"Neill * * 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. */
//revised from cojen import java.lang.ref.Reference; import java.lang.ref.ReferenceQueue; import java.lang.ref.WeakReference; import java.util.AbstractCollection; import java.util.AbstractMap; import java.util.AbstractSet; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set;
/*
* Copyright 2004 Brian S O"Neill * * 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. */
//revised from cojen import java.lang.ref.Reference; import java.lang.ref.SoftReference; import java.util.Map; /**
* A Map that softly references its values and can be used as a simple cache. * SoftValuedHashMap is not thread-safe and must be wrapped with * Collections.synchronizedMap to be made thread-safe. * <p> * Note: Softly referenced entries may be automatically removed during * either accessor or mutator operations, possibly causing a concurrent * modification to be detected. Therefore, even if multiple threads are only * accessing this map, be sure to synchronize this map first. Also, do not * rely on the value returned by size() when using an iterator from this map. * The iterators may return less entries than the amount reported by size(). * * @author Brian S O"Neill */
public class SoftValuedHashMap<K, V> extends ReferencedValueHashMap<K, V> {
/**
* Constructs a new, empty map with the specified initial
* capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the HashMap.
* @param loadFactor the load factor of the HashMap
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive.
*/
public SoftValuedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
}
/**
* Constructs a new, empty map with the specified initial capacity
* and default load factor, which is 0.75.
*
* @param initialCapacity the initial capacity of the HashMap.
* @throws IllegalArgumentException if the initial capacity is less
* than zero.
*/
public SoftValuedHashMap(int initialCapacity) {
super(initialCapacity);
}
/**
* Constructs a new, empty map with a default capacity and load
* factor, which is 0.75.
*/
public SoftValuedHashMap() {
super();
}
/**
* Constructs a new map with the same mappings as the given map. The
* map is created with a capacity of twice the number of mappings in
* the given map or 11 (whichever is greater), and a default load factor,
* which is 0.75.
*/
public SoftValuedHashMap(Map<? extends K, ? extends V> t) {
super(t);
}
Entry<K, V> newEntry(int hash, K key, V value, Entry<K, V> next) {
return new SoftEntry<K, V>(hash, key, value, next);
}
static class SoftEntry<K, V> extends ReferencedValueHashMap.Entry<K, V> {
SoftEntry(int hash, K key, V value, Entry<K, V> next) {
super(hash, key, value, next);
}
SoftEntry(int hash, K key, Reference<V> value, Entry<K, V> next) {
super(hash, key, value, next);
}
Entry newEntry(int hash, K key, Reference<V> value, Entry<K, V> next) {
return new SoftEntry<K, V>(hash, key, value, next);
}
Reference<V> newReference(V value) {
return new SoftReference<V>(value);
}
}
}
/**
* A Map that references its values and can be used as a simple cache. * Instances are not thread-safe and must be wrapped with * Collections.synchronizedMap to be made thread-safe. * <p> * Note: Referenced entries may be automatically removed during * either accessor or mutator operations, possibly causing a concurrent * modification to be detected. Therefore, even if multiple threads are only * accessing this map, be sure to synchronize this map first. Also, do not * rely on the value returned by size() when using an iterator from this map. * The iterators may return less entries than the amount reported by size(). * * @author Brian S O"Neill */ abstract class ReferencedValueHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable
{
private transient Entry<K, V>[] table;
private transient int count;
private int threshold;
private final float loadFactor;
private transient volatile int modCount;
// Views
private transient Set<K> keySet;
private transient Set<Map.Entry<K, V>> entrySet;
private transient Collection<V> values;
/**
* Constructs a new, empty map with the specified initial
* capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the HashMap.
* @param loadFactor the load factor of the HashMap
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive.
*/
public ReferencedValueHashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal Initial Capacity: "+
initialCapacity);
}
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Illegal Load factor: "+
loadFactor);
}
if (initialCapacity == 0) {
initialCapacity = 1;
}
this.loadFactor = loadFactor;
this.table = new Entry[initialCapacity];
this.threshold = (int)(initialCapacity * loadFactor);
}
/**
* Constructs a new, empty map with the specified initial capacity
* and default load factor, which is 0.75.
*
* @param initialCapacity the initial capacity of the HashMap.
* @throws IllegalArgumentException if the initial capacity is less
* than zero.
*/
public ReferencedValueHashMap(int initialCapacity) {
this(initialCapacity, 0.75f);
}
/**
* Constructs a new, empty map with a default capacity and load
* factor, which is 0.75.
*/
public ReferencedValueHashMap() {
this(11, 0.75f);
}
/**
* Constructs a new map with the same mappings as the given map. The
* map is created with a capacity of twice the number of mappings in
* the given map or 11 (whichever is greater), and a default load factor,
* which is 0.75.
*/
public ReferencedValueHashMap(Map<? extends K, ? extends V> t) {
this(Math.max(2 * t.size(), 11), 0.75f);
putAll(t);
}
public int size() {
return this.count;
}
public boolean isEmpty() {
return this.count == 0;
}
public boolean containsValue(Object value) {
if (value == null) {
value = KeyFactory.NULL;
}
Entry[] tab = this.table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i], prev = null; e != null; e = e.next) {
Object entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[i] = e.next;
}
this.count--;
} else if (value.equals(entryValue)) {
return true;
} else {
prev = e;
}
}
}
return false;
}
public boolean containsKey(Object key) {
Entry<K, V>[] tab = this.table;
if (key != null) {
int hash = key.hashCode();
int index = (hash & 0x7fffffff) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key.equals(e.key)) {
return true;
} else {
prev = e;
}
}
} else {
for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[0] = e.next;
}
this.count--;
} else if (e.key == null) {
return true;
} else {
prev = e;
}
}
}
return false;
}
public V get(Object key) {
Entry<K, V>[] tab = this.table;
if (key != null) {
int hash = key.hashCode();
int index = (hash & 0x7fffffff) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
V entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
count--;
} else if (e.hash == hash && key.equals(e.key)) {
return (entryValue == KeyFactory.NULL) ? null : entryValue;
} else {
prev = e;
}
}
} else {
for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
V entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
}
else {
tab[0] = e.next;
}
this.count--;
} else if (e.key == null) {
return (entryValue == KeyFactory.NULL) ? null : entryValue;
} else {
prev = e;
}
}
}
return null;
}
/**
* Scans the contents of this map, removing all entries that have a
* cleared soft value.
*/
private void cleanup() {
Entry<K, V>[] tab = this.table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry<K, V> e = tab[i], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[i] = e.next;
}
this.count--;
} else {
prev = e;
}
}
}
}
/**
* Rehashes the contents of this map into a new HashMap instance
* with a larger capacity. This method is called automatically when the
* number of keys in this map exceeds its capacity and load factor.
*/
private void rehash() {
int oldCapacity = this.table.length;
Entry<K, V>[] oldMap = this.table;
int newCapacity = oldCapacity * 2 + 1;
Entry<K, V>[] newMap = new Entry[newCapacity];
this.modCount++;
this.threshold = (int)(newCapacity * this.loadFactor);
this.table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K, V> old = oldMap[i] ; old != null ; ) {
Entry<K, V> e = old;
old = old.next;
// Only copy entry if its value hasn"t been cleared.
if (e.get() == null) {
this.count--;
} else {
int index = (e.hash & 0x7fffffff) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}
}
public V put(K key, V value) {
if (value == null) {
value = (V) KeyFactory.NULL;
}
// Makes sure the key is not already in the HashMap.
Entry<K, V>[] tab = this.table;
int hash;
int index;
if (key != null) {
hash = key.hashCode();
index = (hash & 0x7fffffff) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
V entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key.equals(e.key)) {
e.setValue(value);
return (entryValue == KeyFactory.NULL) ? null : entryValue;
} else {
prev = e;
}
}
} else {
hash = 0;
index = 0;
for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
V entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[0] = e.next;
}
this.count--;
} else if (e.key == null) {
e.setValue(value);
return (entryValue == KeyFactory.NULL) ? null : entryValue;
} else {
prev = e;
}
}
}
this.modCount++;
if (this.count >= this.threshold) {
// Cleanup the table if the threshold is exceeded.
cleanup();
}
if (this.count >= this.threshold) {
// Rehash the table if the threshold is still exceeded.
rehash();
tab = this.table;
index = (hash & 0x7fffffff) % tab.length;
}
// Creates the new entry.
Entry<K, V> e = newEntry(hash, key, (V)value, tab[index]);
tab[index] = e;
this.count++;
return null;
}
public V remove(Object key) {
Entry<K, V>[] tab = this.table;
if (key != null) {
int hash = key.hashCode();
int index = (hash & 0x7fffffff) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
V entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key.equals(e.key)) {
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
e.setValue(null);
return (entryValue == KeyFactory.NULL) ? null : entryValue;
} else {
prev = e;
}
}
} else {
for (Entry<K, V> e = tab[0], prev = null; e != null; e = e.next) {
V entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[0] = e.next;
}
this.count--;
} else if (e.key == null) {
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[0] = e.next;
}
this.count--;
e.setValue(null);
return (entryValue == KeyFactory.NULL) ? null : entryValue;
} else {
prev = e;
}
}
}
return null;
}
public void putAll(Map<? extends K, ? extends V> t) {
Iterator i = t.entrySet().iterator();
while (i.hasNext()) {
Map.Entry<K, V> e = (Map.Entry<K, V>) i.next();
put(e.getKey(), e.getValue());
}
}
public void clear() {
Entry[] tab = this.table;
this.modCount++;
for (int index = tab.length; --index >= 0; ) {
tab[index] = null;
}
this.count = 0;
}
public Object clone() {
try {
ReferencedValueHashMap t = (ReferencedValueHashMap)super.clone();
t.table = new Entry[this.table.length];
for (int i = this.table.length ; i-- > 0 ; ) {
t.table[i] = (this.table[i] != null)
? (Entry)this.table[i].clone() : null;
}
t.keySet = null;
t.entrySet = null;
t.values = null;
t.modCount = 0;
return t;
} catch (CloneNotSupportedException e) {
// this shouldn"t happen, since we are Cloneable
throw new InternalError();
}
}
public Set<K> keySet() {
if (this.keySet == null) {
this.keySet = new AbstractSet<K>() {
public Iterator iterator() {
return createHashIterator(WeakIdentityMap.KEYS);
}
public int size() {
return ReferencedValueHashMap.this.count;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
if (o == null) {
if (ReferencedValueHashMap.this.containsKey(null)) {
ReferencedValueHashMap.this.remove(null);
return true;
} else {
return false;
}
} else {
return ReferencedValueHashMap.this.remove(o) != null;
}
}
public void clear() {
ReferencedValueHashMap.this.clear();
}
public String toString() {
return WeakIdentityMap.toString(this);
}
};
}
return this.keySet;
}
public Collection<V> values() {
if (this.values==null) {
this.values = new AbstractCollection<V>() {
public Iterator iterator() {
return createHashIterator(WeakIdentityMap.VALUES);
}
public int size() {
return ReferencedValueHashMap.this.count;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
ReferencedValueHashMap.this.clear();
}
public String toString() {
return WeakIdentityMap.toString(this);
}
};
}
return this.values;
}
public Set<Map.Entry<K, V>> entrySet() {
if (this.entrySet==null) {
this.entrySet = new AbstractSet<Map.Entry<K, V>>() {
public Iterator iterator() {
return createHashIterator(WeakIdentityMap.ENTRIES);
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
Map.Entry entry = (Map.Entry)o;
Object key = entry.getKey();
Entry[] tab = ReferencedValueHashMap.this.table;
int hash = key == null ? 0 : key.hashCode();
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
Object entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
ReferencedValueHashMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
ReferencedValueHashMap.this.count--;
} else if (e.hash == hash && e.equals(entry)) {
return true;
} else {
prev = e;
}
}
return false;
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
Map.Entry entry = (Map.Entry)o;
Object key = entry.getKey();
Entry[] tab = ReferencedValueHashMap.this.table;
int hash = key == null ? 0 : key.hashCode();
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
Object entryValue = e.get();
if (entryValue == null) {
// Clean up after a cleared Reference.
ReferencedValueHashMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
ReferencedValueHashMap.this.count--;
} else if (e.hash == hash && e.equals(entry)) {
ReferencedValueHashMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
ReferencedValueHashMap.this.count--;
e.setValue(null);
return true;
} else {
prev = e;
}
}
return false;
}
public int size() {
return ReferencedValueHashMap.this.count;
}
public void clear() {
ReferencedValueHashMap.this.clear();
}
public String toString() {
return WeakIdentityMap.toString(this);
}
};
}
return this.entrySet;
}
public String toString() {
// Cleanup stale entries first, so as not to allocate a larger than
// necessary StringBuffer.
cleanup();
return WeakIdentityMap.toString(this);
}
abstract Entry<K, V> newEntry(int hash, K key, V value, Entry<K, V> next);
private Iterator createHashIterator(int type) {
if (this.count == 0) {
return Collections.EMPTY_SET.iterator();
} else {
return new HashIterator(type);
}
}
/**
* Collision list entry.
*/
abstract static class Entry<K, V> implements Map.Entry<K, V> {
int hash;
K key;
Entry<K, V> next;
private Reference<V> value;
Entry(int hash, K key, V value, Entry<K, V> next) {
this.hash = hash;
this.key = key;
this.value = newReference(value);
this.next = next;
}
Entry(int hash, K key, Reference<V> value, Entry<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
// Map.Entry Ops
public K getKey() {
return this.key;
}
public V getValue() {
V value = this.value.get();
return value == KeyFactory.NULL ? null : value;
}
public V setValue(V value) {
V oldValue = getValue();
this.value = newReference(value == null ? ((V) KeyFactory.NULL) : value);
return oldValue;
}
public boolean equals(Object obj) {
if (!(obj instanceof Map.Entry)) {
return false;
}
return equals((Map.Entry)obj);
}
boolean equals(Map.Entry e) {
Object thisValue = get();
if (thisValue == null) {
return false;
} else if (thisValue == KeyFactory.NULL) {
thisValue = null;
}
return (this.key == null ? e.getKey() == null : this.key.equals(e.getKey())) &&
(thisValue == null ? e.getValue() == null : thisValue.equals(e.getValue()));
}
public int hashCode() {
return this.hash ^ get().hashCode();
}
public String toString() {
return this.key + "=" + getValue();
}
protected Object clone() {
return newEntry(this.hash, this.key, (Reference)this.value,
(this.next == null ? null : (Entry)this.next.clone()));
}
abstract Entry newEntry(int hash, K key, Reference<V> value, Entry<K, V> next);
abstract Reference<V> newReference(V value);
// Like getValue(), except does not convert NULL to null.
V get() {
return this.value.get();
}
}
private class HashIterator implements Iterator {
private final int type;
private final Entry[] table;
private int index;
// To ensure that the iterator doesn"t return cleared entries, keep a
// hard reference to the value. Its existence will prevent the soft
// value from being cleared.
private Object entryValue;
private Entry entry;
private Entry last;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
private int expectedModCount = ReferencedValueHashMap.this.modCount;
HashIterator(int type) {
this.table = ReferencedValueHashMap.this.table;
this.type = type;
this.index = table.length;
}
public boolean hasNext() {
while (this.entry == null || (this.entryValue = this.entry.get()) == null) {
if (this.entry != null) {
// Clean up after a cleared Reference.
remove(this.entry);
this.entry = this.entry.next;
}
if (this.entry == null) {
if (this.index <= 0) {
return false;
} else {
this.entry = this.table[--this.index];
}
}
}
return true;
}
public Object next() {
if (ReferencedValueHashMap.this.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (!hasNext()) {
throw new NoSuchElementException();
}
this.last = this.entry;
this.entry = this.entry.next;
return this.type == WeakIdentityMap.KEYS ? this.last.getKey() :
(this.type == WeakIdentityMap.VALUES ? this.last.getValue() : this.last);
}
public void remove() {
if (this.last == null) {
throw new IllegalStateException();
}
if (ReferencedValueHashMap.this.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
remove(this.last);
this.last = null;
}
private void remove(Entry toRemove) {
Entry[] tab = this.table;
int index = (toRemove.hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
if (e == toRemove) {
ReferencedValueHashMap.this.modCount++;
expectedModCount++;
if (prev == null) {
tab[index] = e.next;
} else {
prev.next = e.next;
}
ReferencedValueHashMap.this.count--;
return;
} else {
prev = e;
}
}
throw new ConcurrentModificationException();
}
}
}
class WeakIdentityMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable {
// Types of Iterators
static final int KEYS = 0;
static final int VALUES = 1;
static final int ENTRIES = 2;
/**
* Converts a collection to string, supporting collections that contain
* self references
*/
static String toString(Collection c) {
if (c.size() == 0) {
return "[]";
}
StringBuffer buf = new StringBuffer(32 * c.size());
buf.append("[");
Iterator it = c.iterator();
boolean hasNext = it.hasNext();
while (hasNext) {
Object obj = it.next();
buf.append(obj == c ? "(this Collection)" : obj);
if (hasNext) {
buf.append(", ");
}
}
buf.append("]");
return buf.toString();
}
/**
* Converts a map to string, supporting maps that contain self references
*/
static String toString(Map m) {
if (m.size() == 0) {
return "{}";
}
StringBuffer buf = new StringBuffer(32 * m.size());
buf.append("{");
Iterator it = m.entrySet().iterator();
boolean hasNext = it.hasNext();
while (hasNext) {
Map.Entry entry = (Map.Entry)it.next();
Object key = entry.getKey();
Object value = entry.getValue();
buf.append(key == m ? "(this Map)" : key)
.append("=")
.append(value == m ? "(this Map)" : value);
hasNext = it.hasNext();
if (hasNext) {
buf.append(",").append(" ");
}
}
buf.append("}");
return buf.toString();
}
private transient Entry<K, V>[] table;
private transient int count;
private int threshold;
private final float loadFactor;
private final ReferenceQueue<K> queue;
private transient volatile int modCount;
// Views
private transient Set<K> keySet;
private transient Set<Map.Entry<K, V>> entrySet;
private transient Collection<V> values;
public WeakIdentityMap(int initialCapacity, float loadFactor) {
if (initialCapacity <= 0) {
throw new IllegalArgumentException("Initial capacity must be greater than 0");
}
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Load factor must be greater than 0");
}
this.loadFactor = loadFactor;
this.table = new Entry[initialCapacity];
this.threshold = (int)(initialCapacity * loadFactor);
this.queue = new ReferenceQueue();
}
public WeakIdentityMap(int initialCapacity) {
this(initialCapacity, 0.75f);
}
public WeakIdentityMap() {
this(11, 0.75f);
}
public WeakIdentityMap(Map<? extends K, ? extends V> t) {
this(Math.max(2 * t.size(), 11), 0.75f);
putAll(t);
}
public int size() {
// Cleanup right before, to report a more accurate size.
cleanup();
return this.count;
}
public boolean isEmpty() {
return this.count == 0;
}
public boolean containsValue(Object value) {
Entry[] tab = this.table;
if (value == null) {
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[i] = e.next;
}
this.count--;
} else if (e.value == null) {
return true;
} else {
prev = e;
}
}
}
} else {
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[i] = e.next;
}
this.count--;
} else if (value.equals(e.value)) {
return true;
} else {
prev = e;
}
}
}
}
return false;
}
public boolean containsKey(Object key) {
if (key == null) {
key = KeyFactory.NULL;
}
Entry[] tab = this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key == entryKey) {
return true;
} else {
prev = e;
}
}
return false;
}
public V get(Object key) {
if (key == null) {
key = KeyFactory.NULL;
}
Entry<K, V>[] tab = this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key == entryKey) {
return e.value;
} else {
prev = e;
}
}
return null;
}
private void cleanup() {
// Cleanup after cleared References.
Entry[] tab = this.table;
ReferenceQueue queue = this.queue;
Reference ref;
while ((ref = queue.poll()) != null) {
// Since buckets are single-linked, traverse entire list and
// cleanup all cleared references in it.
int index = (((Entry) ref).hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
if (e.get() == null) {
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else {
prev = e;
}
}
}
}
private void rehash() {
int oldCapacity = this.table.length;
Entry[] oldMap = this.table;
int newCapacity = oldCapacity * 2 + 1;
if (newCapacity <= 0) {
// Overflow.
if ((newCapacity = Integer.MAX_VALUE) == oldCapacity) {
return;
}
}
Entry[] newMap = new Entry[newCapacity];
this.modCount++;
this.threshold = (int)(newCapacity * this.loadFactor);
this.table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry old = oldMap[i] ; old != null ; ) {
Entry e = old;
old = old.next;
// Only copy entry if its key hasn"t been cleared.
if (e.get() == null) {
this.count--;
} else {
int index = (e.hash & 0x7fffffff) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}
}
public V put(K key, V value) {
if (key == null) {
key = (K) KeyFactory.NULL;
}
cleanup();
// Make sure the key is not already in the WeakIdentityMap.
Entry[] tab = this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key == entryKey) {
Object old = e.value;
e.value = value;
return (V) old;
} else {
prev = e;
}
}
this.modCount++;
if (this.count >= this.threshold) {
// Rehash the table if the threshold is still exceeded.
rehash();
tab = this.table;
index = (hash & 0x7fffffff) % tab.length;
}
// Creates the new entry.
Entry e = new Entry(hash, key, this.queue, value, tab[index]);
tab[index] = e;
this.count++;
return null;
}
public V remove(Object key) {
if (key == null) {
key = KeyFactory.NULL;
}
Entry<K, V>[] tab = this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry<K, V> e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash && key == entryKey) {
this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
V oldValue = e.value;
e.value = null;
return oldValue;
} else {
prev = e;
}
}
return null;
}
public void putAll(Map<? extends K, ? extends V> t) {
Iterator i = t.entrySet().iterator();
while (i.hasNext()) {
Map.Entry e = (Map.Entry) i.next();
put((K) e.getKey(), (V) e.getValue());
}
}
public void clear() {
Entry[] tab = this.table;
this.modCount++;
for (int index = tab.length; --index >= 0; ) {
tab[index] = null;
}
this.count = 0;
}
public Object clone() {
try {
WeakIdentityMap t = (WeakIdentityMap)super.clone();
t.table = new Entry[this.table.length];
for (int i = this.table.length ; i-- > 0 ; ) {
t.table[i] = (this.table[i] != null)
? (Entry)this.table[i].copy(this.queue) : null;
}
t.keySet = null;
t.entrySet = null;
t.values = null;
t.modCount = 0;
return t;
}
catch (CloneNotSupportedException e) {
// this shouldn"t happen, since we are Cloneable
throw new InternalError();
}
}
public Set<K> keySet() {
if (this.keySet == null) {
this.keySet = new AbstractSet<K>() {
public Iterator iterator() {
return createHashIterator(KEYS);
}
public int size() {
return WeakIdentityMap.this.count;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return o == null ? false : WeakIdentityMap.this.remove(o) == o;
}
public void clear() {
WeakIdentityMap.this.clear();
}
public String toString() {
return WeakIdentityMap.this.toString(this);
}
};
}
return this.keySet;
}
public Collection<V> values() {
if (this.values==null) {
this.values = new AbstractCollection<V>() {
public Iterator<V> iterator() {
return createHashIterator(VALUES);
}
public int size() {
return WeakIdentityMap.this.count;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
WeakIdentityMap.this.clear();
}
public String toString() {
return WeakIdentityMap.this.toString(this);
}
};
}
return this.values;
}
public Set<Map.Entry<K, V>> entrySet() {
if (this.entrySet==null) {
this.entrySet = new AbstractSet<Map.Entry<K, V>>() {
public Iterator<Map.Entry<K, V>> iterator() {
return createHashIterator(ENTRIES);
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
Map.Entry entry = (Map.Entry)o;
Object key = entry.getKey();
Entry[] tab = WeakIdentityMap.this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
Object entryKey = e.get();
if (entryKey == null) {
// Clean up after a cleared Reference.
WeakIdentityMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
WeakIdentityMap.this.count--;
} else if (e.hash == hash && e.equals(entry)) {
return true;
} else {
prev = e;
}
}
return false;
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
Map.Entry entry = (Map.Entry)o;
Object key = entry.getKey();
Entry[] tab = WeakIdentityMap.this.table;
int hash = System.identityHashCode(key);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
if (e.get() == null) {
// Clean up after a cleared Reference.
WeakIdentityMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
WeakIdentityMap.this.count--;
} else if (e.hash == hash && e.equals(entry)) {
WeakIdentityMap.this.modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
WeakIdentityMap.this.count--;
e.value = null;
return true;
} else {
prev = e;
}
}
return false;
}
public int size() {
return WeakIdentityMap.this.count;
}
public void clear() {
WeakIdentityMap.this.clear();
}
public String toString() {
return WeakIdentityMap.toString(this);
}
};
}
return this.entrySet;
}
/**
* Gets the map as a String.
*
* @return a string version of the map
*/
public String toString() {
return toString(this);
}
private Iterator createHashIterator(int type) {
if (this.count == 0) {
return Collections.EMPTY_SET.iterator();
} else {
return new HashIterator(type);
}
}
/**
* WeakIdentityMap collision list entry.
*/
private static class Entry<K, V> extends WeakReference<K> implements Map.Entry<K, V> {
int hash;
V value;
Entry<K, V> next;
Entry(int hash, K key, ReferenceQueue<K> queue, V value, Entry<K, V> next) {
super(key, queue);
this.hash = hash;
this.value = value;
this.next = next;
}
public void clear() {
// Do nothing if reference is explicity cleared. This prevents
// backdoor modification of map entries.
}
public K getKey() {
K key = Entry.this.get();
return key == KeyFactory.NULL ? null : key;
}
public V getValue() {
return this.value;
}
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object obj) {
if (!(obj instanceof Map.Entry)) {
return false;
}
return equals((Map.Entry)obj);
}
boolean equals(Map.Entry<K, V> e) {
Object thisKey = get();
if (thisKey == null) {
return false;
} else if (thisKey == KeyFactory.NULL) {
thisKey = null;
}
return (thisKey == e.getKey()) &&
(this.value == null ? e.getValue() == null : this.value.equals(e.getValue()));
}
public int hashCode() {
return this.hash ^ (this.value == null ? 0 : this.value.hashCode());
}
public String toString() {
return getKey() + "=" + this.value;
}
protected Object copy(ReferenceQueue queue) {
return new Entry(this.hash, get(), queue, this.value,
(this.next == null ? null : (Entry)this.next.copy(queue)));
}
}
private class HashIterator implements Iterator {
private final int type;
private final Entry[] table;
private int index;
// To ensure that the iterator doesn"t return cleared entries, keep a
// hard reference to the key. Its existence will prevent the weak
// key from being cleared.
Object entryKey;
Entry entry;
Entry last;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
private int expectedModCount = WeakIdentityMap.this.modCount;
HashIterator(int type) {
this.table = WeakIdentityMap.this.table;
this.type = type;
this.index = table.length;
}
public boolean hasNext() {
while (this.entry == null || (this.entryKey = this.entry.get()) == null) {
if (this.entry != null) {
// Clean up after a cleared Reference.
remove(this.entry);
this.entry = this.entry.next;
}
else {
if (this.index <= 0) {
return false;
}
else {
this.entry = this.table[--this.index];
}
}
}
return true;
}
public Object next() {
if (WeakIdentityMap.this.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
}
if (!hasNext()) {
throw new NoSuchElementException();
}
this.last = this.entry;
this.entry = this.entry.next;
return this.type == KEYS ? this.last.getKey() :
(this.type == VALUES ? this.last.getValue() : this.last);
}
public void remove() {
if (this.last == null) {
throw new IllegalStateException();
}
if (WeakIdentityMap.this.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
}
remove(this.last);
this.last = null;
}
private void remove(Entry toRemove) {
Entry[] tab = this.table;
int index = (toRemove.hash & 0x7fffffff) % tab.length;
for (Entry e = tab[index], prev = null; e != null; e = e.next) {
if (e == toRemove) {
WeakIdentityMap.this.modCount++;
expectedModCount++;
if (prev == null) {
tab[index] = e.next;
} else {
prev.next = e.next;
}
WeakIdentityMap.this.count--;
return;
} else {
prev = e;
}
}
throw new ConcurrentModificationException();
}
public String toString() {
if (this.last != null) {
return "Iterator[" + this.last + "]";
} else {
return "Iterator[]";
}
}
}
} /*
- Copyright 2004 Brian S O"Neill
- 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.
- /
/**
- KeyFactory generates keys which can be hashed or compared for any kind of
- object including arrays, arrays of arrays, and null. All hashcode
- computations, equality tests, and ordering comparsisons fully recurse into
- arrays.
- @author Brian S O"Neill
- /
class KeyFactory {
static final Object NULL = new Comparable() {
public int compareTo(Object obj) {
return obj == this || obj == null ? 0 : 1;
}
};
public static Object createKey(boolean[] obj) {
return obj == null ? NULL : new BooleanArrayKey(obj);
}
public static Object createKey(byte[] obj) {
return obj == null ? NULL : new ByteArrayKey(obj);
}
public static Object createKey(char[] obj) {
return obj == null ? NULL : new CharArrayKey(obj);
}
public static Object createKey(double[] obj) {
return obj == null ? NULL : new DoubleArrayKey(obj);
}
public static Object createKey(float[] obj) {
return obj == null ? NULL : new FloatArrayKey(obj);
}
public static Object createKey(int[] obj) {
return obj == null ? NULL : new IntArrayKey(obj);
}
public static Object createKey(long[] obj) {
return obj == null ? NULL : new LongArrayKey(obj);
}
public static Object createKey(short[] obj) {
return obj == null ? NULL : new ShortArrayKey(obj);
}
public static Object createKey(Object[] obj) {
return obj == null ? NULL : new ObjectArrayKey(obj);
}
public static Object createKey(Object obj) {
if (obj == null) {
return NULL;
}
if (!obj.getClass().isArray()) {
return obj;
}
if (obj instanceof Object[]) {
return createKey((Object[])obj);
} else if (obj instanceof int[]) {
return createKey((int[])obj);
} else if (obj instanceof float[]) {
return createKey((float[])obj);
} else if (obj instanceof long[]) {
return createKey((long[])obj);
} else if (obj instanceof double[]) {
return createKey((double[])obj);
} else if (obj instanceof byte[]) {
return createKey((byte[])obj);
} else if (obj instanceof char[]) {
return createKey((char[])obj);
} else if (obj instanceof boolean[]) {
return createKey((boolean[])obj);
} else if (obj instanceof short[]) {
return createKey((short[])obj);
} else {
return obj;
}
}
static int hashCode(boolean[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + (a[i] ? 0 : 1);
}
return hash == 0 ? -1 : hash;
}
static int hashCode(byte[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + a[i];
}
return hash == 0 ? -1 : hash;
}
static int hashCode(char[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + a[i];
}
return hash == 0 ? -1 : hash;
}
static int hashCode(double[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
long v = Double.doubleToLongBits(a[i]);
hash = hash * 31 + (int)(v ^ v >>> 32);
}
return hash == 0 ? -1 : hash;
}
static int hashCode(float[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = hash * 31 + Float.floatToIntBits(a[i]);
}
return hash == 0 ? -1 : hash;
}
static int hashCode(int[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + a[i];
}
return hash == 0 ? -1 : hash;
}
static int hashCode(long[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
long v = a[i];
hash = hash * 31 + (int)(v ^ v >>> 32);
}
return hash == 0 ? -1 : hash;
}
static int hashCode(short[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = (hash << 1) + a[i];
}
return hash == 0 ? -1 : hash;
}
static int hashCode(Object[] a) {
int hash = 0;
for (int i = a.length; --i >= 0; ) {
hash = hash * 31 + hashCode(a[i]);
}
return hash == 0 ? -1 : hash;
}
// Compute object or array hashcode and recurses into arrays within.
static int hashCode(Object a) {
if (a == null) {
return -1;
}
if (!a.getClass().isArray()) {
return a.hashCode();
}
if (a instanceof Object[]) {
return hashCode((Object[])a);
} else if (a instanceof int[]) {
return hashCode((int[])a);
} else if (a instanceof float[]) {
return hashCode((float[])a);
} else if (a instanceof long[]) {
return hashCode((long[])a);
} else if (a instanceof double[]) {
return hashCode((double[])a);
} else if (a instanceof byte[]) {
return hashCode((byte[])a);
} else if (a instanceof char[]) {
return hashCode((char[])a);
} else if (a instanceof boolean[]) {
return hashCode((boolean[])a);
} else if (a instanceof short[]) {
return hashCode((short[])a);
} else {
int hash = a.getClass().hashCode();
return hash == 0 ? -1 : hash;
}
}
// Compares object arrays and recurses into arrays within.
static boolean equals(Object[] a, Object[] b) {
if (a == b) {
return true;
}
if (a == null || b == null) {
return false;
}
int i;
if ((i = a.length) != b.length) {
return false;
}
while (--i >= 0) {
if (!equals(a[i], b[i])) {
return false;
}
}
return true;
}
// Compares objects or arrays and recurses into arrays within.
static boolean equals(Object a, Object b) {
if (a == b) {
return true;
}
if (a == null || b == null) {
return false;
}
Class ac = a.getClass();
if (!(ac.isArray())) {
return a.equals(b);
}
if (ac != b.getClass()) {
return false;
}
if (a instanceof Object[]) {
return equals((Object[])a, (Object[])b);
} else if (a instanceof int[]) {
return Arrays.equals((int[])a, (int[])b);
} else if (a instanceof float[]) {
return Arrays.equals((float[])a, (float[])b);
} else if (a instanceof long[]) {
return Arrays.equals((long[])a, (long[])b);
} else if (a instanceof double[]) {
return Arrays.equals((double[])a, (double[])b);
} else if (a instanceof byte[]) {
return Arrays.equals((byte[])a, (byte[])b);
} else if (a instanceof char[]) {
return Arrays.equals((char[])a, (char[])b);
} else if (a instanceof boolean[]) {
return Arrays.equals((boolean[])a, (boolean[])b);
} else if (a instanceof short[]) {
return Arrays.equals((short[])a, (short[])b);
} else {
return a.equals(b);
}
}
static int compare(boolean[] a, boolean[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int av = a[i] ? 0 : 1;
int bv = b[i] ? 0 : 1;
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(byte[] a, byte[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
byte av = a[i];
byte bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(char[] a, char[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
char av = a[i];
char bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(double[] a, double[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int v = Double.rupare(a[i], b[i]);
if (v != 0) {
return v;
}
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(float[] a, float[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int v = Float.rupare(a[i], b[i]);
if (v != 0) {
return v;
}
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(int[] a, int[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int av = a[i];
int bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(long[] a, long[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
long av = a[i];
long bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
static int compare(short[] a, short[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
short av = a[i];
short bv = b[i];
return av < bv ? -1 : (av > bv ? 1 : 0);
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
// Compares object arrays and recurses into arrays within.
static int compare(Object[] a, Object[] b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
int length = Math.min(a.length, b.length);
for (int i=0; i<length; i++) {
int v = compare(a[i], b[i]);
if (v != 0) {
return v;
}
}
return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
}
// Compares objects or arrays and recurses into arrays within.
static int compare(Object a, Object b) {
if (a == b) {
return 0;
}
if (a == null) {
return 1;
}
if (b == null) {
return -1;
}
Class ac = a.getClass();
if (!(ac.isArray())) {
return ((Comparable)a).rupareTo(b);
}
if (ac != b.getClass()) {
throw new ClassCastException();
}
if (a instanceof Object[]) {
return compare((Object[])a, (Object[])b);
} else if (a instanceof int[]) {
return compare((int[])a, (int[])b);
} else if (a instanceof float[]) {
return compare((float[])a, (float[])b);
} else if (a instanceof long[]) {
return compare((long[])a, (long[])b);
} else if (a instanceof double[]) {
return compare((double[])a, (double[])b);
} else if (a instanceof byte[]) {
return compare((byte[])a, (byte[])b);
} else if (a instanceof char[]) {
return compare((char[])a, (char[])b);
} else if (a instanceof boolean[]) {
return compare((boolean[])a, (boolean[])b);
} else if (a instanceof short[]) {
return compare((short[])a, (short[])b);
} else {
throw new ClassCastException();
}
}
protected KeyFactory() {
}
private static interface ArrayKey extends Comparable, java.io.Serializable {
int hashCode();
boolean equals(Object obj);
int compareTo(Object obj);
}
private static class BooleanArrayKey implements ArrayKey {
protected final boolean[] mArray;
private transient int mHash;
BooleanArrayKey(boolean[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof BooleanArrayKey ?
Arrays.equals(mArray, ((BooleanArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((BooleanArrayKey) obj).mArray);
}
}
private static class ByteArrayKey implements ArrayKey {
protected final byte[] mArray;
private transient int mHash;
ByteArrayKey(byte[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof ByteArrayKey ?
Arrays.equals(mArray, ((ByteArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((ByteArrayKey) obj).mArray);
}
}
private static class CharArrayKey implements ArrayKey {
protected final char[] mArray;
private transient int mHash;
CharArrayKey(char[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof CharArrayKey ?
Arrays.equals(mArray, ((CharArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((CharArrayKey) obj).mArray);
}
}
private static class DoubleArrayKey implements ArrayKey {
protected final double[] mArray;
private transient int mHash;
DoubleArrayKey(double[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof DoubleArrayKey ?
Arrays.equals(mArray, ((DoubleArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((DoubleArrayKey) obj).mArray);
}
}
private static class FloatArrayKey implements ArrayKey {
protected final float[] mArray;
private transient int mHash;
FloatArrayKey(float[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof FloatArrayKey ?
Arrays.equals(mArray, ((FloatArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((FloatArrayKey) obj).mArray);
}
}
private static class IntArrayKey implements ArrayKey {
protected final int[] mArray;
private transient int mHash;
IntArrayKey(int[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof IntArrayKey ?
Arrays.equals(mArray, ((IntArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((IntArrayKey) obj).mArray);
}
}
private static class LongArrayKey implements ArrayKey {
protected final long[] mArray;
private transient int mHash;
LongArrayKey(long[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof LongArrayKey ?
Arrays.equals(mArray, ((LongArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((LongArrayKey) obj).mArray);
}
}
private static class ShortArrayKey implements ArrayKey {
protected final short[] mArray;
private transient int mHash;
ShortArrayKey(short[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof ShortArrayKey ?
Arrays.equals(mArray, ((ShortArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((ShortArrayKey) obj).mArray);
}
}
private static class ObjectArrayKey implements ArrayKey {
protected final Object[] mArray;
private transient int mHash;
ObjectArrayKey(Object[] array) {
mArray = array;
}
public int hashCode() {
int hash = mHash;
return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
}
public boolean equals(Object obj) {
return this == obj ? true :
(obj instanceof ObjectArrayKey ?
KeyFactory.equals(mArray, ((ObjectArrayKey) obj).mArray) : false);
}
public int compareTo(Object obj) {
return compare(mArray, ((ObjectArrayKey) obj).mArray);
}
}
}
</source>
