[cvs] / jsr166 / src / test / tck / PriorityQueueTest.java Repository:
ViewVC logotype

Annotation of /jsr166/src/test/tck/PriorityQueueTest.java

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.44 - (view) (download)

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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8