On Sunday, November 2, 2003, at 07:27 PM, Stephen Colebourne wrote:
I haven't tested it, but I suspect the performance gain to be noticable, and
[collections] has to choose the fastest implementation if it has a choice.
Would you consider the alternative implementation I suggest?
Stephen
Performance optimized version attached. I think this actually reads more clearly anyway. Must try to stop thinking in Ruby when writing Java =) I also cleaned up the spec breaking toArray(Object[] array) implementation.
The highly unoptimized part is adding and removing composited collections. I let ArrayList handle the array resizing for me.
-Brian
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.setAddAllMutator(new CompositeCollection.Mutator()
{
public Object execute(Collection[] collections, CompositeCollection
composite, Object[] args)
{
Collection c = (Collection) args[0];
for (int i = 0; i < collections.length; i++)
{
collections[i].addAll(c);
}
return new Boolean(true);
}
});
c.addComposited(one);
two.add("foo");
c.addAll(two);
assertTrue(c.contains("foo"));
assertTrue(one.contains("foo"));
}
public void testAddMutator()
{
c.setAddMutator(new CompositeCollection.Mutator()
{
public Object execute(Collection[] collections, CompositeCollection
composite, Object[] args)
{
Object c = args[0];
for (int i = 0; i < collections.length; i++)
{
collections[i].add(c);
}
return new Boolean(true);
}
});
c.addComposited(one);
c.add("foo");
assertTrue(c.contains("foo"));
assertTrue(one.contains("foo"));
}
}
/* 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 "Apache", "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", * "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 org.apache.commons.collections.iterators.IteratorChain; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Iterator; import java.util.Collections; import java.lang.reflect.Array; /** * Represents a composite collection of collections. Changes to contained * collections will be reflected in this class. Changes to this class * will be propogated to contained collections. See individual methods * for specific behaviors in regard to mutators. * * @author <a href="mailto:[EMAIL PROTECTED]">Brian McCallister</a> */ public class CompositeCollection implements Collection { /** Mutator to handle calls to add(Object) */ protected Mutator addStrat; /** Mutator to handle calls to addAll(Collection c) */ protected Mutator addAllStrat; /** 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); } /** * @return number of elements in all contained containers */ public int size() { int size = 0; for (int i = 0; i < this.all.length; ++i) { size += this.all[i].size(); } return size; } /** * @return true if all of the contained collections are empty */ public boolean isEmpty() { for (int i = 0; i < this.all.length; ++i) { if (!this.all[i].isEmpty()) return false; } return true; } /** * @return true if o is contained in any of the contained collections */ public boolean contains(Object o) { for (int i = 0; i < this.all.length; ++i) { if (this.all[i].contains(o)) return true; } return false; } /** * @return a <code>IteratorChain</code> instance which supports * <code>remove()</code> correctly. It does iterate * 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 the composite */ public Object[] toArray() { final Object[] ary = new Object[this.size()]; int i = 0; for (Iterator itty = this.iterator(); itty.hasNext(); i++) { ary[i] = itty.next(); } return ary; } /** * Per Collection spec */ public Object[] toArray(Object a[]) { int size = this.size(); Object[] ary = null; if (a.length >= size) { ary = a; } else { ary = (Object[]) Array.newInstance(a.getClass().getComponentType() , size); } int offset = 0; for (int i = 0; i < this.all.length; ++i) { for (Iterator itty = this.all[i].iterator(); itty.hasNext();) { ary[offset++] = itty.next(); } } return ary; } /** * Throws Unsupported Operation Exception if no Mutator is specified * via <code>CompositeCollection.setAddMutator()</code> otherwise * delegates to the Mutator. * <p> * @throws ClassCastException if Mutator doesn't return a Boolean * @throws UnsupportedOperationException if Mutator hasn't been set */ public boolean add(Object o) { if (this.addStrat == null) throw new UnsupportedOperationException(); Object ret = this.addStrat.execute(this.all, this, new Object[]{o}); if (ret instanceof Boolean) return ((Boolean) ret).booleanValue(); throw new ClassCastException("Mutator for add must return a Boolean"); } /** * Specify a Mutator instance to handle addAll calls. The Mutator <b>must</b> * return a Boolean. */ public void setAddMutator(Mutator m) { this.addStrat = m; } /** * Finds and removes the first element equal to o */ public boolean remove(Object o) { for (Iterator i = this.iterator(); i.hasNext();) { if (i.equals(o)) { i.remove(); return true; } } return false; } /** * This is O(n^2) at the moment, be careful using it */ public boolean containsAll(Collection c) { for (Iterator i = c.iterator(); i.hasNext();) { if (!this.contains(i.next())) return false; } return true; } /** * Throws Unsupported Operation Exception if no Mutator is specified * via <code>CompositeCollection.setAddAllMutator()</code> otherwise * delegates to the Mutator. * <p> * @throws ClassCastException if Mutator doesn't return a Boolean * @throws UnsupportedOperationException if Mutator hasn't been set */ public boolean addAll(Collection c) { if (this.addAllStrat == null) throw new UnsupportedOperationException("No Mutator set"); Object ret = this.addAllStrat.execute(this.all, this, new Object[]{c}); if (ret instanceof Boolean) return ((Boolean) ret).booleanValue(); throw new ClassCastException("Mutator for addAll must return a Boolean"); } /** * Specify a Mutator instance to handle addAll calls. The Mutator <b>must</b> * return a Boolean. */ public void setAddAllMutator(Mutator m) { this.addAllStrat = m; } /** * Removes from every contained collection */ public boolean removeAll(Collection c) { boolean changed = false; for (int i = 0; i < this.all.length; ++i) { changed = (this.all[i].removeAll(c) || changed); } return changed; } /** * Applies to every contained collection */ public boolean retainAll(final Collection c) { boolean changed = false; for (int i = 0; i < this.all.length; ++i) { changed = (this.all[i].retainAll(c) || changed); } return changed; } /** * Removes all of the elements from this collection (optional operation). * This collection will be empty after this method returns unless it * throws an exception. * * @throws UnsupportedOperationException if the <tt>clear</tt> method is * not supported by this collection. */ public void clear() { for (int i = 0; i < this.all.length; ++i) { this.all[i].clear(); } } /** * 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}); } /** * @param c Collection to be removed from the collection of managed collections */ public void removeComposited(Collection c) { ArrayList list = new ArrayList(this.all.length); list.addAll(Arrays.asList(this.all)); list.remove(c); this.all = (Collection[]) list.toArray(new Collection[list.size()]); } /** * @return Unmodifiable collection of all collections in this composite */ public Collection getCollections() { return Collections.unmodifiableList(Arrays.asList(this.all)); } /** * Pluggable class to handle mutators in indeterminate behavior cases. */ public interface Mutator { /** * @param collections All of the Collection instances in this CompositeCollection * @param composite The CompositeCollection being changed * @param args Arguments to the method call, ie for add(Object o) * this would be an Object[] with one element, o * @return value to be returned by the method called */ public Object execute(Collection[] collections, CompositeCollection composite, Object[] args); } }
PGP.sig
Description: Binary data
PGP.sig
Description: Binary data
PGP.sig
Description: This is a digitally signed message part
