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