ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/PriorityQueueTest.java
(Generate patch)

Comparing jsr166/src/test/tck/PriorityQueueTest.java (file contents):
Revision 1.13 by jsr166, Sat Nov 21 10:25:05 2009 UTC vs.
Revision 1.34 by jsr166, Fri May 15 18:21:19 2015 UTC

# Line 1 | Line 1
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/licenses/publicdomain
4 > * http://creativecommons.org/publicdomain/zero/1.0/
5   * Other contributors include Andrew Wright, Jeffrey Hayes,
6   * Pat Fisher, Mike Judd.
7   */
8  
9 < import junit.framework.*;
10 < import java.util.*;
11 < import java.util.concurrent.*;
12 < import java.io.*;
9 > import java.util.Arrays;
10 > import java.util.Collection;
11 > import java.util.Comparator;
12 > import java.util.Iterator;
13 > import java.util.NoSuchElementException;
14 > import java.util.PriorityQueue;
15 > import java.util.Queue;
16 >
17 > import junit.framework.Test;
18 > import junit.framework.TestSuite;
19  
20   public class PriorityQueueTest extends JSR166TestCase {
21      public static void main(String[] args) {
22 <        junit.textui.TestRunner.run (suite());
22 >        main(suite(), args);
23      }
24      public static Test suite() {
25          return new TestSuite(PriorityQueueTest.class);
# Line 21 | Line 27 | public class PriorityQueueTest extends J
27  
28      static class MyReverseComparator implements Comparator {
29          public int compare(Object x, Object y) {
30 <            int i = ((Integer)x).intValue();
25 <            int j = ((Integer)y).intValue();
26 <            if (i < j) return 1;
27 <            if (i > j) return -1;
28 <            return 0;
30 >            return ((Comparable)y).compareTo(x);
31          }
32      }
33  
34      /**
35 <     * Create a queue of given size containing consecutive
35 >     * Returns a new queue of given size containing consecutive
36       * Integers 0 ... n.
37       */
38 <    private PriorityQueue populatedQueue(int n) {
39 <        PriorityQueue q = new PriorityQueue(n);
38 >    private PriorityQueue<Integer> populatedQueue(int n) {
39 >        PriorityQueue<Integer> q = new PriorityQueue<Integer>(n);
40          assertTrue(q.isEmpty());
41 <        for (int i = n-1; i >= 0; i-=2)
41 >        for (int i = n-1; i >= 0; i -= 2)
42              assertTrue(q.offer(new Integer(i)));
43 <        for (int i = (n & 1); i < n; i+=2)
43 >        for (int i = (n & 1); i < n; i += 2)
44              assertTrue(q.offer(new Integer(i)));
45          assertFalse(q.isEmpty());
46          assertEquals(n, q.size());
# Line 57 | Line 59 | public class PriorityQueueTest extends J
59       */
60      public void testConstructor2() {
61          try {
62 <            PriorityQueue q = new PriorityQueue(0);
62 >            new PriorityQueue(0);
63              shouldThrow();
64          } catch (IllegalArgumentException success) {}
65      }
# Line 67 | Line 69 | public class PriorityQueueTest extends J
69       */
70      public void testConstructor3() {
71          try {
72 <            PriorityQueue q = new PriorityQueue((Collection)null);
72 >            new PriorityQueue((Collection)null);
73              shouldThrow();
74          } catch (NullPointerException success) {}
75      }
# Line 77 | Line 79 | public class PriorityQueueTest extends J
79       */
80      public void testConstructor4() {
81          try {
82 <            Integer[] ints = new Integer[SIZE];
81 <            PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
82 >            new PriorityQueue(Arrays.asList(new Integer[SIZE]));
83              shouldThrow();
84          } catch (NullPointerException success) {}
85      }
# Line 87 | Line 88 | public class PriorityQueueTest extends J
88       * Initializing from Collection with some null elements throws NPE
89       */
90      public void testConstructor5() {
91 +        Integer[] ints = new Integer[SIZE];
92 +        for (int i = 0; i < SIZE-1; ++i)
93 +            ints[i] = new Integer(i);
94          try {
95 <            Integer[] ints = new Integer[SIZE];
92 <            for (int i = 0; i < SIZE-1; ++i)
93 <                ints[i] = new Integer(i);
94 <            PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
95 >            new PriorityQueue(Arrays.asList(ints));
96              shouldThrow();
97          } catch (NullPointerException success) {}
98      }
# Line 100 | Line 101 | public class PriorityQueueTest extends J
101       * Queue contains all elements of collection used to initialize
102       */
103      public void testConstructor6() {
104 <        try {
105 <            Integer[] ints = new Integer[SIZE];
106 <            for (int i = 0; i < SIZE; ++i)
107 <                ints[i] = new Integer(i);
108 <            PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
109 <            for (int i = 0; i < SIZE; ++i)
109 <                assertEquals(ints[i], q.poll());
110 <        }
111 <        finally {}
104 >        Integer[] ints = new Integer[SIZE];
105 >        for (int i = 0; i < SIZE; ++i)
106 >            ints[i] = new Integer(i);
107 >        PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
108 >        for (int i = 0; i < SIZE; ++i)
109 >            assertEquals(ints[i], q.poll());
110      }
111  
112      /**
113       * The comparator used in constructor is used
114       */
115      public void testConstructor7() {
116 <        try {
117 <            MyReverseComparator cmp = new MyReverseComparator();
118 <            PriorityQueue q = new PriorityQueue(SIZE, cmp);
119 <            assertEquals(cmp, q.comparator());
120 <            Integer[] ints = new Integer[SIZE];
121 <            for (int i = 0; i < SIZE; ++i)
122 <                ints[i] = new Integer(i);
123 <            q.addAll(Arrays.asList(ints));
124 <            for (int i = SIZE-1; i >= 0; --i)
127 <                assertEquals(ints[i], q.poll());
128 <        }
129 <        finally {}
116 >        MyReverseComparator cmp = new MyReverseComparator();
117 >        PriorityQueue q = new PriorityQueue(SIZE, cmp);
118 >        assertEquals(cmp, q.comparator());
119 >        Integer[] ints = new Integer[SIZE];
120 >        for (int i = 0; i < SIZE; ++i)
121 >            ints[i] = new Integer(i);
122 >        q.addAll(Arrays.asList(ints));
123 >        for (int i = SIZE-1; i >= 0; --i)
124 >            assertEquals(ints[i], q.poll());
125      }
126  
127      /**
# Line 162 | Line 157 | public class PriorityQueueTest extends J
157       * offer(null) throws NPE
158       */
159      public void testOfferNull() {
160 +        PriorityQueue q = new PriorityQueue(1);
161          try {
166 –            PriorityQueue q = new PriorityQueue(1);
162              q.offer(null);
163              shouldThrow();
164          } catch (NullPointerException success) {}
# Line 173 | Line 168 | public class PriorityQueueTest extends J
168       * add(null) throws NPE
169       */
170      public void testAddNull() {
171 +        PriorityQueue q = new PriorityQueue(1);
172          try {
177 –            PriorityQueue q = new PriorityQueue(1);
173              q.add(null);
174              shouldThrow();
175          } catch (NullPointerException success) {}
# Line 193 | Line 188 | public class PriorityQueueTest extends J
188       * Offer of non-Comparable throws CCE
189       */
190      public void testOfferNonComparable() {
191 +        PriorityQueue q = new PriorityQueue(1);
192          try {
197 –            PriorityQueue q = new PriorityQueue(1);
198 –            q.offer(new Object());
193              q.offer(new Object());
194              q.offer(new Object());
195              shouldThrow();
# Line 217 | Line 211 | public class PriorityQueueTest extends J
211       * addAll(null) throws NPE
212       */
213      public void testAddAll1() {
214 +        PriorityQueue q = new PriorityQueue(1);
215          try {
221 –            PriorityQueue q = new PriorityQueue(1);
216              q.addAll(null);
217              shouldThrow();
218          } catch (NullPointerException success) {}
219      }
220 +
221      /**
222       * addAll of a collection with null elements throws NPE
223       */
224      public void testAddAll2() {
225 +        PriorityQueue q = new PriorityQueue(SIZE);
226          try {
227 <            PriorityQueue q = new PriorityQueue(SIZE);
232 <            Integer[] ints = new Integer[SIZE];
233 <            q.addAll(Arrays.asList(ints));
227 >            q.addAll(Arrays.asList(new Integer[SIZE]));
228              shouldThrow();
229          } catch (NullPointerException success) {}
230      }
231 +
232      /**
233       * addAll of a collection with any null elements throws NPE after
234       * possibly adding some elements
235       */
236      public void testAddAll3() {
237 +        PriorityQueue q = new PriorityQueue(SIZE);
238 +        Integer[] ints = new Integer[SIZE];
239 +        for (int i = 0; i < SIZE-1; ++i)
240 +            ints[i] = new Integer(i);
241          try {
243 –            PriorityQueue q = new PriorityQueue(SIZE);
244 –            Integer[] ints = new Integer[SIZE];
245 –            for (int i = 0; i < SIZE-1; ++i)
246 –                ints[i] = new Integer(i);
242              q.addAll(Arrays.asList(ints));
243              shouldThrow();
244          } catch (NullPointerException success) {}
# Line 253 | Line 248 | public class PriorityQueueTest extends J
248       * Queue contains all elements of successful addAll
249       */
250      public void testAddAll5() {
251 <        try {
252 <            Integer[] empty = new Integer[0];
253 <            Integer[] ints = new Integer[SIZE];
254 <            for (int i = 0; i < SIZE; ++i)
255 <                ints[i] = new Integer(SIZE-1-i);
256 <            PriorityQueue q = new PriorityQueue(SIZE);
257 <            assertFalse(q.addAll(Arrays.asList(empty)));
258 <            assertTrue(q.addAll(Arrays.asList(ints)));
259 <            for (int i = 0; i < SIZE; ++i)
265 <                assertEquals(new Integer(i), q.poll());
266 <        }
267 <        finally {}
251 >        Integer[] empty = new Integer[0];
252 >        Integer[] ints = new Integer[SIZE];
253 >        for (int i = 0; i < SIZE; ++i)
254 >            ints[i] = new Integer(SIZE-1-i);
255 >        PriorityQueue q = new PriorityQueue(SIZE);
256 >        assertFalse(q.addAll(Arrays.asList(empty)));
257 >        assertTrue(q.addAll(Arrays.asList(ints)));
258 >        for (int i = 0; i < SIZE; ++i)
259 >            assertEquals(new Integer(i), q.poll());
260      }
261  
262      /**
# Line 273 | Line 265 | public class PriorityQueueTest extends J
265      public void testPoll() {
266          PriorityQueue q = populatedQueue(SIZE);
267          for (int i = 0; i < SIZE; ++i) {
268 <            assertEquals(i, ((Integer)q.poll()).intValue());
268 >            assertEquals(i, q.poll());
269          }
270          assertNull(q.poll());
271      }
# Line 284 | Line 276 | public class PriorityQueueTest extends J
276      public void testPeek() {
277          PriorityQueue q = populatedQueue(SIZE);
278          for (int i = 0; i < SIZE; ++i) {
279 <            assertEquals(i, ((Integer)q.peek()).intValue());
280 <            q.poll();
279 >            assertEquals(i, q.peek());
280 >            assertEquals(i, q.poll());
281              assertTrue(q.peek() == null ||
282 <                       i != ((Integer)q.peek()).intValue());
282 >                       !q.peek().equals(i));
283          }
284          assertNull(q.peek());
285      }
# Line 298 | Line 290 | public class PriorityQueueTest extends J
290      public void testElement() {
291          PriorityQueue q = populatedQueue(SIZE);
292          for (int i = 0; i < SIZE; ++i) {
293 <            assertEquals(i, ((Integer)q.element()).intValue());
294 <            q.poll();
293 >            assertEquals(i, q.element());
294 >            assertEquals(i, q.poll());
295          }
296          try {
297              q.element();
# Line 313 | Line 305 | public class PriorityQueueTest extends J
305      public void testRemove() {
306          PriorityQueue q = populatedQueue(SIZE);
307          for (int i = 0; i < SIZE; ++i) {
308 <            assertEquals(i, ((Integer)q.remove()).intValue());
308 >            assertEquals(i, q.remove());
309          }
310          try {
311              q.remove();
# Line 326 | Line 318 | public class PriorityQueueTest extends J
318       */
319      public void testRemoveElement() {
320          PriorityQueue q = populatedQueue(SIZE);
321 <        for (int i = 1; i < SIZE; i+=2) {
322 <            assertTrue(q.remove(new Integer(i)));
323 <        }
324 <        for (int i = 0; i < SIZE; i+=2) {
325 <            assertTrue(q.remove(new Integer(i)));
326 <            assertFalse(q.remove(new Integer(i+1)));
321 >        for (int i = 1; i < SIZE; i += 2) {
322 >            assertTrue(q.contains(i));
323 >            assertTrue(q.remove(i));
324 >            assertFalse(q.contains(i));
325 >            assertTrue(q.contains(i-1));
326 >        }
327 >        for (int i = 0; i < SIZE; i += 2) {
328 >            assertTrue(q.contains(i));
329 >            assertTrue(q.remove(i));
330 >            assertFalse(q.contains(i));
331 >            assertFalse(q.remove(i+1));
332 >            assertFalse(q.contains(i+1));
333          }
334          assertTrue(q.isEmpty());
335      }
# Line 405 | Line 403 | public class PriorityQueueTest extends J
403              assertTrue(q.removeAll(p));
404              assertEquals(SIZE-i, q.size());
405              for (int j = 0; j < i; ++j) {
406 <                Integer I = (Integer)(p.remove());
407 <                assertFalse(q.contains(I));
406 >                Integer x = (Integer)(p.remove());
407 >                assertFalse(q.contains(x));
408              }
409          }
410      }
# Line 419 | Line 417 | public class PriorityQueueTest extends J
417          Object[] o = q.toArray();
418          Arrays.sort(o);
419          for (int i = 0; i < o.length; i++)
420 <            assertEquals(o[i], q.poll());
420 >            assertSame(o[i], q.poll());
421      }
422  
423      /**
424       * toArray(a) contains all elements
425       */
426      public void testToArray2() {
427 <        PriorityQueue q = populatedQueue(SIZE);
427 >        PriorityQueue<Integer> q = populatedQueue(SIZE);
428          Integer[] ints = new Integer[SIZE];
429 <        ints = (Integer[])q.toArray(ints);
429 >        Integer[] array = q.toArray(ints);
430 >        assertSame(ints, array);
431          Arrays.sort(ints);
432          for (int i = 0; i < ints.length; i++)
433 <            assertEquals(ints[i], q.poll());
433 >            assertSame(ints[i], q.poll());
434      }
435  
436      /**
# Line 439 | Line 438 | public class PriorityQueueTest extends J
438       */
439      public void testIterator() {
440          PriorityQueue q = populatedQueue(SIZE);
442 –        int i = 0;
441          Iterator it = q.iterator();
442 <        while (it.hasNext()) {
442 >        int i;
443 >        for (i = 0; it.hasNext(); i++)
444              assertTrue(q.contains(it.next()));
446 –            ++i;
447 –        }
445          assertEquals(i, SIZE);
446 +        assertIteratorExhausted(it);
447 +    }
448 +
449 +    /**
450 +     * iterator of empty collection has no elements
451 +     */
452 +    public void testEmptyIterator() {
453 +        assertIteratorExhausted(new PriorityQueue().iterator());
454      }
455  
456      /**
457       * iterator.remove removes current element
458       */
459 <    public void testIteratorRemove () {
459 >    public void testIteratorRemove() {
460          final PriorityQueue q = new PriorityQueue(3);
461          q.add(new Integer(2));
462          q.add(new Integer(1));
# Line 467 | Line 472 | public class PriorityQueueTest extends J
472          assertFalse(it.hasNext());
473      }
474  
470 –
475      /**
476       * toString contains toStrings of elements
477       */
# Line 475 | Line 479 | public class PriorityQueueTest extends J
479          PriorityQueue q = populatedQueue(SIZE);
480          String s = q.toString();
481          for (int i = 0; i < SIZE; ++i) {
482 <            assertTrue(s.indexOf(String.valueOf(i)) >= 0);
482 >            assertTrue(s.contains(String.valueOf(i)));
483          }
484      }
485  
# Line 483 | Line 487 | public class PriorityQueueTest extends J
487       * A deserialized serialized queue has same elements
488       */
489      public void testSerialization() throws Exception {
490 <        PriorityQueue q = populatedQueue(SIZE);
491 <        ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
492 <        ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
493 <        out.writeObject(q);
494 <        out.close();
495 <
496 <        ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
497 <        ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
498 <        PriorityQueue r = (PriorityQueue)in.readObject();
499 <        assertEquals(q.size(), r.size());
496 <        while (!q.isEmpty())
497 <            assertEquals(q.remove(), r.remove());
490 >        Queue x = populatedQueue(SIZE);
491 >        Queue y = serialClone(x);
492 >
493 >        assertNotSame(x, y);
494 >        assertEquals(x.size(), y.size());
495 >        while (!x.isEmpty()) {
496 >            assertFalse(y.isEmpty());
497 >            assertEquals(x.remove(), y.remove());
498 >        }
499 >        assertTrue(y.isEmpty());
500      }
501   }

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines