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 th