    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;
    023
    024import org.apache.commons.collections4.OrderedIterator;
    025import org.apache.commons.collections4.OrderedMap;
    026import org.apache.commons.collections4.OrderedMapIterator;
    027import org.apache.commons.collections4.ResettableIterator;
    028import org.apache.commons.collections4.iterators.EmptyOrderedIterator;
    029import org.apache.commons.collections4.iterators.EmptyOrderedMapIterator;
    030
    031/**
    032 * An abstract implementation of a hash-based map that links entries to create an
    033 * ordered map and which provides numerous points for subclasses to override.
    034 * <p>
    035 * This class implements all the features necessary for a subclass linked
    036 * hash-based map. Key-value entries are stored in instances of the
    037 * {@code LinkEntry} class which can be overridden and replaced.
    038 * The iterators can similarly be replaced, without the need to replace the KeySet,
    039 * EntrySet and Values view classes.
    040 * </p>
    041 * <p>
    042 * Overridable methods are provided to change the default hashing behavior, and
    043 * to change how entries are added to and removed from the map. Hopefully, all you
    044 * need for unusual subclasses is here.
    045 * </p>
    046 * <p>
    047 * This implementation maintains order by original insertion, but subclasses
    048 * may work differently. The {@code OrderedMap} interface is implemented
    049 * to provide access to bidirectional iteration and extra convenience methods.
    050 * </p>
    051 * <p>
    052 * The {@code orderedMapIterator()} method provides direct access to a
    053 * bidirectional iterator. The iterators from the other views can also be cast
    054 * to {@code OrderedIterator} if required.
    055 * </p>
    056 * <p>
    057 * All the available iterators can be reset back to the start by casting to
    058 * {@code ResettableIterator} and calling {@code reset()}.
    059 * </p>
    060 * <p>
    061 * The implementation is also designed to be subclassed, with lots of useful
    062 * methods exposed.
    063 * </p>
    064 *
    065 * @param <K> the type of the keys in this map
    066 * @param <V> the type of the values in this map
    067 * @since 3.0
    068 */
    069public abstract class AbstractLinkedMap<K, V> extends AbstractHashedMap<K, V> implements OrderedMap<K, V> {
    070
    071    /**
    072     * EntrySet iterator.
    073     */
    074    protected static class EntrySetIterator<K, V> extends LinkIterator<K, V> implements
    075            OrderedIterator<Map.Entry<K, V>>, ResettableIterator<Map.Entry<K, V>> {
    076
    077        protected EntrySetIterator(final AbstractLinkedMap<K, V> parent) {
    078            super(parent);
    079        }
    080
    081        @Override
    082        public Map.Entry<K, V> next() {
    083            return super.nextEntry();
    084        }
    085
    086        @Override
    087        public Map.Entry<K, V> previous() {
    088            return super.previousEntry();
    089        }
    090    }
    091
    092    /**
    093     * KeySet iterator.
    094     */
    095    protected static class KeySetIterator<K> extends LinkIterator<K, Object> implements
    096            OrderedIterator<K>, ResettableIterator<K> {
    097
    098        @SuppressWarnings("unchecked")
    099        protected KeySetIterator(final AbstractLinkedMap<K, ?> parent) {
    100            super((AbstractLinkedMap<K, Object>) parent);
    101        }
    102
    103        @Override
    104        public K next() {
    105            return super.nextEntry().getKey();
    106        }
    107
    108        @Override
    109        public K previous() {
    110            return super.previousEntry().getKey();
    111        }
    112    }
    113
    114    /**
    115     * LinkEntry that stores the data.
    116     * <p>
    117     * If you subclass {@code AbstractLinkedMap} but not {@code LinkEntry}
    118     * then you will not be able to access the protected fields.
    119     * The {@code entryXxx()} methods on {@code AbstractLinkedMap} exist
    120     * to provide the necessary access.
    121     */
    122    protected static class LinkEntry<K, V> extends HashEntry<K, V> {
    123        /** The entry before this one in the order */
    124        protected LinkEntry<K, V> before;
    125        /** The entry after this one in the order */
    126        protected LinkEntry<K, V> after;
    127
    128        /**
    129         * Constructs a new entry.
    130         *
    131         * @param next  the next entry in the hash bucket sequence
    132         * @param hashCode  the hash code
    133         * @param key  the key
    134         * @param value  the value
    135         */
    136        protected LinkEntry(final HashEntry<K, V> next, final int hashCode, final Object key, final V value) {
    137            super(next, hashCode, key, value);
    138        }
    139    }
    140
    141    /**
    142     * Base Iterator that iterates in link order.
    143     */
    144    protected abstract static class LinkIterator<K, V> {
    145
    146        /** The parent map */
    147        protected final AbstractLinkedMap<K, V> parent;
    148        /** The current (last returned) entry */
    149        protected LinkEntry<K, V> last;
    150        /** The next entry */
    151        protected LinkEntry<K, V> next;
    152        /** The modification count expected */
    153        protected int expectedModCount;
    154
    155        protected LinkIterator(final AbstractLinkedMap<K, V> parent) {
    156            this.parent = parent;
    157            this.next = parent.header.after;
    158            this.expectedModCount = parent.modCount;
    159        }
    160
    161        protected LinkEntry<K, V> currentEntry() {
    162            return last;
    163        }
    164
    165        public boolean hasNext() {
    166            return next != parent.header;
    167        }
    168
    169        public boolean hasPrevious() {
    170            return next.before != parent.header;
    171        }
    172
    173        protected LinkEntry<K, V> nextEntry() {
    174            if (parent.modCount != expectedModCount) {
    175                throw new ConcurrentModificationException();
    176            }
    177            if (next == parent.header)  {
    178                throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
    179            }
    180            last = next;
    181            next = next.after;
    182            return last;
    183        }
    184
    185        protected LinkEntry<K, V> previousEntry() {
    186            if (parent.modCount != expectedModCount) {
    187                throw new ConcurrentModificationException();
    188            }
    189            final LinkEntry<K, V> previous = next.before;
    190            if (previous == parent.header)  {
    191                throw new NoSuchElementException(AbstractHashedMap.NO_PREVIOUS_ENTRY);
    192            }
    193            next = previous;
    194            last = previous;
    195            return last;
    196        }
    197
    198        public void remove() {
    199            if (last == null) {
    200                throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
    201            }
    202            if (parent.modCount != expectedModCount) {
    203                throw new ConcurrentModificationException();
    204            }
    205            parent.remove(last.getKey());
    206            last = null;
    207            expectedModCount = parent.modCount;
    208        }
    209
    210        public void reset() {
    211            last = null;
    212            next = parent.header.after;
    213        }
    214
    215        @Override
    216        public String toString() {
    217            if (last != null) {
    218                return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
    219            }
    220            return "Iterator[]";
    221        }
    222    }
    223
    224    /**
    225     * MapIterator implementation.
    226     */
    227    protected static class LinkMapIterator<K, V> extends LinkIterator<K, V> implements
    228            OrderedMapIterator<K, V>, ResettableIterator<K> {
    229
    230        protected LinkMapIterator(final AbstractLinkedMap<K, V> parent) {
    231            super(parent);
    232        }
    233
    234        @Override
    235        public K getKey() {
    236            final LinkEntry<K, V> current = currentEntry();
    237            if (current == null) {
    238                throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
    239            }
    240            return current.getKey();
    241        }
    242
    243        @Override
    244        public V getValue() {
    245            final LinkEntry<K, V> current = currentEntry();
    246            if (current == null) {
    247                throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
    248            }
    249            return current.getValue();
    250        }
    251
    252        @Override
    253        public K next() {
    254            return super.nextEntry().getKey();
    255        }
    256
    257        @Override
    258        public K previous() {
    259            return super.previousEntry().getKey();
    260        }
    261
    262        @Override
    263        public V setValue(final V value) {
    264            final LinkEntry<K, V> current = currentEntry();
    265            if (current == null) {
    266                throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
    267            }
    268            return current.setValue(value);
    269        }
    270    }
    271
    272    /**
    273     * Values iterator.
    274     */
    275    protected static class ValuesIterator<V> extends LinkIterator<Object, V> implements
    276            OrderedIterator<V>, ResettableIterator<V> {
    277
    278        @SuppressWarnings("unchecked")
    279        protected ValuesIterator(final AbstractLinkedMap<?, V> parent) {
    280            super((AbstractLinkedMap<Object, V>) parent);
    281        }
    282
    283        @Override
    284        public V next() {
    285            return super.nextEntry().getValue();
    286        }
    287
    288        @Override
    289        public V previous() {
    290            return super.previousEntry().getValue();
    291        }
    292    }
    293
    294    /** Header in the linked list */
    295    transient LinkEntry<K, V> header;
    296
    297    /**
    298     * Constructor only used in deserialization, do not use otherwise.
    299     */
    300    protected AbstractLinkedMap() {
    301    }
    302
    303    /**
    304     * Constructs a new, empty map with the specified initial capacity.
    305     *
    306     * @param initialCapacity  the initial capacity
    307     * @throws IllegalArgumentException if the initial capacity is negative
    308     */
    309    protected AbstractLinkedMap(final int initialCapacity) {
    310        super(initialCapacity);
    311    }
    312
    313    /**
    314     * Constructs a new, empty map with the specified initial capacity and
    315     * load factor.
    316     *
    317     * @param initialCapacity  the initial capacity
    318     * @param loadFactor  the load factor
    319     * @throws IllegalArgumentException if the initial capacity is negative
    320     * @throws IllegalArgumentException if the load factor is less than zero
    321     */
    322    protected AbstractLinkedMap(final int initialCapacity, final float loadFactor) {
    323        super(initialCapacity, loadFactor);
    324    }
    325
    326    /**
    327     * Constructor which performs no validation on the passed in parameters.
    328     *
    329     * @param initialCapacity  the initial capacity, must be a power of two
    330     * @param loadFactor  the load factor, must be &gt; 0.0f and generally &lt; 1.0f
    331     * @param threshold  the threshold, must be sensible
    332     */
    333    protected AbstractLinkedMap(final int initialCapacity, final float loadFactor, final int threshold) {
    334        super(initialCapacity, loadFactor, threshold);
    335    }
    336
    337    /**
    338     * Constructor copying elements from another map.
    339     *
    340     * @param map  the map to copy
    341     * @throws NullPointerException if the map is null
    342     */
    343    protected AbstractLinkedMap(final Map<? extends K, ? extends V> map) {
    344        super(map);
    345    }
    346
    347    /**
    348     * Adds an entry into this map, maintaining insertion order.
    349     * <p>
    350     * This implementation adds the entry to the data storage table and
    351     * to the end of the linked list.
    352     *
    353     * @param entry  the entry to add
    354     * @param hashIndex  the index into the data array to store at
    355     */
    356    @Override
    357    protected void addEntry(final HashEntry<K, V> entry, final int hashIndex) {
    358        final LinkEntry<K, V> link = (LinkEntry<K, V>) entry;
    359        link.after  = header;
    360        link.before = header.before;
    361        header.before.after = link;
    362        header.before = link;
    363        data[hashIndex] = link;
    364    }
    365
    366    /**
    367     * Clears the map, resetting the size to zero and nullifying references
    368     * to avoid garbage collection issues.
    369     */
    370    @Override
    371    public void clear() {
    372        // override to reset the linked list
    373        super.clear();
    374        header.before = header.after = header;
    375    }
    376
    377    /**
    378     * Checks whether the map contains the specified value.
    379     *
    380     * @param value  the value to search for
    381     * @return true if the map contains the value
    382     */
    383    @Override
    384    public boolean containsValue(final Object value) {
    385        // override uses faster iterator
    386        if (value == null) {
    387            for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after) {
    388                if (entry.getValue() == null) {
    389                    return true;
    390                }
    391            }
    392        } else {
    393            for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after) {
    394                if (isEqualValue(value, entry.getValue())) {
    395                    return true;
    396                }
    397            }
    398        }
    399        return false;
    400    }
    401
    402    /**
    403     * Creates an entry to store the data.
    404     * <p>
    405     * This implementation creates a new LinkEntry instance.
    406     *
    407     * @param next  the next entry in sequence
    408     * @param hashCode  the hash code to use
    409     * @param key  the key to store
    410     * @param value  the value to store
    411     * @return the newly created entry
    412     */
    413    @Override
    414    protected LinkEntry<K, V> createEntry(final HashEntry<K, V> next, final int hashCode, final K key, final V value) {
    415        return new LinkEntry<>(next, hashCode, convertKey(key), value);
    416    }
    417
    418    /**
    419     * Creates an entry set iterator.
    420     * Subclasses can override this to return iterators with different properties.
    421     *
    422     * @return the entrySet iterator
    423     */
    424    @Override
    425    protected Iterator<Map.Entry<K, V>> createEntrySetIterator() {
    426        if (isEmpty()) {
    427            return EmptyOrderedIterator.<Map.Entry<K, V>>emptyOrderedIterator();
    428        }
    429        return new EntrySetIterator<>(this);
    430    }
    431
    432    /**
    433     * Creates a key set iterator.
    434     * Subclasses can override this to return iterators with different properties.
    435     *
    436     * @return the keySet iterator
    437     */
    438    @Override
    439    protected Iterator<K> createKeySetIterator() {
    440        if (isEmpty()) {
    441            return EmptyOrderedIterator.<K>emptyOrderedIterator();
    442        }
    443        return new KeySetIterator<>(this);
    444    }
    445
    446    /**
    447     * Creates a values iterator.
    448     * Subclasses can override this to return iterators with different properties.
    449     *
    450     * @return the values iterator
    451     */
    452    @Override
    453    protected Iterator<V> createValuesIterator() {
    454        if (isEmpty()) {
    455            return EmptyOrderedIterator.<V>emptyOrderedIterator();
    456        }
    457        return new ValuesIterator<>(this);
    458    }
    459
    460    /**
    461     * Gets the {@code after} field from a {@code LinkEntry}.
    462     * Used in subclasses that have no visibility of the field.
    463     *
    464     * @param entry  the entry to query, must not be null
    465     * @return the {@code after} field of the entry
    466     * @throws NullPointerException if the entry is null
    467     * @since 3.1
    468     */
    469    protected LinkEntry<K, V> entryAfter(final LinkEntry<K, V> entry) {
    470        return entry.after;
    471    }
    472
    473    /**
    474     * Gets the {@code before} field from a {@code LinkEntry}.
    475     * Used in subclasses that have no visibility of the field.
    476     *
    477     * @param entry  the entry to query, must not be null
    478     * @return the {@code before} field of the entry
    479     * @throws NullPointerException if the entry is null
    480     * @since 3.1
    481     */
    482    protected LinkEntry<K, V> entryBefore(final LinkEntry<K, V> entry) {
    483        return entry.before;
    484    }
    485
    486    /**
    487     * Gets the first key in the map, which is the first inserted.
    488     *
    489     * @return the eldest key
    490     */
    491    @Override
    492    public K firstKey() {
    493        if (size == 0) {
    494            throw new NoSuchElementException("Map is empty");
    495        }
    496        return header.after.getKey();
    497    }
    498
    499    /**
    500     * Gets the key at the specified index.
    501     *
    502     * @param index  the index to retrieve
    503     * @return the key at the specified index
    504     * @throws IndexOutOfBoundsException if the index is invalid
    505     */
    506    protected LinkEntry<K, V> getEntry(final int index) {
    507        if (index < 0) {
    508            throw new IndexOutOfBoundsException("Index " + index + " is less than zero");
    509        }
    510        if (index >= size) {
    511            throw new IndexOutOfBoundsException("Index " + index + " is invalid for size " + size);
    512        }
    513        LinkEntry<K, V> entry;
    514        if (index < size / 2) {
    515            // Search forwards
    516            entry = header.after;
    517            for (int currentIndex = 0; currentIndex < index; currentIndex++) {
    518                entry = entry.after;
    519            }
    520        } else {
    521            // Search backwards
    522            entry = header;
    523            for (int currentIndex = size; currentIndex > index; currentIndex--) {
    524                entry = entry.before;
    525            }
    526        }
    527        return entry;
    528    }
    529
    530    @Override
    531    protected LinkEntry<K, V> getEntry(final Object key) {
    532        return (LinkEntry<K, V>) super.getEntry(key);
    533    }
    534
    535    /**
    536     * Initialize this subclass during construction.
    537     * <p>
    538     * NOTE: As from v3.2 this method calls
    539     * {@link #createEntry(HashEntry, int, Object, Object)} to create
    540     * the map entry object.
    541     */
    542    @Override
    543    protected void init() {
    544        header = createEntry(null, -1, null, null);
    545        header.before = header.after = header;
    546    }
    547
    548    /**
    549     * Gets the last key in the map, which is the most recently inserted.
    550     *
    551     * @return the most recently inserted key
    552     */
    553    @Override
    554    public K lastKey() {
    555        if (size == 0) {
    556            throw new NoSuchElementException("Map is empty");
    557        }
    558        return header.before.getKey();
    559    }
    560
    561    /**
    562     * {@inheritDoc}
    563     */
    564    @Override
    565    public OrderedMapIterator<K, V> mapIterator() {
    566        if (size == 0) {
    567            return EmptyOrderedMapIterator.<K, V>emptyOrderedMapIterator();
    568        }
    569        return new LinkMapIterator<>(this);
    570    }
    571
    572    /**
    573     * Gets the next key in sequence.
    574     *
    575     * @param key  the key to get after
    576     * @return the next key
    577     */
    578    @Override
    579    public K nextKey(final Object key) {
    580        final LinkEntry<K, V> entry = getEntry(key);
    581        return entry == null || entry.after == header ? null : entry.after.getKey();
    582    }
    583
    584    /**
    585     * Gets the previous key in sequence.
    586     *
    587     * @param key  the key to get before
    588     * @return the previous key
    589     */
    590    @Override
    591    public K previousKey(final Object key) {
    592        final LinkEntry<K, V> entry = getEntry(key);
    593        return entry == null || entry.before == header ? null : entry.before.getKey();
    594    }
    595
    596    /**
    597     * Removes an entry from the map and the linked list.
    598     * <p>
    599     * This implementation removes the entry from the linked list chain, then
    600     * calls the superclass implementation.
    601     *
    602     * @param entry  the entry to remove
    603     * @param hashIndex  the index into the data structure
    604     * @param previous  the previous entry in the chain
    605     */
    606    @Override
    607    protected void removeEntry(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> previous) {
    608        final LinkEntry<K, V> link = (LinkEntry<K, V>) entry;
    609        link.before.after = link.after;
    610        link.after.before = link.before;
    611        link.after = null;
    612        link.before = null;
    613        super.removeEntry(entry, hashIndex, previous);
    614    }
    615
    616}