/[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.47 - (show annotations)
Tue Apr 3 05:49:43 2018 UTC (16 months, 3 weeks ago) by jsr166
Branch: MAIN
Changes since 1.46: +10 -3 lines
add more randomness to sublist testing

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.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 main(suite(), args);
22 }
23
24 public static Test suite() {
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 * Returns a new queue of given size containing consecutive
50 * Integers 0 ... n - 1.
51 */
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
64 /**
65 * new queue is empty
66 */
67 public void testConstructor1() {
68 assertEquals(0, new LinkedList().size());
69 }
70
71 /**
72 * Initializing from null Collection throws NPE
73 */
74 public void testConstructor3() {
75 try {
76 new LinkedList((Collection)null);
77 shouldThrow();
78 } catch (NullPointerException success) {}
79 }
80
81 /**
82 * Queue contains all elements of collection used to initialize
83 */
84 public void testConstructor6() {
85 Integer[] ints = new Integer[SIZE];
86 for (int i = 0; i < SIZE; ++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());
91 }
92
93 /**
94 * isEmpty is true before add, false after
95 */
96 public void testEmpty() {
97 LinkedList q = new LinkedList();
98 assertTrue(q.isEmpty());
99 q.add(new Integer(1));
100 assertFalse(q.isEmpty());
101 q.add(new Integer(2));
102 q.remove();
103 q.remove();
104 assertTrue(q.isEmpty());
105 }
106
107 /**
108 * size changes when elements added and removed
109 */
110 public void testSize() {
111 LinkedList q = populatedQueue(SIZE);
112 for (int i = 0; i < SIZE; ++i) {
113 assertEquals(SIZE - i, q.size());
114 q.remove();
115 }
116 for (int i = 0; i < SIZE; ++i) {
117 assertEquals(i, q.size());
118 q.add(new Integer(i));
119 }
120 }
121
122 /**
123 * offer(null) succeeds
124 */
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 /**
133 * Offer succeeds
134 */
135 public void testOffer() {
136 LinkedList q = new LinkedList();
137 assertTrue(q.offer(new Integer(0)));
138 assertTrue(q.offer(new Integer(1)));
139 }
140
141 /**
142 * add succeeds
143 */
144 public void testAdd() {
145 LinkedList q = new LinkedList();
146 for (int i = 0; i < SIZE; ++i) {
147 assertEquals(i, q.size());
148 assertTrue(q.add(new Integer(i)));
149 }
150 }
151
152 /**
153 * addAll(null) throws NPE
154 */
155 public void testAddAll1() {
156 LinkedList q = new LinkedList();
157 try {
158 q.addAll(null);
159 shouldThrow();
160 } catch (NullPointerException success) {}
161 }
162
163 /**
164 * Queue contains all elements, in traversal order, of successful addAll
165 */
166 public void testAddAll5() {
167 Integer[] empty = new Integer[0];
168 Integer[] ints = new Integer[SIZE];
169 for (int i = 0; i < SIZE; ++i)
170 ints[i] = i;
171 LinkedList q = new LinkedList();
172 assertFalse(q.addAll(Arrays.asList(empty)));
173 assertTrue(q.addAll(Arrays.asList(ints)));
174 for (int i = 0; i < SIZE; ++i)
175 assertEquals(ints[i], q.poll());
176 }
177
178 /**
179 * addAll with too large an index throws IOOBE
180 */
181 public void testAddAll2_IndexOutOfBoundsException() {
182 LinkedList l = new LinkedList();
183 l.add(new Object());
184 LinkedList m = new LinkedList();
185 m.add(new Object());
186 try {
187 l.addAll(4,m);
188 shouldThrow();
189 } catch (IndexOutOfBoundsException success) {}
190 }
191
192 /**
193 * addAll with negative index throws IOOBE
194 */
195 public void testAddAll4_BadIndex() {
196 LinkedList l = new LinkedList();
197 l.add(new Object());
198 LinkedList m = new LinkedList();
199 m.add(new Object());
200 try {
201 l.addAll(-1,m);
202 shouldThrow();
203 } catch (IndexOutOfBoundsException success) {}
204 }
205
206 /**
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, q.poll());
213 }
214 assertNull(q.poll());
215 }
216
217 /**
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, q.peek());
224 assertEquals(i, q.poll());
225 assertTrue(q.peek() == null ||
226 !q.peek().equals(i));
227 }
228 assertNull(q.peek());
229 }
230
231 /**
232 * element returns next element, or throws NSEE if empty
233 */
234 public void testElement() {
235 LinkedList q = populatedQueue(SIZE);
236 for (int i = 0; i < SIZE; ++i) {
237 assertEquals(i, q.element());
238 assertEquals(i, q.poll());
239 }
240 try {
241 q.element();
242 shouldThrow();
243 } catch (NoSuchElementException success) {}
244 }
245
246 /**
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, q.remove());
253 }
254 try {
255 q.remove();
256 shouldThrow();
257 } catch (NoSuchElementException success) {}
258 }
259
260 /**
261 * remove(x) removes x and returns true if present
262 */
263 public void testRemoveElement() {
264 LinkedList q = populatedQueue(SIZE);
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 }
280
281 /**
282 * contains(x) reports true when elements added but not yet removed
283 */
284 public void testContains() {
285 LinkedList q = populatedQueue(SIZE);
286 for (int i = 0; i < SIZE; ++i) {
287 assertTrue(q.contains(new Integer(i)));
288 q.poll();
289 assertFalse(q.contains(new Integer(i)));
290 }
291 }
292
293 /**
294 * clear removes all elements
295 */
296 public void testClear() {
297 LinkedList q = populatedQueue(SIZE);
298 q.clear();
299 assertTrue(q.isEmpty());
300 assertEquals(0, q.size());
301 assertTrue(q.add(new Integer(1)));
302 assertFalse(q.isEmpty());
303 q.clear();
304 assertTrue(q.isEmpty());
305 }
306
307 /**
308 * containsAll(c) is true when c contains a subset of elements
309 */
310 public void testContainsAll() {
311 LinkedList q = populatedQueue(SIZE);
312 LinkedList p = new LinkedList();
313 for (int i = 0; i < SIZE; ++i) {
314 assertTrue(q.containsAll(p));
315 assertFalse(p.containsAll(q));
316 assertTrue(p.add(new Integer(i)));
317 }
318 assertTrue(p.containsAll(q));
319 }
320
321 /**
322 * retainAll(c) retains only those elements of c and reports true if changed
323 */
324 public void testRetainAll() {
325 LinkedList q = populatedQueue(SIZE);
326 LinkedList p = populatedQueue(SIZE);
327 for (int i = 0; i < SIZE; ++i) {
328 boolean changed = q.retainAll(p);
329 if (i == 0)
330 assertFalse(changed);
331 else
332 assertTrue(changed);
333
334 assertTrue(q.containsAll(p));
335 assertEquals(SIZE - i, q.size());
336 p.remove();
337 }
338 }
339
340 /**
341 * removeAll(c) removes only those elements of c and reports true if changed
342 */
343 public void testRemoveAll() {
344 for (int i = 1; i < SIZE; ++i) {
345 LinkedList q = populatedQueue(SIZE);
346 LinkedList p = populatedQueue(i);
347 assertTrue(q.removeAll(p));
348 assertEquals(SIZE - i, q.size());
349 for (int j = 0; j < i; ++j) {
350 Integer x = (Integer)(p.remove());
351 assertFalse(q.contains(x));
352 }
353 }
354 }
355
356 /**
357 * toArray contains all elements in FIFO order
358 */
359 public void testToArray() {
360 LinkedList q = populatedQueue(SIZE);
361 Object[] o = q.toArray();
362 for (int i = 0; i < o.length; i++)
363 assertSame(o[i], q.poll());
364 }
365
366 /**
367 * toArray(a) contains all elements in FIFO order
368 */
369 public void testToArray2() {
370 LinkedList<Integer> q = populatedQueue(SIZE);
371 Integer[] ints = new Integer[SIZE];
372 Integer[] array = q.toArray(ints);
373 assertSame(ints, array);
374 for (int i = 0; i < ints.length; i++)
375 assertSame(ints[i], q.poll());
376 }
377
378 /**
379 * toArray(null) throws NullPointerException
380 */
381 public void testToArray_NullArg() {
382 LinkedList l = new LinkedList();
383 l.add(new Object());
384 try {
385 l.toArray(null);
386 shouldThrow();
387 } catch (NullPointerException success) {}
388 }
389
390 /**
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 l.toArray(new String[10]);
398 shouldThrow();
399 } catch (ArrayStoreException success) {}
400 }
401
402 /**
403 * iterator iterates through all elements
404 */
405 public void testIterator() {
406 LinkedList q = populatedQueue(SIZE);
407 Iterator it = q.iterator();
408 int i;
409 for (i = 0; it.hasNext(); i++)
410 assertTrue(q.contains(it.next()));
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
424 */
425 public void testIteratorOrdering() {
426 final LinkedList q = new LinkedList();
427 q.add(new Integer(1));
428 q.add(new Integer(2));
429 q.add(new Integer(3));
430 int k = 0;
431 for (Iterator it = q.iterator(); it.hasNext();) {
432 assertEquals(++k, it.next());
433 }
434
435 assertEquals(3, k);
436 }
437
438 /**
439 * iterator.remove removes current element
440 */
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 assertEquals(1, it.next());
448 it.remove();
449 it = q.iterator();
450 assertEquals(2, it.next());
451 assertEquals(3, it.next());
452 assertFalse(it.hasNext());
453 }
454
455 /**
456 * Descending iterator iterates through all elements
457 */
458 public void testDescendingIterator() {
459 LinkedList q = populatedQueue(SIZE);
460 int i = 0;
461 Iterator it = q.descendingIterator();
462 while (it.hasNext()) {
463 assertTrue(q.contains(it.next()));
464 ++i;
465 }
466 assertEquals(i, SIZE);
467 assertFalse(it.hasNext());
468 try {
469 it.next();
470 shouldThrow();
471 } catch (NoSuchElementException success) {}
472 }
473
474 /**
475 * Descending iterator ordering is reverse FIFO
476 */
477 public void testDescendingIteratorOrdering() {
478 final LinkedList q = new LinkedList();
479 q.add(new Integer(3));
480 q.add(new Integer(2));
481 q.add(new Integer(1));
482 int k = 0;
483 for (Iterator it = q.descendingIterator(); it.hasNext();) {
484 assertEquals(++k, it.next());
485 }
486
487 assertEquals(3, k);
488 }
489
490 /**
491 * descendingIterator.remove removes current element
492 */
493 public void testDescendingIteratorRemove() {
494 final LinkedList q = new LinkedList();
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 assertSame(it.next(), two);
503 assertSame(it.next(), three);
504 assertFalse(it.hasNext());
505 }
506
507 /**
508 * toString contains toStrings of elements
509 */
510 public void testToString() {
511 LinkedList q = populatedQueue(SIZE);
512 String s = q.toString();
513 for (int i = 0; i < SIZE; ++i) {
514 assertTrue(s.contains(String.valueOf(i)));
515 }
516 }
517
518 /**
519 * peek returns element inserted with addFirst
520 */
521 public void testAddFirst() {
522 LinkedList q = populatedQueue(3);
523 q.addFirst(four);
524 assertSame(four, q.peek());
525 }
526
527 /**
528 * peekFirst returns element inserted with push
529 */
530 public void testPush() {
531 LinkedList q = populatedQueue(3);
532 q.push(four);
533 assertSame(four, q.peekFirst());
534 }
535
536 /**
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, q.pop());
543 }
544 try {
545 q.pop();
546 shouldThrow();
547 } catch (NoSuchElementException success) {}
548 }
549
550 /**
551 * OfferFirst succeeds
552 */
553 public void testOfferFirst() {
554 LinkedList q = new LinkedList();
555 assertTrue(q.offerFirst(new Integer(0)));
556 assertTrue(q.offerFirst(new Integer(1)));
557 }
558
559 /**
560 * OfferLast succeeds
561 */
562 public void testOfferLast() {
563 LinkedList q = new LinkedList();
564 assertTrue(q.offerLast(new Integer(0)));
565 assertTrue(q.offerLast(new Integer(1)));
566 }
567
568 /**
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, q.pollLast());
575 }
576 assertNull(q.pollLast());
577 }
578
579 /**
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, q.peekFirst());
586 assertEquals(i, q.pollFirst());
587 assertTrue(q.peekFirst() == null ||
588 !q.peekFirst().equals(i));
589 }
590 assertNull(q.peekFirst());
591 }
592
593 /**
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, q.peekLast());
600 assertEquals(i, q.pollLast());
601 assertTrue(q.peekLast() == null ||
602 !q.peekLast().equals(i));
603 }
604 assertNull(q.peekLast());
605 }
606
607 public void testFirstElement() {
608 LinkedList q = populatedQueue(SIZE);
609 for (int i = 0; i < SIZE; ++i) {
610 assertEquals(i, q.getFirst());
611 assertEquals(i, q.pollFirst());
612 }
613 try {
614 q.getFirst();
615 shouldThrow();
616 } catch (NoSuchElementException success) {}
617 }
618
619 /**
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, q.getLast());
626 assertEquals(i, q.pollLast());
627 }
628 try {
629 q.getLast();
630 shouldThrow();
631 } catch (NoSuchElementException success) {}
632 assertNull(q.peekLast());
633 }
634
635 /**
636 * removeFirstOccurrence(x) removes x and returns true if present
637 */
638 public void testRemoveFirstOccurrence() {
639 LinkedList q = populatedQueue(SIZE);
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) {
644 assertTrue(q.removeFirstOccurrence(new Integer(i)));
645 assertFalse(q.removeFirstOccurrence(new Integer(i + 1)));
646 }
647 assertTrue(q.isEmpty());
648 }
649
650 /**
651 * removeLastOccurrence(x) removes x and returns true if present
652 */
653 public void testRemoveLastOccurrence() {
654 LinkedList q = populatedQueue(SIZE);
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) {
659 assertTrue(q.removeLastOccurrence(new Integer(i)));
660 assertFalse(q.removeLastOccurrence(new Integer(i + 1)));
661 }
662 assertTrue(q.isEmpty());
663 }
664
665 }

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