Java/Collections Data Structure/Soft Map

Материал из Java эксперт
Версия от 10:23, 1 июня 2010; Admin (обсуждение | вклад) (1 версия)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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>