001    package railo.commons.collections;
002    
003    import java.util.AbstractCollection;
004    import java.util.AbstractSet;
005    import java.util.Collection;
006    import java.util.ConcurrentModificationException;
007    import java.util.Enumeration;
008    import java.util.Iterator;
009    import java.util.Map;
010    import java.util.NoSuchElementException;
011    import java.util.Set;
012    
013    import railo.runtime.type.Collection.Key;
014    
015    /**
016     * This class implements a hashtable, which maps keys to values. Any 
017     * non-<code>null</code> object can be used as a key or as a value. <p>
018     *
019     * To successfully store and retrieve objects from a hashtable, the 
020     * objects used as keys must implement the <code>hashCode</code> 
021     * method and the <code>equals</code> method. <p>
022     *
023     * An instance of <code>Hashtable</code> has two parameters that affect its
024     * performance: <i>initial capacity</i> and <i>load factor</i>.  The
025     * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the
026     * <i>initial capacity</i> is simply the capacity at the time the hash table
027     * is created.  Note that the hash table is <i>open</i>: in the case a "hash
028     * collision", a single bucket stores multiple entries, which must be searched
029     * sequentially.  The <i>load factor</i> is a measure of how full the hash
030     * table is allowed to get before its capacity is automatically increased.
031     * When the number of entries in the hashtable exceeds the product of the load
032     * factor and the current capacity, the capacity is increased by calling the
033     * <code>rehash</code> method.<p>
034     *
035     * Generally, the default load factor (.75) offers a good tradeoff between
036     * time and space costs.  Higher values decrease the space overhead but
037     * increase the time cost to look up an entry (which is reflected in most
038     * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p>
039     *
040     * The initial capacity controls a tradeoff between wasted space and the
041     * need for <code>rehash</code> operations, which are time-consuming.
042     * No <code>rehash</code> operations will <i>ever</i> occur if the initial
043     * capacity is greater than the maximum number of entries the
044     * <tt>Hashtable</tt> will contain divided by its load factor.  However,
045     * setting the initial capacity too high can waste space.<p>
046     *
047     * If many entries are to be made into a <code>Hashtable</code>, 
048     * creating it with a sufficiently large capacity may allow the 
049     * entries to be inserted more efficiently than letting it perform 
050     * automatic rehashing as needed to grow the table. <p>
051     *
052     * This example creates a hashtable of numbers. It uses the names of 
053     * the numbers as keys:
054     * <p><blockquote><pre>
055     *     Hashtable numbers = new Hashtable();
056     *     numbers.put("one", new Integer(1));
057     *     numbers.put("two", new Integer(2));
058     *     numbers.put("three", new Integer(3));
059     * </pre></blockquote>
060     * <p>
061     * To retrieve a number, use the following code: 
062     * <p><blockquote><pre>
063     *     Integer n = (Integer)numbers.get("two");
064     *     if (n != null) {
065     *         System.out.println("two = " + n);
066     *     }
067     * </pre></blockquote>
068     * <p>
069     * As of the Java 2 platform v1.2, this class has been retrofitted to
070     * implement Map, so that it becomes a part of Java's collection framework.
071     * Unlike the new collection implementations, Hashtable is synchronized.<p>
072     *
073     * The Iterators returned by the iterator and listIterator methods
074     * of the Collections returned by all of Hashtable's "collection view methods"
075     * are <em>fail-fast</em>: if the Hashtable is structurally modified
076     * at any time after the Iterator is created, in any way except through the
077     * Iterator's own remove or add methods, the Iterator will throw a
078     * ConcurrentModificationException.  Thus, in the face of concurrent
079     * modification, the Iterator fails quickly and cleanly, rather than risking
080     * arbitrary, non-deterministic behavior at an undetermined time in the future.
081     * The Enumerations returned by Hashtable's keys and values methods are
082     * <em>not</em> fail-fast.
083     *
084     * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
085     * as it is, generally speaking, impossible to make any hard guarantees in the
086     * presence of unsynchronized concurrent modification.  Fail-fast iterators
087     * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 
088     * Therefore, it would be wrong to write a program that depended on this
089     * exception for its correctness: <i>the fail-fast behavior of iterators
090     * should be used only to detect bugs.</i>
091     */
092    public final class KeyImplMap  implements  Cloneable,
093                                                       java.io.Serializable {
094        /**
095         * The hash table data.
096         */
097        private transient Entry table[];
098    
099        /**
100         * The total number of entries in the hash table.
101         */
102        private transient int count;
103    
104        /**
105         * The table is rehashed when its size exceeds this threshold.  (The
106         * value of this field is (int)(capacity * loadFactor).)
107         *
108         * @serial
109         */
110        private int threshold;
111                                 
112        /**
113         * The load factor for the hashtable.
114         *
115         * @serial
116         */
117        private float loadFactor;
118    
119        /**
120         * The number of times this Hashtable has been structurally modified
121         * Structural modifications are those that change the number of entries in
122         * the Hashtable or otherwise modify its internal structure (e.g.,
123         * rehash).  This field is used to make iterators on Collection-views of
124         * the Hashtable fail-fast.  (See ConcurrentModificationException).
125         */
126        private transient int modCount = 0;
127    
128        /** use serialVersionUID from JDK 1.0.2 for interoperability */
129        private static final long serialVersionUID = 1421746759512286392L;
130    
131        /**
132         * Constructs a new, empty hashtable with the specified initial 
133         * capacity and the specified load factor.
134         *
135         * @param      initialCapacity   the initial capacity of the hashtable.
136         * @param      loadFactor        the load factor of the hashtable.
137         * @exception  IllegalArgumentException  if the initial capacity is less
138         *             than zero, or if the load factor is nonpositive.
139         */
140        public KeyImplMap(int initialCapacity, float loadFactor) {
141        if (initialCapacity < 0)
142            throw new IllegalArgumentException("Illegal Capacity: "+
143                                                   initialCapacity);
144            if (loadFactor <= 0 || Float.isNaN(loadFactor))
145                throw new IllegalArgumentException("Illegal Load: "+loadFactor);
146    
147            if (initialCapacity==0)
148                initialCapacity = 1;
149        this.loadFactor = loadFactor;
150        table = new Entry[initialCapacity];
151        threshold = (int)(initialCapacity * loadFactor);
152        }
153    
154        /**
155         * Constructs a new, empty hashtable with the specified initial capacity
156         * and default load factor, which is <tt>0.75</tt>.
157         *
158         * @param     initialCapacity   the initial capacity of the hashtable.
159         * @exception IllegalArgumentException if the initial capacity is less
160         *              than zero.
161         */
162        public KeyImplMap(int initialCapacity) {
163        this(initialCapacity, 0.75f);
164        }
165    
166        /**
167         * Constructs a new, empty hashtable with a default initial capacity (11)
168         * and load factor, which is <tt>0.75</tt>. 
169         */
170        public KeyImplMap() {
171        this(11, 0.75f);
172        }
173    
174        /**
175         * Returns the number of keys in this hashtable.
176         *
177         * @return  the number of keys in this hashtable.
178         */
179        public int size() {
180        return count;
181        }
182    
183        /**
184         * Tests if this hashtable maps no keys to values.
185         *
186         * @return  <code>true</code> if this hashtable maps no keys to values;
187         *          <code>false</code> otherwise.
188         */
189        public boolean isEmpty() {
190        return count == 0;
191        }
192    
193        /**
194         * Returns an enumeration of the keys in this hashtable.
195         *
196         * @return  an enumeration of the keys in this hashtable.
197         * @see     Enumeration
198         * @see     #elements()
199         * @see #keySet()
200         * @see Map
201         */
202        public Enumeration keys() {
203        return getEnumeration(KEYS);
204        }
205    
206        /**
207         * Returns an enumeration of the values in this hashtable.
208         * Use the Enumeration methods on the returned object to fetch the elements
209         * sequentially.
210         *
211         * @return  an enumeration of the values in this hashtable.
212         * @see     java.util.Enumeration
213         * @see     #keys()
214         * @see #values()
215         * @see Map
216         */
217        public Enumeration elements() {
218        return getEnumeration(VALUES);
219        }
220    
221        /**
222         * Tests if some key maps into the specified value in this hashtable.
223         * This operation is more expensive than the <code>containsKey</code>
224         * method.<p>
225         *
226         * Note that this method is identical in functionality to containsValue,
227         * (which is part of the Map interface in the collections framework).
228         * 
229         * @param      value   a value to search for.
230         * @return     <code>true</code> if and only if some key maps to the
231         *             <code>value</code> argument in this hashtable as 
232         *             determined by the <tt>equals</tt> method;
233         *             <code>false</code> otherwise.
234         * @exception  NullPointerException  if the value is <code>null</code>.
235         * @see        #containsKey(Object)
236         * @see        #containsValue(Object)
237         * @see    Map
238         */
239        public boolean contains(Object value) {
240                if (value == null) {
241                    throw new NullPointerException();
242                }
243            
244                Entry tab[] = table;
245                for (int i = tab.length ; i-- > 0 ;) {
246                    for (Entry e = tab[i] ; e != null ; e = e.next) {
247                    if (e.value.equals(value)) {
248                        return true;
249                    }
250                    }
251                }
252                return false;
253        }
254    
255        /**
256         * Returns true if this Hashtable maps one or more keys to this value.<p>
257         *
258         * Note that this method is identical in functionality to contains
259         * (which predates the Map interface).
260         *
261         * @param value value whose presence in this Hashtable is to be tested.
262         * @return <tt>true</tt> if this map maps one or more keys to the
263         *         specified value.
264         * @see    Map
265    *
266         */
267        public boolean containsValue(Object value) {
268        return contains(value);
269        }
270    
271        /**
272         * Tests if the specified object is a key in this hashtable.
273         * 
274         * @param   key   possible key.
275         * @return  <code>true</code> if and only if the specified object 
276         *          is a key in this hashtable, as determined by the 
277         *          <tt>equals</tt> method; <code>false</code> otherwise.
278         * @see     #contains(Object)
279         */
280        public boolean containsKey(Object key) {
281        Entry tab[] = table;
282        int hash = key.hashCode();
283        int index = (hash & 0x7FFFFFFF) % tab.length;
284        for (Entry e = tab[index] ; e != null ; e = e.next) {
285            if ((e.hash == hash) && e.key.equals(key)) {
286            return true;
287            }
288        }
289        return false;
290        }
291    
292        /**
293         * Returns the value to which the specified key is mapped in this hashtable.
294         *
295         * @param   key   a key in the hashtable.
296         * @return  the value to which the key is mapped in this hashtable;
297         *          <code>null</code> if the key is not mapped to any value in
298         *          this hashtable.
299         * @see     #put(Object, Object)
300         */
301        public Key get(Object key) {
302                Entry tab[] = table;
303                int hash = key.hashCode();
304                int index = (hash & 0x7FFFFFFF) % tab.length;
305                for (Entry e = tab[index] ; e != null ; e = e.next) {
306                    if ((e.hash == hash)) {
307                            return e.value;
308                    }
309                }
310                return null;
311        }
312    
313        /**
314         * Increases the capacity of and internally reorganizes this 
315         * hashtable, in order to accommodate and access its entries more 
316         * efficiently.  This method is called automatically when the 
317         * number of keys in the hashtable exceeds this hashtable's capacity 
318         * and load factor. 
319         */
320        protected void rehash() {
321        int oldCapacity = table.length;
322        Entry oldMap[] = table;
323    
324        int newCapacity = oldCapacity * 2 + 1;
325        Entry newMap[] = new Entry[newCapacity];
326    
327        modCount++;
328        threshold = (int)(newCapacity * loadFactor);
329        table = newMap;
330    
331        for (int i = oldCapacity ; i-- > 0 ;) {
332            for (Entry old = oldMap[i] ; old != null ; ) {
333            Entry e = old;
334            old = old.next;
335    
336            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
337            e.next = newMap[index];
338            newMap[index] = e;
339            }
340        }
341        }
342    
343        /**
344         * Maps the specified <code>key</code> to the specified 
345         * <code>value</code> in this hashtable. Neither the key nor the 
346         * value can be <code>null</code>. <p>
347         *
348         * The value can be retrieved by calling the <code>get</code> method 
349         * with a key that is equal to the original key. 
350         *
351         * @param      key     the hashtable key.
352         * @param      value   the value.
353         * @return     the previous value of the specified key in this hashtable,
354         *             or <code>null</code> if it did not have one.
355         * @exception  NullPointerException  if the key or value is
356         *               <code>null</code>.
357         * @see     Object#equals(Object)
358         * @see     #get(Object)
359         */
360        public Object put(Object key, Key value) {
361                // Makes sure the key is not already in the hashtable.
362                Entry tab[] = table;
363                int hash = key.hashCode();
364                int index = (hash & 0x7FFFFFFF) % tab.length;
365                for (Entry e = tab[index] ; e != null ; e = e.next) {
366                    if ((e.hash == hash) ) {
367                    Object old = e.value;
368                    e.value = value;
369                    return old;
370                }
371        }
372    
373        modCount++;
374        if (count >= threshold) {
375            // Rehash the table if the threshold is exceeded
376            rehash();
377    
378                tab = table;
379                index = (hash & 0x7FFFFFFF) % tab.length;
380        } 
381    
382        // Creates the new entry.
383        Entry e = new Entry(hash, key, value, tab[index]);
384        tab[index] = e;
385        count++;
386        return null;
387        }
388    
389        /**
390         * Removes the key (and its corresponding value) from this 
391         * hashtable. This method does nothing if the key is not in the hashtable.
392         *
393         * @param   key   the key that needs to be removed.
394         * @return  the value to which the key had been mapped in this hashtable,
395         *          or <code>null</code> if the key did not have a mapping.
396         */
397        public Object remove(Object key) {
398        Entry tab[] = table;
399        int hash = key.hashCode();
400        int index = (hash & 0x7FFFFFFF) % tab.length;
401        for (Entry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
402            if ((e.hash == hash) && e.key.equals(key)) {
403            modCount++;
404            if (prev != null) {
405                prev.next = e.next;
406            } else {
407                tab[index] = e.next;
408            }
409            count--;
410            Object oldValue = e.value;
411            e.value = null;
412            return oldValue;
413            }
414        }
415        return null;
416        }
417    
418        /**
419         * Clears this hashtable so that it contains no keys. 
420         */
421        public void clear() {
422        Entry tab[] = table;
423        modCount++;
424        for (int index = tab.length; --index >= 0; )
425            tab[index] = null;
426        count = 0;
427        }
428    
429        /**
430         * Creates a shallow copy of this hashtable. All the structure of the 
431         * hashtable itself is copied, but the keys and values are not cloned. 
432         * This is a relatively expensive operation.
433         *
434         * @return  a clone of the hashtable.
435         */
436        public Object clone() {
437        try { 
438            KeyImplMap t = (KeyImplMap)super.clone();
439            t.table = new Entry[table.length];
440            for (int i = table.length ; i-- > 0 ; ) {
441            t.table[i] = (table[i] != null) 
442                ? (Entry)table[i].clone() : null;
443            }
444            t.keySet = null;
445            t.entrySet = null;
446                t.values = null;
447            t.modCount = 0;
448            return t;
449        } catch (CloneNotSupportedException e) { 
450            // this shouldn't happen, since we are Cloneable
451            throw new InternalError();
452        }
453        }
454    
455        /**
456         * Returns a string representation of this <tt>Hashtable</tt> object 
457         * in the form of a set of entries, enclosed in braces and separated 
458         * by the ASCII characters "<tt>,&nbsp;</tt>" (comma and space). Each 
459         * entry is rendered as the key, an equals sign <tt>=</tt>, and the 
460         * associated element, where the <tt>toString</tt> method is used to 
461         * convert the key and element to strings. <p>Overrides to 
462         * <tt>toString</tt> method of <tt>Object</tt>.
463         *
464         * @return  a string representation of this hashtable.
465         */
466        public String toString() {
467        int max = size() - 1;
468        StringBuffer buf = new StringBuffer();
469        Iterator it = entrySet().iterator();
470    
471        buf.append("{");
472        for (int i = 0; i <= max; i++) {
473            Entry e = (Entry) (it.next());
474                Object key = e.getKey();
475                Object value = e.getValue();
476                buf.append((key   == this ? "(this Map)" : key) + "=" + 
477                           (value == this ? "(this Map)" : value));
478    
479            if (i < max)
480            buf.append(", ");
481        }
482        buf.append("}");
483        return buf.toString();
484        }
485    
486    
487        private Enumeration getEnumeration(int type) {
488            if (count == 0) {
489                return emptyEnumerator;
490            } 
491            return new Enumerator(type, false);
492            
493        }
494    
495        private Iterator getIterator(int type) {
496            if (count == 0) {
497                return emptyIterator;
498            } 
499            return new Enumerator(type, true);
500        }
501    
502        // Views
503    
504        /**
505         * Each of these fields are initialized to contain an instance of the
506         * appropriate view the first time this view is requested.  The views are
507         * stateless, so there's no reason to create more than one of each.
508         */
509        private transient volatile Set keySet = null;
510        private transient volatile Set entrySet = null;
511        private transient volatile Collection values = null;
512    
513        /**
514         * Returns a Set view of the keys contained in this Hashtable.  The Set
515         * is backed by the Hashtable, so changes to the Hashtable are reflected
516         * in the Set, and vice-versa.  The Set supports element removal
517         * (which removes the corresponding entry from the Hashtable), but not
518         * element addition.
519         *
520         * @return a set view of the keys contained in this map.
521    *
522         */
523        public Set keySet() {
524        if (keySet == null)
525            keySet = Collections.synchronizedSet(new KeySet(), this);
526        return keySet;
527        }
528    
529        private class KeySet extends AbstractSet {
530            /**
531             * @see java.util.Set#iterator()
532             */
533            public Iterator iterator() {
534            return getIterator(KEYS);
535            }
536            /**
537             * @see java.util.Set#size()
538             */
539            public int size() {
540                return count;
541            }
542            /**
543             * @see java.util.Set#contains(java.lang.Object)
544             */
545            public boolean contains(Object o) {
546                return containsKey(o);
547            }
548            /**
549             * @see java.util.Set#remove(java.lang.Object)
550             */
551            public boolean remove(Object o) {
552                return KeyImplMap.this.remove(o) != null;
553            }
554            /**
555             * @see java.util.Set#clear()
556             */
557            public void clear() {
558                KeyImplMap.this.clear();
559            }
560        }
561    
562        /**
563         * Returns a Set view of the entries contained in this Hashtable.
564         * Each element in this collection is a Map.Entry.  The Set is
565         * backed by the Hashtable, so changes to the Hashtable are reflected in
566         * the Set, and vice-versa.  The Set supports element removal
567         * (which removes the corresponding entry from the Hashtable),
568         * but not element addition.
569         *
570         * @return a set view of the mappings contained in this map.
571         * @see   Map.Entry
572    *
573         */
574        public Set entrySet() {
575        if (entrySet==null)
576            entrySet = Collections.synchronizedSet(new EntrySet(), this);
577        return entrySet;
578        }
579    
580        private class EntrySet extends AbstractSet {
581            /**
582             * @see java.util.Set#iterator()
583             */
584            public Iterator iterator() {
585            return getIterator(ENTRIES);
586            }
587    
588            /**
589             * @see java.util.Set#contains(java.lang.Object)
590             */
591            public boolean contains(Object o) {
592                if (!(o instanceof Entry))
593                    return false;
594                Entry entry = (Entry)o;
595                Object key = entry.getKey();
596                Entry tab[] = table;
597                int hash = key.hashCode();
598                int index = (hash & 0x7FFFFFFF) % tab.length;
599    
600                for (Entry e = tab[index]; e != null; e = e.next)
601                    if (e.hash==hash && e.equals(entry))
602                        return true;
603                return false;
604            }
605    
606            /**
607             * @see java.util.Set#remove(java.lang.Object)
608             */
609            public boolean remove(Object o) {
610                if (!(o instanceof Entry))
611                    return false;
612                Entry entry = (Entry)o;
613                Object key = entry.getKey();
614                Entry tab[] = table;
615                int hash = key.hashCode();
616                int index = (hash & 0x7FFFFFFF) % tab.length;
617    
618                for (Entry e = tab[index], prev = null; e != null;
619                     prev = e, e = e.next) {
620                    if (e.hash==hash && e.equals(entry)) {
621                        modCount++;
622                        if (prev != null)
623                            prev.next = e.next;
624                        else
625                            tab[index] = e.next;
626    
627                        count--;
628                        e.value = null;
629                        return true;
630                    }
631                }
632                return false;
633            }
634    
635            /**
636             * @see java.util.Set#size()
637             */
638            public int size() {
639                return count;
640            }
641    
642            /**
643             * @see java.util.Set#clear()
644             */
645            public void clear() {
646                KeyImplMap.this.clear();
647            }
648        }
649    
650        /**
651         * Returns a Collection view of the values contained in this Hashtable.
652         * The Collection is backed by the Hashtable, so changes to the Hashtable
653         * are reflected in the Collection, and vice-versa.  The Collection
654         * supports element removal (which removes the corresponding entry from
655         * the Hashtable), but not element addition.
656         *
657         * @return a collection view of the values contained in this map.
658    *
659         */
660        public Collection values() {
661        if (values==null)
662            values = Collections.synchronizedCollection(new ValueCollection(),
663                                                            this);
664            return values;
665        }
666    
667        private class ValueCollection extends AbstractCollection {
668            /**
669             * @see java.util.AbstractCollection#iterator()
670             */
671            public Iterator iterator() {
672            return getIterator(VALUES);
673            }
674            /**
675             * @see java.util.AbstractCollection#size()
676             */
677            public int size() {
678                return count;
679            }
680            /**
681             * @see java.util.AbstractCollection#contains(java.lang.Object)
682             */
683            public boolean contains(Object o) {
684                return containsValue(o);
685            }
686            /**
687             * @see java.util.AbstractCollection#clear()
688             */
689            public void clear() {
690                KeyImplMap.this.clear();
691            }
692        }
693    
694        /**
695         * Returns the hash code value for this Map as per the definition in the
696         * Map interface.
697         *
698         * @see Map#hashCode()
699    *
700         */
701        public int hashCode() {
702            /*
703             * This code detects the recursion caused by computing the hash code
704             * of a self-referential hash table and prevents the stack overflow
705             * that would otherwise result.  This allows certain 1.1-era
706             * applets with self-referential hash tables to work.  This code
707             * abuses the loadFactor field to do double-duty as a hashCode
708             * in progress flag, so as not to worsen the space performance.
709             * A negative load factor indicates that hash code computation is
710             * in progress.
711             */
712            int h = 0;
713            if (count == 0 || loadFactor < 0)
714                return h;  // Returns zero
715    
716            loadFactor = -loadFactor;  // Mark hashCode computation in progress
717            Entry tab[] = table;
718            for (int i = 0; i < tab.length; i++)
719                for (Entry e = tab[i]; e != null; e = e.next)
720                    h += e.key.hashCode() ^ e.value.hashCode();
721            loadFactor = -loadFactor;  // Mark hashCode computation complete
722    
723        return h;
724        }
725    
726        /**
727         * Hashtable collision list.
728         */
729        private static class Entry  {
730        int hash;
731        Object key;
732        Key value;
733        Entry next;
734    
735        /**
736         * @param hash
737         * @param key
738         * @param value
739         * @param next
740         */
741        protected Entry(int hash, Object key, Key value, Entry next) {
742            this.hash = hash;
743            this.key = key;
744            this.value = value;
745            this.next = next;
746        }
747    
748        /**
749         * @see java.lang.Object#clone()
750         */
751        protected Object clone() {
752            return new Entry(hash, key, value,
753                     (next==null ? null : (Entry)next.clone()));
754        }
755    
756        // Map.Entry Ops 
757    
758        /**
759         * @see java.util.Map.Entry#getKey()
760         */
761        public Object getKey() {
762            return key;
763        }
764    
765        /**
766         * @see java.util.Map.Entry#getValue()
767         */
768        public Key getValue() {
769            return value;
770        }
771    
772        /**
773         * @see java.util.Map.Entry#setValue(java.lang.Object)
774         */
775        public Object setValue(Key value) {
776            if (value == null)
777            throw new NullPointerException();
778    
779            Object oldValue = this.value;
780            this.value = value;
781            return oldValue;
782        }
783    
784        /**
785         * @see java.util.Map.Entry#equals(java.lang.Object)
786         */
787        public boolean equals(Object o) {
788            if (!(o instanceof Entry))
789            return false;
790            Entry e = (Entry)o;
791    
792            return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
793               (value==null ? e.getValue()==null : value.equals(e.getValue()));
794        }
795    
796        /**
797         * @see java.util.Map.Entry#hashCode()
798         */
799        public int hashCode() {
800            return hash ^ (value==null ? 0 : value.hashCode());
801        }
802    
803        /**
804         * @see java.lang.Object#toString()
805         */
806        public String toString() {
807            return key.toString()+"="+value.toString();
808        }
809        }
810    
811        // Types of Enumerations/Iterations
812        private static final int KEYS = 0;
813        private static final int VALUES = 1;
814        private static final int ENTRIES = 2;
815    
816        /**
817         * A hashtable enumerator class.  This class implements both the
818         * Enumeration and Iterator interfaces, but individual instances
819         * can be created with the Iterator methods disabled.  This is necessary
820         * to avoid unintentionally increasing the capabilities granted a user
821         * by passing an Enumeration.
822         */
823        private class Enumerator implements Enumeration, Iterator {
824        Entry[] table = KeyImplMap.this.table;
825        int index = table.length;
826        Entry entry = null;
827        Entry lastReturned = null;
828        int type;
829    
830        /**
831         * Indicates whether this Enumerator is serving as an Iterator
832         * or an Enumeration.  (true -> Iterator).
833         */
834        boolean iterator;
835    
836        /**
837         * The modCount value that the iterator believes that the backing
838         * List should have.  If this expectation is violated, the iterator
839         * has detected concurrent modification.
840         */
841        protected int expectedModCount = modCount;
842    
843        Enumerator(int type, boolean iterator) {
844            this.type = type;
845            this.iterator = iterator;
846        }
847    
848        /**
849         * @see java.util.Enumeration#hasMoreElements()
850         */
851        public boolean hasMoreElements() {
852            Entry e = entry;
853            int i = index;
854            Entry t[] = table;
855            /* Use locals for faster loop iteration */
856            while (e == null && i > 0) { 
857            e = t[--i];
858            }
859            entry = e;
860            index = i;
861            return e != null;
862        }
863    
864        /**
865         * @see java.util.Enumeration#nextElement()
866         */
867        public Object nextElement() {
868            
869            throw new NoSuchElementException("not impl");
870        }
871    
872        /**
873         * @see java.util.Iterator#hasNext()
874         */
875        // Iterator methods
876        public boolean hasNext() {
877            return hasMoreElements();
878        }
879    
880        /**
881         * @see java.util.Iterator#next()
882         */
883        public Object next() {
884            if (modCount != expectedModCount)
885            throw new ConcurrentModificationException();
886            return nextElement();
887        }
888    
889        /**
890         * @see java.util.Iterator#remove()
891         */
892        public void remove() {
893            if (!iterator)
894            throw new UnsupportedOperationException();
895            if (lastReturned == null)
896            throw new IllegalStateException("Hashtable Enumerator");
897            if (modCount != expectedModCount)
898            throw new ConcurrentModificationException();
899    
900            synchronized(KeyImplMap.this) {
901            Entry[] tab = KeyImplMap.this.table;
902            int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
903    
904            for (Entry e = tab[index], prev = null; e != null;
905                 prev = e, e = e.next) {
906                if (e == lastReturned) {
907                modCount++;
908                expectedModCount++;
909                if (prev == null)
910                    tab[index] = e.next;
911                else
912                    prev.next = e.next;
913                count--;
914                lastReturned = null;
915                return;
916                }
917            }
918            throw new ConcurrentModificationException();
919            }
920        }
921        }
922    
923       
924        private static EmptyEnumerator emptyEnumerator = new EmptyEnumerator();
925        private static EmptyIterator emptyIterator = new EmptyIterator();
926    
927        /**
928         * A hashtable enumerator class for empty hash tables, specializes
929         * the general Enumerator
930         */
931        private static class EmptyEnumerator implements Enumeration {
932    
933        EmptyEnumerator() {
934        }
935    
936        /**
937         * @see java.util.Enumeration#hasMoreElements()
938         */
939        public boolean hasMoreElements() {
940            return false;
941        }
942    
943        /**
944         * @see java.util.Enumeration#nextElement()
945         */
946        public Object nextElement() {
947            throw new NoSuchElementException("Hashtable Enumerator");
948        }
949        }
950    
951    
952        /**
953         * A hashtable iterator class for empty hash tables
954         */
955        private static class EmptyIterator implements Iterator {
956    
957        EmptyIterator() {
958        }
959    
960        /**
961         * @see java.util.Iterator#hasNext()
962         */
963        public boolean hasNext() {
964            return false;
965        }
966    
967        /**
968         * @see java.util.Iterator#next()
969         */
970        public Object next() {
971            throw new NoSuchElementException("Hashtable Iterator");
972        }
973    
974        /**
975         * @see java.util.Iterator#remove()
976         */
977        public void remove() {
978            throw new IllegalStateException("Hashtable Iterator");
979        }
980    
981        }
982    
983    }