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