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