    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 */
    017package org.apache.commons.collections4.map;
    018
    019import java.util.ConcurrentModificationException;
    020import java.util.Iterator;
    021import java.util.Map;
    022import java.util.NoSuchElementException;
    023import java.util.Objects;
    024
    025import org.apache.commons.collections4.OrderedIterator;
    026import org.apache.commons.collections4.OrderedMap;
    027import org.apache.commons.collections4.OrderedMapIterator;
    028import org.apache.commons.collections4.ResettableIterator;
    029import org.apache.commons.collections4.iterators.EmptyOrderedIterator;
    030import org.apache.commons.collections4.iterators.EmptyOrderedMapIterator;
    031
    032/**
    033 * An abstract implementation of a hash-based map that links entries to create an
    034 * ordered map and which provides numerous points for subclasses to override.
    035 * <p>
    036 * This class implements all the features necessary for a subclass linked
    037 * hash-based map. Key-value entries are stored in instances of the
    038 * {@code LinkEntry} class which can be overridden and replaced.
    039 * The iterators can similarly be replaced, without the need to replace the KeySet,
    040 * EntrySet and Values view classes.
    041 * </p>
    042 * <p>
    043 * Overridable methods are provided to change the default hashing behavior, and
    044 * to change how entries are added to and removed from the map. Hopefully, all you
    045 * need for unusual subclasses is here.
    046 * </p>
    047 * <p>
    048 * This implementation maintains order by original insertion, but subclasses
    049 * may work differently. The {@code OrderedMap} interface is implemented
    050 * to provide access to bidirectional iteration and extra convenience methods.
    051 * </p>
    052 * <p>
    053 * The {@code orderedMapIterator()} method provides direct access to a
    054 * bidirectional iterator. The iterators from the other views can also be cast
    055 * to {@code OrderedIterator} if required.
    056 * </p>
    057 * <p>
    058 * All the available iterators can be reset back to the start by casting to
    059 * {@code ResettableIterator} and calling {@code reset()}.
    060 * </p>
    061 * <p>
    062 * The implementation is also designed to be subclassed, with lots of useful
    063 * methods exposed.
    064 * </p>
    065 *
    066 * @param <K> the type of the keys in this map
    067 * @param <V> the type of the values in this map
    068 * @since 3.0
    069 */
    070public abstract class AbstractLinkedMap<K, V> extends AbstractHashedMap<K, V> implements OrderedMap<K, V> {
    071
    072    /**
    073     * EntrySet iterator.
    074     *
    075     * @param <K> the key type.
    076     * @param <V> the value type.
    077     */
    078    protected static class EntrySetIterator<K, V> extends LinkIterator<K, V> implements
    079            OrderedIterator<Map.Entry<K, V>>, ResettableIterator<Map.Entry<K, V>> {
    080
    081        /**
    082         * Constructs a new instance.
    083         *
    084         * @param parent The parent AbstractLinkedMap.
    085         */
    086        protected EntrySetIterator(final AbstractLinkedMap<K, V> parent) {
    087            super(parent);
    088        }
    089
    090        @Override
    091        public Map.Entry<K, V> next() {
    092            return super.nextEntry();
    093        }
    094
    095        @Override
    096        public Map.Entry<K, V> previous() {
    097            return super.previousEntry();
    098        }
    099    }
    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 &gt; 0.0f and generally &lt; 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}