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