/[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.49 - (show annotations)
Fri Jun 22 00:04:58 2018 UTC (14 months ago) by jsr166
Branch: MAIN
CVS Tags: HEAD
Changes since 1.48: +1 -1 lines
sync upstream changes

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[] a = q.toArray();
362 assertSame(Object[].class, a.getClass());
363 for (Object o : a)
364 assertSame(o, q.poll());
365 assertTrue(q.isEmpty());
366 }
367
368 /**
369 * toArray(a) contains all elements in FIFO order
370 */
371 public void testToArray2() {
372 LinkedList<Integer> q = populatedQueue(SIZE);
373 Integer[] ints = new Integer[SIZE];
374 Integer[] array = q.toArray(ints);
375 assertSame(ints, array);
376 for (Integer o : ints)
377 assertSame(o, q.poll());
378 assertTrue(q.isEmpty());
379 }
380
381 /**
382 * toArray(null) throws NullPointerException
383 */
384 public void testToArray_NullArg() {
385 LinkedList l = new LinkedList();
386 l.add(new Object());
387 try {
388 l.toArray((Object[])null);
389 shouldThrow();
390 } catch (NullPointerException success) {}
391 }
392
393 /**
394 * toArray(incompatible array type) throws ArrayStoreException
395 */
396 public void testToArray1_BadArg() {
397 LinkedList l = new LinkedList();
398 l.add(new Integer(5));
399 try {
400 l.toArray(new String[10]);
401 shouldThrow();
402 } catch (ArrayStoreException success) {}
403 }
404
405 /**
406 * iterator iterates through all elements
407 */
408 public void testIterator() {
409 LinkedList q = populatedQueue(SIZE);
410 Iterator it = q.iterator();
411 int i;
412 for (i = 0; it.hasNext(); i++)
413 assertTrue(q.contains(it.next()));
414 assertEquals(i, SIZE);
415 assertIteratorExhausted(it);
416 }
417
418 /**
419 * iterator of empty collection has no elements
420 */
421 public void testEmptyIterator() {
422 assertIteratorExhausted(new LinkedList().iterator());
423 }
424
425 /**
426 * iterator ordering is FIFO
427 */
428 public void testIteratorOrdering() {
429 final LinkedList q = new LinkedList();
430 q.add(new Integer(1));
431 q.add(new Integer(2));
432 q.add(new Integer(3));
433 int k = 0;
434 for (Iterator it = q.iterator(); it.hasNext();) {
435 assertEquals(++k, it.next());
436 }
437
438 assertEquals(3, k);
439 }
440
441 /**
442 * iterator.remove removes current element
443 */
444 public void testIteratorRemove() {
445 final LinkedList q = new LinkedList();
446 q.add(new Integer(1));
447 q.add(new Integer(2));
448 q.add(new Integer(3));
449 Iterator it = q.iterator();
450 assertEquals(1, it.next());
451 it.remove();
452 it = q.iterator();
453 assertEquals(2, it.next());
454 assertEquals(3, it.next());
455 assertFalse(it.hasNext());
456 }
457
458 /**
459 * Descending iterator iterates through all elements
460 */
461 public void testDescendingIterator() {
462 LinkedList q = populatedQueue(SIZE);
463 int i = 0;
464 Iterator it = q.descendingIterator();
465 while (it.hasNext()) {
466 assertTrue(q.contains(it.next()));
467 ++i;
468 }
469 assertEquals(i, SIZE);
470 assertFalse(it.hasNext());
471 try {
472 it.next();
473 shouldThrow();
474 } catch (NoSuchElementException success) {}
475 }
476
477 /**
478 * Descending iterator ordering is reverse FIFO
479 */
480 public void testDescendingIteratorOrdering() {
481 final LinkedList q = new LinkedList();
482 q.add(new Integer(3));
483 q.add(new Integer(2));
484 q.add(new Integer(1));
485 int k = 0;
486 for (Iterator it = q.descendingIterator(); it.hasNext();) {
487 assertEquals(++k, it.next());
488 }
489
490 assertEquals(3, k);
491 }
492
493 /**
494 * descendingIterator.remove removes current element
495 */
496 public void testDescendingIteratorRemove() {
497 final LinkedList q = new LinkedList();
498 q.add(three);
499 q.add(two);
500 q.add(one);
501 Iterator it = q.descendingIterator();
502 it.next();
503 it.remove();
504 it = q.descendingIterator();
505 assertSame(it.next(), two);
506 assertSame(it.next(), three);
507 assertFalse(it.hasNext());
508 }
509
510 /**
511 * toString contains toStrings of elements
512 */
513 public void testToString() {
514 LinkedList q = populatedQueue(SIZE);
515 String s = q.toString();
516 for (int i = 0; i < SIZE; ++i) {
517 assertTrue(s.contains(String.valueOf(i)));
518 }
519 }
520
521 /**
522 * peek returns element inserted with addFirst
523 */
524 public void testAddFirst() {
525 LinkedList q = populatedQueue(3);
526 q.addFirst(four);
527 assertSame(four, q.peek());
528 }
529
530 /**
531 * peekFirst returns element inserted with push
532 */
533 public void testPush() {
534 LinkedList q = populatedQueue(3);
535 q.push(four);
536 assertSame(four, q.peekFirst());
537 }
538
539 /**
540 * pop removes next element, or throws NSEE if empty
541 */
542 public void testPop() {
543 LinkedList q = populatedQueue(SIZE);
544 for (int i = 0; i < SIZE; ++i) {
545 assertEquals(i, q.pop());
546 }
547 try {
548 q.pop();
549 shouldThrow();
550 } catch (NoSuchElementException success) {}
551 }
552
553 /**
554 * OfferFirst succeeds
555 */
556 public void testOfferFirst() {
557 LinkedList q = new LinkedList();
558 assertTrue(q.offerFirst(new Integer(0)));
559 assertTrue(q.offerFirst(new Integer(1)));
560 }
561
562 /**
563 * OfferLast succeeds
564 */
565 public void testOfferLast() {
566 LinkedList q = new LinkedList();
567 assertTrue(q.offerLast(new Integer(0)));
568 assertTrue(q.offerLast(new Integer(1)));
569 }
570
571 /**
572 * pollLast succeeds unless empty
573 */
574 public void testPollLast() {
575 LinkedList q = populatedQueue(SIZE);
576 for (int i = SIZE - 1; i >= 0; --i) {
577 assertEquals(i, q.pollLast());
578 }
579 assertNull(q.pollLast());
580 }
581
582 /**
583 * peekFirst returns next element, or null if empty
584 */
585 public void testPeekFirst() {
586 LinkedList q = populatedQueue(SIZE);
587 for (int i = 0; i < SIZE; ++i) {
588 assertEquals(i, q.peekFirst());
589 assertEquals(i, q.pollFirst());
590 assertTrue(q.peekFirst() == null ||
591 !q.peekFirst().equals(i));
592 }
593 assertNull(q.peekFirst());
594 }
595
596 /**
597 * peekLast returns next element, or null if empty
598 */
599 public void testPeekLast() {
600 LinkedList q = populatedQueue(SIZE);
601 for (int i = SIZE - 1; i >= 0; --i) {
602 assertEquals(i, q.peekLast());
603 assertEquals(i, q.pollLast());
604 assertTrue(q.peekLast() == null ||
605 !q.peekLast().equals(i));
606 }
607 assertNull(q.peekLast());
608 }
609
610 public void testFirstElement() {
611 LinkedList q = populatedQueue(SIZE);
612 for (int i = 0; i < SIZE; ++i) {
613 assertEquals(i, q.getFirst());
614 assertEquals(i, q.pollFirst());
615 }
616 try {
617 q.getFirst();
618 shouldThrow();
619 } catch (NoSuchElementException success) {}
620 }
621
622 /**
623 * getLast returns next element, or throws NSEE if empty
624 */
625 public void testLastElement() {
626 LinkedList q = populatedQueue(SIZE);
627 for (int i = SIZE - 1; i >= 0; --i) {
628 assertEquals(i, q.getLast());
629 assertEquals(i, q.pollLast());
630 }
631 try {
632 q.getLast();
633 shouldThrow();
634 } catch (NoSuchElementException success) {}
635 assertNull(q.peekLast());
636 }
637
638 /**
639 * removeFirstOccurrence(x) removes x and returns true if present
640 */
641 public void testRemoveFirstOccurrence() {
642 LinkedList q = populatedQueue(SIZE);
643 for (int i = 1; i < SIZE; i += 2) {
644 assertTrue(q.removeFirstOccurrence(new Integer(i)));
645 }
646 for (int i = 0; i < SIZE; i += 2) {
647 assertTrue(q.removeFirstOccurrence(new Integer(i)));
648 assertFalse(q.removeFirstOccurrence(new Integer(i + 1)));
649 }
650 assertTrue(q.isEmpty());
651 }
652
653 /**
654 * removeLastOccurrence(x) removes x and returns true if present
655 */
656 public void testRemoveLastOccurrence() {
657 LinkedList q = populatedQueue(SIZE);
658 for (int i = 1; i < SIZE; i += 2) {
659 assertTrue(q.removeLastOccurrence(new Integer(i)));
660 }
661 for (int i = 0; i < SIZE; i += 2) {
662 assertTrue(q.removeLastOccurrence(new Integer(i)));
663 assertFalse(q.removeLastOccurrence(new Integer(i + 1)));
664 }
665 assertTrue(q.isEmpty());
666 }
667
668 }

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