[cvs] / jsr166 / src / test / tck / ConcurrentSkipListSetTest.java Repository:
ViewVC logotype

Annotation of /jsr166/src/test/tck/ConcurrentSkipListSetTest.java

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.34 - (view) (download)

1 : dl 1.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 : jsr166 1.20 * http://creativecommons.org/publicdomain/zero/1.0/
5 : dl 1.1 */
6 :    
7 : jsr166 1.23 import java.util.Arrays;
8 :     import java.util.BitSet;
9 :     import java.util.Collection;
10 :     import java.util.Comparator;
11 :     import java.util.Iterator;
12 :     import java.util.NavigableSet;
13 :     import java.util.NoSuchElementException;
14 :     import java.util.Random;
15 :     import java.util.Set;
16 :     import java.util.SortedSet;
17 :     import java.util.concurrent.ConcurrentSkipListSet;
18 : dl 1.1
19 : jsr166 1.31 import junit.framework.Test;
20 :     import junit.framework.TestSuite;
21 :    
22 : dl 1.1 public class ConcurrentSkipListSetTest extends JSR166TestCase {
23 :     public static void main(String[] args) {
24 : jsr166 1.13 junit.textui.TestRunner.run(suite());
25 : dl 1.1 }
26 :     public static Test suite() {
27 : jsr166 1.7 return new TestSuite(ConcurrentSkipListSetTest.class);
28 : dl 1.1 }
29 :    
30 : jsr166 1.4 static class MyReverseComparator implements Comparator {
31 : dl 1.1 public int compare(Object x, Object y) {
32 : jsr166 1.11 return ((Comparable)y).compareTo(x);
33 : dl 1.1 }
34 :     }
35 :    
36 :     /**
37 : jsr166 1.28 * Returns a new set of given size containing consecutive
38 : dl 1.1 * Integers 0 ... n.
39 :     */
40 : jsr166 1.18 private ConcurrentSkipListSet<Integer> populatedSet(int n) {
41 :     ConcurrentSkipListSet<Integer> q =
42 :     new ConcurrentSkipListSet<Integer>();
43 : dl 1.1 assertTrue(q.isEmpty());
44 : jsr166 1.32 for (int i = n-1; i >= 0; i -= 2)
45 : jsr166 1.7 assertTrue(q.add(new Integer(i)));
46 : jsr166 1.32 for (int i = (n & 1); i < n; i += 2)
47 : jsr166 1.7 assertTrue(q.add(new Integer(i)));
48 : dl 1.1 assertFalse(q.isEmpty());
49 : jsr166 1.7 assertEquals(n, q.size());
50 : dl 1.1 return q;
51 :     }
52 :    
53 :     /**
54 : jsr166 1.28 * Returns a new set of first 5 ints.
55 : dl 1.1 */
56 :     private ConcurrentSkipListSet set5() {
57 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet();
58 :     assertTrue(q.isEmpty());
59 :     q.add(one);
60 :     q.add(two);
61 :     q.add(three);
62 :     q.add(four);
63 :     q.add(five);
64 : jsr166 1.7 assertEquals(5, q.size());
65 : dl 1.1 return q;
66 :     }
67 : jsr166 1.4
68 : dl 1.1 /**
69 :     * A new set has unbounded capacity
70 :     */
71 :     public void testConstructor1() {
72 :     assertEquals(0, new ConcurrentSkipListSet().size());
73 :     }
74 :    
75 :     /**
76 :     * Initializing from null Collection throws NPE
77 :     */
78 :     public void testConstructor3() {
79 :     try {
80 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet((Collection)null);
81 :     shouldThrow();
82 : jsr166 1.8 } catch (NullPointerException success) {}
83 : dl 1.1 }
84 :    
85 :     /**
86 :     * Initializing from Collection of null elements throws NPE
87 :     */
88 :     public void testConstructor4() {
89 :     try {
90 :     Integer[] ints = new Integer[SIZE];
91 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet(Arrays.asList(ints));
92 :     shouldThrow();
93 : jsr166 1.8 } catch (NullPointerException success) {}
94 : dl 1.1 }
95 :    
96 :     /**
97 :     * Initializing from Collection with some null elements throws NPE
98 :     */
99 :     public void testConstructor5() {
100 :     try {
101 :     Integer[] ints = new Integer[SIZE];
102 :     for (int i = 0; i < SIZE-1; ++i)
103 :     ints[i] = new Integer(i);
104 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet(Arrays.asList(ints));
105 :     shouldThrow();
106 : jsr166 1.8 } catch (NullPointerException success) {}
107 : dl 1.1 }
108 :    
109 :     /**
110 :     * Set contains all elements of collection used to initialize
111 :     */
112 :     public void testConstructor6() {
113 : jsr166 1.8 Integer[] ints = new Integer[SIZE];
114 :     for (int i = 0; i < SIZE; ++i)
115 :     ints[i] = new Integer(i);
116 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet(Arrays.asList(ints));
117 :     for (int i = 0; i < SIZE; ++i)
118 :     assertEquals(ints[i], q.pollFirst());
119 : dl 1.1 }
120 :    
121 :     /**
122 :     * The comparator used in constructor is used
123 :     */
124 :     public void testConstructor7() {
125 : jsr166 1.9 MyReverseComparator cmp = new MyReverseComparator();
126 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet(cmp);
127 :     assertEquals(cmp, q.comparator());
128 :     Integer[] ints = new Integer[SIZE];
129 :     for (int i = 0; i < SIZE; ++i)
130 :     ints[i] = new Integer(i);
131 :     q.addAll(Arrays.asList(ints));
132 :     for (int i = SIZE-1; i >= 0; --i)
133 :     assertEquals(ints[i], q.pollFirst());
134 : dl 1.1 }
135 :    
136 :     /**
137 :     * isEmpty is true before add, false after
138 :     */
139 :     public void testEmpty() {
140 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet();
141 :     assertTrue(q.isEmpty());
142 :     q.add(new Integer(1));
143 :     assertFalse(q.isEmpty());
144 :     q.add(new Integer(2));
145 :     q.pollFirst();
146 :     q.pollFirst();
147 :     assertTrue(q.isEmpty());
148 :     }
149 :    
150 :     /**
151 :     * size changes when elements added and removed
152 :     */
153 :     public void testSize() {
154 :     ConcurrentSkipListSet q = populatedSet(SIZE);
155 :     for (int i = 0; i < SIZE; ++i) {
156 :     assertEquals(SIZE-i, q.size());
157 :     q.pollFirst();
158 :     }
159 :     for (int i = 0; i < SIZE; ++i) {
160 :     assertEquals(i, q.size());
161 :     q.add(new Integer(i));
162 :     }
163 :     }
164 :    
165 :     /**
166 :     * add(null) throws NPE
167 :     */
168 :     public void testAddNull() {
169 : jsr166 1.7 try {
170 : dl 1.1 ConcurrentSkipListSet q = new ConcurrentSkipListSet();
171 :     q.add(null);
172 :     shouldThrow();
173 : jsr166 1.8 } catch (NullPointerException success) {}
174 : dl 1.1 }
175 :    
176 :     /**
177 :     * Add of comparable element succeeds
178 :     */
179 :     public void testAdd() {
180 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet();
181 :     assertTrue(q.add(zero));
182 :     assertTrue(q.add(one));
183 :     }
184 :    
185 :     /**
186 :     * Add of duplicate element fails
187 :     */
188 :     public void testAddDup() {
189 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet();
190 :     assertTrue(q.add(zero));
191 :     assertFalse(q.add(zero));
192 :     }
193 :    
194 :     /**
195 :     * Add of non-Comparable throws CCE
196 :     */
197 :     public void testAddNonComparable() {
198 :     try {
199 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet();
200 :     q.add(new Object());
201 :     q.add(new Object());
202 :     q.add(new Object());
203 :     shouldThrow();
204 : jsr166 1.8 } catch (ClassCastException success) {}
205 : dl 1.1 }
206 :    
207 :     /**
208 :     * addAll(null) throws NPE
209 :     */
210 :     public void testAddAll1() {
211 :     try {
212 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet();
213 :     q.addAll(null);
214 :     shouldThrow();
215 : jsr166 1.8 } catch (NullPointerException success) {}
216 : dl 1.1 }
217 : jsr166 1.14
218 : dl 1.1 /**
219 :     * addAll of a collection with null elements throws NPE
220 :     */
221 :     public void testAddAll2() {
222 :     try {
223 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet();
224 :     Integer[] ints = new Integer[SIZE];
225 :     q.addAll(Arrays.asList(ints));
226 :     shouldThrow();
227 : jsr166 1.8 } catch (NullPointerException success) {}
228 : dl 1.1 }
229 : jsr166 1.14
230 : dl 1.1 /**
231 :     * addAll of a collection with any null elements throws NPE after
232 :     * possibly adding some elements
233 :     */
234 :     public void testAddAll3() {
235 :     try {
236 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet();
237 :     Integer[] ints = new Integer[SIZE];
238 :     for (int i = 0; i < SIZE-1; ++i)
239 :     ints[i] = new Integer(i);
240 :     q.addAll(Arrays.asList(ints));
241 :     shouldThrow();
242 : jsr166 1.8 } catch (NullPointerException success) {}
243 : dl 1.1 }
244 :    
245 :     /**
246 :     * Set contains all elements of successful addAll
247 :     */
248 :     public void testAddAll5() {
249 : jsr166 1.9 Integer[] empty = new Integer[0];
250 :     Integer[] ints = new Integer[SIZE];
251 :     for (int i = 0; i < SIZE; ++i)
252 :     ints[i] = new Integer(SIZE-1-i);
253 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet();
254 :     assertFalse(q.addAll(Arrays.asList(empty)));
255 :     assertTrue(q.addAll(Arrays.asList(ints)));
256 :     for (int i = 0; i < SIZE; ++i)
257 : jsr166 1.11 assertEquals(i, q.pollFirst());
258 : dl 1.1 }
259 :    
260 :     /**
261 :     * pollFirst succeeds unless empty
262 :     */
263 :     public void testPollFirst() {
264 :     ConcurrentSkipListSet q = populatedSet(SIZE);
265 :     for (int i = 0; i < SIZE; ++i) {
266 : jsr166 1.11 assertEquals(i, q.pollFirst());
267 : dl 1.1 }
268 : jsr166 1.7 assertNull(q.pollFirst());
269 : dl 1.1 }
270 :    
271 :     /**
272 :     * pollLast succeeds unless empty
273 :     */
274 :     public void testPollLast() {
275 :     ConcurrentSkipListSet q = populatedSet(SIZE);
276 :     for (int i = SIZE-1; i >= 0; --i) {
277 : jsr166 1.11 assertEquals(i, q.pollLast());
278 : dl 1.1 }
279 : jsr166 1.7 assertNull(q.pollFirst());
280 : dl 1.1 }
281 :    
282 :     /**
283 :     * remove(x) removes x and returns true if present
284 :     */
285 :     public void testRemoveElement() {
286 :     ConcurrentSkipListSet q = populatedSet(SIZE);
287 : jsr166 1.32 for (int i = 1; i < SIZE; i += 2) {
288 : jsr166 1.19 assertTrue(q.contains(i));
289 :     assertTrue(q.remove(i));
290 :     assertFalse(q.contains(i));
291 :     assertTrue(q.contains(i-1));
292 : dl 1.1 }
293 : jsr166 1.32 for (int i = 0; i < SIZE; i += 2) {
294 : jsr166 1.19 assertTrue(q.contains(i));
295 :     assertTrue(q.remove(i));
296 :     assertFalse(q.contains(i));
297 :     assertFalse(q.remove(i+1));
298 :     assertFalse(q.contains(i+1));
299 : dl 1.1 }
300 :     assertTrue(q.isEmpty());
301 :     }
302 : jsr166 1.4
303 : dl 1.1 /**
304 :     * contains(x) reports true when elements added but not yet removed
305 :     */
306 :     public void testContains() {
307 :     ConcurrentSkipListSet q = populatedSet(SIZE);
308 :     for (int i = 0; i < SIZE; ++i) {
309 :     assertTrue(q.contains(new Integer(i)));
310 :     q.pollFirst();
311 :     assertFalse(q.contains(new Integer(i)));
312 :     }
313 :     }
314 :    
315 :     /**
316 :     * clear removes all elements
317 :     */
318 :     public void testClear() {
319 :     ConcurrentSkipListSet q = populatedSet(SIZE);
320 :     q.clear();
321 :     assertTrue(q.isEmpty());
322 :     assertEquals(0, q.size());
323 :     q.add(new Integer(1));
324 :     assertFalse(q.isEmpty());
325 :     q.clear();
326 :     assertTrue(q.isEmpty());
327 :     }
328 :    
329 :     /**
330 :     * containsAll(c) is true when c contains a subset of elements
331 :     */
332 :     public void testContainsAll() {
333 :     ConcurrentSkipListSet q = populatedSet(SIZE);
334 :     ConcurrentSkipListSet p = new ConcurrentSkipListSet();
335 :     for (int i = 0; i < SIZE; ++i) {
336 :     assertTrue(q.containsAll(p));
337 :     assertFalse(p.containsAll(q));
338 :     p.add(new Integer(i));
339 :     }
340 :     assertTrue(p.containsAll(q));
341 :     }
342 :    
343 :     /**
344 :     * retainAll(c) retains only those elements of c and reports true if changed
345 :     */
346 :     public void testRetainAll() {
347 :     ConcurrentSkipListSet q = populatedSet(SIZE);
348 :     ConcurrentSkipListSet p = populatedSet(SIZE);
349 :     for (int i = 0; i < SIZE; ++i) {
350 :     boolean changed = q.retainAll(p);
351 :     if (i == 0)
352 :     assertFalse(changed);
353 :     else
354 :     assertTrue(changed);
355 :    
356 :     assertTrue(q.containsAll(p));
357 :     assertEquals(SIZE-i, q.size());
358 :     p.pollFirst();
359 :     }
360 :     }
361 :    
362 :     /**
363 :     * removeAll(c) removes only those elements of c and reports true if changed
364 :     */
365 :     public void testRemoveAll() {
366 :     for (int i = 1; i < SIZE; ++i) {
367 :     ConcurrentSkipListSet q = populatedSet(SIZE);
368 :     ConcurrentSkipListSet p = populatedSet(i);
369 :     assertTrue(q.removeAll(p));
370 :     assertEquals(SIZE-i, q.size());
371 :     for (int j = 0; j < i; ++j) {
372 : jsr166 1.33 Integer x = (Integer)(p.pollFirst());
373 :     assertFalse(q.contains(x));
374 : dl 1.1 }
375 :     }
376 :     }
377 :    
378 :     /**
379 :     * lower returns preceding element
380 :     */
381 :     public void testLower() {
382 :     ConcurrentSkipListSet q = set5();
383 :     Object e1 = q.lower(three);
384 :     assertEquals(two, e1);
385 :    
386 :     Object e2 = q.lower(six);
387 :     assertEquals(five, e2);
388 :    
389 :     Object e3 = q.lower(one);
390 :     assertNull(e3);
391 :    
392 :     Object e4 = q.lower(zero);
393 :     assertNull(e4);
394 :     }
395 :    
396 :     /**
397 :     * higher returns next element
398 :     */
399 :     public void testHigher() {
400 :     ConcurrentSkipListSet q = set5();
401 :     Object e1 = q.higher(three);
402 :     assertEquals(four, e1);
403 :    
404 :     Object e2 = q.higher(zero);
405 :     assertEquals(one, e2);
406 :    
407 :     Object e3 = q.higher(five);
408 :     assertNull(e3);
409 :    
410 :     Object e4 = q.higher(six);
411 :     assertNull(e4);
412 :     }
413 :    
414 :     /**
415 :     * floor returns preceding element
416 :     */
417 :     public void testFloor() {
418 :     ConcurrentSkipListSet q = set5();
419 :     Object e1 = q.floor(three);
420 :     assertEquals(three, e1);
421 :    
422 :     Object e2 = q.floor(six);
423 :     assertEquals(five, e2);
424 :    
425 :     Object e3 = q.floor(one);
426 :     assertEquals(one, e3);
427 :    
428 :     Object e4 = q.floor(zero);
429 :     assertNull(e4);
430 :     }
431 :    
432 :     /**
433 :     * ceiling returns next element
434 :     */
435 :     public void testCeiling() {
436 :     ConcurrentSkipListSet q = set5();
437 :     Object e1 = q.ceiling(three);
438 :     assertEquals(three, e1);
439 :    
440 :     Object e2 = q.ceiling(zero);
441 :     assertEquals(one, e2);
442 :    
443 :     Object e3 = q.ceiling(five);
444 :     assertEquals(five, e3);
445 :    
446 :     Object e4 = q.ceiling(six);
447 :     assertNull(e4);
448 :     }
449 :    
450 :     /**
451 : jsr166 1.17 * toArray contains all elements in sorted order
452 : dl 1.1 */
453 :     public void testToArray() {
454 :     ConcurrentSkipListSet q = populatedSet(SIZE);
455 : jsr166 1.7 Object[] o = q.toArray();
456 :     for (int i = 0; i < o.length; i++)
457 : jsr166 1.17 assertSame(o[i], q.pollFirst());
458 : dl 1.1 }
459 :    
460 :     /**
461 : jsr166 1.17 * toArray(a) contains all elements in sorted order
462 : dl 1.1 */
463 :     public void testToArray2() {
464 : jsr166 1.18 ConcurrentSkipListSet<Integer> q = populatedSet(SIZE);
465 : jsr166 1.7 Integer[] ints = new Integer[SIZE];
466 : jsr166 1.26 assertSame(ints, q.toArray(ints));
467 : jsr166 1.5 for (int i = 0; i < ints.length; i++)
468 : jsr166 1.17 assertSame(ints[i], q.pollFirst());
469 : dl 1.1 }
470 : jsr166 1.4
471 : dl 1.1 /**
472 :     * iterator iterates through all elements
473 :     */
474 :     public void testIterator() {
475 :     ConcurrentSkipListSet q = populatedSet(SIZE);
476 :     int i = 0;
477 : jsr166 1.7 Iterator it = q.iterator();
478 : jsr166 1.5 while (it.hasNext()) {
479 : dl 1.1 assertTrue(q.contains(it.next()));
480 :     ++i;
481 :     }
482 :     assertEquals(i, SIZE);
483 :     }
484 :    
485 :     /**
486 :     * iterator of empty set has no elements
487 :     */
488 :     public void testEmptyIterator() {
489 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet();
490 :     int i = 0;
491 : jsr166 1.7 Iterator it = q.iterator();
492 : jsr166 1.5 while (it.hasNext()) {
493 : dl 1.1 assertTrue(q.contains(it.next()));
494 :     ++i;
495 :     }
496 : jsr166 1.24 assertEquals(0, i);
497 : dl 1.1 }
498 :    
499 :     /**
500 :     * iterator.remove removes current element
501 :     */
502 : jsr166 1.13 public void testIteratorRemove() {
503 : dl 1.1 final ConcurrentSkipListSet q = new ConcurrentSkipListSet();
504 :     q.add(new Integer(2));
505 :     q.add(new Integer(1));
506 :     q.add(new Integer(3));
507 :    
508 :     Iterator it = q.iterator();
509 :     it.next();
510 :     it.remove();
511 :    
512 :     it = q.iterator();
513 :     assertEquals(it.next(), new Integer(2));
514 :     assertEquals(it.next(), new Integer(3));
515 :     assertFalse(it.hasNext());
516 :     }
517 :    
518 :     /**
519 :     * toString contains toStrings of elements
520 :     */
521 :     public void testToString() {
522 :     ConcurrentSkipListSet q = populatedSet(SIZE);
523 :     String s = q.toString();
524 :     for (int i = 0; i < SIZE; ++i) {
525 : jsr166 1.22 assertTrue(s.contains(String.valueOf(i)));
526 : dl 1.1 }
527 : jsr166 1.4 }
528 : dl 1.1
529 :     /**
530 : jsr166 1.4 * A deserialized serialized set has same elements
531 : dl 1.1 */
532 : jsr166 1.8 public void testSerialization() throws Exception {
533 : jsr166 1.23 NavigableSet x = populatedSet(SIZE);
534 :     NavigableSet y = serialClone(x);
535 :    
536 : jsr166 1.30 assertNotSame(x, y);
537 : jsr166 1.23 assertEquals(x.size(), y.size());
538 :     assertEquals(x, y);
539 :     assertEquals(y, x);
540 :     while (!x.isEmpty()) {
541 :     assertFalse(y.isEmpty());
542 :     assertEquals(x.pollFirst(), y.pollFirst());
543 :     }
544 :     assertTrue(y.isEmpty());
545 : dl 1.1 }
546 :    
547 :     /**
548 :     * subSet returns set with keys in requested range
549 :     */
550 :     public void testSubSetContents() {
551 :     ConcurrentSkipListSet set = set5();
552 :     SortedSet sm = set.subSet(two, four);
553 :     assertEquals(two, sm.first());
554 :     assertEquals(three, sm.last());
555 :     assertEquals(2, sm.size());
556 :     assertFalse(sm.contains(one));
557 :     assertTrue(sm.contains(two));
558 :     assertTrue(sm.contains(three));
559 :     assertFalse(sm.contains(four));
560 :     assertFalse(sm.contains(five));
561 :     Iterator i = sm.iterator();
562 :     Object k;
563 :     k = (Integer)(i.next());
564 :     assertEquals(two, k);
565 :     k = (Integer)(i.next());
566 :     assertEquals(three, k);
567 :     assertFalse(i.hasNext());
568 :     Iterator j = sm.iterator();
569 :     j.next();
570 :     j.remove();
571 :     assertFalse(set.contains(two));
572 :     assertEquals(4, set.size());
573 :     assertEquals(1, sm.size());
574 :     assertEquals(three, sm.first());
575 :     assertEquals(three, sm.last());
576 :     assertTrue(sm.remove(three));
577 :     assertTrue(sm.isEmpty());
578 :     assertEquals(3, set.size());
579 :     }
580 :    
581 :     public void testSubSetContents2() {
582 :     ConcurrentSkipListSet set = set5();
583 :     SortedSet sm = set.subSet(two, three);
584 :     assertEquals(1, sm.size());
585 :     assertEquals(two, sm.first());
586 :     assertEquals(two, sm.last());
587 :     assertFalse(sm.contains(one));
588 :     assertTrue(sm.contains(two));
589 :     assertFalse(sm.contains(three));
590 :     assertFalse(sm.contains(four));
591 :     assertFalse(sm.contains(five));
592 :     Iterator i = sm.iterator();
593 :     Object k;
594 :     k = (Integer)(i.next());
595 :     assertEquals(two, k);
596 :     assertFalse(i.hasNext());
597 :     Iterator j = sm.iterator();
598 :     j.next();
599 :     j.remove();
600 :     assertFalse(set.contains(two));
601 :     assertEquals(4, set.size());
602 :     assertEquals(0, sm.size());
603 :     assertTrue(sm.isEmpty());
604 :     assertFalse(sm.remove(three));
605 :     assertEquals(4, set.size());
606 :     }
607 :    
608 :     /**
609 :     * headSet returns set with keys in requested range
610 :     */
611 :     public void testHeadSetContents() {
612 :     ConcurrentSkipListSet set = set5();
613 :     SortedSet sm = set.headSet(four);
614 :     assertTrue(sm.contains(one));
615 :     assertTrue(sm.contains(two));
616 :     assertTrue(sm.contains(three));
617 :     assertFalse(sm.contains(four));
618 :     assertFalse(sm.contains(five));
619 :     Iterator i = sm.iterator();
620 :     Object k;
621 :     k = (Integer)(i.next());
622 :     assertEquals(one, k);
623 :     k = (Integer)(i.next());
624 :     assertEquals(two, k);
625 :     k = (Integer)(i.next());
626 :     assertEquals(three, k);
627 :     assertFalse(i.hasNext());
628 :     sm.clear();
629 :     assertTrue(sm.isEmpty());
630 :     assertEquals(2, set.size());
631 :     assertEquals(four, set.first());
632 :     }
633 :    
634 :     /**
635 :     * tailSet returns set with keys in requested range
636 :     */
637 :     public void testTailSetContents() {
638 :     ConcurrentSkipListSet set = set5();
639 :     SortedSet sm = set.tailSet(two);
640 :     assertFalse(sm.contains(one));
641 :     assertTrue(sm.contains(two));
642 :     assertTrue(sm.contains(three));
643 :     assertTrue(sm.contains(four));
644 :     assertTrue(sm.contains(five));
645 :     Iterator i = sm.iterator();
646 :     Object k;
647 :     k = (Integer)(i.next());
648 :     assertEquals(two, k);
649 :     k = (Integer)(i.next());
650 :     assertEquals(three, k);
651 :     k = (Integer)(i.next());
652 :     assertEquals(four, k);
653 :     k = (Integer)(i.next());
654 :     assertEquals(five, k);
655 :     assertFalse(i.hasNext());
656 :    
657 :     SortedSet ssm = sm.tailSet(four);
658 :     assertEquals(four, ssm.first());
659 :     assertEquals(five, ssm.last());
660 :     assertTrue(ssm.remove(four));
661 :     assertEquals(1, ssm.size());
662 :     assertEquals(3, sm.size());
663 :     assertEquals(4, set.size());
664 :     }
665 :    
666 : dl 1.2 Random rnd = new Random(666);
667 :    
668 :     /**
669 :     * Subsets of subsets subdivide correctly
670 :     */
671 : jsr166 1.10 public void testRecursiveSubSets() throws Exception {
672 : jsr166 1.16 int setSize = expensiveTests ? 1000 : 100;
673 : jsr166 1.7 Class cl = ConcurrentSkipListSet.class;
674 : dl 1.2
675 :     NavigableSet<Integer> set = newSet(cl);
676 : jsr166 1.23 BitSet bs = new BitSet(setSize);
677 : dl 1.2
678 : jsr166 1.23 populate(set, setSize, bs);
679 :     check(set, 0, setSize - 1, true, bs);
680 :     check(set.descendingSet(), 0, setSize - 1, false, bs);
681 :    
682 :     mutateSet(set, 0, setSize - 1, bs);
683 :     check(set, 0, setSize - 1, true, bs);
684 :     check(set.descendingSet(), 0, setSize - 1, false, bs);
685 : dl 1.2
686 : dl 1.3 bashSubSet(set.subSet(0, true, setSize, false),
687 : jsr166 1.23 0, setSize - 1, true, bs);
688 : dl 1.2 }
689 :    
690 : jsr166 1.29 /**
691 :     * addAll is idempotent
692 :     */
693 :     public void testAddAll_idempotent() throws Exception {
694 :     Set x = populatedSet(SIZE);
695 :     Set y = new ConcurrentSkipListSet(x);
696 :     y.addAll(x);
697 :     assertEquals(x, y);
698 :     assertEquals(y, x);
699 :     }
700 :    
701 : jsr166 1.10 static NavigableSet<Integer> newSet(Class cl) throws Exception {
702 :     NavigableSet<Integer> result = (NavigableSet<Integer>) cl.newInstance();
703 : jsr166 1.24 assertEquals(0, result.size());
704 : dl 1.2 assertFalse(result.iterator().hasNext());
705 :     return result;
706 :     }
707 :    
708 : jsr166 1.23 void populate(NavigableSet<Integer> set, int limit, BitSet bs) {
709 : dl 1.2 for (int i = 0, n = 2 * limit / 3; i < n; i++) {
710 :     int element = rnd.nextInt(limit);
711 : jsr166 1.23 put(set, element, bs);
712 : dl 1.2 }
713 :     }
714 :    
715 : jsr166 1.23 void mutateSet(NavigableSet<Integer> set, int min, int max, BitSet bs) {
716 : dl 1.2 int size = set.size();
717 :     int rangeSize = max - min + 1;
718 :    
719 :     // Remove a bunch of entries directly
720 :     for (int i = 0, n = rangeSize / 2; i < n; i++) {
721 : jsr166 1.23 remove(set, min - 5 + rnd.nextInt(rangeSize + 10), bs);
722 : dl 1.2 }
723 :    
724 :     // Remove a bunch of entries with iterator
725 : jsr166 1.5 for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
726 : dl 1.2 if (rnd.nextBoolean()) {
727 :     bs.clear(it.next());
728 :     it.remove();
729 :     }
730 :     }
731 :    
732 :     // Add entries till we're back to original size
733 :     while (set.size() < size) {
734 :     int element = min + rnd.nextInt(rangeSize);
735 : jsr166 1.34 assertTrue(element >= min && element <= max);
736 : jsr166 1.23 put(set, element, bs);
737 : dl 1.2 }
738 :     }
739 :    
740 : jsr166 1.23 void mutateSubSet(NavigableSet<Integer> set, int min, int max,
741 :     BitSet bs) {
742 : dl 1.2 int size = set.size();
743 :     int rangeSize = max - min + 1;
744 :    
745 :     // Remove a bunch of entries directly
746 :     for (int i = 0, n = rangeSize / 2; i < n; i++) {
747 : jsr166 1.23 remove(set, min - 5 + rnd.nextInt(rangeSize + 10), bs);
748 : dl 1.2 }
749 :    
750 :     // Remove a bunch of entries with iterator
751 : jsr166 1.5 for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
752 : dl 1.2 if (rnd.nextBoolean()) {
753 :     bs.clear(it.next());
754 :     it.remove();
755 :     }
756 :     }
757 :    
758 :     // Add entries till we're back to original size
759 :     while (set.size() < size) {
760 :     int element = min - 5 + rnd.nextInt(rangeSize + 10);
761 : jsr166 1.34 if (element >= min && element <= max) {
762 : jsr166 1.23 put(set, element, bs);
763 : dl 1.2 } else {
764 :     try {
765 :     set.add(element);
766 : jsr166 1.10 shouldThrow();
767 :     } catch (IllegalArgumentException success) {}
768 : dl 1.2 }
769 :     }
770 :     }
771 :    
772 : jsr166 1.23 void put(NavigableSet<Integer> set, int element, BitSet bs) {
773 : dl 1.2 if (set.add(element))
774 :     bs.set(element);
775 :     }
776 :    
777 : jsr166 1.23 void remove(NavigableSet<Integer> set, int element, BitSet bs) {
778 : dl 1.2 if (set.remove(element))
779 :     bs.clear(element);
780 :     }
781 :    
782 :     void bashSubSet(NavigableSet<Integer> set,
783 : jsr166 1.23 int min, int max, boolean ascending,
784 :     BitSet bs) {
785 :     check(set, min, max, ascending, bs);
786 :     check(set.descendingSet(), min, max, !ascending, bs);
787 :    
788 :     mutateSubSet(set, min, max, bs);
789 :     check(set, min, max, ascending, bs);
790 :     check(set.descendingSet(), min, max, !ascending, bs);
791 : dl 1.2
792 :     // Recurse
793 :     if (max - min < 2)
794 :     return;
795 :     int midPoint = (min + max) / 2;
796 :    
797 :     // headSet - pick direction and endpoint inclusion randomly
798 :     boolean incl = rnd.nextBoolean();
799 : dl 1.3 NavigableSet<Integer> hm = set.headSet(midPoint, incl);
800 : dl 1.2 if (ascending) {
801 :     if (rnd.nextBoolean())
802 : jsr166 1.23 bashSubSet(hm, min, midPoint - (incl ? 0 : 1), true, bs);
803 : dl 1.2 else
804 :     bashSubSet(hm.descendingSet(), min, midPoint - (incl ? 0 : 1),
805 : jsr166 1.23 false, bs);
806 : dl 1.2 } else {
807 :     if (rnd.nextBoolean())
808 : jsr166 1.23 bashSubSet(hm, midPoint + (incl ? 0 : 1), max, false, bs);
809 : dl 1.2 else
810 :     bashSubSet(hm.descendingSet(), midPoint + (incl ? 0 : 1), max,
811 : jsr166 1.23 true, bs);
812 : dl 1.2 }
813 :    
814 :     // tailSet - pick direction and endpoint inclusion randomly
815 :     incl = rnd.nextBoolean();
816 : dl 1.3 NavigableSet<Integer> tm = set.tailSet(midPoint,incl);
817 : dl 1.2 if (ascending) {
818 :     if (rnd.nextBoolean())
819 : jsr166 1.23 bashSubSet(tm, midPoint + (incl ? 0 : 1), max, true, bs);
820 : dl 1.2 else
821 :     bashSubSet(tm.descendingSet(), midPoint + (incl ? 0 : 1), max,
822 : jsr166 1.23 false, bs);
823 : dl 1.2 } else {
824 :     if (rnd.nextBoolean()) {
825 : jsr166 1.23 bashSubSet(tm, min, midPoint - (incl ? 0 : 1), false, bs);
826 : dl 1.2 } else {
827 :     bashSubSet(tm.descendingSet(), min, midPoint - (incl ? 0 : 1),
828 : jsr166 1.23 true, bs);
829 : dl 1.2 }
830 :     }
831 :    
832 :     // subSet - pick direction and endpoint inclusion randomly
833 :     int rangeSize = max - min + 1;
834 :     int[] endpoints = new int[2];
835 :     endpoints[0] = min + rnd.nextInt(rangeSize);
836 :     endpoints[1] = min + rnd.nextInt(rangeSize);
837 :     Arrays.sort(endpoints);
838 :     boolean lowIncl = rnd.nextBoolean();
839 :     boolean highIncl = rnd.nextBoolean();
840 :     if (ascending) {
841 : dl 1.3 NavigableSet<Integer> sm = set.subSet(
842 : dl 1.2 endpoints[0], lowIncl, endpoints[1], highIncl);
843 :     if (rnd.nextBoolean())
844 :     bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
845 : jsr166 1.23 endpoints[1] - (highIncl ? 0 : 1), true, bs);
846 : dl 1.2 else
847 :     bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
848 : jsr166 1.23 endpoints[1] - (highIncl ? 0 : 1), false, bs);
849 : dl 1.2 } else {
850 : dl 1.3 NavigableSet<Integer> sm = set.subSet(
851 : dl 1.2 endpoints[1], highIncl, endpoints[0], lowIncl);
852 :     if (rnd.nextBoolean())
853 :     bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
854 : jsr166 1.23 endpoints[1] - (highIncl ? 0 : 1), false, bs);
855 : dl 1.2 else
856 :     bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
857 : jsr166 1.23 endpoints[1] - (highIncl ? 0 : 1), true, bs);
858 : dl 1.2 }
859 :     }
860 :    
861 :     /**
862 :     * min and max are both inclusive. If max < min, interval is empty.
863 :     */
864 :     void check(NavigableSet<Integer> set,
865 : jsr166 1.23 final int min, final int max, final boolean ascending,
866 :     final BitSet bs) {
867 : jsr166 1.21 class ReferenceSet {
868 : dl 1.2 int lower(int element) {
869 :     return ascending ?
870 :     lowerAscending(element) : higherAscending(element);
871 :     }
872 :     int floor(int element) {
873 :     return ascending ?
874 :     floorAscending(element) : ceilingAscending(element);
875 :     }
876 :     int ceiling(int element) {
877 :     return ascending ?
878 :     ceilingAscending(element) : floorAscending(element);
879 :     }
880 :     int higher(int element) {
881 :     return ascending ?
882 :     higherAscending(element) : lowerAscending(element);
883 :     }
884 :     int first() {
885 :     return ascending ? firstAscending() : lastAscending();
886 :     }
887 :     int last() {
888 :     return ascending ? lastAscending() : firstAscending();
889 :     }
890 :     int lowerAscending(int element) {
891 :     return floorAscending(element - 1);
892 :     }
893 :     int floorAscending(int element) {
894 :     if (element < min)
895 :     return -1;
896 :     else if (element > max)
897 :     element = max;
898 :    
899 :     // BitSet should support this! Test would run much faster
900 :     while (element >= min) {
901 :     if (bs.get(element))
902 : jsr166 1.15 return element;
903 : dl 1.2 element--;
904 :     }
905 :     return -1;
906 :     }
907 :     int ceilingAscending(int element) {
908 :     if (element < min)
909 :     element = min;
910 :     else if (element > max)
911 :     return -1;
912 :     int result = bs.nextSetBit(element);
913 :     return result > max ? -1 : result;
914 :     }
915 :     int higherAscending(int element) {
916 :     return ceilingAscending(element + 1);
917 :     }
918 :     private int firstAscending() {
919 :     int result = ceilingAscending(min);
920 :     return result > max ? -1 : result;
921 :     }
922 :     private int lastAscending() {
923 :     int result = floorAscending(max);
924 :     return result < min ? -1 : result;
925 :     }
926 :     }
927 :     ReferenceSet rs = new ReferenceSet();
928 :    
929 :     // Test contents using containsElement
930 :     int size = 0;
931 :     for (int i = min; i <= max; i++) {
932 :     boolean bsContainsI = bs.get(i);
933 :     assertEquals(bsContainsI, set.contains(i));
934 :     if (bsContainsI)
935 :     size++;
936 :     }
937 : jsr166 1.25 assertEquals(size, set.size());
938 : dl 1.2
939 :     // Test contents using contains elementSet iterator
940 :     int size2 = 0;
941 :     int previousElement = -1;
942 :     for (int element : set) {
943 :     assertTrue(bs.get(element));
944 :     size2++;
945 :     assertTrue(previousElement < 0 || (ascending ?
946 :     element - previousElement > 0 : element - previousElement < 0));
947 :     previousElement = element;
948 :     }
949 :     assertEquals(size2, size);
950 :    
951 :     // Test navigation ops
952 :     for (int element = min - 1; element <= max + 1; element++) {
953 :     assertEq(set.lower(element), rs.lower(element));
954 :     assertEq(set.floor(element), rs.floor(element));
955 :     assertEq(set.higher(element), rs.higher(element));
956 :     assertEq(set.ceiling(element), rs.ceiling(element));
957 :     }
958 :    
959 :     // Test extrema
960 :     if (set.size() != 0) {
961 :     assertEq(set.first(), rs.first());
962 :     assertEq(set.last(), rs.last());
963 :     } else {
964 :     assertEq(rs.first(), -1);
965 :     assertEq(rs.last(), -1);
966 :     try {
967 :     set.first();
968 : jsr166 1.10 shouldThrow();
969 :     } catch (NoSuchElementException success) {}
970 : dl 1.2 try {
971 :     set.last();
972 : jsr166 1.10 shouldThrow();
973 :     } catch (NoSuchElementException success) {}
974 : dl 1.2 }
975 :     }
976 :    
977 :     static void assertEq(Integer i, int j) {
978 :     if (i == null)
979 :     assertEquals(j, -1);
980 :     else
981 :     assertEquals((int) i, j);
982 :     }
983 :    
984 :     static boolean eq(Integer i, int j) {
985 :     return i == null ? j == -1 : i == j;
986 :     }
987 :    
988 : dl 1.1 }

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8