You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ch...@apache.org on 2017/07/11 17:53:54 UTC
[06/18] commons-collections git commit: to ease maintenance,
removed all unreleased classes from the 1.x branch
http://git-wip-us.apache.org/repos/asf/commons-collections/blob/03ef3163/src/java/org/apache/commons/collections/DoubleOrderedMap.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/commons/collections/DoubleOrderedMap.java b/src/java/org/apache/commons/collections/DoubleOrderedMap.java
deleted file mode 100644
index 94009a4..0000000
--- a/src/java/org/apache/commons/collections/DoubleOrderedMap.java
+++ /dev/null
@@ -1,2046 +0,0 @@
-/*
- * $Header: /home/jerenkrantz/tmp/commons/commons-convert/cvs/home/cvs/jakarta-commons//collections/src/java/org/apache/commons/collections/DoubleOrderedMap.java,v 1.1 2002/01/20 04:36:08 craigmcc Exp $
- * $Revision: 1.1 $
- * $Date: 2002/01/20 04:36:08 $
- *
- * ====================================================================
- *
- * The Apache Software License, Version 1.1
- *
- * Copyright (c) 1999-2002 The Apache Software Foundation. All rights
- * reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- *
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in
- * the documentation and/or other materials provided with the
- * distribution.
- *
- * 3. The end-user documentation included with the redistribution, if
- * any, must include the following acknowlegement:
- * "This product includes software developed by the
- * Apache Software Foundation (http://www.apache.org/)."
- * Alternately, this acknowlegement may appear in the software itself,
- * if and wherever such third-party acknowlegements normally appear.
- *
- * 4. The names "The Jakarta Project", "Commons", and "Apache Software
- * Foundation" must not be used to endorse or promote products derived
- * from this software without prior written permission. For written
- * permission, please contact apache@apache.org.
- *
- * 5. Products derived from this software may not be called "Apache"
- * nor may "Apache" appear in their names without prior written
- * permission of the Apache Group.
- *
- * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
- * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
- * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
- * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
- * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
- * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- * ====================================================================
- *
- * This software consists of voluntary contributions made by many
- * individuals on behalf of the Apache Software Foundation. For more
- * information on the Apache Software Foundation, please see
- * <http://www.apache.org/>.
- *
- */
-
-package org.apache.commons.collections;
-
-
-
-import java.lang.reflect.Array;
-
-import java.util.*;
-
-
-/**
-* Red-Black tree-based implementation of Map. This class guarantees
-* that the map will be in both ascending key order and ascending
-* value order, sorted according to the natural order for the key's
-* and value's classes.<p>
-*
-* This Map is intended for applications that need to be able to look
-* up a key-value pairing by either key or value, and need to do so
-* with equal efficiency.<p>
-*
-* While that goal could be accomplished by taking a pair of TreeMaps
-* and redirecting requests to the appropriate TreeMap (e.g.,
-* containsKey would be directed to the TreeMap that maps values to
-* keys, containsValue would be directed to the TreeMap that maps keys
-* to values), there are problems with that implementation,
-* particularly when trying to keep the two TreeMaps synchronized with
-* each other. And if the data contained in the TreeMaps is large, the
-* cost of redundant storage becomes significant.<p>
-*
-* This solution keeps the data properly synchronized and minimizes
-* the data storage. The red-black algorithm is based on TreeMap's,
-* but has been modified to simultaneously map a tree node by key and
-* by value. This doubles the cost of put operations (but so does
-* using two TreeMaps), and nearly doubles the cost of remove
-* operations (there is a savings in that the lookup of the node to be
-* removed only has to be performed once). And since only one node
-* contains the key and value, storage is significantly less than that
-* required by two TreeMaps.<p>
-*
-* There are some limitations placed on data kept in this Map. The
-* biggest one is this:<p>
-*
-* When performing a put operation, neither the key nor the value may
-* already exist in the Map. In the java.util Map implementations
-* (HashMap, TreeMap), you can perform a put with an already mapped
-* key, and neither cares about duplicate values at all ... but this
-* implementation's put method with throw an IllegalArgumentException
-* if either the key or the value is already in the Map.<p>
-*
-* Obviously, that same restriction (and consequence of failing to
-* heed that restriction) applies to the putAll method.<p>
-*
-* The Map.Entry instances returned by the appropriate methods will
-* not allow setValue() and will throw an
-* UnsupportedOperationException on attempts to call that method.<p>
-*
-* New methods are added to take advantage of the fact that values are
-* kept sorted independently of their keys:<p>
-*
-* Object getKeyForValue(Object value) is the opposite of get; it
-* takes a value and returns its key, if any.<p>
-*
-* Object removeValue(Object value) finds and removes the specified
-* value and returns the now un-used key.<p>
-*
-* Set entrySetByValue() returns the Map.Entry's in a Set whose
-* iterator will iterate over the Map.Entry's in ascending order by
-* their corresponding values.<p>
-*
-* Set keySetByValue() returns the keys in a Set whose iterator will
-* iterate over the keys in ascending order by their corresponding
-* values.<p>
-*
-* Collection valuesByValue() returns the values in a Collection whose
-* iterator will iterate over the values in ascending order.<p>
-*
-* @author Marc Johnson (marcj at users dot sourceforge dot net)
-*/
-
-// final for performance
-public final class DoubleOrderedMap extends AbstractMap {
-
- private Node[] rootNode = new Node[]{ null,
- null };
- private int nodeCount = 0;
- private int modifications = 0;
- private Set[] setOfKeys = new Set[]{ null,
- null };
- private Set[] setOfEntries = new Set[]{ null,
- null };
- private Collection[] collectionOfValues = new Collection[]{
-null,
-
-null };
- private static final int KEY = 0;
- private static final int VALUE = 1;
- private static final int SUM_OF_INDICES = KEY + VALUE;
- private static final int FIRST_INDEX = 0;
- private static final int NUMBER_OF_INDICES = 2;
- private static final String[] dataName = new String[]{ "key",
- "value"
-};
-
- /**
- * Construct a new DoubleOrderedMap
- */
- public DoubleOrderedMap() {}
-
- /**
- * Constructs a new DoubleOrderedMap from an existing Map, with keys and
- * values sorted
- *
- * @param map the map whose mappings are to be placed in this map.
- *
- * @exception ClassCastException if the keys in the map are not
- * Comparable, or are not mutually
- * comparable; also if the values in
- * the map are not Comparable, or
- * are not mutually Comparable
- * @exception NullPointerException if any key or value in the map
- * is null
- * @exception IllegalArgumentException if there are duplicate keys
- * or duplicate values in the
- * map
- */
- public DoubleOrderedMap(final Map map)
- throws ClassCastException, NullPointerException,
- IllegalArgumentException {
- putAll(map);
- }
-
- /**
- * Returns the key to which this map maps the specified value.
- * Returns null if the map contains no mapping for this value.
- *
- * @param value value whose associated key is to be returned.
- *
- * @return the key to which this map maps the specified value, or
- * null if the map contains no mapping for this value.
- *
- * @exception ClassCastException if the value is of an
- * inappropriate type for this map.
- * @exception NullPointerException if the value is null
- */
- public Object getKeyForValue(final Object value)
- throws ClassCastException, NullPointerException {
- return doGet((Comparable) value, VALUE);
- }
-
- /**
- * Removes the mapping for this value from this map if present
- *
- * @param value value whose mapping is to be removed from the map.
- *
- * @return previous key associated with specified value, or null
- * if there was no mapping for value.
- */
- public Object removeValue(final Object value) {
- return doRemove((Comparable) value, VALUE);
- }
-
- /**
- * Returns a set view of the mappings contained in this map. Each
- * element in the returned set is a Map.Entry. The set is backed
- * by the map, so changes to the map are reflected in the set, and
- * vice-versa. If the map is modified while an iteration over the
- * set is in progress, the results of the iteration are
- * undefined. The set supports element removal, which removes the
- * corresponding mapping from the map, via the Iterator.remove,
- * Set.remove, removeAll, retainAll and clear operations. It does
- * not support the add or addAll operations.<p>
- *
- * The difference between this method and entrySet is that
- * entrySet's iterator() method returns an iterator that iterates
- * over the mappings in ascending order by key. This method's
- * iterator method iterates over the mappings in ascending order
- * by value.
- *
- * @return a set view of the mappings contained in this map.
- */
- public Set entrySetByValue() {
-
- if (setOfEntries[VALUE] == null) {
- setOfEntries[VALUE] = new AbstractSet() {
-
- public Iterator iterator() {
-
- return new DoubleOrderedMapIterator(VALUE) {
-
- protected Object doGetNext() {
- return lastReturnedNode;
- }
- };
- }
-
- public boolean contains(Object o) {
-
- if (!(o instanceof Map.Entry)) {
- return false;
- }
-
- Map.Entry entry = (Map.Entry) o;
- Object key = entry.getKey();
- Node node = lookup((Comparable) entry.getValue(),
- VALUE);
-
- return (node != null) && node.getData(KEY).equals(key);
- }
-
- public boolean remove(Object o) {
-
- if (!(o instanceof Map.Entry)) {
- return false;
- }
-
- Map.Entry entry = (Map.Entry) o;
- Object key = entry.getKey();
- Node node = lookup((Comparable) entry.getValue(),
- VALUE);
-
- if ((node != null) && node.getData(KEY).equals(key)) {
- doRedBlackDelete(node);
-
- return true;
- }
-
- return false;
- }
-
- public int size() {
- return DoubleOrderedMap.this.size();
- }
-
- public void clear() {
- DoubleOrderedMap.this.clear();
- }
- };
- }
-
- return setOfEntries[VALUE];
- }
-
- /**
- * Returns a set view of the keys contained in this map. The set
- * is backed by the map, so changes to the map are reflected in
- * the set, and vice-versa. If the map is modified while an
- * iteration over the set is in progress, the results of the
- * iteration are undefined. The set supports element removal,
- * which removes the corresponding mapping from the map, via the
- * Iterator.remove, Set.remove, removeAll, retainAll, and clear
- * operations. It does not support the add or addAll
- * operations.<p>
- *
- * The difference between this method and keySet is that keySet's
- * iterator() method returns an iterator that iterates over the
- * keys in ascending order by key. This method's iterator method
- * iterates over the keys in ascending order by value.
- *
- * @return a set view of the keys contained in this map.
- */
- public Set keySetByValue() {
-
- if (setOfKeys[VALUE] == null) {
- setOfKeys[VALUE] = new AbstractSet() {
-
- public Iterator iterator() {
-
- return new DoubleOrderedMapIterator(VALUE) {
-
- protected Object doGetNext() {
- return lastReturnedNode.getData(KEY);
- }
- };
- }
-
- public int size() {
- return DoubleOrderedMap.this.size();
- }
-
- public boolean contains(Object o) {
- return containsKey(o);
- }
-
- public boolean remove(Object o) {
-
- int oldnodeCount = nodeCount;
-
- DoubleOrderedMap.this.remove(o);
-
- return nodeCount != oldnodeCount;
- }
-
- public void clear() {
- DoubleOrderedMap.this.clear();
- }
- };
- }
-
- return setOfKeys[VALUE];
- }
-
- /**
- * Returns a collection view of the values contained in this
- * map. The collection is backed by the map, so changes to the map
- * are reflected in the collection, and vice-versa. If the map is
- * modified while an iteration over the collection is in progress,
- * the results of the iteration are undefined. The collection
- * supports element removal, which removes the corresponding
- * mapping from the map, via the Iterator.remove,
- * Collection.remove, removeAll, retainAll and clear operations.
- * It does not support the add or addAll operations.<p>
- *
- * The difference between this method and values is that values's
- * iterator() method returns an iterator that iterates over the
- * values in ascending order by key. This method's iterator method
- * iterates over the values in ascending order by key.
- *
- * @return a collection view of the values contained in this map.
- */
- public Collection valuesByValue() {
-
- if (collectionOfValues[VALUE] == null) {
- collectionOfValues[VALUE] = new AbstractCollection() {
-
- public Iterator iterator() {
-
- return new DoubleOrderedMapIterator(VALUE) {
-
- protected Object doGetNext() {
- return lastReturnedNode.getData(VALUE);
- }
- };
- }
-
- public int size() {
- return DoubleOrderedMap.this.size();
- }
-
- public boolean contains(Object o) {
- return containsValue(o);
- }
-
- public boolean remove(Object o) {
-
- int oldnodeCount = nodeCount;
-
- removeValue(o);
-
- return nodeCount != oldnodeCount;
- }
-
- public boolean removeAll(Collection c) {
-
- boolean modified = false;
- Iterator iter = c.iterator();
-
- while (iter.hasNext()) {
- if (removeValue(iter.next()) != null) {
- modified = true;
- }
- }
-
- return modified;
- }
-
- public void clear() {
- DoubleOrderedMap.this.clear();
- }
- };
- }
-
- return collectionOfValues[VALUE];
- }
-
- /**
- * common remove logic (remove by key or remove by value)
- *
- * @param o the key, or value, that we're looking for
- * @param index KEY or VALUE
- *
- * @return the key, if remove by value, or the value, if remove by
- * key. null if the specified key or value could not be
- * found
- */
- private Object doRemove(final Comparable o, final int index) {
-
- Node node = lookup(o, index);
- Object rval = null;
-
- if (node != null) {
- rval = node.getData(oppositeIndex(index));
-
- doRedBlackDelete(node);
- }
-
- return rval;
- }
-
- /**
- * common get logic, used to get by key or get by value
- *
- * @param o the key or value that we're looking for
- * @param index KEY or VALUE
- *
- * @return the key (if the value was mapped) or the value (if the
- * key was mapped); null if we couldn't find the specified
- * object
- */
- private Object doGet(final Comparable o, final int index) {
-
- checkNonNullComparable(o, index);
-
- Node node = lookup(o, index);
-
- return ((node == null)
- ? null
- : node.getData(oppositeIndex(index)));
- }
-
- /**
- * Get the opposite index of the specified index
- *
- * @param index KEY or VALUE
- *
- * @return VALUE (if KEY was specified), else KEY
- */
- private int oppositeIndex(final int index) {
-
- // old trick ... to find the opposite of a value, m or n,
- // subtract the value from the sum of the two possible
- // values. (m + n) - m = n; (m + n) - n = m
- return SUM_OF_INDICES - index;
- }
-
- /**
- * do the actual lookup of a piece of data
- *
- * @param data the key or value to be looked up
- * @param index KEY or VALUE
- *
- * @return the desired Node, or null if there is no mapping of the
- * specified data
- */
- private Node lookup(final Comparable data, final int index) {
-
- Node rval = null;
- Node node = rootNode[index];
-
- while (node != null) {
- int cmp = compare(data, node.getData(index));
-
- if (cmp == 0) {
- rval = node;
-
- break;
- } else {
- node = (cmp < 0)
- ? node.getLeft(index)
- : node.getRight(index);
- }
- }
-
- return rval;
- }
-
- /**
- * Compare two objects
- *
- * @param o1 the first object
- * @param o2 the second object
- *
- * @return negative value if o1 < o2; 0 if o1 == o2; positive
- * value if o1 > o2
- */
- private static int compare(final Comparable o1, final Comparable o2) {
- return ((Comparable) o1).compareTo(o2);
- }
-
- /**
- * find the least node from a given node. very useful for starting
- * a sorting iterator ...
- *
- * @param node the node from which we will start searching
- * @param index KEY or VALUE
- *
- * @return the smallest node, from the specified node, in the
- * specified mapping
- */
- private static Node leastNode(final Node node, final int index) {
-
- Node rval = node;
-
- if (rval != null) {
- while (rval.getLeft(index) != null) {
- rval = rval.getLeft(index);
- }
- }
-
- return rval;
- }
-
- /**
- * get the next larger node from the specified node
- *
- * @param node the node to be searched from
- * @param index KEY or VALUE
- *
- * @return the specified node
- */
- private Node nextGreater(final Node node, final int index) {
-
- Node rval = null;
-
- if (node == null) {
- rval = null;
- } else if (node.getRight(index) != null) {
-
- // everything to the node's right is larger. The least of
- // the right node's descendents is the next larger node
- rval = leastNode(node.getRight(index), index);
- } else {
-
- // traverse up our ancestry until we find an ancestor that
- // is null or one whose left child is our ancestor. If we
- // find a null, then this node IS the largest node in the
- // tree, and there is no greater node. Otherwise, we are
- // the largest node in the subtree on that ancestor's left
- // ... and that ancestor is the next greatest node
- Node parent = node.getParent(index);
- Node child = node;
-
- while ((parent != null) && (child == parent.getRight(index))) {
- child = parent;
- parent = parent.getParent(index);
- }
-
- rval = parent;
- }
-
- return rval;
- }
-
- /**
- * copy the color from one node to another, dealing with the fact
- * that one or both nodes may, in fact, be null
- *
- * @param from the node whose color we're copying; may be null
- * @param to the node whose color we're changing; may be null
- * @param index KEY or VALUE
- */
- private static void copyColor(final Node from, final Node to,
- final int index) {
-
- if (to != null) {
- if (from == null) {
-
- // by default, make it black
- to.setBlack(index);
- } else {
- to.copyColor(from, index);
- }
- }
- }
-
- /**
- * is the specified node red? if the node does not exist, no, it's
- * black, thank you
- *
- * @param node the node (may be null) in question
- * @param index KEY or VALUE
- */
- private static boolean isRed(final Node node, final int index) {
-
- return ((node == null)
- ? false
- : node.isRed(index));
- }
-
- /**
- * is the specified black red? if the node does not exist, sure,
- * it's black, thank you
- *
- * @param node the node (may be null) in question
- * @param index KEY or VALUE
- */
- private static boolean isBlack(final Node node, final int index) {
-
- return ((node == null)
- ? true
- : node.isBlack(index));
- }
-
- /**
- * force a node (if it exists) red
- *
- * @param node the node (may be null) in question
- * @param index KEY or VALUE
- */
- private static void makeRed(final Node node, final int index) {
-
- if (node != null) {
- node.setRed(index);
- }
- }
-
- /**
- * force a node (if it exists) black
- *
- * @param node the node (may be null) in question
- * @param index KEY or VALUE
- */
- private static void makeBlack(final Node node, final int index) {
-
- if (node != null) {
- node.setBlack(index);
- }
- }
-
- /**
- * get a node's grandparent. mind you, the node, its parent, or
- * its grandparent may not exist. no problem
- *
- * @param node the node (may be null) in question
- * @param index KEY or VALUE
- */
- private static Node getGrandParent(final Node node, final int index) {
- return getParent(getParent(node, index), index);
- }
-
- /**
- * get a node's parent. mind you, the node, or its parent, may not
- * exist. no problem
- *
- * @param node the node (may be null) in question
- * @param index KEY or VALUE
- */
- private static Node getParent(final Node node, final int index) {
-
- return ((node == null)
- ? null
- : node.getParent(index));
- }
-
- /**
- * get a node's right child. mind you, the node may not exist. no
- * problem
- *
- * @param node the node (may be null) in question
- * @param index KEY or VALUE
- */
- private static Node getRightChild(final Node node, final int index) {
-
- return (node == null)
- ? null
- : node.getRight(index);
- }
-
- /**
- * get a node's left child. mind you, the node may not exist. no
- * problem
- *
- * @param node the node (may be null) in question
- * @param index KEY or VALUE
- */
- private static Node getLeftChild(final Node node, final int index) {
-
- return (node == null)
- ? null
- : node.getLeft(index);
- }
-
- /**
- * is this node its parent's left child? mind you, the node, or
- * its parent, may not exist. no problem. if the node doesn't
- * exist ... it's its non-existent parent's left child. If the
- * node does exist but has no parent ... no, we're not the
- * non-existent parent's left child. Otherwise (both the specified
- * node AND its parent exist), check.
- *
- * @param node the node (may be null) in question
- * @param index KEY or VALUE
- */
- private static boolean isLeftChild(final Node node, final int index) {
-
- return (node == null)
- ? true
- : ((node.getParent(index) == null)
- ? false
- : (node == node.getParent(index).getLeft(index)));
- }
-
- /**
- * is this node its parent's right child? mind you, the node, or
- * its parent, may not exist. no problem. if the node doesn't
- * exist ... it's its non-existent parent's right child. If the
- * node does exist but has no parent ... no, we're not the
- * non-existent parent's right child. Otherwise (both the
- * specified node AND its parent exist), check.
- *
- * @param node the node (may be null) in question
- * @param index KEY or VALUE
- */
- private static boolean isRightChild(final Node node, final int index) {
-
- return (node == null)
- ? true
- : ((node.getParent(index) == null)
- ? false
- : (node == node.getParent(index).getRight(index)));
- }
-
- /**
- * do a rotate left. standard fare in the world of balanced trees
- *
- * @param node the node to be rotated
- * @param index KEY or VALUE
- */
- private void rotateLeft(final Node node, final int index) {
-
- Node rightChild = node.getRight(index);
-
- node.setRight(rightChild.getLeft(index), index);
-
- if (rightChild.getLeft(index) != null) {
- rightChild.getLeft(index).setParent(node, index);
- }
-
- rightChild.setParent(node.getParent(index), index);
-
- if (node.getParent(index) == null) {
-
- // node was the root ... now its right child is the root
- rootNode[index] = rightChild;
- } else if (node.getParent(index).getLeft(index) == node) {
- node.getParent(index).setLeft(rightChild, index);
- } else {
- node.getParent(index).setRight(rightChild, index);
- }
-
- rightChild.setLeft(node, index);
- node.setParent(rightChild, index);
- }
-
- /**
- * do a rotate right. standard fare in the world of balanced trees
- *
- * @param node the node to be rotated
- * @param index KEY or VALUE
- */
- private void rotateRight(final Node node, final int index) {
-
- Node leftChild = node.getLeft(index);
-
- node.setLeft(leftChild.getRight(index), index);
-
- if (leftChild.getRight(index) != null) {
- leftChild.getRight(index).setParent(node, index);
- }
-
- leftChild.setParent(node.getParent(index), index);
-
- if (node.getParent(index) == null) {
-
- // node was the root ... now its left child is the root
- rootNode[index] = leftChild;
- } else if (node.getParent(index).getRight(index) == node) {
- node.getParent(index).setRight(leftChild, index);
- } else {
- node.getParent(index).setLeft(leftChild, index);
- }
-
- leftChild.setRight(node, index);
- node.setParent(leftChild, index);
- }
-
- /**
- * complicated red-black insert stuff. Based on Sun's TreeMap
- * implementation, though it's barely recognizeable any more
- *
- * @param insertedNode the node to be inserted
- * @param index KEY or VALUE
- */
- private void doRedBlackInsert(final Node insertedNode, final int index)
-{
-
- Node currentNode = insertedNode;
-
- makeRed(currentNode, index);
-
- while ((currentNode != null) && (currentNode != rootNode[index])
- && (isRed(currentNode.getParent(index), index))) {
- if (isLeftChild(getParent(currentNode, index), index)) {
- Node y = getRightChild(getGrandParent(currentNode, index),
- index);
-
- if (isRed(y, index)) {
- makeBlack(getParent(currentNode, index), index);
- makeBlack(y, index);
- makeRed(getGrandParent(currentNode, index), index);
-
- currentNode = getGrandParent(currentNode, index);
- } else {
- if (isRightChild(currentNode, index)) {
- currentNode = getParent(currentNode, index);
-
- rotateLeft(currentNode, index);
- }
-
- makeBlack(getParent(currentNode, index), index);
- makeRed(getGrandParent(currentNode, index), index);
-
- if (getGrandParent(currentNode, index) != null) {
- rotateRight(getGrandParent(currentNode, index),
- index);
- }
- }
- } else {
-
- // just like clause above, except swap left for right
- Node y = getLeftChild(getGrandParent(currentNode, index),
- index);
-
- if (isRed(y, index)) {
- makeBlack(getParent(currentNode, index), index);
- makeBlack(y, index);
- makeRed(getGrandParent(currentNode, index), index);
-
- currentNode = getGrandParent(currentNode, index);
- } else {
- if (isLeftChild(currentNode, index)) {
- currentNode = getParent(currentNode, index);
-
- rotateRight(currentNode, index);
- }
-
- makeBlack(getParent(currentNode, index), index);
- makeRed(getGrandParent(currentNode, index), index);
-
- if (getGrandParent(currentNode, index) != null) {
- rotateLeft(getGrandParent(currentNode, index),
-index);
- }
- }
- }
- }
-
- makeBlack(rootNode[index], index);
- }
-
- /**
- * complicated red-black delete stuff. Based on Sun's TreeMap
- * implementation, though it's barely recognizeable any more
- *
- * @param deletedNode the node to be deleted
- */
- private void doRedBlackDelete(final Node deletedNode) {
-
- for (int index = FIRST_INDEX; index < NUMBER_OF_INDICES; index++) {
-
- // if deleted node has both left and children, swap with
- // the next greater node
- if ((deletedNode.getLeft(index) != null)
- && (deletedNode.getRight(index) != null)) {
- swapPosition(nextGreater(deletedNode, index), deletedNode,
- index);
- }
-
- Node replacement = ((deletedNode.getLeft(index) != null)
- ? deletedNode.getLeft(index)
- : deletedNode.getRight(index));
-
- if (replacement != null) {
- replacement.setParent(deletedNode.getParent(index), index);
-
- if (deletedNode.getParent(index) == null) {
- rootNode[index] = replacement;
- } else if (deletedNode
- == deletedNode.getParent(index).getLeft(index)) {
- deletedNode.getParent(index).setLeft(replacement,
-index);
- } else {
- deletedNode.getParent(index).setRight(replacement,
-index);
- }
-
- deletedNode.setLeft(null, index);
- deletedNode.setRight(null, index);
- deletedNode.setParent(null, index);
-
- if (isBlack(deletedNode, index)) {
- doRedBlackDeleteFixup(replacement, index);
- }
- } else {
-
- // replacement is null
- if (deletedNode.getParent(index) == null) {
-
- // empty tree
- rootNode[index] = null;
- } else {
-
- // deleted node had no children
- if (isBlack(deletedNode, index)) {
- doRedBlackDeleteFixup(deletedNode, index);
- }
-
- if (deletedNode.getParent(index) != null) {
- if (deletedNode
- == deletedNode.getParent(index)
- .getLeft(index)) {
- deletedNode.getParent(index).setLeft(null,
-index);
- } else {
- deletedNode.getParent(index).setRight(null,
- index);
- }
-
- deletedNode.setParent(null, index);
- }
- }
- }
- }
-
- shrink();
- }
-
- /**
- * complicated red-black delete stuff. Based on Sun's TreeMap
- * implementation, though it's barely recognizeable any more. This
- * rebalances the tree (somewhat, as red-black trees are not
- * perfectly balanced -- perfect balancing takes longer)
- *
- * @param replacementNode the node being replaced
- * @param index KEY or VALUE
- */
- private void doRedBlackDeleteFixup(final Node replacementNode,
- final int index) {
-
- Node currentNode = replacementNode;
-
- while ((currentNode != rootNode[index])
- && (isBlack(currentNode, index))) {
- if (isLeftChild(currentNode, index)) {
- Node siblingNode =
- getRightChild(getParent(currentNode, index), index);
-
- if (isRed(siblingNode, index)) {
- makeBlack(siblingNode, index);
- makeRed(getParent(currentNode, index), index);
- rotateLeft(getParent(currentNode, index), index);
-
- siblingNode = getRightChild(getParent(currentNode,
-index),
- index);
- }
-
- if (isBlack(getLeftChild(siblingNode, index), index)
- && isBlack(getRightChild(siblingNode, index),
- index)) {
- makeRed(siblingNode, index);
-
- currentNode = getParent(currentNode, index);
- } else {
- if (isBlack(getRightChild(siblingNode, index), index)) {
- makeBlack(getLeftChild(siblingNode, index), index);
- makeRed(siblingNode, index);
- rotateRight(siblingNode, index);
-
- siblingNode =
- getRightChild(getParent(currentNode, index),
- index);
- }
-
- copyColor(getParent(currentNode, index), siblingNode,
- index);
- makeBlack(getParent(currentNode, index), index);
- makeBlack(getRightChild(siblingNode, index), index);
- rotateLeft(getParent(currentNode, index), index);
-
- currentNode = rootNode[index];
- }
- } else {
- Node siblingNode = getLeftChild(getParent(currentNode,
-index),
- index);
-
- if (isRed(siblingNode, index)) {
- makeBlack(siblingNode, index);
- makeRed(getParent(currentNode, index), index);
- rotateRight(getParent(currentNode, index), index);
-
- siblingNode = getLeftChild(getParent(currentNode,
-index),
- index);
- }
-
- if (isBlack(getRightChild(siblingNode, index), index)
- && isBlack(getLeftChild(siblingNode, index), index))
-{
- makeRed(siblingNode, index);
-
- currentNode = getParent(currentNode, index);
- } else {
- if (isBlack(getLeftChild(siblingNode, index), index)) {
- makeBlack(getRightChild(siblingNode, index), index);
- makeRed(siblingNode, index);
- rotateLeft(siblingNode, index);
-
- siblingNode =
- getLeftChild(getParent(currentNode, index),
- index);
- }
-
- copyColor(getParent(currentNode, index), siblingNode,
- index);
- makeBlack(getParent(currentNode, index), index);
- makeBlack(getLeftChild(siblingNode, index), index);
- rotateRight(getParent(currentNode, index), index);
-
- currentNode = rootNode[index];
- }
- }
- }
-
- makeBlack(currentNode, index);
- }
-
- /**
- * swap two nodes (except for their content), taking care of
- * special cases where one is the other's parent ... hey, it
- * happens.
- *
- * @param x one node
- * @param y another node
- * @param index KEY or VALUE
- */
- private void swapPosition(final Node x, final Node y, final int index) {
-
- // Save initial values.
- Node xFormerParent = x.getParent(index);
- Node xFormerLeftChild = x.getLeft(index);
- Node xFormerRightChild = x.getRight(index);
- Node yFormerParent = y.getParent(index);
- Node yFormerLeftChild = y.getLeft(index);
- Node yFormerRightChild = y.getRight(index);
- boolean xWasLeftChild =
- (x.getParent(index) != null)
- && (x == x.getParent(index).getLeft(index));
- boolean yWasLeftChild =
- (y.getParent(index) != null)
- && (y == y.getParent(index).getLeft(index));
-
- // Swap, handling special cases of one being the other's parent.
- if (x == yFormerParent) { // x was y's parent
- x.setParent(y, index);
-
- if (yWasLeftChild) {
- y.setLeft(x, index);
- y.setRight(xFormerRightChild, index);
- } else {
- y.setRight(x, index);
- y.setLeft(xFormerLeftChild, index);
- }
- } else {
- x.setParent(yFormerParent, index);
-
- if (yFormerParent != null) {
- if (yWasLeftChild) {
- yFormerParent.setLeft(x, index);
- } else {
- yFormerParent.setRight(x, index);
- }
- }
-
- y.setLeft(xFormerLeftChild, index);
- y.setRight(xFormerRightChild, index);
- }
-
- if (y == xFormerParent) { // y was x's parent
- y.setParent(x, index);
-
- if (xWasLeftChild) {
- x.setLeft(y, index);
- x.setRight(yFormerRightChild, index);
- } else {
- x.setRight(y, index);
- x.setLeft(yFormerLeftChild, index);
- }
- } else {
- y.setParent(xFormerParent, index);
-
- if (xFormerParent != null) {
- if (xWasLeftChild) {
- xFormerParent.setLeft(y, index);
- } else {
- xFormerParent.setRight(y, index);
- }
- }
-
- x.setLeft(yFormerLeftChild, index);
- x.setRight(yFormerRightChild, index);
- }
-
- // Fix children's parent pointers
- if (x.getLeft(index) != null) {
- x.getLeft(index).setParent(x, index);
- }
-
- if (x.getRight(index) != null) {
- x.getRight(index).setParent(x, index);
- }
-
- if (y.getLeft(index) != null) {
- y.getLeft(index).setParent(y, index);
- }
-
- if (y.getRight(index) != null) {
- y.getRight(index).setParent(y, index);
- }
-
- x.swapColors(y, index);
-
- // Check if root changed
- if (rootNode[index] == x) {
- rootNode[index] = y;
- } else if (rootNode[index] == y) {
- rootNode[index] = x;
- }
- }
-
- /**
- * check if an object is fit to be proper input ... has to be
- * Comparable and non-null
- *
- * @param o the object being checked
- * @param index KEY or VALUE (used to put the right word in the
- * exception message)
- *
- * @exception NullPointerException if o is null
- * @exception ClassCastException if o is not Comparable
- */
- private static void checkNonNullComparable(final Object o,
- final int index) {
-
- if (o == null) {
- throw new NullPointerException(dataName[index]
- + " cannot be null");
- }
-
- if (!(o instanceof Comparable)) {
- throw new ClassCastException(dataName[index]
- + " must be Comparable");
- }
- }
-
- /**
- * check a key for validity (non-null and implements Comparable)
- *
- * @param key the key to be checked
- *
- * @exception NullPointerException if key is null
- * @exception ClassCastException if key is not Comparable
- */
- private static void checkKey(final Object key) {
- checkNonNullComparable(key, KEY);
- }
-
- /**
- * check a value for validity (non-null and implements Comparable)
- *
- * @param value the value to be checked
- *
- * @exception NullPointerException if value is null
- * @exception ClassCastException if value is not Comparable
- */
- private static void checkValue(final Object value) {
- checkNonNullComparable(value, VALUE);
- }
-
- /**
- * check a key and a value for validity (non-null and implements
- * Comparable)
- *
- * @param key the key to be checked
- * @param value the value to be checked
- *
- * @exception NullPointerException if key or value is null
- * @exception ClassCastException if key or value is not Comparable
- */
- private static void checkKeyAndValue(final Object key,
- final Object value) {
- checkKey(key);
- checkValue(value);
- }
-
- /**
- * increment the modification count -- used to check for
- * concurrent modification of the map through the map and through
- * an Iterator from one of its Set or Collection views
- */
- private void modify() {
- modifications++;
- }
-
- /**
- * bump up the size and note that the map has changed
- */
- private void grow() {
-
- modify();
-
- nodeCount++;
- }
-
- /**
- * decrement the size and note that the map has changed
- */
- private void shrink() {
-
- modify();
-
- nodeCount--;
- }
-
- /**
- * insert a node by its value
- *
- * @param newNode the node to be inserted
- *
- * @exception IllegalArgumentException if the node already exists
- * in the value mapping
- */
- private void insertValue(final Node newNode)
- throws IllegalArgumentException {
-
- Node node = rootNode[VALUE];
-
- while (true) {
- int cmp = compare(newNode.getData(VALUE), node.getData(VALUE));
-
- if (cmp == 0) {
- throw new IllegalArgumentException(
- "Cannot store a duplicate value (\""
- + newNode.getData(VALUE) + "\") in this Map");
- } else if (cmp < 0) {
- if (node.getLeft(VALUE) != null) {
- node = node.getLeft(VALUE);
- } else {
- node.setLeft(newNode, VALUE);
- newNode.setParent(node, VALUE);
- doRedBlackInsert(newNode, VALUE);
-
- break;
- }
- } else { // cmp > 0
- if (node.getRight(VALUE) != null) {
- node = node.getRight(VALUE);
- } else {
- node.setRight(newNode, VALUE);
- newNode.setParent(node, VALUE);
- doRedBlackInsert(newNode, VALUE);
-
- break;
- }
- }
- }
- }
-
- /* ********** START implementation of Map ********** */
-
- /**
- * Returns the number of key-value mappings in this map. If the
- * map contains more than Integer.MAXVALUE elements, returns
- * Integer.MAXVALUE.
- *
- * @return the number of key-value mappings in this map.
- */
- public int size() {
- return nodeCount;
- }
-
- /**
- * Returns true if this map contains a mapping for the specified
- * key.
- *
- * @param key key whose presence in this map is to be tested.
- *
- * @return true if this map contains a mapping for the specified
- * key.
- *
- * @exception ClassCastException if the key is of an inappropriate
- * type for this map.
- * @exception NullPointerException if the key is null
- */
- public boolean containsKey(final Object key)
- throws ClassCastException, NullPointerException {
-
- checkKey(key);
-
- return lookup((Comparable) key, KEY) != null;
- }
-
- /**
- * Returns true if this map maps one or more keys to the
- * specified value.
- *
- * @param value value whose presence in this map is to be tested.
- *
- * @return true if this map maps one or more keys to the specified
- * value.
- */
- public boolean containsValue(final Object value) {
-
- checkValue(value);
-
- return lookup((Comparable) value, VALUE) != null;
- }
-
- /**
- * Returns the value to which this map maps the specified
- * key. Returns null if the map contains no mapping for this key.
- *
- * @param key key whose associated value is to be returned.
- *
- * @return the value to which this map maps the specified key, or
- * null if the map contains no mapping for this key.
- *
- * @exception ClassCastException if the key is of an inappropriate
- * type for this map.
- * @exception NullPointerException if the key is null
- */
- public Object get(final Object key)
- throws ClassCastException, NullPointerException {
- return doGet((Comparable) key, KEY);
- }
-
- /**
- * Associates the specified value with the specified key in this
- * map.
- *
- * @param key key with which the specified value is to be
- * associated.
- * @param value value to be associated with the specified key.
- *
- * @return null
- *
- * @exception ClassCastException if the class of the specified key
- * or value prevents it from being
- * stored in this map.
- * @exception NullPointerException if the specified key or value
- * is null
- * @exception IllegalArgumentException if the key duplicates an
- * existing key, or if the
- * value duplicates an
- * existing value
- */
- public Object put(final Object key, final Object value)
- throws ClassCastException, NullPointerException,
- IllegalArgumentException {
-
- checkKeyAndValue(key, value);
-
- Node node = rootNode[KEY];
-
- if (node == null) {
- Node root = new Node((Comparable) key, (Comparable) value);
-
- rootNode[KEY] = root;
- rootNode[VALUE] = root;
-
- grow();
- } else {
- while (true) {
- int cmp = compare((Comparable) key, node.getData(KEY));
-
- if (cmp == 0) {
- throw new IllegalArgumentException(
- "Cannot store a duplicate key (\"" + key
- + "\") in this Map");
- } else if (cmp < 0) {
- if (node.getLeft(KEY) != null) {
- node = node.getLeft(KEY);
- } else {
- Node newNode = new Node((Comparable) key,
- (Comparable) value);
-
- insertValue(newNode);
- node.setLeft(newNode, KEY);
- newNode.setParent(node, KEY);
- doRedBlackInsert(newNode, KEY);
- grow();
-
- break;
- }
- } else { // cmp > 0
- if (node.getRight(KEY) != null) {
- node = node.getRight(KEY);
- } else {
- Node newNode = new Node((Comparable) key,
- (Comparable) value);
-
- insertValue(newNode);
- node.setRight(newNode, KEY);
- newNode.setParent(node, KEY);
- doRedBlackInsert(newNode, KEY);
- grow();
-
- break;
- }
- }
- }
- }
-
- return null;
- }
-
- /**
- * Removes the mapping for this key from this map if present
- *
- * @param key key whose mapping is to be removed from the map.
- *
- * @return previous value associated with specified key, or null
- * if there was no mapping for key.
- */
- public Object remove(final Object key) {
- return doRemove((Comparable) key, KEY);
- }
-
- /**
- * Removes all mappings from this map
- */
- public void clear() {
-
- modify();
-
- nodeCount = 0;
- rootNode[KEY] = null;
- rootNode[VALUE] = null;
- }
-
- /**
- * Returns a set view of the keys contained in this map. The set
- * is backed by the map, so changes to the map are reflected in
- * the set, and vice-versa. If the map is modified while an
- * iteration over the set is in progress, the results of the
- * iteration are undefined. The set supports element removal,
- * which removes the corresponding mapping from the map, via the
- * Iterator.remove, Set.remove, removeAll, retainAll, and clear
- * operations. It does not support the add or addAll operations.
- *
- * @return a set view of the keys contained in this map.
- */
- public Set keySet() {
-
- if (setOfKeys[KEY] == null) {
- setOfKeys[KEY] = new AbstractSet() {
-
- public Iterator iterator() {
-
- return new DoubleOrderedMapIterator(KEY) {
-
- protected Object doGetNext() {
- return lastReturnedNode.getData(KEY);
- }
- };
- }
-
- public int size() {
- return DoubleOrderedMap.this.size();
- }
-
- public boolean contains(Object o) {
- return containsKey(o);
- }
-
- public boolean remove(Object o) {
-
- int oldNodeCount = nodeCount;
-
- DoubleOrderedMap.this.remove(o);
-
- return nodeCount != oldNodeCount;
- }
-
- public void clear() {
- DoubleOrderedMap.this.clear();
- }
- };
- }
-
- return setOfKeys[KEY];
- }
-
- /**
- * Returns a collection view of the values contained in this
- * map. The collection is backed by the map, so changes to the map
- * are reflected in the collection, and vice-versa. If the map is
- * modified while an iteration over the collection is in progress,
- * the results of the iteration are undefined. The collection
- * supports element removal, which removes the corresponding
- * mapping from the map, via the Iterator.remove,
- * Collection.remove, removeAll, retainAll and clear operations.
- * It does not support the add or addAll operations.
- *
- * @return a collection view of the values contained in this map.
- */
- public Collection values() {
-
- if (collectionOfValues[KEY] == null) {
- collectionOfValues[KEY] = new AbstractCollection() {
-
- public Iterator iterator() {
-
- return new DoubleOrderedMapIterator(KEY) {
-
- protected Object doGetNext() {
- return lastReturnedNode.getData(VALUE);
- }
- };
- }
-
- public int size() {
- return DoubleOrderedMap.this.size();
- }
-
- public boolean contains(Object o) {
- return containsValue(o);
- }
-
- public boolean remove(Object o) {
-
- int oldNodeCount = nodeCount;
-
- removeValue(o);
-
- return nodeCount != oldNodeCount;
- }
-
- public boolean removeAll(Collection c) {
-
- boolean modified = false;
- Iterator iter = c.iterator();
-
- while (iter.hasNext()) {
- if (removeValue(iter.next()) != null) {
- modified = true;
- }
- }
-
- return modified;
- }
-
- public void clear() {
- DoubleOrderedMap.this.clear();
- }
- };
- }
-
- return collectionOfValues[KEY];
- }
-
- /**
- * Returns a set view of the mappings contained in this map. Each
- * element in the returned set is a Map.Entry. The set is backed
- * by the map, so changes to the map are reflected in the set, and
- * vice-versa. If the map is modified while an iteration over the
- * set is in progress, the results of the iteration are
- * undefined. The set supports element removal, which removes the
- * corresponding mapping from the map, via the Iterator.remove,
- * Set.remove, removeAll, retainAll and clear operations. It does
- * not support the add or addAll operations.
- *
- * @return a set view of the mappings contained in this map.
- */
- public Set entrySet() {
-
- if (setOfEntries[KEY] == null) {
- setOfEntries[KEY] = new AbstractSet() {
-
- public Iterator iterator() {
-
- return new DoubleOrderedMapIterator(KEY) {
-
- protected Object doGetNext() {
- return lastReturnedNode;
- }
- };
- }
-
- public boolean contains(Object o) {
-
- if (!(o instanceof Map.Entry)) {
- return false;
- }
-
- Map.Entry entry = (Map.Entry) o;
- Object value = entry.getValue();
- Node node = lookup((Comparable) entry.getKey(),
- KEY);
-
- return (node != null)
- && node.getData(VALUE).equals(value);
- }
-
- public boolean remove(Object o) {
-
- if (!(o instanceof Map.Entry)) {
- return false;
- }
-
- Map.Entry entry = (Map.Entry) o;
- Object value = entry.getValue();
- Node node = lookup((Comparable) entry.getKey(),
- KEY);
-
- if ((node != null) && node.getData(VALUE).equals(value))
-{
- doRedBlackDelete(node);
-
- return true;
- }
-
- return false;
- }
-
- public int size() {
- return DoubleOrderedMap.this.size();
- }
-
- public void clear() {
- DoubleOrderedMap.this.clear();
- }
- };
- }
-
- return setOfEntries[KEY];
- }
-
- /* ********** END implementation of Map ********** */
- private abstract class DoubleOrderedMapIterator implements Iterator {
-
- private int expectedModifications;
- protected Node lastReturnedNode;
- private Node nextNode;
- private int iteratorType;
-
- /**
- * Constructor
- *
- * @param type
- */
- DoubleOrderedMapIterator(final int type) {
-
- iteratorType = type;
- expectedModifications = DoubleOrderedMap.this.modifications;
- lastReturnedNode = null;
- nextNode = leastNode(rootNode[iteratorType],
- iteratorType);
- }
-
- /**
- * @return 'next', whatever that means for a given kind of
- * DoubleOrderedMapIterator
- */
- protected abstract Object doGetNext();
-
- /* ********** START implementation of Iterator ********** */
-
- /**
- * @return true if the iterator has more elements.
- */
- public final boolean hasNext() {
- return nextNode != null;
- }
-
- /**
- * @return the next element in the iteration.
- *
- * @exception NoSuchElementException if iteration has no more
- * elements.
- * @exception ConcurrentModificationException if the
- * DoubleOrderedMap is
- * modified behind
- * the iterator's
- * back
- */
- public final Object next()
- throws NoSuchElementException,
- ConcurrentModificationException {
-
- if (nextNode == null) {
- throw new NoSuchElementException();
- }
-
- if (modifications != expectedModifications) {
- throw new ConcurrentModificationException();
- }
-
- lastReturnedNode = nextNode;
- nextNode = nextGreater(nextNode, iteratorType);
-
- return doGetNext();
- }
-
- /**
- * Removes from the underlying collection the last element
- * returned by the iterator. This method can be called only
- * once per call to next. The behavior of an iterator is
- * unspecified if the underlying collection is modified while
- * the iteration is in progress in any way other than by
- * calling this method.
- *
- * @exception IllegalStateException if the next method has not
- * yet been called, or the
- * remove method has already
- * been called after the last
- * call to the next method.
- * @exception ConcurrentModificationException if the
- * DoubleOrderedMap is
- * modified behind
- * the iterator's
- * back
- */
- public final void remove()
- throws IllegalStateException,
- ConcurrentModificationException {
-
- if (lastReturnedNode == null) {
- throw new IllegalStateException();
- }
-
- if (modifications != expectedModifications) {
- throw new ConcurrentModificationException();
- }
-
- doRedBlackDelete(lastReturnedNode);
-
- expectedModifications++;
-
- lastReturnedNode = null;
- }
-
- /* ********** END implementation of Iterator ********** */
- } // end private abstract class DoubleOrderedMapIterator
-
- // final for performance
- private static final class Node implements Map.Entry {
-
- private Comparable[] data;
- private Node[] leftNode;
- private Node[] rightNode;
- private Node[] parentNode;
- private boolean[] blackColor;
- private int hashcodeValue;
- private boolean calculatedHashCode;
-
- /**
- * Make a new cell with given key and value, and with null
- * links, and black (true) colors.
- *
- * @param key
- * @param value
- */
- Node(final Comparable key, final Comparable value) {
-
- data = new Comparable[]{ key, value };
- leftNode = new Node[]{ null, null };
- rightNode = new Node[]{ null, null };
- parentNode = new Node[]{ null, null };
- blackColor = new boolean[]{ true, true };
- calculatedHashCode = false;
- }
-
- /**
- * get the specified data
- *
- * @param index KEY or VALUE
- *
- * @return the key or value
- */
- private Comparable getData(final int index) {
- return data[index];
- }
-
- /**
- * Set this node's left node
- *
- * @param node the new left node
- * @param index KEY or VALUE
- */
- private void setLeft(final Node node, final int index) {
- leftNode[index] = node;
- }
-
- /**
- * get the left node
- *
- * @param index KEY or VALUE
- *
- * @return the left node -- may be null
- */
- private Node getLeft(final int index) {
- return leftNode[index];
- }
-
- /**
- * Set this node's right node
- *
- * @param node the new right node
- * @param index KEY or VALUE
- */
- private void setRight(final Node node, final int index) {
- rightNode[index] = node;
- }
-
- /**
- * get the right node
- *
- * @param index KEY or VALUE
- *
- * @return the right node -- may be null
- */
- private Node getRight(final int index) {
- return rightNode[index];
- }
-
- /**
- * Set this node's parent node
- *
- * @param node the new parent node
- * @param index KEY or VALUE
- */
- private void setParent(final Node node, final int index) {
- parentNode[index] = node;
- }
-
- /**
- * get the parent node
- *
- * @param index KEY or VALUE
- *
- * @return the parent node -- may be null
- */
- private Node getParent(final int index) {
- return parentNode[index];
- }
-
- /**
- * exchange colors with another node
- *
- * @param node the node to swap with
- * @param index KEY or VALUE
- */
- private void swapColors(final Node node, final int index) {
-
- // Swap colors -- old hacker's trick
- blackColor[index] ^= node.blackColor[index];
- node.blackColor[index] ^= blackColor[index];
- blackColor[index] ^= node.blackColor[index];
- }
-
- /**
- * is this node black?
- *
- * @param index KEY or VALUE
- *
- * @return true if black (which is represented as a true boolean)
- */
- private boolean isBlack(final int index) {
- return blackColor[index];
- }
-
- /**
- * is this node red?
- *
- * @param index KEY or VALUE
- *
- * @return true if non-black
- */
- private boolean isRed(final int index) {
- return !blackColor[index];
- }
-
- /**
- * make this node black
- *
- * @param index KEY or VALUE
- */
- private void setBlack(final int index) {
- blackColor[index] = true;
- }
-
- /**
- * make this node red
- *
- * @param index KEY or VALUE
- */
- private void setRed(final int index) {
- blackColor[index] = false;
- }
-
- /**
- * make this node the same color as another
- *
- * @param node the node whose color we're adopting
- * @param index KEY or VALUE
- */
- private void copyColor(final Node node, final int index) {
- blackColor[index] = node.blackColor[index];
- }
-
- /* ********** START implementation of Map.Entry ********** */
-
- /**
- * @return the key corresponding to this entry.
- */
- public Object getKey() {
- return data[KEY];
- }
-
- /**
- * @return the value corresponding to this entry.
- */
- public Object getValue() {
- return data[VALUE];
- }
-
- /**
- * Optional operation that is not permitted in this
- * implementation
- *
- * @param ignored
- *
- * @return does not return
- *
- * @exception UnsupportedOperationException
- */
- public Object setValue(Object ignored)
- throws UnsupportedOperationException {
- throw new UnsupportedOperationException(
- "Map.Entry.setValue is not supported");
- }
-
- /**
- * Compares the specified object with this entry for equality.
- * Returns true if the given object is also a map entry and
- * the two entries represent the same mapping.
- *
- * @param o object to be compared for equality with this map
- * entry.
- * @return true if the specified object is equal to this map
- * entry.
- */
- public boolean equals(Object o) {
-
- if (this == o) {
- return true;
- }
-
- if (!(o instanceof Map.Entry)) {
- return false;
- }
-
- Map.Entry e = (Map.Entry) o;
-
- return data[KEY].equals(e.getKey())
- && data[VALUE].equals(e.getValue());
- }
-
- /**
- * @return the hash code value for this map entry.
- */
- public int hashCode() {
-
- if (!calculatedHashCode) {
- hashcodeValue = data[KEY].hashCode()
- ^ data[VALUE].hashCode();
- calculatedHashCode = true;
- }
-
- return hashcodeValue;
- }
-
- /* ********** END implementation of Map.Entry ********** */
- }
-} // end public class DoubleOrderedMap
http://git-wip-us.apache.org/repos/asf/commons-collections/blob/03ef3163/src/java/org/apache/commons/collections/HashBag.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/commons/collections/HashBag.java b/src/java/org/apache/commons/collections/HashBag.java
deleted file mode 100644
index bb1f7df..0000000
--- a/src/java/org/apache/commons/collections/HashBag.java
+++ /dev/null
@@ -1,89 +0,0 @@
-/*
- * $Header: /home/jerenkrantz/tmp/commons/commons-convert/cvs/home/cvs/jakarta-commons//collections/src/java/org/apache/commons/collections/HashBag.java,v 1.2 2002/02/10 08:07:42 jstrachan Exp $
- * $Revision: 1.2 $
- * $Date: 2002/02/10 08:07:42 $
- *
- * ====================================================================
- *
- * The Apache Software License, Version 1.1
- *
- * Copyright (c) 1999-2002 The Apache Software Foundation. All rights
- * reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- *
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in
- * the documentation and/or other materials provided with the
- * distribution.
- *
- * 3. The end-user documentation included with the redistribution, if
- * any, must include the following acknowlegement:
- * "This product includes software developed by the
- * Apache Software Foundation (http://www.apache.org/)."
- * Alternately, this acknowlegement may appear in the software itself,
- * if and wherever such third-party acknowlegements normally appear.
- *
- * 4. The names "The Jakarta Project", "Commons", and "Apache Software
- * Foundation" must not be used to endorse or promote products derived
- * from this software without prior written permission. For written
- * permission, please contact apache@apache.org.
- *
- * 5. Products derived from this software may not be called "Apache"
- * nor may "Apache" appear in their names without prior written
- * permission of the Apache Group.
- *
- * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
- * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
- * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
- * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
- * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
- * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- * ====================================================================
- *
- * This software consists of voluntary contributions made by many
- * individuals on behalf of the Apache Software Foundation. For more
- * information on the Apache Software Foundation, please see
- * <http://www.apache.org/>.
- *
- */
-
-package org.apache.commons.collections;
-
-import java.util.Collection;
-import java.util.HashMap;
-
-/**
- * An implementation of {@link Bag} that is backed by a {@link
- * HashMap}.
- *
- * @author Chuck Burdick
- **/
-public class HashBag extends AbstractBag implements Bag {
- public HashBag() {
- setMap(new HashMap());
- }
-
- /**
- * New {@link Bag} containing all the members of the given
- * collection.
- * @see #addAll
- **/
- public HashBag(Collection c) {
- this();
- addAll(c);
- }
-}
-
-
http://git-wip-us.apache.org/repos/asf/commons-collections/blob/03ef3163/src/java/org/apache/commons/collections/ListUtils.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/commons/collections/ListUtils.java b/src/java/org/apache/commons/collections/ListUtils.java
deleted file mode 100644
index 55f5ad3..0000000
--- a/src/java/org/apache/commons/collections/ListUtils.java
+++ /dev/null
@@ -1,119 +0,0 @@
-/*
- * $Header: /home/jerenkrantz/tmp/commons/commons-convert/cvs/home/cvs/jakarta-commons//collections/src/java/org/apache/commons/collections/ListUtils.java,v 1.3 2002/02/10 08:07:42 jstrachan Exp $
- * $Revision: 1.3 $
- * $Date: 2002/02/10 08:07:42 $
- *
- * ====================================================================
- *
- * The Apache Software License, Version 1.1
- *
- * Copyright (c) 1999-2002 The Apache Software Foundation. All rights
- * reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- *
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in
- * the documentation and/or other materials provided with the
- * distribution.
- *
- * 3. The end-user documentation included with the redistribution, if
- * any, must include the following acknowlegement:
- * "This product includes software developed by the
- * Apache Software Foundation (http://www.apache.org/)."
- * Alternately, this acknowlegement may appear in the software itself,
- * if and wherever such third-party acknowlegements normally appear.
- *
- * 4. The names "The Jakarta Project", "Commons", and "Apache Software
- * Foundation" must not be used to endorse or promote products derived
- * from this software without prior written permission. For written
- * permission, please contact apache@apache.org.
- *
- * 5. Products derived from this software may not be called "Apache"
- * nor may "Apache" appear in their names without prior written
- * permission of the Apache Group.
- *
- * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
- * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
- * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
- * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
- * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
- * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- * ====================================================================
- *
- * This software consists of voluntary contributions made by many
- * individuals on behalf of the Apache Software Foundation. For more
- * information on the Apache Software Foundation, please see
- * <http://www.apache.org/>.
- *
- */
-package org.apache.commons.collections;
-
-import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.List;
-
-/**
- * Miscelaneous utilities to manipulate Lists.
- *
- * @author <a href="mailto:fede@apache.org">Federico Barbieri</a>
- * @author <a href="mailto:donaldp@apache.org">Peter Donald</a>
- * @deprecated See {@link org.apache.commons.collections.CollectionUtils}.
- */
-public class ListUtils
-{
- public static List intersection( final List list1, final List list2 )
- {
- final ArrayList result = new ArrayList();
- final Iterator iterator = list2.iterator();
-
- while( iterator.hasNext() )
- {
- final Object o = iterator.next();
-
- if ( list1.contains( o ) )
- {
- result.add( o );
- }
- }
-
- return result;
- }
-
- public static List subtract( final List list1, final List list2 )
- {
- final ArrayList result = new ArrayList( list1 );
- final Iterator iterator = list2.iterator();
-
- while( iterator.hasNext() )
- {
- result.remove( iterator.next() );
- }
-
- return result;
- }
-
- public static List sum( final List list1, final List list2 )
- {
- return subtract( union( list1, list2 ),
- intersection( list1, list2 ) );
- }
-
- public static List union( final List list1, final List list2 )
- {
- final ArrayList result = new ArrayList( list1 );
- result.addAll( list2 );
- return result;
- }
-}
http://git-wip-us.apache.org/repos/asf/commons-collections/blob/03ef3163/src/java/org/apache/commons/collections/MultiHashMap.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/commons/collections/MultiHashMap.java b/src/java/org/apache/commons/collections/MultiHashMap.java
deleted file mode 100644
index 0bed923..0000000
--- a/src/java/org/apache/commons/collections/MultiHashMap.java
+++ /dev/null
@@ -1,206 +0,0 @@
-/*
- * $Header: /home/jerenkrantz/tmp/commons/commons-convert/cvs/home/cvs/jakarta-commons//collections/src/java/org/apache/commons/collections/MultiHashMap.java,v 1.2 2002/02/10 08:07:42 jstrachan Exp $
- * $Revision: 1.2 $
- * $Date: 2002/02/10 08:07:42 $
- *
- * ====================================================================
- *
- * The Apache Software License, Version 1.1
- *
- * Copyright (c) 1999-2002 The Apache Software Foundation. All rights
- * reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- *
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in
- * the documentation and/or other materials provided with the
- * distribution.
- *
- * 3. The end-user documentation included with the redistribution, if
- * any, must include the following acknowlegement:
- * "This product includes software developed by the
- * Apache Software Foundation (http://www.apache.org/)."
- * Alternately, this acknowlegement may appear in the software itself,
- * if and wherever such third-party acknowlegements normally appear.
- *
- * 4. The names "The Jakarta Project", "Commons", and "Apache Software
- * Foundation" must not be used to endorse or promote products derived
- * from this software without prior written permission. For written
- * permission, please contact apache@apache.org.
- *
- * 5. Products derived from this software may not be called "Apache"
- * nor may "Apache" appear in their names without prior written
- * permission of the Apache Group.
- *
- * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
- * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
- * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
- * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
- * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
- * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- * ====================================================================
- *
- * This software consists of voluntary contributions made by many
- * individuals on behalf of the Apache Software Foundation. For more
- * information on the Apache Software Foundation, please see
- * <http://www.apache.org/>.
- *
- */
-package org.apache.commons.collections;
-
-import java.util.*;
-import java.io.*;
-
-/** see MultiMap for details of an important semantic difference
- * between this and a typical HashMap
- *
- * @author Christopher Berry
- * @author <a href="mailto:jstrachan@apache.org">James Strachan</a>
- */
-public class MultiHashMap extends HashMap implements MultiMap
-{
- //----------------- Data
- private static int sCount = 0;
- private String mName = null;
-
- public MultiHashMap()
- {
- super();
- setName();
- }
-
- public MultiHashMap( int initialCapacity )
- {
- super( initialCapacity );
- setName();
- }
-
- public MultiHashMap(int initialCapacity, float loadFactor )
- {
- super( initialCapacity, loadFactor);
- setName();
- }
-
- public MultiHashMap( Map mapToCopy )
- {
- super( mapToCopy );
- }
-
- private void setName()
- {
- sCount++;
- mName = "MultiMap-" + sCount;
- }
-
- public String getName()
- { return mName; }
-
- public Object put( Object key, Object value )
- {
- // NOTE:: put might be called during deserialization !!!!!!
- // so we must provide a hook to handle this case
- // This means that we cannot make MultiMaps of ArrayLists !!!
-
- if ( value instanceof ArrayList ) {
- return ( super.put( key, value ) );
- }
-
- ArrayList keyList = (ArrayList)(super.get( key ));
- if ( keyList == null ) {
- keyList = new ArrayList(10);
-
- super.put( key, keyList );
- }
-
- boolean results = keyList.add( value );
-
- return ( results ? value : null );
- }
-
- public boolean containsValue( Object value )
- {
- Set pairs = super.entrySet();
-
- if ( pairs == null )
- return false;
-
- Iterator pairsIterator = pairs.iterator();
- while ( pairsIterator.hasNext() ) {
- Map.Entry keyValuePair = (Map.Entry)(pairsIterator.next());
- ArrayList list = (ArrayList)(keyValuePair.getValue());
- if( list.contains( value ) )
- return true;
- }
- return false;
- }
-
- public Object remove( Object key, Object item )
- {
- ArrayList valuesForKey = (ArrayList) super.get( key );
-
- if ( valuesForKey == null )
- return null;
-
- valuesForKey.remove( item );
- return item;
- }
-
- public void clear()
- {
- Set pairs = super.entrySet();
- Iterator pairsIterator = pairs.iterator();
- while ( pairsIterator.hasNext() ) {
- Map.Entry keyValuePair = (Map.Entry)(pairsIterator.next());
- ArrayList list = (ArrayList)(keyValuePair.getValue());
- list.clear();
- }
- super.clear();
- }
-
- public void putAll( Map mapToPut )
- {
- super.putAll( mapToPut );
- }
-
- public Collection values()
- {
- ArrayList returnList = new ArrayList( super.size() );
-
- Set pairs = super.entrySet();
- Iterator pairsIterator = pairs.iterator();
- while ( pairsIterator.hasNext() ) {
- Map.Entry keyValuePair = (Map.Entry)(pairsIterator.next());
- ArrayList list = (ArrayList)(keyValuePair.getValue());
-
- Object[] values = list.toArray();
- for( int ii=0; ii < values.length; ii++ ) {
- boolean successfulAdd = returnList.add( values[ii] );
- }
- }
- return returnList;
- }
-
- // FIXME:: do we need to implement this??
- // public boolean equals( Object obj ) {}
-
- // --------------- From Cloneable
- public Object clone()
- {
- MultiHashMap obj = (MultiHashMap)(super.clone());
- obj.mName = mName;
- return obj;
- }
-
-}