/[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.41 - (show annotations)
Sun Oct 16 20:44:18 2016 UTC (2 years, 10 months ago) by jsr166
Branch: MAIN
Changes since 1.40: +3 -1 lines
improve populatedFoo methods

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

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