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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8