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