1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package com.google.common.collect;
18
19 import static com.google.common.collect.Iterables.unmodifiableIterable;
20 import static com.google.common.collect.Sets.newEnumSet;
21 import static com.google.common.collect.Sets.newHashSet;
22 import static com.google.common.collect.Sets.newLinkedHashSet;
23 import static com.google.common.collect.Sets.powerSet;
24 import static com.google.common.collect.Sets.unmodifiableNavigableSet;
25 import static com.google.common.collect.testing.IteratorFeature.UNMODIFIABLE;
26 import static com.google.common.truth.Truth.assertThat;
27 import static java.io.ObjectStreamConstants.TC_REFERENCE;
28 import static java.io.ObjectStreamConstants.baseWireHandle;
29 import static java.util.Collections.emptySet;
30 import static java.util.Collections.singleton;
31
32 import com.google.common.annotations.GwtCompatible;
33 import com.google.common.annotations.GwtIncompatible;
34 import com.google.common.collect.testing.AnEnum;
35 import com.google.common.collect.testing.IteratorTester;
36 import com.google.common.collect.testing.MinimalIterable;
37 import com.google.common.collect.testing.NavigableSetTestSuiteBuilder;
38 import com.google.common.collect.testing.SafeTreeSet;
39 import com.google.common.collect.testing.SetTestSuiteBuilder;
40 import com.google.common.collect.testing.TestEnumSetGenerator;
41 import com.google.common.collect.testing.TestStringSetGenerator;
42 import com.google.common.collect.testing.features.CollectionFeature;
43 import com.google.common.collect.testing.features.CollectionSize;
44 import com.google.common.collect.testing.features.SetFeature;
45 import com.google.common.testing.EqualsTester;
46 import com.google.common.testing.NullPointerTester;
47 import com.google.common.testing.SerializableTester;
48
49 import junit.framework.Test;
50 import junit.framework.TestCase;
51 import junit.framework.TestSuite;
52
53 import java.io.ByteArrayInputStream;
54 import java.io.ByteArrayOutputStream;
55 import java.io.IOException;
56 import java.io.ObjectInputStream;
57 import java.io.ObjectOutputStream;
58 import java.io.Serializable;
59 import java.nio.ByteBuffer;
60 import java.util.ArrayList;
61 import java.util.Arrays;
62 import java.util.Collection;
63 import java.util.Collections;
64 import java.util.Comparator;
65 import java.util.EnumSet;
66 import java.util.HashMap;
67 import java.util.HashSet;
68 import java.util.Iterator;
69 import java.util.LinkedHashMap;
70 import java.util.LinkedHashSet;
71 import java.util.List;
72 import java.util.Map;
73 import java.util.NavigableSet;
74 import java.util.NoSuchElementException;
75 import java.util.Set;
76 import java.util.SortedSet;
77 import java.util.TreeSet;
78 import java.util.concurrent.CopyOnWriteArraySet;
79
80 import javax.annotation.Nullable;
81
82
83
84
85
86
87
88 @GwtCompatible(emulated = true)
89 public class SetsTest extends TestCase {
90
91 private static final IteratorTester.KnownOrder KNOWN_ORDER =
92 IteratorTester.KnownOrder.KNOWN_ORDER;
93
94 private static final Collection<Integer> EMPTY_COLLECTION
95 = Arrays.<Integer>asList();
96
97 private static final Collection<Integer> SOME_COLLECTION
98 = Arrays.asList(0, 1, 1);
99
100 private static final Iterable<Integer> SOME_ITERABLE
101 = new Iterable<Integer>() {
102 @Override
103 public Iterator<Integer> iterator() {
104 return SOME_COLLECTION.iterator();
105 }
106 };
107
108 private static final List<Integer> LONGER_LIST
109 = Arrays.asList(8, 6, 7, 5, 3, 0, 9);
110
111 private static final Comparator<Integer> SOME_COMPARATOR
112 = Collections.reverseOrder();
113
114 @GwtIncompatible("suite")
115 public static Test suite() {
116 TestSuite suite = new TestSuite();
117 suite.addTestSuite(SetsTest.class);
118
119 suite.addTest(SetTestSuiteBuilder.using(new TestStringSetGenerator() {
120 @Override protected Set<String> create(String[] elements) {
121 return Sets.newConcurrentHashSet(Arrays.asList(elements));
122 }
123 })
124 .named("Sets.newConcurrentHashSet")
125 .withFeatures(CollectionSize.ANY, SetFeature.GENERAL_PURPOSE)
126 .createTestSuite());
127
128 suite.addTest(SetTestSuiteBuilder.using(new TestStringSetGenerator() {
129 @Override protected Set<String> create(String[] elements) {
130 int size = elements.length;
131
132 Set<String> set1 = (size > 1)
133 ? Sets.newHashSet(
134 Arrays.asList(elements).subList(0, size - 1))
135 : Sets.newHashSet(elements);
136
137 Set<String> set2 = (size > 0)
138 ? Sets.newHashSet(
139 Arrays.asList(elements).subList(1, size))
140 : Sets.<String>newHashSet();
141 return Sets.union(set1, set2);
142 }
143 })
144 .named("Sets.union")
145 .withFeatures(CollectionSize.ANY, CollectionFeature.ALLOWS_NULL_VALUES)
146 .createTestSuite());
147
148 suite.addTest(SetTestSuiteBuilder.using(new TestStringSetGenerator() {
149 @Override protected Set<String> create(String[] elements) {
150 Set<String> set1 = Sets.newHashSet(elements);
151 set1.add(samples().e3);
152 Set<String> set2 = Sets.newHashSet(elements);
153 set2.add(samples().e4);
154 return Sets.intersection(set1, set2);
155 }
156 })
157 .named("Sets.intersection")
158 .withFeatures(CollectionSize.ANY, CollectionFeature.ALLOWS_NULL_VALUES)
159 .createTestSuite());
160
161 suite.addTest(SetTestSuiteBuilder.using(new TestStringSetGenerator() {
162 @Override protected Set<String> create(String[] elements) {
163 Set<String> set1 = Sets.newHashSet(elements);
164 set1.add(samples().e3);
165 Set<String> set2 = Sets.newHashSet(samples().e3);
166 return Sets.difference(set1, set2);
167 }
168 })
169 .named("Sets.difference")
170 .withFeatures(CollectionSize.ANY, CollectionFeature.ALLOWS_NULL_VALUES)
171 .createTestSuite());
172
173 suite.addTest(SetTestSuiteBuilder.using(new TestEnumSetGenerator() {
174 @Override protected Set<AnEnum> create(AnEnum[] elements) {
175 AnEnum[] otherElements = new AnEnum[elements.length - 1];
176 System.arraycopy(
177 elements, 1, otherElements, 0, otherElements.length);
178 return Sets.immutableEnumSet(elements[0], otherElements);
179 }
180 })
181 .named("Sets.immutableEnumSet")
182 .withFeatures(CollectionSize.ONE, CollectionSize.SEVERAL,
183 CollectionFeature.ALLOWS_NULL_QUERIES)
184 .createTestSuite());
185
186 suite.addTest(NavigableSetTestSuiteBuilder.using(new TestStringSetGenerator() {
187 @Override protected Set<String> create(String[] elements) {
188 SafeTreeSet<String> set = new SafeTreeSet<String>(Arrays.asList(elements));
189 return Sets.unmodifiableNavigableSet(set);
190 }
191
192 @Override
193 public List<String> order(List<String> insertionOrder) {
194 return Ordering.natural().sortedCopy(insertionOrder);
195 }
196 })
197 .named("Sets.unmodifiableNavigableSet[TreeSet]")
198 .withFeatures(CollectionSize.ANY, CollectionFeature.KNOWN_ORDER,
199 CollectionFeature.SERIALIZABLE)
200 .createTestSuite());
201
202 suite.addTest(testsForFilter());
203 suite.addTest(testsForFilterNoNulls());
204 suite.addTest(testsForFilterFiltered());
205
206 return suite;
207 }
208
209 @GwtIncompatible("suite")
210 private static Test testsForFilter() {
211 return SetTestSuiteBuilder.using(new TestStringSetGenerator() {
212 @Override public Set<String> create(String[] elements) {
213 Set<String> unfiltered = Sets.newLinkedHashSet();
214 unfiltered.add("yyy");
215 Collections.addAll(unfiltered, elements);
216 unfiltered.add("zzz");
217 return Sets.filter(unfiltered, Collections2Test.NOT_YYY_ZZZ);
218 }
219 })
220 .named("Sets.filter")
221 .withFeatures(
222 CollectionFeature.SUPPORTS_ADD,
223 CollectionFeature.SUPPORTS_REMOVE,
224 CollectionFeature.ALLOWS_NULL_VALUES,
225 CollectionFeature.KNOWN_ORDER,
226 CollectionSize.ANY)
227 .createTestSuite();
228 }
229
230 @GwtIncompatible("suite")
231 private static Test testsForFilterNoNulls() {
232 TestSuite suite = new TestSuite();
233 suite.addTest(SetTestSuiteBuilder.using(new TestStringSetGenerator() {
234 @Override public Set<String> create(String[] elements) {
235 Set<String> unfiltered = Sets.newLinkedHashSet();
236 unfiltered.add("yyy");
237 unfiltered.addAll(ImmutableList.copyOf(elements));
238 unfiltered.add("zzz");
239 return Sets.filter(unfiltered, Collections2Test.LENGTH_1);
240 }
241 })
242 .named("Sets.filter, no nulls")
243 .withFeatures(
244 CollectionFeature.SUPPORTS_ADD,
245 CollectionFeature.SUPPORTS_REMOVE,
246 CollectionFeature.KNOWN_ORDER,
247 CollectionSize.ANY,
248 CollectionFeature.ALLOWS_NULL_QUERIES)
249 .createTestSuite());
250 suite.addTest(NavigableSetTestSuiteBuilder.using(new TestStringSetGenerator() {
251 @Override public NavigableSet<String> create(String[] elements) {
252 NavigableSet<String> unfiltered = Sets.newTreeSet();
253 unfiltered.add("yyy");
254 unfiltered.addAll(ImmutableList.copyOf(elements));
255 unfiltered.add("zzz");
256 return Sets.filter(unfiltered, Collections2Test.LENGTH_1);
257 }
258
259 @Override
260 public List<String> order(List<String> insertionOrder) {
261 return Ordering.natural().sortedCopy(insertionOrder);
262 }
263 })
264 .named("Sets.filter[NavigableSet]")
265 .withFeatures(
266 CollectionFeature.SUPPORTS_ADD,
267 CollectionFeature.SUPPORTS_REMOVE,
268 CollectionFeature.KNOWN_ORDER,
269 CollectionSize.ANY,
270 CollectionFeature.ALLOWS_NULL_QUERIES)
271 .createTestSuite());
272 return suite;
273 }
274
275 @GwtIncompatible("suite")
276 private static Test testsForFilterFiltered() {
277 return SetTestSuiteBuilder.using(new TestStringSetGenerator() {
278 @Override public Set<String> create(String[] elements) {
279 Set<String> unfiltered = Sets.newLinkedHashSet();
280 unfiltered.add("yyy");
281 unfiltered.addAll(ImmutableList.copyOf(elements));
282 unfiltered.add("zzz");
283 unfiltered.add("abc");
284 return Sets.filter(
285 Sets.filter(unfiltered, Collections2Test.LENGTH_1),
286 Collections2Test.NOT_YYY_ZZZ);
287 }
288 })
289 .named("Sets.filter, filtered input")
290 .withFeatures(
291 CollectionFeature.SUPPORTS_ADD,
292 CollectionFeature.SUPPORTS_REMOVE,
293 CollectionFeature.KNOWN_ORDER,
294 CollectionSize.ANY,
295 CollectionFeature.ALLOWS_NULL_QUERIES)
296 .createTestSuite();
297 }
298
299 private enum SomeEnum { A, B, C, D }
300
301 public void testImmutableEnumSet() {
302 Set<SomeEnum> units = Sets.immutableEnumSet(SomeEnum.D, SomeEnum.B);
303
304 assertThat(units).has().exactly(SomeEnum.B, SomeEnum.D).inOrder();
305 try {
306 units.remove(SomeEnum.B);
307 fail("ImmutableEnumSet should throw an exception on remove()");
308 } catch (UnsupportedOperationException expected) {}
309 try {
310 units.add(SomeEnum.C);
311 fail("ImmutableEnumSet should throw an exception on add()");
312 } catch (UnsupportedOperationException expected) {}
313 }
314
315 @GwtIncompatible("SerializableTester")
316 public void testImmutableEnumSet_serialized() {
317 Set<SomeEnum> units = Sets.immutableEnumSet(SomeEnum.D, SomeEnum.B);
318
319 assertThat(units).has().exactly(SomeEnum.B, SomeEnum.D).inOrder();
320
321 Set<SomeEnum> copy = SerializableTester.reserializeAndAssert(units);
322 assertTrue(copy instanceof ImmutableEnumSet);
323 }
324
325 public void testImmutableEnumSet_fromIterable() {
326 ImmutableSet<SomeEnum> none
327 = Sets.immutableEnumSet(MinimalIterable.<SomeEnum>of());
328 assertThat(none).isEmpty();
329
330 ImmutableSet<SomeEnum> one
331 = Sets.immutableEnumSet(MinimalIterable.of(SomeEnum.B));
332 assertThat(one).has().item(SomeEnum.B);
333
334 ImmutableSet<SomeEnum> two
335 = Sets.immutableEnumSet(MinimalIterable.of(SomeEnum.D, SomeEnum.B));
336 assertThat(two).has().exactly(SomeEnum.B, SomeEnum.D).inOrder();
337 }
338
339 @GwtIncompatible("java serialization not supported in GWT.")
340 public void testImmutableEnumSet_deserializationMakesDefensiveCopy()
341 throws Exception {
342 ImmutableSet<SomeEnum> original =
343 Sets.immutableEnumSet(SomeEnum.A, SomeEnum.B);
344 int handleOffset = 6;
345 byte[] serializedForm = serializeWithBackReference(original, handleOffset);
346 ObjectInputStream in =
347 new ObjectInputStream(new ByteArrayInputStream(serializedForm));
348
349 ImmutableSet<?> deserialized = (ImmutableSet<?>) in.readObject();
350 EnumSet<?> delegate = (EnumSet<?>) in.readObject();
351
352 assertEquals(original, deserialized);
353 assertTrue(delegate.remove(SomeEnum.A));
354 assertTrue(deserialized.contains(SomeEnum.A));
355 }
356
357 @GwtIncompatible("java serialization not supported in GWT.")
358 private static byte[] serializeWithBackReference(
359 Object original, int handleOffset) throws IOException {
360 ByteArrayOutputStream bos = new ByteArrayOutputStream();
361 ObjectOutputStream out = new ObjectOutputStream(bos);
362
363 out.writeObject(original);
364
365 byte[] handle = toByteArray(baseWireHandle + handleOffset);
366 byte[] ref = prepended(TC_REFERENCE, handle);
367 bos.write(ref);
368
369 return bos.toByteArray();
370 }
371
372 private static byte[] prepended(byte b, byte[] array) {
373 byte[] out = new byte[array.length + 1];
374 out[0] = b;
375 System.arraycopy(array, 0, out, 1, array.length);
376 return out;
377 }
378
379 @GwtIncompatible("java.nio.ByteBuffer")
380 private static byte[] toByteArray(int h) {
381 return ByteBuffer.allocate(4).putInt(h).array();
382 }
383
384 public void testNewEnumSet_empty() {
385 EnumSet<SomeEnum> copy =
386 newEnumSet(Collections.<SomeEnum>emptySet(), SomeEnum.class);
387 assertEquals(EnumSet.noneOf(SomeEnum.class), copy);
388 }
389
390 public void testNewEnumSet_enumSet() {
391 EnumSet<SomeEnum> set = EnumSet.of(SomeEnum.A, SomeEnum.D);
392 assertEquals(set, newEnumSet(set, SomeEnum.class));
393 }
394
395 public void testNewEnumSet_collection() {
396 Set<SomeEnum> set = ImmutableSet.of(SomeEnum.B, SomeEnum.C);
397 assertEquals(set, newEnumSet(set, SomeEnum.class));
398 }
399
400 public void testNewEnumSet_iterable() {
401 Set<SomeEnum> set = ImmutableSet.of(SomeEnum.A, SomeEnum.B, SomeEnum.C);
402 assertEquals(set, newEnumSet(unmodifiableIterable(set), SomeEnum.class));
403 }
404
405 public void testNewHashSetEmpty() {
406 HashSet<Integer> set = Sets.newHashSet();
407 verifySetContents(set, EMPTY_COLLECTION);
408 }
409
410 public void testNewHashSetVarArgs() {
411 HashSet<Integer> set = Sets.newHashSet(0, 1, 1);
412 verifySetContents(set, Arrays.asList(0, 1));
413 }
414
415 public void testNewHashSetFromCollection() {
416 HashSet<Integer> set = Sets.newHashSet(SOME_COLLECTION);
417 verifySetContents(set, SOME_COLLECTION);
418 }
419
420 public void testNewHashSetFromIterable() {
421 HashSet<Integer> set = Sets.newHashSet(SOME_ITERABLE);
422 verifySetContents(set, SOME_ITERABLE);
423 }
424
425 public void testNewHashSetWithExpectedSizeSmall() {
426 HashSet<Integer> set = Sets.newHashSetWithExpectedSize(0);
427 verifySetContents(set, EMPTY_COLLECTION);
428 }
429
430 public void testNewHashSetWithExpectedSizeLarge() {
431 HashSet<Integer> set = Sets.newHashSetWithExpectedSize(1000);
432 verifySetContents(set, EMPTY_COLLECTION);
433 }
434
435 public void testNewHashSetFromIterator() {
436 HashSet<Integer> set = Sets.newHashSet(SOME_COLLECTION.iterator());
437 verifySetContents(set, SOME_COLLECTION);
438 }
439
440 public void testNewConcurrentHashSetEmpty() {
441 Set<Integer> set = Sets.newConcurrentHashSet();
442 verifySetContents(set, EMPTY_COLLECTION);
443 }
444
445 public void testNewConcurrentHashSetFromCollection() {
446 Set<Integer> set = Sets.newConcurrentHashSet(SOME_COLLECTION);
447 verifySetContents(set, SOME_COLLECTION);
448 }
449
450 public void testNewLinkedHashSetEmpty() {
451 LinkedHashSet<Integer> set = Sets.newLinkedHashSet();
452 verifyLinkedHashSetContents(set, EMPTY_COLLECTION);
453 }
454
455 public void testNewLinkedHashSetFromCollection() {
456 LinkedHashSet<Integer> set = Sets.newLinkedHashSet(LONGER_LIST);
457 verifyLinkedHashSetContents(set, LONGER_LIST);
458 }
459
460 public void testNewLinkedHashSetFromIterable() {
461 LinkedHashSet<Integer> set = Sets.newLinkedHashSet(new Iterable<Integer>()
462 {
463 @Override
464 public Iterator<Integer> iterator() {
465 return LONGER_LIST.iterator();
466 }
467 });
468 verifyLinkedHashSetContents(set, LONGER_LIST);
469 }
470
471 public void testNewLinkedHashSetWithExpectedSizeSmall() {
472 LinkedHashSet<Integer> set = Sets.newLinkedHashSetWithExpectedSize(0);
473 verifySetContents(set, EMPTY_COLLECTION);
474 }
475
476 public void testNewLinkedHashSetWithExpectedSizeLarge() {
477 LinkedHashSet<Integer> set = Sets.newLinkedHashSetWithExpectedSize(1000);
478 verifySetContents(set, EMPTY_COLLECTION);
479 }
480
481 public void testNewTreeSetEmpty() {
482 TreeSet<Integer> set = Sets.newTreeSet();
483 verifySortedSetContents(set, EMPTY_COLLECTION, null);
484 }
485
486 public void testNewTreeSetEmptyDerived() {
487 TreeSet<Derived> set = Sets.newTreeSet();
488 assertTrue(set.isEmpty());
489 set.add(new Derived("foo"));
490 set.add(new Derived("bar"));
491 assertThat(set).has().exactly(new Derived("bar"), new Derived("foo")).inOrder();
492 }
493
494 public void testNewTreeSetEmptyNonGeneric() {
495 TreeSet<LegacyComparable> set = Sets.newTreeSet();
496 assertTrue(set.isEmpty());
497 set.add(new LegacyComparable("foo"));
498 set.add(new LegacyComparable("bar"));
499 assertThat(set).has()
500 .exactly(new LegacyComparable("bar"), new LegacyComparable("foo")).inOrder();
501 }
502
503 public void testNewTreeSetFromCollection() {
504 TreeSet<Integer> set = Sets.newTreeSet(SOME_COLLECTION);
505 verifySortedSetContents(set, SOME_COLLECTION, null);
506 }
507
508 public void testNewTreeSetFromIterable() {
509 TreeSet<Integer> set = Sets.newTreeSet(SOME_ITERABLE);
510 verifySortedSetContents(set, SOME_ITERABLE, null);
511 }
512
513 public void testNewTreeSetFromIterableDerived() {
514 Iterable<Derived> iterable =
515 Arrays.asList(new Derived("foo"), new Derived("bar"));
516 TreeSet<Derived> set = Sets.newTreeSet(iterable);
517 assertThat(set).has().exactly(
518 new Derived("bar"), new Derived("foo")).inOrder();
519 }
520
521 public void testNewTreeSetFromIterableNonGeneric() {
522 Iterable<LegacyComparable> iterable =
523 Arrays.asList(new LegacyComparable("foo"), new LegacyComparable("bar"));
524 TreeSet<LegacyComparable> set = Sets.newTreeSet(iterable);
525 assertThat(set).has().exactly(
526 new LegacyComparable("bar"), new LegacyComparable("foo")).inOrder();
527 }
528
529 public void testNewTreeSetEmptyWithComparator() {
530 TreeSet<Integer> set = Sets.newTreeSet(SOME_COMPARATOR);
531 verifySortedSetContents(set, EMPTY_COLLECTION, SOME_COMPARATOR);
532 }
533
534 public void testNewIdentityHashSet() {
535 Set<Integer> set = Sets.newIdentityHashSet();
536 Integer value1 = new Integer(12357);
537 Integer value2 = new Integer(12357);
538 assertTrue(set.add(value1));
539 assertFalse(set.contains(value2));
540 assertTrue(set.contains(value1));
541 assertTrue(set.add(value2));
542 assertEquals(2, set.size());
543 }
544
545 @GwtIncompatible("CopyOnWriteArraySet")
546 public void testNewCOWASEmpty() {
547 CopyOnWriteArraySet<Integer> set = Sets.newCopyOnWriteArraySet();
548 verifySetContents(set, EMPTY_COLLECTION);
549 }
550
551 @GwtIncompatible("CopyOnWriteArraySet")
552 public void testNewCOWASFromIterable() {
553 CopyOnWriteArraySet<Integer> set = Sets.newCopyOnWriteArraySet(SOME_ITERABLE);
554 verifySetContents(set, SOME_COLLECTION);
555 }
556
557 public void testComplementOfEnumSet() {
558 Set<SomeEnum> units = EnumSet.of(SomeEnum.B, SomeEnum.D);
559 EnumSet<SomeEnum> otherUnits = Sets.complementOf(units);
560 verifySetContents(otherUnits, EnumSet.of(SomeEnum.A, SomeEnum.C));
561 }
562
563 public void testComplementOfEnumSetWithType() {
564 Set<SomeEnum> units = EnumSet.of(SomeEnum.B, SomeEnum.D);
565 EnumSet<SomeEnum> otherUnits = Sets.complementOf(units, SomeEnum.class);
566 verifySetContents(otherUnits, EnumSet.of(SomeEnum.A, SomeEnum.C));
567 }
568
569 public void testComplementOfRegularSet() {
570 Set<SomeEnum> units = Sets.newHashSet(SomeEnum.B, SomeEnum.D);
571 EnumSet<SomeEnum> otherUnits = Sets.complementOf(units);
572 verifySetContents(otherUnits, EnumSet.of(SomeEnum.A, SomeEnum.C));
573 }
574
575 public void testComplementOfRegularSetWithType() {
576 Set<SomeEnum> units = Sets.newHashSet(SomeEnum.B, SomeEnum.D);
577 EnumSet<SomeEnum> otherUnits = Sets.complementOf(units, SomeEnum.class);
578 verifySetContents(otherUnits, EnumSet.of(SomeEnum.A, SomeEnum.C));
579 }
580
581 public void testComplementOfEmptySet() {
582 Set<SomeEnum> noUnits = Collections.emptySet();
583 EnumSet<SomeEnum> allUnits = Sets.complementOf(noUnits, SomeEnum.class);
584 verifySetContents(EnumSet.allOf(SomeEnum.class), allUnits);
585 }
586
587 public void testComplementOfFullSet() {
588 Set<SomeEnum> allUnits = Sets.newHashSet(SomeEnum.values());
589 EnumSet<SomeEnum> noUnits = Sets.complementOf(allUnits, SomeEnum.class);
590 verifySetContents(noUnits, EnumSet.noneOf(SomeEnum.class));
591 }
592
593 public void testComplementOfEmptyEnumSetWithoutType() {
594 Set<SomeEnum> noUnits = EnumSet.noneOf(SomeEnum.class);
595 EnumSet<SomeEnum> allUnits = Sets.complementOf(noUnits);
596 verifySetContents(allUnits, EnumSet.allOf(SomeEnum.class));
597 }
598
599 public void testComplementOfEmptySetWithoutTypeDoesntWork() {
600 Set<SomeEnum> set = Collections.emptySet();
601 try {
602 Sets.complementOf(set);
603 fail();
604 } catch (IllegalArgumentException expected) {}
605 }
606
607 @GwtIncompatible("NullPointerTester")
608 public void testNullPointerExceptions() {
609 new NullPointerTester()
610 .setDefault(Enum.class, SomeEnum.A)
611 .setDefault(Class.class, SomeEnum.class)
612 .testAllPublicStaticMethods(Sets.class);
613 }
614
615 public void testNewSetFromMap() {
616 Set<Integer> set = Sets.newSetFromMap(new HashMap<Integer, Boolean>());
617 set.addAll(SOME_COLLECTION);
618 verifySetContents(set, SOME_COLLECTION);
619 }
620
621 @GwtIncompatible("SerializableTester")
622 public void testNewSetFromMapSerialization() {
623 Set<Integer> set =
624 Sets.newSetFromMap(new LinkedHashMap<Integer, Boolean>());
625 set.addAll(SOME_COLLECTION);
626 Set<Integer> copy = SerializableTester.reserializeAndAssert(set);
627 assertThat(copy).has().exactly(0, 1).inOrder();
628 }
629
630 public void testNewSetFromMapIllegal() {
631 Map<Integer, Boolean> map = new LinkedHashMap<Integer, Boolean>();
632 map.put(2, true);
633 try {
634 Sets.newSetFromMap(map);
635 fail();
636 } catch (IllegalArgumentException expected) {}
637 }
638
639
640
641
642
643
644
645 @SuppressWarnings("unchecked")
646 public void testCartesianProduct_zeroary() {
647 assertThat(Sets.cartesianProduct()).has().exactly(list());
648 }
649
650
651
652
653
654 @SuppressWarnings("unchecked")
655 public void testCartesianProduct_unary() {
656 assertThat(Sets.cartesianProduct(set(1, 2))).has().exactly(list(1), list(2));
657 }
658
659 @SuppressWarnings("unchecked")
660 public void testCartesianProduct_binary0x0() {
661 Set<Integer> mt = emptySet();
662 assertEmpty(Sets.cartesianProduct(mt, mt));
663 }
664
665 @SuppressWarnings("unchecked")
666 public void testCartesianProduct_binary0x1() {
667 Set<Integer> mt = emptySet();
668 assertEmpty(Sets.cartesianProduct(mt, set(1)));
669 }
670
671 @SuppressWarnings("unchecked")
672 public void testCartesianProduct_binary1x0() {
673 Set<Integer> mt = emptySet();
674 assertEmpty(Sets.cartesianProduct(set(1), mt));
675 }
676
677 private static void assertEmpty(Set<? extends List<?>> set) {
678 assertTrue(set.isEmpty());
679 assertEquals(0, set.size());
680 assertFalse(set.iterator().hasNext());
681 }
682
683 @SuppressWarnings("unchecked")
684 public void testCartesianProduct_binary1x1() {
685 assertThat(Sets.cartesianProduct(set(1), set(2))).has().item(list(1, 2));
686 }
687
688 @SuppressWarnings("unchecked")
689 public void testCartesianProduct_binary1x2() {
690 assertThat(Sets.cartesianProduct(set(1), set(2, 3)))
691 .has().exactly(list(1, 2), list(1, 3)).inOrder();
692 }
693
694 @SuppressWarnings("unchecked")
695 public void testCartesianProduct_binary2x2() {
696 assertThat(Sets.cartesianProduct(set(1, 2), set(3, 4)))
697 .has().exactly(list(1, 3), list(1, 4), list(2, 3), list(2, 4)).inOrder();
698 }
699
700 @SuppressWarnings("unchecked")
701 public void testCartesianProduct_2x2x2() {
702 assertThat(Sets.cartesianProduct(set(0, 1), set(0, 1), set(0, 1))).has().exactly(
703 list(0, 0, 0), list(0, 0, 1), list(0, 1, 0), list(0, 1, 1),
704 list(1, 0, 0), list(1, 0, 1), list(1, 1, 0), list(1, 1, 1)).inOrder();
705 }
706
707 @SuppressWarnings("unchecked")
708 public void testCartesianProduct_contains() {
709 Set<List<Integer>> actual = Sets.cartesianProduct(set(1, 2), set(3, 4));
710 assertTrue(actual.contains(list(1, 3)));
711 assertTrue(actual.contains(list(1, 4)));
712 assertTrue(actual.contains(list(2, 3)));
713 assertTrue(actual.contains(list(2, 4)));
714 assertFalse(actual.contains(list(3, 1)));
715 }
716
717 @SuppressWarnings("unchecked")
718 public void testCartesianProduct_unrelatedTypes() {
719 Set<Integer> x = set(1, 2);
720 Set<String> y = set("3", "4");
721
722 List<Object> exp1 = list((Object) 1, "3");
723 List<Object> exp2 = list((Object) 1, "4");
724 List<Object> exp3 = list((Object) 2, "3");
725 List<Object> exp4 = list((Object) 2, "4");
726
727 assertThat(Sets.<Object>cartesianProduct(x, y))
728 .has().exactly(exp1, exp2, exp3, exp4).inOrder();
729 }
730
731 @SuppressWarnings("unchecked")
732 public void testCartesianProductTooBig() {
733 Set<Integer> set = ContiguousSet.create(Range.closed(0, 10000), DiscreteDomain.integers());
734 try {
735 Sets.cartesianProduct(set, set, set, set, set);
736 fail("Expected IAE");
737 } catch (IllegalArgumentException expected) {}
738 }
739
740 @SuppressWarnings("unchecked")
741 public void testCartesianProduct_hashCode() {
742
743
744 Set<List<Integer>> degenerate = Sets.cartesianProduct();
745 checkHashCode(degenerate);
746
747 checkHashCode(Sets.cartesianProduct(set(1, 2)));
748
749 int num = Integer.MAX_VALUE / 3 * 2;
750 checkHashCode(Sets.cartesianProduct(set(1, 2, num)));
751
752 Set<Integer> mt = emptySet();
753 checkHashCode(Sets.cartesianProduct(mt, mt));
754 checkHashCode(Sets.cartesianProduct(mt, set(num)));
755 checkHashCode(Sets.cartesianProduct(set(num), mt));
756 checkHashCode(Sets.cartesianProduct(set(num), set(1)));
757 checkHashCode(Sets.cartesianProduct(set(1), set(2, num)));
758 checkHashCode(Sets.cartesianProduct(set(1, num), set(2, num - 1)));
759 checkHashCode(Sets.cartesianProduct(
760 set(1, num), set(2, num - 1), set(3, num + 1)));
761
762
763 checkHashCode(Sets.cartesianProduct(
764 set(1, num, num + 1), set(2), set(3, num + 2), set(4, 5, 6, 7, 8)));
765 }
766
767 public void testPowerSetEmpty() {
768 ImmutableSet<Integer> elements = ImmutableSet.of();
769 Set<Set<Integer>> powerSet = powerSet(elements);
770 assertEquals(1, powerSet.size());
771 assertEquals(ImmutableSet.of(ImmutableSet.of()), powerSet);
772 assertEquals(0, powerSet.hashCode());
773 }
774
775 public void testPowerSetContents() {
776 ImmutableSet<Integer> elements = ImmutableSet.of(1, 2, 3);
777 Set<Set<Integer>> powerSet = powerSet(elements);
778 assertEquals(8, powerSet.size());
779 assertEquals(4 * 1 + 4 * 2 + 4 * 3, powerSet.hashCode());
780
781 Set<Set<Integer>> expected = newHashSet();
782 expected.add(ImmutableSet.<Integer>of());
783 expected.add(ImmutableSet.of(1));
784 expected.add(ImmutableSet.of(2));
785 expected.add(ImmutableSet.of(3));
786 expected.add(ImmutableSet.of(1, 2));
787 expected.add(ImmutableSet.of(1, 3));
788 expected.add(ImmutableSet.of(2, 3));
789 expected.add(ImmutableSet.of(1, 2, 3));
790
791 Set<Set<Integer>> almostPowerSet = newHashSet(expected);
792 almostPowerSet.remove(ImmutableSet.of(1, 2, 3));
793 almostPowerSet.add(ImmutableSet.of(1, 2, 4));
794
795 new EqualsTester()
796 .addEqualityGroup(expected, powerSet)
797 .addEqualityGroup(ImmutableSet.of(1, 2, 3))
798 .addEqualityGroup(almostPowerSet)
799 .testEquals();
800
801 for (Set<Integer> subset : expected) {
802 assertTrue(powerSet.contains(subset));
803 }
804 assertFalse(powerSet.contains(ImmutableSet.of(1, 2, 4)));
805 assertFalse(powerSet.contains(singleton(null)));
806 assertFalse(powerSet.contains(null));
807 assertFalse(powerSet.contains("notASet"));
808 }
809
810 public void testPowerSetIteration_manual() {
811 ImmutableSet<Integer> elements = ImmutableSet.of(1, 2, 3);
812 Set<Set<Integer>> powerSet = powerSet(elements);
813
814 Iterator<Set<Integer>> i = powerSet.iterator();
815 assertEquals(ImmutableSet.of(), i.next());
816 assertEquals(ImmutableSet.of(1), i.next());
817 assertEquals(ImmutableSet.of(2), i.next());
818 assertEquals(ImmutableSet.of(2, 1), i.next());
819 assertEquals(ImmutableSet.of(3), i.next());
820 assertEquals(ImmutableSet.of(3, 1), i.next());
821 assertEquals(ImmutableSet.of(3, 2), i.next());
822 assertEquals(ImmutableSet.of(3, 2, 1), i.next());
823 assertFalse(i.hasNext());
824 try {
825 i.next();
826 fail();
827 } catch (NoSuchElementException expected) {
828 }
829 }
830
831 @GwtIncompatible("too slow for GWT")
832 public void testPowerSetIteration_iteratorTester() {
833 ImmutableSet<Integer> elements = ImmutableSet.of(1, 2);
834
835 Set<Set<Integer>> expected = newLinkedHashSet();
836 expected.add(ImmutableSet.<Integer>of());
837 expected.add(ImmutableSet.of(1));
838 expected.add(ImmutableSet.of(2));
839 expected.add(ImmutableSet.of(1, 2));
840
841 final Set<Set<Integer>> powerSet = powerSet(elements);
842 new IteratorTester<Set<Integer>>(6, UNMODIFIABLE, expected, KNOWN_ORDER) {
843 @Override protected Iterator<Set<Integer>> newTargetIterator() {
844 return powerSet.iterator();
845 }
846 }.test();
847 }
848
849 public void testPowerSetIteration_iteratorTester_fast() {
850 ImmutableSet<Integer> elements = ImmutableSet.of(1, 2);
851
852 Set<Set<Integer>> expected = newLinkedHashSet();
853 expected.add(ImmutableSet.<Integer>of());
854 expected.add(ImmutableSet.of(1));
855 expected.add(ImmutableSet.of(2));
856 expected.add(ImmutableSet.of(1, 2));
857
858 final Set<Set<Integer>> powerSet = powerSet(elements);
859 new IteratorTester<Set<Integer>>(4, UNMODIFIABLE, expected, KNOWN_ORDER) {
860 @Override protected Iterator<Set<Integer>> newTargetIterator() {
861 return powerSet.iterator();
862 }
863 }.test();
864 }
865
866 public void testPowerSetSize() {
867 assertPowerSetSize(1);
868 assertPowerSetSize(2, 'a');
869 assertPowerSetSize(4, 'a', 'b');
870 assertPowerSetSize(8, 'a', 'b', 'c');
871 assertPowerSetSize(16, 'a', 'b', 'd', 'e');
872 assertPowerSetSize(1 << 30,
873 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
874 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '1', '2',
875 '3', '4');
876 }
877
878 public void testPowerSetCreationErrors() {
879 try {
880 powerSet(newHashSet('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
881 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
882 'y', 'z', '1', '2', '3', '4', '5'));
883 fail();
884 } catch (IllegalArgumentException expected) {
885 }
886
887 try {
888 powerSet(singleton(null));
889 fail();
890 } catch (NullPointerException expected) {
891 }
892 }
893
894 public void testPowerSetEqualsAndHashCode_verifyAgainstHashSet() {
895 ImmutableList<Integer> allElements = ImmutableList.of(4233352, 3284593,
896 3794208, 3849533, 4013967, 2902658, 1886275, 2131109, 985872, 1843868);
897 for (int i = 0; i < allElements.size(); i++) {
898 Set<Integer> elements = newHashSet(allElements.subList(0, i));
899 Set<Set<Integer>> powerSet1 = powerSet(elements);
900 Set<Set<Integer>> powerSet2 = powerSet(elements);
901 new EqualsTester()
902 .addEqualityGroup(powerSet1, powerSet2, toHashSets(powerSet1))
903 .addEqualityGroup(ImmutableSet.of())
904 .addEqualityGroup(ImmutableSet.of(9999999))
905 .addEqualityGroup("notASet")
906 .testEquals();
907 assertEquals(toHashSets(powerSet1).hashCode(), powerSet1.hashCode());
908 }
909 }
910
911
912
913
914
915 public void testPowerSetHashCode_inputHashCodeTimesTooFarValueIsZero() {
916 Set<Object> sumToEighthMaxIntElements =
917 newHashSet(objectWithHashCode(1 << 29), objectWithHashCode(0));
918 assertPowerSetHashCode(1 << 30, sumToEighthMaxIntElements);
919
920 Set<Object> sumToQuarterMaxIntElements =
921 newHashSet(objectWithHashCode(1 << 30), objectWithHashCode(0));
922 assertPowerSetHashCode(1 << 31, sumToQuarterMaxIntElements);
923 }
924
925 public void testPowerSetShowOff() {
926 Set<Object> zero = ImmutableSet.of();
927 Set<Set<Object>> one = powerSet(zero);
928 Set<Set<Set<Object>>> two = powerSet(one);
929 Set<Set<Set<Set<Object>>>> four = powerSet(two);
930 Set<Set<Set<Set<Set<Object>>>>> sixteen = powerSet(four);
931 Set<Set<Set<Set<Set<Set<Object>>>>>> sixtyFiveThousandish =
932 powerSet(sixteen);
933 assertEquals(1 << 16, sixtyFiveThousandish.size());
934
935 assertTrue(powerSet(makeSetOfZeroToTwentyNine())
936 .contains(makeSetOfZeroToTwentyNine()));
937 assertFalse(powerSet(makeSetOfZeroToTwentyNine())
938 .contains(ImmutableSet.of(30)));
939 }
940
941 private static Set<Integer> makeSetOfZeroToTwentyNine() {
942
943 Set<Integer> zeroToTwentyNine = newHashSet();
944 for (int i = 0; i < 30; i++) {
945 zeroToTwentyNine.add(i);
946 }
947 return zeroToTwentyNine;
948 }
949
950 private static <E> Set<Set<E>> toHashSets(Set<Set<E>> powerSet) {
951 Set<Set<E>> result = newHashSet();
952 for (Set<E> subset : powerSet) {
953 result.add(new HashSet<E>(subset));
954 }
955 return result;
956 }
957
958 private static Object objectWithHashCode(final int hashCode) {
959 return new Object() {
960 @Override public int hashCode() {
961 return hashCode;
962 }
963 };
964 }
965
966 private static void assertPowerSetHashCode(int expected, Set<?> elements) {
967 assertEquals(expected, powerSet(elements).hashCode());
968 }
969
970 private static void assertPowerSetSize(int i, Object... elements) {
971 assertEquals(i, powerSet(newHashSet(elements)).size());
972 }
973
974 private static void checkHashCode(Set<?> set) {
975 assertEquals(Sets.newHashSet(set).hashCode(), set.hashCode());
976 }
977
978 private static <E> Set<E> set(E... elements) {
979 return ImmutableSet.copyOf(elements);
980 }
981
982 private static <E> List<E> list(E... elements) {
983 return ImmutableList.copyOf(elements);
984 }
985
986
987
988
989
990
991
992 private static <E> void verifyLinkedHashSetContents(
993 LinkedHashSet<E> set, Collection<E> contents) {
994 assertEquals("LinkedHashSet should have preserved order for iteration",
995 new ArrayList<E>(set), new ArrayList<E>(contents));
996 verifySetContents(set, contents);
997 }
998
999
1000
1001
1002
1003
1004
1005 private static <E> void verifySortedSetContents(
1006 SortedSet<E> set, Iterable<E> iterable,
1007 @Nullable Comparator<E> comparator) {
1008 assertSame(comparator, set.comparator());
1009 verifySetContents(set, iterable);
1010 }
1011
1012
1013
1014
1015
1016 private static <E> void verifySetContents(Set<E> set, Iterable<E> contents) {
1017 Set<E> expected = null;
1018 if (contents instanceof Set) {
1019 expected = (Set<E>) contents;
1020 } else {
1021 expected = new HashSet<E>();
1022 for (E element : contents) {
1023 expected.add(element);
1024 }
1025 }
1026 assertEquals(expected, set);
1027 }
1028
1029
1030
1031
1032 static class Base implements Comparable<Base>, Serializable {
1033 private final String s;
1034
1035 public Base(String s) {
1036 this.s = s;
1037 }
1038
1039 @Override public int hashCode() {
1040 return s.hashCode();
1041 }
1042
1043 @Override public boolean equals(Object other) {
1044 if (other == null) {
1045 return false;
1046 } else if (other instanceof Base) {
1047 return s.equals(((Base) other).s);
1048 } else {
1049 return false;
1050 }
1051 }
1052
1053 @Override
1054 public int compareTo(Base o) {
1055 return s.compareTo(o.s);
1056 }
1057
1058 private static final long serialVersionUID = 0;
1059 }
1060
1061
1062
1063
1064 static class Derived extends Base {
1065 public Derived(String s) {
1066 super(s);
1067 }
1068
1069 private static final long serialVersionUID = 0;
1070 }
1071
1072 @GwtIncompatible("NavigableSet")
1073 public void testUnmodifiableNavigableSet() {
1074 TreeSet<Integer> mod = Sets.newTreeSet();
1075 mod.add(1);
1076 mod.add(2);
1077 mod.add(3);
1078
1079 NavigableSet<Integer> unmod = unmodifiableNavigableSet(mod);
1080
1081
1082 mod.add(4);
1083 assertTrue(unmod.contains(4));
1084 assertTrue(unmod.descendingSet().contains(4));
1085
1086 ensureNotDirectlyModifiable(unmod);
1087 ensureNotDirectlyModifiable(unmod.descendingSet());
1088 ensureNotDirectlyModifiable(unmod.headSet(2));
1089 ensureNotDirectlyModifiable(unmod.headSet(2, true));
1090 ensureNotDirectlyModifiable(unmod.tailSet(2));
1091 ensureNotDirectlyModifiable(unmod.tailSet(2, true));
1092 ensureNotDirectlyModifiable(unmod.subSet(1, 3));
1093 ensureNotDirectlyModifiable(unmod.subSet(1, true, 3, true));
1094
1095
1096 NavigableSet<Integer> reverse = unmod.descendingSet();
1097 try {
1098 reverse.add(4);
1099 fail("UnsupportedOperationException expected");
1100 } catch (UnsupportedOperationException expected) {
1101 }
1102 try {
1103 reverse.addAll(Collections.singleton(4));
1104 fail("UnsupportedOperationException expected");
1105 } catch (UnsupportedOperationException expected) {
1106 }
1107 try {
1108 reverse.remove(4);
1109 fail("UnsupportedOperationException expected");
1110 } catch (UnsupportedOperationException expected) {
1111 }
1112 }
1113
1114 void ensureNotDirectlyModifiable(SortedSet<Integer> unmod) {
1115 try {
1116 unmod.add(4);
1117 fail("UnsupportedOperationException expected");
1118 } catch (UnsupportedOperationException expected) {
1119 }
1120 try {
1121 unmod.remove(4);
1122 fail("UnsupportedOperationException expected");
1123 } catch (UnsupportedOperationException expected) {
1124 }
1125 try {
1126 unmod.addAll(Collections.singleton(4));
1127 fail("UnsupportedOperationException expected");
1128 } catch (UnsupportedOperationException expected) {
1129 }
1130 try {
1131 Iterator<Integer> iterator = unmod.iterator();
1132 iterator.next();
1133 iterator.remove();
1134 fail("UnsupportedOperationException expected");
1135 } catch (UnsupportedOperationException expected) {
1136 }
1137 }
1138
1139 @GwtIncompatible("NavigableSet")
1140 void ensureNotDirectlyModifiable(NavigableSet<Integer> unmod) {
1141 try {
1142 unmod.add(4);
1143 fail("UnsupportedOperationException expected");
1144 } catch (UnsupportedOperationException expected) {
1145 }
1146 try {
1147 unmod.remove(4);
1148 fail("UnsupportedOperationException expected");
1149 } catch (UnsupportedOperationException expected) {
1150 }
1151 try {
1152 unmod.addAll(Collections.singleton(4));
1153 fail("UnsupportedOperationException expected");
1154 } catch (UnsupportedOperationException expected) {
1155 }
1156 try {
1157 unmod.pollFirst();
1158 fail("UnsupportedOperationException expected");
1159 } catch (UnsupportedOperationException expected) {
1160 }
1161 try {
1162 unmod.pollLast();
1163 fail("UnsupportedOperationException expected");
1164 } catch (UnsupportedOperationException expected) {
1165 }
1166 try {
1167 Iterator<Integer> iterator = unmod.iterator();
1168 iterator.next();
1169 iterator.remove();
1170 fail("UnsupportedOperationException expected");
1171 } catch (UnsupportedOperationException expected) {
1172 }
1173 try {
1174 Iterator<Integer> iterator = unmod.descendingIterator();
1175 iterator.next();
1176 iterator.remove();
1177 fail("UnsupportedOperationException expected");
1178 } catch (UnsupportedOperationException expected) {
1179 }
1180 }
1181 }