/[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.46 - (show annotations)
Sat Mar 11 18:20:47 2017 UTC (2 years, 5 months ago) by jsr166
Branch: MAIN
Changes since 1.45: +1 -1 lines
make some methods static as suggested by errorprone [MethodCanBeStatic]

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

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