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.*;
import java.io.*;

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)));
        }
        assertTrue(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);
        }
    }        

    public void testSerialization() {
        PriorityQueue q = fullQueue(N);
        try {
            ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
            ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
            out.writeObject(q);
            out.close();

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