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