0001: /*
0002: * Copyright 2001-2005 The Apache Software Foundation
0003: *
0004: * Licensed under the Apache License, Version 2.0 (the "License");
0005: * you may not use this file except in compliance with the License.
0006: * You may obtain a copy of the License at
0007: *
0008: * http://www.apache.org/licenses/LICENSE-2.0
0009: *
0010: * Unless required by applicable law or agreed to in writing, software
0011: * distributed under the License is distributed on an "AS IS" BASIS,
0012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013: * See the License for the specific language governing permissions and
0014: * limitations under the License.
0015: */
0016: package org.apache.commons.collections.bidimap;
0017:
0018: import java.util.AbstractSet;
0019: import java.util.Collection;
0020: import java.util.ConcurrentModificationException;
0021: import java.util.Iterator;
0022: import java.util.Map;
0023: import java.util.NoSuchElementException;
0024: import java.util.Set;
0025:
0026: import org.apache.commons.collections.BidiMap;
0027: import org.apache.commons.collections.KeyValue;
0028: import org.apache.commons.collections.MapIterator;
0029: import org.apache.commons.collections.OrderedBidiMap;
0030: import org.apache.commons.collections.OrderedIterator;
0031: import org.apache.commons.collections.OrderedMapIterator;
0032: import org.apache.commons.collections.iterators.EmptyOrderedMapIterator;
0033: import org.apache.commons.collections.keyvalue.UnmodifiableMapEntry;
0034:
0035: /**
0036: * Red-Black tree-based implementation of BidiMap where all objects added
0037: * implement the <code>Comparable</code> interface.
0038: * <p>
0039: * This class guarantees that the map will be in both ascending key order
0040: * and ascending value order, sorted according to the natural order for
0041: * the key's and value's classes.
0042: * <p>
0043: * This Map is intended for applications that need to be able to look
0044: * up a key-value pairing by either key or value, and need to do so
0045: * with equal efficiency.
0046: * <p>
0047: * While that goal could be accomplished by taking a pair of TreeMaps
0048: * and redirecting requests to the appropriate TreeMap (e.g.,
0049: * containsKey would be directed to the TreeMap that maps values to
0050: * keys, containsValue would be directed to the TreeMap that maps keys
0051: * to values), there are problems with that implementation.
0052: * If the data contained in the TreeMaps is large, the cost of redundant
0053: * storage becomes significant. The {@link DualTreeBidiMap} and
0054: * {@link DualHashBidiMap} implementations use this approach.
0055: * <p>
0056: * This solution keeps minimizes the data storage by holding data only once.
0057: * The red-black algorithm is based on java util TreeMap, but has been modified
0058: * to simultaneously map a tree node by key and by value. This doubles the
0059: * cost of put operations (but so does using two TreeMaps), and nearly doubles
0060: * the cost of remove operations (there is a savings in that the lookup of the
0061: * node to be removed only has to be performed once). And since only one node
0062: * contains the key and value, storage is significantly less than that
0063: * required by two TreeMaps.
0064: * <p>
0065: * The Map.Entry instances returned by the appropriate methods will
0066: * not allow setValue() and will throw an
0067: * UnsupportedOperationException on attempts to call that method.
0068: *
0069: * @since Commons Collections 3.0 (previously DoubleOrderedMap v2.0)
0070: * @version $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
0071: *
0072: * @author Marc Johnson
0073: * @author Stephen Colebourne
0074: */
0075: public class TreeBidiMap implements OrderedBidiMap {
0076:
0077: private static final int KEY = 0;
0078: private static final int VALUE = 1;
0079: private static final int MAPENTRY = 2;
0080: private static final int INVERSEMAPENTRY = 3;
0081: private static final int SUM_OF_INDICES = KEY + VALUE;
0082: private static final int FIRST_INDEX = 0;
0083: private static final int NUMBER_OF_INDICES = 2;
0084: private static final String[] dataName = new String[] { "key",
0085: "value" };
0086:
0087: private Node[] rootNode = new Node[2];
0088: private int nodeCount = 0;
0089: private int modifications = 0;
0090: private Set keySet;
0091: private Set valuesSet;
0092: private Set entrySet;
0093: private TreeBidiMap.Inverse inverse = null;
0094:
0095: //-----------------------------------------------------------------------
0096: /**
0097: * Constructs a new empty TreeBidiMap.
0098: */
0099: public TreeBidiMap() {
0100: super ();
0101: }
0102:
0103: /**
0104: * Constructs a new TreeBidiMap by copying an existing Map.
0105: *
0106: * @param map the map to copy
0107: * @throws ClassCastException if the keys/values in the map are
0108: * not Comparable or are not mutually comparable
0109: * @throws NullPointerException if any key or value in the map is null
0110: */
0111: public TreeBidiMap(final Map map) {
0112: super ();
0113: putAll(map);
0114: }
0115:
0116: //-----------------------------------------------------------------------
0117: /**
0118: * Returns the number of key-value mappings in this map.
0119: *
0120: * @return the number of key-value mappings in this map
0121: */
0122: public int size() {
0123: return nodeCount;
0124: }
0125:
0126: /**
0127: * Checks whether the map is empty or not.
0128: *
0129: * @return true if the map is empty
0130: */
0131: public boolean isEmpty() {
0132: return (nodeCount == 0);
0133: }
0134:
0135: /**
0136: * Checks whether this map contains the a mapping for the specified key.
0137: * <p>
0138: * The key must implement <code>Comparable</code>.
0139: *
0140: * @param key key whose presence in this map is to be tested
0141: * @return true if this map contains a mapping for the specified key
0142: * @throws ClassCastException if the key is of an inappropriate type
0143: * @throws NullPointerException if the key is null
0144: */
0145: public boolean containsKey(final Object key) {
0146: checkKey(key);
0147: return (lookup((Comparable) key, KEY) != null);
0148: }
0149:
0150: /**
0151: * Checks whether this map contains the a mapping for the specified value.
0152: * <p>
0153: * The value must implement <code>Comparable</code>.
0154: *
0155: * @param value value whose presence in this map is to be tested
0156: * @return true if this map contains a mapping for the specified value
0157: * @throws ClassCastException if the value is of an inappropriate type
0158: * @throws NullPointerException if the value is null
0159: */
0160: public boolean containsValue(final Object value) {
0161: checkValue(value);
0162: return (lookup((Comparable) value, VALUE) != null);
0163: }
0164:
0165: /**
0166: * Gets the value to which this map maps the specified key.
0167: * Returns null if the map contains no mapping for this key.
0168: * <p>
0169: * The key must implement <code>Comparable</code>.
0170: *
0171: * @param key key whose associated value is to be returned
0172: * @return the value to which this map maps the specified key,
0173: * or null if the map contains no mapping for this key
0174: * @throws ClassCastException if the key is of an inappropriate type
0175: * @throws NullPointerException if the key is null
0176: */
0177: public Object get(final Object key) {
0178: return doGet((Comparable) key, KEY);
0179: }
0180:
0181: /**
0182: * Puts the key-value pair into the map, replacing any previous pair.
0183: * <p>
0184: * When adding a key-value pair, the value may already exist in the map
0185: * against a different key. That mapping is removed, to ensure that the
0186: * value only occurs once in the inverse map.
0187: * <pre>
0188: * BidiMap map1 = new TreeBidiMap();
0189: * map.put("A","B"); // contains A mapped to B, as per Map
0190: * map.put("A","C"); // contains A mapped to C, as per Map
0191: *
0192: * BidiMap map2 = new TreeBidiMap();
0193: * map.put("A","B"); // contains A mapped to B, as per Map
0194: * map.put("C","B"); // contains C mapped to B, key A is removed
0195: * </pre>
0196: * <p>
0197: * Both key and value must implement <code>Comparable</code>.
0198: *
0199: * @param key key with which the specified value is to be associated
0200: * @param value value to be associated with the specified key
0201: * @return the previous value for the key
0202: * @throws ClassCastException if the key is of an inappropriate type
0203: * @throws NullPointerException if the key is null
0204: */
0205: public Object put(final Object key, final Object value) {
0206: return doPut((Comparable) key, (Comparable) value, KEY);
0207: }
0208:
0209: /**
0210: * Puts all the mappings from the specified map into this map.
0211: * <p>
0212: * All keys and values must implement <code>Comparable</code>.
0213: *
0214: * @param map the map to copy from
0215: */
0216: public void putAll(Map map) {
0217: Iterator it = map.entrySet().iterator();
0218: while (it.hasNext()) {
0219: Map.Entry entry = (Map.Entry) it.next();
0220: put(entry.getKey(), entry.getValue());
0221: }
0222: }
0223:
0224: /**
0225: * Removes the mapping for this key from this map if present.
0226: * <p>
0227: * The key must implement <code>Comparable</code>.
0228: *
0229: * @param key key whose mapping is to be removed from the map.
0230: * @return previous value associated with specified key,
0231: * or null if there was no mapping for key.
0232: * @throws ClassCastException if the key is of an inappropriate type
0233: * @throws NullPointerException if the key is null
0234: */
0235: public Object remove(final Object key) {
0236: return doRemove((Comparable) key, KEY);
0237: }
0238:
0239: /**
0240: * Removes all mappings from this map.
0241: */
0242: public void clear() {
0243: modify();
0244:
0245: nodeCount = 0;
0246: rootNode[KEY] = null;
0247: rootNode[VALUE] = null;
0248: }
0249:
0250: //-----------------------------------------------------------------------
0251: /**
0252: * Returns the key to which this map maps the specified value.
0253: * Returns null if the map contains no mapping for this value.
0254: * <p>
0255: * The value must implement <code>Comparable</code>.
0256: *
0257: * @param value value whose associated key is to be returned.
0258: * @return the key to which this map maps the specified value,
0259: * or null if the map contains no mapping for this value.
0260: * @throws ClassCastException if the value is of an inappropriate type
0261: * @throws NullPointerException if the value is null
0262: */
0263: public Object getKey(final Object value) {
0264: return doGet((Comparable) value, VALUE);
0265: }
0266:
0267: /**
0268: * Removes the mapping for this value from this map if present.
0269: * <p>
0270: * The value must implement <code>Comparable</code>.
0271: *
0272: * @param value value whose mapping is to be removed from the map
0273: * @return previous key associated with specified value,
0274: * or null if there was no mapping for value.
0275: * @throws ClassCastException if the value is of an inappropriate type
0276: * @throws NullPointerException if the value is null
0277: */
0278: public Object removeValue(final Object value) {
0279: return doRemove((Comparable) value, VALUE);
0280: }
0281:
0282: //-----------------------------------------------------------------------
0283: /**
0284: * Gets the first (lowest) key currently in this map.
0285: *
0286: * @return the first (lowest) key currently in this sorted map
0287: * @throws NoSuchElementException if this map is empty
0288: */
0289: public Object firstKey() {
0290: if (nodeCount == 0) {
0291: throw new NoSuchElementException("Map is empty");
0292: }
0293: return leastNode(rootNode[KEY], KEY).getKey();
0294: }
0295:
0296: /**
0297: * Gets the last (highest) key currently in this map.
0298: *
0299: * @return the last (highest) key currently in this sorted map
0300: * @throws NoSuchElementException if this map is empty
0301: */
0302: public Object lastKey() {
0303: if (nodeCount == 0) {
0304: throw new NoSuchElementException("Map is empty");
0305: }
0306: return greatestNode(rootNode[KEY], KEY).getKey();
0307: }
0308:
0309: /**
0310: * Gets the next key after the one specified.
0311: * <p>
0312: * The key must implement <code>Comparable</code>.
0313: *
0314: * @param key the key to search for next from
0315: * @return the next key, null if no match or at end
0316: */
0317: public Object nextKey(Object key) {
0318: checkKey(key);
0319: Node node = nextGreater(lookup((Comparable) key, KEY), KEY);
0320: return (node == null ? null : node.getKey());
0321: }
0322:
0323: /**
0324: * Gets the previous key before the one specified.
0325: * <p>
0326: * The key must implement <code>Comparable</code>.
0327: *
0328: * @param key the key to search for previous from
0329: * @return the previous key, null if no match or at start
0330: */
0331: public Object previousKey(Object key) {
0332: checkKey(key);
0333: Node node = nextSmaller(lookup((Comparable) key, KEY), KEY);
0334: return (node == null ? null : node.getKey());
0335: }
0336:
0337: //-----------------------------------------------------------------------
0338: /**
0339: * Returns a set view of the keys contained in this map in key order.
0340: * <p>
0341: * The set is backed by the map, so changes to the map are reflected in
0342: * the set, and vice-versa. If the map is modified while an iteration over
0343: * the set is in progress, the results of the iteration are undefined.
0344: * <p>
0345: * The set supports element removal, which removes the corresponding mapping
0346: * from the map. It does not support the add or addAll operations.
0347: *
0348: * @return a set view of the keys contained in this map.
0349: */
0350: public Set keySet() {
0351: if (keySet == null) {
0352: keySet = new View(this , KEY, KEY);
0353: }
0354: return keySet;
0355: }
0356:
0357: //-----------------------------------------------------------------------
0358: /**
0359: * Returns a set view of the values contained in this map in key order.
0360: * The returned object can be cast to a Set.
0361: * <p>
0362: * The set is backed by the map, so changes to the map are reflected in
0363: * the set, and vice-versa. If the map is modified while an iteration over
0364: * the set is in progress, the results of the iteration are undefined.
0365: * <p>
0366: * The set supports element removal, which removes the corresponding mapping
0367: * from the map. It does not support the add or addAll operations.
0368: *
0369: * @return a set view of the values contained in this map.
0370: */
0371: public Collection values() {
0372: if (valuesSet == null) {
0373: valuesSet = new View(this , KEY, VALUE);
0374: }
0375: return valuesSet;
0376: }
0377:
0378: //-----------------------------------------------------------------------
0379: /**
0380: * Returns a set view of the entries contained in this map in key order.
0381: * For simple iteration through the map, the MapIterator is quicker.
0382: * <p>
0383: * The set is backed by the map, so changes to the map are reflected in
0384: * the set, and vice-versa. If the map is modified while an iteration over
0385: * the set is in progress, the results of the iteration are undefined.
0386: * <p>
0387: * The set supports element removal, which removes the corresponding mapping
0388: * from the map. It does not support the add or addAll operations.
0389: * The returned MapEntry objects do not support setValue.
0390: *
0391: * @return a set view of the values contained in this map.
0392: */
0393: public Set entrySet() {
0394: if (entrySet == null) {
0395: return new EntryView(this , KEY, MAPENTRY);
0396: }
0397: return entrySet;
0398: }
0399:
0400: //-----------------------------------------------------------------------
0401: /**
0402: * Gets an iterator over the map entries.
0403: * <p>
0404: * For this map, this iterator is the fastest way to iterate over the entries.
0405: *
0406: * @return an iterator
0407: */
0408: public MapIterator mapIterator() {
0409: if (isEmpty()) {
0410: return EmptyOrderedMapIterator.INSTANCE;
0411: }
0412: return new ViewMapIterator(this , KEY);
0413: }
0414:
0415: /**
0416: * Gets an ordered iterator over the map entries.
0417: * <p>
0418: * This iterator allows both forward and reverse iteration over the entries.
0419: *
0420: * @return an iterator
0421: */
0422: public OrderedMapIterator orderedMapIterator() {
0423: if (isEmpty()) {
0424: return EmptyOrderedMapIterator.INSTANCE;
0425: }
0426: return new ViewMapIterator(this , KEY);
0427: }
0428:
0429: //-----------------------------------------------------------------------
0430: /**
0431: * Gets the inverse map for comparison.
0432: *
0433: * @return the inverse map
0434: */
0435: public BidiMap inverseBidiMap() {
0436: return inverseOrderedBidiMap();
0437: }
0438:
0439: /**
0440: * Gets the inverse map for comparison.
0441: *
0442: * @return the inverse map
0443: */
0444: public OrderedBidiMap inverseOrderedBidiMap() {
0445: if (inverse == null) {
0446: inverse = new Inverse(this );
0447: }
0448: return inverse;
0449: }
0450:
0451: //-----------------------------------------------------------------------
0452: /**
0453: * Compares for equals as per the API.
0454: *
0455: * @param obj the object to compare to
0456: * @return true if equal
0457: */
0458: public boolean equals(Object obj) {
0459: return this .doEquals(obj, KEY);
0460: }
0461:
0462: /**
0463: * Gets the hash code value for this map as per the API.
0464: *
0465: * @return the hash code value for this map
0466: */
0467: public int hashCode() {
0468: return this .doHashCode(KEY);
0469: }
0470:
0471: /**
0472: * Returns a string version of this Map in standard format.
0473: *
0474: * @return a standard format string version of the map
0475: */
0476: public String toString() {
0477: return this .doToString(KEY);
0478: }
0479:
0480: //-----------------------------------------------------------------------
0481: /**
0482: * Common get logic, used to get by key or get by value
0483: *
0484: * @param obj the key or value that we're looking for
0485: * @param index the KEY or VALUE int
0486: * @return the key (if the value was mapped) or the value (if the
0487: * key was mapped); null if we couldn't find the specified
0488: * object
0489: */
0490: private Object doGet(final Comparable obj, final int index) {
0491: checkNonNullComparable(obj, index);
0492: Node node = lookup(obj, index);
0493: return ((node == null) ? null : node
0494: .getData(oppositeIndex(index)));
0495: }
0496:
0497: /**
0498: * Common put logic, differing only in the return value.
0499: *
0500: * @param key the key, always the main map key
0501: * @param value the value, always the main map value
0502: * @param index the KEY or VALUE int, for the return value only
0503: * @return the previously mapped value
0504: */
0505: private Object doPut(final Comparable key, final Comparable value,
0506: final int index) {
0507: checkKeyAndValue(key, value);
0508:
0509: // store previous and remove previous mappings
0510: Object prev = (index == KEY ? doGet(key, KEY) : doGet(value,
0511: VALUE));
0512: doRemove(key, KEY);
0513: doRemove(value, VALUE);
0514:
0515: Node node = rootNode[KEY];
0516: if (node == null) {
0517: // map is empty
0518: Node root = new Node(key, value);
0519: rootNode[KEY] = root;
0520: rootNode[VALUE] = root;
0521: grow();
0522:
0523: } else {
0524: // add new mapping
0525: while (true) {
0526: int cmp = compare(key, node.getData(KEY));
0527:
0528: if (cmp == 0) {
0529: // shouldn't happen
0530: throw new IllegalArgumentException(
0531: "Cannot store a duplicate key (\"" + key
0532: + "\") in this Map");
0533: } else if (cmp < 0) {
0534: if (node.getLeft(KEY) != null) {
0535: node = node.getLeft(KEY);
0536: } else {
0537: Node newNode = new Node(key, value);
0538:
0539: insertValue(newNode);
0540: node.setLeft(newNode, KEY);
0541: newNode.setParent(node, KEY);
0542: doRedBlackInsert(newNode, KEY);
0543: grow();
0544:
0545: break;
0546: }
0547: } else { // cmp > 0
0548: if (node.getRight(KEY) != null) {
0549: node = node.getRight(KEY);
0550: } else {
0551: Node newNode = new Node(key, value);
0552:
0553: insertValue(newNode);
0554: node.setRight(newNode, KEY);
0555: newNode.setParent(node, KEY);
0556: doRedBlackInsert(newNode, KEY);
0557: grow();
0558:
0559: break;
0560: }
0561: }
0562: }
0563: }
0564: return prev;
0565: }
0566:
0567: /**
0568: * Remove by object (remove by key or remove by value)
0569: *
0570: * @param o the key, or value, that we're looking for
0571: * @param index the KEY or VALUE int
0572: *
0573: * @return the key, if remove by value, or the value, if remove by
0574: * key. null if the specified key or value could not be
0575: * found
0576: */
0577: private Object doRemove(final Comparable o, final int index) {
0578: Node node = lookup(o, index);
0579: Object rval = null;
0580: if (node != null) {
0581: rval = node.getData(oppositeIndex(index));
0582: doRedBlackDelete(node);
0583: }
0584: return rval;
0585: }
0586:
0587: /**
0588: * do the actual lookup of a piece of data
0589: *
0590: * @param data the key or value to be looked up
0591: * @param index the KEY or VALUE int
0592: * @return the desired Node, or null if there is no mapping of the
0593: * specified data
0594: */
0595: private Node lookup(final Comparable data, final int index) {
0596: Node rval = null;
0597: Node node = rootNode[index];
0598:
0599: while (node != null) {
0600: int cmp = compare(data, node.getData(index));
0601: if (cmp == 0) {
0602: rval = node;
0603: break;
0604: } else {
0605: node = (cmp < 0) ? node.getLeft(index) : node
0606: .getRight(index);
0607: }
0608: }
0609:
0610: return rval;
0611: }
0612:
0613: /**
0614: * get the next larger node from the specified node
0615: *
0616: * @param node the node to be searched from
0617: * @param index the KEY or VALUE int
0618: * @return the specified node
0619: */
0620: private Node nextGreater(final Node node, final int index) {
0621: Node rval = null;
0622: if (node == null) {
0623: rval = null;
0624: } else if (node.getRight(index) != null) {
0625: // everything to the node's right is larger. The least of
0626: // the right node's descendants is the next larger node
0627: rval = leastNode(node.getRight(index), index);
0628: } else {
0629: // traverse up our ancestry until we find an ancestor that
0630: // is null or one whose left child is our ancestor. If we
0631: // find a null, then this node IS the largest node in the
0632: // tree, and there is no greater node. Otherwise, we are
0633: // the largest node in the subtree on that ancestor's left
0634: // ... and that ancestor is the next greatest node
0635: Node parent = node.getParent(index);
0636: Node child = node;
0637:
0638: while ((parent != null)
0639: && (child == parent.getRight(index))) {
0640: child = parent;
0641: parent = parent.getParent(index);
0642: }
0643: rval = parent;
0644: }
0645: return rval;
0646: }
0647:
0648: /**
0649: * get the next larger node from the specified node
0650: *
0651: * @param node the node to be searched from
0652: * @param index the KEY or VALUE int
0653: * @return the specified node
0654: */
0655: private Node nextSmaller(final Node node, final int index) {
0656: Node rval = null;
0657: if (node == null) {
0658: rval = null;
0659: } else if (node.getLeft(index) != null) {
0660: // everything to the node's left is smaller. The greatest of
0661: // the left node's descendants is the next smaller node
0662: rval = greatestNode(node.getLeft(index), index);
0663: } else {
0664: // traverse up our ancestry until we find an ancestor that
0665: // is null or one whose right child is our ancestor. If we
0666: // find a null, then this node IS the largest node in the
0667: // tree, and there is no greater node. Otherwise, we are
0668: // the largest node in the subtree on that ancestor's right
0669: // ... and that ancestor is the next greatest node
0670: Node parent = node.getParent(index);
0671: Node child = node;
0672:
0673: while ((parent != null) && (child == parent.getLeft(index))) {
0674: child = parent;
0675: parent = parent.getParent(index);
0676: }
0677: rval = parent;
0678: }
0679: return rval;
0680: }
0681:
0682: //-----------------------------------------------------------------------
0683: /**
0684: * Get the opposite index of the specified index
0685: *
0686: * @param index the KEY or VALUE int
0687: * @return VALUE (if KEY was specified), else KEY
0688: */
0689: private static int oppositeIndex(final int index) {
0690: // old trick ... to find the opposite of a value, m or n,
0691: // subtract the value from the sum of the two possible
0692: // values. (m + n) - m = n; (m + n) - n = m
0693: return SUM_OF_INDICES - index;
0694: }
0695:
0696: /**
0697: * Compare two objects
0698: *
0699: * @param o1 the first object
0700: * @param o2 the second object
0701: *
0702: * @return negative value if o1 < o2; 0 if o1 == o2; positive
0703: * value if o1 > o2
0704: */
0705: private static int compare(final Comparable o1, final Comparable o2) {
0706: return o1.compareTo(o2);
0707: }
0708:
0709: /**
0710: * Find the least node from a given node.
0711: *
0712: * @param node the node from which we will start searching
0713: * @param index the KEY or VALUE int
0714: * @return the smallest node, from the specified node, in the
0715: * specified mapping
0716: */
0717: private static Node leastNode(final Node node, final int index) {
0718: Node rval = node;
0719: if (rval != null) {
0720: while (rval.getLeft(index) != null) {
0721: rval = rval.getLeft(index);
0722: }
0723: }
0724: return rval;
0725: }
0726:
0727: /**
0728: * Find the greatest node from a given node.
0729: *
0730: * @param node the node from which we will start searching
0731: * @param index the KEY or VALUE int
0732: * @return the greatest node, from the specified node
0733: */
0734: private static Node greatestNode(final Node node, final int index) {
0735: Node rval = node;
0736: if (rval != null) {
0737: while (rval.getRight(index) != null) {
0738: rval = rval.getRight(index);
0739: }
0740: }
0741: return rval;
0742: }
0743:
0744: /**
0745: * copy the color from one node to another, dealing with the fact
0746: * that one or both nodes may, in fact, be null
0747: *
0748: * @param from the node whose color we're copying; may be null
0749: * @param to the node whose color we're changing; may be null
0750: * @param index the KEY or VALUE int
0751: */
0752: private static void copyColor(final Node from, final Node to,
0753: final int index) {
0754: if (to != null) {
0755: if (from == null) {
0756: // by default, make it black
0757: to.setBlack(index);
0758: } else {
0759: to.copyColor(from, index);
0760: }
0761: }
0762: }
0763:
0764: /**
0765: * is the specified node red? if the node does not exist, no, it's
0766: * black, thank you
0767: *
0768: * @param node the node (may be null) in question
0769: * @param index the KEY or VALUE int
0770: */
0771: private static boolean isRed(final Node node, final int index) {
0772: return ((node == null) ? false : node.isRed(index));
0773: }
0774:
0775: /**
0776: * is the specified black red? if the node does not exist, sure,
0777: * it's black, thank you
0778: *
0779: * @param node the node (may be null) in question
0780: * @param index the KEY or VALUE int
0781: */
0782: private static boolean isBlack(final Node node, final int index) {
0783: return ((node == null) ? true : node.isBlack(index));
0784: }
0785:
0786: /**
0787: * force a node (if it exists) red
0788: *
0789: * @param node the node (may be null) in question
0790: * @param index the KEY or VALUE int
0791: */
0792: private static void makeRed(final Node node, final int index) {
0793: if (node != null) {
0794: node.setRed(index);
0795: }
0796: }
0797:
0798: /**
0799: * force a node (if it exists) black
0800: *
0801: * @param node the node (may be null) in question
0802: * @param index the KEY or VALUE int
0803: */
0804: private static void makeBlack(final Node node, final int index) {
0805: if (node != null) {
0806: node.setBlack(index);
0807: }
0808: }
0809:
0810: /**
0811: * get a node's grandparent. mind you, the node, its parent, or
0812: * its grandparent may not exist. no problem
0813: *
0814: * @param node the node (may be null) in question
0815: * @param index the KEY or VALUE int
0816: */
0817: private static Node getGrandParent(final Node node, final int index) {
0818: return getParent(getParent(node, index), index);
0819: }
0820:
0821: /**
0822: * get a node's parent. mind you, the node, or its parent, may not
0823: * exist. no problem
0824: *
0825: * @param node the node (may be null) in question
0826: * @param index the KEY or VALUE int
0827: */
0828: private static Node getParent(final Node node, final int index) {
0829: return ((node == null) ? null : node.getParent(index));
0830: }
0831:
0832: /**
0833: * get a node's right child. mind you, the node may not exist. no
0834: * problem
0835: *
0836: * @param node the node (may be null) in question
0837: * @param index the KEY or VALUE int
0838: */
0839: private static Node getRightChild(final Node node, final int index) {
0840: return (node == null) ? null : node.getRight(index);
0841: }
0842:
0843: /**
0844: * get a node's left child. mind you, the node may not exist. no
0845: * problem
0846: *
0847: * @param node the node (may be null) in question
0848: * @param index the KEY or VALUE int
0849: */
0850: private static Node getLeftChild(final Node node, final int index) {
0851: return (node == null) ? null : node.getLeft(index);
0852: }
0853:
0854: /**
0855: * is this node its parent's left child? mind you, the node, or
0856: * its parent, may not exist. no problem. if the node doesn't
0857: * exist ... it's its non-existent parent's left child. If the
0858: * node does exist but has no parent ... no, we're not the
0859: * non-existent parent's left child. Otherwise (both the specified
0860: * node AND its parent exist), check.
0861: *
0862: * @param node the node (may be null) in question
0863: * @param index the KEY or VALUE int
0864: */
0865: private static boolean isLeftChild(final Node node, final int index) {
0866: return (node == null) ? true
0867: : ((node.getParent(index) == null) ? false
0868: : (node == node.getParent(index).getLeft(index)));
0869: }
0870:
0871: /**
0872: * is this node its parent's right child? mind you, the node, or
0873: * its parent, may not exist. no problem. if the node doesn't
0874: * exist ... it's its non-existent parent's right child. If the
0875: * node does exist but has no parent ... no, we're not the
0876: * non-existent parent's right child. Otherwise (both the
0877: * specified node AND its parent exist), check.
0878: *
0879: * @param node the node (may be null) in question
0880: * @param index the KEY or VALUE int
0881: */
0882: private static boolean isRightChild(final Node node, final int index) {
0883: return (node == null) ? true
0884: : ((node.getParent(index) == null) ? false
0885: : (node == node.getParent(index)
0886: .getRight(index)));
0887: }
0888:
0889: /**
0890: * do a rotate left. standard fare in the world of balanced trees
0891: *
0892: * @param node the node to be rotated
0893: * @param index the KEY or VALUE int
0894: */
0895: private void rotateLeft(final Node node, final int index) {
0896: Node rightChild = node.getRight(index);
0897: node.setRight(rightChild.getLeft(index), index);
0898:
0899: if (rightChild.getLeft(index) != null) {
0900: rightChild.getLeft(index).setParent(node, index);
0901: }
0902: rightChild.setParent(node.getParent(index), index);
0903:
0904: if (node.getParent(index) == null) {
0905: // node was the root ... now its right child is the root
0906: rootNode[index] = rightChild;
0907: } else if (node.getParent(index).getLeft(index) == node) {
0908: node.getParent(index).setLeft(rightChild, index);
0909: } else {
0910: node.getParent(index).setRight(rightChild, index);
0911: }
0912:
0913: rightChild.setLeft(node, index);
0914: node.setParent(rightChild, index);
0915: }
0916:
0917: /**
0918: * do a rotate right. standard fare in the world of balanced trees
0919: *
0920: * @param node the node to be rotated
0921: * @param index the KEY or VALUE int
0922: */
0923: private void rotateRight(final Node node, final int index) {
0924: Node leftChild = node.getLeft(index);
0925: node.setLeft(leftChild.getRight(index), index);
0926: if (leftChild.getRight(index) != null) {
0927: leftChild.getRight(index).setParent(node, index);
0928: }
0929: leftChild.setParent(node.getParent(index), index);
0930:
0931: if (node.getParent(index) == null) {
0932: // node was the root ... now its left child is the root
0933: rootNode[index] = leftChild;
0934: } else if (node.getParent(index).getRight(index) == node) {
0935: node.getParent(index).setRight(leftChild, index);
0936: } else {
0937: node.getParent(index).setLeft(leftChild, index);
0938: }
0939:
0940: leftChild.setRight(node, index);
0941: node.setParent(leftChild, index);
0942: }
0943:
0944: /**
0945: * complicated red-black insert stuff. Based on Sun's TreeMap
0946: * implementation, though it's barely recognizable any more
0947: *
0948: * @param insertedNode the node to be inserted
0949: * @param index the KEY or VALUE int
0950: */
0951: private void doRedBlackInsert(final Node insertedNode,
0952: final int index) {
0953: Node currentNode = insertedNode;
0954: makeRed(currentNode, index);
0955:
0956: while ((currentNode != null)
0957: && (currentNode != rootNode[index])
0958: && (isRed(currentNode.getParent(index), index))) {
0959: if (isLeftChild(getParent(currentNode, index), index)) {
0960: Node y = getRightChild(getGrandParent(currentNode,
0961: index), index);
0962:
0963: if (isRed(y, index)) {
0964: makeBlack(getParent(currentNode, index), index);
0965: makeBlack(y, index);
0966: makeRed(getGrandParent(currentNode, index), index);
0967:
0968: currentNode = getGrandParent(currentNode, index);
0969: } else {
0970: if (isRightChild(currentNode, index)) {
0971: currentNode = getParent(currentNode, index);
0972:
0973: rotateLeft(currentNode, index);
0974: }
0975:
0976: makeBlack(getParent(currentNode, index), index);
0977: makeRed(getGrandParent(currentNode, index), index);
0978:
0979: if (getGrandParent(currentNode, index) != null) {
0980: rotateRight(getGrandParent(currentNode, index),
0981: index);
0982: }
0983: }
0984: } else {
0985:
0986: // just like clause above, except swap left for right
0987: Node y = getLeftChild(
0988: getGrandParent(currentNode, index), index);
0989:
0990: if (isRed(y, index)) {
0991: makeBlack(getParent(currentNode, index), index);
0992: makeBlack(y, index);
0993: makeRed(getGrandParent(currentNode, index), index);
0994:
0995: currentNode = getGrandParent(currentNode, index);
0996: } else {
0997: if (isLeftChild(currentNode, index)) {
0998: currentNode = getParent(currentNode, index);
0999:
1000: rotateRight(currentNode, index);
1001: }
1002:
1003: makeBlack(getParent(currentNode, index), index);
1004: makeRed(getGrandParent(currentNode, index), index);
1005:
1006: if (getGrandParent(currentNode, index) != null) {
1007: rotateLeft(getGrandParent(currentNode, index),
1008: index);
1009: }
1010: }
1011: }
1012: }
1013:
1014: makeBlack(rootNode[index], index);
1015: }
1016:
1017: /**
1018: * complicated red-black delete stuff. Based on Sun's TreeMap
1019: * implementation, though it's barely recognizable any more
1020: *
1021: * @param deletedNode the node to be deleted
1022: */
1023: private void doRedBlackDelete(final Node deletedNode) {
1024: for (int index = FIRST_INDEX; index < NUMBER_OF_INDICES; index++) {
1025: // if deleted node has both left and children, swap with
1026: // the next greater node
1027: if ((deletedNode.getLeft(index) != null)
1028: && (deletedNode.getRight(index) != null)) {
1029: swapPosition(nextGreater(deletedNode, index),
1030: deletedNode, index);
1031: }
1032:
1033: Node replacement = ((deletedNode.getLeft(index) != null) ? deletedNode
1034: .getLeft(index)
1035: : deletedNode.getRight(index));
1036:
1037: if (replacement != null) {
1038: replacement.setParent(deletedNode.getParent(index),
1039: index);
1040:
1041: if (deletedNode.getParent(index) == null) {
1042: rootNode[index] = replacement;
1043: } else if (deletedNode == deletedNode.getParent(index)
1044: .getLeft(index)) {
1045: deletedNode.getParent(index).setLeft(replacement,
1046: index);
1047: } else {
1048: deletedNode.getParent(index).setRight(replacement,
1049: index);
1050: }
1051:
1052: deletedNode.setLeft(null, index);
1053: deletedNode.setRight(null, index);
1054: deletedNode.setParent(null, index);
1055:
1056: if (isBlack(deletedNode, index)) {
1057: doRedBlackDeleteFixup(replacement, index);
1058: }
1059: } else {
1060:
1061: // replacement is null
1062: if (deletedNode.getParent(index) == null) {
1063:
1064: // empty tree
1065: rootNode[index] = null;
1066: } else {
1067:
1068: // deleted node had no children
1069: if (isBlack(deletedNode, index)) {
1070: doRedBlackDeleteFixup(deletedNode, index);
1071: }
1072:
1073: if (deletedNode.getParent(index) != null) {
1074: if (deletedNode == deletedNode.getParent(index)
1075: .getLeft(index)) {
1076: deletedNode.getParent(index).setLeft(null,
1077: index);
1078: } else {
1079: deletedNode.getParent(index).setRight(null,
1080: index);
1081: }
1082:
1083: deletedNode.setParent(null, index);
1084: }
1085: }
1086: }
1087: }
1088: shrink();
1089: }
1090:
1091: /**
1092: * complicated red-black delete stuff. Based on Sun's TreeMap
1093: * implementation, though it's barely recognizable any more. This
1094: * rebalances the tree (somewhat, as red-black trees are not
1095: * perfectly balanced -- perfect balancing takes longer)
1096: *
1097: * @param replacementNode the node being replaced
1098: * @param index the KEY or VALUE int
1099: */
1100: private void doRedBlackDeleteFixup(final Node replacementNode,
1101: final int index) {
1102: Node currentNode = replacementNode;
1103:
1104: while ((currentNode != rootNode[index])
1105: && (isBlack(currentNode, index))) {
1106: if (isLeftChild(currentNode, index)) {
1107: Node siblingNode = getRightChild(getParent(currentNode,
1108: index), index);
1109:
1110: if (isRed(siblingNode, index)) {
1111: makeBlack(siblingNode, index);
1112: makeRed(getParent(currentNode, index), index);
1113: rotateLeft(getParent(currentNode, index), index);
1114:
1115: siblingNode = getRightChild(getParent(currentNode,
1116: index), index);
1117: }
1118:
1119: if (isBlack(getLeftChild(siblingNode, index), index)
1120: && isBlack(getRightChild(siblingNode, index),
1121: index)) {
1122: makeRed(siblingNode, index);
1123:
1124: currentNode = getParent(currentNode, index);
1125: } else {
1126: if (isBlack(getRightChild(siblingNode, index),
1127: index)) {
1128: makeBlack(getLeftChild(siblingNode, index),
1129: index);
1130: makeRed(siblingNode, index);
1131: rotateRight(siblingNode, index);
1132:
1133: siblingNode = getRightChild(getParent(
1134: currentNode, index), index);
1135: }
1136:
1137: copyColor(getParent(currentNode, index),
1138: siblingNode, index);
1139: makeBlack(getParent(currentNode, index), index);
1140: makeBlack(getRightChild(siblingNode, index), index);
1141: rotateLeft(getParent(currentNode, index), index);
1142:
1143: currentNode = rootNode[index];
1144: }
1145: } else {
1146: Node siblingNode = getLeftChild(getParent(currentNode,
1147: index), index);
1148:
1149: if (isRed(siblingNode, index)) {
1150: makeBlack(siblingNode, index);
1151: makeRed(getParent(currentNode, index), index);
1152: rotateRight(getParent(currentNode, index), index);
1153:
1154: siblingNode = getLeftChild(getParent(currentNode,
1155: index), index);
1156: }
1157:
1158: if (isBlack(getRightChild(siblingNode, index), index)
1159: && isBlack(getLeftChild(siblingNode, index),
1160: index)) {
1161: makeRed(siblingNode, index);
1162:
1163: currentNode = getParent(currentNode, index);
1164: } else {
1165: if (isBlack(getLeftChild(siblingNode, index), index)) {
1166: makeBlack(getRightChild(siblingNode, index),
1167: index);
1168: makeRed(siblingNode, index);
1169: rotateLeft(siblingNode, index);
1170:
1171: siblingNode = getLeftChild(getParent(
1172: currentNode, index), index);
1173: }
1174:
1175: copyColor(getParent(currentNode, index),
1176: siblingNode, index);
1177: makeBlack(getParent(currentNode, index), index);
1178: makeBlack(getLeftChild(siblingNode, index), index);
1179: rotateRight(getParent(currentNode, index), index);
1180:
1181: currentNode = rootNode[index];
1182: }
1183: }
1184: }
1185:
1186: makeBlack(currentNode, index);
1187: }
1188:
1189: /**
1190: * swap two nodes (except for their content), taking care of
1191: * special cases where one is the other's parent ... hey, it
1192: * happens.
1193: *
1194: * @param x one node
1195: * @param y another node
1196: * @param index the KEY or VALUE int
1197: */
1198: private void swapPosition(final Node x, final Node y,
1199: final int index) {
1200: // Save initial values.
1201: Node xFormerParent = x.getParent(index);
1202: Node xFormerLeftChild = x.getLeft(index);
1203: Node xFormerRightChild = x.getRight(index);
1204: Node yFormerParent = y.getParent(index);
1205: Node yFormerLeftChild = y.getLeft(index);
1206: Node yFormerRightChild = y.getRight(index);
1207: boolean xWasLeftChild = (x.getParent(index) != null)
1208: && (x == x.getParent(index).getLeft(index));
1209: boolean yWasLeftChild = (y.getParent(index) != null)
1210: && (y == y.getParent(index).getLeft(index));
1211:
1212: // Swap, handling special cases of one being the other's parent.
1213: if (x == yFormerParent) { // x was y's parent
1214: x.setParent(y, index);
1215:
1216: if (yWasLeftChild) {
1217: y.setLeft(x, index);
1218: y.setRight(xFormerRightChild, index);
1219: } else {
1220: y.setRight(x, index);
1221: y.setLeft(xFormerLeftChild, index);
1222: }
1223: } else {
1224: x.setParent(yFormerParent, index);
1225:
1226: if (yFormerParent != null) {
1227: if (yWasLeftChild) {
1228: yFormerParent.setLeft(x, index);
1229: } else {
1230: yFormerParent.setRight(x, index);
1231: }
1232: }
1233:
1234: y.setLeft(xFormerLeftChild, index);
1235: y.setRight(xFormerRightChild, index);
1236: }
1237:
1238: if (y == xFormerParent) { // y was x's parent
1239: y.setParent(x, index);
1240:
1241: if (xWasLeftChild) {
1242: x.setLeft(y, index);
1243: x.setRight(yFormerRightChild, index);
1244: } else {
1245: x.setRight(y, index);
1246: x.setLeft(yFormerLeftChild, index);
1247: }
1248: } else {
1249: y.setParent(xFormerParent, index);
1250:
1251: if (xFormerParent != null) {
1252: if (xWasLeftChild) {
1253: xFormerParent.setLeft(y, index);
1254: } else {
1255: xFormerParent.setRight(y, index);
1256: }
1257: }
1258:
1259: x.setLeft(yFormerLeftChild, index);
1260: x.setRight(yFormerRightChild, index);
1261: }
1262:
1263: // Fix children's parent pointers
1264: if (x.getLeft(index) != null) {
1265: x.getLeft(index).setParent(x, index);
1266: }
1267:
1268: if (x.getRight(index) != null) {
1269: x.getRight(index).setParent(x, index);
1270: }
1271:
1272: if (y.getLeft(index) != null) {
1273: y.getLeft(index).setParent(y, index);
1274: }
1275:
1276: if (y.getRight(index) != null) {
1277: y.getRight(index).setParent(y, index);
1278: }
1279:
1280: x.swapColors(y, index);
1281:
1282: // Check if root changed
1283: if (rootNode[index] == x) {
1284: rootNode[index] = y;
1285: } else if (rootNode[index] == y) {
1286: rootNode[index] = x;
1287: }
1288: }
1289:
1290: /**
1291: * check if an object is fit to be proper input ... has to be
1292: * Comparable and non-null
1293: *
1294: * @param o the object being checked
1295: * @param index the KEY or VALUE int (used to put the right word in the
1296: * exception message)
1297: *
1298: * @throws NullPointerException if o is null
1299: * @throws ClassCastException if o is not Comparable
1300: */
1301: private static void checkNonNullComparable(final Object o,
1302: final int index) {
1303: if (o == null) {
1304: throw new NullPointerException(dataName[index]
1305: + " cannot be null");
1306: }
1307: if (!(o instanceof Comparable)) {
1308: throw new ClassCastException(dataName[index]
1309: + " must be Comparable");
1310: }
1311: }
1312:
1313: /**
1314: * check a key for validity (non-null and implements Comparable)
1315: *
1316: * @param key the key to be checked
1317: *
1318: * @throws NullPointerException if key is null
1319: * @throws ClassCastException if key is not Comparable
1320: */
1321: private static void checkKey(final Object key) {
1322: checkNonNullComparable(key, KEY);
1323: }
1324:
1325: /**
1326: * check a value for validity (non-null and implements Comparable)
1327: *
1328: * @param value the value to be checked
1329: *
1330: * @throws NullPointerException if value is null
1331: * @throws ClassCastException if value is not Comparable
1332: */
1333: private static void checkValue(final Object value) {
1334: checkNonNullComparable(value, VALUE);
1335: }
1336:
1337: /**
1338: * check a key and a value for validity (non-null and implements
1339: * Comparable)
1340: *
1341: * @param key the key to be checked
1342: * @param value the value to be checked
1343: *
1344: * @throws NullPointerException if key or value is null
1345: * @throws ClassCastException if key or value is not Comparable
1346: */
1347: private static void checkKeyAndValue(final Object key,
1348: final Object value) {
1349: checkKey(key);
1350: checkValue(value);
1351: }
1352:
1353: /**
1354: * increment the modification count -- used to check for
1355: * concurrent modification of the map through the map and through
1356: * an Iterator from one of its Set or Collection views
1357: */
1358: private void modify() {
1359: modifications++;
1360: }
1361:
1362: /**
1363: * bump up the size and note that the map has changed
1364: */
1365: private void grow() {
1366: modify();
1367: nodeCount++;
1368: }
1369:
1370: /**
1371: * decrement the size and note that the map has changed
1372: */
1373: private void shrink() {
1374: modify();
1375: nodeCount--;
1376: }
1377:
1378: /**
1379: * insert a node by its value
1380: *
1381: * @param newNode the node to be inserted
1382: *
1383: * @throws IllegalArgumentException if the node already exists
1384: * in the value mapping
1385: */
1386: private void insertValue(final Node newNode)
1387: throws IllegalArgumentException {
1388: Node node = rootNode[VALUE];
1389:
1390: while (true) {
1391: int cmp = compare(newNode.getData(VALUE), node
1392: .getData(VALUE));
1393:
1394: if (cmp == 0) {
1395: throw new IllegalArgumentException(
1396: "Cannot store a duplicate value (\""
1397: + newNode.getData(VALUE)
1398: + "\") in this Map");
1399: } else if (cmp < 0) {
1400: if (node.getLeft(VALUE) != null) {
1401: node = node.getLeft(VALUE);
1402: } else {
1403: node.setLeft(newNode, VALUE);
1404: newNode.setParent(node, VALUE);
1405: doRedBlackInsert(newNode, VALUE);
1406:
1407: break;
1408: }
1409: } else { // cmp > 0
1410: if (node.getRight(VALUE) != null) {
1411: node = node.getRight(VALUE);
1412: } else {
1413: node.setRight(newNode, VALUE);
1414: newNode.setParent(node, VALUE);
1415: doRedBlackInsert(newNode, VALUE);
1416:
1417: break;
1418: }
1419: }
1420: }
1421: }
1422:
1423: //-----------------------------------------------------------------------
1424: /**
1425: * Compares for equals as per the API.
1426: *
1427: * @param obj the object to compare to
1428: * @param type the KEY or VALUE int
1429: * @return true if equal
1430: */
1431: private boolean doEquals(Object obj, final int type) {
1432: if (obj == this ) {
1433: return true;
1434: }
1435: if (obj instanceof Map == false) {
1436: return false;
1437: }
1438: Map other = (Map) obj;
1439: if (other.size() != size()) {
1440: return false;
1441: }
1442:
1443: if (nodeCount > 0) {
1444: try {
1445: for (MapIterator it = new ViewMapIterator(this , type); it
1446: .hasNext();) {
1447: Object key = it.next();
1448: Object value = it.getValue();
1449: if (value.equals(other.get(key)) == false) {
1450: return false;
1451: }
1452: }
1453: } catch (ClassCastException ex) {
1454: return false;
1455: } catch (NullPointerException ex) {
1456: return false;
1457: }
1458: }
1459: return true;
1460: }
1461:
1462: /**
1463: * Gets the hash code value for this map as per the API.
1464: *
1465: * @param type the KEY or VALUE int
1466: * @return the hash code value for this map
1467: */
1468: private int doHashCode(final int type) {
1469: int total = 0;
1470: if (nodeCount > 0) {
1471: for (MapIterator it = new ViewMapIterator(this , type); it
1472: .hasNext();) {
1473: Object key = it.next();
1474: Object value = it.getValue();
1475: total += (key.hashCode() ^ value.hashCode());
1476: }
1477: }
1478: return total;
1479: }
1480:
1481: /**
1482: * Gets the string form of this map as per AbstractMap.
1483: *
1484: * @param type the KEY or VALUE int
1485: * @return the string form of this map
1486: */
1487: private String doToString(final int type) {
1488: if (nodeCount == 0) {
1489: return "{}";
1490: }
1491: StringBuffer buf = new StringBuffer(nodeCount * 32);
1492: buf.append('{');
1493: MapIterator it = new ViewMapIterator(this , type);
1494: boolean hasNext = it.hasNext();
1495: while (hasNext) {
1496: Object key = it.next();
1497: Object value = it.getValue();
1498: buf.append(key == this ? "(this Map)" : key).append('=')
1499: .append(value == this ? "(this Map)" : value);
1500:
1501: hasNext = it.hasNext();
1502: if (hasNext) {
1503: buf.append(", ");
1504: }
1505: }
1506:
1507: buf.append('}');
1508: return buf.toString();
1509: }
1510:
1511: //-----------------------------------------------------------------------
1512: /**
1513: * A view of this map.
1514: */
1515: static class View extends AbstractSet {
1516:
1517: /** The parent map. */
1518: protected final TreeBidiMap main;
1519: /** Whether to return KEY or VALUE order. */
1520: protected final int orderType;
1521: /** Whether to return KEY, VALUE, MAPENTRY or INVERSEMAPENTRY data. */
1522: protected final int dataType;
1523:
1524: /**
1525: * Constructor.
1526: *
1527: * @param main the main map
1528: * @param orderType the KEY or VALUE int for the order
1529: * @param dataType the KEY, VALUE, MAPENTRY or INVERSEMAPENTRY int
1530: */
1531: View(final TreeBidiMap main, final int orderType,
1532: final int dataType) {
1533: super ();
1534: this .main = main;
1535: this .orderType = orderType;
1536: this .dataType = dataType;
1537: }
1538:
1539: public Iterator iterator() {
1540: return new ViewIterator(main, orderType, dataType);
1541: }
1542:
1543: public int size() {
1544: return main.size();
1545: }
1546:
1547: public boolean contains(final Object obj) {
1548: checkNonNullComparable(obj, dataType);
1549: return (main.lookup((Comparable) obj, dataType) != null);
1550: }
1551:
1552: public boolean remove(final Object obj) {
1553: return (main.doRemove((Comparable) obj, dataType) != null);
1554: }
1555:
1556: public void clear() {
1557: main.clear();
1558: }
1559: }
1560:
1561: //-----------------------------------------------------------------------
1562: /**
1563: * An iterator over the map.
1564: */
1565: static class ViewIterator implements OrderedIterator {
1566:
1567: /** The parent map. */
1568: protected final TreeBidiMap main;
1569: /** Whether to return KEY or VALUE order. */
1570: protected final int orderType;
1571: /** Whether to return KEY, VALUE, MAPENTRY or INVERSEMAPENTRY data. */
1572: protected final int dataType;
1573: /** The last node returned by the iterator. */
1574: protected Node lastReturnedNode;
1575: /** The next node to be returned by the iterator. */
1576: protected Node nextNode;
1577: /** The previous node in the sequence returned by the iterator. */
1578: protected Node previousNode;
1579: /** The modification count. */
1580: private int expectedModifications;
1581:
1582: /**
1583: * Constructor.
1584: *
1585: * @param main the main map
1586: * @param orderType the KEY or VALUE int for the order
1587: * @param dataType the KEY, VALUE, MAPENTRY or INVERSEMAPENTRY int
1588: */
1589: ViewIterator(final TreeBidiMap main, final int orderType,
1590: final int dataType) {
1591: super ();
1592: this .main = main;
1593: this .orderType = orderType;
1594: this .dataType = dataType;
1595: expectedModifications = main.modifications;
1596: nextNode = leastNode(main.rootNode[orderType], orderType);
1597: lastReturnedNode = null;
1598: previousNode = null;
1599: }
1600:
1601: public final boolean hasNext() {
1602: return (nextNode != null);
1603: }
1604:
1605: public final Object next() {
1606: if (nextNode == null) {
1607: throw new NoSuchElementException();
1608: }
1609: if (main.modifications != expectedModifications) {
1610: throw new ConcurrentModificationException();
1611: }
1612: lastReturnedNode = nextNode;
1613: previousNode = nextNode;
1614: nextNode = main.nextGreater(nextNode, orderType);
1615: return doGetData();
1616: }
1617:
1618: public boolean hasPrevious() {
1619: return (previousNode != null);
1620: }
1621:
1622: public Object previous() {
1623: if (previousNode == null) {
1624: throw new NoSuchElementException();
1625: }
1626: if (main.modifications != expectedModifications) {
1627: throw new ConcurrentModificationException();
1628: }
1629: nextNode = lastReturnedNode;
1630: if (nextNode == null) {
1631: nextNode = main.nextGreater(previousNode, orderType);
1632: }
1633: lastReturnedNode = previousNode;
1634: previousNode = main.nextSmaller(previousNode, orderType);
1635: return doGetData();
1636: }
1637:
1638: /**
1639: * Gets the data value for the lastReturnedNode field.
1640: * @return the data value
1641: */
1642: protected Object doGetData() {
1643: switch (dataType) {
1644: case KEY:
1645: return lastReturnedNode.getKey();
1646: case VALUE:
1647: return lastReturnedNode.getValue();
1648: case MAPENTRY:
1649: return lastReturnedNode;
1650: case INVERSEMAPENTRY:
1651: return new UnmodifiableMapEntry(lastReturnedNode
1652: .getValue(), lastReturnedNode.getKey());
1653: }
1654: return null;
1655: }
1656:
1657: public final void remove() {
1658: if (lastReturnedNode == null) {
1659: throw new IllegalStateException();
1660: }
1661: if (main.modifications != expectedModifications) {
1662: throw new ConcurrentModificationException();
1663: }
1664: main.doRedBlackDelete(lastReturnedNode);
1665: expectedModifications++;
1666: lastReturnedNode = null;
1667: if (nextNode == null) {
1668: previousNode = TreeBidiMap.greatestNode(
1669: main.rootNode[orderType], orderType);
1670: } else {
1671: previousNode = main.nextSmaller(nextNode, orderType);
1672: }
1673: }
1674: }
1675:
1676: //-----------------------------------------------------------------------
1677: /**
1678: * An iterator over the map.
1679: */
1680: static class ViewMapIterator extends ViewIterator implements
1681: OrderedMapIterator {
1682:
1683: private final int oppositeType;
1684:
1685: /**
1686: * Constructor.
1687: *
1688: * @param main the main map
1689: * @param orderType the KEY or VALUE int for the order
1690: */
1691: ViewMapIterator(final TreeBidiMap main, final int orderType) {
1692: super (main, orderType, orderType);
1693: this .oppositeType = oppositeIndex(dataType);
1694: }
1695:
1696: public Object getKey() {
1697: if (lastReturnedNode == null) {
1698: throw new IllegalStateException(
1699: "Iterator getKey() can only be called after next() and before remove()");
1700: }
1701: return lastReturnedNode.getData(dataType);
1702: }
1703:
1704: public Object getValue() {
1705: if (lastReturnedNode == null) {
1706: throw new IllegalStateException(
1707: "Iterator getValue() can only be called after next() and before remove()");
1708: }
1709: return lastReturnedNode.getData(oppositeType);
1710: }
1711:
1712: public Object setValue(final Object obj) {
1713: throw new UnsupportedOperationException();
1714: }
1715: }
1716:
1717: //-----------------------------------------------------------------------
1718: /**
1719: * A view of this map.
1720: */
1721: static class EntryView extends View {
1722:
1723: private final int oppositeType;
1724:
1725: /**
1726: * Constructor.
1727: *
1728: * @param main the main map
1729: * @param orderType the KEY or VALUE int for the order
1730: * @param dataType the MAPENTRY or INVERSEMAPENTRY int for the returned data
1731: */
1732: EntryView(final TreeBidiMap main, final int orderType,
1733: final int dataType) {
1734: super (main, orderType, dataType);
1735: this .oppositeType = TreeBidiMap.oppositeIndex(orderType);
1736: }
1737:
1738: public boolean contains(Object obj) {
1739: if (obj instanceof Map.Entry == false) {
1740: return false;
1741: }
1742: Map.Entry entry = (Map.Entry) obj;
1743: Object value = entry.getValue();
1744: Node node = main.lookup((Comparable) entry.getKey(),
1745: orderType);
1746: return (node != null && node.getData(oppositeType).equals(
1747: value));
1748: }
1749:
1750: public boolean remove(Object obj) {
1751: if (obj instanceof Map.Entry == false) {
1752: return false;
1753: }
1754: Map.Entry entry = (Map.Entry) obj;
1755: Object value = entry.getValue();
1756: Node node = main.lookup((Comparable) entry.getKey(),
1757: orderType);
1758: if (node != null
1759: && node.getData(oppositeType).equals(value)) {
1760: main.doRedBlackDelete(node);
1761: return true;
1762: }
1763: return false;
1764: }
1765: }
1766:
1767: //-----------------------------------------------------------------------
1768: /**
1769: * A node used to store the data.
1770: */
1771: static class Node implements Map.Entry, KeyValue {
1772:
1773: private Comparable[] data;
1774: private Node[] leftNode;
1775: private Node[] rightNode;
1776: private Node[] parentNode;
1777: private boolean[] blackColor;
1778: private int hashcodeValue;
1779: private boolean calculatedHashCode;
1780:
1781: /**
1782: * Make a new cell with given key and value, and with null
1783: * links, and black (true) colors.
1784: *
1785: * @param key
1786: * @param value
1787: */
1788: Node(final Comparable key, final Comparable value) {
1789: super ();
1790: data = new Comparable[] { key, value };
1791: leftNode = new Node[2];
1792: rightNode = new Node[2];
1793: parentNode = new Node[2];
1794: blackColor = new boolean[] { true, true };
1795: calculatedHashCode = false;
1796: }
1797:
1798: /**
1799: * Get the specified data.
1800: *
1801: * @param index the KEY or VALUE int
1802: * @return the key or value
1803: */
1804: private Comparable getData(final int index) {
1805: return data[index];
1806: }
1807:
1808: /**
1809: * Set this node's left node.
1810: *
1811: * @param node the new left node
1812: * @param index the KEY or VALUE int
1813: */
1814: private void setLeft(final Node node, final int index) {
1815: leftNode[index] = node;
1816: }
1817:
1818: /**
1819: * Get the left node.
1820: *
1821: * @param index the KEY or VALUE int
1822: * @return the left node, may be null
1823: */
1824: private Node getLeft(final int index) {
1825: return leftNode[index];
1826: }
1827:
1828: /**
1829: * Set this node's right node.
1830: *
1831: * @param node the new right node
1832: * @param index the KEY or VALUE int
1833: */
1834: private void setRight(final Node node, final int index) {
1835: rightNode[index] = node;
1836: }
1837:
1838: /**
1839: * Get the right node.
1840: *
1841: * @param index the KEY or VALUE int
1842: * @return the right node, may be null
1843: */
1844: private Node getRight(final int index) {
1845: return rightNode[index];
1846: }
1847:
1848: /**
1849: * Set this node's parent node.
1850: *
1851: * @param node the new parent node
1852: * @param index the KEY or VALUE int
1853: */
1854: private void setParent(final Node node, final int index) {
1855: parentNode[index] = node;
1856: }
1857:
1858: /**
1859: * Get the parent node.
1860: *
1861: * @param index the KEY or VALUE int
1862: * @return the parent node, may be null
1863: */
1864: private Node getParent(final int index) {
1865: return parentNode[index];
1866: }
1867:
1868: /**
1869: * Exchange colors with another node.
1870: *
1871: * @param node the node to swap with
1872: * @param index the KEY or VALUE int
1873: */
1874: private void swapColors(final Node node, final int index) {
1875: // Swap colors -- old hacker's trick
1876: blackColor[index] ^= node.blackColor[index];
1877: node.blackColor[index] ^= blackColor[index];
1878: blackColor[index] ^= node.blackColor[index];
1879: }
1880:
1881: /**
1882: * Is this node black?
1883: *
1884: * @param index the KEY or VALUE int
1885: * @return true if black (which is represented as a true boolean)
1886: */
1887: private boolean isBlack(final int index) {
1888: return blackColor[index];
1889: }
1890:
1891: /**
1892: * Is this node red?
1893: *
1894: * @param index the KEY or VALUE int
1895: * @return true if non-black
1896: */
1897: private boolean isRed(final int index) {
1898: return !blackColor[index];
1899: }
1900:
1901: /**
1902: * Make this node black.
1903: *
1904: * @param index the KEY or VALUE int
1905: */
1906: private void setBlack(final int index) {
1907: blackColor[index] = true;
1908: }
1909:
1910: /**
1911: * Make this node red.
1912: *
1913: * @param index the KEY or VALUE int
1914: */
1915: private void setRed(final int index) {
1916: blackColor[index] = false;
1917: }
1918:
1919: /**
1920: * Make this node the same color as another
1921: *
1922: * @param node the node whose color we're adopting
1923: * @param index the KEY or VALUE int
1924: */
1925: private void copyColor(final Node node, final int index) {
1926: blackColor[index] = node.blackColor[index];
1927: }
1928:
1929: //-------------------------------------------------------------------
1930: /**
1931: * Gets the key.
1932: *
1933: * @return the key corresponding to this entry.
1934: */
1935: public Object getKey() {
1936: return data[KEY];
1937: }
1938:
1939: /**
1940: * Gets the value.
1941: *
1942: * @return the value corresponding to this entry.
1943: */
1944: public Object getValue() {
1945: return data[VALUE];
1946: }
1947:
1948: /**
1949: * Optional operation that is not permitted in this implementation
1950: *
1951: * @param ignored
1952: * @return does not return
1953: * @throws UnsupportedOperationException always
1954: */
1955: public Object setValue(final Object ignored)
1956: throws UnsupportedOperationException {
1957: throw new UnsupportedOperationException(
1958: "Map.Entry.setValue is not supported");
1959: }
1960:
1961: /**
1962: * Compares the specified object with this entry for equality.
1963: * Returns true if the given object is also a map entry and
1964: * the two entries represent the same mapping.
1965: *
1966: * @param obj the object to be compared for equality with this entry.
1967: * @return true if the specified object is equal to this entry.
1968: */
1969: public boolean equals(final Object obj) {
1970: if (obj == this ) {
1971: return true;
1972: }
1973: if (!(obj instanceof Map.Entry)) {
1974: return false;
1975: }
1976: Map.Entry e = (Map.Entry) obj;
1977: return data[KEY].equals(e.getKey())
1978: && data[VALUE].equals(e.getValue());
1979: }
1980:
1981: /**
1982: * @return the hash code value for this map entry.
1983: */
1984: public int hashCode() {
1985: if (!calculatedHashCode) {
1986: hashcodeValue = data[KEY].hashCode()
1987: ^ data[VALUE].hashCode();
1988: calculatedHashCode = true;
1989: }
1990: return hashcodeValue;
1991: }
1992: }
1993:
1994: //-----------------------------------------------------------------------
1995: /**
1996: * A node used to store the data.
1997: */
1998: static class Inverse implements OrderedBidiMap {
1999:
2000: /** The parent map. */
2001: private final TreeBidiMap main;
2002: /** Store the keySet once created. */
2003: private Set keySet;
2004: /** Store the valuesSet once created. */
2005: private Set valuesSet;
2006: /** Store the entrySet once created. */
2007: private Set entrySet;
2008:
2009: /**
2010: * Constructor.
2011: * @param main the main map
2012: */
2013: Inverse(final TreeBidiMap main) {
2014: super ();
2015: this .main = main;
2016: }
2017:
2018: public int size() {
2019: return main.size();
2020: }
2021:
2022: public boolean isEmpty() {
2023: return main.isEmpty();
2024: }
2025:
2026: public Object get(final Object key) {
2027: return main.getKey(key);
2028: }
2029:
2030: public Object getKey(final Object value) {
2031: return main.get(value);
2032: }
2033:
2034: public boolean containsKey(final Object key) {
2035: return main.containsValue(key);
2036: }
2037:
2038: public boolean containsValue(final Object value) {
2039: return main.containsKey(value);
2040: }
2041:
2042: public Object firstKey() {
2043: if (main.nodeCount == 0) {
2044: throw new NoSuchElementException("Map is empty");
2045: }
2046: return TreeBidiMap.leastNode(main.rootNode[VALUE], VALUE)
2047: .getValue();
2048: }
2049:
2050: public Object lastKey() {
2051: if (main.nodeCount == 0) {
2052: throw new NoSuchElementException("Map is empty");
2053: }
2054: return TreeBidiMap
2055: .greatestNode(main.rootNode[VALUE], VALUE)
2056: .getValue();
2057: }
2058:
2059: public Object nextKey(Object key) {
2060: checkKey(key);
2061: Node node = main.nextGreater(main.lookup((Comparable) key,
2062: VALUE), VALUE);
2063: return (node == null ? null : node.getValue());
2064: }
2065:
2066: public Object previousKey(Object key) {
2067: checkKey(key);
2068: Node node = main.nextSmaller(main.lookup((Comparable) key,
2069: VALUE), VALUE);
2070: return (node == null ? null : node.getValue());
2071: }
2072:
2073: public Object put(final Object key, final Object value) {
2074: return main.doPut((Comparable) value, (Comparable) key,
2075: VALUE);
2076: }
2077:
2078: public void putAll(Map map) {
2079: Iterator it = map.entrySet().iterator();
2080: while (it.hasNext()) {
2081: Map.Entry entry = (Map.Entry) it.next();
2082: put(entry.getKey(), entry.getValue());
2083: }
2084: }
2085:
2086: public Object remove(final Object key) {
2087: return main.removeValue(key);
2088: }
2089:
2090: public Object removeValue(final Object value) {
2091: return main.remove(value);
2092: }
2093:
2094: public void clear() {
2095: main.clear();
2096: }
2097:
2098: public Set keySet() {
2099: if (keySet == null) {
2100: keySet = new View(main, VALUE, VALUE);
2101: }
2102: return keySet;
2103: }
2104:
2105: public Collection values() {
2106: if (valuesSet == null) {
2107: valuesSet = new View(main, VALUE, KEY);
2108: }
2109: return valuesSet;
2110: }
2111:
2112: public Set entrySet() {
2113: if (entrySet == null) {
2114: return new EntryView(main, VALUE, INVERSEMAPENTRY);
2115: }
2116: return entrySet;
2117: }
2118:
2119: public MapIterator mapIterator() {
2120: if (isEmpty()) {
2121: return EmptyOrderedMapIterator.INSTANCE;
2122: }
2123: return new ViewMapIterator(main, VALUE);
2124: }
2125:
2126: public OrderedMapIterator orderedMapIterator() {
2127: if (isEmpty()) {
2128: return EmptyOrderedMapIterator.INSTANCE;
2129: }
2130: return new ViewMapIterator(main, VALUE);
2131: }
2132:
2133: public BidiMap inverseBidiMap() {
2134: return main;
2135: }
2136:
2137: public OrderedBidiMap inverseOrderedBidiMap() {
2138: return main;
2139: }
2140:
2141: public boolean equals(Object obj) {
2142: return main.doEquals(obj, VALUE);
2143: }
2144:
2145: public int hashCode() {
2146: return main.doHashCode(VALUE);
2147: }
2148:
2149: public String toString() {
2150: return main.doToString(VALUE);
2151: }
2152: }
2153:
2154: }
|