/[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.16 - (show annotations)
Sun Nov 22 18:57:17 2009 UTC (9 years, 9 months ago) by jsr166
Branch: MAIN
Changes since 1.15: +35 -37 lines
use autoboxing judiciously for readability

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

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