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