/[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.27 - (show annotations)
Fri May 27 19:14:39 2011 UTC (8 years, 2 months ago) by jsr166
Branch: MAIN
Changes since 1.26: +1 -3 lines
indexOf => contains

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 * toString contains toStrings of elements
473 */
474 public void testToString() {
475 LinkedList q = populatedQueue(SIZE);
476 String s = q.toString();
477 for (int i = 0; i < SIZE; ++i) {
478 assertTrue(s.contains(String.valueOf(i)));
479 }
480 }
481
482 /**
483 * peek returns element inserted with addFirst
484 */
485 public void testAddFirst() {
486 LinkedList q = populatedQueue(3);
487 q.addFirst(four);
488 assertSame(four, q.peek());
489 }
490
491 /**
492 * peekFirst returns element inserted with push
493 */
494 public void testPush() {
495 LinkedList q = populatedQueue(3);
496 q.push(four);
497 assertSame(four, q.peekFirst());
498 }
499
500 /**
501 * pop removes next element, or throws NSEE if empty
502 */
503 public void testPop() {
504 LinkedList q = populatedQueue(SIZE);
505 for (int i = 0; i < SIZE; ++i) {
506 assertEquals(i, q.pop());
507 }
508 try {
509 q.pop();
510 shouldThrow();
511 } catch (NoSuchElementException success) {}
512 }
513
514 /**
515 * OfferFirst succeeds
516 */
517 public void testOfferFirst() {
518 LinkedList q = new LinkedList();
519 assertTrue(q.offerFirst(new Integer(0)));
520 assertTrue(q.offerFirst(new Integer(1)));
521 }
522
523 /**
524 * OfferLast succeeds
525 */
526 public void testOfferLast() {
527 LinkedList q = new LinkedList();
528 assertTrue(q.offerLast(new Integer(0)));
529 assertTrue(q.offerLast(new Integer(1)));
530 }
531
532 /**
533 * pollLast succeeds unless empty
534 */
535 public void testPollLast() {
536 LinkedList q = populatedQueue(SIZE);
537 for (int i = SIZE-1; i >= 0; --i) {
538 assertEquals(i, q.pollLast());
539 }
540 assertNull(q.pollLast());
541 }
542
543 /**
544 * peekFirst returns next element, or null if empty
545 */
546 public void testPeekFirst() {
547 LinkedList q = populatedQueue(SIZE);
548 for (int i = 0; i < SIZE; ++i) {
549 assertEquals(i, q.peekFirst());
550 assertEquals(i, q.pollFirst());
551 assertTrue(q.peekFirst() == null ||
552 !q.peekFirst().equals(i));
553 }
554 assertNull(q.peekFirst());
555 }
556
557 /**
558 * peekLast returns next element, or null if empty
559 */
560 public void testPeekLast() {
561 LinkedList q = populatedQueue(SIZE);
562 for (int i = SIZE-1; i >= 0; --i) {
563 assertEquals(i, q.peekLast());
564 assertEquals(i, q.pollLast());
565 assertTrue(q.peekLast() == null ||
566 !q.peekLast().equals(i));
567 }
568 assertNull(q.peekLast());
569 }
570
571 public void testFirstElement() {
572 LinkedList q = populatedQueue(SIZE);
573 for (int i = 0; i < SIZE; ++i) {
574 assertEquals(i, q.getFirst());
575 assertEquals(i, q.pollFirst());
576 }
577 try {
578 q.getFirst();
579 shouldThrow();
580 } catch (NoSuchElementException success) {}
581 }
582
583 /**
584 * getLast returns next element, or throws NSEE if empty
585 */
586 public void testLastElement() {
587 LinkedList q = populatedQueue(SIZE);
588 for (int i = SIZE-1; i >= 0; --i) {
589 assertEquals(i, q.getLast());
590 assertEquals(i, q.pollLast());
591 }
592 try {
593 q.getLast();
594 shouldThrow();
595 } catch (NoSuchElementException success) {}
596 assertNull(q.peekLast());
597 }
598
599 /**
600 * removeFirstOccurrence(x) removes x and returns true if present
601 */
602 public void testRemoveFirstOccurrence() {
603 LinkedList q = populatedQueue(SIZE);
604 for (int i = 1; i < SIZE; i+=2) {
605 assertTrue(q.removeFirstOccurrence(new Integer(i)));
606 }
607 for (int i = 0; i < SIZE; i+=2) {
608 assertTrue(q.removeFirstOccurrence(new Integer(i)));
609 assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
610 }
611 assertTrue(q.isEmpty());
612 }
613
614 /**
615 * removeLastOccurrence(x) removes x and returns true if present
616 */
617 public void testRemoveLastOccurrence() {
618 LinkedList q = populatedQueue(SIZE);
619 for (int i = 1; i < SIZE; i+=2) {
620 assertTrue(q.removeLastOccurrence(new Integer(i)));
621 }
622 for (int i = 0; i < SIZE; i+=2) {
623 assertTrue(q.removeLastOccurrence(new Integer(i)));
624 assertFalse(q.removeLastOccurrence(new Integer(i+1)));
625 }
626 assertTrue(q.isEmpty());
627 }
628
629 }

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