/[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.30 - (show annotations)
Tue Feb 21 01:54:04 2012 UTC (7 years, 6 months ago) by jsr166
Branch: MAIN
Changes since 1.29: +1 -1 lines
use third person in javadoc first sentence

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

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