test/tck/PriorityQueueTest.java

/*
 * Written by members of JCP JSR-166 Expert Group and released to the
 * public domain. Use, modify, and redistribute this code in any way
 * without acknowledgement. Other contributors include Andrew Wright,
 * Jeffrey Hayes, Pat Fischer, Mike Judd.
 */

import junit.framework.*;
import java.util.*;
import java.util.concurrent.*;

public class PriorityQueueTest extends TestCase {

    private static final int N = 10;
    private static final long SHORT_DELAY_MS = 100; 
    private static final long MEDIUM_DELAY_MS = 1000;
    private static final long LONG_DELAY_MS = 10000; 

    public static void main(String[] args) {
        junit.textui.TestRunner.run (suite());  
    }

    public static Test suite() {
        return new TestSuite(PriorityQueueTest.class);
    }

    static class MyReverseComparator implements Comparator { 
        public int compare(Object x, Object y) {
            int i = ((Integer)x).intValue();
            int j = ((Integer)y).intValue();
            if (i < j) return 1;
            if (i > j) return -1;
            return 0;
        }
    }


    /**
     * Create a queue of given size containing consecutive
     * Integers 0 ... n.
     */
    private PriorityQueue fullQueue(int n) {
        PriorityQueue q = new PriorityQueue(n);
        assertTrue(q.isEmpty());
        for(int i = n-1; i >= 0; i-=2)
            assertTrue(q.offer(new Integer(i)));
        for(int i = (n & 1); i < n; i+=2)
            assertTrue(q.offer(new Integer(i)));
        assertFalse(q.isEmpty());
        assertEquals(n, q.size());
        return q;
    }
 
    public void testConstructor1(){
        assertEquals(0, new PriorityQueue(N).size());
    }

    public void testConstructor2(){
        try {
            PriorityQueue q = new PriorityQueue(0);
            fail("Cannot make zero-sized");
        }
        catch (IllegalArgumentException success) {}
    }

    public void testConstructor3() {

        try {
            PriorityQueue q = new PriorityQueue((Collection)null);
            fail("Cannot make from null collection");
        }
        catch (NullPointerException success) {}
    }

    public void testConstructor4(){
        try {
            Integer[] ints = new Integer[N];
            PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
            fail("Cannot make with null elements");
        }
        catch (NullPointerException success) {}
    }

    public void testConstructor5(){
        try {
            Integer[] ints = new Integer[N];
            for (int i = 0; i < N-1; ++i)
                ints[i] = new Integer(i);
            PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
            fail("Cannot make with null elements");
        }
        catch (NullPointerException success) {}
    }

    public void testConstructor6(){
        try {
            Integer[] ints = new Integer[N];
            for (int i = 0; i < N; ++i)
                ints[i] = new Integer(i);
            PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
            for (int i = 0; i < N; ++i)
                assertEquals(ints[i], q.poll());
        }
        finally {}
    }

    public void testConstructor7(){
        try {
            PriorityQueue q = new PriorityQueue(N, new MyReverseComparator());
            Integer[] ints = new Integer[N];
            for (int i = 0; i < N; ++i)
                ints[i] = new Integer(i);
            q.addAll(Arrays.asList(ints));
            for (int i = N-1; i >= 0; --i)
                assertEquals(ints[i], q.poll());
        }
        finally {}
    }

    public void testEmpty() {
        PriorityQueue q = new PriorityQueue(2);
        assertTrue(q.isEmpty());
        q.add(new Integer(1));
        assertFalse(q.isEmpty());
        q.add(new Integer(2));
        q.remove();
        q.remove();
        assertTrue(q.isEmpty());
    }

    public void testSize() {
        PriorityQueue q = fullQueue(N);
        for (int i = 0; i < N; ++i) {
            assertEquals(N-i, q.size());
            q.remove();
        }
        for (int i = 0; i < N; ++i) {
            assertEquals(i, q.size());
            q.add(new Integer(i));
        }
    }

    public void testOfferNull(){
        try {
            PriorityQueue q = new PriorityQueue(1);
            q.offer(null);
            fail("should throw NPE");
        } catch (NullPointerException success) { }   
    }

    public void testOffer() {
        PriorityQueue q = new PriorityQueue(1);
        assertTrue(q.offer(new Integer(0)));
        assertTrue(q.offer(new Integer(1)));
    }

    public void testOfferNonComparable() {
        try {
            PriorityQueue q = new PriorityQueue(1);
            q.offer(new Object());
            q.offer(new Object());
            q.offer(new Object());
            fail("should throw CCE");
        }
        catch(ClassCastException success) {}
    }

    public void testAdd(){
        PriorityQueue q = new PriorityQueue(N);
        for (int i = 0; i < N; ++i) {
            assertEquals(i, q.size());
            assertTrue(q.add(new Integer(i)));
        }
    }

    public void testAddAll1(){
        try {
            PriorityQueue q = new PriorityQueue(1);
            q.addAll(null);
            fail("Cannot add null collection");
        }
        catch (NullPointerException success) {}
    }
    public void testAddAll2(){
        try {
            PriorityQueue q = new PriorityQueue(N);
            Integer[] ints = new Integer[N];
            q.addAll(Arrays.asList(ints));
            fail("Cannot add null elements");
        }
        catch (NullPointerException success) {}
    }
    public void testAddAll3(){
        try {
            PriorityQueue q = new PriorityQueue(N);
            Integer[] ints = new Integer[N];
            for (int i = 0; i < N-1; ++i)
                ints[i] = new Integer(i);
            q.addAll(Arrays.asList(ints));
            fail("Cannot add null elements");
        }
        catch (NullPointerException success) {}
    }

    public void testAddAll5(){
        try {
            Integer[] empty = new Integer[0];
            Integer[] ints = new Integer[N];
            for (int i = 0; i < N; ++i)
                ints[i] = new Integer(N-1-i);
            PriorityQueue q = new PriorityQueue(N);
            assertFalse(q.addAll(Arrays.asList(empty)));
            assertTrue(q.addAll(Arrays.asList(ints)));
            for (int i = 0; i < N; ++i)
                assertEquals(new Integer(i), q.poll());
        }
        finally {}
    }

    public void testPoll(){
        PriorityQueue q = fullQueue(N);
        for (int i = 0; i < N; ++i) {
            assertEquals(i, ((Integer)q.poll()).intValue());
        }
        assertNull(q.poll());
    }

    public void testPeek(){
        PriorityQueue q = fullQueue(N);
        for (int i = 0; i < N; ++i) {
            assertEquals(i, ((Integer)q.peek()).intValue());
            q.poll();
            assertTrue(q.peek() == null ||
                       i != ((Integer)q.peek()).intValue());
        }
        assertNull(q.peek());
    }

    public void testElement(){
        PriorityQueue q = fullQueue(N);
        for (int i = 0; i < N; ++i) {
            assertEquals(i, ((Integer)q.element()).intValue());
            q.poll();
        }
        try {
            q.element();
            fail("no such element");
        }
        catch (NoSuchElementException success) {}
    }

    public void testRemove(){
        PriorityQueue q = fullQueue(N);
        for (int i = 0; i < N; ++i) {
            assertEquals(i, ((Integer)q.remove()).intValue());
        }
        try {
            q.remove();
            fail("remove should throw");
        } catch (NoSuchElementException success){
        }   
    }

    public void testRemoveElement(){
        PriorityQueue q = fullQueue(N);
        for (int i = 1; i < N; i+=2) {
            assertTrue(q.remove(new Integer(i)));
        }
        for (int i = 0; i < N; i+=2) {
            assertTrue(q.remove(new Integer(i)));
            assertFalse(q.remove(new Integer(i+1)));
        }
        assert(q.isEmpty());
    }
        
    public void testContains(){
        PriorityQueue q = fullQueue(N);
        for (int i = 0; i < N; ++i) {
            assertTrue(q.contains(new Integer(i)));
            q.poll();
            assertFalse(q.contains(new Integer(i)));
        }
    }

    public void testClear(){
        PriorityQueue q = fullQueue(N);
        q.clear();
        assertTrue(q.isEmpty());
        assertEquals(0, q.size());
        q.add(new Integer(1));
        assertFalse(q.isEmpty());
        q.clear();
        assertTrue(q.isEmpty());
    }

    public void testContainsAll(){
        PriorityQueue q = fullQueue(N);
        PriorityQueue p = new PriorityQueue(N);
        for (int i = 0; i < N; ++i) {
            assertTrue(q.containsAll(p));
            assertFalse(p.containsAll(q));
            p.add(new Integer(i));
        }
        assertTrue(p.containsAll(q));
    }

    public void testRetainAll(){
        PriorityQueue q = fullQueue(N);
        PriorityQueue p = fullQueue(N);
        for (int i = 0; i < N; ++i) {
            boolean changed = q.retainAll(p);
            if (i == 0)
                assertFalse(changed);
            else
                assertTrue(changed);

            assertTrue(q.containsAll(p));
            assertEquals(N-i, q.size());
            p.remove();
        }
    }

    public void testRemoveAll(){
        for (int i = 1; i < N; ++i) {
            PriorityQueue q = fullQueue(N);
            PriorityQueue p = fullQueue(i);
            assertTrue(q.removeAll(p));
            assertEquals(N-i, q.size());
            for (int j = 0; j < i; ++j) {
                Integer I = (Integer)(p.remove());
                assertFalse(q.contains(I));
            }
        }
    }

    public void testToArray(){
        PriorityQueue q = fullQueue(N);
        Object[] o = q.toArray();
        Arrays.sort(o);
        for(int i = 0; i < o.length; i++)
            assertEquals(o[i], q.poll());
    }

    public void testToArray2(){
        PriorityQueue q = fullQueue(N);
        Integer[] ints = new Integer[N];
        ints = (Integer[])q.toArray(ints);
        Arrays.sort(ints);
        for(int i = 0; i < ints.length; i++)
            assertEquals(ints[i], q.poll());
    }
    
    public void testIterator(){
        PriorityQueue q = fullQueue(N);
        int i = 0;
        Iterator it = q.iterator();
        while(it.hasNext()) {
            assertTrue(q.contains(it.next()));
            ++i;
        }
        assertEquals(i, N);
    }

    public void testIteratorRemove () {

        final PriorityQueue q = new PriorityQueue(3);

        q.add(new Integer(2));
        q.add(new Integer(1));
        q.add(new Integer(3));

        Iterator it = q.iterator();
        it.next();
        it.remove();

        it = q.iterator();
        assertEquals(it.next(), new Integer(2));
        assertEquals(it.next(), new Integer(3));
        assertFalse(it.hasNext());
    }


    public void testToString(){
        PriorityQueue q = fullQueue(N);
        String s = q.toString();
        for (int i = 0; i < N; ++i) {
            assertTrue(s.indexOf(String.valueOf(i)) >= 0);
        }
    }        

}
Revision:	1.1
Committed:	Sun Aug 31 19:24:55 2003 UTC (20 years, 8 months ago) by dl
Branch:	MAIN
Log Message:	First check-in of tests to be in tck
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by members of JCP JSR-166 Expert Group and released to the
3			* public domain. Use, modify, and redistribute this code in any way
4			* without acknowledgement. Other contributors include Andrew Wright,
5			* Jeffrey Hayes, Pat Fischer, Mike Judd.
6			*/
7
8			import junit.framework.*;
9			import java.util.*;
10			import java.util.concurrent.*;
11
12			public class PriorityQueueTest extends TestCase {
13
14			private static final int N = 10;
15			private static final long SHORT_DELAY_MS = 100;
16			private static final long MEDIUM_DELAY_MS = 1000;
17			private static final long LONG_DELAY_MS = 10000;
18
19			public static void main(String[] args) {
20			junit.textui.TestRunner.run (suite());
21			}
22
23			public static Test suite() {
24			return new TestSuite(PriorityQueueTest.class);
25			}
26
27			static class MyReverseComparator implements Comparator {
28			public int compare(Object x, Object y) {
29			int i = ((Integer)x).intValue();
30			int j = ((Integer)y).intValue();
31			if (i < j) return 1;
32			if (i > j) return -1;
33			return 0;
34			}
35			}
36
37
38			/**
39			* Create a queue of given size containing consecutive
40			* Integers 0 ... n.
41			*/
42			private PriorityQueue fullQueue(int n) {
43			PriorityQueue q = new PriorityQueue(n);
44			assertTrue(q.isEmpty());
45			for(int i = n-1; i >= 0; i-=2)
46			assertTrue(q.offer(new Integer(i)));
47			for(int i = (n & 1); i < n; i+=2)
48			assertTrue(q.offer(new Integer(i)));
49			assertFalse(q.isEmpty());
50			assertEquals(n, q.size());
51			return q;
52			}
53
54			public void testConstructor1(){
55			assertEquals(0, new PriorityQueue(N).size());
56			}
57
58			public void testConstructor2(){
59			try {
60			PriorityQueue q = new PriorityQueue(0);
61			fail("Cannot make zero-sized");
62			}
63			catch (IllegalArgumentException success) {}
64			}
65
66			public void testConstructor3() {
67
68			try {
69			PriorityQueue q = new PriorityQueue((Collection)null);
70			fail("Cannot make from null collection");
71			}
72			catch (NullPointerException success) {}
73			}
74
75			public void testConstructor4(){
76			try {
77			Integer[] ints = new Integer[N];
78			PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
79			fail("Cannot make with null elements");
80			}
81			catch (NullPointerException success) {}
82			}
83
84			public void testConstructor5(){
85			try {
86			Integer[] ints = new Integer[N];
87			for (int i = 0; i < N-1; ++i)
88			ints[i] = new Integer(i);
89			PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
90			fail("Cannot make with null elements");
91			}
92			catch (NullPointerException success) {}
93			}
94
95			public void testConstructor6(){
96			try {
97			Integer[] ints = new Integer[N];
98			for (int i = 0; i < N; ++i)
99			ints[i] = new Integer(i);
100			PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
101			for (int i = 0; i < N; ++i)
102			assertEquals(ints[i], q.poll());
103			}
104			finally {}
105			}
106
107			public void testConstructor7(){
108			try {
109			PriorityQueue q = new PriorityQueue(N, new MyReverseComparator());
110			Integer[] ints = new Integer[N];
111			for (int i = 0; i < N; ++i)
112			ints[i] = new Integer(i);
113			q.addAll(Arrays.asList(ints));
114			for (int i = N-1; i >= 0; --i)
115			assertEquals(ints[i], q.poll());
116			}
117			finally {}
118			}
119
120			public void testEmpty() {
121			PriorityQueue q = new PriorityQueue(2);
122			assertTrue(q.isEmpty());
123			q.add(new Integer(1));
124			assertFalse(q.isEmpty());
125			q.add(new Integer(2));
126			q.remove();
127			q.remove();
128			assertTrue(q.isEmpty());
129			}
130
131			public void testSize() {
132			PriorityQueue q = fullQueue(N);
133			for (int i = 0; i < N; ++i) {
134			assertEquals(N-i, q.size());
135			q.remove();
136			}
137			for (int i = 0; i < N; ++i) {
138			assertEquals(i, q.size());
139			q.add(new Integer(i));
140			}
141			}
142
143			public void testOfferNull(){
144			try {
145			PriorityQueue q = new PriorityQueue(1);
146			q.offer(null);
147			fail("should throw NPE");
148			} catch (NullPointerException success) { }
149			}
150
151			public void testOffer() {
152			PriorityQueue q = new PriorityQueue(1);
153			assertTrue(q.offer(new Integer(0)));
154			assertTrue(q.offer(new Integer(1)));
155			}
156
157			public void testOfferNonComparable() {
158			try {
159			PriorityQueue q = new PriorityQueue(1);
160			q.offer(new Object());
161			q.offer(new Object());
162			q.offer(new Object());
163			fail("should throw CCE");
164			}
165			catch(ClassCastException success) {}
166			}
167
168			public void testAdd(){
169			PriorityQueue q = new PriorityQueue(N);
170			for (int i = 0; i < N; ++i) {
171			assertEquals(i, q.size());
172			assertTrue(q.add(new Integer(i)));
173			}
174			}
175
176			public void testAddAll1(){
177			try {
178			PriorityQueue q = new PriorityQueue(1);
179			q.addAll(null);
180			fail("Cannot add null collection");
181			}
182			catch (NullPointerException success) {}
183			}
184			public void testAddAll2(){
185			try {
186			PriorityQueue q = new PriorityQueue(N);
187			Integer[] ints = new Integer[N];
188			q.addAll(Arrays.asList(ints));
189			fail("Cannot add null elements");
190			}
191			catch (NullPointerException success) {}
192			}
193			public void testAddAll3(){
194			try {
195			PriorityQueue q = new PriorityQueue(N);
196			Integer[] ints = new Integer[N];
197			for (int i = 0; i < N-1; ++i)
198			ints[i] = new Integer(i);
199			q.addAll(Arrays.asList(ints));
200			fail("Cannot add null elements");
201			}
202			catch (NullPointerException success) {}
203			}
204
205			public void testAddAll5(){
206			try {
207			Integer[] empty = new Integer[0];
208			Integer[] ints = new Integer[N];
209			for (int i = 0; i < N; ++i)
210			ints[i] = new Integer(N-1-i);
211			PriorityQueue q = new PriorityQueue(N);
212			assertFalse(q.addAll(Arrays.asList(empty)));
213			assertTrue(q.addAll(Arrays.asList(ints)));
214			for (int i = 0; i < N; ++i)
215			assertEquals(new Integer(i), q.poll());
216			}
217			finally {}
218			}
219
220			public void testPoll(){
221			PriorityQueue q = fullQueue(N);
222			for (int i = 0; i < N; ++i) {
223			assertEquals(i, ((Integer)q.poll()).intValue());
224			}
225			assertNull(q.poll());
226			}
227
228			public void testPeek(){
229			PriorityQueue q = fullQueue(N);
230			for (int i = 0; i < N; ++i) {
231			assertEquals(i, ((Integer)q.peek()).intValue());
232			q.poll();
233			assertTrue(q.peek() == null \|\|
234			i != ((Integer)q.peek()).intValue());
235			}
236			assertNull(q.peek());
237			}
238
239			public void testElement(){
240			PriorityQueue q = fullQueue(N);
241			for (int i = 0; i < N; ++i) {
242			assertEquals(i, ((Integer)q.element()).intValue());
243			q.poll();
244			}
245			try {
246			q.element();
247			fail("no such element");
248			}
249			catch (NoSuchElementException success) {}
250			}
251
252			public void testRemove(){
253			PriorityQueue q = fullQueue(N);
254			for (int i = 0; i < N; ++i) {
255			assertEquals(i, ((Integer)q.remove()).intValue());
256			}
257			try {
258			q.remove();
259			fail("remove should throw");
260			} catch (NoSuchElementException success){
261			}
262			}
263
264			public void testRemoveElement(){
265			PriorityQueue q = fullQueue(N);
266			for (int i = 1; i < N; i+=2) {
267			assertTrue(q.remove(new Integer(i)));
268			}
269			for (int i = 0; i < N; i+=2) {
270			assertTrue(q.remove(new Integer(i)));
271			assertFalse(q.remove(new Integer(i+1)));
272			}
273			assert(q.isEmpty());
274			}
275
276			public void testContains(){
277			PriorityQueue q = fullQueue(N);
278			for (int i = 0; i < N; ++i) {
279			assertTrue(q.contains(new Integer(i)));
280			q.poll();
281			assertFalse(q.contains(new Integer(i)));
282			}
283			}
284
285			public void testClear(){
286			PriorityQueue q = fullQueue(N);
287			q.clear();
288			assertTrue(q.isEmpty());
289			assertEquals(0, q.size());
290			q.add(new Integer(1));
291			assertFalse(q.isEmpty());
292			q.clear();
293			assertTrue(q.isEmpty());
294			}
295
296			public void testContainsAll(){
297			PriorityQueue q = fullQueue(N);
298			PriorityQueue p = new PriorityQueue(N);
299			for (int i = 0; i < N; ++i) {
300			assertTrue(q.containsAll(p));
301			assertFalse(p.containsAll(q));
302			p.add(new Integer(i));
303			}
304			assertTrue(p.containsAll(q));
305			}
306
307			public void testRetainAll(){
308			PriorityQueue q = fullQueue(N);
309			PriorityQueue p = fullQueue(N);
310			for (int i = 0; i < N; ++i) {
311			boolean changed = q.retainAll(p);
312			if (i == 0)
313			assertFalse(changed);
314			else
315			assertTrue(changed);
316
317			assertTrue(q.containsAll(p));
318			assertEquals(N-i, q.size());
319			p.remove();
320			}
321			}
322
323			public void testRemoveAll(){
324			for (int i = 1; i < N; ++i) {
325			PriorityQueue q = fullQueue(N);
326			PriorityQueue p = fullQueue(i);
327			assertTrue(q.removeAll(p));
328			assertEquals(N-i, q.size());
329			for (int j = 0; j < i; ++j) {
330			Integer I = (Integer)(p.remove());
331			assertFalse(q.contains(I));
332			}
333			}
334			}
335
336			public void testToArray(){
337			PriorityQueue q = fullQueue(N);
338			Object[] o = q.toArray();
339			Arrays.sort(o);
340			for(int i = 0; i < o.length; i++)
341			assertEquals(o[i], q.poll());
342			}
343
344			public void testToArray2(){
345			PriorityQueue q = fullQueue(N);
346			Integer[] ints = new Integer[N];
347			ints = (Integer[])q.toArray(ints);
348			Arrays.sort(ints);
349			for(int i = 0; i < ints.length; i++)
350			assertEquals(ints[i], q.poll());
351			}
352
353			public void testIterator(){
354			PriorityQueue q = fullQueue(N);
355			int i = 0;
356			Iterator it = q.iterator();
357			while(it.hasNext()) {
358			assertTrue(q.contains(it.next()));
359			++i;
360			}
361			assertEquals(i, N);
362			}
363
364			public void testIteratorRemove () {
365
366			final PriorityQueue q = new PriorityQueue(3);
367
368			q.add(new Integer(2));
369			q.add(new Integer(1));
370			q.add(new Integer(3));
371
372			Iterator it = q.iterator();
373			it.next();
374			it.remove();
375
376			it = q.iterator();
377			assertEquals(it.next(), new Integer(2));
378			assertEquals(it.next(), new Integer(3));
379			assertFalse(it.hasNext());
380			}
381
382
383			public void testToString(){
384			PriorityQueue q = fullQueue(N);
385			String s = q.toString();
386			for (int i = 0; i < N; ++i) {
387			assertTrue(s.indexOf(String.valueOf(i)) >= 0);
388			}
389			}
390
391			}