commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Henning P. Schmiedehausen" <...@intermeta.de>
Subject [COLLECTIONS] OrderedSet - Bugzilla # 18006
Date Wed, 26 Mar 2003 09:10:55 GMT
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


Mime
View raw message