Soft Valued HashMap : Soft Map « Collections Data Structure « Java

Java
1. 2D Graphics GUI
2. 3D
3. Advanced Graphics
4. Ant
5. Apache Common
6. Chart
7. Class
8. Collections Data Structure
9. Data Type
10. Database SQL JDBC
11. Design Pattern
12. Development Class
13. EJB3
14. Email
15. Event
16. File Input Output
17. Game
18. Generics
19. GWT
20. Hibernate
21. I18N
22. J2EE
23. J2ME
24. JDK 6
25. JNDI LDAP
26. JPA
27. JSP
28. JSTL
29. Language Basics
30. Network Protocol
31. PDF RTF
32. Reflection
33. Regular Expressions
34. Scripting
35. Security
36. Servlets
37. Spring
38. Swing Components
39. Swing JFC
40. SWT JFace Eclipse
41. Threads
42. Tiny Application
43. Velocity
44. Web Services SOA
45. XML
Java Tutorial
Java Source Code / Java Documentation
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java » Collections Data Structure » Soft MapScreenshots 
Soft Valued HashMap
 
/*
 *  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 <tt>0.75</tt>.
     *
     @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 <tt>0.75</tt>.
     */
    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 <tt>0.75</tt>.
     */
    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 <= || 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 <tt>0.75</tt>.
     *
     @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 <tt>0.75</tt>.
     */
    public ReferencedValueHashMap() {
        this(110.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 <tt>0.75</tt>.
     */
    public ReferencedValueHashMap(Map<? extends K, ? extends V> t) {
        this(Math.max(* 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-- > ;) {
            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.NULLnull : 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.NULLnull : 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-- > ;) {
            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 <tt>HashMap</tt> 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 * 1;
        Entry<K, V>[] newMap = new Entry[newCapacity];

        this.modCount++;
        this.threshold = (int)(newCapacity * this.loadFactor);
        this.table = newMap;

        for (int i = oldCapacity ; i-- > ;) {
            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 = (VKeyFactory.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.NULLnull : 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.NULLnull : 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.NULLnull : 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.NULLnull : 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[indexnull;
        }
        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-- > ) {
                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 (!(instanceof Map.Entry)) {
                        return false;
                    }
                    Map.Entry entry = (Map.Entry)o;
                    Object key = entry.getKey();

                    Entry[] tab = ReferencedValueHashMap.this.table;
                    int hash = key == null : 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 (!(instanceof Map.Entry)) {
                        return false;
                    }
                    Map.Entry entry = (Map.Entry)o;
                    Object key = entry.getKey();
                    Entry[] tab = ReferencedValueHashMap.this.table;
                    int hash = key == null : 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 ((VKeyFactory.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 <= || 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(110.75f);
   }

   public WeakIdentityMap(Map<? extends K, ? extends V> t) {
       this(Math.max(* 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-- > ;) {
               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-- > ;) {
               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 = (((Entryref).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 * 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-- > ;) {
           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 = (KKeyFactory.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 (Vold;
           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.Entryi.next();
           put((Ke.getKey()(Ve.getValue());
       }
   }

   public void clear() {
       Entry[] tab = this.table;
       this.modCount++;
       for (int index = tab.length; --index >= 0) {
           tab[indexnull;
       }
       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-- > ) {
               t.table[i(this.table[i!= null
                   (Entry)this.table[i].copy(this.queuenull;
           }
           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 (!(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 (!(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 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 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[i1);
       }
       return hash == ? -: hash;
   }

   static int hashCode(byte[] a) {
       int hash = 0;
       for (int i = a.length; --i >= 0) {
           hash = (hash << 1+ a[i];
       }
       return hash == ? -: hash;
   }

   static int hashCode(char[] a) {
       int hash = 0;
       for (int i = a.length; --i >= 0) {
           hash = (hash << 1+ a[i];
       }
       return hash == ? -: 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 == ? -: 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 == ? -: hash;
   }

   static int hashCode(int[] a) {
       int hash = 0;
       for (int i = a.length; --i >= 0) {
           hash = (hash << 1+ a[i];
       }
       return hash == ? -: 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 == ? -: hash;
   }

   static int hashCode(short[] a) {
       int hash = 0;
       for (int i = a.length; --i >= 0) {
           hash = (hash << 1+ a[i];
       }
       return hash == ? -: hash;
   }

   static int hashCode(Object[] a) {
       int hash = 0;
       for (int i = a.length; --i >= 0) {
           hash = hash * 31 + hashCode(a[i]);
       }
       return hash == ? -: 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 (instanceof Object[]) {
           return hashCode((Object[])a);
       else if (instanceof int[]) {
           return hashCode((int[])a);
       else if (instanceof float[]) {
           return hashCode((float[])a);
       else if (instanceof long[]) {
           return hashCode((long[])a);
       else if (instanceof double[]) {
           return hashCode((double[])a);
       else if (instanceof byte[]) {
           return hashCode((byte[])a);
       else if (instanceof char[]) {
           return hashCode((char[])a);
       else if (instanceof boolean[]) {
           return hashCode((boolean[])a);
       else if (instanceof short[]) {
           return hashCode((short[])a);
       else {
           int hash = a.getClass().hashCode();
           return hash == ? -: 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 (instanceof Object[]) {
           return equals((Object[])a, (Object[])b);
       else if (instanceof int[]) {
           return Arrays.equals((int[])a, (int[])b);
       else if (instanceof float[]) {
           return Arrays.equals((float[])a, (float[])b);
       else if (instanceof long[]) {
           return Arrays.equals((long[])a, (long[])b);
       else if (instanceof double[]) {
           return Arrays.equals((double[])a, (double[])b);
       else if (instanceof byte[]) {
           return Arrays.equals((byte[])a, (byte[])b);
       else if (instanceof char[]) {
           return Arrays.equals((char[])a, (char[])b);
       else if (instanceof boolean[]) {
           return Arrays.equals((boolean[])a, (boolean[])b);
       else if (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[i1;
           int bv = b[i1;
           return av < bv ? -(av > bv ? 0);
       }
       return a.length < b.length ? -(a.length > b.length ? 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 ? -(av > bv ? 0);
       }
       return a.length < b.length ? -(a.length > b.length ? 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 ? -(av > bv ? 0);
       }
       return a.length < b.length ? -(a.length > b.length ? 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.compare(a[i], b[i]);
           if (v != 0) {
               return v;
           }
       }
       return a.length < b.length ? -(a.length > b.length ? 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.compare(a[i], b[i]);
           if (v != 0) {
               return v;
           }
       }
       return a.length < b.length ? -(a.length > b.length ? 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 ? -(av > bv ? 0);
       }
       return a.length < b.length ? -(a.length > b.length ? 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 ? -(av > bv ? 0);
       }
       return a.length < b.length ? -(a.length > b.length ? 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 ? -(av > bv ? 0);
       }
       return a.length < b.length ? -(a.length > b.length ? 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 ? -(a.length > b.length ? 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).compareTo(b);
       }
       if (ac != b.getClass()) {
           throw new ClassCastException();
       }
       if (instanceof Object[]) {
           return compare((Object[])a, (Object[])b);
       else if (instanceof int[]) {
           return compare((int[])a, (int[])b);
       else if (instanceof float[]) {
           return compare((float[])a, (float[])b);
       else if (instanceof long[]) {
           return compare((long[])a, (long[])b);
       else if (instanceof double[]) {
           return compare((double[])a, (double[])b);
       else if (instanceof byte[]) {
           return compare((byte[])a, (byte[])b);
       else if (instanceof char[]) {
           return compare((char[])a, (char[])b);
       else if (instanceof boolean[]) {
           return compare((boolean[])a, (boolean[])b);
       else if (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 == ? mHash = KeyFactory.hashCode(mArray: hash;
       }

       public boolean equals(Object obj) {
           return this == obj ? true :
               (obj instanceof BooleanArrayKey ?
                Arrays.equals(mArray, ((BooleanArrayKeyobj).mArrayfalse);
       }

       public int compareTo(Object obj) {
           return compare(mArray, ((BooleanArrayKeyobj).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 == ? mHash = KeyFactory.hashCode(mArray: hash;
       }

       public boolean equals(Object obj) {
           return this == obj ? true :
               (obj instanceof ByteArrayKey ?
                Arrays.equals(mArray, ((ByteArrayKeyobj).mArrayfalse);
       }

       public int compareTo(Object obj) {
           return compare(mArray, ((ByteArrayKeyobj).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 == ? mHash = KeyFactory.hashCode(mArray: hash;
       }

       public boolean equals(Object obj) {
           return this == obj ? true :
               (obj instanceof CharArrayKey ?
                Arrays.equals(mArray, ((CharArrayKeyobj).mArrayfalse);
       }

       public int compareTo(Object obj) {
           return compare(mArray, ((CharArrayKeyobj).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 == ? mHash = KeyFactory.hashCode(mArray: hash;
       }

       public boolean equals(Object obj) {
           return this == obj ? true :
               (obj instanceof DoubleArrayKey ?
                Arrays.equals(mArray, ((DoubleArrayKeyobj).mArrayfalse);
       }

       public int compareTo(Object obj) {
           return compare(mArray, ((DoubleArrayKeyobj).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 == ? mHash = KeyFactory.hashCode(mArray: hash;
       }

       public boolean equals(Object obj) {
           return this == obj ? true :
               (obj instanceof FloatArrayKey ?
                Arrays.equals(mArray, ((FloatArrayKeyobj).mArrayfalse);
       }

       public int compareTo(Object obj) {
           return compare(mArray, ((FloatArrayKeyobj).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 == ? mHash = KeyFactory.hashCode(mArray: hash;
       }

       public boolean equals(Object obj) {
           return this == obj ? true :
               (obj instanceof IntArrayKey ?
                Arrays.equals(mArray, ((IntArrayKeyobj).mArrayfalse);
       }

       public int compareTo(Object obj) {
           return compare(mArray, ((IntArrayKeyobj).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 == ? mHash = KeyFactory.hashCode(mArray: hash;
       }

       public boolean equals(Object obj) {
           return this == obj ? true :
               (obj instanceof LongArrayKey ?
                Arrays.equals(mArray, ((LongArrayKeyobj).mArrayfalse);
       }

       public int compareTo(Object obj) {
           return compare(mArray, ((LongArrayKeyobj).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 == ? mHash = KeyFactory.hashCode(mArray: hash;
       }

       public boolean equals(Object obj) {
           return this == obj ? true :
               (obj instanceof ShortArrayKey ?
                Arrays.equals(mArray, ((ShortArrayKeyobj).mArrayfalse);
       }

       public int compareTo(Object obj) {
           return compare(mArray, ((ShortArrayKeyobj).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 == ? mHash = KeyFactory.hashCode(mArray: hash;
       }

       public boolean equals(Object obj) {
           return this == obj ? true :
               (obj instanceof ObjectArrayKey ?
                KeyFactory.equals(mArray, ((ObjectArrayKeyobj).mArrayfalse);
       }

       public int compareTo(Object obj) {
           return compare(mArray, ((ObjectArrayKeyobj).mArray);
       }
   }
}

   
  
Related examples in the same category
1. Soft HashMap
2. A java.util.Map implementation with soft values
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.