/[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.43 - (show annotations)
Mon Nov 14 23:57:55 2016 UTC (2 years, 9 months ago) by jsr166
Branch: MAIN
Changes since 1.42: +9 -2 lines
add LinkedList subList tests

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

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