/[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.23 - (show annotations)
Thu Nov 4 01:04:54 2010 UTC (8 years, 9 months ago) by jsr166
Branch: MAIN
Changes since 1.22: +5 -7 lines
strengthen toArray tests

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 in FIFO order
322 */
323 public void testToArray() {
324 LinkedList q = populatedQueue(SIZE);
325 Object[] o = q.toArray();
326 for (int i = 0; i < o.length; i++)
327 assertSame(o[i], q.poll());
328 }
329
330 /**
331 * toArray(a) contains all elements in FIFO order
332 */
333 public void testToArray2() {
334 LinkedList q = populatedQueue(SIZE);
335 Integer[] ints = new Integer[SIZE];
336 assertSame(ints, q.toArray(ints));
337 for (int i = 0; i < ints.length; i++)
338 assertSame(ints[i], q.poll());
339 }
340
341 /**
342 * toArray(null) throws NullPointerException
343 */
344 public void testToArray_NullArg() {
345 LinkedList l = new LinkedList();
346 l.add(new Object());
347 try {
348 l.toArray(null);
349 shouldThrow();
350 } catch (NullPointerException success) {}
351 }
352
353 /**
354 * toArray(incompatible array type) throws ArrayStoreException
355 */
356 public void testToArray1_BadArg() {
357 LinkedList l = new LinkedList();
358 l.add(new Integer(5));
359 try {
360 l.toArray(new String[10]);
361 shouldThrow();
362 } catch (ArrayStoreException success) {}
363 }
364
365 /**
366 * iterator iterates through all elements
367 */
368 public void testIterator() {
369 LinkedList q = populatedQueue(SIZE);
370 int i = 0;
371 Iterator it = q.iterator();
372 while (it.hasNext()) {
373 assertTrue(q.contains(it.next()));
374 ++i;
375 }
376 assertEquals(i, SIZE);
377 }
378
379 /**
380 * iterator ordering is FIFO
381 */
382 public void testIteratorOrdering() {
383 final LinkedList q = new LinkedList();
384 q.add(new Integer(1));
385 q.add(new Integer(2));
386 q.add(new Integer(3));
387 int k = 0;
388 for (Iterator it = q.iterator(); it.hasNext();) {
389 assertEquals(++k, it.next());
390 }
391
392 assertEquals(3, k);
393 }
394
395 /**
396 * iterator.remove removes current element
397 */
398 public void testIteratorRemove() {
399 final LinkedList q = new LinkedList();
400 q.add(new Integer(1));
401 q.add(new Integer(2));
402 q.add(new Integer(3));
403 Iterator it = q.iterator();
404 assertEquals(it.next(), 1);
405 it.remove();
406 it = q.iterator();
407 assertEquals(it.next(), 2);
408 assertEquals(it.next(), 3);
409 assertFalse(it.hasNext());
410 }
411
412 /**
413 * Descending iterator iterates through all elements
414 */
415 public void testDescendingIterator() {
416 LinkedList q = populatedQueue(SIZE);
417 int i = 0;
418 Iterator it = q.descendingIterator();
419 while (it.hasNext()) {
420 assertTrue(q.contains(it.next()));
421 ++i;
422 }
423 assertEquals(i, SIZE);
424 assertFalse(it.hasNext());
425 try {
426 it.next();
427 shouldThrow();
428 } catch (NoSuchElementException success) {}
429 }
430
431 /**
432 * Descending iterator ordering is reverse FIFO
433 */
434 public void testDescendingIteratorOrdering() {
435 final LinkedList q = new LinkedList();
436 q.add(new Integer(3));
437 q.add(new Integer(2));
438 q.add(new Integer(1));
439 int k = 0;
440 for (Iterator it = q.descendingIterator(); it.hasNext();) {
441 assertEquals(++k, it.next());
442 }
443
444 assertEquals(3, k);
445 }
446
447 /**
448 * descendingIterator.remove removes current element
449 */
450 public void testDescendingIteratorRemove() {
451 final LinkedList q = new LinkedList();
452 q.add(three);
453 q.add(two);
454 q.add(one);
455 Iterator it = q.descendingIterator();
456 it.next();
457 it.remove();
458 it = q.descendingIterator();
459 assertSame(it.next(), two);
460 assertSame(it.next(), three);
461 assertFalse(it.hasNext());
462 }
463
464
465 /**
466 * toString contains toStrings of elements
467 */
468 public void testToString() {
469 LinkedList q = populatedQueue(SIZE);
470 String s = q.toString();
471 for (int i = 0; i < SIZE; ++i) {
472 assertTrue(s.indexOf(String.valueOf(i)) >= 0);
473 }
474 }
475
476 /**
477 * peek returns element inserted with addFirst
478 */
479 public void testAddFirst() {
480 LinkedList q = populatedQueue(3);
481 q.addFirst(four);
482 assertSame(four, q.peek());
483 }
484
485 /**
486 * peekFirst returns element inserted with push
487 */
488 public void testPush() {
489 LinkedList q = populatedQueue(3);
490 q.push(four);
491 assertSame(four, q.peekFirst());
492 }
493
494 /**
495 * pop removes next element, or throws NSEE if empty
496 */
497 public void testPop() {
498 LinkedList q = populatedQueue(SIZE);
499 for (int i = 0; i < SIZE; ++i) {
500 assertEquals(i, q.pop());
501 }
502 try {
503 q.pop();
504 shouldThrow();
505 } catch (NoSuchElementException success) {}
506 }
507
508 /**
509 * OfferFirst succeeds
510 */
511 public void testOfferFirst() {
512 LinkedList q = new LinkedList();
513 assertTrue(q.offerFirst(new Integer(0)));
514 assertTrue(q.offerFirst(new Integer(1)));
515 }
516
517 /**
518 * OfferLast succeeds
519 */
520 public void testOfferLast() {
521 LinkedList q = new LinkedList();
522 assertTrue(q.offerLast(new Integer(0)));
523 assertTrue(q.offerLast(new Integer(1)));
524 }
525
526 /**
527 * pollLast succeeds unless empty
528 */
529 public void testPollLast() {
530 LinkedList q = populatedQueue(SIZE);
531 for (int i = SIZE-1; i >= 0; --i) {
532 assertEquals(i, q.pollLast());
533 }
534 assertNull(q.pollLast());
535 }
536
537 /**
538 * peekFirst returns next element, or null if empty
539 */
540 public void testPeekFirst() {
541 LinkedList q = populatedQueue(SIZE);
542 for (int i = 0; i < SIZE; ++i) {
543 assertEquals(i, q.peekFirst());
544 assertEquals(i, q.pollFirst());
545 assertTrue(q.peekFirst() == null ||
546 !q.peekFirst().equals(i));
547 }
548 assertNull(q.peekFirst());
549 }
550
551
552 /**
553 * peekLast returns next element, or null if empty
554 */
555 public void testPeekLast() {
556 LinkedList q = populatedQueue(SIZE);
557 for (int i = SIZE-1; i >= 0; --i) {
558 assertEquals(i, q.peekLast());
559 assertEquals(i, q.pollLast());
560 assertTrue(q.peekLast() == null ||
561 !q.peekLast().equals(i));
562 }
563 assertNull(q.peekLast());
564 }
565
566 public void testFirstElement() {
567 LinkedList q = populatedQueue(SIZE);
568 for (int i = 0; i < SIZE; ++i) {
569 assertEquals(i, q.getFirst());
570 assertEquals(i, q.pollFirst());
571 }
572 try {
573 q.getFirst();
574 shouldThrow();
575 } catch (NoSuchElementException success) {}
576 }
577
578 /**
579 * getLast returns next element, or throws NSEE if empty
580 */
581 public void testLastElement() {
582 LinkedList q = populatedQueue(SIZE);
583 for (int i = SIZE-1; i >= 0; --i) {
584 assertEquals(i, q.getLast());
585 assertEquals(i, q.pollLast());
586 }
587 try {
588 q.getLast();
589 shouldThrow();
590 } catch (NoSuchElementException success) {}
591 assertNull(q.peekLast());
592 }
593
594 /**
595 * removeFirstOccurrence(x) removes x and returns true if present
596 */
597 public void testRemoveFirstOccurrence() {
598 LinkedList q = populatedQueue(SIZE);
599 for (int i = 1; i < SIZE; i+=2) {
600 assertTrue(q.removeFirstOccurrence(new Integer(i)));
601 }
602 for (int i = 0; i < SIZE; i+=2) {
603 assertTrue(q.removeFirstOccurrence(new Integer(i)));
604 assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
605 }
606 assertTrue(q.isEmpty());
607 }
608
609 /**
610 * removeLastOccurrence(x) removes x and returns true if present
611 */
612 public void testRemoveLastOccurrence() {
613 LinkedList q = populatedQueue(SIZE);
614 for (int i = 1; i < SIZE; i+=2) {
615 assertTrue(q.removeLastOccurrence(new Integer(i)));
616 }
617 for (int i = 0; i < SIZE; i+=2) {
618 assertTrue(q.removeLastOccurrence(new Integer(i)));
619 assertFalse(q.removeLastOccurrence(new Integer(i+1)));
620 }
621 assertTrue(q.isEmpty());
622 }
623
624 }

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