/[cvs]/jsr166/src/test/tck/LinkedListTest.java
ViewVC logotype

Contents of /jsr166/src/test/tck/LinkedListTest.java

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.38 - (show annotations)
Fri May 15 18:21:19 2015 UTC (4 years, 3 months ago) by jsr166
Branch: MAIN
Changes since 1.37: +3 -1 lines
try/catch block scope hygiene

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
9 import java.util.Arrays;
10 import java.util.Collection;
11 import java.util.Iterator;
12 import java.util.LinkedList;
13 import java.util.NoSuchElementException;
14
15 import junit.framework.Test;
16 import junit.framework.TestSuite;
17
18 public class LinkedListTest extends JSR166TestCase {
19 public static void main(String[] args) {
20 main(suite(), args);
21 }
22
23 public static Test suite() {
24 return new TestSuite(LinkedListTest.class);
25 }
26
27 /**
28 * Returns a new queue of given size containing consecutive
29 * Integers 0 ... n.
30 */
31 private LinkedList<Integer> populatedQueue(int n) {
32 LinkedList<Integer> q = new LinkedList<Integer>();
33 assertTrue(q.isEmpty());
34 for (int i = 0; i < n; ++i)
35 assertTrue(q.offer(new Integer(i)));
36 assertFalse(q.isEmpty());
37 assertEquals(n, q.size());
38 return q;
39 }
40
41 /**
42 * new queue is empty
43 */
44 public void testConstructor1() {
45 assertEquals(0, new LinkedList().size());
46 }
47
48 /**
49 * Initializing from null Collection throws NPE
50 */
51 public void testConstructor3() {
52 try {
53 new LinkedList((Collection)null);
54 shouldThrow();
55 } catch (NullPointerException success) {}
56 }
57
58 /**
59 * Queue contains all elements of collection used to initialize
60 */
61 public void testConstructor6() {
62 Integer[] ints = new Integer[SIZE];
63 for (int i = 0; i < SIZE; ++i)
64 ints[i] = i;
65 LinkedList q = new LinkedList(Arrays.asList(ints));
66 for (int i = 0; i < SIZE; ++i)
67 assertEquals(ints[i], q.poll());
68 }
69
70 /**
71 * isEmpty is true before add, false after
72 */
73 public void testEmpty() {
74 LinkedList q = new LinkedList();
75 assertTrue(q.isEmpty());
76 q.add(new Integer(1));
77 assertFalse(q.isEmpty());
78 q.add(new Integer(2));
79 q.remove();
80 q.remove();
81 assertTrue(q.isEmpty());
82 }
83
84 /**
85 * size changes when elements added and removed
86 */
87 public void testSize() {
88 LinkedList q = populatedQueue(SIZE);
89 for (int i = 0; i < SIZE; ++i) {
90 assertEquals(SIZE-i, q.size());
91 q.remove();
92 }
93 for (int i = 0; i < SIZE; ++i) {
94 assertEquals(i, q.size());
95 q.add(new Integer(i));
96 }
97 }
98
99 /**
100 * offer(null) succeeds
101 */
102 public void testOfferNull() {
103 LinkedList q = new LinkedList();
104 q.offer(null);
105 assertNull(q.get(0));
106 assertTrue(q.contains(null));
107 }
108
109 /**
110 * Offer succeeds
111 */
112 public void testOffer() {
113 LinkedList q = new LinkedList();
114 assertTrue(q.offer(new Integer(0)));
115 assertTrue(q.offer(new Integer(1)));
116 }
117
118 /**
119 * add succeeds
120 */
121 public void testAdd() {
122 LinkedList q = new LinkedList();
123 for (int i = 0; i < SIZE; ++i) {
124 assertEquals(i, q.size());
125 assertTrue(q.add(new Integer(i)));
126 }
127 }
128
129 /**
130 * addAll(null) throws NPE
131 */
132 public void testAddAll1() {
133 LinkedList q = new LinkedList();
134 try {
135 q.addAll(null);
136 shouldThrow();
137 } catch (NullPointerException success) {}
138 }
139
140 /**
141 * Queue contains all elements, in traversal order, of successful addAll
142 */
143 public void testAddAll5() {
144 Integer[] empty = new Integer[0];
145 Integer[] ints = new Integer[SIZE];
146 for (int i = 0; i < SIZE; ++i)
147 ints[i] = i;
148 LinkedList q = new LinkedList();
149 assertFalse(q.addAll(Arrays.asList(empty)));
150 assertTrue(q.addAll(Arrays.asList(ints)));
151 for (int i = 0; i < SIZE; ++i)
152 assertEquals(ints[i], q.poll());
153 }
154
155 /**
156 * addAll with too large an index throws IOOBE
157 */
158 public void testAddAll2_IndexOutOfBoundsException() {
159 LinkedList l = new LinkedList();
160 l.add(new Object());
161 LinkedList m = new LinkedList();
162 m.add(new Object());
163 try {
164 l.addAll(4,m);
165 shouldThrow();
166 } catch (IndexOutOfBoundsException success) {}
167 }
168
169 /**
170 * addAll with negative index throws IOOBE
171 */
172 public void testAddAll4_BadIndex() {
173 LinkedList l = new LinkedList();
174 l.add(new Object());
175 LinkedList m = new LinkedList();
176 m.add(new Object());
177 try {
178 l.addAll(-1,m);
179 shouldThrow();
180 } catch (IndexOutOfBoundsException success) {}
181 }
182
183 /**
184 * poll succeeds unless empty
185 */
186 public void testPoll() {
187 LinkedList q = populatedQueue(SIZE);
188 for (int i = 0; i < SIZE; ++i) {
189 assertEquals(i, q.poll());
190 }
191 assertNull(q.poll());
192 }
193
194 /**
195 * peek returns next element, or null if empty
196 */
197 public void testPeek() {
198 LinkedList q = populatedQueue(SIZE);
199 for (int i = 0; i < SIZE; ++i) {
200 assertEquals(i, q.peek());
201 assertEquals(i, q.poll());
202 assertTrue(q.peek() == null ||
203 !q.peek().equals(i));
204 }
205 assertNull(q.peek());
206 }
207
208 /**
209 * element returns next element, or throws NSEE if empty
210 */
211 public void testElement() {
212 LinkedList q = populatedQueue(SIZE);
213 for (int i = 0; i < SIZE; ++i) {
214 assertEquals(i, q.element());
215 assertEquals(i, q.poll());
216 }
217 try {
218 q.element();
219 shouldThrow();
220 } catch (NoSuchElementException success) {}
221 }
222
223 /**
224 * remove removes next element, or throws NSEE if empty
225 */
226 public void testRemove() {
227 LinkedList q = populatedQueue(SIZE);
228 for (int i = 0; i < SIZE; ++i) {
229 assertEquals(i, q.remove());
230 }
231 try {
232 q.remove();
233 shouldThrow();
234 } catch (NoSuchElementException success) {}
235 }
236
237 /**
238 * remove(x) removes x and returns true if present
239 */
240 public void testRemoveElement() {
241 LinkedList q = populatedQueue(SIZE);
242 for (int i = 1; i < SIZE; i += 2) {
243 assertTrue(q.contains(i));
244 assertTrue(q.remove((Integer)i));
245 assertFalse(q.contains(i));
246 assertTrue(q.contains(i-1));
247 }
248 for (int i = 0; i < SIZE; i += 2) {
249 assertTrue(q.contains(i));
250 assertTrue(q.remove((Integer)i));
251 assertFalse(q.contains(i));
252 assertFalse(q.remove((Integer)(i+1)));
253 assertFalse(q.contains(i+1));
254 }
255 assertTrue(q.isEmpty());
256 }
257
258 /**
259 * contains(x) reports true when elements added but not yet removed
260 */
261 public void testContains() {
262 LinkedList q = populatedQueue(SIZE);
263 for (int i = 0; i < SIZE; ++i) {
264 assertTrue(q.contains(new Integer(i)));
265 q.poll();
266 assertFalse(q.contains(new Integer(i)));
267 }
268 }
269
270 /**
271 * clear removes all elements
272 */
273 public void testClear() {
274 LinkedList q = populatedQueue(SIZE);
275 q.clear();
276 assertTrue(q.isEmpty());
277 assertEquals(0, q.size());
278 assertTrue(q.add(new Integer(1)));
279 assertFalse(q.isEmpty());
280 q.clear();
281 assertTrue(q.isEmpty());
282 }
283
284 /**
285 * containsAll(c) is true when c contains a subset of elements
286 */
287 public void testContainsAll() {
288 LinkedList q = populatedQueue(SIZE);
289 LinkedList p = new LinkedList();
290 for (int i = 0; i < SIZE; ++i) {
291 assertTrue(q.containsAll(p));
292 assertFalse(p.containsAll(q));
293 assertTrue(p.add(new Integer(i)));
294 }
295 assertTrue(p.containsAll(q));
296 }
297
298 /**
299 * retainAll(c) retains only those elements of c and reports true if changed
300 */
301 public void testRetainAll() {
302 LinkedList q = populatedQueue(SIZE);
303 LinkedList p = populatedQueue(SIZE);
304 for (int i = 0; i < SIZE; ++i) {
305 boolean changed = q.retainAll(p);
306 if (i == 0)
307 assertFalse(changed);
308 else
309 assertTrue(changed);
310
311 assertTrue(q.containsAll(p));
312 assertEquals(SIZE-i, q.size());
313 p.remove();
314 }
315 }
316
317 /**
318 * removeAll(c) removes only those elements of c and reports true if changed
319 */
320 public void testRemoveAll() {
321 for (int i = 1; i < SIZE; ++i) {
322 LinkedList q = populatedQueue(SIZE);
323 LinkedList p = populatedQueue(i);
324 assertTrue(q.removeAll(p));
325 assertEquals(SIZE-i, q.size());
326 for (int j = 0; j < i; ++j) {
327 Integer x = (Integer)(p.remove());
328 assertFalse(q.contains(x));
329 }
330 }
331 }
332
333 /**
334 * toArray contains all elements in FIFO order
335 */
336 public void testToArray() {
337 LinkedList q = populatedQueue(SIZE);
338 Object[] o = q.toArray();
339 for (int i = 0; i < o.length; i++)
340 assertSame(o[i], q.poll());
341 }
342
343 /**
344 * toArray(a) contains all elements in FIFO order
345 */
346 public void testToArray2() {
347 LinkedList<Integer> q = populatedQueue(SIZE);
348 Integer[] ints = new Integer[SIZE];
349 Integer[] array = q.toArray(ints);
350 assertSame(ints, array);
351 for (int i = 0; i < ints.length; i++)
352 assertSame(ints[i], q.poll());
353 }
354
355 /**
356 * toArray(null) throws NullPointerException
357 */
358 public void testToArray_NullArg() {
359 LinkedList l = new LinkedList();
360 l.add(new Object());
361 try {
362 l.toArray(null);
363 shouldThrow();
364 } catch (NullPointerException success) {}
365 }
366
367 /**
368 * toArray(incompatible array type) throws ArrayStoreException
369 */
370 public void testToArray1_BadArg() {
371 LinkedList l = new LinkedList();
372 l.add(new Integer(5));
373 try {
374 l.toArray(new String[10]);
375 shouldThrow();
376 } catch (ArrayStoreException success) {}
377 }
378
379 /**
380 * iterator iterates through all elements
381 */
382 public void testIterator() {
383 LinkedList q = populatedQueue(SIZE);
384 Iterator it = q.iterator();
385 int i;
386 for (i = 0; it.hasNext(); i++)
387 assertTrue(q.contains(it.next()));
388 assertEquals(i, SIZE);
389 assertIteratorExhausted(it);
390 }
391
392 /**
393 * iterator of empty collection has no elements
394 */
395 public void testEmptyIterator() {
396 assertIteratorExhausted(new LinkedList().iterator());
397 }
398
399 /**
400 * iterator ordering is FIFO
401 */
402 public void testIteratorOrdering() {
403 final LinkedList q = new LinkedList();
404 q.add(new Integer(1));
405 q.add(new Integer(2));
406 q.add(new Integer(3));
407 int k = 0;
408 for (Iterator it = q.iterator(); it.hasNext();) {
409 assertEquals(++k, it.next());
410 }
411
412 assertEquals(3, k);
413 }
414
415 /**
416 * iterator.remove removes current element
417 */
418 public void testIteratorRemove() {
419 final LinkedList q = new LinkedList();
420 q.add(new Integer(1));
421 q.add(new Integer(2));
422 q.add(new Integer(3));
423 Iterator it = q.iterator();
424 assertEquals(1, it.next());
425 it.remove();
426 it = q.iterator();
427 assertEquals(2, it.next());
428 assertEquals(3, it.next());
429 assertFalse(it.hasNext());
430 }
431
432 /**
433 * Descending iterator iterates through all elements
434 */
435 public void testDescendingIterator() {
436 LinkedList q = populatedQueue(SIZE);
437 int i = 0;
438 Iterator it = q.descendingIterator();
439 while (it.hasNext()) {
440 assertTrue(q.contains(it.next()));
441 ++i;
442 }
443 assertEquals(i, SIZE);
444 assertFalse(it.hasNext());
445 try {
446 it.next();
447 shouldThrow();
448 } catch (NoSuchElementException success) {}
449 }
450
451 /**
452 * Descending iterator ordering is reverse FIFO
453 */
454 public void testDescendingIteratorOrdering() {
455 final LinkedList q = new LinkedList();
456 q.add(new Integer(3));
457 q.add(new Integer(2));
458 q.add(new Integer(1));
459 int k = 0;
460 for (Iterator it = q.descendingIterator(); it.hasNext();) {
461 assertEquals(++k, it.next());
462 }
463
464 assertEquals(3, k);
465 }
466
467 /**
468 * descendingIterator.remove removes current element
469 */
470 public void testDescendingIteratorRemove() {
471 final LinkedList q = new LinkedList();
472 q.add(three);
473 q.add(two);
474 q.add(one);
475 Iterator it = q.descendingIterator();
476 it.next();
477 it.remove();
478 it = q.descendingIterator();
479 assertSame(it.next(), two);
480 assertSame(it.next(), three);
481 assertFalse(it.hasNext());
482 }
483
484 /**
485 * toString contains toStrings of elements
486 */
487 public void testToString() {
488 LinkedList q = populatedQueue(SIZE);
489 String s = q.toString();
490 for (int i = 0; i < SIZE; ++i) {
491 assertTrue(s.contains(String.valueOf(i)));
492 }
493 }
494
495 /**
496 * peek returns element inserted with addFirst
497 */
498 public void testAddFirst() {
499 LinkedList q = populatedQueue(3);
500 q.addFirst(four);
501 assertSame(four, q.peek());
502 }
503
504 /**
505 * peekFirst returns element inserted with push
506 */
507 public void testPush() {
508 LinkedList q = populatedQueue(3);
509 q.push(four);
510 assertSame(four, q.peekFirst());
511 }
512
513 /**
514 * pop removes next element, or throws NSEE if empty
515 */
516 public void testPop() {
517 LinkedList q = populatedQueue(SIZE);
518 for (int i = 0; i < SIZE; ++i) {
519 assertEquals(i, q.pop());
520 }
521 try {
522 q.pop();
523 shouldThrow();
524 } catch (NoSuchElementException success) {}
525 }
526
527 /**
528 * OfferFirst succeeds
529 */
530 public void testOfferFirst() {
531 LinkedList q = new LinkedList();
532 assertTrue(q.offerFirst(new Integer(0)));
533 assertTrue(q.offerFirst(new Integer(1)));
534 }
535
536 /**
537 * OfferLast succeeds
538 */
539 public void testOfferLast() {
540 LinkedList q = new LinkedList();
541 assertTrue(q.offerLast(new Integer(0)));
542 assertTrue(q.offerLast(new Integer(1)));
543 }
544
545 /**
546 * pollLast succeeds unless empty
547 */
548 public void testPollLast() {
549 LinkedList q = populatedQueue(SIZE);
550 for (int i = SIZE-1; i >= 0; --i) {
551 assertEquals(i, q.pollLast());
552 }
553 assertNull(q.pollLast());
554 }
555
556 /**
557 * peekFirst returns next element, or null if empty
558 */
559 public void testPeekFirst() {
560 LinkedList q = populatedQueue(SIZE);
561 for (int i = 0; i < SIZE; ++i) {
562 assertEquals(i, q.peekFirst());
563 assertEquals(i, q.pollFirst());
564 assertTrue(q.peekFirst() == null ||
565 !q.peekFirst().equals(i));
566 }
567 assertNull(q.peekFirst());
568 }
569
570 /**
571 * peekLast returns next element, or null if empty
572 */
573 public void testPeekLast() {
574 LinkedList q = populatedQueue(SIZE);
575 for (int i = SIZE-1; i >= 0; --i) {
576 assertEquals(i, q.peekLast());
577 assertEquals(i, q.pollLast());
578 assertTrue(q.peekLast() == null ||
579 !q.peekLast().equals(i));
580 }
581 assertNull(q.peekLast());
582 }
583
584 public void testFirstElement() {
585 LinkedList q = populatedQueue(SIZE);
586 for (int i = 0; i < SIZE; ++i) {
587 assertEquals(i, q.getFirst());
588 assertEquals(i, q.pollFirst());
589 }
590 try {
591 q.getFirst();
592 shouldThrow();
593 } catch (NoSuchElementException success) {}
594 }
595
596 /**
597 * getLast returns next element, or throws NSEE if empty
598 */
599 public void testLastElement() {
600 LinkedList q = populatedQueue(SIZE);
601 for (int i = SIZE-1; i >= 0; --i) {
602 assertEquals(i, q.getLast());
603 assertEquals(i, q.pollLast());
604 }
605 try {
606 q.getLast();
607 shouldThrow();
608 } catch (NoSuchElementException success) {}
609 assertNull(q.peekLast());
610 }
611
612 /**
613 * removeFirstOccurrence(x) removes x and returns true if present
614 */
615 public void testRemoveFirstOccurrence() {
616 LinkedList q = populatedQueue(SIZE);
617 for (int i = 1; i < SIZE; i += 2) {
618 assertTrue(q.removeFirstOccurrence(new Integer(i)));
619 }
620 for (int i = 0; i < SIZE; i += 2) {
621 assertTrue(q.removeFirstOccurrence(new Integer(i)));
622 assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
623 }
624 assertTrue(q.isEmpty());
625 }
626
627 /**
628 * removeLastOccurrence(x) removes x and returns true if present
629 */
630 public void testRemoveLastOccurrence() {
631 LinkedList q = populatedQueue(SIZE);
632 for (int i = 1; i < SIZE; i += 2) {
633 assertTrue(q.removeLastOccurrence(new Integer(i)));
634 }
635 for (int i = 0; i < SIZE; i += 2) {
636 assertTrue(q.removeLastOccurrence(new Integer(i)));
637 assertFalse(q.removeLastOccurrence(new Integer(i+1)));
638 }
639 assertTrue(q.isEmpty());
640 }
641
642 }

dl@cs.oswego.edu
ViewVC Help
Powered by ViewVC 1.1.27