0001: /*
0002: * @(#)TreeMap.java 1.50 06/10/10
0003: *
0004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
0005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
0006: *
0007: * This program is free software; you can redistribute it and/or
0008: * modify it under the terms of the GNU General Public License version
0009: * 2 only, as published by the Free Software Foundation.
0010: *
0011: * This program is distributed in the hope that it will be useful, but
0012: * WITHOUT ANY WARRANTY; without even the implied warranty of
0013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0014: * General Public License version 2 for more details (a copy is
0015: * included at /legal/license.txt).
0016: *
0017: * You should have received a copy of the GNU General Public License
0018: * version 2 along with this work; if not, write to the Free Software
0019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
0020: * 02110-1301 USA
0021: *
0022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
0023: * Clara, CA 95054 or visit www.sun.com if you need additional
0024: * information or have any questions.
0025: *
0026: */
0027:
0028: package java.util;
0029:
0030: /**
0031: * Red-Black tree based implementation of the <tt>SortedMap</tt> interface.
0032: * This class guarantees that the map will be in ascending key order, sorted
0033: * according to the <i>natural order</i> for the key's class (see
0034: * <tt>Comparable</tt>), or by the comparator provided at creation time,
0035: * depending on which constructor is used.<p>
0036: *
0037: * This implementation provides guaranteed log(n) time cost for the
0038: * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and <tt>remove</tt>
0039: * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
0040: * Rivest's <I>Introduction to Algorithms</I>.<p>
0041: *
0042: * Note that the ordering maintained by a sorted map (whether or not an
0043: * explicit comparator is provided) must be <i>consistent with equals</i> if
0044: * this sorted map is to correctly implement the <tt>Map</tt> interface. (See
0045: * <tt>Comparable</tt> or <tt>Comparator</tt> for a precise definition of
0046: * <i>consistent with equals</i>.) This is so because the <tt>Map</tt>
0047: * interface is defined in terms of the equals operation, but a map performs
0048: * all key comparisons using its <tt>compareTo</tt> (or <tt>compare</tt>)
0049: * method, so two keys that are deemed equal by this method are, from the
0050: * standpoint of the sorted map, equal. The behavior of a sorted map
0051: * <i>is</i> well-defined even if its ordering is inconsistent with equals; it
0052: * just fails to obey the general contract of the <tt>Map</tt> interface.<p>
0053: *
0054: * <b>Note that this implementation is not synchronized.</b> If multiple
0055: * threads access a map concurrently, and at least one of the threads modifies
0056: * the map structurally, it <i>must</i> be synchronized externally. (A
0057: * structural modification is any operation that adds or deletes one or more
0058: * mappings; merely changing the value associated with an existing key is not
0059: * a structural modification.) This is typically accomplished by
0060: * synchronizing on some object that naturally encapsulates the map. If no
0061: * such object exists, the map should be "wrapped" using the
0062: * <tt>Collections.synchronizedMap</tt> method. This is best done at creation
0063: * time, to prevent accidental unsynchronized access to the map:
0064: * <pre>
0065: * Map m = Collections.synchronizedMap(new TreeMap(...));
0066: * </pre><p>
0067: *
0068: * The iterators returned by all of this class's "collection view methods" are
0069: * <i>fail-fast</i>: if the map is structurally modified at any time after the
0070: * iterator is created, in any way except through the iterator's own
0071: * <tt>remove</tt> or <tt>add</tt> methods, the iterator throws a
0072: * <tt>ConcurrentModificationException</tt>. Thus, in the face of concurrent
0073: * modification, the iterator fails quickly and cleanly, rather than risking
0074: * arbitrary, non-deterministic behavior at an undetermined time in the
0075: * future.
0076: *
0077: * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
0078: * as it is, generally speaking, impossible to make any hard guarantees in the
0079: * presence of unsynchronized concurrent modification. Fail-fast iterators
0080: * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
0081: * Therefore, it would be wrong to write a program that depended on this
0082: * exception for its correctness: <i>the fail-fast behavior of iterators
0083: * should be used only to detect bugs.</i><p>
0084: *
0085: * This class is a member of the
0086: * <a href="{@docRoot}/../guide/collections/index.html">
0087: * Java Collections Framework</a>.
0088: *
0089: * @author Josh Bloch and Doug Lea
0090: * @version 1.43, 02/02/00
0091: * @see Map
0092: * @see HashMap
0093: * @see Hashtable
0094: * @see Comparable
0095: * @see Comparator
0096: * @see Collection
0097: * @see Collections#synchronizedMap(Map)
0098: * @since 1.2
0099: */
0100:
0101: public class TreeMap extends AbstractMap implements SortedMap,
0102: Cloneable, java.io.Serializable {
0103: /**
0104: * The Comparator used to maintain order in this TreeMap, or
0105: * null if this TreeMap uses its elements natural ordering.
0106: *
0107: * @serial
0108: */
0109: private Comparator comparator = null;
0110:
0111: private transient Entry root = null;
0112:
0113: /**
0114: * The number of entries in the tree
0115: */
0116: private transient int size = 0;
0117:
0118: /**
0119: * The number of structural modifications to the tree.
0120: */
0121: private transient int modCount = 0;
0122:
0123: private void incrementSize() {
0124: modCount++;
0125: size++;
0126: }
0127:
0128: private void decrementSize() {
0129: modCount++;
0130: size--;
0131: }
0132:
0133: /**
0134: * Constructs a new, empty map, sorted according to the keys' natural
0135: * order. All keys inserted into the map must implement the
0136: * <tt>Comparable</tt> interface. Furthermore, all such keys must be
0137: * <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
0138: * ClassCastException for any elements <tt>k1</tt> and <tt>k2</tt> in the
0139: * map. If the user attempts to put a key into the map that violates this
0140: * constraint (for example, the user attempts to put a string key into a
0141: * map whose keys are integers), the <tt>put(Object key, Object
0142: * value)</tt> call will throw a <tt>ClassCastException</tt>.
0143: *
0144: * @see Comparable
0145: */
0146: public TreeMap() {
0147: }
0148:
0149: /**
0150: * Constructs a new, empty map, sorted according to the given comparator.
0151: * All keys inserted into the map must be <i>mutually comparable</i> by
0152: * the given comparator: <tt>comparator.compare(k1, k2)</tt> must not
0153: * throw a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
0154: * <tt>k2</tt> in the map. If the user attempts to put a key into the
0155: * map that violates this constraint, the <tt>put(Object key, Object
0156: * value)</tt> call will throw a <tt>ClassCastException</tt>.
0157: *
0158: * @param c the comparator that will be used to sort this map. A
0159: * <tt>null</tt> value indicates that the keys' <i>natural
0160: * ordering</i> should be used.
0161: */
0162: public TreeMap(Comparator c) {
0163: this .comparator = c;
0164: }
0165:
0166: /**
0167: * Constructs a new map containing the same mappings as the given map,
0168: * sorted according to the keys' <i>natural order</i>. All keys inserted
0169: * into the new map must implement the <tt>Comparable</tt> interface.
0170: * Furthermore, all such keys must be <i>mutually comparable</i>:
0171: * <tt>k1.compareTo(k2)</tt> must not throw a <tt>ClassCastException</tt>
0172: * for any elements <tt>k1</tt> and <tt>k2</tt> in the map. This method
0173: * runs in n*log(n) time.
0174: *
0175: * @param m the map whose mappings are to be placed in this map.
0176: * @throws ClassCastException the keys in t are not Comparable, or
0177: * are not mutually comparable.
0178: * @throws NullPointerException if the specified map is null.
0179: */
0180: public TreeMap(Map m) {
0181: putAll(m);
0182: }
0183:
0184: /**
0185: * Constructs a new map containing the same mappings as the given
0186: * <tt>SortedMap</tt>, sorted according to the same ordering. This method
0187: * runs in linear time.
0188: *
0189: * @param m the sorted map whose mappings are to be placed in this map,
0190: * and whose comparator is to be used to sort this map.
0191: * @throws NullPointerException if the specified sorted map is null.
0192: */
0193: public TreeMap(SortedMap m) {
0194: comparator = m.comparator();
0195: try {
0196: buildFromSorted(m.size(), m.entrySet().iterator(), null,
0197: null);
0198: } catch (java.io.IOException cannotHappen) {
0199: } catch (ClassNotFoundException cannotHappen) {
0200: }
0201: }
0202:
0203: // Query Operations
0204:
0205: /**
0206: * Returns the number of key-value mappings in this map.
0207: *
0208: * @return the number of key-value mappings in this map.
0209: */
0210: public int size() {
0211: return size;
0212: }
0213:
0214: /**
0215: * Returns <tt>true</tt> if this map contains a mapping for the specified
0216: * key.
0217: *
0218: * @param key key whose presence in this map is to be tested.
0219: *
0220: * @return <tt>true</tt> if this map contains a mapping for the
0221: * specified key.
0222: * @throws ClassCastException if the key cannot be compared with the keys
0223: * currently in the map.
0224: * @throws NullPointerException key is <tt>null</tt> and this map uses
0225: * natural ordering, or its comparator does not tolerate
0226: * <tt>null</tt> keys.
0227: */
0228: public boolean containsKey(Object key) {
0229: return getEntry(key) != null;
0230: }
0231:
0232: /**
0233: * Returns <tt>true</tt> if this map maps one or more keys to the
0234: * specified value. More formally, returns <tt>true</tt> if and only if
0235: * this map contains at least one mapping to a value <tt>v</tt> such
0236: * that <tt>(value==null ? v==null : value.equals(v))</tt>. This
0237: * operation will probably require time linear in the Map size for most
0238: * implementations of Map.
0239: *
0240: * @param value value whose presence in this Map is to be tested.
0241: * @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
0242: * <tt>false</tt> otherwise.
0243: * @since 1.2
0244: */
0245: public boolean containsValue(Object value) {
0246: return (root == null ? false
0247: : (value == null ? valueSearchNull(root)
0248: : valueSearchNonNull(root, value)));
0249: }
0250:
0251: private boolean valueSearchNull(Entry n) {
0252: if (n.value == null)
0253: return true;
0254:
0255: // Check left and right subtrees for value
0256: return (n.left != null && valueSearchNull(n.left))
0257: || (n.right != null && valueSearchNull(n.right));
0258: }
0259:
0260: private boolean valueSearchNonNull(Entry n, Object value) {
0261: // Check this node for the value
0262: if (value.equals(n.value))
0263: return true;
0264:
0265: // Check left and right subtrees for value
0266: return (n.left != null && valueSearchNonNull(n.left, value))
0267: || (n.right != null && valueSearchNonNull(n.right,
0268: value));
0269: }
0270:
0271: /**
0272: * Returns the value to which this map maps the specified key. Returns
0273: * <tt>null</tt> if the map contains no mapping for this key. A return
0274: * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
0275: * map contains no mapping for the key; it's also possible that the map
0276: * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
0277: * operation may be used to distinguish these two cases.
0278: *
0279: * @param key key whose associated value is to be returned.
0280: * @return the value to which this map maps the specified key, or
0281: * <tt>null</tt> if the map contains no mapping for the key.
0282: * @throws ClassCastException key cannot be compared with the keys
0283: * currently in the map.
0284: * @throws NullPointerException key is <tt>null</tt> and this map uses
0285: * natural ordering, or its comparator does not tolerate
0286: * <tt>null</tt> keys.
0287: *
0288: * @see #containsKey(Object)
0289: */
0290: public Object get(Object key) {
0291: Entry p = getEntry(key);
0292: return (p == null ? null : p.value);
0293: }
0294:
0295: /**
0296: * Returns the comparator used to order this map, or <tt>null</tt> if this
0297: * map uses its keys' natural order.
0298: *
0299: * @return the comparator associated with this sorted map, or
0300: * <tt>null</tt> if it uses its keys' natural sort method.
0301: */
0302: public Comparator comparator() {
0303: return comparator;
0304: }
0305:
0306: /**
0307: * Returns the first (lowest) key currently in this sorted map.
0308: *
0309: * @return the first (lowest) key currently in this sorted map.
0310: * @throws NoSuchElementException Map is empty.
0311: */
0312: public Object firstKey() {
0313: return key(firstEntry());
0314: }
0315:
0316: /**
0317: * Returns the last (highest) key currently in this sorted map.
0318: *
0319: * @return the last (highest) key currently in this sorted map.
0320: * @throws NoSuchElementException Map is empty.
0321: */
0322: public Object lastKey() {
0323: return key(lastEntry());
0324: }
0325:
0326: /**
0327: * Copies all of the mappings from the specified map to this map. These
0328: * mappings replace any mappings that this map had for any of the keys
0329: * currently in the specified map.
0330: *
0331: * @param map mappings to be stored in this map.
0332: * @throws ClassCastException class of a key or value in the specified
0333: * map prevents it from being stored in this map.
0334: *
0335: * @throws NullPointerException if the given map is <tt>null</tt> or
0336: * this map does not permit <tt>null</tt> keys and a
0337: * key in the specified map is <tt>null</tt>.
0338: */
0339: public void putAll(Map map) {
0340: int mapSize = map.size();
0341: if (size == 0 && mapSize != 0 && map instanceof SortedMap) {
0342: Comparator c = ((SortedMap) map).comparator();
0343: if (c == comparator || (c != null && c.equals(comparator))) {
0344: ++modCount;
0345: try {
0346: buildFromSorted(mapSize, map.entrySet().iterator(),
0347: null, null);
0348: } catch (java.io.IOException cannotHappen) {
0349: } catch (ClassNotFoundException cannotHappen) {
0350: }
0351: return;
0352: }
0353: }
0354: super .putAll(map);
0355: }
0356:
0357: /**
0358: * Returns this map's entry for the given key, or <tt>null</tt> if the map
0359: * does not contain an entry for the key.
0360: *
0361: * @return this map's entry for the given key, or <tt>null</tt> if the map
0362: * does not contain an entry for the key.
0363: * @throws ClassCastException if the key cannot be compared with the keys
0364: * currently in the map.
0365: * @throws NullPointerException key is <tt>null</tt> and this map uses
0366: * natural order, or its comparator does not tolerate *
0367: * <tt>null</tt> keys.
0368: */
0369: private Entry getEntry(Object key) {
0370: Entry p = root;
0371: while (p != null) {
0372: int cmp = compare(key, p.key);
0373: if (cmp == 0)
0374: return p;
0375: else if (cmp < 0)
0376: p = p.left;
0377: else
0378: p = p.right;
0379: }
0380: return null;
0381: }
0382:
0383: /**
0384: * Gets the entry corresponding to the specified key; if no such entry
0385: * exists, returns the entry for the least key greater than the specified
0386: * key; if no such entry exists (i.e., the greatest key in the Tree is less
0387: * than the specified key), returns <tt>null</tt>.
0388: */
0389: private Entry getCeilEntry(Object key) {
0390: Entry p = root;
0391: if (p == null)
0392: return null;
0393:
0394: while (true) {
0395: int cmp = compare(key, p.key);
0396: if (cmp == 0) {
0397: return p;
0398: } else if (cmp < 0) {
0399: if (p.left != null)
0400: p = p.left;
0401: else
0402: return p;
0403: } else {
0404: if (p.right != null) {
0405: p = p.right;
0406: } else {
0407: Entry parent = p.parent;
0408: Entry ch = p;
0409: while (parent != null && ch == parent.right) {
0410: ch = parent;
0411: parent = parent.parent;
0412: }
0413: return parent;
0414: }
0415: }
0416: }
0417: }
0418:
0419: /**
0420: * Returns the entry for the greatest key less than the specified key; if
0421: * no such entry exists (i.e., the least key in the Tree is greater than
0422: * the specified key), returns <tt>null</tt>.
0423: */
0424: private Entry getPrecedingEntry(Object key) {
0425: Entry p = root;
0426: if (p == null)
0427: return null;
0428:
0429: while (true) {
0430: int cmp = compare(key, p.key);
0431: if (cmp > 0) {
0432: if (p.right != null)
0433: p = p.right;
0434: else
0435: return p;
0436: } else {
0437: if (p.left != null) {
0438: p = p.left;
0439: } else {
0440: Entry parent = p.parent;
0441: Entry ch = p;
0442: while (parent != null && ch == parent.left) {
0443: ch = parent;
0444: parent = parent.parent;
0445: }
0446: return parent;
0447: }
0448: }
0449: }
0450: }
0451:
0452: /**
0453: * Returns the key corresonding to the specified Entry. Throw
0454: * NoSuchElementException if the Entry is <tt>null</tt>.
0455: */
0456: private static Object key(Entry e) {
0457: if (e == null)
0458: throw new NoSuchElementException();
0459: return e.key;
0460: }
0461:
0462: /**
0463: * Associates the specified value with the specified key in this map.
0464: * If the map previously contained a mapping for this key, the old
0465: * value is replaced.
0466: *
0467: * @param key key with which the specified value is to be associated.
0468: * @param value value to be associated with the specified key.
0469: *
0470: * @return previous value associated with specified key, or <tt>null</tt>
0471: * if there was no mapping for key. A <tt>null</tt> return can
0472: * also indicate that the map previously associated <tt>null</tt>
0473: * with the specified key.
0474: * @throws ClassCastException key cannot be compared with the keys
0475: * currently in the map.
0476: * @throws NullPointerException key is <tt>null</tt> and this map uses
0477: * natural order, or its comparator does not tolerate
0478: * <tt>null</tt> keys.
0479: */
0480: public Object put(Object key, Object value) {
0481: Entry t = root;
0482:
0483: if (t == null) {
0484: incrementSize();
0485: root = new Entry(key, value, null);
0486: return null;
0487: }
0488:
0489: while (true) {
0490: int cmp = compare(key, t.key);
0491: if (cmp == 0) {
0492: return t.setValue(value);
0493: } else if (cmp < 0) {
0494: if (t.left != null) {
0495: t = t.left;
0496: } else {
0497: incrementSize();
0498: t.left = new Entry(key, value, t);
0499: fixAfterInsertion(t.left);
0500: return null;
0501: }
0502: } else { // cmp > 0
0503: if (t.right != null) {
0504: t = t.right;
0505: } else {
0506: incrementSize();
0507: t.right = new Entry(key, value, t);
0508: fixAfterInsertion(t.right);
0509: return null;
0510: }
0511: }
0512: }
0513: }
0514:
0515: /**
0516: * Removes the mapping for this key from this TreeMap if present.
0517: *
0518: * @param key key for which mapping should be removed
0519: * @return previous value associated with specified key, or <tt>null</tt>
0520: * if there was no mapping for key. A <tt>null</tt> return can
0521: * also indicate that the map previously associated
0522: * <tt>null</tt> with the specified key.
0523: *
0524: * @throws ClassCastException key cannot be compared with the keys
0525: * currently in the map.
0526: * @throws NullPointerException key is <tt>null</tt> and this map uses
0527: * natural order, or its comparator does not tolerate
0528: * <tt>null</tt> keys.
0529: */
0530: public Object remove(Object key) {
0531: Entry p = getEntry(key);
0532: if (p == null)
0533: return null;
0534:
0535: Object oldValue = p.value;
0536: deleteEntry(p);
0537: return oldValue;
0538: }
0539:
0540: /**
0541: * Removes all mappings from this TreeMap.
0542: */
0543: public void clear() {
0544: modCount++;
0545: size = 0;
0546: root = null;
0547: }
0548:
0549: /**
0550: * Returns a shallow copy of this <tt>TreeMap</tt> instance. (The keys and
0551: * values themselves are not cloned.)
0552: *
0553: * @return a shallow copy of this Map.
0554: */
0555: public Object clone() {
0556: TreeMap clone = null;
0557: try {
0558: clone = (TreeMap) super .clone();
0559: } catch (CloneNotSupportedException e) {
0560: throw new InternalError();
0561: }
0562:
0563: // Put clone into "virgin" state (except for comparator)
0564: clone.root = null;
0565: clone.size = 0;
0566: clone.modCount = 0;
0567: clone.entrySet = null;
0568:
0569: // Initialize clone with our mappings
0570: try {
0571: clone.buildFromSorted(size, entrySet().iterator(), null,
0572: null);
0573: } catch (java.io.IOException cannotHappen) {
0574: } catch (ClassNotFoundException cannotHappen) {
0575: }
0576:
0577: return clone;
0578: }
0579:
0580: // Views
0581:
0582: /**
0583: * This field is initialized to contain an instance of the entry set
0584: * view the first time this view is requested. The view is stateless,
0585: * so there's no reason to create more than one.
0586: */
0587: private transient volatile Set entrySet = null;
0588:
0589: /**
0590: * Returns a Set view of the keys contained in this map. The set's
0591: * iterator will return the keys in ascending order. The map is backed by
0592: * this <tt>TreeMap</tt> instance, so changes to this map are reflected in
0593: * the Set, and vice-versa. The Set supports element removal, which
0594: * removes the corresponding mapping from the map, via the
0595: * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
0596: * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support
0597: * the <tt>add</tt> or <tt>addAll</tt> operations.
0598: *
0599: * @return a set view of the keys contained in this TreeMap.
0600: */
0601: public Set keySet() {
0602: if (keySet == null) {
0603: keySet = new AbstractSet() {
0604: public Iterator iterator() {
0605: return new KeyIterator();
0606: }
0607:
0608: public int size() {
0609: return TreeMap.this .size();
0610: }
0611:
0612: public boolean contains(Object o) {
0613: return containsKey(o);
0614: }
0615:
0616: public boolean remove(Object o) {
0617: int oldSize = size;
0618: TreeMap.this .remove(o);
0619: return size != oldSize;
0620: }
0621:
0622: public void clear() {
0623: TreeMap.this .clear();
0624: }
0625: };
0626: }
0627: return keySet;
0628: }
0629:
0630: /**
0631: * Returns a collection view of the values contained in this map. The
0632: * collection's iterator will return the values in the order that their
0633: * corresponding keys appear in the tree. The collection is backed by
0634: * this <tt>TreeMap</tt> instance, so changes to this map are reflected in
0635: * the collection, and vice-versa. The collection supports element
0636: * removal, which removes the corresponding mapping from the map through
0637: * the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
0638: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
0639: * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
0640: *
0641: * @return a collection view of the values contained in this map.
0642: */
0643: public Collection values() {
0644: if (values == null) {
0645: values = new AbstractCollection() {
0646: public Iterator iterator() {
0647: return new ValueIterator();
0648: }
0649:
0650: public int size() {
0651: return TreeMap.this .size();
0652: }
0653:
0654: public boolean contains(Object o) {
0655: for (Entry e = firstEntry(); e != null; e = successor(e))
0656: if (valEquals(e.getValue(), o))
0657: return true;
0658: return false;
0659: }
0660:
0661: public boolean remove(Object o) {
0662: for (Entry e = firstEntry(); e != null; e = successor(e)) {
0663: if (valEquals(e.getValue(), o)) {
0664: deleteEntry(e);
0665: return true;
0666: }
0667: }
0668: return false;
0669: }
0670:
0671: public void clear() {
0672: TreeMap.this .clear();
0673: }
0674: };
0675: }
0676: return values;
0677: }
0678:
0679: /**
0680: * Returns a set view of the mappings contained in this map. The set's
0681: * iterator returns the mappings in ascending key order. Each element in
0682: * the returned set is a <tt>Map.Entry</tt>. The set is backed by this
0683: * map, so changes to this map are reflected in the set, and vice-versa.
0684: * The set supports element removal, which removes the corresponding
0685: * mapping from the TreeMap, through the <tt>Iterator.remove</tt>,
0686: * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
0687: * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
0688: * <tt>addAll</tt> operations.
0689: *
0690: * @return a set view of the mappings contained in this map.
0691: * @see Map.Entry
0692: */
0693: public Set entrySet() {
0694: if (entrySet == null) {
0695: entrySet = new AbstractSet() {
0696: public Iterator iterator() {
0697: return new EntryIterator();
0698: }
0699:
0700: public boolean contains(Object o) {
0701: if (!(o instanceof Map.Entry))
0702: return false;
0703: Map.Entry entry = (Map.Entry) o;
0704: Object value = entry.getValue();
0705: Entry p = getEntry(entry.getKey());
0706: return p != null && valEquals(p.getValue(), value);
0707: }
0708:
0709: public boolean remove(Object o) {
0710: if (!(o instanceof Map.Entry))
0711: return false;
0712: Map.Entry entry = (Map.Entry) o;
0713: Object value = entry.getValue();
0714: Entry p = getEntry(entry.getKey());
0715: if (p != null && valEquals(p.getValue(), value)) {
0716: deleteEntry(p);
0717: return true;
0718: }
0719: return false;
0720: }
0721:
0722: public int size() {
0723: return TreeMap.this .size();
0724: }
0725:
0726: public void clear() {
0727: TreeMap.this .clear();
0728: }
0729: };
0730: }
0731: return entrySet;
0732: }
0733:
0734: /**
0735: * Returns a view of the portion of this map whose keys range from
0736: * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive. (If
0737: * <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
0738: * is empty.) The returned sorted map is backed by this map, so changes
0739: * in the returned sorted map are reflected in this map, and vice-versa.
0740: * The returned sorted map supports all optional map operations.<p>
0741: *
0742: * The sorted map returned by this method will throw an
0743: * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
0744: * less than <tt>fromKey</tt> or greater than or equal to
0745: * <tt>toKey</tt>.<p>
0746: *
0747: * Note: this method always returns a <i>half-open range</i> (which
0748: * includes its low endpoint but not its high endpoint). If you need a
0749: * <i>closed range</i> (which includes both endpoints), and the key type
0750: * allows for calculation of the successor a given key, merely request the
0751: * subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
0752: * For example, suppose that <tt>m</tt> is a sorted map whose keys are
0753: * strings. The following idiom obtains a view containing all of the
0754: * key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
0755: * and <tt>high</tt>, inclusive:
0756: * <pre> SortedMap sub = m.submap(low, high+"\0");</pre>
0757: * A similar technique can be used to generate an <i>open range</i> (which
0758: * contains neither endpoint). The following idiom obtains a view
0759: * containing all of the key-value mappings in <tt>m</tt> whose keys are
0760: * between <tt>low</tt> and <tt>high</tt>, exclusive:
0761: * <pre> SortedMap sub = m.subMap(low+"\0", high);</pre>
0762: *
0763: * @param fromKey low endpoint (inclusive) of the subMap.
0764: * @param toKey high endpoint (exclusive) of the subMap.
0765: *
0766: * @return a view of the portion of this map whose keys range from
0767: * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
0768: *
0769: * @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
0770: * cannot be compared to one another using this map's comparator
0771: * (or, if the map has no comparator, using natural ordering).
0772: * @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
0773: * <tt>toKey</tt>.
0774: * @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
0775: * <tt>null</tt> and this map uses natural order, or its
0776: * comparator does not tolerate <tt>null</tt> keys.
0777: */
0778: public SortedMap subMap(Object fromKey, Object toKey) {
0779: return new SubMap(fromKey, toKey);
0780: }
0781:
0782: /**
0783: * Returns a view of the portion of this map whose keys are strictly less
0784: * than <tt>toKey</tt>. The returned sorted map is backed by this map, so
0785: * changes in the returned sorted map are reflected in this map, and
0786: * vice-versa. The returned sorted map supports all optional map
0787: * operations.<p>
0788: *
0789: * The sorted map returned by this method will throw an
0790: * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
0791: * greater than or equal to <tt>toKey</tt>.<p>
0792: *
0793: * Note: this method always returns a view that does not contain its
0794: * (high) endpoint. If you need a view that does contain this endpoint,
0795: * and the key type allows for calculation of the successor a given key,
0796: * merely request a headMap bounded by <tt>successor(highEndpoint)</tt>.
0797: * For example, suppose that suppose that <tt>m</tt> is a sorted map whose
0798: * keys are strings. The following idiom obtains a view containing all of
0799: * the key-value mappings in <tt>m</tt> whose keys are less than or equal
0800: * to <tt>high</tt>:
0801: * <pre>
0802: * SortedMap head = m.headMap(high+"\0");
0803: * </pre>
0804: *
0805: * @param toKey high endpoint (exclusive) of the headMap.
0806: * @return a view of the portion of this map whose keys are strictly
0807: * less than <tt>toKey</tt>.
0808: *
0809: * @throws ClassCastException if <tt>toKey</tt> is not compatible
0810: * with this map's comparator (or, if the map has no comparator,
0811: * if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
0812: * @throws IllegalArgumentException if this map is itself a subMap,
0813: * headMap, or tailMap, and <tt>toKey</tt> is not within the
0814: * specified range of the subMap, headMap, or tailMap.
0815: * @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
0816: * this map uses natural order, or its comparator does not
0817: * tolerate <tt>null</tt> keys.
0818: */
0819: public SortedMap headMap(Object toKey) {
0820: return new SubMap(toKey, true);
0821: }
0822:
0823: /**
0824: * Returns a view of the portion of this map whose keys are greater than
0825: * or equal to <tt>fromKey</tt>. The returned sorted map is backed by
0826: * this map, so changes in the returned sorted map are reflected in this
0827: * map, and vice-versa. The returned sorted map supports all optional map
0828: * operations.<p>
0829: *
0830: * The sorted map returned by this method will throw an
0831: * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
0832: * less than <tt>fromKey</tt>.<p>
0833: *
0834: * Note: this method always returns a view that contains its (low)
0835: * endpoint. If you need a view that does not contain this endpoint, and
0836: * the element type allows for calculation of the successor a given value,
0837: * merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
0838: * For For example, suppose that suppose that <tt>m</tt> is a sorted map
0839: * whose keys are strings. The following idiom obtains a view containing
0840: * all of the key-value mappings in <tt>m</tt> whose keys are strictly
0841: * greater than <tt>low</tt>: <pre>
0842: * SortedMap tail = m.tailMap(low+"\0");
0843: * </pre>
0844: *
0845: * @param fromKey low endpoint (inclusive) of the tailMap.
0846: * @return a view of the portion of this map whose keys are greater
0847: * than or equal to <tt>fromKey</tt>.
0848: * @throws ClassCastException if <tt>fromKey</tt> is not compatible
0849: * with this map's comparator (or, if the map has no comparator,
0850: * if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
0851: * @throws IllegalArgumentException if this map is itself a subMap,
0852: * headMap, or tailMap, and <tt>fromKey</tt> is not within the
0853: * specified range of the subMap, headMap, or tailMap.
0854: * @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and
0855: * this map uses natural order, or its comparator does not
0856: * tolerate <tt>null</tt> keys.
0857: */
0858: public SortedMap tailMap(Object fromKey) {
0859: return new SubMap(fromKey, false);
0860: }
0861:
0862: private class SubMap extends AbstractMap implements SortedMap,
0863: java.io.Serializable {
0864: private static final long serialVersionUID = -6520786458950516097L;
0865:
0866: /**
0867: * fromKey is significant only if fromStart is false. Similarly,
0868: * toKey is significant only if toStart is false.
0869: */
0870: private boolean fromStart = false, toEnd = false;
0871: private Object fromKey, toKey;
0872:
0873: SubMap(Object fromKey, Object toKey) {
0874: if (compare(fromKey, toKey) > 0)
0875: throw new IllegalArgumentException("fromKey > toKey");
0876: this .fromKey = fromKey;
0877: this .toKey = toKey;
0878: }
0879:
0880: SubMap(Object key, boolean headMap) {
0881: compare(key, key); // Type-check key
0882:
0883: if (headMap) {
0884: fromStart = true;
0885: toKey = key;
0886: } else {
0887: toEnd = true;
0888: fromKey = key;
0889: }
0890: }
0891:
0892: SubMap(boolean fromStart, Object fromKey, boolean toEnd,
0893: Object toKey) {
0894: this .fromStart = fromStart;
0895: this .fromKey = fromKey;
0896: this .toEnd = toEnd;
0897: this .toKey = toKey;
0898: }
0899:
0900: public boolean isEmpty() {
0901: return entrySet.isEmpty();
0902: }
0903:
0904: public boolean containsKey(Object key) {
0905: return inRange(key) && TreeMap.this .containsKey(key);
0906: }
0907:
0908: public Object get(Object key) {
0909: if (!inRange(key))
0910: return null;
0911: return TreeMap.this .get(key);
0912: }
0913:
0914: public Object put(Object key, Object value) {
0915: if (!inRange(key))
0916: throw new IllegalArgumentException("key out of range");
0917: return TreeMap.this .put(key, value);
0918: }
0919:
0920: public Comparator comparator() {
0921: return comparator;
0922: }
0923:
0924: public Object firstKey() {
0925: Object first = key(fromStart ? firstEntry()
0926: : getCeilEntry(fromKey));
0927: if (!toEnd && compare(first, toKey) >= 0)
0928: throw (new NoSuchElementException());
0929: return first;
0930: }
0931:
0932: public Object lastKey() {
0933: Object last = key(toEnd ? lastEntry()
0934: : getPrecedingEntry(toKey));
0935: if (!fromStart && compare(last, fromKey) < 0)
0936: throw (new NoSuchElementException());
0937: return last;
0938: }
0939:
0940: private transient Set entrySet = new EntrySetView();
0941:
0942: public Set entrySet() {
0943: return entrySet;
0944: }
0945:
0946: private class EntrySetView extends AbstractSet {
0947: private transient int size = -1, sizeModCount;
0948:
0949: public int size() {
0950: if (size == -1 || sizeModCount != TreeMap.this .modCount) {
0951: size = 0;
0952: sizeModCount = TreeMap.this .modCount;
0953: Iterator i = iterator();
0954: while (i.hasNext()) {
0955: size++;
0956: i.next();
0957: }
0958: }
0959: return size;
0960: }
0961:
0962: public boolean isEmpty() {
0963: return !iterator().hasNext();
0964: }
0965:
0966: public boolean contains(Object o) {
0967: if (!(o instanceof Map.Entry))
0968: return false;
0969: Map.Entry entry = (Map.Entry) o;
0970: Object key = entry.getKey();
0971: if (!inRange(key))
0972: return false;
0973: TreeMap.Entry node = getEntry(key);
0974: return node != null
0975: && valEquals(node.getValue(), entry.getValue());
0976: }
0977:
0978: public boolean remove(Object o) {
0979: if (!(o instanceof Map.Entry))
0980: return false;
0981: Map.Entry entry = (Map.Entry) o;
0982: Object key = entry.getKey();
0983: if (!inRange(key))
0984: return false;
0985: TreeMap.Entry node = getEntry(key);
0986: if (node != null
0987: && valEquals(node.getValue(), entry.getValue())) {
0988: deleteEntry(node);
0989: return true;
0990: }
0991: return false;
0992: }
0993:
0994: public Iterator iterator() {
0995: return new SubMapEntryIterator(
0996: (fromStart ? firstEntry()
0997: : getCeilEntry(fromKey)), (toEnd ? null
0998: : getCeilEntry(toKey)));
0999: }
1000: }
1001:
1002: public SortedMap subMap(Object fromKey, Object toKey) {
1003: if (!inRange2(fromKey))
1004: throw new IllegalArgumentException(
1005: "fromKey out of range");
1006: if (!inRange2(toKey))
1007: throw new IllegalArgumentException("toKey out of range");
1008: return new SubMap(fromKey, toKey);
1009: }
1010:
1011: public SortedMap headMap(Object toKey) {
1012: if (!inRange2(toKey))
1013: throw new IllegalArgumentException("toKey out of range");
1014: return new SubMap(fromStart, fromKey, false, toKey);
1015: }
1016:
1017: public SortedMap tailMap(Object fromKey) {
1018: if (!inRange2(fromKey))
1019: throw new IllegalArgumentException(
1020: "fromKey out of range");
1021: return new SubMap(false, fromKey, toEnd, toKey);
1022: }
1023:
1024: private boolean inRange(Object key) {
1025: return (fromStart || compare(key, fromKey) >= 0)
1026: && (toEnd || compare(key, toKey) < 0);
1027: }
1028:
1029: // This form allows the high endpoint (as well as all legit keys)
1030: private boolean inRange2(Object key) {
1031: return (fromStart || compare(key, fromKey) >= 0)
1032: && (toEnd || compare(key, toKey) <= 0);
1033: }
1034: }
1035:
1036: /**
1037: * TreeMap Iterator.
1038: */
1039: private class EntryIterator implements Iterator {
1040: private int expectedModCount = TreeMap.this .modCount;
1041: private Entry lastReturned = null;
1042: Entry next;
1043:
1044: EntryIterator() {
1045: next = firstEntry();
1046: }
1047:
1048: // Used by SubMapEntryIterator
1049: EntryIterator(Entry first) {
1050: next = first;
1051: }
1052:
1053: public boolean hasNext() {
1054: return next != null;
1055: }
1056:
1057: final Entry nextEntry() {
1058: if (next == null)
1059: throw new NoSuchElementException();
1060: if (modCount != expectedModCount)
1061: throw new ConcurrentModificationException();
1062: lastReturned = next;
1063: next = successor(next);
1064: return lastReturned;
1065: }
1066:
1067: public Object next() {
1068: return nextEntry();
1069: }
1070:
1071: public void remove() {
1072: if (lastReturned == null)
1073: throw new IllegalStateException();
1074: if (modCount != expectedModCount)
1075: throw new ConcurrentModificationException();
1076: if (lastReturned.left != null && lastReturned.right != null)
1077: next = lastReturned;
1078: deleteEntry(lastReturned);
1079: expectedModCount++;
1080: lastReturned = null;
1081: }
1082: }
1083:
1084: private class KeyIterator extends EntryIterator {
1085: public Object next() {
1086: return nextEntry().key;
1087: }
1088: }
1089:
1090: private class ValueIterator extends EntryIterator {
1091: public Object next() {
1092: return nextEntry().value;
1093: }
1094: }
1095:
1096: private class SubMapEntryIterator extends EntryIterator {
1097: private final Object firstExcludedKey;
1098:
1099: SubMapEntryIterator(Entry first, Entry firstExcluded) {
1100: super (first);
1101: firstExcludedKey = (firstExcluded == null ? firstExcluded
1102: : firstExcluded.key);
1103: }
1104:
1105: public boolean hasNext() {
1106: return next != null && next.key != firstExcludedKey;
1107: }
1108:
1109: public Object next() {
1110: if (next == null || next.key == firstExcludedKey)
1111: throw new NoSuchElementException();
1112: return nextEntry();
1113: }
1114: }
1115:
1116: /**
1117: * Compares two keys using the correct comparison method for this TreeMap.
1118: */
1119: private int compare(Object k1, Object k2) {
1120: return (comparator == null ? ((Comparable) k1).compareTo(k2)
1121: : comparator.compare(k1, k2));
1122: }
1123:
1124: /**
1125: * Test two values for equality. Differs from o1.equals(o2) only in
1126: * that it copes with with <tt>null</tt> o1 properly.
1127: */
1128: private static boolean valEquals(Object o1, Object o2) {
1129: return (o1 == null ? o2 == null : o1.equals(o2));
1130: }
1131:
1132: private static final boolean RED = false;
1133: private static final boolean BLACK = true;
1134:
1135: /**
1136: * Node in the Tree. Doubles as a means to pass key-value pairs back to
1137: * user (see Map.Entry).
1138: */
1139:
1140: static class Entry implements Map.Entry {
1141: Object key;
1142: Object value;
1143: Entry left = null;
1144: Entry right = null;
1145: Entry parent;
1146: boolean color = BLACK;
1147:
1148: /**
1149: * Make a new cell with given key, value, and parent, and with
1150: * <tt>null</tt> child links, and BLACK color.
1151: */
1152: Entry(Object key, Object value, Entry parent) {
1153: this .key = key;
1154: this .value = value;
1155: this .parent = parent;
1156: }
1157:
1158: /**
1159: * Returns the key.
1160: *
1161: * @return the key.
1162: */
1163: public Object getKey() {
1164: return key;
1165: }
1166:
1167: /**
1168: * Returns the value associated with the key.
1169: *
1170: * @return the value associated with the key.
1171: */
1172: public Object getValue() {
1173: return value;
1174: }
1175:
1176: /**
1177: * Replaces the value currently associated with the key with the given
1178: * value.
1179: *
1180: * @return the value associated with the key before this method was
1181: * called.
1182: */
1183: public Object setValue(Object value) {
1184: Object oldValue = this .value;
1185: this .value = value;
1186: return oldValue;
1187: }
1188:
1189: public boolean equals(Object o) {
1190: if (!(o instanceof Map.Entry))
1191: return false;
1192: Map.Entry e = (Map.Entry) o;
1193:
1194: return valEquals(key, e.getKey())
1195: && valEquals(value, e.getValue());
1196: }
1197:
1198: public int hashCode() {
1199: int keyHash = (key == null ? 0 : key.hashCode());
1200: int valueHash = (value == null ? 0 : value.hashCode());
1201: return keyHash ^ valueHash;
1202: }
1203:
1204: public String toString() {
1205: return key + "=" + value;
1206: }
1207: }
1208:
1209: /**
1210: * Returns the first Entry in the TreeMap (according to the TreeMap's
1211: * key-sort function). Returns null if the TreeMap is empty.
1212: */
1213: private Entry firstEntry() {
1214: Entry p = root;
1215: if (p != null)
1216: while (p.left != null)
1217: p = p.left;
1218: return p;
1219: }
1220:
1221: /**
1222: * Returns the last Entry in the TreeMap (according to the TreeMap's
1223: * key-sort function). Returns null if the TreeMap is empty.
1224: */
1225: private Entry lastEntry() {
1226: Entry p = root;
1227: if (p != null)
1228: while (p.right != null)
1229: p = p.right;
1230: return p;
1231: }
1232:
1233: /**
1234: * Returns the successor of the specified Entry, or null if no such.
1235: */
1236: private Entry successor(Entry t) {
1237: if (t == null)
1238: return null;
1239: else if (t.right != null) {
1240: Entry p = t.right;
1241: while (p.left != null)
1242: p = p.left;
1243: return p;
1244: } else {
1245: Entry p = t.parent;
1246: Entry ch = t;
1247: while (p != null && ch == p.right) {
1248: ch = p;
1249: p = p.parent;
1250: }
1251: return p;
1252: }
1253: }
1254:
1255: /**
1256: * Balancing operations.
1257: *
1258: * Implementations of rebalancings during insertion and deletion are
1259: * slightly different than the CLR version. Rather than using dummy
1260: * nilnodes, we use a set of accessors that deal properly with null. They
1261: * are used to avoid messiness surrounding nullness checks in the main
1262: * algorithms.
1263: */
1264:
1265: private static boolean colorOf(Entry p) {
1266: return (p == null ? BLACK : p.color);
1267: }
1268:
1269: private static Entry parentOf(Entry p) {
1270: return (p == null ? null : p.parent);
1271: }
1272:
1273: private static void setColor(Entry p, boolean c) {
1274: if (p != null)
1275: p.color = c;
1276: }
1277:
1278: private static Entry leftOf(Entry p) {
1279: return (p == null) ? null : p.left;
1280: }
1281:
1282: private static Entry rightOf(Entry p) {
1283: return (p == null) ? null : p.right;
1284: }
1285:
1286: /** From CLR **/
1287: private void rotateLeft(Entry p) {
1288: Entry r = p.right;
1289: p.right = r.left;
1290: if (r.left != null)
1291: r.left.parent = p;
1292: r.parent = p.parent;
1293: if (p.parent == null)
1294: root = r;
1295: else if (p.parent.left == p)
1296: p.parent.left = r;
1297: else
1298: p.parent.right = r;
1299: r.left = p;
1300: p.parent = r;
1301: }
1302:
1303: /** From CLR **/
1304: private void rotateRight(Entry p) {
1305: Entry l = p.left;
1306: p.left = l.right;
1307: if (l.right != null)
1308: l.right.parent = p;
1309: l.parent = p.parent;
1310: if (p.parent == null)
1311: root = l;
1312: else if (p.parent.right == p)
1313: p.parent.right = l;
1314: else
1315: p.parent.left = l;
1316: l.right = p;
1317: p.parent = l;
1318: }
1319:
1320: /** From CLR **/
1321: private void fixAfterInsertion(Entry x) {
1322: x.color = RED;
1323:
1324: while (x != null && x != root && x.parent.color == RED) {
1325: if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
1326: Entry y = rightOf(parentOf(parentOf(x)));
1327: if (colorOf(y) == RED) {
1328: setColor(parentOf(x), BLACK);
1329: setColor(y, BLACK);
1330: setColor(parentOf(parentOf(x)), RED);
1331: x = parentOf(parentOf(x));
1332: } else {
1333: if (x == rightOf(parentOf(x))) {
1334: x = parentOf(x);
1335: rotateLeft(x);
1336: }
1337: setColor(parentOf(x), BLACK);
1338: setColor(parentOf(parentOf(x)), RED);
1339: if (parentOf(parentOf(x)) != null)
1340: rotateRight(parentOf(parentOf(x)));
1341: }
1342: } else {
1343: Entry y = leftOf(parentOf(parentOf(x)));
1344: if (colorOf(y) == RED) {
1345: setColor(parentOf(x), BLACK);
1346: setColor(y, BLACK);
1347: setColor(parentOf(parentOf(x)), RED);
1348: x = parentOf(parentOf(x));
1349: } else {
1350: if (x == leftOf(parentOf(x))) {
1351: x = parentOf(x);
1352: rotateRight(x);
1353: }
1354: setColor(parentOf(x), BLACK);
1355: setColor(parentOf(parentOf(x)), RED);
1356: if (parentOf(parentOf(x)) != null)
1357: rotateLeft(parentOf(parentOf(x)));
1358: }
1359: }
1360: }
1361: root.color = BLACK;
1362: }
1363:
1364: /**
1365: * Delete node p, and then rebalance the tree.
1366: */
1367:
1368: private void deleteEntry(Entry p) {
1369: decrementSize();
1370:
1371: // If strictly internal, copy successor's element to p and then make p
1372: // point to successor.
1373: if (p.left != null && p.right != null) {
1374: Entry s = successor(p);
1375: p.key = s.key;
1376: p.value = s.value;
1377: p = s;
1378: } // p has 2 children
1379:
1380: // Start fixup at replacement node, if it exists.
1381: Entry replacement = (p.left != null ? p.left : p.right);
1382:
1383: if (replacement != null) {
1384: // Link replacement to parent
1385: replacement.parent = p.parent;
1386: if (p.parent == null)
1387: root = replacement;
1388: else if (p == p.parent.left)
1389: p.parent.left = replacement;
1390: else
1391: p.parent.right = replacement;
1392:
1393: // Null out links so they are OK to use by fixAfterDeletion.
1394: p.left = p.right = p.parent = null;
1395:
1396: // Fix replacement
1397: if (p.color == BLACK)
1398: fixAfterDeletion(replacement);
1399: } else if (p.parent == null) { // return if we are the only node.
1400: root = null;
1401: } else { // No children. Use self as phantom replacement and unlink.
1402: if (p.color == BLACK)
1403: fixAfterDeletion(p);
1404:
1405: if (p.parent != null) {
1406: if (p == p.parent.left)
1407: p.parent.left = null;
1408: else if (p == p.parent.right)
1409: p.parent.right = null;
1410: p.parent = null;
1411: }
1412: }
1413: }
1414:
1415: /** From CLR **/
1416: private void fixAfterDeletion(Entry x) {
1417: while (x != root && colorOf(x) == BLACK) {
1418: if (x == leftOf(parentOf(x))) {
1419: Entry sib = rightOf(parentOf(x));
1420:
1421: if (colorOf(sib) == RED) {
1422: setColor(sib, BLACK);
1423: setColor(parentOf(x), RED);
1424: rotateLeft(parentOf(x));
1425: sib = rightOf(parentOf(x));
1426: }
1427:
1428: if (colorOf(leftOf(sib)) == BLACK
1429: && colorOf(rightOf(sib)) == BLACK) {
1430: setColor(sib, RED);
1431: x = parentOf(x);
1432: } else {
1433: if (colorOf(rightOf(sib)) == BLACK) {
1434: setColor(leftOf(sib), BLACK);
1435: setColor(sib, RED);
1436: rotateRight(sib);
1437: sib = rightOf(parentOf(x));
1438: }
1439: setColor(sib, colorOf(parentOf(x)));
1440: setColor(parentOf(x), BLACK);
1441: setColor(rightOf(sib), BLACK);
1442: rotateLeft(parentOf(x));
1443: x = root;
1444: }
1445: } else { // symmetric
1446: Entry sib = leftOf(parentOf(x));
1447:
1448: if (colorOf(sib) == RED) {
1449: setColor(sib, BLACK);
1450: setColor(parentOf(x), RED);
1451: rotateRight(parentOf(x));
1452: sib = leftOf(parentOf(x));
1453: }
1454:
1455: if (colorOf(rightOf(sib)) == BLACK
1456: && colorOf(leftOf(sib)) == BLACK) {
1457: setColor(sib, RED);
1458: x = parentOf(x);
1459: } else {
1460: if (colorOf(leftOf(sib)) == BLACK) {
1461: setColor(rightOf(sib), BLACK);
1462: setColor(sib, RED);
1463: rotateLeft(sib);
1464: sib = leftOf(parentOf(x));
1465: }
1466: setColor(sib, colorOf(parentOf(x)));
1467: setColor(parentOf(x), BLACK);
1468: setColor(leftOf(sib), BLACK);
1469: rotateRight(parentOf(x));
1470: x = root;
1471: }
1472: }
1473: }
1474:
1475: setColor(x, BLACK);
1476: }
1477:
1478: private static final long serialVersionUID = 919286545866124006L;
1479:
1480: /**
1481: * Save the state of the <tt>TreeMap</tt> instance to a stream (i.e.,
1482: * serialize it).
1483: *
1484: * @serialData The <i>size</i> of the TreeMap (the number of key-value
1485: * mappings) is emitted (int), followed by the key (Object)
1486: * and value (Object) for each key-value mapping represented
1487: * by the TreeMap. The key-value mappings are emitted in
1488: * key-order (as determined by the TreeMap's Comparator,
1489: * or by the keys' natural ordering if the TreeMap has no
1490: * Comparator).
1491: */
1492: private void writeObject(java.io.ObjectOutputStream s)
1493: throws java.io.IOException {
1494: // Write out the Comparator and any hidden stuff
1495: s.defaultWriteObject();
1496:
1497: // Write out size (number of Mappings)
1498: s.writeInt(size);
1499:
1500: // Write out keys and values (alternating)
1501: for (Iterator i = entrySet().iterator(); i.hasNext();) {
1502: Entry e = (Entry) i.next();
1503: s.writeObject(e.key);
1504: s.writeObject(e.value);
1505: }
1506: }
1507:
1508: /**
1509: * Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
1510: * deserialize it).
1511: */
1512: private void readObject(final java.io.ObjectInputStream s)
1513: throws java.io.IOException, ClassNotFoundException {
1514: // Read in the Comparator and any hidden stuff
1515: s.defaultReadObject();
1516:
1517: // Read in size
1518: int size = s.readInt();
1519:
1520: buildFromSorted(size, null, s, null);
1521: }
1522:
1523: /** Intended to be called only from TreeSet.readObject **/
1524: void readTreeSet(int size, java.io.ObjectInputStream s,
1525: Object defaultVal) throws java.io.IOException,
1526: ClassNotFoundException {
1527: buildFromSorted(size, null, s, defaultVal);
1528: }
1529:
1530: /** Intended to be called only from TreeSet.addAll **/
1531: void addAllForTreeSet(SortedSet set, Object defaultVal) {
1532: try {
1533: buildFromSorted(set.size(), set.iterator(), null,
1534: defaultVal);
1535: } catch (java.io.IOException cannotHappen) {
1536: } catch (ClassNotFoundException cannotHappen) {
1537: }
1538: }
1539:
1540: /**
1541: * Linear time tree building algorithm from sorted data. Can accept keys
1542: * and/or values from iterator or stream. This leads to too many
1543: * parameters, but seems better than alternatives. The four formats
1544: * that this method accepts are:
1545: *
1546: * 1) An iterator of Map.Entries. (it != null, defaultVal == null).
1547: * 2) An iterator of keys. (it != null, defaultVal != null).
1548: * 3) A stream of alternating serialized keys and values.
1549: * (it == null, defaultVal == null).
1550: * 4) A stream of serialized keys. (it == null, defaultVal != null).
1551: *
1552: * It is assumed that the comparator of the TreeMap is already set prior
1553: * to calling this method.
1554: *
1555: * @param size the number of keys (or key-value pairs) to be read from
1556: * the iterator or stream.
1557: * @param it If non-null, new entries are created from entries
1558: * or keys read from this iterator.
1559: * @param it If non-null, new entries are created from keys and
1560: * possibly values read from this stream in serialized form.
1561: * Exactly one of it and str should be non-null.
1562: * @param defaultVal if non-null, this default value is used for
1563: * each value in the map. If null, each value is read from
1564: * iterator or stream, as described above.
1565: * @throws IOException propagated from stream reads. This cannot
1566: * occur if str is null.
1567: * @throws ClassNotFoundException propagated from readObject.
1568: * This cannot occur if str is null.
1569: */
1570: private void buildFromSorted(int size, Iterator it,
1571: java.io.ObjectInputStream str, Object defaultVal)
1572: throws java.io.IOException, ClassNotFoundException {
1573: this .size = size;
1574: root = buildFromSorted(0, 0, size - 1, computeRedLevel(size),
1575: it, str, defaultVal);
1576: }
1577:
1578: /**
1579: * Recursive "helper method" that does the real work of the
1580: * of the previous method. Identically named parameters have
1581: * identical definitions. Additional parameters are documented below.
1582: * It is assumed that the comparator and size fields of the TreeMap are
1583: * already set prior to calling this method. (It ignores both fields.)
1584: *
1585: * @param level the current level of tree. Initial call should be 0.
1586: * @param lo the first element index of this subtree. Initial should be 0.
1587: * @param hi the last element index of this subtree. Initial should be
1588: * size-1.
1589: * @param redLevel the level at which nodes should be red.
1590: * Must be equal to computeRedLevel for tree of this size.
1591: */
1592: private static Entry buildFromSorted(int level, int lo, int hi,
1593: int redLevel, Iterator it, java.io.ObjectInputStream str,
1594: Object defaultVal) throws java.io.IOException,
1595: ClassNotFoundException {
1596: /*
1597: * Strategy: The root is the middlemost element. To get to it, we
1598: * have to first recursively construct the entire left subtree,
1599: * so as to grab all of its elements. We can then proceed with right
1600: * subtree.
1601: *
1602: * The lo and hi arguments are the minimum and maximum
1603: * indices to pull out of the iterator or stream for current subtree.
1604: * They are not actually indexed, we just proceed sequentially,
1605: * ensuring that items are extracted in corresponding order.
1606: */
1607:
1608: if (hi < lo)
1609: return null;
1610:
1611: int mid = (lo + hi) / 2;
1612:
1613: Entry left = null;
1614: if (lo < mid)
1615: left = buildFromSorted(level + 1, lo, mid - 1, redLevel,
1616: it, str, defaultVal);
1617:
1618: // extract key and/or value from iterator or stream
1619: Object key;
1620: Object value;
1621: if (it != null) { // use iterator
1622: if (defaultVal == null) {
1623: Map.Entry entry = (Map.Entry) it.next();
1624: key = entry.getKey();
1625: value = entry.getValue();
1626: } else {
1627: key = it.next();
1628: value = defaultVal;
1629: }
1630: } else { // use stream
1631: key = str.readObject();
1632: value = (defaultVal != null ? defaultVal : str.readObject());
1633: }
1634:
1635: Entry middle = new Entry(key, value, null);
1636:
1637: // color nodes in non-full bottommost level red
1638: if (level == redLevel)
1639: middle.color = RED;
1640:
1641: if (left != null) {
1642: middle.left = left;
1643: left.parent = middle;
1644: }
1645:
1646: if (mid < hi) {
1647: Entry right = buildFromSorted(level + 1, mid + 1, hi,
1648: redLevel, it, str, defaultVal);
1649: middle.right = right;
1650: right.parent = middle;
1651: }
1652:
1653: return middle;
1654: }
1655:
1656: /**
1657: * Find the level down to which to assign all nodes BLACK. This is the
1658: * last `full' level of the complete binary tree produced by
1659: * buildTree. The remaining nodes are colored RED. (This makes a `nice'
1660: * set of color assignments wrt future insertions.) This level number is
1661: * computed by finding the number of splits needed to reach the zeroeth
1662: * node. (The answer is ~lg(N), but in any case must be computed by same
1663: * quick O(lg(N)) loop.)
1664: */
1665: private static int computeRedLevel(int sz) {
1666: int level = 0;
1667: for (int m = sz - 1; m >= 0; m = m / 2 - 1)
1668: level++;
1669: return level;
1670: }
1671: }
|