/[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.36 - (show annotations)
Sun Feb 22 04:34:44 2015 UTC (4 years, 6 months ago) by jsr166
Branch: MAIN
Changes since 1.35: +1 -1 lines
unused variable cleanup

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

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