Java/Collections Data Structure/Soft Map — различия между версиями
Admin (обсуждение | вклад) м (1 версия) |
|
(нет различий)
|
Текущая версия на 10:23, 1 июня 2010
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>