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 apa...@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 apa...@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 apa...@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:f...@apache.org";>Federico Barbieri</a> - * @author <a href="mailto:dona...@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 apa...@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:jstrac...@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; - } - -}
