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