Return-Path: Delivered-To: apmail-jakarta-commons-dev-archive@apache.org Received: (qmail 41011 invoked from network); 10 Feb 2002 05:53:21 -0000 Received: from unknown (HELO nagoya.betaversion.org) (192.18.49.131) by daedalus.apache.org with SMTP; 10 Feb 2002 05:53:21 -0000 Received: (qmail 13946 invoked by uid 97); 10 Feb 2002 05:53:25 -0000 Delivered-To: qmlist-jakarta-archive-commons-dev@jakarta.apache.org Received: (qmail 13926 invoked by uid 97); 10 Feb 2002 05:53:25 -0000 Mailing-List: contact commons-dev-help@jakarta.apache.org; run by ezmlm Precedence: bulk List-Unsubscribe: List-Subscribe: List-Help: List-Post: List-Id: "Jakarta Commons Developers List" Reply-To: "Jakarta Commons Developers List" Delivered-To: mailing list commons-dev@jakarta.apache.org Received: (qmail 13915 invoked from network); 10 Feb 2002 05:53:24 -0000 From: "Michael Smith" To: "Jakarta Commons Developers List" Subject: [collections][PATCH] Various problems with AbstractBag Date: Sun, 10 Feb 2002 00:53:23 -0500 Message-ID: MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_NextPart_000_0008_01C1B1CD.5722E040" X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0) Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N ------=_NextPart_000_0008_01C1B1CD.5722E040 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit The following patch fixes the following problems with org.apache.commons.collections.AbstractBag: - 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 article: http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html - 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. Regards, michael ------=_NextPart_000_0008_01C1B1CD.5722E040 Content-Type: application/octet-stream; name="AbstractBag-20020209.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="AbstractBag-20020209.patch" Index: src/java/org/apache/commons/collections/AbstractBag.java =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D RCS file: = /home/cvspublic/jakarta-commons/collections/src/java/org/apache/commons/c= ollections/AbstractBag.java,v retrieving revision 1.1 diff -u -r1.1 AbstractBag.java --- src/java/org/apache/commons/collections/AbstractBag.java 29 Aug 2001 = 15:28:07 -0000 1.1 +++ src/java/org/apache/commons/collections/AbstractBag.java 10 Feb 2002 = 05:16:58 -0000 @@ -63,6 +63,7 @@ =20 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 = implementations. + * Subclasses need only to call {@link #setMap(Map)} in their = constructor=20 + * specifying a map instance that will be used to store the contents of = + * the bag.=20 * * @author Chuck Burdick + * @author Michael Smith **/ public abstract class AbstractBag implements Bag { private Map _map =3D null; @@ -91,7 +96,7 @@ int count =3D (i + getCount(o)); _map.put(o, new Integer(count)); _total +=3D i; - return (getCount(o) =3D=3D i); + return (count =3D=3D i); } else { return false; } @@ -139,13 +144,9 @@ } =20 public boolean equals(Object o) { - boolean result =3D false; - if (o instanceof AbstractBag) { - result =3D _map.equals(((AbstractBag)o).getMap()); - } else if (o instanceof Map) { - result =3D _map.equals((Map)o); - } - return result; + return (o =3D=3D this ||=20 + (o !=3D null && o.getClass().equals(this.getClass()) && + ((AbstractBag)o)._map.equals(this._map))); } =20 public int hashCode() { @@ -203,12 +204,15 @@ _mods++; boolean result =3D false; int count =3D getCount(o); - if (count > i) { + if (i <=3D 0) { + result =3D false; + } else if (count > i) { _map.put(o, new Integer(count - i)); result =3D true; _total -=3D i; - } else { - result =3D uniqueSet().remove(o); + } else { // count > 0 && count <=3D i =20 + // need to remove all + result =3D (_map.remove(o) !=3D null); _total -=3D count; } return result; @@ -274,7 +278,7 @@ } =20 public Set uniqueSet() { - return _map.keySet(); + return Collections.unmodifiableSet(_map.keySet()); } =20 public int size() { @@ -316,7 +320,7 @@ Iterator i =3D uniqueSet().iterator(); while (i.hasNext()) { Object current =3D i.next(); - for (int index =3D 0; index < getCount(current); index++) { + for (int index =3D getCount(current); index > 0; index--) { result.add(current); } } ------=_NextPart_000_0008_01C1B1CD.5722E040 Content-Type: text/plain; charset=us-ascii -- To unsubscribe, e-mail: For additional commands, e-mail: ------=_NextPart_000_0008_01C1B1CD.5722E040--