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" <[EMAIL PROTECTED]> Newsgroups: hometree.jakarta.commons.dev To: <[EMAIL PROTECTED]> 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 [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 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 [EMAIL PROTECTED] Collection} that contains each object only once but keeps the sequence > + * of the objects like a list. > + * > + * @author <a hef="mailto:[EMAIL PROTECTED]">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> > + [EMAIL PROTECTED] org.apache.commons.collections.OrderedSet}<br> > + </td> > + </tr> > + <tr> > <td valign="top">Utilities</td> > <td valign="top"> > [EMAIL PROTECTED] 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 [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 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 [EMAIL PROTECTED] TestSet} for exercising the [EMAIL PROTECTED] > OrderedSet} > + * implementation. > + * > + * @author <a hef="mailto:[EMAIL PROTECTED]">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 > [EMAIL PROTECTED] +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: [EMAIL PROTECTED] > For additional commands, e-mail: [EMAIL PROTECTED] > --------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
