[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.18 - (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 :     * http://creativecommons.org/licenses/publicdomain
5 :     */
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 :     assertTrue(q.remove(new Integer(i)));
280 :     }
281 :     for (int i = 0; i < SIZE; i+=2) {
282 :     assertTrue(q.remove(new Integer(i)));
283 :     assertFalse(q.remove(new Integer(i+1)));
284 :     }
285 :     assertTrue(q.isEmpty());
286 :     }
287 : jsr166 1.4
288 : dl 1.1 /**
289 :     * contains(x) reports true when elements added but not yet removed
290 :     */
291 :     public void testContains() {
292 :     ConcurrentSkipListSet q = populatedSet(SIZE);
293 :     for (int i = 0; i < SIZE; ++i) {
294 :     assertTrue(q.contains(new Integer(i)));
295 :     q.pollFirst();
296 :     assertFalse(q.contains(new Integer(i)));
297 :     }
298 :     }
299 :    
300 :     /**
301 :     * clear removes all elements
302 :     */
303 :     public void testClear() {
304 :     ConcurrentSkipListSet q = populatedSet(SIZE);
305 :     q.clear();
306 :     assertTrue(q.isEmpty());
307 :     assertEquals(0, q.size());
308 :     q.add(new Integer(1));
309 :     assertFalse(q.isEmpty());
310 :     q.clear();
311 :     assertTrue(q.isEmpty());
312 :     }
313 :    
314 :     /**
315 :     * containsAll(c) is true when c contains a subset of elements
316 :     */
317 :     public void testContainsAll() {
318 :     ConcurrentSkipListSet q = populatedSet(SIZE);
319 :     ConcurrentSkipListSet p = new ConcurrentSkipListSet();
320 :     for (int i = 0; i < SIZE; ++i) {
321 :     assertTrue(q.containsAll(p));
322 :     assertFalse(p.containsAll(q));
323 :     p.add(new Integer(i));
324 :     }
325 :     assertTrue(p.containsAll(q));
326 :     }
327 :    
328 :     /**
329 :     * retainAll(c) retains only those elements of c and reports true if changed
330 :     */
331 :     public void testRetainAll() {
332 :     ConcurrentSkipListSet q = populatedSet(SIZE);
333 :     ConcurrentSkipListSet p = populatedSet(SIZE);
334 :     for (int i = 0; i < SIZE; ++i) {
335 :     boolean changed = q.retainAll(p);
336 :     if (i == 0)
337 :     assertFalse(changed);
338 :     else
339 :     assertTrue(changed);
340 :    
341 :     assertTrue(q.containsAll(p));
342 :     assertEquals(SIZE-i, q.size());
343 :     p.pollFirst();
344 :     }
345 :     }
346 :    
347 :     /**
348 :     * removeAll(c) removes only those elements of c and reports true if changed
349 :     */
350 :     public void testRemoveAll() {
351 :     for (int i = 1; i < SIZE; ++i) {
352 :     ConcurrentSkipListSet q = populatedSet(SIZE);
353 :     ConcurrentSkipListSet p = populatedSet(i);
354 :     assertTrue(q.removeAll(p));
355 :     assertEquals(SIZE-i, q.size());
356 :     for (int j = 0; j < i; ++j) {
357 :     Integer I = (Integer)(p.pollFirst());
358 :     assertFalse(q.contains(I));
359 :     }
360 :     }
361 :     }
362 :    
363 : jsr166 1.4
364 : dl 1.1
365 :     /**
366 :     * lower returns preceding element
367 :     */
368 :     public void testLower() {
369 :     ConcurrentSkipListSet q = set5();
370 :     Object e1 = q.lower(three);
371 :     assertEquals(two, e1);
372 :    
373 :     Object e2 = q.lower(six);
374 :     assertEquals(five, e2);
375 :    
376 :     Object e3 = q.lower(one);
377 :     assertNull(e3);
378 :    
379 :     Object e4 = q.lower(zero);
380 :     assertNull(e4);
381 :     }
382 :    
383 :     /**
384 :     * higher returns next element
385 :     */
386 :     public void testHigher() {
387 :     ConcurrentSkipListSet q = set5();
388 :     Object e1 = q.higher(three);
389 :     assertEquals(four, e1);
390 :    
391 :     Object e2 = q.higher(zero);
392 :     assertEquals(one, e2);
393 :    
394 :     Object e3 = q.higher(five);
395 :     assertNull(e3);
396 :    
397 :     Object e4 = q.higher(six);
398 :     assertNull(e4);
399 :     }
400 :    
401 :     /**
402 :     * floor returns preceding element
403 :     */
404 :     public void testFloor() {
405 :     ConcurrentSkipListSet q = set5();
406 :     Object e1 = q.floor(three);
407 :     assertEquals(three, e1);
408 :    
409 :     Object e2 = q.floor(six);
410 :     assertEquals(five, e2);
411 :    
412 :     Object e3 = q.floor(one);
413 :     assertEquals(one, e3);
414 :    
415 :     Object e4 = q.floor(zero);
416 :     assertNull(e4);
417 :     }
418 :    
419 :     /**
420 :     * ceiling returns next element
421 :     */
422 :     public void testCeiling() {
423 :     ConcurrentSkipListSet q = set5();
424 :     Object e1 = q.ceiling(three);
425 :     assertEquals(three, e1);
426 :    
427 :     Object e2 = q.ceiling(zero);
428 :     assertEquals(one, e2);
429 :    
430 :     Object e3 = q.ceiling(five);
431 :     assertEquals(five, e3);
432 :    
433 :     Object e4 = q.ceiling(six);
434 :     assertNull(e4);
435 :     }
436 :    
437 :     /**
438 : jsr166 1.17 * toArray contains all elements in sorted order
439 : dl 1.1 */
440 :     public void testToArray() {
441 :     ConcurrentSkipListSet q = populatedSet(SIZE);
442 : jsr166 1.7 Object[] o = q.toArray();
443 :     for (int i = 0; i < o.length; i++)
444 : jsr166 1.17 assertSame(o[i], q.pollFirst());
445 : dl 1.1 }
446 :    
447 :     /**
448 : jsr166 1.17 * toArray(a) contains all elements in sorted order
449 : dl 1.1 */
450 :     public void testToArray2() {
451 : jsr166 1.18 ConcurrentSkipListSet<Integer> q = populatedSet(SIZE);
452 : jsr166 1.7 Integer[] ints = new Integer[SIZE];
453 : jsr166 1.18 Integer[] array = q.toArray(ints);
454 :     assertSame(ints, array);
455 : jsr166 1.5 for (int i = 0; i < ints.length; i++)
456 : jsr166 1.17 assertSame(ints[i], q.pollFirst());
457 : dl 1.1 }
458 : jsr166 1.4
459 : dl 1.1 /**
460 :     * iterator iterates through all elements
461 :     */
462 :     public void testIterator() {
463 :     ConcurrentSkipListSet q = populatedSet(SIZE);
464 :     int i = 0;
465 : jsr166 1.7 Iterator it = q.iterator();
466 : jsr166 1.5 while (it.hasNext()) {
467 : dl 1.1 assertTrue(q.contains(it.next()));
468 :     ++i;
469 :     }
470 :     assertEquals(i, SIZE);
471 :     }
472 :    
473 :     /**
474 :     * iterator of empty set has no elements
475 :     */
476 :     public void testEmptyIterator() {
477 :     ConcurrentSkipListSet q = new ConcurrentSkipListSet();
478 :     int i = 0;
479 : jsr166 1.7 Iterator it = q.iterator();
480 : jsr166 1.5 while (it.hasNext()) {
481 : dl 1.1 assertTrue(q.contains(it.next()));
482 :     ++i;
483 :     }
484 :     assertEquals(i, 0);
485 :     }
486 :    
487 :     /**
488 :     * iterator.remove removes current element
489 :     */
490 : jsr166 1.13 public void testIteratorRemove() {
491 : dl 1.1 final ConcurrentSkipListSet q = new ConcurrentSkipListSet();
492 :     q.add(new Integer(2));
493 :     q.add(new Integer(1));
494 :     q.add(new Integer(3));
495 :    
496 :     Iterator it = q.iterator();
497 :     it.next();
498 :     it.remove();
499 :    
500 :     it = q.iterator();
501 :     assertEquals(it.next(), new Integer(2));
502 :     assertEquals(it.next(), new Integer(3));
503 :     assertFalse(it.hasNext());
504 :     }
505 :    
506 :    
507 :     /**
508 :     * toString contains toStrings of elements
509 :     */
510 :     public void testToString() {
511 :     ConcurrentSkipListSet q = populatedSet(SIZE);
512 :     String s = q.toString();
513 :     for (int i = 0; i < SIZE; ++i) {
514 :     assertTrue(s.indexOf(String.valueOf(i)) >= 0);
515 :     }
516 : jsr166 1.4 }
517 : dl 1.1
518 :     /**
519 : jsr166 1.4 * A deserialized serialized set has same elements
520 : dl 1.1 */
521 : jsr166 1.8 public void testSerialization() throws Exception {
522 : dl 1.1 ConcurrentSkipListSet q = populatedSet(SIZE);
523 : jsr166 1.8 ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
524 :     ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
525 :     out.writeObject(q);
526 :     out.close();
527 :    
528 :     ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
529 :     ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
530 :     ConcurrentSkipListSet r = (ConcurrentSkipListSet)in.readObject();
531 :     assertEquals(q.size(), r.size());
532 :     while (!q.isEmpty())
533 :     assertEquals(q.pollFirst(), r.pollFirst());
534 : dl 1.1 }
535 :    
536 :     /**
537 :     * subSet returns set with keys in requested range
538 :     */
539 :     public void testSubSetContents() {
540 :     ConcurrentSkipListSet set = set5();
541 :     SortedSet sm = set.subSet(two, four);
542 :     assertEquals(two, sm.first());
543 :     assertEquals(three, sm.last());
544 :     assertEquals(2, sm.size());
545 :     assertFalse(sm.contains(one));
546 :     assertTrue(sm.contains(two));
547 :     assertTrue(sm.contains(three));
548 :     assertFalse(sm.contains(four));
549 :     assertFalse(sm.contains(five));
550 :     Iterator i = sm.iterator();
551 :     Object k;
552 :     k = (Integer)(i.next());
553 :     assertEquals(two, k);
554 :     k = (Integer)(i.next());
555 :     assertEquals(three, k);
556 :     assertFalse(i.hasNext());
557 :     Iterator j = sm.iterator();
558 :     j.next();
559 :     j.remove();
560 :     assertFalse(set.contains(two));
561 :     assertEquals(4, set.size());
562 :     assertEquals(1, sm.size());
563 :     assertEquals(three, sm.first());
564 :     assertEquals(three, sm.last());
565 :     assertTrue(sm.remove(three));
566 :     assertTrue(sm.isEmpty());
567 :     assertEquals(3, set.size());
568 :     }
569 :    
570 :     public void testSubSetContents2() {
571 :     ConcurrentSkipListSet set = set5();
572 :     SortedSet sm = set.subSet(two, three);
573 :     assertEquals(1, sm.size());
574 :     assertEquals(two, sm.first());
575 :     assertEquals(two, sm.last());
576 :     assertFalse(sm.contains(one));
577 :     assertTrue(sm.contains(two));
578 :     assertFalse(sm.contains(three));
579 :     assertFalse(sm.contains(four));
580 :     assertFalse(sm.contains(five));
581 :     Iterator i = sm.iterator();
582 :     Object k;
583 :     k = (Integer)(i.next());
584 :     assertEquals(two, k);
585 :     assertFalse(i.hasNext());
586 :     Iterator j = sm.iterator();
587 :     j.next();
588 :     j.remove();
589 :     assertFalse(set.contains(two));
590 :     assertEquals(4, set.size());
591 :     assertEquals(0, sm.size());
592 :     assertTrue(sm.isEmpty());
593 :     assertFalse(sm.remove(three));
594 :     assertEquals(4, set.size());
595 :     }
596 :    
597 :     /**
598 :     * headSet returns set with keys in requested range
599 :     */
600 :     public void testHeadSetContents() {
601 :     ConcurrentSkipListSet set = set5();
602 :     SortedSet sm = set.headSet(four);
603 :     assertTrue(sm.contains(one));
604 :     assertTrue(sm.contains(two));
605 :     assertTrue(sm.contains(three));
606 :     assertFalse(sm.contains(four));
607 :     assertFalse(sm.contains(five));
608 :     Iterator i = sm.iterator();
609 :     Object k;
610 :     k = (Integer)(i.next());
611 :     assertEquals(one, k);
612 :     k = (Integer)(i.next());
613 :     assertEquals(two, k);
614 :     k = (Integer)(i.next());
615 :     assertEquals(three, k);
616 :     assertFalse(i.hasNext());
617 :     sm.clear();
618 :     assertTrue(sm.isEmpty());
619 :     assertEquals(2, set.size());
620 :     assertEquals(four, set.first());
621 :     }
622 :    
623 :     /**
624 :     * tailSet returns set with keys in requested range
625 :     */
626 :     public void testTailSetContents() {
627 :     ConcurrentSkipListSet set = set5();
628 :     SortedSet sm = set.tailSet(two);
629 :     assertFalse(sm.contains(one));
630 :     assertTrue(sm.contains(two));
631 :     assertTrue(sm.contains(three));
632 :     assertTrue(sm.contains(four));
633 :     assertTrue(sm.contains(five));
634 :     Iterator i = sm.iterator();
635 :     Object k;
636 :     k = (Integer)(i.next());
637 :     assertEquals(two, k);
638 :     k = (Integer)(i.next());
639 :     assertEquals(three, k);
640 :     k = (Integer)(i.next());
641 :     assertEquals(four, k);
642 :     k = (Integer)(i.next());
643 :     assertEquals(five, k);
644 :     assertFalse(i.hasNext());
645 :    
646 :     SortedSet ssm = sm.tailSet(four);
647 :     assertEquals(four, ssm.first());
648 :     assertEquals(five, ssm.last());
649 :     assertTrue(ssm.remove(four));
650 :     assertEquals(1, ssm.size());
651 :     assertEquals(3, sm.size());
652 :     assertEquals(4, set.size());
653 :     }
654 :    
655 : dl 1.2 Random rnd = new Random(666);
656 :     BitSet bs;
657 :    
658 :     /**
659 :     * Subsets of subsets subdivide correctly
660 :     */
661 : jsr166 1.10 public void testRecursiveSubSets() throws Exception {
662 : jsr166 1.16 int setSize = expensiveTests ? 1000 : 100;
663 : jsr166 1.7 Class cl = ConcurrentSkipListSet.class;
664 : dl 1.2
665 :     NavigableSet<Integer> set = newSet(cl);
666 :     bs = new BitSet(setSize);
667 :    
668 :     populate(set, setSize);
669 :     check(set, 0, setSize - 1, true);
670 :     check(set.descendingSet(), 0, setSize - 1, false);
671 :    
672 :     mutateSet(set, 0, setSize - 1);
673 :     check(set, 0, setSize - 1, true);
674 :     check(set.descendingSet(), 0, setSize - 1, false);
675 :    
676 : dl 1.3 bashSubSet(set.subSet(0, true, setSize, false),
677 : dl 1.2 0, setSize - 1, true);
678 :     }
679 :    
680 : jsr166 1.10 static NavigableSet<Integer> newSet(Class cl) throws Exception {
681 :     NavigableSet<Integer> result = (NavigableSet<Integer>) cl.newInstance();
682 : dl 1.2 assertEquals(result.size(), 0);
683 :     assertFalse(result.iterator().hasNext());
684 :     return result;
685 :     }
686 :    
687 :     void populate(NavigableSet<Integer> set, int limit) {
688 :     for (int i = 0, n = 2 * limit / 3; i < n; i++) {
689 :     int element = rnd.nextInt(limit);
690 :     put(set, element);
691 :     }
692 :     }
693 :    
694 :     void mutateSet(NavigableSet<Integer> set, int min, int max) {
695 :     int size = set.size();
696 :     int rangeSize = max - min + 1;
697 :    
698 :     // Remove a bunch of entries directly
699 :     for (int i = 0, n = rangeSize / 2; i < n; i++) {
700 :     remove(set, min - 5 + rnd.nextInt(rangeSize + 10));
701 :     }
702 :    
703 :     // Remove a bunch of entries with iterator
704 : jsr166 1.5 for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
705 : dl 1.2 if (rnd.nextBoolean()) {
706 :     bs.clear(it.next());
707 :     it.remove();
708 :     }
709 :     }
710 :    
711 :     // Add entries till we're back to original size
712 :     while (set.size() < size) {
713 :     int element = min + rnd.nextInt(rangeSize);
714 :     assertTrue(element >= min && element<= max);
715 :     put(set, element);
716 :     }
717 :     }
718 :    
719 :     void mutateSubSet(NavigableSet<Integer> set, int min, int max) {
720 :     int size = set.size();
721 :     int rangeSize = max - min + 1;
722 :    
723 :     // Remove a bunch of entries directly
724 :     for (int i = 0, n = rangeSize / 2; i < n; i++) {
725 :     remove(set, min - 5 + rnd.nextInt(rangeSize + 10));
726 :     }
727 :    
728 :     // Remove a bunch of entries with iterator
729 : jsr166 1.5 for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
730 : dl 1.2 if (rnd.nextBoolean()) {
731 :     bs.clear(it.next());
732 :     it.remove();
733 :     }
734 :     }
735 :    
736 :     // Add entries till we're back to original size
737 :     while (set.size() < size) {
738 :     int element = min - 5 + rnd.nextInt(rangeSize + 10);
739 :     if (element >= min && element<= max) {
740 :     put(set, element);
741 :     } else {
742 :     try {
743 :     set.add(element);
744 : jsr166 1.10 shouldThrow();
745 :     } catch (IllegalArgumentException success) {}
746 : dl 1.2 }
747 :     }
748 :     }
749 :    
750 :     void put(NavigableSet<Integer> set, int element) {
751 :     if (set.add(element))
752 :     bs.set(element);
753 :     }
754 :    
755 :     void remove(NavigableSet<Integer> set, int element) {
756 :     if (set.remove(element))
757 :     bs.clear(element);
758 :     }
759 :    
760 :     void bashSubSet(NavigableSet<Integer> set,
761 :     int min, int max, boolean ascending) {
762 :     check(set, min, max, ascending);
763 :     check(set.descendingSet(), min, max, !ascending);
764 :    
765 :     mutateSubSet(set, min, max);
766 :     check(set, min, max, ascending);
767 :     check(set.descendingSet(), min, max, !ascending);
768 :    
769 :     // Recurse
770 :     if (max - min < 2)
771 :     return;
772 :     int midPoint = (min + max) / 2;
773 :    
774 :     // headSet - pick direction and endpoint inclusion randomly
775 :     boolean incl = rnd.nextBoolean();
776 : dl 1.3 NavigableSet<Integer> hm = set.headSet(midPoint, incl);
777 : dl 1.2 if (ascending) {
778 :     if (rnd.nextBoolean())
779 :     bashSubSet(hm, min, midPoint - (incl ? 0 : 1), true);
780 :     else
781 :     bashSubSet(hm.descendingSet(), min, midPoint - (incl ? 0 : 1),
782 :     false);
783 :     } else {
784 :     if (rnd.nextBoolean())
785 :     bashSubSet(hm, midPoint + (incl ? 0 : 1), max, false);
786 :     else
787 :     bashSubSet(hm.descendingSet(), midPoint + (incl ? 0 : 1), max,
788 :     true);
789 :     }
790 :    
791 :     // tailSet - pick direction and endpoint inclusion randomly
792 :     incl = rnd.nextBoolean();
793 : dl 1.3 NavigableSet<Integer> tm = set.tailSet(midPoint,incl);
794 : dl 1.2 if (ascending) {
795 :     if (rnd.nextBoolean())
796 :     bashSubSet(tm, midPoint + (incl ? 0 : 1), max, true);
797 :     else
798 :     bashSubSet(tm.descendingSet(), midPoint + (incl ? 0 : 1), max,
799 :     false);
800 :     } else {
801 :     if (rnd.nextBoolean()) {
802 :     bashSubSet(tm, min, midPoint - (incl ? 0 : 1), false);
803 :     } else {
804 :     bashSubSet(tm.descendingSet(), min, midPoint - (incl ? 0 : 1),
805 :     true);
806 :     }
807 :     }
808 :    
809 :     // subSet - pick direction and endpoint inclusion randomly
810 :     int rangeSize = max - min + 1;
811 :     int[] endpoints = new int[2];
812 :     endpoints[0] = min + rnd.nextInt(rangeSize);
813 :     endpoints[1] = min + rnd.nextInt(rangeSize);
814 :     Arrays.sort(endpoints);
815 :     boolean lowIncl = rnd.nextBoolean();
816 :     boolean highIncl = rnd.nextBoolean();
817 :     if (ascending) {
818 : dl 1.3 NavigableSet<Integer> sm = set.subSet(
819 : dl 1.2 endpoints[0], lowIncl, endpoints[1], highIncl);
820 :     if (rnd.nextBoolean())
821 :     bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
822 :     endpoints[1] - (highIncl ? 0 : 1), true);
823 :     else
824 :     bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
825 :     endpoints[1] - (highIncl ? 0 : 1), false);
826 :     } else {
827 : dl 1.3 NavigableSet<Integer> sm = set.subSet(
828 : dl 1.2 endpoints[1], highIncl, endpoints[0], lowIncl);
829 :     if (rnd.nextBoolean())
830 :     bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
831 :     endpoints[1] - (highIncl ? 0 : 1), false);
832 :     else
833 :     bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
834 :     endpoints[1] - (highIncl ? 0 : 1), true);
835 :     }
836 :     }
837 :    
838 :     /**
839 :     * min and max are both inclusive. If max < min, interval is empty.
840 :     */
841 :     void check(NavigableSet<Integer> set,
842 :     final int min, final int max, final boolean ascending) {
843 :     class ReferenceSet {
844 :     int lower(int element) {
845 :     return ascending ?
846 :     lowerAscending(element) : higherAscending(element);
847 :     }
848 :     int floor(int element) {
849 :     return ascending ?
850 :     floorAscending(element) : ceilingAscending(element);
851 :     }
852 :     int ceiling(int element) {
853 :     return ascending ?
854 :     ceilingAscending(element) : floorAscending(element);
855 :     }
856 :     int higher(int element) {
857 :     return ascending ?
858 :     higherAscending(element) : lowerAscending(element);
859 :     }
860 :     int first() {
861 :     return ascending ? firstAscending() : lastAscending();
862 :     }
863 :     int last() {
864 :     return ascending ? lastAscending() : firstAscending();
865 :     }
866 :     int lowerAscending(int element) {
867 :     return floorAscending(element - 1);
868 :     }
869 :     int floorAscending(int element) {
870 :     if (element < min)
871 :     return -1;
872 :     else if (element > max)
873 :     element = max;
874 :    
875 :     // BitSet should support this! Test would run much faster
876 :     while (element >= min) {
877 :     if (bs.get(element))
878 : jsr166 1.15 return element;
879 : dl 1.2 element--;
880 :     }
881 :     return -1;
882 :     }
883 :     int ceilingAscending(int element) {
884 :     if (element < min)
885 :     element = min;
886 :     else if (element > max)
887 :     return -1;
888 :     int result = bs.nextSetBit(element);
889 :     return result > max ? -1 : result;
890 :     }
891 :     int higherAscending(int element) {
892 :     return ceilingAscending(element + 1);
893 :     }
894 :     private int firstAscending() {
895 :     int result = ceilingAscending(min);
896 :     return result > max ? -1 : result;
897 :     }
898 :     private int lastAscending() {
899 :     int result = floorAscending(max);
900 :     return result < min ? -1 : result;
901 :     }
902 :     }
903 :     ReferenceSet rs = new ReferenceSet();
904 :    
905 :     // Test contents using containsElement
906 :     int size = 0;
907 :     for (int i = min; i <= max; i++) {
908 :     boolean bsContainsI = bs.get(i);
909 :     assertEquals(bsContainsI, set.contains(i));
910 :     if (bsContainsI)
911 :     size++;
912 :     }
913 :     assertEquals(set.size(), size);
914 :    
915 :     // Test contents using contains elementSet iterator
916 :     int size2 = 0;
917 :     int previousElement = -1;
918 :     for (int element : set) {
919 :     assertTrue(bs.get(element));
920 :     size2++;
921 :     assertTrue(previousElement < 0 || (ascending ?
922 :     element - previousElement > 0 : element - previousElement < 0));
923 :     previousElement = element;
924 :     }
925 :     assertEquals(size2, size);
926 :    
927 :     // Test navigation ops
928 :     for (int element = min - 1; element <= max + 1; element++) {
929 :     assertEq(set.lower(element), rs.lower(element));
930 :     assertEq(set.floor(element), rs.floor(element));
931 :     assertEq(set.higher(element), rs.higher(element));
932 :     assertEq(set.ceiling(element), rs.ceiling(element));
933 :     }
934 :    
935 :     // Test extrema
936 :     if (set.size() != 0) {
937 :     assertEq(set.first(), rs.first());
938 :     assertEq(set.last(), rs.last());
939 :     } else {
940 :     assertEq(rs.first(), -1);
941 :     assertEq(rs.last(), -1);
942 :     try {
943 :     set.first();
944 : jsr166 1.10 shouldThrow();
945 :     } catch (NoSuchElementException success) {}
946 : dl 1.2 try {
947 :     set.last();
948 : jsr166 1.10 shouldThrow();
949 :     } catch (NoSuchElementException success) {}
950 : dl 1.2 }
951 :     }
952 :    
953 :     static void assertEq(Integer i, int j) {
954 :     if (i == null)
955 :     assertEquals(j, -1);
956 :     else
957 :     assertEquals((int) i, j);
958 :     }
959 :    
960 :     static boolean eq(Integer i, int j) {
961 :     return i == null ? j == -1 : i == j;
962 :     }
963 :    
964 : dl 1.1 }

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8