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