commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael Smith" <>
Subject [collections][PATCH] Various problems with AbstractBag
Date Fri, 01 Feb 2002 06:07:14 GMT
The following patch fixes the following problems with

 - Documentation does not specify exactly what a subcless needs to do to
extend AbstractBag to make a concrete subclass.

 - AbstractBag.add(Object,int) has two calls to getCount(o), when only
one is necessary.  This wastes a few cycles to perform method
invocations, a map lookup, a cast, and a few comparisons.

 - The equals(Object) method will incorrectly throw a
NullPointerException if a null value is passed.  The
Object.equals(Object) API specifies "For any non-null reference value x,
x.equals(null) should return false".

 - The equals(Object) method will only work if the object passed in
extends AbstractMap or implements Map.  Neither of these facts is
documented, and neither is correct.  The contract for
Object.equals(Object) states: "for any reference values x and y,
x.equals(y) should return true if and only if y.equals(x) returns true.
".  Returning true when the argument is a Map is incorrect since he
reverse (the map checking to see if its equal to the bag) will most
certainly be false.  The same can be said for AbstractMap.  A subclass
of AbstractMap may add extra data to be stored within the Bag that must
also be compared for them to be equal.  The reverse comparison
(specialized subclass equals basic abstract bap) will fail.  You can
read more about this in a three-year old, but still valid java world

 - if remove(Object,int) is called passing in 0 as the number to remove
and specifying an object that exists in th bag, true will be returned
from the method. Per the Bag API specification, true should only return
when an object is actually removed.  Since no objects are removed, false
should be returned instead. Additionally, if a negative number is
specified, not only is the object not removed, but object(s) are *added*
(well, in the sense that it is equivalent of calling add(o, -i))

 - the uniqueSet() method returns the set of unique objects, however the
set is modifiable.  If the underlying map implementation has the set
backed by the map (as per the map contract -- so it should), then
elements can be removed form the unique set and have them removed from
the underlying map as well.  This causes consistency problems with the
Bag since _total will then be incorrect.

 - in extractList(), getCount(current) is called each time through the
inner loop, adding lots of extra overhead.  Reversing the loop (starting
at the count and going down to 0) eliminates the excess overhead.

Note:  In line with "Elements of Java Style" rule number 1, I have
adhered to the style of the original, using 3 space indents instead of 2
(which I believe is the agreed upon indent spacing).  I've also left all
those ^M's in the file, even though they are completely annoying (I even
made sure my new lines of code had them to match the style of the rest).

Note:  I felt catching and fixing all of the above was enough to warrant
adding my name to the author's list.  If a committer disagrees, feel
free to remove it.


RCS file:
retrieving revision 1.1
diff -u -r1.1
che/commons/collections/	29 Aug 2001 15:28:07 -0000	1.1
che/commons/collections/	1 Feb 2002 05:50:03 -0000
@@ -63,6 +63,7 @@

 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.ConcurrentModificationException;
 import java.util.Iterator;
 import java.util.List;
@@ -73,8 +74,12 @@
  * This class provides a skeletal implementation of the {@link Bag}
  * interface to minimize the effort required for target
+ * Subclasses need only to call {@link #setMap(Map)} in their
+ * specifying a map instance that will be used to store the contents of
+ * the bag.
  * @author Chuck Burdick
+ * @author <a href="">Michael Smith</a>
 public abstract class AbstractBag implements Bag {
    private Map _map = null;
@@ -91,7 +96,7 @@
          int count = (i + getCount(o));
          _map.put(o, new Integer(count));
          _total += i;
-         return (getCount(o) == i);
+         return (count == i);
       } else {
          return false;
@@ -139,13 +144,9 @@

    public boolean equals(Object o) {
-      boolean result = false;
-      if (o instanceof AbstractBag) {
-         result = _map.equals(((AbstractBag)o).getMap());
-      } else if (o instanceof Map) {
-         result = _map.equals((Map)o);
-      }
-      return result;
+      return (o == this ||
+              (o != null && o.getClass().equals(this.getClass()) &&
+               ((AbstractBag)o)._map.equals(this._map)));

    public int hashCode() {
@@ -203,12 +204,15 @@
       boolean result = false;
       int count = getCount(o);
-      if (count > i) {
+      if (i <= 0) {
+         result = false;
+      } else if (count > i) {
          _map.put(o, new Integer(count - i));
          result = true;
          _total -= i;
-      } else {
-         result = uniqueSet().remove(o);
+      } else { // count > 0 && count <= i
+         // need to remove all
+         result = (_map.remove(o) != null);
          _total -= count;
       return result;
@@ -274,7 +278,7 @@

    public Set uniqueSet() {
-      return _map.keySet();
+      return Collections.unmodifiableSet(_map.keySet());

    public int size() {
@@ -316,7 +320,7 @@
       Iterator i = uniqueSet().iterator();
       while (i.hasNext()) {
          Object current =;
-         for (int index = 0; index < getCount(current); index++) {
+         for (int index = getCount(current); index > 0; index--) {

To unsubscribe, e-mail:   <>
For additional commands, e-mail: <>

View raw message