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