1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections.map;
18
19 import java.util.ConcurrentModificationException;
20 import java.util.Iterator;
21 import java.util.Map;
22 import java.util.NoSuchElementException;
23
24 import org.apache.commons.collections.OrderedIterator;
25 import org.apache.commons.collections.OrderedMap;
26 import org.apache.commons.collections.OrderedMapIterator;
27 import org.apache.commons.collections.ResettableIterator;
28 import org.apache.commons.collections.iterators.EmptyOrderedIterator;
29 import org.apache.commons.collections.iterators.EmptyOrderedMapIterator;
30
31 /**
32 * An abstract implementation of a hash-based map that links entries to create an
33 * ordered map and which provides numerous points for subclasses to override.
34 * <p>
35 * This class implements all the features necessary for a subclass linked
36 * hash-based map. Key-value entries are stored in instances of the
37 * <code>LinkEntry</code> class which can be overridden and replaced.
38 * The iterators can similarly be replaced, without the need to replace the KeySet,
39 * EntrySet and Values view classes.
40 * <p>
41 * Overridable methods are provided to change the default hashing behaviour, and
42 * to change how entries are added to and removed from the map. Hopefully, all you
43 * need for unusual subclasses is here.
44 * <p>
45 * This implementation maintains order by original insertion, but subclasses
46 * may work differently. The <code>OrderedMap</code> interface is implemented
47 * to provide access to bidirectional iteration and extra convenience methods.
48 * <p>
49 * The <code>orderedMapIterator()</code> method provides direct access to a
50 * bidirectional iterator. The iterators from the other views can also be cast
51 * to <code>OrderedIterator</code> if required.
52 * <p>
53 * All the available iterators can be reset back to the start by casting to
54 * <code>ResettableIterator</code> and calling <code>reset()</code>.
55 * <p>
56 * The implementation is also designed to be subclassed, with lots of useful
57 * methods exposed.
58 *
59 * @since 3.0
60 * @version $Id: AbstractLinkedMap.java 1429905 2013-01-07 17:15:14Z ggregory $
61 */
62 public abstract class AbstractLinkedMap<K, V> extends AbstractHashedMap<K, V> implements OrderedMap<K, V> {
63
64 /** Header in the linked list */
65 protected transient LinkEntry<K, V> header;
66
67 /**
68 * Constructor only used in deserialization, do not use otherwise.
69 */
70 protected AbstractLinkedMap() {
71 super();
72 }
73
74 /**
75 * Constructor which performs no validation on the passed in parameters.
76 *
77 * @param initialCapacity the initial capacity, must be a power of two
78 * @param loadFactor the load factor, must be > 0.0f and generally < 1.0f
79 * @param threshold the threshold, must be sensible
80 */
81 protected AbstractLinkedMap(final int initialCapacity, final float loadFactor, final int threshold) {
82 super(initialCapacity, loadFactor, threshold);
83 }
84
85 /**
86 * Constructs a new, empty map with the specified initial capacity.
87 *
88 * @param initialCapacity the initial capacity
89 * @throws IllegalArgumentException if the initial capacity is negative
90 */
91 protected AbstractLinkedMap(final int initialCapacity) {
92 super(initialCapacity);
93 }
94
95 /**
96 * Constructs a new, empty map with the specified initial capacity and
97 * load factor.
98 *
99 * @param initialCapacity the initial capacity
100 * @param loadFactor the load factor
101 * @throws IllegalArgumentException if the initial capacity is negative
102 * @throws IllegalArgumentException if the load factor is less than zero
103 */
104 protected AbstractLinkedMap(final int initialCapacity, final float loadFactor) {
105 super(initialCapacity, loadFactor);
106 }
107
108 /**
109 * Constructor copying elements from another map.
110 *
111 * @param map the map to copy
112 * @throws NullPointerException if the map is null
113 */
114 protected AbstractLinkedMap(final Map<K, V> map) {
115 super(map);
116 }
117
118 /**
119 * Initialise this subclass during construction.
120 * <p>
121 * NOTE: As from v3.2 this method calls
122 * {@link #createEntry(HashEntry, int, Object, Object)} to create
123 * the map entry object.
124 */
125 @Override
126 protected void init() {
127 header = createEntry(null, -1, null, null);
128 header.before = header.after = header;
129 }
130
131 //-----------------------------------------------------------------------
132 /**
133 * Checks whether the map contains the specified value.
134 *
135 * @param value the value to search for
136 * @return true if the map contains the value
137 */
138 @Override
139 public boolean containsValue(final Object value) {
140 // override uses faster iterator
141 if (value == null) {
142 for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after) {
143 if (entry.getValue() == null) {
144 return true;
145 }
146 }
147 } else {
148 for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after) {
149 if (isEqualValue(value, entry.getValue())) {
150 return true;
151 }
152 }
153 }
154 return false;
155 }
156
157 /**
158 * Clears the map, resetting the size to zero and nullifying references
159 * to avoid garbage collection issues.
160 */
161 @Override
162 public void clear() {
163 // override to reset the linked list
164 super.clear();
165 header.before = header.after = header;
166 }
167
168 //-----------------------------------------------------------------------
169 /**
170 * Gets the first key in the map, which is the first inserted.
171 *
172 * @return the eldest key
173 */
174 public K firstKey() {
175 if (size == 0) {
176 throw new NoSuchElementException("Map is empty");
177 }
178 return header.after.getKey();
179 }
180
181 /**
182 * Gets the last key in the map, which is the most recently inserted.
183 *
184 * @return the most recently inserted key
185 */
186 public K lastKey() {
187 if (size == 0) {
188 throw new NoSuchElementException("Map is empty");
189 }
190 return header.before.getKey();
191 }
192
193 /**
194 * Gets the next key in sequence.
195 *
196 * @param key the key to get after
197 * @return the next key
198 */
199 public K nextKey(final Object key) {
200 final LinkEntry<K, V> entry = getEntry(key);
201 return entry == null || entry.after == header ? null : entry.after.getKey();
202 }
203
204 @Override
205 protected LinkEntry<K, V> getEntry(final Object key) {
206 return (LinkEntry<K, V>) super.getEntry(key);
207 }
208
209 /**
210 * Gets the previous key in sequence.
211 *
212 * @param key the key to get before
213 * @return the previous key
214 */
215 public K previousKey(final Object key) {
216 final LinkEntry<K, V> entry = getEntry(key);
217 return entry == null || entry.before == header ? null : entry.before.getKey();
218 }
219
220 //-----------------------------------------------------------------------
221 /**
222 * Gets the key at the specified index.
223 *
224 * @param index the index to retrieve
225 * @return the key at the specified index
226 * @throws IndexOutOfBoundsException if the index is invalid
227 */
228 protected LinkEntry<K, V> getEntry(final int index) {
229 if (index < 0) {
230 throw new IndexOutOfBoundsException("Index " + index + " is less than zero");
231 }
232 if (index >= size) {
233 throw new IndexOutOfBoundsException("Index " + index + " is invalid for size " + size);
234 }
235 LinkEntry<K, V> entry;
236 if (index < size / 2) {
237 // Search forwards
238 entry = header.after;
239 for (int currentIndex = 0; currentIndex < index; currentIndex++) {
240 entry = entry.after;
241 }
242 } else {
243 // Search backwards
244 entry = header;
245 for (int currentIndex = size; currentIndex > index; currentIndex--) {
246 entry = entry.before;
247 }
248 }
249 return entry;
250 }
251
252 /**
253 * Adds an entry into this map, maintaining insertion order.
254 * <p>
255 * This implementation adds the entry to the data storage table and
256 * to the end of the linked list.
257 *
258 * @param entry the entry to add
259 * @param hashIndex the index into the data array to store at
260 */
261 @Override
262 protected void addEntry(final HashEntry<K, V> entry, final int hashIndex) {
263 final LinkEntry<K, V> link = (LinkEntry<K, V>) entry;
264 link.after = header;
265 link.before = header.before;
266 header.before.after = link;
267 header.before = link;
268 data[hashIndex] = link;
269 }
270
271 /**
272 * Creates an entry to store the data.
273 * <p>
274 * This implementation creates a new LinkEntry instance.
275 *
276 * @param next the next entry in sequence
277 * @param hashCode the hash code to use
278 * @param key the key to store
279 * @param value the value to store
280 * @return the newly created entry
281 */
282 @Override
283 protected LinkEntry<K, V> createEntry(final HashEntry<K, V> next, final int hashCode, final K key, final V value) {
284 return new LinkEntry<K, V>(next, hashCode, convertKey(key), value);
285 }
286
287 /**
288 * Removes an entry from the map and the linked list.
289 * <p>
290 * This implementation removes the entry from the linked list chain, then
291 * calls the superclass implementation.
292 *
293 * @param entry the entry to remove
294 * @param hashIndex the index into the data structure
295 * @param previous the previous entry in the chain
296 */
297 @Override
298 protected void removeEntry(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> previous) {
299 final LinkEntry<K, V> link = (LinkEntry<K, V>) entry;
300 link.before.after = link.after;
301 link.after.before = link.before;
302 link.after = null;
303 link.before = null;
304 super.removeEntry(entry, hashIndex, previous);
305 }
306
307 //-----------------------------------------------------------------------
308 /**
309 * Gets the <code>before</code> field from a <code>LinkEntry</code>.
310 * Used in subclasses that have no visibility of the field.
311 *
312 * @param entry the entry to query, must not be null
313 * @return the <code>before</code> field of the entry
314 * @throws NullPointerException if the entry is null
315 * @since 3.1
316 */
317 protected LinkEntry<K, V> entryBefore(final LinkEntry<K, V> entry) {
318 return entry.before;
319 }
320
321 /**
322 * Gets the <code>after</code> field from a <code>LinkEntry</code>.
323 * Used in subclasses that have no visibility of the field.
324 *
325 * @param entry the entry to query, must not be null
326 * @return the <code>after</code> field of the entry
327 * @throws NullPointerException if the entry is null
328 * @since 3.1
329 */
330 protected LinkEntry<K, V> entryAfter(final LinkEntry<K, V> entry) {
331 return entry.after;
332 }
333
334 //-----------------------------------------------------------------------
335 /**
336 * {@inheritDoc}
337 */
338 @Override
339 public OrderedMapIterator<K, V> mapIterator() {
340 if (size == 0) {
341 return EmptyOrderedMapIterator.<K, V>emptyOrderedMapIterator();
342 }
343 return new LinkMapIterator<K, V>(this);
344 }
345
346 /**
347 * MapIterator implementation.
348 */
349 protected static class LinkMapIterator<K, V> extends LinkIterator<K, V> implements
350 OrderedMapIterator<K, V>, ResettableIterator<K> {
351
352 protected LinkMapIterator(final AbstractLinkedMap<K, V> parent) {
353 super(parent);
354 }
355
356 public K next() {
357 return super.nextEntry().getKey();
358 }
359
360 public K previous() {
361 return super.previousEntry().getKey();
362 }
363
364 public K getKey() {
365 final LinkEntry<K, V> current = currentEntry();
366 if (current == null) {
367 throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
368 }
369 return current.getKey();
370 }
371
372 public V getValue() {
373 final LinkEntry<K, V> current = currentEntry();
374 if (current == null) {
375 throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
376 }
377 return current.getValue();
378 }
379
380 public V setValue(final V value) {
381 final LinkEntry<K, V> current = currentEntry();
382 if (current == null) {
383 throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
384 }
385 return current.setValue(value);
386 }
387 }
388
389 //-----------------------------------------------------------------------
390 /**
391 * Creates an entry set iterator.
392 * Subclasses can override this to return iterators with different properties.
393 *
394 * @return the entrySet iterator
395 */
396 @Override
397 protected Iterator<Map.Entry<K, V>> createEntrySetIterator() {
398 if (size() == 0) {
399 return EmptyOrderedIterator.<Map.Entry<K, V>>emptyOrderedIterator();
400 }
401 return new EntrySetIterator<K, V>(this);
402 }
403
404 /**
405 * EntrySet iterator.
406 */
407 protected static class EntrySetIterator<K, V> extends LinkIterator<K, V> implements
408 OrderedIterator<Map.Entry<K, V>>, ResettableIterator<Map.Entry<K, V>> {
409
410 protected EntrySetIterator(final AbstractLinkedMap<K, V> parent) {
411 super(parent);
412 }
413
414 public Map.Entry<K, V> next() {
415 return super.nextEntry();
416 }
417
418 public Map.Entry<K, V> previous() {
419 return super.previousEntry();
420 }
421 }
422
423 //-----------------------------------------------------------------------
424 /**
425 * Creates a key set iterator.
426 * Subclasses can override this to return iterators with different properties.
427 *
428 * @return the keySet iterator
429 */
430 @Override
431 protected Iterator<K> createKeySetIterator() {
432 if (size() == 0) {
433 return EmptyOrderedIterator.<K>emptyOrderedIterator();
434 }
435 return new KeySetIterator<K>(this);
436 }
437
438 /**
439 * KeySet iterator.
440 */
441 protected static class KeySetIterator<K> extends LinkIterator<K, Object> implements
442 OrderedIterator<K>, ResettableIterator<K> {
443
444 @SuppressWarnings("unchecked")
445 protected KeySetIterator(final AbstractLinkedMap<K, ?> parent) {
446 super((AbstractLinkedMap<K, Object>) parent);
447 }
448
449 public K next() {
450 return super.nextEntry().getKey();
451 }
452
453 public K previous() {
454 return super.previousEntry().getKey();
455 }
456 }
457
458 //-----------------------------------------------------------------------
459 /**
460 * Creates a values iterator.
461 * Subclasses can override this to return iterators with different properties.
462 *
463 * @return the values iterator
464 */
465 @Override
466 protected Iterator<V> createValuesIterator() {
467 if (size() == 0) {
468 return EmptyOrderedIterator.<V>emptyOrderedIterator();
469 }
470 return new ValuesIterator<V>(this);
471 }
472
473 /**
474 * Values iterator.
475 */
476 protected static class ValuesIterator<V> extends LinkIterator<Object, V> implements
477 OrderedIterator<V>, ResettableIterator<V> {
478
479 @SuppressWarnings("unchecked")
480 protected ValuesIterator(final AbstractLinkedMap<?, V> parent) {
481 super((AbstractLinkedMap<Object, V>) parent);
482 }
483
484 public V next() {
485 return super.nextEntry().getValue();
486 }
487
488 public V previous() {
489 return super.previousEntry().getValue();
490 }
491 }
492
493 //-----------------------------------------------------------------------
494 /**
495 * LinkEntry that stores the data.
496 * <p>
497 * If you subclass <code>AbstractLinkedMap</code> but not <code>LinkEntry</code>
498 * then you will not be able to access the protected fields.
499 * The <code>entryXxx()</code> methods on <code>AbstractLinkedMap</code> exist
500 * to provide the necessary access.
501 */
502 protected static class LinkEntry<K, V> extends HashEntry<K, V> {
503 /** The entry before this one in the order */
504 protected LinkEntry<K, V> before;
505 /** The entry after this one in the order */
506 protected LinkEntry<K, V> after;
507
508 /**
509 * Constructs a new entry.
510 *
511 * @param next the next entry in the hash bucket sequence
512 * @param hashCode the hash code
513 * @param key the key
514 * @param value the value
515 */
516 protected LinkEntry(final HashEntry<K, V> next, final int hashCode, final Object key, final V value) {
517 super(next, hashCode, key, value);
518 }
519 }
520
521 /**
522 * Base Iterator that iterates in link order.
523 */
524 protected static abstract class LinkIterator<K, V> {
525
526 /** The parent map */
527 protected final AbstractLinkedMap<K, V> parent;
528 /** The current (last returned) entry */
529 protected LinkEntry<K, V> last;
530 /** The next entry */
531 protected LinkEntry<K, V> next;
532 /** The modification count expected */
533 protected int expectedModCount;
534
535 protected LinkIterator(final AbstractLinkedMap<K, V> parent) {
536 super();
537 this.parent = parent;
538 this.next = parent.header.after;
539 this.expectedModCount = parent.modCount;
540 }
541
542 public boolean hasNext() {
543 return next != parent.header;
544 }
545
546 public boolean hasPrevious() {
547 return next.before != parent.header;
548 }
549
550 protected LinkEntry<K, V> nextEntry() {
551 if (parent.modCount != expectedModCount) {
552 throw new ConcurrentModificationException();
553 }
554 if (next == parent.header) {
555 throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
556 }
557 last = next;
558 next = next.after;
559 return last;
560 }
561
562 protected LinkEntry<K, V> previousEntry() {
563 if (parent.modCount != expectedModCount) {
564 throw new ConcurrentModificationException();
565 }
566 final LinkEntry<K, V> previous = next.before;
567 if (previous == parent.header) {
568 throw new NoSuchElementException(AbstractHashedMap.NO_PREVIOUS_ENTRY);
569 }
570 next = previous;
571 last = previous;
572 return last;
573 }
574
575 protected LinkEntry<K, V> currentEntry() {
576 return last;
577 }
578
579 public void remove() {
580 if (last == null) {
581 throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
582 }
583 if (parent.modCount != expectedModCount) {
584 throw new ConcurrentModificationException();
585 }
586 parent.remove(last.getKey());
587 last = null;
588 expectedModCount = parent.modCount;
589 }
590
591 public void reset() {
592 last = null;
593 next = parent.header.after;
594 }
595
596 @Override
597 public String toString() {
598 if (last != null) {
599 return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
600 }
601 return "Iterator[]";
602 }
603 }
604
605 }