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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8