Java > Open Source Codes > org > eclipse > emf > common > util > BasicEMap


1 /**
2  * <copyright>
3  *
4  * Copyright (c) 2002-2004 IBM Corporation and others.
5  * All rights reserved. This program and the accompanying materials
6  * are made available under the terms of the Eclipse Public License v1.0
7  * which accompanies this distribution, and is available at
8  * http://www.eclipse.org/legal/epl-v10.html
9  *
10  * Contributors:
11  * IBM - Initial API and implementation
12  *
13  * </copyright>
14  *
15  * $Id: BasicEMap.java,v 1.6 2005/06/08 06:19:08 nickb Exp $
16  */
17 package org.eclipse.emf.common.util;
18
19
20 import java.io.IOException ;
21 import java.io.ObjectInputStream ;
22 import java.io.ObjectOutputStream ;
23 import java.io.Serializable ;
24 import java.util.AbstractCollection ;
25 import java.util.AbstractSet ;
26 import java.util.Collection ;
27 import java.util.ConcurrentModificationException ;
28 import java.util.Iterator ;
29 import java.util.List ;
30 import java.util.ListIterator ;
31 import java.util.Map ;
32 import java.util.NoSuchElementException ;
33 import java.util.Set ;
34
35
36 /**
37  * A highly extensible map implementation.
38  */
39 public class BasicEMap implements EMap, Cloneable , Serializable
40 {
41   /**
42    * An extended implementation interface for caching hash values
43    * and for upating an entry that may be manufactured as a uninitialized instance by a factory.
44    * No client is expected to use this interface,
45    * other than to implement it in conjunction with a map implementation.
46    */
47   public interface Entry extends Map.Entry
48   {
49     /**
50      * Sets the key.
51      * This should only be called by the map implementation,
52      * since the key of an entry already in the map must be immutable.
53      * @param key the key.
54      */
55     void setKey(Object key);
56
57     /**
58      * Returns the hash code of the key.
59      * Only the map implementation would really care.
60      */
61     int getHash();
62
63     /**
64      * Sets the hash code of the key.
65      * This should only be called by the map implementation,
66      * since the hash code of the key of an entry already in the map must be immutable.
67      * @param hash the hash.
68      */
69     void setHash(int hash);
70   }
71
72   /**
73    * The underlying list of entries.
74    */
75   protected transient EList delegateEList;
76
77   /**
78    * The size of the map.
79    */
80   protected int size;
81
82   /**
83    * The array of entry lists into which the hash codes are indexed.
84    */
85   protected transient BasicEList entryData[];
86
87   /**
88    * The modification indicator used to ensure iterator integrity.
89    */
90   protected transient int modCount;
91
92   /**
93    * An implementation class to hold the views.
94    */
95   protected static class View
96   {
97     /**
98      * The map view.
99      */
100     public transient Map map;
101
102     /**
103      * The map key set view.
104      */
105     public transient Set keySet;
106
107     /**
108      * The entry set view.
109      */
110     public transient Set entrySet;
111
112     /**
113      * The values collection view.
114      */
115     public transient Collection values;
116
117     /**
118      * Creates an empty instance.
119      */
120     public View()
121     {
122     }
123   }
124
125   /**
126    * The various alternative views of the map.
127    */
128   protected transient View view;
129
130   /**
131    * Creates an empty instance.
132    */
133   public BasicEMap()
134   {
135     initializeDelegateEList();
136   }
137
138   /**
139    * Initializes the {@link #delegateEList}.
140    * This implementation illustrates the precise pattern that is used to
141    * delegate a list implementation's callback methods to the map implementation.
142    */
143   protected void initializeDelegateEList()
144   {
145     delegateEList =
146       new BasicEList()
147       {
148         protected void didAdd(int index, Object newObject)
149         {
150           doPut((Entry)newObject);
151         }
152
153         protected void didSet(int index, Object newObject, Object oldObject)
154         {
155           didRemove(index, oldObject);
156           didAdd(index, newObject);
157         }
158
159         protected void didRemove(int index, Object oldObject)
160         {
161           doRemove((Entry)oldObject);
162         }
163
164         protected void didClear(int size, Object [] oldObjects)
165         {
166           doClear();
167         }
168
169         protected void didMove(int index, Object movedObject, int oldIndex)
170         {
171           doMove((Entry)movedObject);
172         }
173       };
174   }
175
176   /**
177    * Creates an empty instance with the given capacity.
178    * @param initialCapacity the initial capacity of the map before it must grow.
179    * @exception IllegalArgumentException if the <code>initialCapacity</code> is negative.
180    */
181   public BasicEMap(int initialCapacity)
182   {
183     this();
184
185     if (initialCapacity < 0)
186     {
187       throw new IllegalArgumentException ("Illegal Capacity:" + initialCapacity);
188     }
189
190     entryData = newEntryData(initialCapacity);
191   }
192
193   /**
194    * Creates an instance that is a copy of the map.
195    * @param map the initial contents of the map.
196    */
197   public BasicEMap(Map map)
198   {
199     this();
200     int mapSize = map.size();
201     if (mapSize > 0)
202     {
203       entryData = newEntryData(2 * mapSize);
204       putAll(map);
205     }
206   }
207
208   /**
209    * Returns new allocated entry data storage.
210    * Clients may override this to create typed storage, but it's not likely.
211    * The cost of type checking via a typed array is negligable.
212    * @param capacity the capacity of storage needed.
213    * @return new entry data storage.
214    */
215   protected BasicEList [] newEntryData(int capacity)
216   {
217     return new BasicEList[capacity];
218   }
219
220   /**
221    * Ensures that the entry data is created
222    * and is populated with contents of the delegate list.
223    */
224   protected void ensureEntryDataExists()
225   {
226     if (entryData == null)
227     {
228       entryData = newEntryData(2 * size + 1);
229
230       // This should be transparent.
231 //
232 int oldModCount = modCount;
233       size = 0;
234       for (Iterator i = delegateEList.iterator(); i.hasNext(); )
235       {
236         Entry entry = (Entry)i.next();
237         doPut(entry);
238       }
239       modCount = oldModCount;
240     }
241   }
242
243   /**
244    * Returns a new allocated list of entries.
245    * Clients may override this to create typed storage.
246    * The cost of type checking via a typed array is negligable.
247    * The type must be kept in synch with {@link #newEntry(int, Object, Object) newEntry}.
248    * @return a new list of entries.
249    * @see #newEntry(int, Object, Object)
250    */
251   protected BasicEList newList()
252   {
253     return
254       new BasicEList()
255       {
256         public Object [] newData(int listCapacity)
257         {
258           return new EntryImpl [listCapacity];
259         }
260       };
261   }
262
263   /**
264    * Returns a new entry.
265    * The key is {@link #validateKey validated} and the value is {@link #validateValue validated}.
266    * Clients may override this to create typed storage.
267    * The type must be kept in synch with {@link #newList newEntry}.
268    * @param hash the cached hash code of the key.
269    * @param key the key.
270    * @param value the value.
271    * @return a new entry.
272    * @see #newList
273    */
274   protected Entry newEntry(int hash, Object key, Object value)
275   {
276     validateKey(key);
277     validateValue(value);
278     return new EntryImpl(hash, key, value);
279   }
280
281   /**
282    * Sets the value of the entry, and returns the former value.
283    * The value is {@link #validateValue validated}.
284    * @param entry the entry.
285    * @param value the value.
286    * @return the former value, or <code>null</code>.
287    */
288   protected Object putEntry(Entry entry, Object value)
289   {
290     return entry.setValue(value);
291   }
292
293   /**
294    * Returns whether <code>equals</code> rather than <code>==</code> should be used to compare keys.
295    * The default is to return <code>true</code> but clients can optimize performance by returning <code>false</code>.
296    * The performance difference is highly significant.
297    * @return whether <code>equals</code> rather than <code>==</code> should be used to compare keys.
298    */
299   protected boolean useEqualsForKey()
300   {
301     return true;
302   }
303
304   /**
305    * Returns whether <code>equals</code> rather than <code>==</code> should be used to compare values.
306    * The default is to return <code>true</code> but clients can optimize performance by returning <code>false</code>.
307    * The performance difference is highly significant.
308    * @return whether <code>equals</code> rather than <code>==</code> should be used to compare values.
309    */
310   protected boolean useEqualsForValue()
311   {
312     return true;
313   }
314
315   /**
316    * Resolves the value associated with the key and returns the result.
317    * This implementation simply returns the <code>value</code>;
318    * clients can use this to transform objects as they are fetched.
319    * @param key the key of an entry.
320    * @param value the value of an entry.
321    * @return the resolved value.
322    */
323   protected Object resolve(Object key, Object value)
324   {
325     return value;
326   }
327
328   /**
329    * Validates a new key.
330    * This implementation does nothing,
331    * but clients may throw runtime exceptions
332    * in order to handle constraint violations.
333    * @param key the new key.
334    * @exception IllegalArgumentException if a constraint prevents the object from being added.
335    */
336   protected void validateKey(Object key)
337   {
338   }
339
340   /**
341    * Validates a new key.
342    * This implementation does nothing,
343    * but clients may throw runtime exceptions
344    * in order to handle constraint violations.
345    * @param value the new value.
346    * @exception IllegalArgumentException if a constraint prevents the object from being added.
347    */
348   protected void validateValue(Object value)
349   {
350   }
351
352   /**
353    * Called to indicate that the entry has been added.
354    * This implementation does nothing;
355    * clients can use this to monitor additions to the map.
356    * @param entry the added entry.
357    */
358   protected void didAdd(Entry entry)
359   {
360   }
361
362   /**
363    * Called to indicate that the entry has an updated value.
364    * This implementation does nothing;
365    * clients can use this to monitor value changes in the map.
366    * @param entry the new entry.
367    */
368   protected void didModify(Entry entry, Object oldValue)
369   {
370   }
371
372   /**
373    * Called to indicate that the entry has been removed.
374    * This implementation does nothing;
375    * clients can use this to monitor removals from the map.
376    * @param entry the removed entry.
377    */
378   protected void didRemove(Entry entry)
379   {
380   }
381
382   /**
383    * Called to indicate that the map has been cleared.
384    * This implementation does calls {@link #didRemove didRemove} for each entry;
385    * clients can use this to monitor clearing of the map.
386    * @param oldEntryData the removed entries.
387    */
388   protected void didClear(BasicEList [] oldEntryData)
389   {
390     if (oldEntryData != null)
391     {
392       for (int i = 0; i < oldEntryData.length; ++i)
393       {
394         BasicEList eList = oldEntryData[i];
395         if (eList != null)
396         {
397           Entry [] entries = (Entry [])eList.data;
398           int size = eList.size;
399           for (int j = 0; j < size; ++j)
400           {
401             Entry entry = entries[j];
402             didRemove(entry);
403           }
404         }
405       }
406     }
407   }
408
409   /**
410    * Returns the number of entries in the map.
411    * @return the number of entries in the map.
412    */
413   public int size()
414   {
415     return size;
416   }
417
418   /**
419    * Returns whether the map has zero size.
420    * @return whether the map has zero size.
421    */
422   public boolean isEmpty()
423   {
424     return size == 0;
425   }
426
427   /*
428    * Javadoc copied from interface.
429    */
430   public int indexOfKey(Object key)
431   {
432     if (useEqualsForKey() && key != null)
433     {
434       for (int i = 0, size = delegateEList.size(); i < size; ++i)
435       {
436         Entry entry = (Entry)delegateEList.get(i);
437         if (key.equals(entry.getKey()))
438         {
439           return i;
440         }
441       }
442     }
443     else
444     {
445       for (int i = 0, size = delegateEList.size(); i < size; ++i)
446       {
447         Entry entry = (Entry)delegateEList.get(i);
448         if (key == entry.getKey())
449         {
450           return i;
451         }
452       }
453     }
454
455     return -1;
456   }
457
458   /*
459    * Javadoc copied from interface.
460    */
461   public boolean containsKey(Object key)
462   {
463     if (size > 0)
464     {
465       ensureEntryDataExists();
466       int hash = hashOf(key);
467       int index = indexOf(hash);
468       int entryIndex = entryIndexForKey(index, hash, key);
469       return entryIndex != -1;
470     }
471     else
472     {
473       return false;
474     }
475   }
476
477   /*
478    * Javadoc copied from interface.
479    */
480   public boolean containsValue(Object value)
481   {
482     if (size > 0)
483     {
484       ensureEntryDataExists();
485
486       if (useEqualsForValue() && value != null)
487       {
488         for (int i = 0; i < entryData.length; ++i)
489         {
490           BasicEList eList = entryData[i];
491           if (eList != null)
492           {
493             Entry [] entries = (Entry [])eList.data;
494             int size = eList.size;
495             for (int j = 0; j < size; ++j)
496             {
497               Entry entry = entries[j];
498               if (value.equals(entry.getValue()))
499               {
500                 return true;
501               }
502             }
503           }
504         }
505       }
506       else
507       {
508         for (int i = 0; i < entryData.length; ++i)
509         {
510           BasicEList eList = entryData[i];
511           if (eList != null)
512           {
513             Entry [] entries = (Entry [])eList.data;
514             int size = eList.size;
515             for (int j = 0; j < size; ++j)
516             {
517               Entry entry = entries[j];
518               if (value == entry.getValue())
519               {
520                 return true;
521               }
522             }
523           }
524         }
525       }
526     }
527
528     return false;
529   }
530
531   /*
532    * Javadoc copied from interface.
533    */
534   public Object get(Object key)
535   {
536     if (size > 0)
537     {
538       ensureEntryDataExists();
539       int hash = hashOf(key);
540       int index = indexOf(hash);
541       Entry entry = entryForKey(index, hash, key);
542       if (entry != null)
543       {
544         return resolve(key, entry.getValue());
545       }
546     }
547
548     return null;
549   }
550
551   /*
552    * Javadoc copied from interface.
553    */
554   public Object put(Object key, Object value)
555   {
556     ensureEntryDataExists();
557
558     int hash = hashOf(key);
559     if (size > 0)
560     {
561       int index = indexOf(hash);
562       Entry entry = entryForKey(index, hash, key);
563       if (entry != null)
564       {
565         Object result = putEntry(entry, value);
566         didModify(entry, result);
567         return result;
568       }
569     }
570
571     Entry entry = newEntry(hash, key, value);
572     delegateEList.add(entry);
573     return null;
574   }
575
576   /**
577    * Adds the new entry to the map.
578    * @param entry the new entry.
579    */
580   protected void doPut(Entry entry)
581   {
582     if (entryData == null)
583     {
584       ++modCount;
585       ++size;
586     }
587     else
588     {
589       int hash = entry.getHash();
590       grow(size + 1);
591       int index = indexOf(hash);
592       BasicEList eList = entryData[index];
593       if (eList == null)
594       {
595         eList = entryData[index] = newList();
596       }
597       eList.add(entry);
598       ++size;
599       didAdd(entry);
600     }
601   }
602
603   /*
604    * Javadoc copied from source.
605    */
606   public Object removeKey(Object key)
607   {
608     ensureEntryDataExists();
609
610     int hash = hashOf(key);
611     int index = indexOf(hash);
612     Entry entry = entryForKey(index, hash, key);
613     if (entry != null)
614     {
615       remove(entry);
616       return entry.getValue();
617     }
618     else
619     {
620       return null;
621     }
622   }
623
624   /**
625    * Removes the entry from the map.
626    * @param entry an entry in the map.
627    */
628   protected void doRemove(Entry entry)
629   {
630     if (entryData == null)
631     {
632       ++modCount;
633       --size;
634     }
635     else
636     {
637       Object key = entry.getKey();
638       int hash = entry.getHash();
639       int index = indexOf(hash);
640       removeEntry(index, entryIndexForKey(index, hash, key));
641       didRemove(entry);
642     }
643   }
644
645   /**
646    * Removes the fully indexed entry from the map and returns it's value.
647    * @param index the index in the entry data
648    * @param entryIndex the index in the list of entries.
649    * @return the value of the entry.
650    */
651   protected Object removeEntry(int index, int entryIndex)
652   {
653     ++modCount;
654     --size;
655
656     Entry entry = (Entry)entryData[index].remove(entryIndex);
657     return entry.getValue();
658   }
659
660   /*
661    * Javadoc copied from interface.
662    */
663   public void putAll(Map map)
664   {
665     for (Iterator i = map.entrySet().iterator(); i.hasNext(); )
666     {
667       Map.Entry entry = (Map.Entry )i.next();
668       put(entry.getKey(), entry.getValue());
669     }
670   }
671
672   /*
673    * Javadoc copied from interface.
674    */
675   public void putAll(EMap map)
676   {
677     for (Iterator i = map.iterator(); i.hasNext(); )
678     {
679       Map.Entry entry = (Map.Entry )i.next();
680       put(entry.getKey(), entry.getValue());
681     }
682   }
683
684   /**
685    * Clears the map.
686    */
687   protected void doClear()
688   {
689     if (entryData == null)
690     {
691       ++modCount;
692       size = 0;
693       didClear(null);
694     }
695     else
696     {
697       ++modCount;
698       BasicEList [] oldEntryData = entryData;
699       entryData = null;
700       size = 0;
701       didClear(oldEntryData);
702     }
703   }
704
705   /**
706    * Increments the modification count.
707    */
708   protected void doMove(Entry entry)
709   {
710     ++modCount;
711   }
712
713   /**
714    * Returns a shallow copy of this map.
715    * @return a shallow copy of this map.
716    */
717   public Object clone()
718   {
719     try
720     {
721       BasicEMap result = (BasicEMap)super.clone();
722       if (entryData != null)
723       {
724         result.entryData = newEntryData(entryData.length);
725         for (int i = 0; i < entryData.length; ++i)
726         {
727           result.entryData[i] = (entryData[i] == null ? null : (BasicEList)entryData[i].clone());
728         }
729       }
730       result.view = null;
731       result.modCount = 0;
732       return result;
733     }
734     catch (CloneNotSupportedException exception)
735     {
736       throw new InternalError ();
737     }
738   }
739
740   protected class DelegatingMap implements EMap.InternalMapView
741   {
742     public DelegatingMap()
743     {
744     }
745
746     public EMap eMap()
747     {
748       return BasicEMap.this;
749     }
750
751     public int size()
752     {
753       return BasicEMap.this.size();
754     }
755
756     public boolean isEmpty()
757     {
758       return BasicEMap.this.isEmpty();
759     }
760
761     public boolean containsKey(Object key)
762     {
763       return BasicEMap.this.containsKey(key);
764     }
765
766     public boolean containsValue(Object value)
767     {
768       return BasicEMap.this.containsValue(value);
769     }
770
771     public Object get(Object key)
772     {
773       return BasicEMap.this.get(key);
774     }
775
776     public Object put(Object key, Object value)
777     {
778       return BasicEMap.this.put(key, value);
779     }
780
781     public Object remove(Object key)
782     {
783       return BasicEMap.this.removeKey(key);
784     }
785
786     public void putAll(Map map)
787     {
788       BasicEMap.this.putAll(map);
789     }
790
791     public void clear()
792     {
793       BasicEMap.this.clear();
794     }
795
796     public Set keySet()
797     {
798       return BasicEMap.this.keySet();
799     }
800
801     public Collection values()
802     {
803       return BasicEMap.this.values();
804     }
805
806     public Set entrySet()
807     {
808       return BasicEMap.this.entrySet();
809     }
810
811     public boolean equals(Object object)
812     {
813       return BasicEMap.this.equals(object);
814     }
815
816     public int hashCode()
817     {
818       return BasicEMap.this.hashCode();
819     }
820   }
821
822   /*
823    * Javadoc copied from interface.
824    */
825   public Map map()
826   {
827     if (view == null)
828     {
829       view = new View();
830     }
831     if (view.map == null)
832     {
833       view.map = new DelegatingMap();
834     }
835
836     return view.map;
837   }
838
839   /*
840    * Javadoc copied from interface.
841    */
842   public Set keySet()
843   {
844     if (view == null)
845     {
846       view = new View();
847     }
848     if (view.keySet == null)
849     {
850       view.keySet =
851         new AbstractSet ()
852         {
853           public Iterator iterator()
854           {
855             return BasicEMap.this.size == 0 ? ECollections.EMPTY_ELIST.iterator() : new BasicEMap.BasicEMapKeyIterator();
856           }
857
858           public int size()
859           {
860             return BasicEMap.this.size;
861           }
862
863           public boolean contains(Object key)
864           {
865             return BasicEMap.this.containsKey(key);
866           }
867
868           public boolean remove(Object key)
869           {
870             int oldSize = BasicEMap.this.size;
871             BasicEMap.this.removeKey(key);
872             return BasicEMap.this.size != oldSize;
873           }
874
875           public void clear()
876           {
877             BasicEMap.this.clear();
878           }
879        };
880     }
881     return view.keySet;
882   }
883
884   /*
885    * Javadoc copied from interface.
886    */
887   public Collection values()
888   {
889     if (view == null)
890     {
891       view = new View();
892     }
893     if (view.values == null)
894     {
895       view.values =
896         new AbstractCollection ()
897         {
898           public Iterator iterator()
899           {
900             return BasicEMap.this.size == 0 ? ECollections.EMPTY_ELIST.iterator() : new BasicEMap.BasicEMapValueIterator();
901           }
902           public int size()
903           {
904             return size;
905           }
906           public boolean contains(Object value)
907           {
908             return containsValue(value);
909           }
910           public void clear()
911           {
912             BasicEMap.this.clear();
913           }
914         };
915     }
916     return view.values;
917   }
918
919   /*
920    * Javadoc copied from interface.
921    */
922   public Set entrySet()
923   {
924     if (view == null)
925     {
926       view = new View();
927     }
928     if (view.entrySet == null)
929     {
930       view.entrySet = new AbstractSet ()
931       {
932         public int size()
933         {
934           return BasicEMap.this.size;
935         }
936
937         public boolean contains(Object object)
938         {
939           if (BasicEMap.this.size > 0 && object instanceof Map.Entry )
940           {
941             BasicEMap.this.ensureEntryDataExists();
942             Map.Entry otherEntry = (Map.Entry )object;
943             Object key = otherEntry.getKey();
944   
945             int hash = key == null ? 0 : key.hashCode();
946             int index = BasicEMap.this.indexOf(hash);
947             BasicEList eList = entryData[index];
948             if (eList != null)
949             {
950               Entry [] entries = (Entry [])eList.data;
951               int size = eList.size;
952               for (int j = 0; j < size; ++j)
953               {
954                 Entry entry = entries[j];
955                 if (entry.getHash() == hash && entry.equals(otherEntry))
956                 {
957                   return true;
958                 }
959               }
960             }
961           }
962           return false;
963         }
964
965         public boolean remove(Object object)
966         {
967           if (BasicEMap.this.size > 0 && object instanceof Map.Entry )
968           {
969             BasicEMap.this.ensureEntryDataExists();
970             Map.Entry otherEntry = (Map.Entry )object;
971             Object key = otherEntry.getKey();
972             int hash = key == null ? 0 : key.hashCode();
973             int index = BasicEMap.this.indexOf(hash);
974             BasicEList eList = entryData[index];
975             if (eList != null)
976             {
977               Entry [] entries = (Entry [])eList.data;
978               int size = eList.size;
979               for (int j = 0; j < size; ++j)
980               {
981                 Entry entry = entries[j];
982                 if (entry.getHash() == hash && entry.equals(otherEntry))
983                 {
984                   // BasicEMap.this.removeEntry(index, j);
985 remove(otherEntry);
986                   return true;
987                 }
988               }
989             }
990           }
991           return false;
992         }
993
994         public void clear()
995         {
996           BasicEMap.this.clear();
997         }
998
999         public Iterator iterator()
1000        {
1001          return BasicEMap.this.size == 0 ? ECollections.EMPTY_ELIST.iterator() : new BasicEMap.BasicEMapIterator();
1002        }
1003      };
1004    }
1005
1006    return view.entrySet;
1007  }
1008
1009  /**
1010   * A simple and obvious entry implementation.
1011   */
1012  protected class EntryImpl implements Entry
1013  {
1014    /**
1015     * The cached hash code of the key.
1016     */
1017    protected int hash;
1018
1019    /**
1020     * The key.
1021     */
1022    protected Object key;
1023
1024    /**
1025     * The value.
1026     */
1027    protected Object value;
1028  
1029    /**
1030     * Creates a fully initialized instance.
1031     * @param hash the hash code of the key.
1032     * @param key the key.
1033     * @param value the value.
1034     */
1035    public EntryImpl(int hash, Object key, Object value)
1036    {
1037      this.hash = hash;
1038      this.key = key;
1039      this.value = value;
1040    }
1041
1042    /**
1043     * Returns a new entry just like this one.
1044     * @return a new entry just like this one.
1045     */
1046    protected Object clone()
1047    {
1048      return newEntry(hash, key, value);
1049    }
1050
1051    public int getHash()
1052    {
1053      return hash;
1054    }
1055
1056    public void setHash(int hash)
1057    {
1058      this.hash = hash;
1059    }
1060
1061    public Object getKey()
1062    {
1063      return key;
1064    }
1065
1066    public void setKey(Object key)
1067    {
1068      throw new RuntimeException ();
1069    }
1070
1071    public Object getValue()
1072    {
1073      return value;
1074    }
1075
1076    public Object setValue(Object value)
1077    {
1078      BasicEMap.this.validateValue(value);
1079
1080      Object oldValue = this.value;
1081      this.value = value;
1082      return oldValue;
1083    }
1084
1085    public boolean equals(Object object)
1086    {
1087      if (object instanceof Map.Entry )
1088      {
1089        Map.Entry entry = (Map.Entry )object;
1090  
1091        return
1092          (BasicEMap.this.useEqualsForKey() && key != null ? key.equals(entry.getKey()) : key == entry.getKey()) &&
1093          (BasicEMap.this.useEqualsForValue() && value != null ? value.equals(entry.getValue()) : value == entry.getValue());
1094      }
1095      else
1096      {
1097        return false;
1098      }
1099    }
1100
1101    public int hashCode()
1102    {
1103      return hash ^ (value == null ? 0 : value.hashCode());
1104    }
1105
1106    public String toString()
1107    {
1108      return key + "->" + value;
1109    }
1110  }
1111
1112  /**
1113   * An iterator over the map entry data.
1114   */
1115  protected class BasicEMapIterator implements Iterator
1116  {
1117    /**
1118     * The cursor in the entry data.
1119     */
1120    protected int cursor;
1121
1122    /**
1123     * The cursor in the list of entries.
1124     */
1125    protected int entryCursor = -1;
1126
1127    /**
1128     * The last cursor in the entry data.
1129     */
1130    protected int lastCursor;
1131
1132    /**
1133     * The cursor in the list of entries.
1134     */
1135    protected int lastEntryCursor;
1136
1137    /**
1138     * The modification count expected of the map.
1139     */
1140    protected int expectedModCount = modCount;
1141
1142    /**
1143     * Creates an instance.
1144     */
1145    BasicEMapIterator()
1146    {
1147      if (BasicEMap.this.size > 0)
1148      {
1149        scan();
1150      }
1151    }
1152
1153    /**
1154     * Called to yield the iterator result for the entry.
1155     * This implementation returns the entry itself.
1156     * @param entry the entry.
1157     * @return the iterator result for the entry.
1158     */
1159    protected Object yield(Entry entry)
1160    {
1161      return entry;
1162    }
1163
1164    /**
1165     * Scans to the new entry.
1166     */
1167    protected void scan()
1168    {
1169      BasicEMap.this.ensureEntryDataExists();
1170      if (entryCursor != -1)
1171      {
1172        ++entryCursor;
1173        BasicEList eList = BasicEMap.this.entryData[cursor];
1174        if (entryCursor < eList.size)
1175        {
1176          return;
1177        }
1178        ++cursor;
1179      }
1180
1181      for (; cursor < BasicEMap.this.entryData.length; ++cursor)
1182      {
1183        BasicEList eList = BasicEMap.this.entryData[cursor];
1184        if (eList != null && !eList.isEmpty())
1185        {
1186          entryCursor = 0;
1187          return;
1188        }
1189      }
1190
1191      entryCursor = -1;
1192    }
1193
1194    /**
1195     * Returns whether there are more objects.
1196     * @return whether there are more objects.
1197     */
1198    public boolean hasNext()
1199    {
1200      return entryCursor != -1;
1201    }
1202
1203    /**
1204     * Returns the next object and advances the iterator.
1205     * @return the next object.
1206     * @exception NoSuchElementException if the iterator is done.
1207     */
1208    public Object next()
1209    {
1210      if (BasicEMap.this.modCount != expectedModCount)
1211      {
1212        throw new ConcurrentModificationException ();
1213      }
1214
1215      if (entryCursor == -1)
1216      {
1217        throw new NoSuchElementException ();
1218      }
1219
1220      lastCursor = cursor;
1221      lastEntryCursor = entryCursor;
1222
1223      scan();
1224      return yield((Entry)BasicEMap.this.entryData[lastCursor].data[lastEntryCursor]);
1225    }
1226
1227    /**
1228     * Removes the entry of the last object returned by {@link #next()} from the map,
1229     * it's an optional operation.
1230     * @exception IllegalStateException
1231     * if <code>next</code> has not yet been called,
1232     * or <code>remove</code> has already been called after the last call to <code>next</code>.
1233     */
1234    public void remove()
1235    {
1236      if (modCount != expectedModCount)
1237      {
1238        throw new ConcurrentModificationException ();
1239      }
1240
1241      if (lastEntryCursor == -1)
1242      {
1243        throw new IllegalStateException ();
1244      }
1245
1246      delegateEList.remove(entryData[lastCursor].get(lastEntryCursor));
1247
1248      expectedModCount = BasicEMap.this.modCount;
1249      lastEntryCursor = -1;
1250    }
1251  }
1252
1253  /**
1254   * An iterator over the map key data.
1255   */
1256  protected class BasicEMapKeyIterator extends BasicEMapIterator
1257  {
1258    /**
1259     * Creates an instance.
1260     */
1261    BasicEMapKeyIterator()
1262    {
1263    }
1264
1265    /**
1266     * Called to yield the iterator result for the entry.
1267     * This implementation returns the key of the entry.
1268     * @param entry the entry.
1269     * @return the key of the entry.
1270     */
1271    protected Object yield(Entry entry)
1272    {
1273      return entry.getKey();
1274    }
1275  }
1276
1277  /**
1278   * An iterator over the map value data.
1279   */
1280  protected class BasicEMapValueIterator extends BasicEMapIterator
1281  {
1282    /**
1283     * Creates an instance.
1284     */
1285    BasicEMapValueIterator()
1286    {
1287    }
1288
1289    /**
1290     * Called to yield the iterator result for the entry.
1291     * This implementation returns the value of the entry.
1292     * @param entry the entry.
1293     * @return the value of the entry.
1294     */
1295    protected Object yield(Entry entry)
1296    {
1297      return entry.getValue();
1298    }
1299  }
1300
1301  /**
1302   * Called to return the hash code of the key.
1303   * @param key the key.
1304   * @return the hash code of the object.
1305   */
1306  protected int hashOf(Object key)
1307  {
1308    return key == null ? 0 : key.hashCode();
1309  }
1310
1311  /**
1312   * Called to return the entry data index corresponding to the hash code.
1313   * @param hash the hash code.
1314   * @return the index corresponding to the hash code.
1315   */
1316  protected int indexOf(int hash)
1317  {
1318    return (hash & 0x7FFFFFFF) % entryData.length;
1319  }
1320
1321  /**
1322   * Called to return the entry given the index, the hash, and the key.
1323   * @param index the entry data index of the key.
1324   * @param hash the hash code of the key.
1325   * @param key the key.
1326   * @return the entry.
1327   */
1328  protected Entry entryForKey(int index, int hash, Object key)
1329  {
1330    BasicEList eList = entryData[index];
1331    if (eList != null)
1332    {
1333      Entry [] entries = (Entry [])eList.data;
1334      int size = eList.size;
1335      if (useEqualsForKey() && key != null)
1336      {
1337        for (int j = 0; j < size; ++j)
1338        {
1339          Entry entry = entries[j];
1340          if (entry.getHash() == hash && key.equals(entry.getKey()))
1341          {
1342            return entry;
1343          }
1344        }
1345      }
1346      else
1347      {
1348        for (int j = 0; j < size; ++j)
1349        {
1350          Entry entry = entries[j];
1351          if (entry.getKey() == key)
1352          {
1353            return entry;
1354          }
1355        }
1356      }
1357    }
1358
1359    return null;
1360  }
1361
1362  /**
1363   * Called to return the entry list index given the index, the hash, and the key.
1364   * @param index the entry data index of the key.
1365   * @param hash the hash code of the key.
1366   * @param key the key.
1367   * @return the entry list index.
1368   */
1369  protected int entryIndexForKey(int index, int hash, Object key)
1370  {
1371    if (useEqualsForKey() && key != null)
1372    {
1373      BasicEList eList = entryData[index];
1374      if (eList != null)
1375      {
1376        Entry [] entries = (Entry [])eList.data;
1377        int size = eList.size;
1378        for (int j = 0; j < size; ++j)
1379        {
1380          Entry entry = entries[j];
1381          if (entry.getHash() == hash && key.equals(entry.getKey()))
1382          {
1383            return j;
1384          }
1385        }
1386      }
1387    }
1388    else
1389    {
1390      BasicEList eList = entryData[index];
1391      if (eList != null)
1392      {
1393        Entry [] entries = (Entry [])eList.data;
1394        int size = eList.size;
1395        for (int j = 0; j < size; ++j)
1396        {
1397          Entry entry = entries[j];
1398          if (entry.getKey() == key)
1399          {
1400            return j;
1401          }
1402        }
1403      }
1404    }
1405
1406    return -1;
1407  }
1408
1409  /**
1410   * Grows the capacity of the map
1411   * to ensure that no additional growth is needed until the size exceeds the specified minimun capacity.
1412   */
1413  protected boolean grow(int minimumCapacity)
1414  {
1415    ++modCount;
1416    int oldCapacity = entryData == null ? 0 : entryData.length;
1417    if (minimumCapacity > oldCapacity)
1418    {
1419      BasicEList [] oldEntryData = entryData;
1420      entryData = newEntryData(2 * oldCapacity + 4);
1421
1422      for (int i = 0; i < oldCapacity; ++i)
1423      {
1424        BasicEList oldEList = oldEntryData[i];
1425        if (oldEList != null)
1426        {
1427          Entry [] entries = (Entry [])oldEList.data;
1428          int size = oldEList.size;
1429          for (int j = 0; j < size; ++j)
1430          {
1431            Entry entry = entries[j];
1432            int index = indexOf(entry.getHash());
1433            BasicEList eList = entryData[index];
1434            if (eList == null)
1435            {
1436              eList = entryData[index] = newList();
1437            }
1438            eList.add(entry);
1439          }
1440        }
1441      }
1442
1443      return true;
1444    }
1445    else
1446    {
1447      return false;
1448    }
1449  }
1450
1451  private void writeObject(ObjectOutputStream objectOutputStream) throws IOException
1452  {
1453    objectOutputStream.defaultWriteObject();
1454
1455    if (entryData == null)
1456    {
1457      objectOutputStream.writeInt(0);
1458    }
1459    else
1460    {
1461      // Write the capacity.
1462 //
1463 objectOutputStream.writeInt(entryData.length);
1464  
1465      // Write all the entryData; there will be size of them.
1466 //
1467 for (int i = 0; i < entryData.length; ++i)
1468      {
1469        BasicEList eList = entryData[i];
1470        if (eList != null)
1471        {
1472          Entry [] entries = (Entry [])eList.data;
1473          int size = eList.size;
1474          for (int j = 0; j < size; ++j)
1475          {
1476            Entry entry = entries[j];
1477            objectOutputStream.writeObject(entry.getKey());
1478            objectOutputStream.writeObject(entry.getValue());
1479          }
1480        }
1481      }
1482    }
1483  }
1484
1485  private void readObject(ObjectInputStream objectInputStream) throws IOException , ClassNotFoundException
1486  {
1487    objectInputStream.defaultReadObject();
1488  
1489    // Restore the capacity, if there was any.
1490 //
1491 int capacity = objectInputStream.readInt();
1492    if (capacity > 0)
1493    {
1494      entryData = newEntryData(capacity);
1495    
1496      // Read all size number of entryData.
1497 //
1498 for (int i = 0; i < size; ++i)
1499      {
1500        Object key = objectInputStream.readObject();
1501        Object value = objectInputStream.readObject();
1502        put(key, value);
1503      }
1504    }
1505  }
1506
1507  /**
1508   * Delegates to {@link #delegateEList}.
1509   */
1510  public boolean contains(Object object)
1511  {
1512    return delegateEList.contains(object);
1513  }
1514
1515  /**
1516   * Delegates to {@link #delegateEList}.
1517   */
1518  public boolean containsAll(Collection collection)
1519  {
1520    return delegateEList.containsAll(collection);
1521  }
1522
1523  /**
1524   * Delegates to {@link #delegateEList}.
1525   */
1526  public int indexOf(Object object)
1527  {
1528    return delegateEList.indexOf(object);
1529  }
1530
1531  /**
1532   * Delegates to {@link #delegateEList}.
1533   */
1534  public int lastIndexOf(Object object)
1535  {
1536    return delegateEList.lastIndexOf(object);
1537  }
1538
1539  /**
1540   * Delegates to {@link #delegateEList}.
1541   */
1542  public Object [] toArray()
1543  {
1544    return delegateEList.toArray();
1545  }
1546
1547  /**
1548   * Delegates to {@link #delegateEList}.
1549   */
1550  public Object [] toArray(Object array[])
1551  {
1552    return delegateEList.toArray(array);
1553  }
1554
1555  /**
1556   * Delegates to {@link #delegateEList}.
1557   */
1558  public Object get(int index)
1559  {
1560    return delegateEList.get(index);
1561  }
1562
1563  /**
1564   * Delegates to {@link #delegateEList}.
1565   */
1566  public Object set(int index, Object object)
1567  {
1568    return delegateEList.set(index, object);
1569  }
1570
1571  /**
1572   * Delegates to {@link #delegateEList}.
1573   */
1574  public boolean add(Object object)
1575  {
1576    return delegateEList.add(object);
1577  }
1578
1579  /**
1580   * Delegates to {@link #delegateEList}.
1581   */
1582  public void add(int index, Object object)
1583  {
1584    delegateEList.add(index, object);
1585  }
1586
1587  /**
1588   * Delegates to {@link #delegateEList}.
1589   */
1590  public boolean addAll(Collection collection)
1591  {
1592    return delegateEList.addAll(collection);
1593  }
1594
1595  /**
1596   * Delegates to {@link #delegateEList}.
1597   */
1598  public boolean addAll(int index, Collection collection)
1599  {
1600    return delegateEList.addAll(index, collection);
1601  }
1602
1603  /**
1604   * Delegates to {@link #delegateEList}.
1605   */
1606  public boolean remove(Object object)
1607  {
1608    if (object instanceof Map.Entry )
1609    {
1610      return delegateEList.remove(object);
1611    }
1612    else
1613    {
1614      boolean result = containsKey(object);
1615      removeKey(object);
1616      return result;
1617    }
1618  }
1619
1620  /**
1621   * Delegates to {@link #delegateEList}.
1622   */
1623  public boolean removeAll(Collection collection)
1624  {
1625    return delegateEList.removeAll(collection);
1626  }
1627
1628  /**
1629   * Delegates to {@link #delegateEList}.
1630   */
1631  public Object remove(int index)
1632  {
1633    return delegateEList.remove(index);
1634  }
1635
1636  /**
1637   * Delegates to {@link #delegateEList}.
1638   */
1639  public boolean retainAll(Collection collection)
1640  {
1641    return delegateEList.retainAll(collection);
1642  }
1643
1644  /**
1645   * Delegates to {@link #delegateEList}.
1646   */
1647  public void clear()
1648  {
1649    delegateEList.clear();
1650  }
1651
1652  /**
1653   * Delegates to {@link #delegateEList}.
1654   */
1655  public void move(int index, Object object)
1656  {
1657    delegateEList.move(index, object);
1658  }
1659
1660  /**
1661   * Delegates to {@link #delegateEList}.
1662   */
1663  public Object move(int targetIndex, int sourceIndex)
1664  {
1665    return delegateEList.move(targetIndex, sourceIndex);
1666  }
1667
1668  /**
1669   * Delegates to {@link #delegateEList}.
1670   */
1671  public Iterator iterator()
1672  {
1673    return delegateEList.iterator();
1674  }
1675
1676  /**
1677   * Delegates to {@link #delegateEList}.
1678   */
1679  public ListIterator listIterator()
1680  {
1681    return delegateEList.listIterator();
1682  }
1683
1684  /**
1685   * Delegates to {@link #delegateEList}.
1686   */
1687  public ListIterator listIterator(int index)
1688  {
1689    return delegateEList.listIterator(index);
1690  }
1691
1692  /**
1693   * Delegates to {@link #delegateEList}.
1694   */
1695  public List subList(int start, int end)
1696  {
1697    return delegateEList.subList(start, end);
1698  }
1699
1700  public int hashCode()
1701  {
1702    return delegateEList.hashCode();
1703  }
1704
1705  public boolean equals(Object object)
1706  {
1707    if (object instanceof EMap)
1708    {
1709      return delegateEList.equals(object);
1710    }
1711    else
1712    {
1713      return false;
1714    }
1715  }
1716
1717  /**
1718   * Delegates to {@link #delegateEList}.
1719   */
1720  public String toString()
1721  {
1722    return delegateEList.toString();
1723  }
1724}
1725

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags