Java > Open Source Codes > org > apache > commons > collections > map > AbstractLinkedMap


1 /*
2  * Copyright 2003-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package org.apache.commons.collections.map;
17
18 import java.util.ConcurrentModificationException ;
19 import java.util.Iterator ;
20 import java.util.Map ;
21 import java.util.NoSuchElementException ;
22
23 import org.apache.commons.collections.MapIterator;
24 import org.apache.commons.collections.OrderedIterator;
25 import org.apache.commons.collections.OrderedMap;
26 import org.apache.commons.collections.OrderedMapIterator;
27 import org.apache.commons.collections.ResettableIterator;
28 import org.apache.commons.collections.iterators.EmptyOrderedIterator;
29 import org.apache.commons.collections.iterators.EmptyOrderedMapIterator;
30
31 /**
32  * An abstract implementation of a hash-based map that links entries to create an
33  * ordered map and which provides numerous points for subclasses to override.
34  * <p>
35  * This class implements all the features necessary for a subclass linked
36  * hash-based map. Key-value entries are stored in instances of the
37  * <code>LinkEntry</code> class which can be overridden and replaced.
38  * The iterators can similarly be replaced, without the need to replace the KeySet,
39  * EntrySet and Values view classes.
40  * <p>
41  * Overridable methods are provided to change the default hashing behaviour, and
42  * to change how entries are added to and removed from the map. Hopefully, all you
43  * need for unusual subclasses is here.
44  * <p>
45  * This implementation maintains order by original insertion, but subclasses
46  * may work differently. The <code>OrderedMap</code> interface is implemented
47  * to provide access to bidirectional iteration and extra convenience methods.
48  * <p>
49  * The <code>orderedMapIterator()</code> method provides direct access to a
50  * bidirectional iterator. The iterators from the other views can also be cast
51  * to <code>OrderedIterator</code> if required.
52  * <p>
53  * All the available iterators can be reset back to the start by casting to
54  * <code>ResettableIterator</code> and calling <code>reset()</code>.
55  * <p>
56  * The implementation is also designed to be subclassed, with lots of useful
57  * methods exposed.
58  *
59  * @since Commons Collections 3.0
60  * @version $Revision: 1.12 $ $Date: 2004/05/26 21:56:05 $
61  *
62  * @author java util LinkedHashMap
63  * @author Stephen Colebourne
64  */
65 public class AbstractLinkedMap extends AbstractHashedMap implements OrderedMap {
66     
67     /** Header in the linked list */
68     protected transient LinkEntry header;
69
70     /**
71      * Constructor only used in deserialization, do not use otherwise.
72      */
73     protected AbstractLinkedMap() {
74         super();
75     }
76
77     /**
78      * Constructor which performs no validation on the passed in parameters.
79      *
80      * @param initialCapacity the initial capacity, must be a power of two
81      * @param loadFactor the load factor, must be > 0.0f and generally < 1.0f
82      * @param threshold the threshold, must be sensible
83      */
84     protected AbstractLinkedMap(int initialCapacity, float loadFactor, int threshold) {
85         super(initialCapacity, loadFactor, threshold);
86     }
87
88     /**
89      * Constructs a new, empty map with the specified initial capacity.
90      *
91      * @param initialCapacity the initial capacity
92      * @throws IllegalArgumentException if the initial capacity is less than one
93      */
94     protected AbstractLinkedMap(int initialCapacity) {
95         super(initialCapacity);
96     }
97
98     /**
99      * Constructs a new, empty map with the specified initial capacity and
100      * load factor.
101      *
102      * @param initialCapacity the initial capacity
103      * @param loadFactor the load factor
104      * @throws IllegalArgumentException if the initial capacity is less than one
105      * @throws IllegalArgumentException if the load factor is less than zero
106      */
107     protected AbstractLinkedMap(int initialCapacity, float loadFactor) {
108         super(initialCapacity, loadFactor);
109     }
110
111     /**
112      * Constructor copying elements from another map.
113      *
114      * @param map the map to copy
115      * @throws NullPointerException if the map is null
116      */
117     protected AbstractLinkedMap(Map map) {
118         super(map);
119     }
120
121     /**
122      * Initialise this subclass during construction.
123      */
124     protected void init() {
125         header = new LinkEntry(null, -1, null, null);
126         header.before = header.after = header;
127     }
128
129     //-----------------------------------------------------------------------
130 /**
131      * Checks whether the map contains the specified value.
132      *
133      * @param value the value to search for
134      * @return true if the map contains the value
135      */
136     public boolean containsValue(Object value) {
137         // override uses faster iterator
138 if (value == null) {
139             for (LinkEntry entry = header.after; entry != header; entry = entry.after) {
140                 if (entry.getValue() == null) {
141                     return true;
142                 }
143             }
144         } else {
145             for (LinkEntry entry = header.after; entry != header; entry = entry.after) {
146                 if (isEqualValue(value, entry.getValue())) {
147                     return true;
148                 }
149             }
150         }
151         return false;
152     }
153
154     /**
155      * Clears the map, resetting the size to zero and nullifying references
156      * to avoid garbage collection issues.
157      */
158     public void clear() {
159         // override to reset the linked list
160 super.clear();
161         header.before = header.after = header;
162     }
163
164     //-----------------------------------------------------------------------
165 /**
166      * Gets the first key in the map, which is the most recently inserted.
167      *
168      * @return the most recently inserted key
169      */
170     public Object firstKey() {
171         if (size == 0) {
172             throw new NoSuchElementException ("Map is empty");
173         }
174         return header.after.getKey();
175     }
176
177     /**
178      * Gets the last key in the map, which is the first inserted.
179      *
180      * @return the eldest key
181      */
182     public Object lastKey() {
183         if (size == 0) {
184             throw new NoSuchElementException ("Map is empty");
185         }
186         return header.before.getKey();
187     }
188
189     /**
190      * Gets the next key in sequence.
191      *
192      * @param key the key to get after
193      * @return the next key
194      */
195     public Object nextKey(Object key) {
196         LinkEntry entry = (LinkEntry) getEntry(key);
197         return (entry == null || entry.after == header ? null : entry.after.getKey());
198     }
199
200     /**
201      * Gets the previous key in sequence.
202      *
203      * @param key the key to get before
204      * @return the previous key
205      */
206     public Object previousKey(Object key) {
207         LinkEntry entry = (LinkEntry) getEntry(key);
208         return (entry == null || entry.before == header ? null : entry.before.getKey());
209     }
210
211     //-----------------------------------------------------------------------
212 /**
213      * Gets the key at the specified index.
214      *
215      * @param index the index to retrieve
216      * @return the key at the specified index
217      * @throws IndexOutOfBoundsException if the index is invalid
218      */
219     protected LinkEntry getEntry(int index) {
220         if (index < 0) {
221             throw new IndexOutOfBoundsException ("Index " + index + " is less than zero");
222         }
223         if (index >= size) {
224             throw new IndexOutOfBoundsException ("Index " + index + " is invalid for size " + size);
225         }
226         LinkEntry entry;
227         if (index < (size / 2)) {
228             // Search forwards
229 entry = header.after;
230             for (int currentIndex = 0; currentIndex < index; currentIndex++) {
231                 entry = entry.after;
232             }
233         } else {
234             // Search backwards
235 entry = header;
236             for (int currentIndex = size; currentIndex > index; currentIndex--) {
237                 entry = entry.before;
238             }
239         }
240         return entry;
241     }
242     
243     /**
244      * Adds an entry into this map, maintaining insertion order.
245      * <p>
246      * This implementation adds the entry to the data storage table and
247      * to the end of the linked list.
248      *
249      * @param entry the entry to add
250      * @param hashIndex the index into the data array to store at
251      */
252     protected void addEntry(HashEntry entry, int hashIndex) {
253         LinkEntry link = (LinkEntry) entry;
254         link.after = header;
255         link.before = header.before;
256         header.before.after = link;
257         header.before = link;
258         data[hashIndex] = entry;
259     }
260     
261     /**
262      * Creates an entry to store the data.
263      * <p>
264      * This implementation creates a new LinkEntry instance.
265      *
266      * @param next the next entry in sequence
267      * @param hashCode the hash code to use
268      * @param key the key to store
269      * @param value the value to store
270      * @return the newly created entry
271      */
272     protected HashEntry createEntry(HashEntry next, int hashCode, Object key, Object value) {
273         return new LinkEntry(next, hashCode, key, value);
274     }
275     
276     /**
277      * Removes an entry from the map and the linked list.
278      * <p>
279      * This implementation removes the entry from the linked list chain, then
280      * calls the superclass implementation.
281      *
282      * @param entry the entry to remove
283      * @param hashIndex the index into the data structure
284      * @param previous the previous entry in the chain
285      */
286     protected void removeEntry(HashEntry entry, int hashIndex, HashEntry previous) {
287         LinkEntry link = (LinkEntry) entry;
288         link.before.after = link.after;
289         link.after.before = link.before;
290         link.after = null;
291         link.before = null;
292         super.removeEntry(entry, hashIndex, previous);
293     }
294     
295     //-----------------------------------------------------------------------
296 /**
297      * Gets the <code>before</code> field from a <code>LinkEntry</code>.
298      * Used in subclasses that have no visibility of the field.
299      *
300      * @param entry the entry to query, must not be null
301      * @return the <code>before</code> field of the entry
302      * @throws NullPointerException if the entry is null
303      * @since Commons Collections 3.1
304      */
305     protected LinkEntry entryBefore(LinkEntry entry) {
306         return entry.before;
307     }
308     
309     /**
310      * Gets the <code>after</code> field from a <code>LinkEntry</code>.
311      * Used in subclasses that have no visibility of the field.
312      *
313      * @param entry the entry to query, must not be null
314      * @return the <code>after</code> field of the entry
315      * @throws NullPointerException if the entry is null
316      * @since Commons Collections 3.1
317      */
318     protected LinkEntry entryAfter(LinkEntry entry) {
319         return entry.after;
320     }
321     
322     //-----------------------------------------------------------------------
323 /**
324      * Gets an iterator over the map.
325      * Changes made to the iterator affect this map.
326      * <p>
327      * A MapIterator returns the keys in the map. It also provides convenient
328      * methods to get the key and value, and set the value.
329      * It avoids the need to create an entrySet/keySet/values object.
330      *
331      * @return the map iterator
332      */
333     public MapIterator mapIterator() {
334         if (size == 0) {
335             return EmptyOrderedMapIterator.INSTANCE;
336         }
337         return new LinkMapIterator(this);
338     }
339
340     /**
341      * Gets a bidirectional iterator over the map.
342      * Changes made to the iterator affect this map.
343      * <p>
344      * A MapIterator returns the keys in the map. It also provides convenient
345      * methods to get the key and value, and set the value.
346      * It avoids the need to create an entrySet/keySet/values object.
347      *
348      * @return the map iterator
349      */
350     public OrderedMapIterator orderedMapIterator() {
351         if (size == 0) {
352             return EmptyOrderedMapIterator.INSTANCE;
353         }
354         return new LinkMapIterator(this);
355     }
356
357     /**
358      * MapIterator implementation.
359      */
360     protected static class LinkMapIterator extends LinkIterator implements OrderedMapIterator {
361         
362         protected LinkMapIterator(AbstractLinkedMap parent) {
363             super(parent);
364         }
365
366         public Object next() {
367             return super.nextEntry().getKey();
368         }
369
370         public Object previous() {
371             return super.previousEntry().getKey();
372         }
373
374         public Object getKey() {
375             HashEntry current = currentEntry();
376             if (current == null) {
377                 throw new IllegalStateException (AbstractHashedMap.GETKEY_INVALID);
378             }
379             return current.getKey();
380         }
381
382         public Object getValue() {
383             HashEntry current = currentEntry();
384             if (current == null) {
385                 throw new IllegalStateException (AbstractHashedMap.GETVALUE_INVALID);
386             }
387             return current.getValue();
388         }
389
390         public Object setValue(Object value) {
391             HashEntry 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     protected Iterator createEntrySetIterator() {
407         if (size() == 0) {
408             return EmptyOrderedIterator.INSTANCE;
409         }
410         return new EntrySetIterator(this);
411     }
412
413     /**
414      * EntrySet iterator.
415      */
416     protected static class EntrySetIterator extends LinkIterator {
417         
418         protected EntrySetIterator(AbstractLinkedMap parent) {
419             super(parent);
420         }
421
422         public Object next() {
423             return super.nextEntry();
424         }
425
426         public Object previous() {
427             return super.previousEntry();
428         }
429     }
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     protected Iterator createKeySetIterator() {
439         if (size() == 0) {
440             return EmptyOrderedIterator.INSTANCE;
441         }
442         return new KeySetIterator(this);
443     }
444
445     /**
446      * KeySet iterator.
447      */
448     protected static class KeySetIterator extends EntrySetIterator {
449         
450         protected KeySetIterator(AbstractLinkedMap parent) {
451             super(parent);
452         }
453
454         public Object next() {
455             return super.nextEntry().getKey();
456         }
457
458         public Object previous() {
459             return super.previousEntry().getKey();
460         }
461     }
462     
463     //-----------------------------------------------------------------------
464 /**
465      * Creates a values iterator.
466      * Subclasses can override this to return iterators with different properties.
467      *
468      * @return the values iterator
469      */
470     protected Iterator createValuesIterator() {
471         if (size() == 0) {
472             return EmptyOrderedIterator.INSTANCE;
473         }
474         return new ValuesIterator(this);
475     }
476
477     /**
478      * Values iterator.
479      */
480     protected static class ValuesIterator extends LinkIterator {
481         
482         protected ValuesIterator(AbstractLinkedMap parent) {
483             super(parent);
484         }
485
486         public Object next() {
487             return super.nextEntry().getValue();
488         }
489
490         public Object previous() {
491             return super.previousEntry().getValue();
492         }
493     }
494     
495     //-----------------------------------------------------------------------
496 /**
497      * LinkEntry that stores the data.
498      * <p>
499      * If you subclass <code>AbstractLinkedMap</code> but not <code>LinkEntry</code>
500      * then you will not be able to access the protected fields.
501      * The <code>entryXxx()</code> methods on <code>AbstractLinkedMap</code> exist
502      * to provide the necessary access.
503      */
504     protected static class LinkEntry extends HashEntry {
505         /** The entry before this one in the order */
506         protected LinkEntry before;
507         /** The entry after this one in the order */
508         protected LinkEntry after;
509         
510         /**
511          * Constructs a new entry.
512          *
513          * @param next the next entry in the hash bucket sequence
514          * @param hashCode the hash code
515          * @param key the key
516          * @param value the value
517          */
518         protected LinkEntry(HashEntry next, int hashCode, Object key, Object value) {
519             super(next, hashCode, key, value);
520         }
521     }
522     
523     /**
524      * Base Iterator that iterates in link order.
525      */
526     protected static abstract class LinkIterator
527             implements OrderedIterator, ResettableIterator {
528                 
529         /** The parent map */
530         protected final AbstractLinkedMap parent;
531         /** The current (last returned) entry */
532         protected LinkEntry last;
533         /** The next entry */
534         protected LinkEntry next;
535         /** The modification count expected */
536         protected int expectedModCount;
537         
538         protected LinkIterator(AbstractLinkedMap parent) {
539             super();
540             this.parent = parent;
541             this.next = parent.header.after;
542             this.expectedModCount = parent.modCount;
543         }
544
545         public boolean hasNext() {
546             return (next != parent.header);
547         }
548         
549         public boolean hasPrevious() {
550             return (next.before != parent.header);
551         }
552
553         protected LinkEntry nextEntry() {
554             if (parent.modCount != expectedModCount) {
555                 throw new ConcurrentModificationException ();
556             }
557             if (next == parent.header) {
558                 throw new NoSuchElementException (AbstractHashedMap.NO_NEXT_ENTRY);
559             }
560             last = next;
561             next = next.after;
562             return last;
563         }
564
565         protected LinkEntry previousEntry() {
566             if (parent.modCount != expectedModCount) {
567                 throw new ConcurrentModificationException ();
568             }
569             LinkEntry previous = next.before;
570             if (previous == parent.header) {
571                 throw new NoSuchElementException (AbstractHashedMap.NO_PREVIOUS_ENTRY);
572             }
573             next = previous;
574             last = previous;
575             return last;
576         }
577         
578         protected LinkEntry currentEntry() {
579             return last;
580         }
581         
582         public void remove() {
583             if (last == null) {
584                 throw new IllegalStateException (AbstractHashedMap.REMOVE_INVALID);
585             }
586             if (parent.modCount != expectedModCount) {
587                 throw new ConcurrentModificationException ();
588             }
589             parent.remove(last.getKey());
590             last = null;
591             expectedModCount = parent.modCount;
592         }
593         
594         public void reset() {
595             last = null;
596             next = parent.header.after;
597         }
598
599         public String toString() {
600             if (last != null) {
601                 return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
602             } else {
603                 return "Iterator[]";
604             }
605         }
606     }
607     
608 }
609

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags