0001: /*
0002: * Copyright 2002-2004 The Apache Software Foundation
0003: *
0004: * Licensed under the Apache License, Version 2.0 (the "License");
0005: * you may not use this file except in compliance with the License.
0006: * You may obtain a copy of the License at
0007: *
0008: * http://www.apache.org/licenses/LICENSE-2.0
0009: *
0010: * Unless required by applicable law or agreed to in writing, software
0011: * distributed under the License is distributed on an "AS IS" BASIS,
0012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013: * See the License for the specific language governing permissions and
0014: * limitations under the License.
0015: */
0016: package org.apache.commons.collections;
0017:
0018: import java.io.Externalizable;
0019: import java.io.IOException;
0020: import java.io.ObjectInput;
0021: import java.io.ObjectOutput;
0022: import java.util.AbstractCollection;
0023: import java.util.AbstractSet;
0024: import java.util.ArrayList;
0025: import java.util.Collection;
0026: import java.util.ConcurrentModificationException;
0027: import java.util.HashMap;
0028: import java.util.Iterator;
0029: import java.util.List;
0030: import java.util.Map;
0031: import java.util.NoSuchElementException;
0032: import java.util.Set;
0033:
0034: import org.apache.commons.collections.list.UnmodifiableList;
0035:
0036: /**
0037: * A map of objects whose mapping entries are sequenced based on the order in
0038: * which they were added. This data structure has fast <i>O(1)</i> search
0039: * time, deletion time, and insertion time.
0040: * <p>
0041: * Although this map is sequenced, it cannot implement
0042: * {@link java.util.List} because of incompatible interface definitions.
0043: * The remove methods in List and Map have different return values
0044: * (see: {@link java.util.List#remove(Object)} and {@link java.util.Map#remove(Object)}).
0045: * <p>
0046: * This class is not thread safe. When a thread safe implementation is
0047: * required, use {@link java.util.Collections#synchronizedMap(Map)} as it is documented,
0048: * or use explicit synchronization controls.
0049: *
0050: * @deprecated Replaced by LinkedMap and ListOrderedMap in map subpackage. Due to be removed in v4.0.
0051: * @see org.apache.commons.collections.map.LinkedMap
0052: * @see org.apache.commons.collections.map.ListOrderedMap
0053: * @since Commons Collections 2.0
0054: * @version $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
0055: *
0056: * @author Michael A. Smith
0057: * @author Daniel Rall
0058: * @author Henning P. Schmiedehausen
0059: * @author Stephen Colebourne
0060: */
0061: public class SequencedHashMap implements Map, Cloneable, Externalizable {
0062:
0063: /**
0064: * {@link java.util.Map.Entry} that doubles as a node in the linked list
0065: * of sequenced mappings.
0066: */
0067: private static class Entry implements Map.Entry, KeyValue {
0068: // Note: This class cannot easily be made clonable. While the actual
0069: // implementation of a clone would be simple, defining the semantics is
0070: // difficult. If a shallow clone is implemented, then entry.next.prev !=
0071: // entry, which is unintuitive and probably breaks all sorts of assumptions
0072: // in code that uses this implementation. If a deep clone is
0073: // implemented, then what happens when the linked list is cyclical (as is
0074: // the case with SequencedHashMap)? It's impossible to know in the clone
0075: // when to stop cloning, and thus you end up in a recursive loop,
0076: // continuously cloning the "next" in the list.
0077:
0078: private final Object key;
0079: private Object value;
0080:
0081: // package private to allow the SequencedHashMap to access and manipulate
0082: // them.
0083: Entry next = null;
0084: Entry prev = null;
0085:
0086: public Entry(Object key, Object value) {
0087: this .key = key;
0088: this .value = value;
0089: }
0090:
0091: // per Map.Entry.getKey()
0092: public Object getKey() {
0093: return this .key;
0094: }
0095:
0096: // per Map.Entry.getValue()
0097: public Object getValue() {
0098: return this .value;
0099: }
0100:
0101: // per Map.Entry.setValue()
0102: public Object setValue(Object value) {
0103: Object oldValue = this .value;
0104: this .value = value;
0105: return oldValue;
0106: }
0107:
0108: public int hashCode() {
0109: // implemented per api docs for Map.Entry.hashCode()
0110: return ((getKey() == null ? 0 : getKey().hashCode()) ^ (getValue() == null ? 0
0111: : getValue().hashCode()));
0112: }
0113:
0114: public boolean equals(Object obj) {
0115: if (obj == null)
0116: return false;
0117: if (obj == this )
0118: return true;
0119: if (!(obj instanceof Map.Entry))
0120: return false;
0121:
0122: Map.Entry other = (Map.Entry) obj;
0123:
0124: // implemented per api docs for Map.Entry.equals(Object)
0125: return ((getKey() == null ? other.getKey() == null
0126: : getKey().equals(other.getKey())) && (getValue() == null ? other
0127: .getValue() == null
0128: : getValue().equals(other.getValue())));
0129: }
0130:
0131: public String toString() {
0132: return "[" + getKey() + "=" + getValue() + "]";
0133: }
0134: }
0135:
0136: /**
0137: * Construct an empty sentinel used to hold the head (sentinel.next) and the
0138: * tail (sentinel.prev) of the list. The sentinel has a <code>null</code>
0139: * key and value.
0140: */
0141: private static final Entry createSentinel() {
0142: Entry s = new Entry(null, null);
0143: s.prev = s;
0144: s.next = s;
0145: return s;
0146: }
0147:
0148: /**
0149: * Sentinel used to hold the head and tail of the list of entries.
0150: */
0151: private Entry sentinel;
0152:
0153: /**
0154: * Map of keys to entries
0155: */
0156: private HashMap entries;
0157:
0158: /**
0159: * Holds the number of modifications that have occurred to the map,
0160: * excluding modifications made through a collection view's iterator
0161: * (e.g. entrySet().iterator().remove()). This is used to create a
0162: * fail-fast behavior with the iterators.
0163: */
0164: private transient long modCount = 0;
0165:
0166: /**
0167: * Construct a new sequenced hash map with default initial size and load
0168: * factor.
0169: */
0170: public SequencedHashMap() {
0171: sentinel = createSentinel();
0172: entries = new HashMap();
0173: }
0174:
0175: /**
0176: * Construct a new sequenced hash map with the specified initial size and
0177: * default load factor.
0178: *
0179: * @param initialSize the initial size for the hash table
0180: *
0181: * @see HashMap#HashMap(int)
0182: */
0183: public SequencedHashMap(int initialSize) {
0184: sentinel = createSentinel();
0185: entries = new HashMap(initialSize);
0186: }
0187:
0188: /**
0189: * Construct a new sequenced hash map with the specified initial size and
0190: * load factor.
0191: *
0192: * @param initialSize the initial size for the hash table
0193: *
0194: * @param loadFactor the load factor for the hash table.
0195: *
0196: * @see HashMap#HashMap(int,float)
0197: */
0198: public SequencedHashMap(int initialSize, float loadFactor) {
0199: sentinel = createSentinel();
0200: entries = new HashMap(initialSize, loadFactor);
0201: }
0202:
0203: /**
0204: * Construct a new sequenced hash map and add all the elements in the
0205: * specified map. The order in which the mappings in the specified map are
0206: * added is defined by {@link #putAll(Map)}.
0207: */
0208: public SequencedHashMap(Map m) {
0209: this ();
0210: putAll(m);
0211: }
0212:
0213: /**
0214: * Removes an internal entry from the linked list. This does not remove
0215: * it from the underlying map.
0216: */
0217: private void removeEntry(Entry entry) {
0218: entry.next.prev = entry.prev;
0219: entry.prev.next = entry.next;
0220: }
0221:
0222: /**
0223: * Inserts a new internal entry to the tail of the linked list. This does
0224: * not add the entry to the underlying map.
0225: */
0226: private void insertEntry(Entry entry) {
0227: entry.next = sentinel;
0228: entry.prev = sentinel.prev;
0229: sentinel.prev.next = entry;
0230: sentinel.prev = entry;
0231: }
0232:
0233: // per Map.size()
0234:
0235: /**
0236: * Implements {@link Map#size()}.
0237: */
0238: public int size() {
0239: // use the underlying Map's size since size is not maintained here.
0240: return entries.size();
0241: }
0242:
0243: /**
0244: * Implements {@link Map#isEmpty()}.
0245: */
0246: public boolean isEmpty() {
0247: // for quick check whether the map is entry, we can check the linked list
0248: // and see if there's anything in it.
0249: return sentinel.next == sentinel;
0250: }
0251:
0252: /**
0253: * Implements {@link Map#containsKey(Object)}.
0254: */
0255: public boolean containsKey(Object key) {
0256: // pass on to underlying map implementation
0257: return entries.containsKey(key);
0258: }
0259:
0260: /**
0261: * Implements {@link Map#containsValue(Object)}.
0262: */
0263: public boolean containsValue(Object value) {
0264: // unfortunately, we cannot just pass this call to the underlying map
0265: // because we are mapping keys to entries, not keys to values. The
0266: // underlying map doesn't have an efficient implementation anyway, so this
0267: // isn't a big deal.
0268:
0269: // do null comparison outside loop so we only need to do it once. This
0270: // provides a tighter, more efficient loop at the expense of slight
0271: // code duplication.
0272: if (value == null) {
0273: for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
0274: if (pos.getValue() == null)
0275: return true;
0276: }
0277: } else {
0278: for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
0279: if (value.equals(pos.getValue()))
0280: return true;
0281: }
0282: }
0283: return false;
0284: }
0285:
0286: /**
0287: * Implements {@link Map#get(Object)}.
0288: */
0289: public Object get(Object o) {
0290: // find entry for the specified key object
0291: Entry entry = (Entry) entries.get(o);
0292: if (entry == null)
0293: return null;
0294:
0295: return entry.getValue();
0296: }
0297:
0298: /**
0299: * Return the entry for the "oldest" mapping. That is, return the Map.Entry
0300: * for the key-value pair that was first put into the map when compared to
0301: * all the other pairings in the map. This behavior is equivalent to using
0302: * <code>entrySet().iterator().next()</code>, but this method provides an
0303: * optimized implementation.
0304: *
0305: * @return The first entry in the sequence, or <code>null</code> if the
0306: * map is empty.
0307: */
0308: public Map.Entry getFirst() {
0309: // sentinel.next points to the "first" element of the sequence -- the head
0310: // of the list, which is exactly the entry we need to return. We must test
0311: // for an empty list though because we don't want to return the sentinel!
0312: return (isEmpty()) ? null : sentinel.next;
0313: }
0314:
0315: /**
0316: * Return the key for the "oldest" mapping. That is, return the key for the
0317: * mapping that was first put into the map when compared to all the other
0318: * objects in the map. This behavior is equivalent to using
0319: * <code>getFirst().getKey()</code>, but this method provides a slightly
0320: * optimized implementation.
0321: *
0322: * @return The first key in the sequence, or <code>null</code> if the
0323: * map is empty.
0324: */
0325: public Object getFirstKey() {
0326: // sentinel.next points to the "first" element of the sequence -- the head
0327: // of the list -- and the requisite key is returned from it. An empty list
0328: // does not need to be tested. In cases where the list is empty,
0329: // sentinel.next will point to the sentinel itself which has a null key,
0330: // which is exactly what we would want to return if the list is empty (a
0331: // nice convenient way to avoid test for an empty list)
0332: return sentinel.next.getKey();
0333: }
0334:
0335: /**
0336: * Return the value for the "oldest" mapping. That is, return the value for
0337: * the mapping that was first put into the map when compared to all the
0338: * other objects in the map. This behavior is equivalent to using
0339: * <code>getFirst().getValue()</code>, but this method provides a slightly
0340: * optimized implementation.
0341: *
0342: * @return The first value in the sequence, or <code>null</code> if the
0343: * map is empty.
0344: */
0345: public Object getFirstValue() {
0346: // sentinel.next points to the "first" element of the sequence -- the head
0347: // of the list -- and the requisite value is returned from it. An empty
0348: // list does not need to be tested. In cases where the list is empty,
0349: // sentinel.next will point to the sentinel itself which has a null value,
0350: // which is exactly what we would want to return if the list is empty (a
0351: // nice convenient way to avoid test for an empty list)
0352: return sentinel.next.getValue();
0353: }
0354:
0355: /**
0356: * Return the entry for the "newest" mapping. That is, return the Map.Entry
0357: * for the key-value pair that was first put into the map when compared to
0358: * all the other pairings in the map. The behavior is equivalent to:
0359: *
0360: * <pre>
0361: * Object obj = null;
0362: * Iterator iter = entrySet().iterator();
0363: * while(iter.hasNext()) {
0364: * obj = iter.next();
0365: * }
0366: * return (Map.Entry)obj;
0367: * </pre>
0368: *
0369: * However, the implementation of this method ensures an O(1) lookup of the
0370: * last key rather than O(n).
0371: *
0372: * @return The last entry in the sequence, or <code>null</code> if the map
0373: * is empty.
0374: */
0375: public Map.Entry getLast() {
0376: // sentinel.prev points to the "last" element of the sequence -- the tail
0377: // of the list, which is exactly the entry we need to return. We must test
0378: // for an empty list though because we don't want to return the sentinel!
0379: return (isEmpty()) ? null : sentinel.prev;
0380: }
0381:
0382: /**
0383: * Return the key for the "newest" mapping. That is, return the key for the
0384: * mapping that was last put into the map when compared to all the other
0385: * objects in the map. This behavior is equivalent to using
0386: * <code>getLast().getKey()</code>, but this method provides a slightly
0387: * optimized implementation.
0388: *
0389: * @return The last key in the sequence, or <code>null</code> if the map is
0390: * empty.
0391: */
0392: public Object getLastKey() {
0393: // sentinel.prev points to the "last" element of the sequence -- the tail
0394: // of the list -- and the requisite key is returned from it. An empty list
0395: // does not need to be tested. In cases where the list is empty,
0396: // sentinel.prev will point to the sentinel itself which has a null key,
0397: // which is exactly what we would want to return if the list is empty (a
0398: // nice convenient way to avoid test for an empty list)
0399: return sentinel.prev.getKey();
0400: }
0401:
0402: /**
0403: * Return the value for the "newest" mapping. That is, return the value for
0404: * the mapping that was last put into the map when compared to all the other
0405: * objects in the map. This behavior is equivalent to using
0406: * <code>getLast().getValue()</code>, but this method provides a slightly
0407: * optimized implementation.
0408: *
0409: * @return The last value in the sequence, or <code>null</code> if the map
0410: * is empty.
0411: */
0412: public Object getLastValue() {
0413: // sentinel.prev points to the "last" element of the sequence -- the tail
0414: // of the list -- and the requisite value is returned from it. An empty
0415: // list does not need to be tested. In cases where the list is empty,
0416: // sentinel.prev will point to the sentinel itself which has a null value,
0417: // which is exactly what we would want to return if the list is empty (a
0418: // nice convenient way to avoid test for an empty list)
0419: return sentinel.prev.getValue();
0420: }
0421:
0422: /**
0423: * Implements {@link Map#put(Object, Object)}.
0424: */
0425: public Object put(Object key, Object value) {
0426: modCount++;
0427:
0428: Object oldValue = null;
0429:
0430: // lookup the entry for the specified key
0431: Entry e = (Entry) entries.get(key);
0432:
0433: // check to see if it already exists
0434: if (e != null) {
0435: // remove from list so the entry gets "moved" to the end of list
0436: removeEntry(e);
0437:
0438: // update value in map
0439: oldValue = e.setValue(value);
0440:
0441: // Note: We do not update the key here because its unnecessary. We only
0442: // do comparisons using equals(Object) and we know the specified key and
0443: // that in the map are equal in that sense. This may cause a problem if
0444: // someone does not implement their hashCode() and/or equals(Object)
0445: // method properly and then use it as a key in this map.
0446: } else {
0447: // add new entry
0448: e = new Entry(key, value);
0449: entries.put(key, e);
0450: }
0451: // assert(entry in map, but not list)
0452:
0453: // add to list
0454: insertEntry(e);
0455:
0456: return oldValue;
0457: }
0458:
0459: /**
0460: * Implements {@link Map#remove(Object)}.
0461: */
0462: public Object remove(Object key) {
0463: Entry e = removeImpl(key);
0464: return (e == null) ? null : e.getValue();
0465: }
0466:
0467: /**
0468: * Fully remove an entry from the map, returning the old entry or null if
0469: * there was no such entry with the specified key.
0470: */
0471: private Entry removeImpl(Object key) {
0472: Entry e = (Entry) entries.remove(key);
0473: if (e == null)
0474: return null;
0475: modCount++;
0476: removeEntry(e);
0477: return e;
0478: }
0479:
0480: /**
0481: * Adds all the mappings in the specified map to this map, replacing any
0482: * mappings that already exist (as per {@link Map#putAll(Map)}). The order
0483: * in which the entries are added is determined by the iterator returned
0484: * from {@link Map#entrySet()} for the specified map.
0485: *
0486: * @param t the mappings that should be added to this map.
0487: *
0488: * @throws NullPointerException if <code>t</code> is <code>null</code>
0489: */
0490: public void putAll(Map t) {
0491: Iterator iter = t.entrySet().iterator();
0492: while (iter.hasNext()) {
0493: Map.Entry entry = (Map.Entry) iter.next();
0494: put(entry.getKey(), entry.getValue());
0495: }
0496: }
0497:
0498: /**
0499: * Implements {@link Map#clear()}.
0500: */
0501: public void clear() {
0502: modCount++;
0503:
0504: // remove all from the underlying map
0505: entries.clear();
0506:
0507: // and the list
0508: sentinel.next = sentinel;
0509: sentinel.prev = sentinel;
0510: }
0511:
0512: /**
0513: * Implements {@link Map#equals(Object)}.
0514: */
0515: public boolean equals(Object obj) {
0516: if (obj == null)
0517: return false;
0518: if (obj == this )
0519: return true;
0520:
0521: if (!(obj instanceof Map))
0522: return false;
0523:
0524: return entrySet().equals(((Map) obj).entrySet());
0525: }
0526:
0527: /**
0528: * Implements {@link Map#hashCode()}.
0529: */
0530: public int hashCode() {
0531: return entrySet().hashCode();
0532: }
0533:
0534: /**
0535: * Provides a string representation of the entries within the map. The
0536: * format of the returned string may change with different releases, so this
0537: * method is suitable for debugging purposes only. If a specific format is
0538: * required, use {@link #entrySet()}.{@link Set#iterator() iterator()} and
0539: * iterate over the entries in the map formatting them as appropriate.
0540: */
0541: public String toString() {
0542: StringBuffer buf = new StringBuffer();
0543: buf.append('[');
0544: for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
0545: buf.append(pos.getKey());
0546: buf.append('=');
0547: buf.append(pos.getValue());
0548: if (pos.next != sentinel) {
0549: buf.append(',');
0550: }
0551: }
0552: buf.append(']');
0553:
0554: return buf.toString();
0555: }
0556:
0557: /**
0558: * Implements {@link Map#keySet()}.
0559: */
0560: public Set keySet() {
0561: return new AbstractSet() {
0562:
0563: // required impls
0564: public Iterator iterator() {
0565: return new OrderedIterator(KEY);
0566: }
0567:
0568: public boolean remove(Object o) {
0569: Entry e = SequencedHashMap.this .removeImpl(o);
0570: return (e != null);
0571: }
0572:
0573: // more efficient impls than abstract set
0574: public void clear() {
0575: SequencedHashMap.this .clear();
0576: }
0577:
0578: public int size() {
0579: return SequencedHashMap.this .size();
0580: }
0581:
0582: public boolean isEmpty() {
0583: return SequencedHashMap.this .isEmpty();
0584: }
0585:
0586: public boolean contains(Object o) {
0587: return SequencedHashMap.this .containsKey(o);
0588: }
0589:
0590: };
0591: }
0592:
0593: /**
0594: * Implements {@link Map#values()}.
0595: */
0596: public Collection values() {
0597: return new AbstractCollection() {
0598: // required impl
0599: public Iterator iterator() {
0600: return new OrderedIterator(VALUE);
0601: }
0602:
0603: public boolean remove(Object value) {
0604: // do null comparison outside loop so we only need to do it once. This
0605: // provides a tighter, more efficient loop at the expense of slight
0606: // code duplication.
0607: if (value == null) {
0608: for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
0609: if (pos.getValue() == null) {
0610: SequencedHashMap.this .removeImpl(pos
0611: .getKey());
0612: return true;
0613: }
0614: }
0615: } else {
0616: for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
0617: if (value.equals(pos.getValue())) {
0618: SequencedHashMap.this .removeImpl(pos
0619: .getKey());
0620: return true;
0621: }
0622: }
0623: }
0624:
0625: return false;
0626: }
0627:
0628: // more efficient impls than abstract collection
0629: public void clear() {
0630: SequencedHashMap.this .clear();
0631: }
0632:
0633: public int size() {
0634: return SequencedHashMap.this .size();
0635: }
0636:
0637: public boolean isEmpty() {
0638: return SequencedHashMap.this .isEmpty();
0639: }
0640:
0641: public boolean contains(Object o) {
0642: return SequencedHashMap.this .containsValue(o);
0643: }
0644: };
0645: }
0646:
0647: /**
0648: * Implements {@link Map#entrySet()}.
0649: */
0650: public Set entrySet() {
0651: return new AbstractSet() {
0652: // helper
0653: private Entry findEntry(Object o) {
0654: if (o == null)
0655: return null;
0656: if (!(o instanceof Map.Entry))
0657: return null;
0658:
0659: Map.Entry e = (Map.Entry) o;
0660: Entry entry = (Entry) entries.get(e.getKey());
0661: if (entry != null && entry.equals(e))
0662: return entry;
0663: else
0664: return null;
0665: }
0666:
0667: // required impl
0668: public Iterator iterator() {
0669: return new OrderedIterator(ENTRY);
0670: }
0671:
0672: public boolean remove(Object o) {
0673: Entry e = findEntry(o);
0674: if (e == null)
0675: return false;
0676:
0677: return SequencedHashMap.this .removeImpl(e.getKey()) != null;
0678: }
0679:
0680: // more efficient impls than abstract collection
0681: public void clear() {
0682: SequencedHashMap.this .clear();
0683: }
0684:
0685: public int size() {
0686: return SequencedHashMap.this .size();
0687: }
0688:
0689: public boolean isEmpty() {
0690: return SequencedHashMap.this .isEmpty();
0691: }
0692:
0693: public boolean contains(Object o) {
0694: return findEntry(o) != null;
0695: }
0696: };
0697: }
0698:
0699: // constants to define what the iterator should return on "next"
0700: private static final int KEY = 0;
0701: private static final int VALUE = 1;
0702: private static final int ENTRY = 2;
0703: private static final int REMOVED_MASK = 0x80000000;
0704:
0705: private class OrderedIterator implements Iterator {
0706: /**
0707: * Holds the type that should be returned from the iterator. The value
0708: * should be either {@link #KEY}, {@link #VALUE}, or {@link #ENTRY}. To
0709: * save a tiny bit of memory, this field is also used as a marker for when
0710: * remove has been called on the current object to prevent a second remove
0711: * on the same element. Essentially, if this value is negative (i.e. the
0712: * bit specified by {@link #REMOVED_MASK} is set), the current position
0713: * has been removed. If positive, remove can still be called.
0714: */
0715: private int returnType;
0716:
0717: /**
0718: * Holds the "current" position in the iterator. When pos.next is the
0719: * sentinel, we've reached the end of the list.
0720: */
0721: private Entry pos = sentinel;
0722:
0723: /**
0724: * Holds the expected modification count. If the actual modification
0725: * count of the map differs from this value, then a concurrent
0726: * modification has occurred.
0727: */
0728: private transient long expectedModCount = modCount;
0729:
0730: /**
0731: * Construct an iterator over the sequenced elements in the order in which
0732: * they were added. The {@link #next()} method returns the type specified
0733: * by <code>returnType</code> which must be either {@link #KEY}, {@link
0734: * #VALUE}, or {@link #ENTRY}.
0735: */
0736: public OrderedIterator(int returnType) {
0737: //// Since this is a private inner class, nothing else should have
0738: //// access to the constructor. Since we know the rest of the outer
0739: //// class uses the iterator correctly, we can leave of the following
0740: //// check:
0741: //if(returnType >= 0 && returnType <= 2) {
0742: // throw new IllegalArgumentException("Invalid iterator type");
0743: //}
0744:
0745: // Set the "removed" bit so that the iterator starts in a state where
0746: // "next" must be called before "remove" will succeed.
0747: this .returnType = returnType | REMOVED_MASK;
0748: }
0749:
0750: /**
0751: * Returns whether there is any additional elements in the iterator to be
0752: * returned.
0753: *
0754: * @return <code>true</code> if there are more elements left to be
0755: * returned from the iterator; <code>false</code> otherwise.
0756: */
0757: public boolean hasNext() {
0758: return pos.next != sentinel;
0759: }
0760:
0761: /**
0762: * Returns the next element from the iterator.
0763: *
0764: * @return the next element from the iterator.
0765: *
0766: * @throws NoSuchElementException if there are no more elements in the
0767: * iterator.
0768: *
0769: * @throws ConcurrentModificationException if a modification occurs in
0770: * the underlying map.
0771: */
0772: public Object next() {
0773: if (modCount != expectedModCount) {
0774: throw new ConcurrentModificationException();
0775: }
0776: if (pos.next == sentinel) {
0777: throw new NoSuchElementException();
0778: }
0779:
0780: // clear the "removed" flag
0781: returnType = returnType & ~REMOVED_MASK;
0782:
0783: pos = pos.next;
0784: switch (returnType) {
0785: case KEY:
0786: return pos.getKey();
0787: case VALUE:
0788: return pos.getValue();
0789: case ENTRY:
0790: return pos;
0791: default:
0792: // should never happen
0793: throw new Error("bad iterator type: " + returnType);
0794: }
0795:
0796: }
0797:
0798: /**
0799: * Removes the last element returned from the {@link #next()} method from
0800: * the sequenced map.
0801: *
0802: * @throws IllegalStateException if there isn't a "last element" to be
0803: * removed. That is, if {@link #next()} has never been called, or if
0804: * {@link #remove()} was already called on the element.
0805: *
0806: * @throws ConcurrentModificationException if a modification occurs in
0807: * the underlying map.
0808: */
0809: public void remove() {
0810: if ((returnType & REMOVED_MASK) != 0) {
0811: throw new IllegalStateException(
0812: "remove() must follow next()");
0813: }
0814: if (modCount != expectedModCount) {
0815: throw new ConcurrentModificationException();
0816: }
0817:
0818: SequencedHashMap.this .removeImpl(pos.getKey());
0819:
0820: // update the expected mod count for the remove operation
0821: expectedModCount++;
0822:
0823: // set the removed flag
0824: returnType = returnType | REMOVED_MASK;
0825: }
0826: }
0827:
0828: // APIs maintained from previous version of SequencedHashMap for backwards
0829: // compatibility
0830:
0831: /**
0832: * Creates a shallow copy of this object, preserving the internal structure
0833: * by copying only references. The keys and values themselves are not
0834: * <code>clone()</code>'d. The cloned object maintains the same sequence.
0835: *
0836: * @return A clone of this instance.
0837: *
0838: * @throws CloneNotSupportedException if clone is not supported by a
0839: * subclass.
0840: */
0841: public Object clone() throws CloneNotSupportedException {
0842: // yes, calling super.clone() silly since we're just blowing away all
0843: // the stuff that super might be doing anyway, but for motivations on
0844: // this, see:
0845: // http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html
0846: SequencedHashMap map = (SequencedHashMap) super .clone();
0847:
0848: // create new, empty sentinel
0849: map.sentinel = createSentinel();
0850:
0851: // create a new, empty entry map
0852: // note: this does not preserve the initial capacity and load factor.
0853: map.entries = new HashMap();
0854:
0855: // add all the mappings
0856: map.putAll(this );
0857:
0858: // Note: We cannot just clone the hashmap and sentinel because we must
0859: // duplicate our internal structures. Cloning those two will not clone all
0860: // the other entries they reference, and so the cloned hash map will not be
0861: // able to maintain internal consistency because there are two objects with
0862: // the same entries. See discussion in the Entry implementation on why we
0863: // cannot implement a clone of the Entry (and thus why we need to recreate
0864: // everything).
0865:
0866: return map;
0867: }
0868:
0869: /**
0870: * Returns the Map.Entry at the specified index
0871: *
0872: * @throws ArrayIndexOutOfBoundsException if the specified index is
0873: * <code>< 0</code> or <code>></code> the size of the map.
0874: */
0875: private Map.Entry getEntry(int index) {
0876: Entry pos = sentinel;
0877:
0878: if (index < 0) {
0879: throw new ArrayIndexOutOfBoundsException(index + " < 0");
0880: }
0881:
0882: // loop to one before the position
0883: int i = -1;
0884: while (i < (index - 1) && pos.next != sentinel) {
0885: i++;
0886: pos = pos.next;
0887: }
0888: // pos.next is the requested position
0889:
0890: // if sentinel is next, past end of list
0891: if (pos.next == sentinel) {
0892: throw new ArrayIndexOutOfBoundsException(index + " >= "
0893: + (i + 1));
0894: }
0895:
0896: return pos.next;
0897: }
0898:
0899: /**
0900: * Gets the key at the specified index.
0901: *
0902: * @param index the index to retrieve
0903: * @return the key at the specified index, or null
0904: * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is
0905: * <code>< 0</code> or <code>></code> the size of the map.
0906: */
0907: public Object get(int index) {
0908: return getEntry(index).getKey();
0909: }
0910:
0911: /**
0912: * Gets the value at the specified index.
0913: *
0914: * @param index the index to retrieve
0915: * @return the value at the specified index, or null
0916: * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is
0917: * <code>< 0</code> or <code>></code> the size of the map.
0918: */
0919: public Object getValue(int index) {
0920: return getEntry(index).getValue();
0921: }
0922:
0923: /**
0924: * Gets the index of the specified key.
0925: *
0926: * @param key the key to find the index of
0927: * @return the index, or -1 if not found
0928: */
0929: public int indexOf(Object key) {
0930: Entry e = (Entry) entries.get(key);
0931: if (e == null) {
0932: return -1;
0933: }
0934: int pos = 0;
0935: while (e.prev != sentinel) {
0936: pos++;
0937: e = e.prev;
0938: }
0939: return pos;
0940: }
0941:
0942: /**
0943: * Gets an iterator over the keys.
0944: *
0945: * @return an iterator over the keys
0946: */
0947: public Iterator iterator() {
0948: return keySet().iterator();
0949: }
0950:
0951: /**
0952: * Gets the last index of the specified key.
0953: *
0954: * @param key the key to find the index of
0955: * @return the index, or -1 if not found
0956: */
0957: public int lastIndexOf(Object key) {
0958: // keys in a map are guaranteed to be unique
0959: return indexOf(key);
0960: }
0961:
0962: /**
0963: * Returns a List view of the keys rather than a set view. The returned
0964: * list is unmodifiable. This is required because changes to the values of
0965: * the list (using {@link java.util.ListIterator#set(Object)}) will
0966: * effectively remove the value from the list and reinsert that value at
0967: * the end of the list, which is an unexpected side effect of changing the
0968: * value of a list. This occurs because changing the key, changes when the
0969: * mapping is added to the map and thus where it appears in the list.
0970: *
0971: * <p>An alternative to this method is to use {@link #keySet()}
0972: *
0973: * @see #keySet()
0974: * @return The ordered list of keys.
0975: */
0976: public List sequence() {
0977: List l = new ArrayList(size());
0978: Iterator iter = keySet().iterator();
0979: while (iter.hasNext()) {
0980: l.add(iter.next());
0981: }
0982:
0983: return UnmodifiableList.decorate(l);
0984: }
0985:
0986: /**
0987: * Removes the element at the specified index.
0988: *
0989: * @param index The index of the object to remove.
0990: * @return The previous value corresponding the <code>key</code>, or
0991: * <code>null</code> if none existed.
0992: *
0993: * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is
0994: * <code>< 0</code> or <code>></code> the size of the map.
0995: */
0996: public Object remove(int index) {
0997: return remove(get(index));
0998: }
0999:
1000: // per Externalizable.readExternal(ObjectInput)
1001:
1002: /**
1003: * Deserializes this map from the given stream.
1004: *
1005: * @param in the stream to deserialize from
1006: * @throws IOException if the stream raises it
1007: * @throws ClassNotFoundException if the stream raises it
1008: */
1009: public void readExternal(ObjectInput in) throws IOException,
1010: ClassNotFoundException {
1011: int size = in.readInt();
1012: for (int i = 0; i < size; i++) {
1013: Object key = in.readObject();
1014: Object value = in.readObject();
1015: put(key, value);
1016: }
1017: }
1018:
1019: /**
1020: * Serializes this map to the given stream.
1021: *
1022: * @param out the stream to serialize to
1023: * @throws IOException if the stream raises it
1024: */
1025: public void writeExternal(ObjectOutput out) throws IOException {
1026: out.writeInt(size());
1027: for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
1028: out.writeObject(pos.getKey());
1029: out.writeObject(pos.getValue());
1030: }
1031: }
1032:
1033: // add a serial version uid, so that if we change things in the future
1034: // without changing the format, we can still deserialize properly.
1035: private static final long serialVersionUID = 3380552487888102930L;
1036:
1037: }
|