Mailing-List: contact commons-dev-help@jakarta.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
Date: Sun, 2 Nov 2003 20:44:03 -0500
Subject: Re: [collections] [PATCH] CompositeCollection class for
 Commons-Collections
Content-Type: multipart/signed; protocol="application/pgp-signature";
 micalg=pgp-sha1; boundary="Apple-Mail-15--677669991"
Mime-Version: 1.0 (Apple Message framework v552)
From: Brian McCallister <mccallister@forthillcompany.com>
To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
In-Reply-To: <010401c3a1a1$51df4860$35468151@oemcomputer>
Message-Id: <340E6DC0-0D9F-11D8-A508-000A95782782@forthillcompany.com>
Content-Transfer-Encoding: 7bit

--Apple-Mail-15--677669991
Content-Type: multipart/mixed; boundary=Apple-Mail-14--677669998


--Apple-Mail-14--677669998
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed


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


--Apple-Mail-14--677669998
Content-Disposition: attachment;
	filename=TestCompositeCollection.java
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	x-unix-mode=0644;
	name="TestCompositeCollection.java"

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"));
    }
}

--Apple-Mail-14--677669998
Content-Disposition: attachment;
	filename=CompositeCollection.java
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	x-unix-mode=0644;
	name="CompositeCollection.java"

/* 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 apache@apache.org.
 *
 * 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:brianm@apache.org">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);
    }
}

--Apple-Mail-14--677669998
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed


--Apple-Mail-14--677669998
Content-Disposition: attachment;
	filename=PGP.sig
Content-Transfer-Encoding: 7bit
Content-Type: application/octet-stream;
	x-unix-mode=0666;
	x-mac-type=70674453;
	name="PGP.sig"

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (Darwin)

iD8DBQE/pbLOaOuMdvjqKWcRAieDAJ98JovWwgPFDjG1nTUT7qZUS2PSnwCeK7IC
pUl5E8vt14yfLPL4Og/1Gt0=
=1oYS
-----END PGP SIGNATURE-----

--Apple-Mail-14--677669998
Content-Disposition: attachment;
	filename=PGP.sig
Content-Transfer-Encoding: 7bit
Content-Type: application/octet-stream;
	x-unix-mode=0666;
	x-mac-type=70674453;
	name="PGP.sig"

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (Darwin)

iD8DBQE/pbLaaOuMdvjqKWcRAk8GAJ9y1RmWzrSzbnNdDw2xCcteQS4XbwCfUA/L
gkPCbDsFSURPhMKSC0XVEYc=
=/tDh
-----END PGP SIGNATURE-----

--Apple-Mail-14--677669998--

--Apple-Mail-15--677669991
content-type: application/pgp-signature; x-mac-type=70674453;
	name=PGP.sig
content-description: This is a digitally signed message part
content-disposition: inline; filename=PGP.sig
content-transfer-encoding: 7bit

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (Darwin)

iD8DBQE/pbLjaOuMdvjqKWcRAolyAJ4xwy8iyPL+qEGPsqxHt9ZlgTAVVgCfTWYv
bJ3C9Kz96Y8BoF1FJrb9Oh8=
=f7Qr
-----END PGP SIGNATURE-----

--Apple-Mail-15--677669991--