/[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.26 - (show annotations)
Tue Mar 15 19:47:06 2011 UTC (8 years, 5 months ago) by jsr166
Branch: MAIN
CVS Tags: release-1_7_0
Changes since 1.25: +1 -1 lines
Update Creative Commons license URL in legal notices

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.*;
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<Integer> populatedQueue(int n) {
27 LinkedList<Integer> q = new LinkedList<Integer>();
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.contains(i));
237 assertTrue(q.remove((Integer)i));
238 assertFalse(q.contains(i));
239 assertTrue(q.contains(i-1));
240 }
241 for (int i = 0; i < SIZE; i+=2) {
242 assertTrue(q.contains(i));
243 assertTrue(q.remove((Integer)i));
244 assertFalse(q.contains(i));
245 assertFalse(q.remove((Integer)(i+1)));
246 assertFalse(q.contains(i+1));
247 }
248 assertTrue(q.isEmpty());
249 }
250
251 /**
252 * contains(x) reports true when elements added but not yet removed
253 */
254 public void testContains() {
255 LinkedList q = populatedQueue(SIZE);
256 for (int i = 0; i < SIZE; ++i) {
257 assertTrue(q.contains(new Integer(i)));
258 q.poll();
259 assertFalse(q.contains(new Integer(i)));
260 }
261 }
262
263 /**
264 * clear removes all elements
265 */
266 public void testClear() {
267 LinkedList q = populatedQueue(SIZE);
268 q.clear();
269 assertTrue(q.isEmpty());
270 assertEquals(0, q.size());
271 assertTrue(q.add(new Integer(1)));
272 assertFalse(q.isEmpty());
273 q.clear();
274 assertTrue(q.isEmpty());
275 }
276
277 /**
278 * containsAll(c) is true when c contains a subset of elements
279 */
280 public void testContainsAll() {
281 LinkedList q = populatedQueue(SIZE);
282 LinkedList p = new LinkedList();
283 for (int i = 0; i < SIZE; ++i) {
284 assertTrue(q.containsAll(p));
285 assertFalse(p.containsAll(q));
286 assertTrue(p.add(new Integer(i)));
287 }
288 assertTrue(p.containsAll(q));
289 }
290
291 /**
292 * retainAll(c) retains only those elements of c and reports true if changed
293 */
294 public void testRetainAll() {
295 LinkedList q = populatedQueue(SIZE);
296 LinkedList p = populatedQueue(SIZE);
297 for (int i = 0; i < SIZE; ++i) {
298 boolean changed = q.retainAll(p);
299 if (i == 0)
300 assertFalse(changed);
301 else
302 assertTrue(changed);
303
304 assertTrue(q.containsAll(p));
305 assertEquals(SIZE-i, q.size());
306 p.remove();
307 }
308 }
309
310 /**
311 * removeAll(c) removes only those elements of c and reports true if changed
312 */
313 public void testRemoveAll() {
314 for (int i = 1; i < SIZE; ++i) {
315 LinkedList q = populatedQueue(SIZE);
316 LinkedList p = populatedQueue(i);
317 assertTrue(q.removeAll(p));
318 assertEquals(SIZE-i, q.size());
319 for (int j = 0; j < i; ++j) {
320 Integer I = (Integer)(p.remove());
321 assertFalse(q.contains(I));
322 }
323 }
324 }
325
326 /**
327 * toArray contains all elements in FIFO order
328 */
329 public void testToArray() {
330 LinkedList q = populatedQueue(SIZE);
331 Object[] o = q.toArray();
332 for (int i = 0; i < o.length; i++)
333 assertSame(o[i], q.poll());
334 }
335
336 /**
337 * toArray(a) contains all elements in FIFO order
338 */
339 public void testToArray2() {
340 LinkedList<Integer> q = populatedQueue(SIZE);
341 Integer[] ints = new Integer[SIZE];
342 Integer[] array = q.toArray(ints);
343 assertSame(ints, array);
344 for (int i = 0; i < ints.length; i++)
345 assertSame(ints[i], q.poll());
346 }
347
348 /**
349 * toArray(null) throws NullPointerException
350 */
351 public void testToArray_NullArg() {
352 LinkedList l = new LinkedList();
353 l.add(new Object());
354 try {
355 l.toArray(null);
356 shouldThrow();
357 } catch (NullPointerException success) {}
358 }
359
360 /**
361 * toArray(incompatible array type) throws ArrayStoreException
362 */
363 public void testToArray1_BadArg() {
364 LinkedList l = new LinkedList();
365 l.add(new Integer(5));
366 try {
367 l.toArray(new String[10]);
368 shouldThrow();
369 } catch (ArrayStoreException success) {}
370 }
371
372 /**
373 * iterator iterates through all elements
374 */
375 public void testIterator() {
376 LinkedList q = populatedQueue(SIZE);
377 int i = 0;
378 Iterator it = q.iterator();
379 while (it.hasNext()) {
380 assertTrue(q.contains(it.next()));
381 ++i;
382 }
383 assertEquals(i, SIZE);
384 }
385
386 /**
387 * iterator ordering is FIFO
388 */
389 public void testIteratorOrdering() {
390 final LinkedList q = new LinkedList();
391 q.add(new Integer(1));
392 q.add(new Integer(2));
393 q.add(new Integer(3));
394 int k = 0;
395 for (Iterator it = q.iterator(); it.hasNext();) {
396 assertEquals(++k, it.next());
397 }
398
399 assertEquals(3, k);
400 }
401
402 /**
403 * iterator.remove removes current element
404 */
405 public void testIteratorRemove() {
406 final LinkedList q = new LinkedList();
407 q.add(new Integer(1));
408 q.add(new Integer(2));
409 q.add(new Integer(3));
410 Iterator it = q.iterator();
411 assertEquals(it.next(), 1);
412 it.remove();
413 it = q.iterator();
414 assertEquals(it.next(), 2);
415 assertEquals(it.next(), 3);
416 assertFalse(it.hasNext());
417 }
418
419 /**
420 * Descending iterator iterates through all elements
421 */
422 public void testDescendingIterator() {
423 LinkedList q = populatedQueue(SIZE);
424 int i = 0;
425 Iterator it = q.descendingIterator();
426 while (it.hasNext()) {
427 assertTrue(q.contains(it.next()));
428 ++i;
429 }
430 assertEquals(i, SIZE);
431 assertFalse(it.hasNext());
432 try {
433 it.next();
434 shouldThrow();
435 } catch (NoSuchElementException success) {}
436 }
437
438 /**
439 * Descending iterator ordering is reverse FIFO
440 */
441 public void testDescendingIteratorOrdering() {
442 final LinkedList q = new LinkedList();
443 q.add(new Integer(3));
444 q.add(new Integer(2));
445 q.add(new Integer(1));
446 int k = 0;
447 for (Iterator it = q.descendingIterator(); it.hasNext();) {
448 assertEquals(++k, it.next());
449 }
450
451 assertEquals(3, k);
452 }
453
454 /**
455 * descendingIterator.remove removes current element
456 */
457 public void testDescendingIteratorRemove() {
458 final LinkedList q = new LinkedList();
459 q.add(three);
460 q.add(two);
461 q.add(one);
462 Iterator it = q.descendingIterator();
463 it.next();
464 it.remove();
465 it = q.descendingIterator();
466 assertSame(it.next(), two);
467 assertSame(it.next(), three);
468 assertFalse(it.hasNext());
469 }
470
471
472 /**
473 * toString contains toStrings of elements
474 */
475 public void testToString() {
476 LinkedList q = populatedQueue(SIZE);
477 String s = q.toString();
478 for (int i = 0; i < SIZE; ++i) {
479 assertTrue(s.indexOf(String.valueOf(i)) >= 0);
480 }
481 }
482
483 /**
484 * peek returns element inserted with addFirst
485 */
486 public void testAddFirst() {
487 LinkedList q = populatedQueue(3);
488 q.addFirst(four);
489 assertSame(four, q.peek());
490 }
491
492 /**
493 * peekFirst returns element inserted with push
494 */
495 public void testPush() {
496 LinkedList q = populatedQueue(3);
497 q.push(four);
498 assertSame(four, q.peekFirst());
499 }
500
501 /**
502 * pop removes next element, or throws NSEE if empty
503 */
504 public void testPop() {
505 LinkedList q = populatedQueue(SIZE);
506 for (int i = 0; i < SIZE; ++i) {
507 assertEquals(i, q.pop());
508 }
509 try {
510 q.pop();
511 shouldThrow();
512 } catch (NoSuchElementException success) {}
513 }
514
515 /**
516 * OfferFirst succeeds
517 */
518 public void testOfferFirst() {
519 LinkedList q = new LinkedList();
520 assertTrue(q.offerFirst(new Integer(0)));
521 assertTrue(q.offerFirst(new Integer(1)));
522 }
523
524 /**
525 * OfferLast succeeds
526 */
527 public void testOfferLast() {
528 LinkedList q = new LinkedList();
529 assertTrue(q.offerLast(new Integer(0)));
530 assertTrue(q.offerLast(new Integer(1)));
531 }
532
533 /**
534 * pollLast succeeds unless empty
535 */
536 public void testPollLast() {
537 LinkedList q = populatedQueue(SIZE);
538 for (int i = SIZE-1; i >= 0; --i) {
539 assertEquals(i, q.pollLast());
540 }
541 assertNull(q.pollLast());
542 }
543
544 /**
545 * peekFirst returns next element, or null if empty
546 */
547 public void testPeekFirst() {
548 LinkedList q = populatedQueue(SIZE);
549 for (int i = 0; i < SIZE; ++i) {
550 assertEquals(i, q.peekFirst());
551 assertEquals(i, q.pollFirst());
552 assertTrue(q.peekFirst() == null ||
553 !q.peekFirst().equals(i));
554 }
555 assertNull(q.peekFirst());
556 }
557
558
559 /**
560 * peekLast returns next element, or null if empty
561 */
562 public void testPeekLast() {
563 LinkedList q = populatedQueue(SIZE);
564 for (int i = SIZE-1; i >= 0; --i) {
565 assertEquals(i, q.peekLast());
566 assertEquals(i, q.pollLast());
567 assertTrue(q.peekLast() == null ||
568 !q.peekLast().equals(i));
569 }
570 assertNull(q.peekLast());
571 }
572
573 public void testFirstElement() {
574 LinkedList q = populatedQueue(SIZE);
575 for (int i = 0; i < SIZE; ++i) {
576 assertEquals(i, q.getFirst());
577 assertEquals(i, q.pollFirst());
578 }
579 try {
580 q.getFirst();
581 shouldThrow();
582 } catch (NoSuchElementException success) {}
583 }
584
585 /**
586 * getLast returns next element, or throws NSEE if empty
587 */
588 public void testLastElement() {
589 LinkedList q = populatedQueue(SIZE);
590 for (int i = SIZE-1; i >= 0; --i) {
591 assertEquals(i, q.getLast());
592 assertEquals(i, q.pollLast());
593 }
594 try {
595 q.getLast();
596 shouldThrow();
597 } catch (NoSuchElementException success) {}
598 assertNull(q.peekLast());
599 }
600
601 /**
602 * removeFirstOccurrence(x) removes x and returns true if present
603 */
604 public void testRemoveFirstOccurrence() {
605 LinkedList q = populatedQueue(SIZE);
606 for (int i = 1; i < SIZE; i+=2) {
607 assertTrue(q.removeFirstOccurrence(new Integer(i)));
608 }
609 for (int i = 0; i < SIZE; i+=2) {
610 assertTrue(q.removeFirstOccurrence(new Integer(i)));
611 assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
612 }
613 assertTrue(q.isEmpty());
614 }
615
616 /**
617 * removeLastOccurrence(x) removes x and returns true if present
618 */
619 public void testRemoveLastOccurrence() {
620 LinkedList q = populatedQueue(SIZE);
621 for (int i = 1; i < SIZE; i+=2) {
622 assertTrue(q.removeLastOccurrence(new Integer(i)));
623 }
624 for (int i = 0; i < SIZE; i+=2) {
625 assertTrue(q.removeLastOccurrence(new Integer(i)));
626 assertFalse(q.removeLastOccurrence(new Integer(i+1)));
627 }
628 assertTrue(q.isEmpty());
629 }
630
631 }

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