001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package java.util;
019:
020: /**
021: * LinkedHashMap is a variant on HashMap. Its entries are kept in a
022: * doubly-linked list. The iteration order is, by default, the order in which
023: * keys were inserted.
024: * <p>
025: * If the three argument constructor is used, and <code>order</code> is
026: * specified as <code>true</code>, the iteration would be in the order that
027: * entries were accessed. The access order gets affected by put(), get(),
028: * putAll() operations, but not by operations on the collection views.
029: * <p>
030: * Null elements are allowed, and all the optional Map operations are supported.
031: * <p>
032: *
033: * @since 1.4
034: */
035: public class LinkedHashMap<K, V> extends HashMap<K, V> {
036:
037: private static final long serialVersionUID = 3801124242820219131L;
038:
039: private final boolean accessOrder;
040:
041: transient private LinkedHashMapEntry<K, V> head, tail;
042:
043: /**
044: * Constructs a new empty instance of LinkedHashMap.
045: */
046: public LinkedHashMap() {
047: super ();
048: accessOrder = false;
049: head = null;
050: }
051:
052: /**
053: * Constructor with specified size.
054: *
055: * @param s
056: * Size of LinkedHashMap required
057: */
058: public LinkedHashMap(int s) {
059: super (s);
060: accessOrder = false;
061: head = null;
062: }
063:
064: /**
065: * Constructor with specified size and load factor.
066: *
067: * @param s
068: * Size of LinkedHashMap required
069: * @param lf
070: * Load factor
071: */
072: public LinkedHashMap(int s, float lf) {
073: super (s, lf);
074: accessOrder = false;
075: head = null;
076: tail = null;
077: }
078:
079: /**
080: * Constructor with specified size, load factor and access order
081: *
082: * @param s
083: * Size of LinkedHashmap required
084: * @param lf
085: * Load factor
086: * @param order
087: * If true indicates that traversal order should begin with most
088: * recently accessed
089: */
090: public LinkedHashMap(int s, float lf, boolean order) {
091: super (s, lf);
092: accessOrder = order;
093: head = null;
094: tail = null;
095: }
096:
097: /**
098: * Constructor with input map
099: *
100: * @param m
101: * Input map
102: */
103: public LinkedHashMap(Map<? extends K, ? extends V> m) {
104: accessOrder = false;
105: head = null;
106: tail = null;
107: putAll(m);
108: }
109:
110: private static class AbstractMapIterator<K, V> {
111: int expectedModCount;
112: LinkedHashMapEntry<K, V> futureEntry;
113: LinkedHashMapEntry<K, V> currentEntry;
114: final LinkedHashMap<K, V> associatedMap;
115:
116: AbstractMapIterator(LinkedHashMap<K, V> map) {
117: expectedModCount = map.modCount;
118: futureEntry = map.head;
119: associatedMap = map;
120: }
121:
122: public boolean hasNext() {
123: return (futureEntry != null);
124: }
125:
126: final void checkConcurrentMod()
127: throws ConcurrentModificationException {
128: if (expectedModCount != associatedMap.modCount) {
129: throw new ConcurrentModificationException();
130: }
131: }
132:
133: final void makeNext() {
134: checkConcurrentMod();
135: if (!hasNext()) {
136: throw new NoSuchElementException();
137: }
138: currentEntry = futureEntry;
139: futureEntry = futureEntry.chainForward;
140: }
141:
142: public void remove() {
143: checkConcurrentMod();
144: if (currentEntry == null) {
145: throw new IllegalStateException();
146: }
147: associatedMap.removeEntry(currentEntry);
148: LinkedHashMapEntry<K, V> lhme = currentEntry;
149: LinkedHashMapEntry<K, V> p = lhme.chainBackward;
150: LinkedHashMapEntry<K, V> n = lhme.chainForward;
151: LinkedHashMap<K, V> lhm = associatedMap;
152: if (p != null) {
153: p.chainForward = n;
154: if (n != null) {
155: n.chainBackward = p;
156: } else {
157: lhm.tail = p;
158: }
159: } else {
160: lhm.head = n;
161: if (n != null) {
162: n.chainBackward = null;
163: } else {
164: lhm.tail = null;
165: }
166: }
167: currentEntry = null;
168: expectedModCount++;
169: }
170: }
171:
172: private static class EntryIterator<K, V> extends
173: AbstractMapIterator<K, V> implements
174: Iterator<Map.Entry<K, V>> {
175:
176: EntryIterator(LinkedHashMap<K, V> map) {
177: super (map);
178: }
179:
180: public Map.Entry<K, V> next() {
181: makeNext();
182: return currentEntry;
183: }
184: }
185:
186: private static class KeyIterator<K, V> extends
187: AbstractMapIterator<K, V> implements Iterator<K> {
188:
189: KeyIterator(LinkedHashMap<K, V> map) {
190: super (map);
191: }
192:
193: public K next() {
194: makeNext();
195: return currentEntry.key;
196: }
197: }
198:
199: private static class ValueIterator<K, V> extends
200: AbstractMapIterator<K, V> implements Iterator<V> {
201:
202: ValueIterator(LinkedHashMap<K, V> map) {
203: super (map);
204: }
205:
206: public V next() {
207: makeNext();
208: return currentEntry.value;
209: }
210: }
211:
212: static final class LinkedHashMapEntrySet<KT, VT> extends
213: HashMapEntrySet<KT, VT> {
214: public LinkedHashMapEntrySet(LinkedHashMap<KT, VT> lhm) {
215: super (lhm);
216: }
217:
218: @Override
219: public Iterator<Map.Entry<KT, VT>> iterator() {
220: return new EntryIterator<KT, VT>(
221: (LinkedHashMap<KT, VT>) hashMap());
222: }
223: }
224:
225: static final class LinkedHashMapEntry<K, V> extends Entry<K, V> {
226: LinkedHashMapEntry<K, V> chainForward, chainBackward;
227:
228: LinkedHashMapEntry(K theKey, V theValue) {
229: super (theKey, theValue);
230: chainForward = null;
231: chainBackward = null;
232: }
233:
234: LinkedHashMapEntry(K theKey, int hash) {
235: super (theKey, hash);
236: chainForward = null;
237: chainBackward = null;
238: }
239:
240: @Override
241: @SuppressWarnings("unchecked")
242: public Object clone() {
243: LinkedHashMapEntry<K, V> entry = (LinkedHashMapEntry<K, V>) super
244: .clone();
245: entry.chainBackward = chainBackward;
246: entry.chainForward = chainForward;
247: LinkedHashMapEntry<K, V> lnext = (LinkedHashMapEntry<K, V>) entry.next;
248: if (lnext != null) {
249: entry.next = (LinkedHashMapEntry<K, V>) lnext.clone();
250: }
251: return entry;
252: }
253: }
254:
255: /**
256: * Searches this map for the specified value.
257: *
258: * @param value
259: * the object to search for
260: * @return true if <code>value</code> is a value of this HashMap, false
261: * otherwise
262: */
263: @Override
264: public boolean containsValue(Object value) {
265: LinkedHashMapEntry<K, V> entry = head;
266: if (null == value) {
267: while (null != entry) {
268: if (null == entry.value) {
269: return true;
270: }
271: entry = entry.chainForward;
272: }
273: } else {
274: while (null != entry) {
275: if (value.equals(entry.value)) {
276: return true;
277: }
278: entry = entry.chainForward;
279: }
280: }
281: return false;
282: }
283:
284: /**
285: * Create a new element array
286: *
287: * @param s
288: * @return Reference to the element array
289: */
290: @Override
291: @SuppressWarnings("unchecked")
292: Entry<K, V>[] newElementArray(int s) {
293: return new LinkedHashMapEntry[s];
294: }
295:
296: /**
297: * Retrieve the map value corresponding to the given key.
298: *
299: * @param key
300: * Key value
301: * @return mapped value or null if the key is not in the map
302: */
303: @Override
304: public V get(Object key) {
305: LinkedHashMapEntry<K, V> m;
306: if (key == null) {
307: m = (LinkedHashMapEntry<K, V>) findNullKeyEntry();
308: } else {
309: int hash = key.hashCode();
310: int index = (hash & 0x7FFFFFFF) % elementData.length;
311: m = (LinkedHashMapEntry<K, V>) findNonNullKeyEntry(key,
312: index, hash);
313: }
314: if (m == null) {
315: return null;
316: }
317: if (accessOrder && tail != m) {
318: LinkedHashMapEntry<K, V> p = m.chainBackward;
319: LinkedHashMapEntry<K, V> n = m.chainForward;
320: n.chainBackward = p;
321: if (p != null) {
322: p.chainForward = n;
323: } else {
324: head = n;
325: }
326: m.chainForward = null;
327: m.chainBackward = tail;
328: tail.chainForward = m;
329: tail = m;
330: }
331: return m.value;
332: }
333:
334: /*
335: * @param key @param index @return Entry
336: */
337: @Override
338: Entry<K, V> createEntry(K key, int index, V value) {
339: LinkedHashMapEntry<K, V> m = new LinkedHashMapEntry<K, V>(key,
340: value);
341: m.next = elementData[index];
342: elementData[index] = m;
343: linkEntry(m);
344: return m;
345: }
346:
347: Entry<K, V> createHashedEntry(K key, int index, int hash) {
348: LinkedHashMapEntry<K, V> m = new LinkedHashMapEntry<K, V>(key,
349: hash);
350: m.next = elementData[index];
351: elementData[index] = m;
352: linkEntry(m);
353: return m;
354: }
355:
356: /**
357: * Set the mapped value for the given key to the given value.
358: *
359: * @param key
360: * Key value
361: * @param value
362: * New mapped value
363: * @return The old value if the key was already in the map or null
364: * otherwise.
365: */
366: @Override
367: public V put(K key, V value) {
368: V result = putImpl(key, value);
369:
370: if (removeEldestEntry(head)) {
371: remove(head.key);
372: }
373:
374: return result;
375: }
376:
377: V putImpl(K key, V value) {
378: LinkedHashMapEntry<K, V> m;
379: if (elementCount == 0) {
380: head = tail = null;
381: }
382: if (key == null) {
383: m = (LinkedHashMapEntry<K, V>) findNullKeyEntry();
384: if (m == null) {
385: modCount++;
386: // Check if we need to remove the oldest entry. The check
387: // includes accessOrder since an accessOrder LinkedHashMap does
388: // not record the oldest member in 'head'.
389: if (++elementCount > threshold) {
390: rehash();
391: }
392: m = (LinkedHashMapEntry<K, V>) createHashedEntry(null,
393: 0, 0);
394: } else {
395: linkEntry(m);
396: }
397: } else {
398: int hash = key.hashCode();
399: int index = (hash & 0x7FFFFFFF) % elementData.length;
400: m = (LinkedHashMapEntry<K, V>) findNonNullKeyEntry(key,
401: index, hash);
402: if (m == null) {
403: modCount++;
404: if (++elementCount > threshold) {
405: rehash();
406: index = (hash & 0x7FFFFFFF) % elementData.length;
407: }
408: m = (LinkedHashMapEntry<K, V>) createHashedEntry(key,
409: index, hash);
410: } else {
411: linkEntry(m);
412: }
413: }
414:
415: V result = m.value;
416: m.value = value;
417: return result;
418: }
419:
420: /*
421: * @param m
422: */
423: void linkEntry(LinkedHashMapEntry<K, V> m) {
424: if (tail == m) {
425: return;
426: }
427:
428: if (head == null) {
429: // Check if the map is empty
430: head = tail = m;
431: return;
432: }
433:
434: // we need to link the new entry into either the head or tail
435: // of the chain depending on if the LinkedHashMap is accessOrder or not
436: LinkedHashMapEntry<K, V> p = m.chainBackward;
437: LinkedHashMapEntry<K, V> n = m.chainForward;
438: if (p == null) {
439: if (n != null) {
440: // The entry must be the head but not the tail
441: if (accessOrder) {
442: head = n;
443: n.chainBackward = null;
444: m.chainBackward = tail;
445: m.chainForward = null;
446: tail.chainForward = m;
447: tail = m;
448: }
449: } else {
450: // This is a new entry
451: m.chainBackward = tail;
452: m.chainForward = null;
453: tail.chainForward = m;
454: tail = m;
455: }
456: return;
457: }
458:
459: if (n == null) {
460: // The entry must be the tail so we can't get here
461: return;
462: }
463:
464: // The entry is neither the head nor tail
465: if (accessOrder) {
466: p.chainForward = n;
467: n.chainBackward = p;
468: m.chainForward = null;
469: m.chainBackward = tail;
470: tail.chainForward = m;
471: tail = m;
472: }
473: }
474:
475: /**
476: * Answers a Set of the mappings contained in this HashMap. Each element in
477: * the set is a Map.Entry. The set is backed by this HashMap so changes to
478: * one are reflected by the other. The set does not support adding.
479: *
480: * @return a Set of the mappings
481: */
482: @Override
483: public Set<Map.Entry<K, V>> entrySet() {
484: return new LinkedHashMapEntrySet<K, V>(this );
485: }
486:
487: /**
488: * Answers a Set of the keys contained in this HashMap. The set is backed by
489: * this HashMap so changes to one are reflected by the other. The set does
490: * not support adding.
491: *
492: * @return a Set of the keys
493: */
494: @Override
495: public Set<K> keySet() {
496: if (keySet == null) {
497: keySet = new AbstractSet<K>() {
498: @Override
499: public boolean contains(Object object) {
500: return containsKey(object);
501: }
502:
503: @Override
504: public int size() {
505: return LinkedHashMap.this .size();
506: }
507:
508: @Override
509: public void clear() {
510: LinkedHashMap.this .clear();
511: }
512:
513: @Override
514: public boolean remove(Object key) {
515: if (containsKey(key)) {
516: LinkedHashMap.this .remove(key);
517: return true;
518: }
519: return false;
520: }
521:
522: @Override
523: public Iterator<K> iterator() {
524: return new KeyIterator<K, V>(LinkedHashMap.this );
525: }
526: };
527: }
528: return keySet;
529: }
530:
531: /**
532: * Answers a Collection of the values contained in this HashMap. The
533: * collection is backed by this HashMap so changes to one are reflected by
534: * the other. The collection does not support adding.
535: *
536: * @return a Collection of the values
537: */
538: @Override
539: public Collection<V> values() {
540: if (valuesCollection == null) {
541: valuesCollection = new AbstractCollection<V>() {
542: @Override
543: public boolean contains(Object object) {
544: return containsValue(object);
545: }
546:
547: @Override
548: public int size() {
549: return LinkedHashMap.this .size();
550: }
551:
552: @Override
553: public void clear() {
554: LinkedHashMap.this .clear();
555: }
556:
557: @Override
558: public Iterator<V> iterator() {
559: return new ValueIterator<K, V>(LinkedHashMap.this );
560: }
561: };
562: }
563: return valuesCollection;
564: }
565:
566: /**
567: * Remove the entry corresponding to the given key.
568: *
569: * @param key
570: * the key
571: * @return the value associated with the key or null if the key was no in
572: * the map
573: */
574: @Override
575: public V remove(Object key) {
576: LinkedHashMapEntry<K, V> m = (LinkedHashMapEntry<K, V>) removeEntry(key);
577: if (m == null) {
578: return null;
579: }
580: LinkedHashMapEntry<K, V> p = m.chainBackward;
581: LinkedHashMapEntry<K, V> n = m.chainForward;
582: if (p != null) {
583: p.chainForward = n;
584: } else {
585: head = n;
586: }
587: if (n != null) {
588: n.chainBackward = p;
589: } else {
590: tail = p;
591: }
592: return m.value;
593: }
594:
595: /**
596: * This method is queried from the put and putAll methods to check if the
597: * eldest member of the map should be deleted before adding the new member.
598: * If this map was created with accessOrder = true, then the result of
599: * removeEldesrEntry is assumed to be false.
600: *
601: * @param eldest
602: * @return true if the eldest member should be removed
603: */
604: protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
605: return false;
606: }
607:
608: /**
609: * Removes all mappings from this HashMap, leaving it empty.
610: *
611: * @see #isEmpty()
612: * @see #size()
613: */
614: @Override
615: public void clear() {
616: super.clear();
617: head = tail = null;
618: }
619: }
|