/[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.24 - (show annotations)
Fri Nov 5 00:17:22 2010 UTC (8 years, 9 months ago) by jsr166
Branch: MAIN
Changes since 1.23: +5 -4 lines
very small improvements to testToArray2

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

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