[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.24 - (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 :     * Create a set of given size containing consecutive
36 :     * 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 :     * Create set of first 5 ints
53 :     */
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.18 Integer[] array = q.toArray(ints);
465 :     assertSame(ints, array);
466 : jsr166 1.5 for (int i = 0; i < ints.length; i++)
467 : jsr166 1.17 assertSame(ints[i], q.pollFirst());
468 : dl 1.1 }
469 : jsr166 1.4
470 : dl 1.1 /**
471 :     * iterator iterates through all elements
472 :     */
473 :     public void testIterator() {
474 :     ConcurrentSkipListSet q = populatedSet(SIZE);
475 :     int i = 0;
476 : jsr166 1.7 Iterator it = q.iterator();
477 : jsr166 1.5 while (it.hasNext()) {
478 : dl 1.1 assertTrue(q.contains(it.next()));
479 :     ++i;
480 :     }
481 :     assertEquals(i, SIZE);
482 :     }
483 :    
484 :     /**
485 :     * iterator of empty set has no elements
486 :     */
487 :     public void testEmptyIterator() {
488 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet();
489 :     int i = 0;
490 : jsr166 1.7 Iterator it = q.iterator();
491 : jsr166 1.5 while (it.hasNext()) {
492 : dl 1.1 assertTrue(q.contains(it.next()));
493 :     ++i;
494 :     }
495 : jsr166 1.24 assertEquals(0, i);
496 : dl 1.1 }
497 :    
498 :     /**
499 :     * iterator.remove removes current element
500 :     */
501 : jsr166 1.13 public void testIteratorRemove() {
502 : dl 1.1 final ConcurrentSkipListSet q = new ConcurrentSkipListSet();
503 :     q.add(new Integer(2));
504 :     q.add(new Integer(1));
505 :     q.add(new Integer(3));
506 :    
507 :     Iterator it = q.iterator();
508 :     it.next();
509 :     it.remove();
510 :    
511 :     it = q.iterator();
512 :     assertEquals(it.next(), new Integer(2));
513 :     assertEquals(it.next(), new Integer(3));
514 :     assertFalse(it.hasNext());
515 :     }
516 :    
517 :     /**
518 :     * toString contains toStrings of elements
519 :     */
520 :     public void testToString() {
521 :     ConcurrentSkipListSet q = populatedSet(SIZE);
522 :     String s = q.toString();
523 :     for (int i = 0; i < SIZE; ++i) {
524 : jsr166 1.22 assertTrue(s.contains(String.valueOf(i)));
525 : dl 1.1 }
526 : jsr166 1.4 }
527 : dl 1.1
528 :     /**
529 : jsr166 1.4 * A deserialized serialized set has same elements
530 : dl 1.1 */
531 : jsr166 1.8 public void testSerialization() throws Exception {
532 : jsr166 1.23 NavigableSet x = populatedSet(SIZE);
533 :     NavigableSet y = serialClone(x);
534 :    
535 :     assertTrue(x != y);
536 :     assertEquals(x.size(), y.size());
537 :     assertEquals(x, y);
538 :     assertEquals(y, x);
539 :     while (!x.isEmpty()) {
540 :     assertFalse(y.isEmpty());
541 :     assertEquals(x.pollFirst(), y.pollFirst());
542 :     }
543 :     assertTrue(y.isEmpty());
544 : dl 1.1 }
545 :    
546 :     /**
547 :     * subSet returns set with keys in requested range
548 :     */
549 :     public void testSubSetContents() {
550 :     ConcurrentSkipListSet set = set5();
551 :     SortedSet sm = set.subSet(two, four);
552 :     assertEquals(two, sm.first());
553 :     assertEquals(three, sm.last());
554 :     assertEquals(2, sm.size());
555 :     assertFalse(sm.contains(one));
556 :     assertTrue(sm.contains(two));
557 :     assertTrue(sm.contains(three));
558 :     assertFalse(sm.contains(four));
559 :     assertFalse(sm.contains(five));
560 :     Iterator i = sm.iterator();
561 :     Object k;
562 :     k = (Integer)(i.next());
563 :     assertEquals(two, k);
564 :     k = (Integer)(i.next());
565 :     assertEquals(three, k);
566 :     assertFalse(i.hasNext());
567 :     Iterator j = sm.iterator();
568 :     j.next();
569 :     j.remove();
570 :     assertFalse(set.contains(two));
571 :     assertEquals(4, set.size());
572 :     assertEquals(1, sm.size());
573 :     assertEquals(three, sm.first());
574 :     assertEquals(three, sm.last());
575 :     assertTrue(sm.remove(three));
576 :     assertTrue(sm.isEmpty());
577 :     assertEquals(3, set.size());
578 :     }
579 :    
580 :     public void testSubSetContents2() {
581 :     ConcurrentSkipListSet set = set5();
582 :     SortedSet sm = set.subSet(two, three);
583 :     assertEquals(1, sm.size());
584 :     assertEquals(two, sm.first());
585 :     assertEquals(two, sm.last());
586 :     assertFalse(sm.contains(one));
587 :     assertTrue(sm.contains(two));
588 :     assertFalse(sm.contains(three));
589 :     assertFalse(sm.contains(four));
590 :     assertFalse(sm.contains(five));
591 :     Iterator i = sm.iterator();
592 :     Object k;
593 :     k = (Integer)(i.next());
594 :     assertEquals(two, k);
595 :     assertFalse(i.hasNext());
596 :     Iterator j = sm.iterator();
597 :     j.next();
598 :     j.remove();
599 :     assertFalse(set.contains(two));
600 :     assertEquals(4, set.size());
601 :     assertEquals(0, sm.size());
602 :     assertTrue(sm.isEmpty());
603 :     assertFalse(sm.remove(three));
604 :     assertEquals(4, set.size());
605 :     }
606 :    
607 :     /**
608 :     * headSet returns set with keys in requested range
609 :     */
610 :     public void testHeadSetContents() {
611 :     ConcurrentSkipListSet set = set5();
612 :     SortedSet sm = set.headSet(four);
613 :     assertTrue(sm.contains(one));
614 :     assertTrue(sm.contains(two));
615 :     assertTrue(sm.contains(three));
616 :     assertFalse(sm.contains(four));
617 :     assertFalse(sm.contains(five));
618 :     Iterator i = sm.iterator();
619 :     Object k;
620 :     k = (Integer)(i.next());
621 :     assertEquals(one, k);
622 :     k = (Integer)(i.next());
623 :     assertEquals(two, k);
624 :     k = (Integer)(i.next());
625 :     assertEquals(three, k);
626 :     assertFalse(i.hasNext());
627 :     sm.clear();
628 :     assertTrue(sm.isEmpty());
629 :     assertEquals(2, set.size());
630 :     assertEquals(four, set.first());
631 :     }
632 :    
633 :     /**
634 :     * tailSet returns set with keys in requested range
635 :     */
636 :     public void testTailSetContents() {
637 :     ConcurrentSkipListSet set = set5();
638 :     SortedSet sm = set.tailSet(two);
639 :     assertFalse(sm.contains(one));
640 :     assertTrue(sm.contains(two));
641 :     assertTrue(sm.contains(three));
642 :     assertTrue(sm.contains(four));
643 :     assertTrue(sm.contains(five));
644 :     Iterator i = sm.iterator();
645 :     Object k;
646 :     k = (Integer)(i.next());
647 :     assertEquals(two, k);
648 :     k = (Integer)(i.next());
649 :     assertEquals(three, k);
650 :     k = (Integer)(i.next());
651 :     assertEquals(four, k);
652 :     k = (Integer)(i.next());
653 :     assertEquals(five, k);
654 :     assertFalse(i.hasNext());
655 :    
656 :     SortedSet ssm = sm.tailSet(four);
657 :     assertEquals(four, ssm.first());
658 :     assertEquals(five, ssm.last());
659 :     assertTrue(ssm.remove(four));
660 :     assertEquals(1, ssm.size());
661 :     assertEquals(3, sm.size());
662 :     assertEquals(4, set.size());
663 :     }
664 :    
665 : dl 1.2 Random rnd = new Random(666);
666 :    
667 :     /**
668 :     * Subsets of subsets subdivide correctly
669 :     */
670 : jsr166 1.10 public void testRecursiveSubSets() throws Exception {
671 : jsr166 1.16 int setSize = expensiveTests ? 1000 : 100;
672 : jsr166 1.7 Class cl = ConcurrentSkipListSet.class;
673 : dl 1.2
674 :     NavigableSet<Integer> set = newSet(cl);
675 : jsr166 1.23 BitSet bs = new BitSet(setSize);
676 : dl 1.2
677 : jsr166 1.23 populate(set, setSize, bs);
678 :     check(set, 0, setSize - 1, true, bs);
679 :     check(set.descendingSet(), 0, setSize - 1, false, bs);
680 :    
681 :     mutateSet(set, 0, setSize - 1, bs);
682 :     check(set, 0, setSize - 1, true, bs);
683 :     check(set.descendingSet(), 0, setSize - 1, false, bs);
684 : dl 1.2
685 : dl 1.3 bashSubSet(set.subSet(0, true, setSize, false),
686 : jsr166 1.23 0, setSize - 1, true, bs);
687 : dl 1.2 }
688 :    
689 : jsr166 1.10 static NavigableSet<Integer> newSet(Class cl) throws Exception {
690 :     NavigableSet<Integer> result = (NavigableSet<Integer>) cl.newInstance();
691 : jsr166 1.24 assertEquals(0, result.size());
692 : dl 1.2 assertFalse(result.iterator().hasNext());
693 :     return result;
694 :     }
695 :    
696 : jsr166 1.23 void populate(NavigableSet<Integer> set, int limit, BitSet bs) {
697 : dl 1.2 for (int i = 0, n = 2 * limit / 3; i < n; i++) {
698 :     int element = rnd.nextInt(limit);
699 : jsr166 1.23 put(set, element, bs);
700 : dl 1.2 }
701 :     }
702 :    
703 : jsr166 1.23 void mutateSet(NavigableSet<Integer> set, int min, int max, BitSet bs) {
704 : dl 1.2 int size = set.size();
705 :     int rangeSize = max - min + 1;
706 :    
707 :     // Remove a bunch of entries directly
708 :     for (int i = 0, n = rangeSize / 2; i < n; i++) {
709 : jsr166 1.23 remove(set, min - 5 + rnd.nextInt(rangeSize + 10), bs);
710 : dl 1.2 }
711 :    
712 :     // Remove a bunch of entries with iterator
713 : jsr166 1.5 for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
714 : dl 1.2 if (rnd.nextBoolean()) {
715 :     bs.clear(it.next());
716 :     it.remove();
717 :     }
718 :     }
719 :    
720 :     // Add entries till we're back to original size
721 :     while (set.size() < size) {
722 :     int element = min + rnd.nextInt(rangeSize);
723 :     assertTrue(element >= min && element<= max);
724 : jsr166 1.23 put(set, element, bs);
725 : dl 1.2 }
726 :     }
727 :    
728 : jsr166 1.23 void mutateSubSet(NavigableSet<Integer> set, int min, int max,
729 :     BitSet bs) {
730 : dl 1.2 int size = set.size();
731 :     int rangeSize = max - min + 1;
732 :    
733 :     // Remove a bunch of entries directly
734 :     for (int i = 0, n = rangeSize / 2; i < n; i++) {
735 : jsr166 1.23 remove(set, min - 5 + rnd.nextInt(rangeSize + 10), bs);
736 : dl 1.2 }
737 :    
738 :     // Remove a bunch of entries with iterator
739 : jsr166 1.5 for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
740 : dl 1.2 if (rnd.nextBoolean()) {
741 :     bs.clear(it.next());
742 :     it.remove();
743 :     }
744 :     }
745 :    
746 :     // Add entries till we're back to original size
747 :     while (set.size() < size) {
748 :     int element = min - 5 + rnd.nextInt(rangeSize + 10);
749 :     if (element >= min && element<= max) {
750 : jsr166 1.23 put(set, element, bs);
751 : dl 1.2 } else {
752 :     try {
753 :     set.add(element);
754 : jsr166 1.10 shouldThrow();
755 :     } catch (IllegalArgumentException success) {}
756 : dl 1.2 }
757 :     }
758 :     }
759 :    
760 : jsr166 1.23 void put(NavigableSet<Integer> set, int element, BitSet bs) {
761 : dl 1.2 if (set.add(element))
762 :     bs.set(element);
763 :     }
764 :    
765 : jsr166 1.23 void remove(NavigableSet<Integer> set, int element, BitSet bs) {
766 : dl 1.2 if (set.remove(element))
767 :     bs.clear(element);
768 :     }
769 :    
770 :     void bashSubSet(NavigableSet<Integer> set,
771 : jsr166 1.23 int min, int max, boolean ascending,
772 :     BitSet bs) {
773 :     check(set, min, max, ascending, bs);
774 :     check(set.descendingSet(), min, max, !ascending, bs);
775 :    
776 :     mutateSubSet(set, min, max, bs);
777 :     check(set, min, max, ascending, bs);
778 :     check(set.descendingSet(), min, max, !ascending, bs);
779 : dl 1.2
780 :     // Recurse
781 :     if (max - min < 2)
782 :     return;
783 :     int midPoint = (min + max) / 2;
784 :    
785 :     // headSet - pick direction and endpoint inclusion randomly
786 :     boolean incl = rnd.nextBoolean();
787 : dl 1.3 NavigableSet<Integer> hm = set.headSet(midPoint, incl);
788 : dl 1.2 if (ascending) {
789 :     if (rnd.nextBoolean())
790 : jsr166 1.23 bashSubSet(hm, min, midPoint - (incl ? 0 : 1), true, bs);
791 : dl 1.2 else
792 :     bashSubSet(hm.descendingSet(), min, midPoint - (incl ? 0 : 1),
793 : jsr166 1.23 false, bs);
794 : dl 1.2 } else {
795 :     if (rnd.nextBoolean())
796 : jsr166 1.23 bashSubSet(hm, midPoint + (incl ? 0 : 1), max, false, bs);
797 : dl 1.2 else
798 :     bashSubSet(hm.descendingSet(), midPoint + (incl ? 0 : 1), max,
799 : jsr166 1.23 true, bs);
800 : dl 1.2 }
801 :    
802 :     // tailSet - pick direction and endpoint inclusion randomly
803 :     incl = rnd.nextBoolean();
804 : dl 1.3 NavigableSet<Integer> tm = set.tailSet(midPoint,incl);
805 : dl 1.2 if (ascending) {
806 :     if (rnd.nextBoolean())
807 : jsr166 1.23 bashSubSet(tm, midPoint + (incl ? 0 : 1), max, true, bs);
808 : dl 1.2 else
809 :     bashSubSet(tm.descendingSet(), midPoint + (incl ? 0 : 1), max,
810 : jsr166 1.23 false, bs);
811 : dl 1.2 } else {
812 :     if (rnd.nextBoolean()) {
813 : jsr166 1.23 bashSubSet(tm, min, midPoint - (incl ? 0 : 1), false, bs);
814 : dl 1.2 } else {
815 :     bashSubSet(tm.descendingSet(), min, midPoint - (incl ? 0 : 1),
816 : jsr166 1.23 true, bs);
817 : dl 1.2 }
818 :     }
819 :    
820 :     // subSet - pick direction and endpoint inclusion randomly
821 :     int rangeSize = max - min + 1;
822 :     int[] endpoints = new int[2];
823 :     endpoints[0] = min + rnd.nextInt(rangeSize);
824 :     endpoints[1] = min + rnd.nextInt(rangeSize);
825 :     Arrays.sort(endpoints);
826 :     boolean lowIncl = rnd.nextBoolean();
827 :     boolean highIncl = rnd.nextBoolean();
828 :     if (ascending) {
829 : dl 1.3 NavigableSet<Integer> sm = set.subSet(
830 : dl 1.2 endpoints[0], lowIncl, endpoints[1], highIncl);
831 :     if (rnd.nextBoolean())
832 :     bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
833 : jsr166 1.23 endpoints[1] - (highIncl ? 0 : 1), true, bs);
834 : dl 1.2 else
835 :     bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
836 : jsr166 1.23 endpoints[1] - (highIncl ? 0 : 1), false, bs);
837 : dl 1.2 } else {
838 : dl 1.3 NavigableSet<Integer> sm = set.subSet(
839 : dl 1.2 endpoints[1], highIncl, endpoints[0], lowIncl);
840 :     if (rnd.nextBoolean())
841 :     bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
842 : jsr166 1.23 endpoints[1] - (highIncl ? 0 : 1), false, bs);
843 : dl 1.2 else
844 :     bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
845 : jsr166 1.23 endpoints[1] - (highIncl ? 0 : 1), true, bs);
846 : dl 1.2 }
847 :     }
848 :    
849 :     /**
850 :     * min and max are both inclusive. If max < min, interval is empty.
851 :     */
852 :     void check(NavigableSet<Integer> set,
853 : jsr166 1.23 final int min, final int max, final boolean ascending,
854 :     final BitSet bs) {
855 : jsr166 1.21 class ReferenceSet {
856 : dl 1.2 int lower(int element) {
857 :     return ascending ?
858 :     lowerAscending(element) : higherAscending(element);
859 :     }
860 :     int floor(int element) {
861 :     return ascending ?
862 :     floorAscending(element) : ceilingAscending(element);
863 :     }
864 :     int ceiling(int element) {
865 :     return ascending ?
866 :     ceilingAscending(element) : floorAscending(element);
867 :     }
868 :     int higher(int element) {
869 :     return ascending ?
870 :     higherAscending(element) : lowerAscending(element);
871 :     }
872 :     int first() {
873 :     return ascending ? firstAscending() : lastAscending();
874 :     }
875 :     int last() {
876 :     return ascending ? lastAscending() : firstAscending();
877 :     }
878 :     int lowerAscending(int element) {
879 :     return floorAscending(element - 1);
880 :     }
881 :     int floorAscending(int element) {
882 :     if (element < min)
883 :     return -1;
884 :     else if (element > max)
885 :     element = max;
886 :    
887 :     // BitSet should support this! Test would run much faster
888 :     while (element >= min) {
889 :     if (bs.get(element))
890 : jsr166 1.15 return element;
891 : dl 1.2 element--;
892 :     }
893 :     return -1;
894 :     }
895 :     int ceilingAscending(int element) {
896 :     if (element < min)
897 :     element = min;
898 :     else if (element > max)
899 :     return -1;
900 :     int result = bs.nextSetBit(element);
901 :     return result > max ? -1 : result;
902 :     }
903 :     int higherAscending(int element) {
904 :     return ceilingAscending(element + 1);
905 :     }
906 :     private int firstAscending() {
907 :     int result = ceilingAscending(min);
908 :     return result > max ? -1 : result;
909 :     }
910 :     private int lastAscending() {
911 :     int result = floorAscending(max);
912 :     return result < min ? -1 : result;
913 :     }
914 :     }
915 :     ReferenceSet rs = new ReferenceSet();
916 :    
917 :     // Test contents using containsElement
918 :     int size = 0;
919 :     for (int i = min; i <= max; i++) {
920 :     boolean bsContainsI = bs.get(i);
921 :     assertEquals(bsContainsI, set.contains(i));
922 :     if (bsContainsI)
923 :     size++;
924 :     }
925 :     assertEquals(set.size(), size);
926 :    
927 :     // Test contents using contains elementSet iterator
928 :     int size2 = 0;
929 :     int previousElement = -1;
930 :     for (int element : set) {
931 :     assertTrue(bs.get(element));
932 :     size2++;
933 :     assertTrue(previousElement < 0 || (ascending ?
934 :     element - previousElement > 0 : element - previousElement < 0));
935 :     previousElement = element;
936 :     }
937 :     assertEquals(size2, size);
938 :    
939 :     // Test navigation ops
940 :     for (int element = min - 1; element <= max + 1; element++) {
941 :     assertEq(set.lower(element), rs.lower(element));
942 :     assertEq(set.floor(element), rs.floor(element));
943 :     assertEq(set.higher(element), rs.higher(element));
944 :     assertEq(set.ceiling(element), rs.ceiling(element));
945 :     }
946 :    
947 :     // Test extrema
948 :     if (set.size() != 0) {
949 :     assertEq(set.first(), rs.first());
950 :     assertEq(set.last(), rs.last());
951 :     } else {
952 :     assertEq(rs.first(), -1);
953 :     assertEq(rs.last(), -1);
954 :     try {
955 :     set.first();
956 : jsr166 1.10 shouldThrow();
957 :     } catch (NoSuchElementException success) {}
958 : dl 1.2 try {
959 :     set.last();
960 : jsr166 1.10 shouldThrow();
961 :     } catch (NoSuchElementException success) {}
962 : dl 1.2 }
963 :     }
964 :    
965 :     static void assertEq(Integer i, int j) {
966 :     if (i == null)
967 :     assertEquals(j, -1);
968 :     else
969 :     assertEquals((int) i, j);
970 :     }
971 :    
972 :     static boolean eq(Integer i, int j) {
973 :     return i == null ? j == -1 : i == j;
974 :     }
975 :    
976 : dl 1.1 }

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8