    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 *      https://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
    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 &gt; 0.0f and generally &lt; 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}