commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Stephen Colebourne" <scolebou...@btopenworld.com>
Subject Re: [COLLECTIONS] OrderedSet - Bugzilla # 18006
Date Mon, 31 Mar 2003 22:07:47 GMT
Sounds like a sensible addition to [collections]. At some point, one of the
commiters will take a look (I've been on holiday for the last few days...).
Stephen

----- Original Message -----
From: "Henning P. Schmiedehausen" <hps@intermeta.de>
Newsgroups: hometree.jakarta.commons.dev
To: <commons-dev@jakarta.apache.org>
Sent: Wednesday, March 26, 2003 10:10 AM
Subject: [COLLECTIONS] OrderedSet - Bugzilla # 18006


> Hi,
>
> some days ago I put a new class for the Collections component into
> bugzilla bug haven't received any feedback on this. So I resend here. :-)
>
> --- cut ---
> This is a class implementing the Set interface but keeping the
> sequence of the objects added to the set.
>
> The patch contains unit tests based on TestSet and it passed all the
> unit tests by the commons collections suite. It is fully documented
> and I could use it in the Turbine project. Please add!
> --- cut ---
>
> You can also get the following attachment from bugzilla:
>
> http://issues.apache.org/bugzilla/showattachment.cgi?attach_id=5343
>
> Regards
> Henning
>
>
> diff --exclude=CVS -Nurb
collections/src/java/org/apache/commons/collections/OrderedSet.java
collections.p/src/java/org/apache/commons/collections/OrderedSet.java
> --- collections/src/java/org/apache/commons/collections/OrderedSet.java
Thu Jan  1 01:00:00 1970
> +++ collections.p/src/java/org/apache/commons/collections/OrderedSet.java
Fri Mar 14 18:57:24 2003
> @@ -0,0 +1,509 @@
> +/*
> + * $Header$
> + * $Revision$
> + * $Date$
> + *
> + * ====================================================================
> + *
> + * The Apache Software License, Version 1.1
> + *
> + * Copyright (c) 1999-2002 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 acknowlegement:
> + *       "This product includes software developed by the
> + *        Apache Software Foundation (http://www.apache.org/)."
> + *    Alternately, this acknowlegement may appear in the software itself,
> + *    if and wherever such third-party acknowlegements 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 apache@apache.org.
> + *
> + * 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 Group.
> + *
> + * 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.util.ArrayList;
> +import java.util.Collection;
> +import java.util.ConcurrentModificationException;
> +import java.util.Iterator;
> +import java.util.List;
> +import java.util.Set;
> +
> +/**
> + * A {@link Collection} that contains each object only once but keeps the
sequence
> + * of the objects like a list.
> + *
> + * @author <a hef="mailto:hps@intermeta.de">Henning P. Schmiedehausen</a>
> + * @version $Id$
> + */
> +
> +public class OrderedSet
> +        implements Set
> +{
> +    /** Internal list to hold the sequence of objects */
> +    private List setList = null;
> +
> +    /**
> +     * Constructs a new, empty Set.
> +     */
> +    public OrderedSet()
> +    {
> +        clear();
> +    }
> +
> +    /**
> +     * Constructs a new Set from a given Collection. If
> +     * the collection contains an object twice, only one
> +     * is added.
> +     *
> +     * @param c A collection Object
> +     */
> +    public OrderedSet(Collection c)
> +    {
> +        clear();
> +
> +        if ( c != null)
> +        {
> +            for (Iterator it = c.iterator(); it.hasNext();)
> +            {
> +                Object elem = it.next();
> +                add(elem);
> +            }
> +        }
> +    }
> +
> +    /**
> +     * Purge everything from the set.
> +     *
> +     * @throws UnsupportedOperationException if the clear method
> +     *   is not supported by this set.
> +     */
> +    public void clear()
> +    {
> +        this.setList = new ArrayList();
> +    }
> +
> +    /**
> +     * Returns the number of objects in this set.
> +     *
> +     * @return The size of the set.
> +     */
> +    public int size()
> +    {
> +        return setList.size();
> +    }
> +
> +    /**
> +     * Returns true if this set is empty.
> +     *
> +     * @return true if this set is empty.
> +     */
> +    public boolean isEmpty()
> +    {
> +        return setList.isEmpty();
> +    }
> +
> +    /**
> +     * Returns an iterator over the objects in this set.
> +     * This set guarantees that they are in the same sequence
> +     * as they were added. If an object is added multiple
> +     * times, then its place is the first addition to the set.
> +     *
> +     * @return An iterator for this set.
> +     */
> +    public Iterator iterator()
> +    {
> +        return new OrderedSetIterator(setList);
> +    }
> +
> +    /**
> +     * Adds an object to the set.
> +     * This set keeps the sequence of the additions.
> +     *
> +     * @param o The object to be added to this set.
> +     *
> +     * @return true if this set did not already contain the specified
> +     *         object.
> +     *
> +     * @throws UnsupportedOperationException if the add method is not
> +     *        supported by this set.
> +     * @throws ClassCastException if the class of the specified object
> +     *        prevents it from being added to this set.
> +     * @throws IllegalArgumentException if some aspect of this object
> +     *         prevents it from being added to this set.
> +     */
> +    public boolean add(Object o)
> +    {
> +        synchronized (setList)
> +        {
> +            if (setList.contains(o))
> +            {
> +                return false;
> +            }
> +            setList.add(o);
> +            return true;
> +        }
> +    }
> +
> +    /**
> +     * Adds all objects in the specified collection to this set.
> +     *
> +     * @param c A collection object, whose objects should be added
> +     *
> +     * @return true if any object in the collection was actually added.
> +     *
> +     * @throws UnsupportedOperationException if the addAll method is
> +     *   not supported by this set.
> +     * @throws ClassCastException if the class of some object of the
> +     *   specified collection prevents it from being added to this
> +     *   set.
> +     * @throws IllegalArgumentException if some aspect of some object of
the
> +     *   specified collection prevents it from being added to this
> +     *   set.
> +     */
> +    public boolean addAll(Collection c)
> +    {
> +        synchronized (setList)
> +        {
> +            boolean result = false;
> +
> +            if (c != null)
> +            {
> +                for (Iterator it = c.iterator(); it.hasNext(); )
> +                {
> +                    Object o = it.next();
> +                    if (!setList.contains(o))
> +                    {
> +                        result |= setList.add(o);
> +                    }
> +                }
> +            }
> +            return result;
> +        }
> +    }
> +
> +    /**
> +     * Removes an object from the set.
> +     *
> +     * @param o object to be removed from this set, if present.
> +     *
> +     * @return true if the set contained the specified object.
> +     *
> +     * @throws UnsupportedOperationException if the remove method is
> +     *         not supported by this set.
> +     */
> +    public boolean remove(Object o)
> +    {
> +        return setList.remove(o);
> +    }
> +
> +    /**
> +     * Remove all the objects given in the supplied collection.
> +     *
> +     * @param c A collection with the objects to keep.
> +     *
> +     * @return true if any object was removed.
> +     *
> +     * @throws UnsupportedOperationException if the removeAll
> +     *   method is not supported by this Collection.
> +     */
> +    public boolean removeAll(Collection c)
> +    {
> +        synchronized (setList)
> +        {
> +            boolean result = false;
> +
> +            if (c != null)
> +            {
> +                for (Iterator it = setList.iterator(); it.hasNext(); )
> +                {
> +                    Object o = it.next();
> +                    if (c.contains(o))
> +                    {
> +                        it.remove();
> +                        result = true;
> +                    }
> +                }
> +            }
> +            return result;
> +        }
> +    }
> +
> +    /**
> +     * Returns true if this set contains an object.
> +     *
> +     * @param o The wanted object
> +     *
> +     * @return true if this set contains this object
> +     */
> +    public boolean contains(Object o)
> +    {
> +        return setList.contains(o);
> +    }
> +
> +    /**
> +     * Returns true if this set contains all of the objects in the
> +     * given collection object.
> +     *
> +     * @param c A collection to be checked.
> +     *
> +     * @return true if this set contains all of the objects in this
collection.
> +     */
> +    public boolean containsAll(Collection c)
> +    {
> +        return setList.containsAll(c);
> +    }
> +
> +    /**
> +     * Keep only the objects given in the supplied collection. Remove
> +     * all other objects.
> +     *
> +     * @param c A collection with the objects to keep.
> +     *
> +     * @return true if any object was removed.
> +     *
> +     * @throws UnsupportedOperationException if the retainAll method
> +     *   is not supported by this Collection.
> +     */
> +    public boolean retainAll(Collection c)
> +    {
> +        synchronized (setList)
> +        {
> +            boolean result = false;
> +
> +            if (c != null)
> +            {
> +                for (Iterator it = setList.iterator(); it.hasNext(); )
> +                {
> +                    Object o = it.next();
> +                    if (!c.contains(o))
> +                    {
> +                        it.remove();
> +                        result = true;
> +                    }
> +                }
> +            }
> +            return result;
> +        }
> +    }
> +
> +    /**
> +     * Returns an array containing all of the objects in this set.
> +     *
> +     * @return An array with all objects in this set.
> +     */
> +    public Object[] toArray()
> +    {
> +        return setList.toArray();
> +    }
> +
> +    /**
> +     * Returns an array containing all of the objects in this set
> +     * with the specified runtime type.
> +     *
> +     * @param a An array to put all the objects in. If it is
> +     * not big enough, a new array is allocated which
> +     *          has the needed size.
> +     *
> +     * @return An array containing the objects of this set.
> +     *
> +     * @throws    ArrayStoreException Objects couldn't be fit into
> +     *            the required Array type.
> +     */
> +    public Object[] toArray(Object a[])
> +    {
> +        return setList.toArray(a);
> +    }
> +
> +    /**
> +     * Checks whether the supplied object is equal to this set.
> +     *
> +     * @param o Object to be checked.
> +     *
> +     * @return true if both objects are equal.
> +     */
> +    public boolean equals(Object o)
> +    {
> +        synchronized (setList)
> +        {
> +            if (o == null  || (! (o instanceof Set)))
> +            {
> +                return false;
> +            }
> +
> +            Set s = (Set) o;
> +
> +            if (s.size () != setList.size())
> +            {
> +                return false;
> +            }
> +
> +            // Our iterator is fast, our lookups are slow...
> +            for (Iterator it = setList.iterator(); it.hasNext(); )
> +            {
> +                if (!s.contains(it.next()))
> +                {
> +                    return false;
> +                }
> +            }
> +
> +            return true;
> +        }
> +    }
> +
> +    /**
> +     * Returns the hash code for this set.
> +     *
> +     * @return the hash code for this set.
> +     */
> +    public int hashCode()
> +    {
> +        synchronized (setList)
> +        {
> +            int h = 0;
> +
> +            for (Iterator it = setList.iterator(); it.hasNext(); )
> +            {
> +                Object o = it.next();
> +
> +                if (o != null)
> +                {
> +                    h += o.hashCode();
> +                }
> +            }
> +
> +            return h;
> +        }
> +    }
> +
> +    /**
> +     * And a pretty print toString()
> +     *
> +     * @return A pretty formatted Set of elements.
> +     */
> +    public String toString()
> +    {
> +        synchronized(setList)
> +        {
> +            StringBuffer sb = new StringBuffer();
> +
> +            sb.append('[');
> +
> +            for (Iterator it = setList.iterator(); it.hasNext(); )
> +            {
> +                sb.append(String.valueOf(it.next()));
> +
> +                if (it.hasNext())
> +                {
> +                    sb.append(", ");
> +                }
> +            }
> +            sb.append(']');
> +            return sb.toString();
> +        }
> +    }
> +
> +    /**
> +     * Internal iterator to pass the CoModification test
> +     *
> +     */
> +    private class OrderedSetIterator
> +            implements Iterator
> +    {
> +        /** Object we iterate on */
> +        Collection c;
> +
> +        /** Internal iterator reference */
> +        Iterator it;
> +
> +        /**
> +         * C'tor
> +         */
> +        private OrderedSetIterator(Collection c)
> +        {
> +            this.c = c;
> +            this.it = c.iterator();
> +        }
> +
> +        /**
> +         * Next Element
> +         */
> +        public Object next()
> +        {
> +            coModCheck();
> +            return it.next();
> +        }
> +
> +        /**
> +         * has another element
> +         *
> +         * @return True if yes
> +         */
> +        public boolean hasNext()
> +        {
> +            coModCheck();
> +            return it.hasNext();
> +        }
> +
> +        /**
> +         * Remove current element
> +         *
> +         */
> +        public void remove()
> +        {
> +            coModCheck();
> +            it.remove();
> +        }
> +
> +        /**
> +         * Clear would have pulled the list
> +         * from under us.
> +         */
> +        private void coModCheck()
> +        {
> +            if (setList != c)
> +            {
> +                throw new ConcurrentModificationException();
> +            }
> +        }
> +    }
> +}
> diff --exclude=CVS -Nurb
collections/src/java/org/apache/commons/collections/package.html
collections.p/src/java/org/apache/commons/collections/package.html
> --- collections/src/java/org/apache/commons/collections/package.html Sun
Dec  8 16:30:58 2002
> +++ collections.p/src/java/org/apache/commons/collections/package.html Fri
Mar 14 19:02:03 2003
> @@ -75,6 +75,12 @@
>          </td>
>        </tr>
>        <tr>
> +        <td valign="top">Set Implementations</td>
> +        <td>
> +          {@link org.apache.commons.collections.OrderedSet}<br>
> +        </td>
> +      </tr>
> +      <tr>
>          <td valign="top">Utilities</td>
>          <td valign="top">
>            {@link org.apache.commons.collections.BagUtils}<br>
> diff --exclude=CVS -Nurb
collections/src/test/org/apache/commons/collections/TestAll.java
collections.p/src/test/org/apache/commons/collections/TestAll.java
> --- collections/src/test/org/apache/commons/collections/TestAll.java Sun
Mar  9 01:07:41 2003
> +++ collections.p/src/test/org/apache/commons/collections/TestAll.java Fri
Mar 14 17:56:36 2003
> @@ -108,6 +108,7 @@
>          suite.addTest(TestUnboundedFifoBuffer.suite());
>          suite.addTest(TestReferenceMap.suite());
>          suite.addTest(TestIteratorUtils.suite());
> +        suite.addTest(TestOrderedSet.suite());
>
suite.addTest(org.apache.commons.collections.comparators.TestAll.suite());
>
suite.addTest(org.apache.commons.collections.iterators.TestAll.suite());
>
suite.addTest(org.apache.commons.collections.primitives.TestAll.suite());
> diff --exclude=CVS -Nurb
collections/src/test/org/apache/commons/collections/TestOrderedSet.java
collections.p/src/test/org/apache/commons/collections/TestOrderedSet.java
> ---
collections/src/test/org/apache/commons/collections/TestOrderedSet.java Thu
Jan  1 01:00:00 1970
> +++
collections.p/src/test/org/apache/commons/collections/TestOrderedSet.java
Fri Mar 14 18:58:03 2003
> @@ -0,0 +1,155 @@
> +/*
> + * $Header$
> + * $Revision$
> + * $Date$
> + *
> + * ====================================================================
> + *
> + * The Apache Software License, Version 1.1
> + *
> + * Copyright (c) 1999-2001 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 acknowlegement:
> + *       "This product includes software developed by the
> + *        Apache Software Foundation (http://www.apache.org/)."
> + *    Alternately, this acknowlegement may appear in the software itself,
> + *    if and wherever such third-party acknowlegements 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 apache@apache.org.
> + *
> + * 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 Group.
> + *
> + * 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.util.Iterator;
> +import java.util.Set;
> +
> +import junit.framework.Test;
> +import junit.framework.TestSuite;
> +
> +/**
> + * Extension of {@link TestSet} for exercising the {@link OrderedSet}
> + * implementation.
> + *
> + * @author <a hef="mailto:hps@intermeta.de">Henning P. Schmiedehausen</a>
> + * @version $Id$
> + */
> +public class TestOrderedSet
> +        extends TestSet
> +{
> +    public TestOrderedSet(String testName)
> +    {
> +        super(testName);
> +    }
> +
> +    public static Test suite()
> +    {
> +        return new TestSuite(TestOrderedSet.class);
> +    }
> +
> +    public static void main(String args[])
> +    {
> +        String[] testCaseName = { TestOrderedSet.class.getName() };
> +        junit.textui.TestRunner.main(testCaseName);
> +    }
> +
> +    public Set makeEmptySet()
> +    {
> +        return new OrderedSet();
> +    }
> +
> +    public Set setupSet()
> +    {
> +        Set set = makeEmptySet();
> +
> +        for (int i = 0; i < 10 ; i++)
> +        {
> +            set.add(Integer.toString(i));
> +        }
> +        return set;
> +    }
> +
> +    public void testOrdering()
> +    {
> +        Set set = setupSet();
> +        Iterator it = set.iterator();
> +
> +        for (int i = 0; i < 10 ; i++)
> +        {
> +            assertEquals("Sequence is wrong" ,
> +                    Integer.toString(i), it.next());
> +        }
> +
> +        for (int i = 0; i < 10 ; i += 2)
> +        {
> +            assertTrue("Must be able to remove int",
> +                    set.remove(Integer.toString(i)));
> +        }
> +
> +        it = set.iterator();
> +        for (int i = 1; i < 10 ; i += 2)
> +        {
> +            assertEquals("Sequence is wrong after remove ",
> +                    Integer.toString(i), it.next());
> +        }
> +
> +        for (int i = 0; i < 10 ; i++)
> +        {
> +            set.add(Integer.toString(i));
> +        }
> +
> +        assertEquals("Size of set is wrong!", 10, set.size());
> +
> +        it = set.iterator();
> +        for (int i = 1; i < 10 ; i += 2)
> +        {
> +            assertEquals("Sequence is wrong",
> +                    Integer.toString(i), it.next());
> +        }
> +        for (int i = 0; i < 10 ; i += 2)
> +        {
> +            assertEquals("Sequence is wrong",
> +                    Integer.toString(i), it.next());
> +        }
> +    }
> +}
> --
> Dipl.-Inf. (Univ.) Henning P. Schmiedehausen          INTERMETA GmbH
> hps@intermeta.de        +49 9131 50 654 0   http://www.intermeta.de/
>
> Java, perl, Solaris, Linux, xSP Consulting, Web Services
> freelance consultant -- Jakarta Turbine Development  -- hero for hire
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>


---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message