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

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