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