On Wednesday, November 5, 2003, at 12:10 AM, Phil Steitz wrote:
I think that that javadoc for remove is incorrect when it says:
"This implementation calls <code>remove()</code> on each collection." It stops when it finds the element to be removed. The contract needs to be made more explicit here. It might actually be better to push remove() into the Mutator, since one could argue that the current "remove strategy" (kill the first one found) is no less arbitrary than a default "add" strategy that just adds to the last collection. Might be better to make this pluggable like add.
To quote the Collection API doc:
<quote>
Removes a single instance of the specified element from this collection, if it is present (optional operation). More formally, removes an element e such that (o==null ? e==null : o.equals(e)), if this collection contains one or more such elements.
</quote>
I agree that this could be pluggable, but I think that providing a "remove first found" as a default is very reasonable in this case as it fits the idiomatic behavior people expect from extent collections.
+0 (non-binding) for putting this into the CollectionMutator but providing present behavior as default if no mutator set (rather than an exception as add/addAll do. This is internally inconsistent though so I would welcome better ideas.
The containsAll javadoc says "This is O(n^2) at the moment, be careful using it.".
It is not correct anymore. It was in the original version but the implementation has changed significantly already =)
I am curious about how much faster this can be done without an ordering.
Dropping ordering on what?
The last comment suggests another possibly useful method:
toList(), returning an aggregated collection consisting of all of the objects in the composite collections.
That works for me, though I would make it a Collection and return the actual type of whichever subclass. I suspect Stephen will suggest that it be toCollection(), toList(), and toSet() respectively in order to allow greater specificity of the return type, which I am also okay with.
Hmm, would be nice if Java let you override a method to return a subclass of the return type of the method being overridden. It would satisfy the static typing still.
-Brian
PS: I have attached changes discussed
/* * $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/Closure.java,v 1.7 2003/08/31 17:26:44 scolebourne Exp $ * ==================================================================== * * The Apache Software License, Version 1.1 * * Copyright (c) 2001-2003 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 acknowledgement: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgement may appear in the software itself, * if and wherever such third-party acknowledgements 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 [EMAIL PROTECTED] * * 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 Software Foundation. * * 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.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import org.apache.commons.collections.iterators.IteratorChain;
/**
* A <code>Collection</code> implementation that decorates other collections
* to provide a single unified view.
* <p>
* Changes made to this collection will actually be made on the decorated collection.
* Removal and clear changes are simple, however add operations require the use
* of a pluggable strategy. If no strategy is provided then add is unsupported.
*
* @since Commons Collections 3.0
* @version $Revision: $ $Date: $
*
* @author Brian McCallister
*/
public class CompositeCollection implements Collection {
/** CollectionMutator to handle changes to the collection */
protected CollectionMutator mutator;
/** Collections in the composite */
protected Collection[] all;
/**
* Create an empty CompositeCollection
*/
public CompositeCollection() {
this.all = new Collection[0];
}
/**
* Create a Composite Collection with only c composited
*/
public CompositeCollection(Collection c) {
super();
this.addComposited(c);
}
/**
* Create a CompositeCollection with c as the initial list of
* composited collections.
*/
public CompositeCollection(Collection[] c) {
this.addComposited(c);
}
//-----------------------------------------------------------------------
/**
* Gets the size of this composite collection.
* <p>
* This implementation calls <code>size()</code> on each collection.
*
* @return total number of elements in all contained containers
*/
public int size() {
int size = 0;
for (int i = this.all.length - 1; i >= 0 ; i--) {
size += this.all[i].size();
}
return size;
}
/**
* Checks whether this composite collection is empty.
* <p>
* This implementation calls <code>isEmpty()</code> on each collection.
*
* @return true if all of the contained collections are empty
*/
public boolean isEmpty() {
for (int i = this.all.length - 1; i >= 0 ; i--) {
if (this.all[i].isEmpty() == false) {
return false;
}
}
return true;
}
/**
* Checks whether this composite collection contains the object.
* <p>
* This implementation calls <code>contains()</code> on each collection.
*
* @return true if obj is contained in any of the contained collections
*/
public boolean contains(Object obj) {
for (int i = this.all.length - 1; i >= 0 ; i--) {
if (this.all[i].contains(obj)) {
return true;
}
}
return false;
}
/**
* Gets an iterator over all the collections in this composite.
* <p>
* This implementation uses an <code>IteratorChain</code>.
*
* @return an <code>IteratorChain</code> instance which supports
* <code>remove()</code>. Iteration occurs over contained collections in
* the order they were added, but this behavior should not be relied upon.
* @see IteratorChain
*/
public Iterator iterator() {
IteratorChain chain = new IteratorChain();
for (int i = 0; i < this.all.length; ++i) {
chain.addIterator(this.all[i].iterator());
}
return chain;
}
/**
* Returns an array containing all of the elements in this composite.
*
* @return an object array of all the elements in the collection
*/
public Object[] toArray() {
final Object[] result = new Object[this.size()];
int i = 0;
for (Iterator it = this.iterator(); it.hasNext(); i++) {
result[i] = it.next();
}
return result;
}
/**
* Returns an object array, populating the supplied array if possible.
* See <code>Collection</code> interface for full details.
*
* @return an array of all the elements in the collection
*/
public Object[] toArray(Object array[]) {
int size = this.size();
Object[] result = null;
if (array.length >= size) {
result = array;
} else {
result = (Object[]) Array.newInstance(array.getClass().getComponentType(),
size);
}
int offset = 0;
for (int i = 0; i < this.all.length; ++i) {
for (Iterator it = this.all[i].iterator(); it.hasNext();) {
result[offset++] = it.next();
}
}
return result;
}
/**
* Adds an object to the collection, throwing UnsupportedOperationException
* unless a CollectionMutator strategy is specified.
*
* @param obj the object to add
* @return true if the collection was modified
* @throws UnsupportedOperationException if CollectionMutator hasn't been set
* @throws UnsupportedOperationException if add is unsupported
* @throws ClassCastException if the object cannot be added due to its type
* @throws NullPointerException if the object cannot be added because its null
* @throws IllegalArgumentException if the object cannot be added
*/
public boolean add(Object obj) {
if (this.mutator == null) {
throw new UnsupportedOperationException("add() is not supported on
CompositeCollection without a CollectionMutator strategy");
}
return this.mutator.add(this, this.all, obj);
}
/**
* Finds and removes the first element equal to that specified.
* <p>
* This implementation calls <code>remove()</code> on each collection.
*
* @param obj the object to remove
* @return true if the collection was modified
* @throws UnsupportedOperationException if remove is unsupported
*/
public boolean remove(Object obj) {
for (int i = 0; i < this.all.length; i--) {
if (this.all[i].remove(obj)) {
return true;
}
}
return false;
}
/**
* Checks whether this composite contains all the elements in the specified
collection.
* <p>
* This implementation calls <code>contains()</code> for each element in the
* specified collection.
*
* @param coll the collection to check for
* @return true if all elements contained
*/
public boolean containsAll(Collection coll) {
for (Iterator it = coll.iterator(); it.hasNext();) {
if (this.contains(it.next()) == false) {
return false;
}
}
return true;
}
/**
* Adds a collection of elements to this collection, throwing
* UnsupportedOperationException unless a CollectionMutator strategy is specified.
*
* @param coll the collection to add
* @return true if the collection was modified
* @throws UnsupportedOperationException if CollectionMutator hasn't been set
* @throws UnsupportedOperationException if add is unsupported
* @throws ClassCastException if the object cannot be added due to its type
* @throws NullPointerException if the object cannot be added because its null
* @throws IllegalArgumentException if the object cannot be added
*/
public boolean addAll(Collection coll) {
if (this.mutator == null) {
throw new UnsupportedOperationException("addAll() is not supported on
CompositeCollection without a CollectionMutator strategy");
}
return this.mutator.addAll(this, this.all, coll);
}
/**
* Removes the elements in the specified collection from this composite collection.
* <p>
* This implementation calls <code>removeAll</code> on each collection.
*
* @param coll the collection to remove
* @return true if the collection was modified
* @throws UnsupportedOperationException if removeAll is unsupported
*/
public boolean removeAll(Collection coll) {
if (coll.size() == 0) {
return false;
}
boolean changed = false;
for (int i = this.all.length - 1; i >= 0 ; i--) {
changed = (this.all[i].removeAll(coll) || changed);
}
return changed;
}
/**
* Retains all the elements in the specified collection in this composite
collection,
* removing all others.
* <p>
* This implementation calls <code>retainAll()</code> on each collection.
*
* @param coll the collection to remove
* @return true if the collection was modified
* @throws UnsupportedOperationException if retainAll is unsupported
*/
public boolean retainAll(final Collection coll) {
boolean changed = false;
for (int i = this.all.length - 1; i >= 0 ; i--) {
changed = (this.all[i].retainAll(coll) || changed);
}
return changed;
}
/**
* Removes all of the elements from this collection .
* <p>
* This implementation calls <code>clear()</code> on each collection.
*
* @throws UnsupportedOperationException if clear is unsupported
*/
public void clear() {
for (int i = 0; i < this.all.length; ++i) {
this.all[i].clear();
}
}
//-----------------------------------------------------------------------
/**
* Specify a CollectionMutator strategy instance to handle changes.
*
* @param mutator the mutator to use
*/
public void setMutator(CollectionMutator mutator) {
this.mutator = mutator;
}
/**
* Add these Collections to the list of collections in this composite
*
* @param comps Collections to be appended to the composite
*/
public void addComposited(Collection[] comps) {
ArrayList list = new ArrayList(Arrays.asList(this.all));
list.addAll(Arrays.asList(comps));
all = (Collection[]) list.toArray(new Collection[list.size()]);
}
/**
* Add an additional collection to this composite.
*/
public void addComposited(Collection c) {
this.addComposited(new Collection[] { c });
}
/**
* Add two additional collection to this composite.
*/
public void addComposited(Collection c, Collection d) {
this.addComposited(new Collection[] { c, d });
}
/**
* Removes a collection from the those being decorated in this composite.
*
* @param coll collection to be removed
*/
public void removeComposited(Collection coll) {
ArrayList list = new ArrayList(this.all.length);
list.addAll(Arrays.asList(this.all));
list.remove(coll);
this.all = (Collection[]) list.toArray(new Collection[list.size()]);
}
/**
* Returns a new collection containing all of the elements
*
* @return A new ArrayList containing all of the elements in this composite.
* The new collection is <i>not</i> backed by this composite.
*/
public Collection toCollection(){
return new ArrayList(this);
}
/**
* Gets the collections being decorated.
*
* @return Unmodifiable collection of all collections in this composite.
*/
public Collection getCollections() {
return Collections.unmodifiableList(Arrays.asList(this.all));
}
//-----------------------------------------------------------------------
/**
* Pluggable strategy to handle changes to the composite.
*/
public interface CollectionMutator {
/**
* Called when an object is to be added to the composite.
*
* @param composite the CompositeCollection being changed
* @param collections all of the Collection instances in this
CompositeCollection
* @param obj the object being added
* @return true if the collection is changed
* @throws UnsupportedOperationException if add is unsupported
* @throws ClassCastException if the object cannot be added due to its type
* @throws NullPointerException if the object cannot be added because its null
* @throws IllegalArgumentException if the object cannot be added
*/
public boolean add(CompositeCollection composite, Collection[] collections,
Object obj);
/**
* Called when a collection is to be added to the composite.
*
* @param composite the CompositeCollection being changed
* @param collections all of the Collection instances in this
CompositeCollection
* @param coll the collection being added
* @return true if the collection is changed
* @throws UnsupportedOperationException if add is unsupported
* @throws ClassCastException if the object cannot be added due to its type
* @throws NullPointerException if the object cannot be added because its null
* @throws IllegalArgumentException if the object cannot be added
*/
public boolean addAll(CompositeCollection composite, Collection[] collections,
Collection coll);
}
}
package org.apache.commons.collections;
import junit.framework.TestCase;
import java.util.HashSet;
import java.util.Collection;
import java.util.Iterator;
public class TestCompositeCollection extends TestCase
{
private CompositeCollection c;
private Collection one;
private Collection two;
public void setUp()
{
c = new CompositeCollection();
one = new HashSet();
two = new HashSet();
}
public void testSize()
{
HashSet set = new HashSet();
set.add("a");
set.add("b");
c.addComposited(set);
assertEquals(set.size(), c.size());
}
public void testMultipleCollectionsSize()
{
HashSet set = new HashSet();
set.add("a");
set.add("b");
c.addComposited(set);
HashSet other = new HashSet();
other.add("c");
c.addComposited(other);
assertEquals(set.size() + other.size(), c.size());
}
public void testIsEmpty()
{
assertTrue(c.isEmpty());
HashSet empty = new HashSet();
c.addComposited(empty);
assertTrue(c.isEmpty());
empty.add("a");
assertFalse(c.isEmpty());
}
public void testContains()
{
HashSet empty = new HashSet();
c.addComposited(empty);
Object foo = "foo";
empty.add(foo);
assertTrue(c.contains(foo));
assertFalse(c.contains("bar"));
}
public void testIterator()
{
one.add("1");
two.add("2");
c.addComposited(one);
c.addComposited(two);
Iterator i = c.iterator();
Object next = i.next();
assertTrue(c.contains(next));
assertTrue(one.contains(next));
next = i.next();
i.remove();
assertFalse(c.contains(next));
assertFalse(two.contains(next));
}
public void testToArray()
{
one.add("1");
two.add("2");
c.addComposited(one);
c.addComposited(two);
Object[] arry = c.toArray();
assertEquals(c.size(), arry.length);
assertTrue(c.contains(arry[0]));
assertTrue(c.contains(arry[1]));
}
public void testToArrayArray()
{
one.add("1");
two.add("2");
c.addComposited(one);
c.addComposited(two);
String[] foo = new String[2];
String[] arry = (String[]) c.toArray(foo);
assertEquals(c.size(), arry.length);
assertTrue(c.contains(arry[0]));
assertTrue(c.contains(arry[1]));
}
public void testToArrayArrayEmpty()
{
one.add("1");
two.add("2");
c.addComposited(new Collection[] {one, two});
String[] sa = (String[]) c.toArray(new String[0]);
assertEquals(2, sa.length);
}
public void testClear()
{
one.add("1");
two.add("2");
c.addComposited(one, two);
c.clear();
assertTrue(one.isEmpty());
assertTrue(two.isEmpty());
assertTrue(c.isEmpty());
}
public void testAdd()
{
c.addComposited(one);
try
{
c.add("two");
fail("Should have thrown exception add");
}
catch (Exception e)
{
assertTrue(true);
}
}
public void testAddAll()
{
c.addComposited(one);
try
{
c.addAll(two);
fail("Should have thrown exception add");
}
catch (Exception e)
{
assertTrue(true);
}
}
public void testContainsAll()
{
one.add("1");
two.add("1");
c.addComposited(one);
assertTrue(c.containsAll(two));
}
public void testRetainAll()
{
one.add("1");
one.add("2");
two.add("1");
c.addComposited(one);
c.retainAll(two);
assertFalse(c.contains("2"));
assertFalse(one.contains("2"));
assertTrue(c.contains("1"));
assertTrue(one.contains("1"));
}
public void testAddAllMutator()
{
c.setMutator(new CompositeCollection.CollectionMutator()
{
public boolean add(CompositeCollection composite, Collection[]
collections, Object obj)
{
for (int i = 0; i < collections.length; i++)
{
collections[i].add(obj);
}
return true;
}
public boolean addAll(CompositeCollection composite, Collection[]
collections, Collection coll)
{
for (int i = 0; i < collections.length; i++)
{
collections[i].addAll(coll);
}
return true;
}
});
c.addComposited(one);
two.add("foo");
c.addAll(two);
assertTrue(c.contains("foo"));
assertTrue(one.contains("foo"));
}
public void testAddMutator()
{
c.setMutator(new CompositeCollection.CollectionMutator()
{
public boolean add(CompositeCollection composite, Collection[]
collections, Object obj)
{
for (int i = 0; i < collections.length; i++)
{
collections[i].add(obj);
}
return true;
}
public boolean addAll(CompositeCollection composite, Collection[]
collections, Collection coll)
{
for (int i = 0; i < collections.length; i++)
{
collections[i].addAll(coll);
}
return true;
}
});
c.addComposited(one);
c.add("foo");
assertTrue(c.contains("foo"));
assertTrue(one.contains("foo"));
}
public void testToCollection()
{
one.add("1");
two.add("2");
c.addComposited(one, two);
Collection foo = c.toCollection();
assertTrue(foo.containsAll(c));
assertEquals(c.size(), foo.size());
one.add("3");
assertFalse(foo.containsAll(c));
}
}
PGP.sig
Description: This is a digitally signed message part
