ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/LinkedListTest.java
(Generate patch)

Comparing jsr166/src/test/tck/LinkedListTest.java (file contents):
Revision 1.14 by jsr166, Sat Nov 21 02:39:41 2009 UTC vs.
Revision 1.47 by jsr166, Tue Apr 3 05:49:43 2018 UTC

# Line 1 | Line 1
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/licenses/publicdomain
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 junit.framework.*;
10 < import java.util.*;
11 < import java.util.concurrent.*;
9 > import java.util.Arrays;
10 > import java.util.Collection;
11 > import java.util.Iterator;
12 > import java.util.LinkedList;
13 > import java.util.List;
14 > import java.util.NoSuchElementException;
15 > import java.util.concurrent.ThreadLocalRandom;
16 >
17 > import junit.framework.Test;
18  
19   public class LinkedListTest extends JSR166TestCase {
20      public static void main(String[] args) {
21 <        junit.textui.TestRunner.run (suite());
21 >        main(suite(), args);
22      }
23  
24      public static Test suite() {
25 <        return new TestSuite(LinkedListTest.class);
25 >        class Implementation implements CollectionImplementation {
26 >            public Class<?> klazz() { return LinkedList.class; }
27 >            public List emptyCollection() { return new LinkedList(); }
28 >            public Object makeElement(int i) { return i; }
29 >            public boolean isConcurrent() { return false; }
30 >            public boolean permitsNulls() { return true; }
31 >        }
32 >        class SubListImplementation extends Implementation {
33 >            public List emptyCollection() {
34 >                List list = super.emptyCollection();
35 >                ThreadLocalRandom rnd = ThreadLocalRandom.current();
36 >                if (rnd.nextBoolean())
37 >                    list.add(makeElement(rnd.nextInt()));
38 >                int i = rnd.nextInt(list.size() + 1);
39 >                return list.subList(i, i);
40 >            }
41 >        }
42 >        return newTestSuite(
43 >                LinkedListTest.class,
44 >                CollectionTest.testSuite(new Implementation()),
45 >                CollectionTest.testSuite(new SubListImplementation()));
46      }
47  
48      /**
49 <     * Create a queue of given size containing consecutive
50 <     * Integers 0 ... n.
49 >     * Returns a new queue of given size containing consecutive
50 >     * Integers 0 ... n - 1.
51       */
52 <    private LinkedList populatedQueue(int n) {
53 <        LinkedList q = new LinkedList();
52 >    private static LinkedList<Integer> populatedQueue(int n) {
53 >        LinkedList<Integer> q = new LinkedList<>();
54          assertTrue(q.isEmpty());
55          for (int i = 0; i < n; ++i)
56              assertTrue(q.offer(new Integer(i)));
57          assertFalse(q.isEmpty());
58          assertEquals(n, q.size());
59 +        assertEquals((Integer) 0, q.peekFirst());
60 +        assertEquals((Integer) (n - 1), q.peekLast());
61          return q;
62      }
63  
# Line 45 | Line 73 | public class LinkedListTest extends JSR1
73       */
74      public void testConstructor3() {
75          try {
76 <            LinkedList q = new LinkedList((Collection)null);
76 >            new LinkedList((Collection)null);
77              shouldThrow();
78          } catch (NullPointerException success) {}
79      }
# Line 56 | Line 84 | public class LinkedListTest extends JSR1
84      public void testConstructor6() {
85          Integer[] ints = new Integer[SIZE];
86          for (int i = 0; i < SIZE; ++i)
87 <            ints[i] = new Integer(i);
87 >            ints[i] = i;
88          LinkedList q = new LinkedList(Arrays.asList(ints));
89          for (int i = 0; i < SIZE; ++i)
90              assertEquals(ints[i], q.poll());
# Line 82 | Line 110 | public class LinkedListTest extends JSR1
110      public void testSize() {
111          LinkedList q = populatedQueue(SIZE);
112          for (int i = 0; i < SIZE; ++i) {
113 <            assertEquals(SIZE-i, q.size());
113 >            assertEquals(SIZE - i, q.size());
114              q.remove();
115          }
116          for (int i = 0; i < SIZE; ++i) {
# Line 97 | Line 125 | public class LinkedListTest extends JSR1
125      public void testOfferNull() {
126          LinkedList q = new LinkedList();
127          q.offer(null);
128 +        assertNull(q.get(0));
129 +        assertTrue(q.contains(null));
130      }
131  
132      /**
# Line 123 | Line 153 | public class LinkedListTest extends JSR1
153       * addAll(null) throws NPE
154       */
155      public void testAddAll1() {
156 +        LinkedList q = new LinkedList();
157          try {
127            LinkedList q = new LinkedList();
158              q.addAll(null);
159              shouldThrow();
160          } catch (NullPointerException success) {}
# Line 137 | Line 167 | public class LinkedListTest extends JSR1
167          Integer[] empty = new Integer[0];
168          Integer[] ints = new Integer[SIZE];
169          for (int i = 0; i < SIZE; ++i)
170 <            ints[i] = new Integer(i);
170 >            ints[i] = i;
171          LinkedList q = new LinkedList();
172          assertFalse(q.addAll(Arrays.asList(empty)));
173          assertTrue(q.addAll(Arrays.asList(ints)));
# Line 156 | Line 186 | public class LinkedListTest extends JSR1
186          try {
187              l.addAll(4,m);
188              shouldThrow();
189 <        } catch (IndexOutOfBoundsException  success) {}
189 >        } catch (IndexOutOfBoundsException success) {}
190      }
191  
192      /**
# Line 170 | Line 200 | public class LinkedListTest extends JSR1
200          try {
201              l.addAll(-1,m);
202              shouldThrow();
203 <        } catch (IndexOutOfBoundsException  success) {}
203 >        } catch (IndexOutOfBoundsException success) {}
204      }
205  
206      /**
207 <     *  poll succeeds unless empty
207 >     * poll succeeds unless empty
208       */
209      public void testPoll() {
210          LinkedList q = populatedQueue(SIZE);
211          for (int i = 0; i < SIZE; ++i) {
212 <            assertEquals(i, ((Integer)q.poll()).intValue());
212 >            assertEquals(i, q.poll());
213          }
214          assertNull(q.poll());
215      }
216  
217      /**
218 <     *  peek returns next element, or null if empty
218 >     * peek returns next element, or null if empty
219       */
220      public void testPeek() {
221          LinkedList q = populatedQueue(SIZE);
222          for (int i = 0; i < SIZE; ++i) {
223 <            assertEquals(i, ((Integer)q.peek()).intValue());
224 <            q.poll();
223 >            assertEquals(i, q.peek());
224 >            assertEquals(i, q.poll());
225              assertTrue(q.peek() == null ||
226 <                       i != ((Integer)q.peek()).intValue());
226 >                       !q.peek().equals(i));
227          }
228          assertNull(q.peek());
229      }
# Line 204 | Line 234 | public class LinkedListTest extends JSR1
234      public void testElement() {
235          LinkedList q = populatedQueue(SIZE);
236          for (int i = 0; i < SIZE; ++i) {
237 <            assertEquals(i, ((Integer)q.element()).intValue());
238 <            q.poll();
237 >            assertEquals(i, q.element());
238 >            assertEquals(i, q.poll());
239          }
240          try {
241              q.element();
# Line 214 | Line 244 | public class LinkedListTest extends JSR1
244      }
245  
246      /**
247 <     *  remove removes next element, or throws NSEE if empty
247 >     * remove removes next element, or throws NSEE if empty
248       */
249      public void testRemove() {
250          LinkedList q = populatedQueue(SIZE);
251          for (int i = 0; i < SIZE; ++i) {
252 <            assertEquals(i, ((Integer)q.remove()).intValue());
252 >            assertEquals(i, q.remove());
253          }
254          try {
255              q.remove();
# Line 232 | Line 262 | public class LinkedListTest extends JSR1
262       */
263      public void testRemoveElement() {
264          LinkedList q = populatedQueue(SIZE);
265 <        for (int i = 1; i < SIZE; i+=2) {
266 <            assertTrue(q.remove(new Integer(i)));
267 <        }
268 <        for (int i = 0; i < SIZE; i+=2) {
269 <            assertTrue(q.remove(new Integer(i)));
270 <            assertFalse(q.remove(new Integer(i+1)));
265 >        for (int i = 1; i < SIZE; i += 2) {
266 >            assertTrue(q.contains(i));
267 >            assertTrue(q.remove((Integer)i));
268 >            assertFalse(q.contains(i));
269 >            assertTrue(q.contains(i - 1));
270 >        }
271 >        for (int i = 0; i < SIZE; i += 2) {
272 >            assertTrue(q.contains(i));
273 >            assertTrue(q.remove((Integer)i));
274 >            assertFalse(q.contains(i));
275 >            assertFalse(q.remove((Integer)(i + 1)));
276 >            assertFalse(q.contains(i + 1));
277          }
278          assertTrue(q.isEmpty());
279      }
# Line 262 | Line 298 | public class LinkedListTest extends JSR1
298          q.clear();
299          assertTrue(q.isEmpty());
300          assertEquals(0, q.size());
301 <        q.add(new Integer(1));
301 >        assertTrue(q.add(new Integer(1)));
302          assertFalse(q.isEmpty());
303          q.clear();
304          assertTrue(q.isEmpty());
# Line 277 | Line 313 | public class LinkedListTest extends JSR1
313          for (int i = 0; i < SIZE; ++i) {
314              assertTrue(q.containsAll(p));
315              assertFalse(p.containsAll(q));
316 <            p.add(new Integer(i));
316 >            assertTrue(p.add(new Integer(i)));
317          }
318          assertTrue(p.containsAll(q));
319      }
# Line 296 | Line 332 | public class LinkedListTest extends JSR1
332                  assertTrue(changed);
333  
334              assertTrue(q.containsAll(p));
335 <            assertEquals(SIZE-i, q.size());
335 >            assertEquals(SIZE - i, q.size());
336              p.remove();
337          }
338      }
# Line 309 | Line 345 | public class LinkedListTest extends JSR1
345              LinkedList q = populatedQueue(SIZE);
346              LinkedList p = populatedQueue(i);
347              assertTrue(q.removeAll(p));
348 <            assertEquals(SIZE-i, q.size());
348 >            assertEquals(SIZE - i, q.size());
349              for (int j = 0; j < i; ++j) {
350 <                Integer I = (Integer)(p.remove());
351 <                assertFalse(q.contains(I));
350 >                Integer x = (Integer)(p.remove());
351 >                assertFalse(q.contains(x));
352              }
353          }
354      }
355  
356      /**
357 <     *  toArray contains all elements
357 >     * toArray contains all elements in FIFO order
358       */
359      public void testToArray() {
360          LinkedList q = populatedQueue(SIZE);
361          Object[] o = q.toArray();
326        Arrays.sort(o);
362          for (int i = 0; i < o.length; i++)
363 <            assertEquals(o[i], q.poll());
363 >            assertSame(o[i], q.poll());
364      }
365  
366      /**
367 <     *  toArray(a) contains all elements
367 >     * toArray(a) contains all elements in FIFO order
368       */
369      public void testToArray2() {
370 <        LinkedList q = populatedQueue(SIZE);
370 >        LinkedList<Integer> q = populatedQueue(SIZE);
371          Integer[] ints = new Integer[SIZE];
372 <        ints = (Integer[])q.toArray(ints);
373 <        Arrays.sort(ints);
372 >        Integer[] array = q.toArray(ints);
373 >        assertSame(ints, array);
374          for (int i = 0; i < ints.length; i++)
375 <            assertEquals(ints[i], q.poll());
375 >            assertSame(ints[i], q.poll());
376      }
377  
378      /**
379 <     * toArray(null) throws NPE
379 >     * toArray(null) throws NullPointerException
380       */
381 <    public void testToArray_BadArg() {
381 >    public void testToArray_NullArg() {
382 >        LinkedList l = new LinkedList();
383 >        l.add(new Object());
384          try {
385 <            LinkedList l = new LinkedList();
349 <            l.add(new Object());
350 <            Object o[] = l.toArray(null);
385 >            l.toArray(null);
386              shouldThrow();
387          } catch (NullPointerException success) {}
388      }
389  
390      /**
391 <     * toArray with incompatable aray type throws CCE
391 >     * toArray(incompatible array type) throws ArrayStoreException
392       */
393      public void testToArray1_BadArg() {
394 +        LinkedList l = new LinkedList();
395 +        l.add(new Integer(5));
396          try {
397 <            LinkedList l = new LinkedList();
361 <            l.add(new Integer(5));
362 <            Object o[] = l.toArray(new String[10] );
397 >            l.toArray(new String[10]);
398              shouldThrow();
399          } catch (ArrayStoreException success) {}
400      }
401  
402      /**
403 <     *  iterator iterates through all elements
403 >     * iterator iterates through all elements
404       */
405      public void testIterator() {
406          LinkedList q = populatedQueue(SIZE);
372        int i = 0;
407          Iterator it = q.iterator();
408 <        while (it.hasNext()) {
408 >        int i;
409 >        for (i = 0; it.hasNext(); i++)
410              assertTrue(q.contains(it.next()));
376            ++i;
377        }
411          assertEquals(i, SIZE);
412 +        assertIteratorExhausted(it);
413 +    }
414 +
415 +    /**
416 +     * iterator of empty collection has no elements
417 +     */
418 +    public void testEmptyIterator() {
419 +        assertIteratorExhausted(new LinkedList().iterator());
420      }
421  
422      /**
423 <     *  iterator ordering is FIFO
423 >     * iterator ordering is FIFO
424       */
425      public void testIteratorOrdering() {
426          final LinkedList q = new LinkedList();
# Line 388 | Line 429 | public class LinkedListTest extends JSR1
429          q.add(new Integer(3));
430          int k = 0;
431          for (Iterator it = q.iterator(); it.hasNext();) {
432 <            int i = ((Integer)(it.next())).intValue();
392 <            assertEquals(++k, i);
432 >            assertEquals(++k, it.next());
433          }
434  
435          assertEquals(3, k);
# Line 398 | Line 438 | public class LinkedListTest extends JSR1
438      /**
439       * iterator.remove removes current element
440       */
441 <    public void testIteratorRemove () {
441 >    public void testIteratorRemove() {
442          final LinkedList q = new LinkedList();
443          q.add(new Integer(1));
444          q.add(new Integer(2));
445          q.add(new Integer(3));
446          Iterator it = q.iterator();
447 <        it.next();
447 >        assertEquals(1, it.next());
448          it.remove();
449          it = q.iterator();
450 <        assertEquals(it.next(), new Integer(2));
451 <        assertEquals(it.next(), new Integer(3));
450 >        assertEquals(2, it.next());
451 >        assertEquals(3, it.next());
452          assertFalse(it.hasNext());
453      }
454  
455      /**
456 <     *  Descending iterator iterates through all elements
456 >     * Descending iterator iterates through all elements
457       */
458      public void testDescendingIterator() {
459          LinkedList q = populatedQueue(SIZE);
# Line 432 | Line 472 | public class LinkedListTest extends JSR1
472      }
473  
474      /**
475 <     *  Descending iterator ordering is reverse FIFO
475 >     * Descending iterator ordering is reverse FIFO
476       */
477      public void testDescendingIteratorOrdering() {
478          final LinkedList q = new LinkedList();
# Line 441 | Line 481 | public class LinkedListTest extends JSR1
481          q.add(new Integer(1));
482          int k = 0;
483          for (Iterator it = q.descendingIterator(); it.hasNext();) {
484 <            int i = ((Integer)(it.next())).intValue();
445 <            assertEquals(++k, i);
484 >            assertEquals(++k, it.next());
485          }
486  
487          assertEquals(3, k);
# Line 451 | Line 490 | public class LinkedListTest extends JSR1
490      /**
491       * descendingIterator.remove removes current element
492       */
493 <    public void testDescendingIteratorRemove () {
493 >    public void testDescendingIteratorRemove() {
494          final LinkedList q = new LinkedList();
495 <        q.add(new Integer(3));
496 <        q.add(new Integer(2));
497 <        q.add(new Integer(1));
495 >        q.add(three);
496 >        q.add(two);
497 >        q.add(one);
498          Iterator it = q.descendingIterator();
499          it.next();
500          it.remove();
501          it = q.descendingIterator();
502 <        assertEquals(it.next(), new Integer(2));
503 <        assertEquals(it.next(), new Integer(3));
502 >        assertSame(it.next(), two);
503 >        assertSame(it.next(), three);
504          assertFalse(it.hasNext());
505      }
506  
468
507      /**
508       * toString contains toStrings of elements
509       */
# Line 473 | Line 511 | public class LinkedListTest extends JSR1
511          LinkedList q = populatedQueue(SIZE);
512          String s = q.toString();
513          for (int i = 0; i < SIZE; ++i) {
514 <            assertTrue(s.indexOf(String.valueOf(i)) >= 0);
514 >            assertTrue(s.contains(String.valueOf(i)));
515          }
516      }
517  
# Line 483 | Line 521 | public class LinkedListTest extends JSR1
521      public void testAddFirst() {
522          LinkedList q = populatedQueue(3);
523          q.addFirst(four);
524 <        assertEquals(four,q.peek());
524 >        assertSame(four, q.peek());
525      }
526  
527      /**
# Line 491 | Line 529 | public class LinkedListTest extends JSR1
529       */
530      public void testPush() {
531          LinkedList q = populatedQueue(3);
494        q.pollLast();
532          q.push(four);
533 <        assertEquals(four,q.peekFirst());
533 >        assertSame(four, q.peekFirst());
534      }
535  
536      /**
537 <     *  pop removes next element, or throws NSEE if empty
537 >     * pop removes next element, or throws NSEE if empty
538       */
539      public void testPop() {
540          LinkedList q = populatedQueue(SIZE);
541          for (int i = 0; i < SIZE; ++i) {
542 <            assertEquals(i, ((Integer)q.pop()).intValue());
542 >            assertEquals(i, q.pop());
543          }
544          try {
545              q.pop();
# Line 529 | Line 566 | public class LinkedListTest extends JSR1
566      }
567  
568      /**
569 <     *  pollLast succeeds unless empty
569 >     * pollLast succeeds unless empty
570       */
571      public void testPollLast() {
572          LinkedList q = populatedQueue(SIZE);
573 <        for (int i = SIZE-1; i >= 0; --i) {
574 <            assertEquals(i, ((Integer)q.pollLast()).intValue());
573 >        for (int i = SIZE - 1; i >= 0; --i) {
574 >            assertEquals(i, q.pollLast());
575          }
576          assertNull(q.pollLast());
577      }
578  
579      /**
580 <     *  peekFirst returns next element, or null if empty
580 >     * peekFirst returns next element, or null if empty
581       */
582      public void testPeekFirst() {
583          LinkedList q = populatedQueue(SIZE);
584          for (int i = 0; i < SIZE; ++i) {
585 <            assertEquals(i, ((Integer)q.peekFirst()).intValue());
586 <            q.pollFirst();
585 >            assertEquals(i, q.peekFirst());
586 >            assertEquals(i, q.pollFirst());
587              assertTrue(q.peekFirst() == null ||
588 <                       i != ((Integer)q.peekFirst()).intValue());
588 >                       !q.peekFirst().equals(i));
589          }
590          assertNull(q.peekFirst());
591      }
592  
556
593      /**
594 <     *  peekLast returns next element, or null if empty
594 >     * peekLast returns next element, or null if empty
595       */
596      public void testPeekLast() {
597          LinkedList q = populatedQueue(SIZE);
598 <        for (int i = SIZE-1; i >= 0; --i) {
599 <            assertEquals(i, ((Integer)q.peekLast()).intValue());
600 <            q.pollLast();
598 >        for (int i = SIZE - 1; i >= 0; --i) {
599 >            assertEquals(i, q.peekLast());
600 >            assertEquals(i, q.pollLast());
601              assertTrue(q.peekLast() == null ||
602 <                       i != ((Integer)q.peekLast()).intValue());
602 >                       !q.peekLast().equals(i));
603          }
604          assertNull(q.peekLast());
605      }
# Line 571 | Line 607 | public class LinkedListTest extends JSR1
607      public void testFirstElement() {
608          LinkedList q = populatedQueue(SIZE);
609          for (int i = 0; i < SIZE; ++i) {
610 <            assertEquals(i, ((Integer)q.getFirst()).intValue());
611 <            q.pollFirst();
610 >            assertEquals(i, q.getFirst());
611 >            assertEquals(i, q.pollFirst());
612          }
613          try {
614              q.getFirst();
# Line 581 | Line 617 | public class LinkedListTest extends JSR1
617      }
618  
619      /**
620 <     *  getLast returns next element, or throws NSEE if empty
620 >     * getLast returns next element, or throws NSEE if empty
621       */
622      public void testLastElement() {
623          LinkedList q = populatedQueue(SIZE);
624 <        for (int i = SIZE-1; i >= 0; --i) {
625 <            assertEquals(i, ((Integer)q.getLast()).intValue());
626 <            q.pollLast();
624 >        for (int i = SIZE - 1; i >= 0; --i) {
625 >            assertEquals(i, q.getLast());
626 >            assertEquals(i, q.pollLast());
627          }
628          try {
629              q.getLast();
# Line 601 | Line 637 | public class LinkedListTest extends JSR1
637       */
638      public void testRemoveFirstOccurrence() {
639          LinkedList q = populatedQueue(SIZE);
640 <        for (int i = 1; i < SIZE; i+=2) {
640 >        for (int i = 1; i < SIZE; i += 2) {
641              assertTrue(q.removeFirstOccurrence(new Integer(i)));
642          }
643 <        for (int i = 0; i < SIZE; i+=2) {
643 >        for (int i = 0; i < SIZE; i += 2) {
644              assertTrue(q.removeFirstOccurrence(new Integer(i)));
645 <            assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
645 >            assertFalse(q.removeFirstOccurrence(new Integer(i + 1)));
646          }
647          assertTrue(q.isEmpty());
648      }
# Line 616 | Line 652 | public class LinkedListTest extends JSR1
652       */
653      public void testRemoveLastOccurrence() {
654          LinkedList q = populatedQueue(SIZE);
655 <        for (int i = 1; i < SIZE; i+=2) {
655 >        for (int i = 1; i < SIZE; i += 2) {
656              assertTrue(q.removeLastOccurrence(new Integer(i)));
657          }
658 <        for (int i = 0; i < SIZE; i+=2) {
658 >        for (int i = 0; i < SIZE; i += 2) {
659              assertTrue(q.removeLastOccurrence(new Integer(i)));
660 <            assertFalse(q.removeLastOccurrence(new Integer(i+1)));
660 >            assertFalse(q.removeLastOccurrence(new Integer(i + 1)));
661          }
662          assertTrue(q.isEmpty());
663      }

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines