/[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.34 - (show annotations)
Wed Dec 31 20:17:39 2014 UTC (4 years, 7 months ago) by jsr166
Branch: MAIN
Changes since 1.33: +2 -2 lines
coding style

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

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