1/*
2 * Written by Doug Lea with assistance from members of JCP JSR-166
3 * Expert Group and released to the public domain, as explained at
4 * http://creativecommons.org/publicdomain/zero/1.0/
5 * Other contributors include Andrew Wright, Jeffrey Hayes,
6 * Pat Fisher, Mike Judd.
7 */
8
9package jsr166;
10
11import java.util.Arrays;
12import java.util.Collection;
13import java.util.Comparator;
14import java.util.Iterator;
15import java.util.NoSuchElementException;
16import java.util.PriorityQueue;
17import java.util.Queue;
18
19import junit.framework.Test;
20import junit.framework.TestSuite;
21
22public class PriorityQueueTest extends JSR166TestCase {
23    // android-note: Removed because the CTS runner does a bad job of
24    // retrying tests that have suite() declarations.
25    //
26    // public static void main(String[] args) {
27    //     main(suite(), args);
28    // }
29    // public static Test suite() {
30    //     return new TestSuite(PriorityQueueTest.class);
31    // }
32
33    static class MyReverseComparator implements Comparator {
34        public int compare(Object x, Object y) {
35            return ((Comparable)y).compareTo(x);
36        }
37    }
38
39    /**
40     * Returns a new queue of given size containing consecutive
41     * Integers 0 ... n.
42     */
43    private PriorityQueue<Integer> populatedQueue(int n) {
44        PriorityQueue<Integer> q = new PriorityQueue<Integer>(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    /**
56     * A new queue has unbounded capacity
57     */
58    public void testConstructor1() {
59        assertEquals(0, new PriorityQueue(SIZE).size());
60    }
61
62    /**
63     * Constructor throws IAE if capacity argument nonpositive
64     */
65    public void testConstructor2() {
66        try {
67            new PriorityQueue(0);
68            shouldThrow();
69        } catch (IllegalArgumentException success) {}
70    }
71
72    /**
73     * Initializing from null Collection throws NPE
74     */
75    public void testConstructor3() {
76        try {
77            new PriorityQueue((Collection)null);
78            shouldThrow();
79        } catch (NullPointerException success) {}
80    }
81
82    /**
83     * Initializing from Collection of null elements throws NPE
84     */
85    public void testConstructor4() {
86        try {
87            new PriorityQueue(Arrays.asList(new Integer[SIZE]));
88            shouldThrow();
89        } catch (NullPointerException success) {}
90    }
91
92    /**
93     * Initializing from Collection with some null elements throws NPE
94     */
95    public void testConstructor5() {
96        Integer[] ints = new Integer[SIZE];
97        for (int i = 0; i < SIZE - 1; ++i)
98            ints[i] = new Integer(i);
99        try {
100            new PriorityQueue(Arrays.asList(ints));
101            shouldThrow();
102        } catch (NullPointerException success) {}
103    }
104
105    /**
106     * Queue contains all elements of collection used to initialize
107     */
108    public void testConstructor6() {
109        Integer[] ints = new Integer[SIZE];
110        for (int i = 0; i < SIZE; ++i)
111            ints[i] = new Integer(i);
112        PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
113        for (int i = 0; i < SIZE; ++i)
114            assertEquals(ints[i], q.poll());
115    }
116
117    /**
118     * The comparator used in constructor is used
119     */
120    public void testConstructor7() {
121        MyReverseComparator cmp = new MyReverseComparator();
122        PriorityQueue q = new PriorityQueue(SIZE, cmp);
123        assertEquals(cmp, q.comparator());
124        Integer[] ints = new Integer[SIZE];
125        for (int i = 0; i < SIZE; ++i)
126            ints[i] = new Integer(i);
127        q.addAll(Arrays.asList(ints));
128        for (int i = SIZE - 1; i >= 0; --i)
129            assertEquals(ints[i], q.poll());
130    }
131
132    /**
133     * isEmpty is true before add, false after
134     */
135    public void testEmpty() {
136        PriorityQueue q = new PriorityQueue(2);
137        assertTrue(q.isEmpty());
138        q.add(new Integer(1));
139        assertFalse(q.isEmpty());
140        q.add(new Integer(2));
141        q.remove();
142        q.remove();
143        assertTrue(q.isEmpty());
144    }
145
146    /**
147     * size changes when elements added and removed
148     */
149    public void testSize() {
150        PriorityQueue q = populatedQueue(SIZE);
151        for (int i = 0; i < SIZE; ++i) {
152            assertEquals(SIZE - i, q.size());
153            q.remove();
154        }
155        for (int i = 0; i < SIZE; ++i) {
156            assertEquals(i, q.size());
157            q.add(new Integer(i));
158        }
159    }
160
161    /**
162     * offer(null) throws NPE
163     */
164    public void testOfferNull() {
165        PriorityQueue q = new PriorityQueue(1);
166        try {
167            q.offer(null);
168            shouldThrow();
169        } catch (NullPointerException success) {}
170    }
171
172    /**
173     * add(null) throws NPE
174     */
175    public void testAddNull() {
176        PriorityQueue q = new PriorityQueue(1);
177        try {
178            q.add(null);
179            shouldThrow();
180        } catch (NullPointerException success) {}
181    }
182
183    /**
184     * Offer of comparable element succeeds
185     */
186    public void testOffer() {
187        PriorityQueue q = new PriorityQueue(1);
188        assertTrue(q.offer(zero));
189        assertTrue(q.offer(one));
190    }
191
192    /**
193     * Offer of non-Comparable throws CCE
194     */
195    public void testOfferNonComparable() {
196        PriorityQueue q = new PriorityQueue(1);
197        try {
198            q.offer(new Object());
199            q.offer(new Object());
200            shouldThrow();
201        } catch (ClassCastException success) {}
202    }
203
204    /**
205     * add of comparable succeeds
206     */
207    public void testAdd() {
208        PriorityQueue q = new PriorityQueue(SIZE);
209        for (int i = 0; i < SIZE; ++i) {
210            assertEquals(i, q.size());
211            assertTrue(q.add(new Integer(i)));
212        }
213    }
214
215    /**
216     * addAll(null) throws NPE
217     */
218    public void testAddAll1() {
219        PriorityQueue q = new PriorityQueue(1);
220        try {
221            q.addAll(null);
222            shouldThrow();
223        } catch (NullPointerException success) {}
224    }
225
226    /**
227     * addAll of a collection with null elements throws NPE
228     */
229    public void testAddAll2() {
230        PriorityQueue q = new PriorityQueue(SIZE);
231        try {
232            q.addAll(Arrays.asList(new Integer[SIZE]));
233            shouldThrow();
234        } catch (NullPointerException success) {}
235    }
236
237    /**
238     * addAll of a collection with any null elements throws NPE after
239     * possibly adding some elements
240     */
241    public void testAddAll3() {
242        PriorityQueue q = new PriorityQueue(SIZE);
243        Integer[] ints = new Integer[SIZE];
244        for (int i = 0; i < SIZE - 1; ++i)
245            ints[i] = new Integer(i);
246        try {
247            q.addAll(Arrays.asList(ints));
248            shouldThrow();
249        } catch (NullPointerException success) {}
250    }
251
252    /**
253     * Queue contains all elements of successful addAll
254     */
255    public void testAddAll5() {
256        Integer[] empty = new Integer[0];
257        Integer[] ints = new Integer[SIZE];
258        for (int i = 0; i < SIZE; ++i)
259            ints[i] = new Integer(SIZE - 1 - i);
260        PriorityQueue q = new PriorityQueue(SIZE);
261        assertFalse(q.addAll(Arrays.asList(empty)));
262        assertTrue(q.addAll(Arrays.asList(ints)));
263        for (int i = 0; i < SIZE; ++i)
264            assertEquals(new Integer(i), q.poll());
265    }
266
267    /**
268     * poll succeeds unless empty
269     */
270    public void testPoll() {
271        PriorityQueue q = populatedQueue(SIZE);
272        for (int i = 0; i < SIZE; ++i) {
273            assertEquals(i, q.poll());
274        }
275        assertNull(q.poll());
276    }
277
278    /**
279     * peek returns next element, or null if empty
280     */
281    public void testPeek() {
282        PriorityQueue q = populatedQueue(SIZE);
283        for (int i = 0; i < SIZE; ++i) {
284            assertEquals(i, q.peek());
285            assertEquals(i, q.poll());
286            assertTrue(q.peek() == null ||
287                       !q.peek().equals(i));
288        }
289        assertNull(q.peek());
290    }
291
292    /**
293     * element returns next element, or throws NSEE if empty
294     */
295    public void testElement() {
296        PriorityQueue q = populatedQueue(SIZE);
297        for (int i = 0; i < SIZE; ++i) {
298            assertEquals(i, q.element());
299            assertEquals(i, q.poll());
300        }
301        try {
302            q.element();
303            shouldThrow();
304        } catch (NoSuchElementException success) {}
305    }
306
307    /**
308     * remove removes next element, or throws NSEE if empty
309     */
310    public void testRemove() {
311        PriorityQueue q = populatedQueue(SIZE);
312        for (int i = 0; i < SIZE; ++i) {
313            assertEquals(i, q.remove());
314        }
315        try {
316            q.remove();
317            shouldThrow();
318        } catch (NoSuchElementException success) {}
319    }
320
321    /**
322     * remove(x) removes x and returns true if present
323     */
324    public void testRemoveElement() {
325        PriorityQueue q = populatedQueue(SIZE);
326        for (int i = 1; i < SIZE; i += 2) {
327            assertTrue(q.contains(i));
328            assertTrue(q.remove(i));
329            assertFalse(q.contains(i));
330            assertTrue(q.contains(i - 1));
331        }
332        for (int i = 0; i < SIZE; i += 2) {
333            assertTrue(q.contains(i));
334            assertTrue(q.remove(i));
335            assertFalse(q.contains(i));
336            assertFalse(q.remove(i + 1));
337            assertFalse(q.contains(i + 1));
338        }
339        assertTrue(q.isEmpty());
340    }
341
342    /**
343     * contains(x) reports true when elements added but not yet removed
344     */
345    public void testContains() {
346        PriorityQueue q = populatedQueue(SIZE);
347        for (int i = 0; i < SIZE; ++i) {
348            assertTrue(q.contains(new Integer(i)));
349            q.poll();
350            assertFalse(q.contains(new Integer(i)));
351        }
352    }
353
354    /**
355     * clear removes all elements
356     */
357    public void testClear() {
358        PriorityQueue q = populatedQueue(SIZE);
359        q.clear();
360        assertTrue(q.isEmpty());
361        assertEquals(0, q.size());
362        q.add(new Integer(1));
363        assertFalse(q.isEmpty());
364        q.clear();
365        assertTrue(q.isEmpty());
366    }
367
368    /**
369     * containsAll(c) is true when c contains a subset of elements
370     */
371    public void testContainsAll() {
372        PriorityQueue q = populatedQueue(SIZE);
373        PriorityQueue p = new PriorityQueue(SIZE);
374        for (int i = 0; i < SIZE; ++i) {
375            assertTrue(q.containsAll(p));
376            assertFalse(p.containsAll(q));
377            p.add(new Integer(i));
378        }
379        assertTrue(p.containsAll(q));
380    }
381
382    /**
383     * retainAll(c) retains only those elements of c and reports true if changed
384     */
385    public void testRetainAll() {
386        PriorityQueue q = populatedQueue(SIZE);
387        PriorityQueue p = populatedQueue(SIZE);
388        for (int i = 0; i < SIZE; ++i) {
389            boolean changed = q.retainAll(p);
390            if (i == 0)
391                assertFalse(changed);
392            else
393                assertTrue(changed);
394
395            assertTrue(q.containsAll(p));
396            assertEquals(SIZE - i, q.size());
397            p.remove();
398        }
399    }
400
401    /**
402     * removeAll(c) removes only those elements of c and reports true if changed
403     */
404    public void testRemoveAll() {
405        for (int i = 1; i < SIZE; ++i) {
406            PriorityQueue q = populatedQueue(SIZE);
407            PriorityQueue p = populatedQueue(i);
408            assertTrue(q.removeAll(p));
409            assertEquals(SIZE - i, q.size());
410            for (int j = 0; j < i; ++j) {
411                Integer x = (Integer)(p.remove());
412                assertFalse(q.contains(x));
413            }
414        }
415    }
416
417    /**
418     * toArray contains all elements
419     */
420    public void testToArray() {
421        PriorityQueue q = populatedQueue(SIZE);
422        Object[] o = q.toArray();
423        Arrays.sort(o);
424        for (int i = 0; i < o.length; i++)
425            assertSame(o[i], q.poll());
426    }
427
428    /**
429     * toArray(a) contains all elements
430     */
431    public void testToArray2() {
432        PriorityQueue<Integer> q = populatedQueue(SIZE);
433        Integer[] ints = new Integer[SIZE];
434        Integer[] array = q.toArray(ints);
435        assertSame(ints, array);
436        Arrays.sort(ints);
437        for (int i = 0; i < ints.length; i++)
438            assertSame(ints[i], q.poll());
439    }
440
441    /**
442     * iterator iterates through all elements
443     */
444    public void testIterator() {
445        PriorityQueue q = populatedQueue(SIZE);
446        Iterator it = q.iterator();
447        int i;
448        for (i = 0; it.hasNext(); i++)
449            assertTrue(q.contains(it.next()));
450        assertEquals(i, SIZE);
451        assertIteratorExhausted(it);
452    }
453
454    /**
455     * iterator of empty collection has no elements
456     */
457    public void testEmptyIterator() {
458        assertIteratorExhausted(new PriorityQueue().iterator());
459    }
460
461    /**
462     * iterator.remove removes current element
463     */
464    public void testIteratorRemove() {
465        final PriorityQueue q = new PriorityQueue(3);
466        q.add(new Integer(2));
467        q.add(new Integer(1));
468        q.add(new Integer(3));
469
470        Iterator it = q.iterator();
471        it.next();
472        it.remove();
473
474        it = q.iterator();
475        assertEquals(it.next(), new Integer(2));
476        assertEquals(it.next(), new Integer(3));
477        assertFalse(it.hasNext());
478    }
479
480    /**
481     * toString contains toStrings of elements
482     */
483    public void testToString() {
484        PriorityQueue q = populatedQueue(SIZE);
485        String s = q.toString();
486        for (int i = 0; i < SIZE; ++i) {
487            assertTrue(s.contains(String.valueOf(i)));
488        }
489    }
490
491    /**
492     * A deserialized serialized queue has same elements
493     */
494    public void testSerialization() throws Exception {
495        Queue x = populatedQueue(SIZE);
496        Queue y = serialClone(x);
497
498        assertNotSame(x, y);
499        assertEquals(x.size(), y.size());
500        while (!x.isEmpty()) {
501            assertFalse(y.isEmpty());
502            assertEquals(x.remove(), y.remove());
503        }
504        assertTrue(y.isEmpty());
505    }
506}
507