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