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 * https://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
144 /** The entry before this one in the order */
145 protected LinkEntry<K, V> before;
146
147 /** The entry after this one in the order */
148 protected LinkEntry<K, V> after;
149
150 /**
151 * Constructs a new entry.
152 *
153 * @param next The next entry in the hash bucket sequence
154 * @param hashCode The hash code
155 * @param key The key
156 * @param value The value
157 */
158 protected LinkEntry(final HashEntry<K, V> next, final int hashCode, final Object key, final V value) {
159 super(next, hashCode, key, value);
160 }
161 }
162
163 /**
164 * Base Iterator that iterates in link order.
165 *
166 * @param <K> The key type.
167 * @param <V> The value type.
168 */
169 protected abstract static class LinkIterator<K, V> {
170
171 /** The parent map */
172 protected final AbstractLinkedMap<K, V> parent;
173
174 /** The current (last returned) entry */
175 protected LinkEntry<K, V> last;
176
177 /** The next entry */
178 protected LinkEntry<K, V> next;
179
180 /** The modification count expected */
181 protected int expectedModCount;
182
183 /**
184 * Constructs a new instance.
185 *
186 * @param parent The parent AbstractLinkedMap.
187 */
188 protected LinkIterator(final AbstractLinkedMap<K, V> parent) {
189 this.parent = Objects.requireNonNull(parent, "parent");
190 this.next = parent.header.after;
191 this.expectedModCount = parent.modCount;
192 }
193
194 /**
195 * Gets the current entry.
196 *
197 * @return The current entry.
198 */
199 protected LinkEntry<K, V> currentEntry() {
200 return last;
201 }
202
203 /**
204 * Tests whether there is another entry.
205 *
206 * @return whether there is another entry.
207 */
208 public boolean hasNext() {
209 return next != parent.header;
210 }
211
212 /**
213 * Tests whether there is a previous entry.
214 *
215 * @return whether there is a previous entry.
216 */
217 public boolean hasPrevious() {
218 return next.before != parent.header;
219 }
220
221 /**
222 * Gets the next entry.
223 *
224 * @return The next entry.
225 */
226 protected LinkEntry<K, V> nextEntry() {
227 if (parent.modCount != expectedModCount) {
228 throw new ConcurrentModificationException();
229 }
230 if (next == parent.header) {
231 throw new NoSuchElementException(NO_NEXT_ENTRY);
232 }
233 last = next;
234 next = next.after;
235 return last;
236 }
237
238 /**
239 * Gets the previous entry.
240 *
241 * @return The previous entry.
242 */
243 protected LinkEntry<K, V> previousEntry() {
244 if (parent.modCount != expectedModCount) {
245 throw new ConcurrentModificationException();
246 }
247 final LinkEntry<K, V> previous = next.before;
248 if (previous == parent.header) {
249 throw new NoSuchElementException(NO_PREVIOUS_ENTRY);
250 }
251 next = previous;
252 last = previous;
253 return last;
254 }
255
256 /**
257 * Removes the current entry.
258 */
259 public void remove() {
260 if (last == null) {
261 throw new IllegalStateException(REMOVE_INVALID);
262 }
263 if (parent.modCount != expectedModCount) {
264 throw new ConcurrentModificationException();
265 }
266 parent.remove(last.getKey());
267 last = null;
268 expectedModCount = parent.modCount;
269 }
270
271 /**
272 * Resets the state to the end.
273 */
274 public void reset() {
275 last = null;
276 next = parent.header.after;
277 }
278
279 @Override
280 public String toString() {
281 if (last != null) {
282 return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
283 }
284 return "Iterator[]";
285 }
286 }
287
288 /**
289 * MapIterator implementation.
290 *
291 * @param <K> The key type.
292 * @param <V> The value type.
293 */
294 protected static class LinkMapIterator<K, V> extends LinkIterator<K, V> implements
295 OrderedMapIterator<K, V>, ResettableIterator<K> {
296
297 /**
298 * Constructs a new instance.
299 *
300 * @param parent The parent AbstractLinkedMap.
301 */
302 protected LinkMapIterator(final AbstractLinkedMap<K, V> parent) {
303 super(parent);
304 }
305
306 @Override
307 public K getKey() {
308 final LinkEntry<K, V> current = currentEntry();
309 if (current == null) {
310 throw new IllegalStateException(GETKEY_INVALID);
311 }
312 return current.getKey();
313 }
314
315 @Override
316 public V getValue() {
317 final LinkEntry<K, V> current = currentEntry();
318 if (current == null) {
319 throw new IllegalStateException(GETVALUE_INVALID);
320 }
321 return current.getValue();
322 }
323
324 @Override
325 public K next() {
326 return super.nextEntry().getKey();
327 }
328
329 @Override
330 public K previous() {
331 return super.previousEntry().getKey();
332 }
333
334 @Override
335 public V setValue(final V value) {
336 final LinkEntry<K, V> current = currentEntry();
337 if (current == null) {
338 throw new IllegalStateException(SETVALUE_INVALID);
339 }
340 return current.setValue(value);
341 }
342 }
343
344 /**
345 * Values iterator.
346 *
347 * @param <V> The value type.
348 */
349 protected static class ValuesIterator<V> extends LinkIterator<Object, V> implements
350 OrderedIterator<V>, ResettableIterator<V> {
351
352 /**
353 * Constructs a new instance.
354 *
355 * @param parent The parent AbstractLinkedMap.
356 */
357 @SuppressWarnings("unchecked")
358 protected ValuesIterator(final AbstractLinkedMap<?, V> parent) {
359 super((AbstractLinkedMap<Object, V>) parent);
360 }
361
362 @Override
363 public V next() {
364 return super.nextEntry().getValue();
365 }
366
367 @Override
368 public V previous() {
369 return super.previousEntry().getValue();
370 }
371 }
372
373 /** Header in the linked list */
374 transient LinkEntry<K, V> header;
375
376 /**
377 * Constructor only used in deserialization, do not use otherwise.
378 */
379 protected AbstractLinkedMap() {
380 }
381
382 /**
383 * Constructs a new, empty map with the specified initial capacity.
384 *
385 * @param initialCapacity The initial capacity
386 * @throws IllegalArgumentException if the initial capacity is negative
387 */
388 protected AbstractLinkedMap(final int initialCapacity) {
389 super(initialCapacity);
390 }
391
392 /**
393 * Constructs a new, empty map with the specified initial capacity and
394 * load factor.
395 *
396 * @param initialCapacity The initial capacity
397 * @param loadFactor The load factor
398 * @throws IllegalArgumentException if the initial capacity is negative
399 * @throws IllegalArgumentException if the load factor is less than zero
400 */
401 protected AbstractLinkedMap(final int initialCapacity, final float loadFactor) {
402 super(initialCapacity, loadFactor);
403 }
404
405 /**
406 * Constructor which performs no validation on the passed in parameters.
407 *
408 * @param initialCapacity The initial capacity, must be a power of two
409 * @param loadFactor The load factor, must be > 0.0f and generally < 1.0f
410 * @param threshold The threshold, must be sensible
411 */
412 protected AbstractLinkedMap(final int initialCapacity, final float loadFactor, final int threshold) {
413 super(initialCapacity, loadFactor, threshold);
414 }
415
416 /**
417 * Constructor copying elements from another map.
418 *
419 * @param map The map to copy
420 * @throws NullPointerException if the map is null
421 */
422 protected AbstractLinkedMap(final Map<? extends K, ? extends V> map) {
423 super(map);
424 }
425
426 /**
427 * Adds an entry into this map, maintaining insertion order.
428 * <p>
429 * This implementation adds the entry to the data storage table and
430 * to the end of the linked list.
431 * </p>
432 *
433 * @param entry The entry to add
434 * @param hashIndex The index into the data array to store at
435 */
436 @Override
437 protected void addEntry(final HashEntry<K, V> entry, final int hashIndex) {
438 final LinkEntry<K, V> link = (LinkEntry<K, V>) entry;
439 link.after = header;
440 link.before = header.before;
441 header.before.after = link;
442 header.before = link;
443 data[hashIndex] = link;
444 }
445
446 /**
447 * Clears the map, resetting the size to zero and nullifying references
448 * to avoid garbage collection issues.
449 */
450 @Override
451 public void clear() {
452 // override to reset the linked list
453 super.clear();
454 header.before = header.after = header;
455 }
456
457 /**
458 * Checks whether the map contains the specified value.
459 *
460 * @param value The value to search for
461 * @return true if the map contains the value
462 */
463 @Override
464 public boolean containsValue(final Object value) {
465 // override uses faster iterator
466 if (value == null) {
467 for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after) {
468 if (entry.getValue() == null) {
469 return true;
470 }
471 }
472 } else {
473 for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after) {
474 if (isEqualValue(value, entry.getValue())) {
475 return true;
476 }
477 }
478 }
479 return false;
480 }
481
482 /**
483 * Creates an entry to store the data.
484 * <p>
485 * This implementation creates a new LinkEntry instance.
486 * </p>
487 *
488 * @param next The next entry in sequence
489 * @param hashCode The hash code to use
490 * @param key The key to store
491 * @param value The value to store
492 * @return The newly created entry
493 */
494 @Override
495 protected LinkEntry<K, V> createEntry(final HashEntry<K, V> next, final int hashCode, final K key, final V value) {
496 return new LinkEntry<>(next, hashCode, convertKey(key), value);
497 }
498
499 /**
500 * Creates an entry set iterator.
501 * Subclasses can override this to return iterators with different properties.
502 *
503 * @return The entrySet iterator
504 */
505 @Override
506 protected Iterator<Map.Entry<K, V>> createEntrySetIterator() {
507 if (isEmpty()) {
508 return EmptyOrderedIterator.<Map.Entry<K, V>>emptyOrderedIterator();
509 }
510 return new EntrySetIterator<>(this);
511 }
512
513 /**
514 * Creates a key set iterator.
515 * Subclasses can override this to return iterators with different properties.
516 *
517 * @return The keySet iterator
518 */
519 @Override
520 protected Iterator<K> createKeySetIterator() {
521 if (isEmpty()) {
522 return EmptyOrderedIterator.<K>emptyOrderedIterator();
523 }
524 return new KeySetIterator<>(this);
525 }
526
527 /**
528 * Creates a values iterator.
529 * Subclasses can override this to return iterators with different properties.
530 *
531 * @return The values iterator
532 */
533 @Override
534 protected Iterator<V> createValuesIterator() {
535 if (isEmpty()) {
536 return EmptyOrderedIterator.<V>emptyOrderedIterator();
537 }
538 return new ValuesIterator<>(this);
539 }
540
541 /**
542 * Gets the {@code after} field from a {@code LinkEntry}.
543 * Used in subclasses that have no visibility of the field.
544 *
545 * @param entry The entry to query, must not be null
546 * @return The {@code after} field of the entry
547 * @throws NullPointerException if the entry is null
548 * @since 3.1
549 */
550 protected LinkEntry<K, V> entryAfter(final LinkEntry<K, V> entry) {
551 return entry.after;
552 }
553
554 /**
555 * Gets the {@code before} field from a {@code LinkEntry}.
556 * Used in subclasses that have no visibility of the field.
557 *
558 * @param entry The entry to query, must not be null
559 * @return The {@code before} field of the entry
560 * @throws NullPointerException if the entry is null
561 * @since 3.1
562 */
563 protected LinkEntry<K, V> entryBefore(final LinkEntry<K, V> entry) {
564 return entry.before;
565 }
566
567 /**
568 * Gets the first key in the map, which is the first inserted.
569 *
570 * @return The eldest key
571 */
572 @Override
573 public K firstKey() {
574 if (size == 0) {
575 throw new NoSuchElementException("Map is empty");
576 }
577 return header.after.getKey();
578 }
579
580 /**
581 * Gets the key at the specified index.
582 *
583 * @param index The index to retrieve
584 * @return The key at the specified index
585 * @throws IndexOutOfBoundsException if the index is invalid
586 */
587 protected LinkEntry<K, V> getEntry(final int index) {
588 if (index < 0) {
589 throw new IndexOutOfBoundsException("Index " + index + " is less than zero");
590 }
591 if (index >= size) {
592 throw new IndexOutOfBoundsException("Index " + index + " is invalid for size " + size);
593 }
594 LinkEntry<K, V> entry;
595 if (index < size / 2) {
596 // Search forwards
597 entry = header.after;
598 for (int currentIndex = 0; currentIndex < index; currentIndex++) {
599 entry = entry.after;
600 }
601 } else {
602 // Search backwards
603 entry = header;
604 for (int currentIndex = size; currentIndex > index; currentIndex--) {
605 entry = entry.before;
606 }
607 }
608 return entry;
609 }
610
611 @Override
612 protected LinkEntry<K, V> getEntry(final Object key) {
613 return (LinkEntry<K, V>) super.getEntry(key);
614 }
615
616 /**
617 * Initialize this subclass during construction.
618 * <p>
619 * Note: As from v3.2 this method calls
620 * {@link #createEntry(HashEntry, int, Object, Object)} to create
621 * the map entry object.
622 * </p>
623 */
624 @Override
625 protected void init() {
626 header = createEntry(null, -1, null, null);
627 header.before = header.after = header;
628 }
629
630 /**
631 * Gets the last key in the map, which is the most recently inserted.
632 *
633 * @return The most recently inserted key
634 */
635 @Override
636 public K lastKey() {
637 if (size == 0) {
638 throw new NoSuchElementException("Map is empty");
639 }
640 return header.before.getKey();
641 }
642
643 /**
644 * {@inheritDoc}
645 */
646 @Override
647 public OrderedMapIterator<K, V> mapIterator() {
648 if (size == 0) {
649 return EmptyOrderedMapIterator.<K, V>emptyOrderedMapIterator();
650 }
651 return new LinkMapIterator<>(this);
652 }
653
654 /**
655 * Gets the next key in sequence.
656 *
657 * @param key The key to get after
658 * @return The next key
659 */
660 @Override
661 public K nextKey(final Object key) {
662 final LinkEntry<K, V> entry = getEntry(key);
663 return entry == null || entry.after == header ? null : entry.after.getKey();
664 }
665
666 /**
667 * Gets the previous key in sequence.
668 *
669 * @param key The key to get before
670 * @return The previous key
671 */
672 @Override
673 public K previousKey(final Object key) {
674 final LinkEntry<K, V> entry = getEntry(key);
675 return entry == null || entry.before == header ? null : entry.before.getKey();
676 }
677
678 /**
679 * Removes an entry from the map and the linked list.
680 * <p>
681 * This implementation removes the entry from the linked list chain, then
682 * calls the superclass implementation.
683 * </p>
684 *
685 * @param entry The entry to remove
686 * @param hashIndex The index into the data structure
687 * @param previous The previous entry in the chain
688 */
689 @Override
690 protected void removeEntry(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> previous) {
691 final LinkEntry<K, V> link = (LinkEntry<K, V>) entry;
692 link.before.after = link.after;
693 link.after.before = link.before;
694 link.after = null;
695 link.before = null;
696 super.removeEntry(entry, hashIndex, previous);
697 }
698
699 }