You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by sc...@apache.org on 2003/05/16 16:24:55 UTC
cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections DefaultMapEntry.java DoubleOrderedMap.java DefaultMapBag.java
scolebourne 2003/05/16 07:24:55
Modified: collections/src/java/org/apache/commons/collections
DefaultMapEntry.java DoubleOrderedMap.java
DefaultMapBag.java
Log:
Update licence and javadoc
Revision Changes Path
1.9 +42 -41 jakarta-commons/collections/src/java/org/apache/commons/collections/DefaultMapEntry.java
Index: DefaultMapEntry.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/DefaultMapEntry.java,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -r1.8 -r1.9
--- DefaultMapEntry.java 15 Aug 2002 20:04:31 -0000 1.8
+++ DefaultMapEntry.java 16 May 2003 14:24:54 -0000 1.9
@@ -1,13 +1,10 @@
/*
* $Header$
- * $Revision$
- * $Date$
- *
* ====================================================================
*
* The Apache Software License, Version 1.1
*
- * Copyright (c) 1999-2002 The Apache Software Foundation. All rights
+ * Copyright (c) 2001-2003 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -23,11 +20,11 @@
* distribution.
*
* 3. The end-user documentation included with the redistribution, if
- * any, must include the following acknowlegement:
+ * any, must include the following acknowledgment:
* "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.
+ * Alternately, this acknowledgment may appear in the software itself,
+ * if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "The Jakarta Project", "Commons", and "Apache Software
* Foundation" must not be used to endorse or promote products derived
@@ -36,7 +33,7 @@
*
* 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.
+ * permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
@@ -62,31 +59,35 @@
import java.util.Map;
-/** A default implementation of {@link java.util.Map.Entry}
- *
- * @since 1.0
- * @author <a href="mailto:jstrachan@apache.org">James Strachan</a>
- * @author <a href="mailto:mas@apache.org">Michael A. Smith</a>
- */
-
+/**
+ * A default implementation of {@link java.util.Map.Entry}
+ *
+ * @since Commons Collections 1.0
+ * @version $Revision$ $Date$
+ *
+ * @author <a href="mailto:jstrachan@apache.org">James Strachan</a>
+ * @author <a href="mailto:mas@apache.org">Michael A. Smith</a>
+ */
public class DefaultMapEntry implements Map.Entry {
+ /** The key */
private Object key;
+ /** The value */
private Object value;
/**
- * Constructs a new <Code>DefaultMapEntry</Code> with a null key
- * and null value.
+ * Constructs a new <Code>DefaultMapEntry</Code> with a null key
+ * and null value.
*/
public DefaultMapEntry() {
}
/**
- * Constructs a new <Code>DefaultMapEntry</Code> with the given
- * key and given value.
+ * Constructs a new <Code>DefaultMapEntry</Code> with the given
+ * key and given value.
*
- * @param key the key for the entry, may be null
- * @param value the value for the entyr, may be null
+ * @param key the key for the entry, may be null
+ * @param value the value for the entyr, may be null
*/
public DefaultMapEntry(Object key, Object value) {
this.key = key;
@@ -94,9 +95,9 @@
}
/**
- * Implemented per API documentation of
- * {@link java.util.Map.Entry#equals(Object)}
- **/
+ * Implemented per API documentation of
+ * {@link java.util.Map.Entry#equals(Object)}
+ */
public boolean equals(Object o) {
if( o == null ) return false;
if( o == this ) return true;
@@ -112,9 +113,9 @@
/**
- * Implemented per API documentation of
- * {@link java.util.Map.Entry#hashCode()}
- **/
+ * Implemented per API documentation of
+ * {@link java.util.Map.Entry#hashCode()}
+ */
public int hashCode() {
return ( ( getKey() == null ? 0 : getKey().hashCode() ) ^
( getValue() == null ? 0 : getValue().hashCode() ) );
@@ -126,19 +127,18 @@
//-------------------------------------------------------------------------
/**
- * Returns the key.
+ * Returns the key.
*
- * @return the key
+ * @return the key
*/
public Object getKey() {
return key;
}
-
/**
- * Returns the value.
+ * Returns the value.
*
- * @return the value
+ * @return the value
*/
public Object getValue() {
return value;
@@ -148,20 +148,21 @@
//-------------------------------------------------------------------------
/**
- * Sets the key. This method does not modify any map.
+ * Sets the key. This method does not modify any map.
*
- * @param key the new key
+ * @param key the new key
*/
public void setKey(Object key) {
this.key = key;
}
- /** Note that this method only sets the local reference inside this object and
- * does not modify the original Map.
- *
- * @return the old value of the value
- * @param value the new value
- */
+ /**
+ * Note that this method only sets the local reference inside this object and
+ * does not modify the original Map.
+ *
+ * @return the old value of the value
+ * @param value the new value
+ */
public Object setValue(Object value) {
Object answer = this.value;
this.value = value;
1.4 +130 -157 jakarta-commons/collections/src/java/org/apache/commons/collections/DoubleOrderedMap.java
Index: DoubleOrderedMap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/DoubleOrderedMap.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- DoubleOrderedMap.java 12 Oct 2002 22:15:18 -0000 1.3
+++ DoubleOrderedMap.java 16 May 2003 14:24:54 -0000 1.4
@@ -1,13 +1,10 @@
/*
* $Header$
- * $Revision$
- * $Date$
- *
* ====================================================================
*
* The Apache Software License, Version 1.1
*
- * Copyright (c) 1999-2002 The Apache Software Foundation. All rights
+ * Copyright (c) 2002-2003 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -23,11 +20,11 @@
* distribution.
*
* 3. The end-user documentation included with the redistribution, if
- * any, must include the following acknowlegement:
+ * any, must include the following acknowledgment:
* "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.
+ * Alternately, this acknowledgment may appear in the software itself,
+ * if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "The Jakarta Project", "Commons", and "Apache Software
* Foundation" must not be used to endorse or promote products derived
@@ -36,7 +33,7 @@
*
* 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.
+ * permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
@@ -58,11 +55,8 @@
* <http://www.apache.org/>.
*
*/
-
package org.apache.commons.collections;
-
-
import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
@@ -73,105 +67,99 @@
import java.util.NoSuchElementException;
import java.util.Set;
-
/**
-* 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>
-*
-* @since 2.0
-* @author Marc Johnson (marcj at users dot sourceforge dot net)
-*/
-
-// final for performance
+ * 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>
+ *
+ * @since Commons Collections 2.0
+ * @version $Revision$ $Date$
+ *
+ * @author Marc Johnson (marcj at users dot sourceforge dot net)
+ */
public final class DoubleOrderedMap extends AbstractMap {
+// final for performance
- 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"
-};
+ 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" };
+
+ 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 };
/**
* Construct a new DoubleOrderedMap
*/
- public DoubleOrderedMap() {}
+ public DoubleOrderedMap() {
+ }
/**
* Constructs a new DoubleOrderedMap from an existing Map, with keys and
@@ -179,14 +167,14 @@
*
* @param map the map whose mappings are to be placed in this map.
*
- * @exception ClassCastException if the keys in the map are not
+ * @throws 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
+ * @throws NullPointerException if any key or value in the map
* is null
- * @exception IllegalArgumentException if there are duplicate keys
+ * @throws IllegalArgumentException if there are duplicate keys
* or duplicate values in the
* map
*/
@@ -205,9 +193,9 @@
* @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
+ * @throws ClassCastException if the value is of an
* inappropriate type for this map.
- * @exception NullPointerException if the value is null
+ * @throws NullPointerException if the value is null
*/
public Object getKeyForValue(final Object value)
throws ClassCastException, NullPointerException {
@@ -847,8 +835,7 @@
* @param insertedNode the node to be inserted
* @param index KEY or VALUE
*/
- private void doRedBlackInsert(final Node insertedNode, final int index)
-{
+ private void doRedBlackInsert(final Node insertedNode, final int index) {
Node currentNode = insertedNode;
@@ -904,8 +891,7 @@
makeRed(getGrandParent(currentNode, index), index);
if (getGrandParent(currentNode, index) != null) {
- rotateLeft(getGrandParent(currentNode, index),
-index);
+ rotateLeft(getGrandParent(currentNode, index), index);
}
}
}
@@ -943,11 +929,9 @@
rootNode[index] = replacement;
} else if (deletedNode
== deletedNode.getParent(index).getLeft(index)) {
- deletedNode.getParent(index).setLeft(replacement,
-index);
+ deletedNode.getParent(index).setLeft(replacement, index);
} else {
- deletedNode.getParent(index).setRight(replacement,
-index);
+ deletedNode.getParent(index).setRight(replacement, index);
}
deletedNode.setLeft(null, index);
@@ -975,8 +959,7 @@
if (deletedNode
== deletedNode.getParent(index)
.getLeft(index)) {
- deletedNode.getParent(index).setLeft(null,
-index);
+ deletedNode.getParent(index).setLeft(null, index);
} else {
deletedNode.getParent(index).setRight(null,
index);
@@ -1016,9 +999,7 @@
makeRed(getParent(currentNode, index), index);
rotateLeft(getParent(currentNode, index), index);
- siblingNode = getRightChild(getParent(currentNode,
-index),
- index);
+ siblingNode = getRightChild(getParent(currentNode, index), index);
}
if (isBlack(getLeftChild(siblingNode, index), index)
@@ -1034,8 +1015,7 @@
rotateRight(siblingNode, index);
siblingNode =
- getRightChild(getParent(currentNode, index),
- index);
+ getRightChild(getParent(currentNode, index), index);
}
copyColor(getParent(currentNode, index), siblingNode,
@@ -1047,23 +1027,18 @@
currentNode = rootNode[index];
}
} else {
- Node siblingNode = getLeftChild(getParent(currentNode,
-index),
- index);
+ 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);
+ siblingNode = getLeftChild(getParent(currentNode, index), index);
}
if (isBlack(getRightChild(siblingNode, index), index)
- && isBlack(getLeftChild(siblingNode, index), index))
-{
+ && isBlack(getLeftChild(siblingNode, index), index)) {
makeRed(siblingNode, index);
currentNode = getParent(currentNode, index);
@@ -1074,8 +1049,7 @@
rotateLeft(siblingNode, index);
siblingNode =
- getLeftChild(getParent(currentNode, index),
- index);
+ getLeftChild(getParent(currentNode, index), index);
}
copyColor(getParent(currentNode, index), siblingNode,
@@ -1203,8 +1177,8 @@
* @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
+ * @throws NullPointerException if o is null
+ * @throws ClassCastException if o is not Comparable
*/
private static void checkNonNullComparable(final Object o,
final int index) {
@@ -1225,8 +1199,8 @@
*
* @param key the key to be checked
*
- * @exception NullPointerException if key is null
- * @exception ClassCastException if key is not Comparable
+ * @throws NullPointerException if key is null
+ * @throws ClassCastException if key is not Comparable
*/
private static void checkKey(final Object key) {
checkNonNullComparable(key, KEY);
@@ -1237,8 +1211,8 @@
*
* @param value the value to be checked
*
- * @exception NullPointerException if value is null
- * @exception ClassCastException if value is not Comparable
+ * @throws NullPointerException if value is null
+ * @throws ClassCastException if value is not Comparable
*/
private static void checkValue(final Object value) {
checkNonNullComparable(value, VALUE);
@@ -1251,8 +1225,8 @@
* @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
+ * @throws NullPointerException if key or value is null
+ * @throws ClassCastException if key or value is not Comparable
*/
private static void checkKeyAndValue(final Object key,
final Object value) {
@@ -1294,7 +1268,7 @@
*
* @param newNode the node to be inserted
*
- * @exception IllegalArgumentException if the node already exists
+ * @throws IllegalArgumentException if the node already exists
* in the value mapping
*/
private void insertValue(final Node newNode)
@@ -1355,9 +1329,9 @@
* @return true if this map contains a mapping for the specified
* key.
*
- * @exception ClassCastException if the key is of an inappropriate
+ * @throws ClassCastException if the key is of an inappropriate
* type for this map.
- * @exception NullPointerException if the key is null
+ * @throws NullPointerException if the key is null
*/
public boolean containsKey(final Object key)
throws ClassCastException, NullPointerException {
@@ -1392,9 +1366,9 @@
* @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
+ * @throws ClassCastException if the key is of an inappropriate
* type for this map.
- * @exception NullPointerException if the key is null
+ * @throws NullPointerException if the key is null
*/
public Object get(final Object key)
throws ClassCastException, NullPointerException {
@@ -1411,12 +1385,12 @@
*
* @return null
*
- * @exception ClassCastException if the class of the specified key
+ * @throws 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
+ * @throws NullPointerException if the specified key or value
* is null
- * @exception IllegalArgumentException if the key duplicates an
+ * @throws IllegalArgumentException if the key duplicates an
* existing key, or if the
* value duplicates an
* existing value
@@ -1680,8 +1654,7 @@
Node node = lookup((Comparable) entry.getKey(),
KEY);
- if ((node != null) && node.getData(VALUE).equals(value))
-{
+ if ((node != null) && node.getData(VALUE).equals(value)) {
doRedBlackDelete(node);
return true;
@@ -1743,9 +1716,9 @@
/**
* @return the next element in the iteration.
*
- * @exception NoSuchElementException if iteration has no more
+ * @throws NoSuchElementException if iteration has no more
* elements.
- * @exception ConcurrentModificationException if the
+ * @throws ConcurrentModificationException if the
* DoubleOrderedMap is
* modified behind
* the iterator's
@@ -1777,12 +1750,12 @@
* the iteration is in progress in any way other than by
* calling this method.
*
- * @exception IllegalStateException if the next method has not
+ * @throws 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
+ * @throws ConcurrentModificationException if the
* DoubleOrderedMap is
* modified behind
* the iterator's
@@ -2000,7 +1973,7 @@
*
* @return does not return
*
- * @exception UnsupportedOperationException
+ * @throws UnsupportedOperationException
*/
public Object setValue(Object ignored)
throws UnsupportedOperationException {
1.8 +388 -359 jakarta-commons/collections/src/java/org/apache/commons/collections/DefaultMapBag.java
Index: DefaultMapBag.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/DefaultMapBag.java,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- DefaultMapBag.java 13 Jan 2003 23:54:38 -0000 1.7
+++ DefaultMapBag.java 16 May 2003 14:24:55 -0000 1.8
@@ -1,9 +1,10 @@
/*
* $Header$
* ====================================================================
+ *
* The Apache Software License, Version 1.1
*
- * Copyright (c) 1999-2003 The Apache Software Foundation. All rights
+ * Copyright (c) 2002-2003 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -54,7 +55,6 @@
* <http://www.apache.org/>.
*
*/
-
package org.apache.commons.collections;
import java.util.ArrayList;
@@ -72,383 +72,412 @@
* Subclasses need only to call <code>setMap(Map)</code> in their constructor
* (or invoke the {@link #DefaultMapBag(java.util.Map) Map-constructor})
* specifying a map instance that will be used to store the contents of
- * the bag.<P>
- *
+ * the bag.
+ * <p>
* The map will be used to map bag elements to a number; the number represents
- * the number of occurrences of that element in the bag.<P>
+ * the number of occurrences of that element in the bag.
*
* @since Commons Collections 2.0
* @version $Revision$ $Date$
+ *
* @author Chuck Burdick
* @author <a href="mailto:mas@apache.org">Michael A. Smith</a>
- **/
+ * @author Stephen Colebourne
+ */
public abstract class DefaultMapBag implements Bag {
- private Map _map = null;
- private int _total = 0;
- private int _mods = 0;
-
-
- /**
- * No-argument constructor.
- * Subclasses should invoke <code>setMap(Map)</code> in
- * their constructors.
- */
- public DefaultMapBag() {
- }
-
- /**
- * @since Commons Collections 2.2
- */
- public DefaultMapBag(Map map) {
- setMap(map);
- }
-
- /**
- * Adds a new element to the bag by incrementing its count in the
- * underlying map.
- *
- * @see Bag#add(Object)
- */
- public boolean add(Object o) {
- return add(o, 1);
- }
-
- /**
- * Adds a new element to the bag by incrementing its count in the map.
- *
- * @see Bag#add(Object, int)
- */
- public boolean add(Object o, int i) {
- _mods++;
- if (i > 0) {
- int count = (i + getCount(o));
- _map.put(o, new Integer(count));
- _total += i;
- return (count == i);
- } else {
- return false;
- }
- }
-
- /**
- * Invokes {@link #add(Object)} for each element in the given collection.
- *
- * @see Bag#addAll(Collection)
- */
- public boolean addAll(Collection c) {
- boolean changed = false;
- Iterator i = c.iterator();
- while (i.hasNext()) {
- boolean added = add(i.next());
- changed = changed || added;
- }
- return changed;
- }
-
-
- /**
- * Clears the bag by clearing the underlying map.
- */
- public void clear() {
- _mods++;
- _map.clear();
- _total = 0;
- }
-
- /**
- * Determines if the bag contains the given element by checking if the
- * underlying map contains the element as a key.
- *
- * @return true if the bag contains the given element
- */
- public boolean contains(Object o) {
- return _map.containsKey(o);
- }
-
- public boolean containsAll(Collection c) {
- return containsAll(new HashBag(c));
- }
-
- /**
- * Returns <code>true</code> if the bag contains all elements in
- * the given collection, respecting cardinality.
- * @see #containsAll(Collection)
- **/
- public boolean containsAll(Bag other) {
- boolean result = true;
- Iterator i = other.uniqueSet().iterator();
- while (i.hasNext()) {
- Object current = i.next();
- boolean contains =
- getCount(current) >= ((Bag)other).getCount(current);
- result = result && contains;
- }
- return result;
- }
-
- /**
- * Returns true if the given object is not null, has the precise type
- * of this bag, and contains the same number of occurrences of all the
- * same elements.
- *
- * @param o the object to test for equality
- * @return true if that object equals this bag
- */
- public boolean equals(Object o) {
- return (o == this ||
- (o != null && o.getClass().equals(this.getClass()) &&
- ((DefaultMapBag)o)._map.equals(this._map)));
- }
-
- /**
- * Returns the hash code of the underlying map.
- *
- * @return the hash code of the underlying map
- */
- public int hashCode() {
- return _map.hashCode();
- }
-
- /**
- * Returns true if the underlying map is empty.
- *
- * @return true if there are no elements in this bag
- */
- public boolean isEmpty() {
- return _map.isEmpty();
- }
-
- public Iterator iterator() {
- return new BagIterator(this, extractList().iterator());
- }
-
- private class BagIterator implements Iterator {
- private DefaultMapBag _parent = null;
- private Iterator _support = null;
- private Object _current = null;
- private int _mods = 0;
-
- public BagIterator(DefaultMapBag parent, Iterator support) {
- _parent = parent;
- _support = support;
- _current = null;
- _mods = parent.modCount();
- }
-
- public boolean hasNext() {
- return _support.hasNext();
- }
-
- public Object next() {
- if (_parent.modCount() != _mods) {
- throw new ConcurrentModificationException();
- }
- _current = _support.next();
- return _current;
- }
-
- public void remove() {
- if (_parent.modCount() != _mods) {
- throw new ConcurrentModificationException();
- }
- _support.remove();
- _parent.remove(_current, 1);
- _mods++;
- }
- }
-
- public boolean remove (Object o) {
- return remove(o, getCount(o));
- }
-
- public boolean remove (Object o, int i) {
- _mods++;
- boolean result = false;
- int count = getCount(o);
- if (i <= 0) {
- result = false;
- } else if (count > i) {
- _map.put(o, new Integer(count - i));
- result = true;
- _total -= i;
- } else { // count > 0 && count <= i
- // need to remove all
- result = (_map.remove(o) != null);
- _total -= count;
- }
- return result;
- }
-
- public boolean removeAll(Collection c) {
- boolean result = false;
- if (c != null) {
- Iterator i = c.iterator();
- while (i.hasNext()) {
- boolean changed = remove(i.next(), 1);
- result = result || changed;
- }
- }
- return result;
- }
-
- /**
- * Remove any members of the bag that are not in the given
- * bag, respecting cardinality.
- *
- * @return true if this call changed the collection
- */
- public boolean retainAll(Collection c) {
- return retainAll(new HashBag(c));
- }
-
- /**
- * Remove any members of the bag that are not in the given
- * bag, respecting cardinality.
- * @see #retainAll(Collection)
- * @return <code>true</code> if this call changed the collection
- **/
- public boolean retainAll(Bag other) {
- boolean result = false;
- Bag excess = new HashBag();
- Iterator i = uniqueSet().iterator();
- while (i.hasNext()) {
- Object current = i.next();
- int myCount = getCount(current);
- int otherCount = other.getCount(current);
- if (1 <= otherCount && otherCount <= myCount) {
- excess.add(current, myCount - otherCount);
- } else {
- excess.add(current, myCount);
- }
- }
- if (!excess.isEmpty()) {
- result = removeAll(excess);
- }
- return result;
- }
-
- /**
- * Returns an array of all of this bag's elements.
- *
- * @return an array of all of this bag's elements
- */
- public Object[] toArray() {
- return extractList().toArray();
- }
-
- /**
- * Returns an array of all of this bag's elements.
- *
- * @param a the array to populate
- * @return an array of all of this bag's elements
- */
- public Object[] toArray(Object[] a) {
- return extractList().toArray(a);
- }
-
- /**
- * Returns the number of occurrence of the given element in this bag
- * by looking up its count in the underlying map.
- *
- * @see Bag#getCount(Object)
- */
- public int getCount(Object o) {
- int result = 0;
- Integer count = MapUtils.getInteger(_map, o);
- if (count != null) {
- result = count.intValue();
- }
- return result;
- }
-
- /**
- * Returns an unmodifiable view of the underlying map's key set.
- *
- * @return the set of unique elements in this bag
- */
- public Set uniqueSet() {
- return Collections.unmodifiableSet(_map.keySet());
- }
-
- /**
- * Returns the number of elements in this bag.
- *
- * @return the number of elements in this bag
- */
- public int size() {
- return _total;
- }
-
- /**
- * Actually walks the bag to make sure the count is correct and
- * resets the running total
- **/
- protected int calcTotalSize() {
- _total = extractList().size();
- return _total;
- }
-
- /**
- * Utility method for implementations to set the map that backs
- * this bag. Not intended for interactive use outside of
- * subclasses.
- **/
- protected void setMap(Map m) {
- _map = m;
- }
-
- /**
- * Utility method for implementations to access the map that backs
- * this bag. Not intended for interactive use outside of
- * subclasses.
- **/
- protected Map getMap() {
- return _map;
- }
-
- /**
- * Create a list for use in iteration, etc.
- **/
- private List extractList() {
- List result = new ArrayList();
- Iterator i = uniqueSet().iterator();
- while (i.hasNext()) {
- Object current = i.next();
- for (int index = getCount(current); index > 0; index--) {
- result.add(current);
- }
- }
- return result;
- }
-
- /**
- * Return number of modifications for iterator
- **/
- private int modCount() {
- return _mods;
- }
+ private Map _map = null;
+ private int _total = 0;
+ private int _mods = 0;
+
+ /**
+ * No-argument constructor.
+ * Subclasses should invoke <code>setMap(Map)</code> in
+ * their constructors.
+ */
+ public DefaultMapBag() {
+ }
+
+ /**
+ * Constructor that assigns the specified Map as the backing store.
+ * The map must be empty.
+ *
+ * @param map the map to assign
+ */
+ protected DefaultMapBag(Map map) {
+ setMap(map);
+ }
+
+ /**
+ * Adds a new element to the bag by incrementing its count in the
+ * underlying map.
+ *
+ * @param object the object to add
+ * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
+ */
+ public boolean add(Object object) {
+ return add(object, 1);
+ }
+
+ /**
+ * Adds a new element to the bag by incrementing its count in the map.
+ *
+ * @param object the object to search for
+ * @param nCopies the number of copies to add
+ * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
+ */
+ public boolean add(Object object, int nCopies) {
+ _mods++;
+ if (nCopies > 0) {
+ int count = (nCopies + getCount(object));
+ _map.put(object, new Integer(count));
+ _total += nCopies;
+ return (count == nCopies);
+ } else {
+ return false;
+ }
+ }
+
+ /**
+ * Invokes {@link #add(Object)} for each element in the given collection.
+ *
+ * @param coll the collection to add
+ * @return <code>true</code> if this call changed the bag
+ */
+ public boolean addAll(Collection coll) {
+ boolean changed = false;
+ Iterator i = coll.iterator();
+ while (i.hasNext()) {
+ boolean added = add(i.next());
+ changed = changed || added;
+ }
+ return changed;
+ }
+
+ /**
+ * Clears the bag by clearing the underlying map.
+ */
+ public void clear() {
+ _mods++;
+ _map.clear();
+ _total = 0;
+ }
+
+ /**
+ * Determines if the bag contains the given element by checking if the
+ * underlying map contains the element as a key.
+ *
+ * @param object the object to search for
+ * @return true if the bag contains the given element
+ */
+ public boolean contains(Object object) {
+ return _map.containsKey(object);
+ }
+
+ /**
+ * Determines if the bag contains the given elements.
+ *
+ * @param coll the collection to check against
+ * @return <code>true</code> if the Bag contains all the collection
+ */
+ public boolean containsAll(Collection coll) {
+ return containsAll(new HashBag(coll));
+ }
/**
- * Implement a toString() method suitable for debugging
- **/
+ * Returns <code>true</code> if the bag contains all elements in
+ * the given collection, respecting cardinality.
+ *
+ * @param other the bag to check against
+ * @return <code>true</code> if the Bag contains all the collection
+ */
+ public boolean containsAll(Bag other) {
+ boolean result = true;
+ Iterator i = other.uniqueSet().iterator();
+ while (i.hasNext()) {
+ Object current = i.next();
+ boolean contains = getCount(current) >= ((Bag) other).getCount(current);
+ result = result && contains;
+ }
+ return result;
+ }
+
+ /**
+ * Returns true if the given object is not null, has the precise type
+ * of this bag, and contains the same number of occurrences of all the
+ * same elements.
+ *
+ * @param object the object to test for equality
+ * @return true if that object equals this bag
+ */
+ public boolean equals(Object object) {
+ if (object == this) {
+ return true;
+ }
+ return (object != null &&
+ object.getClass().equals(this.getClass()) &&
+ ((DefaultMapBag) object)._map.equals(this._map));
+ }
+
+ /**
+ * Returns the hash code of the underlying map.
+ *
+ * @return the hash code of the underlying map
+ */
+ public int hashCode() {
+ return _map.hashCode();
+ }
+
+ /**
+ * Returns true if the underlying map is empty.
+ *
+ * @return true if there are no elements in this bag
+ */
+ public boolean isEmpty() {
+ return _map.isEmpty();
+ }
+
+ public Iterator iterator() {
+ return new BagIterator(this, extractList().iterator());
+ }
+
+ private class BagIterator implements Iterator {
+ private DefaultMapBag _parent = null;
+ private Iterator _support = null;
+ private Object _current = null;
+ private int _mods = 0;
+
+ public BagIterator(DefaultMapBag parent, Iterator support) {
+ _parent = parent;
+ _support = support;
+ _current = null;
+ _mods = parent.modCount();
+ }
+
+ public boolean hasNext() {
+ return _support.hasNext();
+ }
+
+ public Object next() {
+ if (_parent.modCount() != _mods) {
+ throw new ConcurrentModificationException();
+ }
+ _current = _support.next();
+ return _current;
+ }
+
+ public void remove() {
+ if (_parent.modCount() != _mods) {
+ throw new ConcurrentModificationException();
+ }
+ _support.remove();
+ _parent.remove(_current, 1);
+ _mods++;
+ }
+ }
+
+ public boolean remove(Object object) {
+ return remove(object, getCount(object));
+ }
+
+ public boolean remove(Object object, int nCopies) {
+ _mods++;
+ boolean result = false;
+ int count = getCount(object);
+ if (nCopies <= 0) {
+ result = false;
+ } else if (count > nCopies) {
+ _map.put(object, new Integer(count - nCopies));
+ result = true;
+ _total -= nCopies;
+ } else { // count > 0 && count <= i
+ // need to remove all
+ result = (_map.remove(object) != null);
+ _total -= count;
+ }
+ return result;
+ }
+
+ public boolean removeAll(Collection coll) {
+ boolean result = false;
+ if (coll != null) {
+ Iterator i = coll.iterator();
+ while (i.hasNext()) {
+ boolean changed = remove(i.next(), 1);
+ result = result || changed;
+ }
+ }
+ return result;
+ }
+
+ /**
+ * Remove any members of the bag that are not in the given
+ * bag, respecting cardinality.
+ *
+ * @param coll the collection to retain
+ * @return true if this call changed the collection
+ */
+ public boolean retainAll(Collection coll) {
+ return retainAll(new HashBag(coll));
+ }
+
+ /**
+ * Remove any members of the bag that are not in the given
+ * bag, respecting cardinality.
+ * @see #retainAll(Collection)
+ *
+ * @param other the bag to retain
+ * @return <code>true</code> if this call changed the collection
+ */
+ public boolean retainAll(Bag other) {
+ boolean result = false;
+ Bag excess = new HashBag();
+ Iterator i = uniqueSet().iterator();
+ while (i.hasNext()) {
+ Object current = i.next();
+ int myCount = getCount(current);
+ int otherCount = other.getCount(current);
+ if (1 <= otherCount && otherCount <= myCount) {
+ excess.add(current, myCount - otherCount);
+ } else {
+ excess.add(current, myCount);
+ }
+ }
+ if (!excess.isEmpty()) {
+ result = removeAll(excess);
+ }
+ return result;
+ }
+
+ /**
+ * Returns an array of all of this bag's elements.
+ *
+ * @return an array of all of this bag's elements
+ */
+ public Object[] toArray() {
+ return extractList().toArray();
+ }
+
+ /**
+ * Returns an array of all of this bag's elements.
+ *
+ * @param array the array to populate
+ * @return an array of all of this bag's elements
+ */
+ public Object[] toArray(Object[] array) {
+ return extractList().toArray(array);
+ }
+
+ /**
+ * Returns the number of occurrence of the given element in this bag
+ * by looking up its count in the underlying map.
+ *
+ * @param object the object to search for
+ * @return the number of occurrences of the object, zero if not found
+ */
+ public int getCount(Object object) {
+ int result = 0;
+ Integer count = MapUtils.getInteger(_map, object);
+ if (count != null) {
+ result = count.intValue();
+ }
+ return result;
+ }
+
+ /**
+ * Returns an unmodifiable view of the underlying map's key set.
+ *
+ * @return the set of unique elements in this bag
+ */
+ public Set uniqueSet() {
+ return Collections.unmodifiableSet(_map.keySet());
+ }
+
+ /**
+ * Returns the number of elements in this bag.
+ *
+ * @return the number of elements in this bag
+ */
+ public int size() {
+ return _total;
+ }
+
+ /**
+ * Actually walks the bag to make sure the count is correct and
+ * resets the running total
+ *
+ * @return the current total size
+ */
+ protected int calcTotalSize() {
+ _total = extractList().size();
+ return _total;
+ }
+
+ /**
+ * Utility method for implementations to set the map that backs
+ * this bag. Not intended for interactive use outside of
+ * subclasses.
+ */
+ protected void setMap(Map map) {
+ if (map == null || map.isEmpty() == false) {
+ throw new IllegalArgumentException("The map must be non-null and empty");
+ }
+ _map = map;
+ }
+
+ /**
+ * Utility method for implementations to access the map that backs
+ * this bag. Not intended for interactive use outside of
+ * subclasses.
+ */
+ protected Map getMap() {
+ return _map;
+ }
+
+ /**
+ * Create a list for use in iteration, etc.
+ */
+ private List extractList() {
+ List result = new ArrayList();
+ Iterator i = uniqueSet().iterator();
+ while (i.hasNext()) {
+ Object current = i.next();
+ for (int index = getCount(current); index > 0; index--) {
+ result.add(current);
+ }
+ }
+ return result;
+ }
+
+ /**
+ * Return number of modifications for iterator.
+ *
+ * @return the modification count
+ */
+ private int modCount() {
+ return _mods;
+ }
+
+ /**
+ * Implement a toString() method suitable for debugging.
+ *
+ * @return a debugging toString
+ */
public String toString() {
StringBuffer buf = new StringBuffer();
buf.append("[");
Iterator i = uniqueSet().iterator();
- while(i.hasNext()) {
+ while (i.hasNext()) {
Object current = i.next();
int count = getCount(current);
buf.append(count);
buf.append(":");
buf.append(current);
- if(i.hasNext()) {
+ if (i.hasNext()) {
buf.append(",");
}
}
buf.append("]");
return buf.toString();
}
+
}
-
-
-
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org