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