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