You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by rw...@apache.org on 2002/07/09 18:48:56 UTC
cvs commit: jakarta-commons/collections/src/test/org/apache/commons/collections TestCollatingIterator.java TestAll.java
rwaldhoff 2002/07/09 09:48:56
Modified: collections/src/test/org/apache/commons/collections
TestAll.java
Added: collections/src/java/org/apache/commons/collections
CollatingIterator.java
collections/src/test/org/apache/commons/collections
TestCollatingIterator.java
Log:
add CollatingIterator and tests
Revision Changes Path
1.1 jakarta-commons/collections/src/java/org/apache/commons/collections/CollatingIterator.java
Index: CollatingIterator.java
===================================================================
/*
* $Header: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/CollatingIterator.java,v 1.1 2002/07/09 16:48:56 rwaldhoff Exp $
* $Revision: 1.1 $
* $Date: 2002/07/09 16:48:56 $
*
* ====================================================================
*
* 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.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.ArrayList;
import java.util.BitSet;
/**
* Provides an ordered iteration over the elements contained in
* a collection of ordered {@link Iterator}s. In other words,
* given two ordered {@link Iterator}s <code>A</code> and <code>B</code>,
* my {@link #next} method will return the lesser of
* <code>A.next()</code> and <code>B.next()</code>.
*
* @version $Revision: 1.1 $ $Date: 2002/07/09 16:48:56 $
* @author Rodney Waldhoff
*/
public class CollatingIterator implements Iterator {
//------------------------------------------------------------ Constructors
public CollatingIterator(Comparator comp) {
this(comp,2);
}
public CollatingIterator(Comparator comp, int initIterCapacity) {
iterators = new ArrayList(initIterCapacity);
comparator = comp;
}
public CollatingIterator(Comparator comp, Iterator a, Iterator b) {
this(comp,2);
addIterator(a);
addIterator(b);
}
//--------------------------------------------------------- Public Methods
public void addIterator(Iterator iter) throws IllegalStateException {
checkNotStarted();
iterators.add(iter);
}
public void setComparator(Comparator comp) throws IllegalStateException {
checkNotStarted();
comparator = comp;
}
public Comparator getIterator() {
return comparator;
}
//------------------------------------------------------- Iterator Methods
public boolean hasNext() {
start();
return anyValueSet(valueSet) || anyHasNext(iterators);
}
public Object next() throws NoSuchElementException {
if(!hasNext()) {
throw new NoSuchElementException();
} else {
int leastIndex = least();
if(leastIndex == -1) {
throw new NoSuchElementException();
} else {
Object val = values.get(leastIndex);
clear(leastIndex);
lastReturned = leastIndex;
return val;
}
}
}
public void remove() {
if(-1 == lastReturned) {
throw new NoSuchElementException("No value has been returned yet.");
} else {
Iterator iter = (Iterator)(iterators.get(lastReturned));
iter.remove();
}
}
//--------------------------------------------------------- Private Methods
private void start() {
if(null == values) {
values = new ArrayList(iterators.size());
valueSet = new BitSet(iterators.size());
for(int i=0;i<iterators.size();i++) {
values.add(null);
valueSet.clear(i);
}
}
}
private boolean set(int i) {
Iterator iter = (Iterator)(iterators.get(i));
if(iter.hasNext()) {
values.set(i,iter.next());
valueSet.set(i);
return true;
} else {
values.set(i,null);
valueSet.clear(i);
return false;
}
}
private void clear(int i) {
values.set(i,null);
valueSet.clear(i);
}
private void checkNotStarted() throws IllegalStateException {
if(null != values) {
throw new IllegalStateException("Can't do that after next or hasNext has been called.");
}
}
private int least() throws IllegalStateException {
int leastIndex = -1;
Object leastObject = null;
for(int i=0;i<values.size();i++) {
if(!valueSet.get(i)) {
set(i);
}
if(valueSet.get(i)) {
if(leastIndex == -1) {
leastIndex = i;
leastObject = values.get(i);
} else {
Object curObject = values.get(i);
if(comparator.compare(curObject,leastObject) < 0) {
leastObject = curObject;
leastIndex = i;
}
}
}
}
return leastIndex;
}
private boolean anyValueSet(BitSet set) {
for(int i=0;i<set.size();i++) {
if(set.get(i)) {
return true;
}
}
return false;
}
private boolean anyHasNext(ArrayList iters) {
for(int i=0;i<iters.size();i++) {
Iterator iter = (Iterator)iters.get(i);
if(iter.hasNext()) {
return true;
}
}
return false;
}
//--------------------------------------------------------- Private Members
/** My {@link Comparator}. */
private Comparator comparator = null;
/** My list of {@link Iterator}s. */
private ArrayList iterators = null;
/** {@link Iterator#next Next} objects peeked from each iterator. */
private ArrayList values = null;
/** Whether or not each {@link #values} element has been set. */
private BitSet valueSet = null;
/** Index of the {@link #iterators iterator} from whom the last returned value was obtained. */
private int lastReturned = -1;
}
1.30 +5 -4 jakarta-commons/collections/src/test/org/apache/commons/collections/TestAll.java
Index: TestAll.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestAll.java,v
retrieving revision 1.29
retrieving revision 1.30
diff -u -r1.29 -r1.30
--- TestAll.java 3 Jul 2002 01:57:08 -0000 1.29
+++ TestAll.java 9 Jul 2002 16:48:56 -0000 1.30
@@ -83,6 +83,7 @@
suite.addTest(TestBinaryHeap.suite());
suite.addTest(TestBoundedFifoBuffer.suite());
suite.addTest(TestBoundedFifoBuffer2.suite());
+ suite.addTest(TestCollatingIterator.suite());
suite.addTest(TestCollectionUtils.suite());
suite.addTest(TestComparableComparator.suite());
suite.addTest(TestComparatorChain.suite());
1.1 jakarta-commons/collections/src/test/org/apache/commons/collections/TestCollatingIterator.java
Index: TestCollatingIterator.java
===================================================================
/*
* $Header: /home/cvs/jakarta-commons/collections/src/test/org/apache/commons/collections/TestCollatingIterator.java,v 1.1 2002/07/09 16:48:56 rwaldhoff Exp $
* $Revision: 1.1 $
* $Date: 2002/07/09 16:48:56 $
*
* ====================================================================
*
* 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 junit.framework.*;
import java.util.Iterator;
import java.util.Comparator;
import java.util.ArrayList;
import org.apache.commons.collections.comparators.ComparableComparator;
/**
* Unit test suite for {@link CollatingIterator}.
* @version $Revision: 1.1 $ $Date: 2002/07/09 16:48:56 $
* @author Rodney Waldhoff
*/
public class TestCollatingIterator extends TestIterator {
//------------------------------------------------------------ Conventional
public TestCollatingIterator(String testName) {
super(testName);
}
public static Test suite() {
return new TestSuite(TestCollatingIterator.class);
}
//--------------------------------------------------------------- Lifecycle
private Comparator comparator = null;
private ArrayList evens = null;
private ArrayList odds = null;
private ArrayList fib = null;
public void setUp() throws Exception {
super.setUp();
comparator = new ComparableComparator();
evens = new ArrayList();
odds = new ArrayList();
for(int i=0;i<20;i++) {
if(0 == i%2) {
evens.add(new Integer(i));
} else {
odds.add(new Integer(i));
}
}
fib = new ArrayList();
fib.add(new Integer(1));
fib.add(new Integer(1));
fib.add(new Integer(2));
fib.add(new Integer(3));
fib.add(new Integer(5));
fib.add(new Integer(8));
fib.add(new Integer(13));
fib.add(new Integer(21));
}
//---------------------------------------------------- TestIterator Methods
public Iterator makeEmptyIterator() {
return new CollatingIterator(comparator);
}
public Iterator makeFullIterator() {
CollatingIterator iter = new CollatingIterator(comparator);
iter.addIterator(evens.iterator());
iter.addIterator(odds.iterator());
iter.addIterator(fib.iterator());
return iter;
}
public Object makeObject() {
return makeFullIterator();
}
public boolean supportsEmptyIterator() {
return true;
}
//------------------------------------------------------------------- Tests
public void testIterateEven() {
CollatingIterator iter = new CollatingIterator(comparator);
iter.addIterator(evens.iterator());
for(int i=0;i<evens.size();i++) {
assertTrue(iter.hasNext());
assertEquals(evens.get(i),iter.next());
}
assertTrue(!iter.hasNext());
}
public void testIterateEvenOdd() {
CollatingIterator iter = new CollatingIterator(comparator);
iter.addIterator(evens.iterator());
iter.addIterator(odds.iterator());
for(int i=0;i<20;i++) {
assertTrue(iter.hasNext());
assertEquals(new Integer(i),iter.next());
}
assertTrue(!iter.hasNext());
}
public void testIterateOddEven() {
CollatingIterator iter = new CollatingIterator(comparator);
iter.addIterator(odds.iterator());
iter.addIterator(evens.iterator());
for(int i=0;i<20;i++) {
assertTrue(iter.hasNext());
assertEquals(new Integer(i),iter.next());
}
assertTrue(!iter.hasNext());
}
public void testIterateEvenEven() {
CollatingIterator iter = new CollatingIterator(comparator);
iter.addIterator(evens.iterator());
iter.addIterator(evens.iterator());
for(int i=0;i<evens.size();i++) {
assertTrue(iter.hasNext());
assertEquals(evens.get(i),iter.next());
assertTrue(iter.hasNext());
assertEquals(evens.get(i),iter.next());
}
assertTrue(!iter.hasNext());
}
public void testIterateFibEvenOdd() {
CollatingIterator iter = new CollatingIterator(comparator);
iter.addIterator(fib.iterator());
iter.addIterator(evens.iterator());
iter.addIterator(odds.iterator());
assertEquals(new Integer(0),iter.next()); // even 0
assertEquals(new Integer(1),iter.next()); // fib 1
assertEquals(new Integer(1),iter.next()); // fib 1
assertEquals(new Integer(1),iter.next()); // odd 1
assertEquals(new Integer(2),iter.next()); // fib 2
assertEquals(new Integer(2),iter.next()); // even 2
assertEquals(new Integer(3),iter.next()); // fib 3
assertEquals(new Integer(3),iter.next()); // odd 3
assertEquals(new Integer(4),iter.next()); // even 4
assertEquals(new Integer(5),iter.next()); // fib 5
assertEquals(new Integer(5),iter.next()); // odd 5
assertEquals(new Integer(6),iter.next()); // even 6
assertEquals(new Integer(7),iter.next()); // odd 7
assertEquals(new Integer(8),iter.next()); // fib 8
assertEquals(new Integer(8),iter.next()); // even 8
assertEquals(new Integer(9),iter.next()); // odd 9
assertEquals(new Integer(10),iter.next()); // even 10
assertEquals(new Integer(11),iter.next()); // odd 11
assertEquals(new Integer(12),iter.next()); // even 12
assertEquals(new Integer(13),iter.next()); // fib 13
assertEquals(new Integer(13),iter.next()); // odd 13
assertEquals(new Integer(14),iter.next()); // even 14
assertEquals(new Integer(15),iter.next()); // odd 15
assertEquals(new Integer(16),iter.next()); // even 16
assertEquals(new Integer(17),iter.next()); // odd 17
assertEquals(new Integer(18),iter.next()); // even 18
assertEquals(new Integer(19),iter.next()); // odd 19
assertEquals(new Integer(21),iter.next()); // fib 21
assertTrue(!iter.hasNext());
}
public void testRemoveFromSingle() {
CollatingIterator iter = new CollatingIterator(comparator);
iter.addIterator(evens.iterator());
int expectedSize = evens.size();
while(iter.hasNext()) {
Integer val = (Integer)(iter.next());
if(val.intValue() % 4 == 0) {
expectedSize--;
iter.remove();
}
}
assertEquals(expectedSize,evens.size());
}
public void testRemoveFromDouble() {
CollatingIterator iter = new CollatingIterator(comparator);
iter.addIterator(evens.iterator());
iter.addIterator(odds.iterator());
int expectedSize = evens.size() + odds.size();
while(iter.hasNext()) {
Integer val = (Integer)(iter.next());
if(val.intValue() % 4 == 0 || val.intValue() % 3 == 0 ) {
expectedSize--;
iter.remove();
}
}
assertEquals(expectedSize,(evens.size() + odds.size()));
}
}
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>