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