001    /*
002     *  Licensed to the Apache Software Foundation (ASF) under one or more
003     *  contributor license agreements.  See the NOTICE file distributed with
004     *  this work for additional information regarding copyright ownership.
005     *  The ASF licenses this file to You under the Apache License, Version 2.0
006     *  (the "License"); you may not use this file except in compliance with
007     *  the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     *  Unless required by applicable law or agreed to in writing, software
012     *  distributed under the License is distributed on an "AS IS" BASIS,
013     *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     *  See the License for the specific language governing permissions and
015     *  limitations under the License.
016     */
017    package org.apache.commons.collections;
018    
019    import java.io.IOException;
020    import java.io.ObjectInputStream;
021    import java.io.ObjectOutputStream;
022    import java.lang.ref.Reference;
023    import java.lang.ref.ReferenceQueue;
024    import java.lang.ref.SoftReference;
025    import java.lang.ref.WeakReference;
026    import java.util.AbstractCollection;
027    import java.util.AbstractMap;
028    import java.util.AbstractSet;
029    import java.util.ArrayList;
030    import java.util.Arrays;
031    import java.util.Collection;
032    import java.util.ConcurrentModificationException;
033    import java.util.Iterator;
034    import java.util.Map;
035    import java.util.NoSuchElementException;
036    import java.util.Set;
037    
038    import org.apache.commons.collections.keyvalue.DefaultMapEntry;
039    
040    /**
041     *  Hash-based {@link Map} implementation that allows
042     *  mappings to be removed by the garbage collector.<p>
043     *
044     *  When you construct a <code>ReferenceMap</code>, you can 
045     *  specify what kind of references are used to store the
046     *  map's keys and values.  If non-hard references are 
047     *  used, then the garbage collector can remove mappings
048     *  if a key or value becomes unreachable, or if the 
049     *  JVM's memory is running low.  For information on how
050     *  the different reference types behave, see
051     *  {@link Reference}.<p>
052     *
053     *  Different types of references can be specified for keys
054     *  and values.  The keys can be configured to be weak but
055     *  the values hard, in which case this class will behave
056     *  like a <a href="http://java.sun.com/j2se/1.4/docs/api/java/util/WeakHashMap.html">
057     *  <code>WeakHashMap</code></a>.  However, you
058     *  can also specify hard keys and weak values, or any other
059     *  combination.  The default constructor uses hard keys
060     *  and soft values, providing a memory-sensitive cache.<p>
061     *
062     *  The algorithms used are basically the same as those
063     *  in {@link java.util.HashMap}.  In particular, you 
064     *  can specify a load factor and capacity to suit your
065     *  needs.  All optional {@link Map} operations are 
066     *  supported.<p>
067     *
068     *  However, this {@link Map} implementation does <I>not</I>
069     *  allow null elements.  Attempting to add a null key or
070     *  or a null value to the map will raise a 
071     *  <code>NullPointerException</code>.<p>
072     *
073     *  As usual, this implementation is not synchronized.  You
074     *  can use {@link java.util.Collections#synchronizedMap} to 
075     *  provide synchronized access to a <code>ReferenceMap</code>.
076     *
077     * @see java.lang.ref.Reference
078     * 
079     * @deprecated Moved to map subpackage. Due to be removed in v4.0.
080     * @since Commons Collections 2.1
081     * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
082     * 
083     * @author Paul Jack
084     */
085    public class ReferenceMap extends AbstractMap {
086    
087        /**
088         *  For serialization.
089         */
090        private static final long serialVersionUID = -3370601314380922368L;
091    
092    
093        /**
094         *  Constant indicating that hard references should be used.
095         */
096        final public static int HARD = 0;
097    
098    
099        /**
100         *  Constant indicating that soft references should be used.
101         */
102        final public static int SOFT = 1;
103    
104    
105        /**
106         *  Constant indicating that weak references should be used.
107         */
108        final public static int WEAK = 2;
109    
110    
111        // --- serialized instance variables:
112    
113    
114        /**
115         *  The reference type for keys.  Must be HARD, SOFT, WEAK.
116         *  Note: I originally marked this field as final, but then this class
117         *   didn't compile under JDK1.2.2.
118         *  @serial
119         */
120        private int keyType;
121    
122    
123        /**
124         *  The reference type for values.  Must be HARD, SOFT, WEAK.
125         *  Note: I originally marked this field as final, but then this class
126         *   didn't compile under JDK1.2.2.
127         *  @serial
128         */
129        private int valueType;
130    
131    
132        /**
133         *  The threshold variable is calculated by multiplying
134         *  table.length and loadFactor.  
135         *  Note: I originally marked this field as final, but then this class
136         *   didn't compile under JDK1.2.2.
137         *  @serial
138         */
139        private float loadFactor;
140        
141        /**
142         * Should the value be automatically purged when the associated key has been collected?
143         */
144        private boolean purgeValues = false;
145    
146    
147        // -- Non-serialized instance variables
148    
149        /**
150         *  ReferenceQueue used to eliminate stale mappings.
151         *  See purge.
152         */
153        private transient ReferenceQueue queue = new ReferenceQueue();
154    
155    
156        /**
157         *  The hash table.  Its length is always a power of two.  
158         */
159        private transient Entry[] table;
160    
161    
162        /**
163         *  Number of mappings in this map.
164         */
165        private transient int size;
166    
167    
168        /**
169         *  When size reaches threshold, the map is resized.  
170         *  See resize().
171         */
172        private transient int threshold;
173    
174    
175        /**
176         *  Number of times this map has been modified.
177         */
178        private transient volatile int modCount;
179    
180    
181        /**
182         *  Cached key set.  May be null if key set is never accessed.
183         */
184        private transient Set keySet;
185    
186    
187        /**
188         *  Cached entry set.  May be null if entry set is never accessed.
189         */
190        private transient Set entrySet;
191    
192    
193        /**
194         *  Cached values.  May be null if values() is never accessed.
195         */
196        private transient Collection values;
197    
198    
199        /**
200         *  Constructs a new <code>ReferenceMap</code> that will
201         *  use hard references to keys and soft references to values.
202         */
203        public ReferenceMap() {
204            this(HARD, SOFT);
205        }
206    
207        /**
208         *  Constructs a new <code>ReferenceMap</code> that will
209         *  use the specified types of references.
210         *
211         *  @param keyType  the type of reference to use for keys;
212         *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
213         *  @param valueType  the type of reference to use for values;
214         *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
215         *  @param purgeValues should the value be automatically purged when the 
216         *   key is garbage collected 
217         */
218        public ReferenceMap(int keyType, int valueType, boolean purgeValues) {
219            this(keyType, valueType);
220            this.purgeValues = purgeValues;
221        }
222    
223        /**
224         *  Constructs a new <code>ReferenceMap</code> that will
225         *  use the specified types of references.
226         *
227         *  @param keyType  the type of reference to use for keys;
228         *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
229         *  @param valueType  the type of reference to use for values;
230         *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
231         */
232        public ReferenceMap(int keyType, int valueType) {
233            this(keyType, valueType, 16, 0.75f);
234        }
235    
236        /**
237         *  Constructs a new <code>ReferenceMap</code> with the
238         *  specified reference types, load factor and initial
239         *  capacity.
240         *
241         *  @param keyType  the type of reference to use for keys;
242         *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
243         *  @param valueType  the type of reference to use for values;
244         *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
245         *  @param capacity  the initial capacity for the map
246         *  @param loadFactor  the load factor for the map
247         *  @param purgeValues should the value be automatically purged when the 
248         *   key is garbage collected 
249         */
250        public ReferenceMap(
251                            int keyType, 
252                            int valueType, 
253                            int capacity, 
254                            float loadFactor, 
255                            boolean purgeValues) {
256            this(keyType, valueType, capacity, loadFactor);
257            this.purgeValues = purgeValues;
258        }
259    
260        /**
261         *  Constructs a new <code>ReferenceMap</code> with the
262         *  specified reference types, load factor and initial
263         *  capacity.
264         *
265         *  @param keyType  the type of reference to use for keys;
266         *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
267         *  @param valueType  the type of reference to use for values;
268         *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
269         *  @param capacity  the initial capacity for the map
270         *  @param loadFactor  the load factor for the map
271         */
272        public ReferenceMap(int keyType, int valueType, int capacity, float loadFactor) {
273            super();
274    
275            verify("keyType", keyType);
276            verify("valueType", valueType);
277    
278            if (capacity <= 0) {
279                throw new IllegalArgumentException("capacity must be positive");
280            }
281            if ((loadFactor <= 0.0f) || (loadFactor >= 1.0f)) {
282                throw new IllegalArgumentException("Load factor must be greater than 0 and less than 1.");
283            }
284    
285            this.keyType = keyType;
286            this.valueType = valueType;
287    
288            int v = 1;
289            while (v < capacity) v *= 2;
290    
291            this.table = new Entry[v];
292            this.loadFactor = loadFactor;
293            this.threshold = (int)(v * loadFactor);
294        }
295    
296    
297        // used by constructor
298        private static void verify(String name, int type) {
299            if ((type < HARD) || (type > WEAK)) {
300                throw new IllegalArgumentException(name + 
301                   " must be HARD, SOFT, WEAK.");
302            }
303        }
304    
305    
306        /**
307         *  Writes this object to the given output stream.
308         *
309         *  @param out  the output stream to write to
310         *  @throws IOException  if the stream raises it
311         */
312        private void writeObject(ObjectOutputStream out) throws IOException {
313            out.defaultWriteObject();
314            out.writeInt(table.length);
315    
316            // Have to use null-terminated list because size might shrink
317            // during iteration
318    
319            for (Iterator iter = entrySet().iterator(); iter.hasNext();) {
320                Map.Entry entry = (Map.Entry)iter.next();
321                out.writeObject(entry.getKey());
322                out.writeObject(entry.getValue());
323            }
324            out.writeObject(null);
325        }
326    
327    
328        /**
329         *  Reads the contents of this object from the given input stream.
330         *
331         *  @param inp  the input stream to read from
332         *  @throws IOException  if the stream raises it
333         *  @throws ClassNotFoundException  if the stream raises it
334         */
335        private void readObject(ObjectInputStream inp) throws IOException, ClassNotFoundException {
336            inp.defaultReadObject();
337            table = new Entry[inp.readInt()];
338            threshold = (int)(table.length * loadFactor);
339            queue = new ReferenceQueue();
340            Object key = inp.readObject();
341            while (key != null) {
342                Object value = inp.readObject();
343                put(key, value);
344                key = inp.readObject();
345            }
346        }
347    
348    
349        /**
350         *  Constructs a reference of the given type to the given 
351         *  referent.  The reference is registered with the queue
352         *  for later purging.
353         *
354         *  @param type  HARD, SOFT or WEAK
355         *  @param referent  the object to refer to
356         *  @param hash  the hash code of the <I>key</I> of the mapping;
357         *    this number might be different from referent.hashCode() if
358         *    the referent represents a value and not a key
359         */
360        private Object toReference(int type, Object referent, int hash) {
361            switch (type) {
362                case HARD: return referent;
363                case SOFT: return new SoftRef(hash, referent, queue);
364                case WEAK: return new WeakRef(hash, referent, queue);
365                default: throw new Error();
366            }
367        }
368    
369    
370        /**
371         *  Returns the entry associated with the given key.
372         *
373         *  @param key  the key of the entry to look up
374         *  @return  the entry associated with that key, or null
375         *    if the key is not in this map
376         */
377        private Entry getEntry(Object key) {
378            if (key == null) return null;
379            int hash = key.hashCode();
380            int index = indexFor(hash);
381            for (Entry entry = table[index]; entry != null; entry = entry.next) {
382                if ((entry.hash == hash) && key.equals(entry.getKey())) {
383                    return entry;
384                }
385            }
386            return null;
387        }
388    
389    
390        /**
391         *  Converts the given hash code into an index into the
392         *  hash table.
393         */
394        private int indexFor(int hash) {
395            // mix the bits to avoid bucket collisions...
396            hash += ~(hash << 15);
397            hash ^= (hash >>> 10);
398            hash += (hash << 3);
399            hash ^= (hash >>> 6);
400            hash += ~(hash << 11);
401            hash ^= (hash >>> 16);
402            return hash & (table.length - 1);
403        }
404    
405    
406    
407        /**
408         *  Resizes this hash table by doubling its capacity.
409         *  This is an expensive operation, as entries must
410         *  be copied from the old smaller table to the new 
411         *  bigger table.
412         */
413        private void resize() {
414            Entry[] old = table;
415            table = new Entry[old.length * 2];
416    
417            for (int i = 0; i < old.length; i++) {
418                Entry next = old[i];
419                while (next != null) {
420                    Entry entry = next;
421                    next = next.next;
422                    int index = indexFor(entry.hash);
423                    entry.next = table[index];
424                    table[index] = entry;
425                }
426                old[i] = null;
427            }
428            threshold = (int)(table.length * loadFactor);
429        }
430    
431    
432    
433        /**
434         * Purges stale mappings from this map.
435         * <p>
436         * Ordinarily, stale mappings are only removed during
437         * a write operation, although this method is called for both
438         * read and write operations to maintain a consistent state.
439         * <p>
440         * Note that this method is not synchronized!  Special
441         * care must be taken if, for instance, you want stale
442         * mappings to be removed on a periodic basis by some
443         * background thread.
444         */
445        private void purge() {
446            Reference ref = queue.poll();
447            while (ref != null) {
448                purge(ref);
449                ref = queue.poll();
450            }
451        }
452    
453    
454        private void purge(Reference ref) {
455            // The hashCode of the reference is the hashCode of the
456            // mapping key, even if the reference refers to the 
457            // mapping value...
458            int hash = ref.hashCode();
459            int index = indexFor(hash);
460            Entry previous = null;
461            Entry entry = table[index];
462            while (entry != null) {
463                if (entry.purge(ref)) {
464                    if (previous == null) table[index] = entry.next;
465                    else previous.next = entry.next;
466                    this.size--;
467                    return;
468                }
469                previous = entry;
470                entry = entry.next;
471            }
472    
473        }
474    
475    
476        /**
477         *  Returns the size of this map.
478         *
479         *  @return  the size of this map
480         */
481        public int size() {
482            purge();
483            return size;
484        }
485    
486    
487        /**
488         *  Returns <code>true</code> if this map is empty.
489         *
490         *  @return <code>true</code> if this map is empty
491         */
492        public boolean isEmpty() {
493            purge();
494            return size == 0;
495        }
496    
497    
498        /**
499         *  Returns <code>true</code> if this map contains the given key.
500         *
501         *  @return true if the given key is in this map
502         */
503        public boolean containsKey(Object key) {
504            purge();
505            Entry entry = getEntry(key);
506            if (entry == null) return false;
507            return entry.getValue() != null;
508        }
509    
510    
511        /**
512         *  Returns the value associated with the given key, if any.
513         *
514         *  @return the value associated with the given key, or <code>null</code>
515         *   if the key maps to no value
516         */
517        public Object get(Object key) {
518            purge();
519            Entry entry = getEntry(key);
520            if (entry == null) return null;
521            return entry.getValue();
522        }
523    
524    
525        /**
526         *  Associates the given key with the given value.<p>
527         *  Neither the key nor the value may be null.
528         *
529         *  @param key  the key of the mapping
530         *  @param value  the value of the mapping
531         *  @return  the last value associated with that key, or 
532         *   null if no value was associated with the key
533         *  @throws NullPointerException if either the key or value
534         *   is null
535         */
536        public Object put(Object key, Object value) {
537            if (key == null) throw new NullPointerException("null keys not allowed");
538            if (value == null) throw new NullPointerException("null values not allowed");
539    
540            purge();
541            if (size + 1 > threshold) resize();
542    
543            int hash = key.hashCode();
544            int index = indexFor(hash);
545            Entry entry = table[index];
546            while (entry != null) {
547                if ((hash == entry.hash) && key.equals(entry.getKey())) {
548                    Object result = entry.getValue();
549                    entry.setValue(value);
550                    return result;
551                }
552                entry = entry.next;
553            }
554            this.size++; 
555            modCount++;
556            key = toReference(keyType, key, hash);
557            value = toReference(valueType, value, hash);
558            table[index] = new Entry(key, hash, value, table[index]);
559            return null;
560        }
561    
562    
563        /**
564         *  Removes the key and its associated value from this map.
565         *
566         *  @param key  the key to remove
567         *  @return the value associated with that key, or null if
568         *   the key was not in the map
569         */
570        public Object remove(Object key) {
571            if (key == null) return null;
572            purge();
573            int hash = key.hashCode();
574            int index = indexFor(hash);
575            Entry previous = null;
576            Entry entry = table[index];
577            while (entry != null) {
578                if ((hash == entry.hash) && key.equals(entry.getKey())) {
579                    if (previous == null) table[index] = entry.next;
580                    else previous.next = entry.next;
581                    this.size--;
582                    modCount++;
583                    return entry.getValue();
584                }
585                previous = entry;
586                entry = entry.next;
587            }
588            return null;
589        }
590    
591    
592        /**
593         *  Clears this map.
594         */
595        public void clear() {
596            Arrays.fill(table, null);
597            size = 0;
598            while (queue.poll() != null); // drain the queue
599        }
600    
601    
602        /**
603         *  Returns a set view of this map's entries.
604         *
605         *  @return a set view of this map's entries
606         */
607        public Set entrySet() {
608            if (entrySet != null) {
609                return entrySet;
610            } 
611            entrySet = new AbstractSet() {
612                public int size() {
613                    return ReferenceMap.this.size();
614                }
615    
616                public void clear() {
617                    ReferenceMap.this.clear();
618                }
619    
620                public boolean contains(Object o) {
621                    if (o == null) return false;
622                    if (!(o instanceof Map.Entry)) return false;
623                    Map.Entry e = (Map.Entry)o;
624                    Entry e2 = getEntry(e.getKey());
625                    return (e2 != null) && e.equals(e2);
626                }
627    
628                public boolean remove(Object o) {
629                    boolean r = contains(o);
630                    if (r) {
631                        Map.Entry e = (Map.Entry)o;
632                        ReferenceMap.this.remove(e.getKey());
633                    }
634                    return r;
635                }
636    
637                public Iterator iterator() {
638                    return new EntryIterator();
639                }
640    
641                public Object[] toArray() {
642                    return toArray(new Object[0]);
643                }
644    
645                public Object[] toArray(Object[] arr) {
646                    ArrayList list = new ArrayList();
647                    Iterator iterator = iterator();
648                    while (iterator.hasNext()) {
649                        Entry e = (Entry)iterator.next();
650                        list.add(new DefaultMapEntry(e.getKey(), e.getValue()));
651                    }
652                    return list.toArray(arr);
653                }
654            };
655            return entrySet;
656        }
657    
658    
659        /**
660         *  Returns a set view of this map's keys.
661         *
662         *  @return a set view of this map's keys
663         */
664        public Set keySet() {
665            if (keySet != null) return keySet;
666            keySet = new AbstractSet() {
667                public int size() {
668                    return ReferenceMap.this.size();
669                }
670    
671                public Iterator iterator() {
672                    return new KeyIterator();
673                }
674    
675                public boolean contains(Object o) {
676                    return containsKey(o);
677                }
678    
679    
680                public boolean remove(Object o) {
681                    Object r = ReferenceMap.this.remove(o);
682                    return r != null;
683                }
684    
685                public void clear() {
686                    ReferenceMap.this.clear();
687                }
688    
689                public Object[] toArray() {
690                    return toArray(new Object[0]);
691                }
692    
693                public Object[] toArray(Object[] array) {
694                    Collection c = new ArrayList(size());
695                    for (Iterator it = iterator(); it.hasNext(); ) {
696                        c.add(it.next());
697                    }
698                    return c.toArray(array);
699                }
700            };
701            return keySet;
702        }
703    
704    
705        /**
706         *  Returns a collection view of this map's values.
707         *
708         *  @return a collection view of this map's values.
709         */
710        public Collection values() {
711            if (values != null) return values;
712            values = new AbstractCollection()  {
713                public int size() {
714                    return ReferenceMap.this.size();
715                }
716    
717                public void clear() {
718                    ReferenceMap.this.clear();
719                }
720    
721                public Iterator iterator() {
722                    return new ValueIterator();
723                }
724    
725                public Object[] toArray() {
726                    return toArray(new Object[0]);
727                }
728    
729                public Object[] toArray(Object[] array) {
730                    Collection c = new ArrayList(size());
731                    for (Iterator it = iterator(); it.hasNext(); ) {
732                        c.add(it.next());
733                    }
734                    return c.toArray(array);
735                }
736            };
737            return values;
738        }
739    
740    
741        // If getKey() or getValue() returns null, it means
742        // the mapping is stale and should be removed.
743        private class Entry implements Map.Entry, KeyValue {
744    
745            Object key;
746            Object value;
747            int hash;
748            Entry next;
749    
750    
751            public Entry(Object key, int hash, Object value, Entry next) {
752                this.key = key;
753                this.hash = hash;
754                this.value = value;
755                this.next = next;
756            }
757    
758    
759            public Object getKey() {
760                return (keyType > HARD) ? ((Reference)key).get() : key;
761            }
762    
763    
764            public Object getValue() {
765                return (valueType > HARD) ? ((Reference)value).get() : value;
766            }
767    
768    
769            public Object setValue(Object object) {
770                Object old = getValue();
771                if (valueType > HARD) ((Reference)value).clear();
772                value = toReference(valueType, object, hash);
773                return old;
774            }
775    
776    
777            public boolean equals(Object o) {
778                if (o == null) return false;
779                if (o == this) return true;
780                if (!(o instanceof Map.Entry)) return false;
781                
782                Map.Entry entry = (Map.Entry)o;
783                Object key = entry.getKey();
784                Object value = entry.getValue();
785                if ((key == null) || (value == null)) return false;
786                return key.equals(getKey()) && value.equals(getValue());
787            }
788    
789    
790            public int hashCode() {
791                Object v = getValue();
792                return hash ^ ((v == null) ? 0 : v.hashCode());
793            }
794    
795    
796            public String toString() {
797                return getKey() + "=" + getValue();
798            }
799    
800    
801            boolean purge(Reference ref) {
802                boolean r = (keyType > HARD) && (key == ref);
803                r = r || ((valueType > HARD) && (value == ref));
804                if (r) {
805                    if (keyType > HARD) ((Reference)key).clear();
806                    if (valueType > HARD) {
807                        ((Reference)value).clear();
808                    } else if (purgeValues) {
809                        value = null;
810                    }
811                }
812                return r;
813            }
814        }
815    
816    
817        private class EntryIterator implements Iterator {
818            // These fields keep track of where we are in the table.
819            int index;
820            Entry entry;
821            Entry previous;
822    
823            // These Object fields provide hard references to the
824            // current and next entry; this assures that if hasNext()
825            // returns true, next() will actually return a valid element.
826            Object nextKey, nextValue;
827            Object currentKey, currentValue;
828    
829            int expectedModCount;
830    
831    
832            public EntryIterator() {
833                index = (size() != 0 ? table.length : 0);
834                // have to do this here!  size() invocation above
835                // may have altered the modCount.
836                expectedModCount = modCount;
837            }
838    
839    
840            public boolean hasNext() {
841                checkMod();
842                while (nextNull()) {
843                    Entry e = entry;
844                    int i = index;
845                    while ((e == null) && (i > 0)) {
846                        i--;
847                        e = table[i];
848                    }
849                    entry = e;
850                    index = i;
851                    if (e == null) {
852                        currentKey = null;
853                        currentValue = null;
854                        return false;
855                    }
856                    nextKey = e.getKey();
857                    nextValue = e.getValue();
858                    if (nextNull()) entry = entry.next;
859                }
860                return true;
861            }
862    
863    
864            private void checkMod() {
865                if (modCount != expectedModCount) {
866                    throw new ConcurrentModificationException();
867                }
868            }
869    
870    
871            private boolean nextNull() {
872                return (nextKey == null) || (nextValue == null);
873            }
874    
875            protected Entry nextEntry() {    
876                checkMod();
877                if (nextNull() && !hasNext()) throw new NoSuchElementException();
878                previous = entry;
879                entry = entry.next;
880                currentKey = nextKey;
881                currentValue = nextValue;
882                nextKey = null;
883                nextValue = null;
884                return previous;
885            }
886    
887    
888            public Object next() {
889                return nextEntry();
890            }
891    
892    
893            public void remove() {
894                checkMod();
895                if (previous == null) throw new IllegalStateException();
896                ReferenceMap.this.remove(currentKey);
897                previous = null;
898                currentKey = null;
899                currentValue = null;
900                expectedModCount = modCount;
901            }
902    
903        }
904    
905    
906        private class ValueIterator extends EntryIterator {
907            public Object next() {
908                return nextEntry().getValue();
909            }
910        }
911    
912    
913        private class KeyIterator extends EntryIterator {
914            public Object next() {
915                return nextEntry().getKey();
916            }
917        }
918    
919    
920    
921        // These two classes store the hashCode of the key of
922        // of the mapping, so that after they're dequeued a quick
923        // lookup of the bucket in the table can occur.
924    
925    
926        private static class SoftRef extends SoftReference {
927            private int hash;
928    
929    
930            public SoftRef(int hash, Object r, ReferenceQueue q) {
931                super(r, q);
932                this.hash = hash;
933            }
934    
935    
936            public int hashCode() {
937                return hash;
938            }
939        }
940    
941    
942        private static class WeakRef extends WeakReference {
943            private int hash;
944    
945    
946            public WeakRef(int hash, Object r, ReferenceQueue q) {
947                super(r, q);
948                this.hash = hash;
949            }
950    
951    
952            public int hashCode() {
953                return hash;
954            }
955        }
956    
957    
958    }