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.testing.IteratorFeature.UNMODIFIABLE;
25 import static com.google.common.truth.Truth.assertThat;
26 import static java.util.Collections.emptySet;
27 import static java.util.Collections.singleton;
28
29 import com.google.common.annotations.GwtCompatible;
30 import com.google.common.collect.testing.IteratorTester;
31 import com.google.common.collect.testing.MinimalIterable;
32 import com.google.common.testing.EqualsTester;
33
34 import junit.framework.TestCase;
35
36 import java.io.Serializable;
37 import java.util.ArrayList;
38 import java.util.Arrays;
39 import java.util.Collection;
40 import java.util.Collections;
41 import java.util.Comparator;
42 import java.util.EnumSet;
43 import java.util.HashMap;
44 import java.util.HashSet;
45 import java.util.Iterator;
46 import java.util.LinkedHashMap;
47 import java.util.LinkedHashSet;
48 import java.util.List;
49 import java.util.Map;
50 import java.util.NoSuchElementException;
51 import java.util.Set;
52 import java.util.SortedSet;
53 import java.util.TreeSet;
54
55 import javax.annotation.Nullable;
56
57
58
59
60
61
62
63 @GwtCompatible(emulated = true)
64 public class SetsTest extends TestCase {
65
66 private static final IteratorTester.KnownOrder KNOWN_ORDER =
67 IteratorTester.KnownOrder.KNOWN_ORDER;
68
69 private static final Collection<Integer> EMPTY_COLLECTION
70 = Arrays.<Integer>asList();
71
72 private static final Collection<Integer> SOME_COLLECTION
73 = Arrays.asList(0, 1, 1);
74
75 private static final Iterable<Integer> SOME_ITERABLE
76 = new Iterable<Integer>() {
77 @Override
78 public Iterator<Integer> iterator() {
79 return SOME_COLLECTION.iterator();
80 }
81 };
82
83 private static final List<Integer> LONGER_LIST
84 = Arrays.asList(8, 6, 7, 5, 3, 0, 9);
85
86 private static final Comparator<Integer> SOME_COMPARATOR
87 = Collections.reverseOrder();
88
89 private enum SomeEnum { A, B, C, D }
90
91 public void testImmutableEnumSet() {
92 Set<SomeEnum> units = Sets.immutableEnumSet(SomeEnum.D, SomeEnum.B);
93
94 assertThat(units).has().exactly(SomeEnum.B, SomeEnum.D).inOrder();
95 try {
96 units.remove(SomeEnum.B);
97 fail("ImmutableEnumSet should throw an exception on remove()");
98 } catch (UnsupportedOperationException expected) {}
99 try {
100 units.add(SomeEnum.C);
101 fail("ImmutableEnumSet should throw an exception on add()");
102 } catch (UnsupportedOperationException expected) {}
103 }
104
105 public void testImmutableEnumSet_fromIterable() {
106 ImmutableSet<SomeEnum> none
107 = Sets.immutableEnumSet(MinimalIterable.<SomeEnum>of());
108 assertThat(none).isEmpty();
109
110 ImmutableSet<SomeEnum> one
111 = Sets.immutableEnumSet(MinimalIterable.of(SomeEnum.B));
112 assertThat(one).has().item(SomeEnum.B);
113
114 ImmutableSet<SomeEnum> two
115 = Sets.immutableEnumSet(MinimalIterable.of(SomeEnum.D, SomeEnum.B));
116 assertThat(two).has().exactly(SomeEnum.B, SomeEnum.D).inOrder();
117 }
118
119 private static byte[] prepended(byte b, byte[] array) {
120 byte[] out = new byte[array.length + 1];
121 out[0] = b;
122 System.arraycopy(array, 0, out, 1, array.length);
123 return out;
124 }
125
126 public void testNewEnumSet_empty() {
127 EnumSet<SomeEnum> copy =
128 newEnumSet(Collections.<SomeEnum>emptySet(), SomeEnum.class);
129 assertEquals(EnumSet.noneOf(SomeEnum.class), copy);
130 }
131
132 public void testNewEnumSet_enumSet() {
133 EnumSet<SomeEnum> set = EnumSet.of(SomeEnum.A, SomeEnum.D);
134 assertEquals(set, newEnumSet(set, SomeEnum.class));
135 }
136
137 public void testNewEnumSet_collection() {
138 Set<SomeEnum> set = ImmutableSet.of(SomeEnum.B, SomeEnum.C);
139 assertEquals(set, newEnumSet(set, SomeEnum.class));
140 }
141
142 public void testNewEnumSet_iterable() {
143 Set<SomeEnum> set = ImmutableSet.of(SomeEnum.A, SomeEnum.B, SomeEnum.C);
144 assertEquals(set, newEnumSet(unmodifiableIterable(set), SomeEnum.class));
145 }
146
147 public void testNewHashSetEmpty() {
148 HashSet<Integer> set = Sets.newHashSet();
149 verifySetContents(set, EMPTY_COLLECTION);
150 }
151
152 public void testNewHashSetVarArgs() {
153 HashSet<Integer> set = Sets.newHashSet(0, 1, 1);
154 verifySetContents(set, Arrays.asList(0, 1));
155 }
156
157 public void testNewHashSetFromCollection() {
158 HashSet<Integer> set = Sets.newHashSet(SOME_COLLECTION);
159 verifySetContents(set, SOME_COLLECTION);
160 }
161
162 public void testNewHashSetFromIterable() {
163 HashSet<Integer> set = Sets.newHashSet(SOME_ITERABLE);
164 verifySetContents(set, SOME_ITERABLE);
165 }
166
167 public void testNewHashSetWithExpectedSizeSmall() {
168 HashSet<Integer> set = Sets.newHashSetWithExpectedSize(0);
169 verifySetContents(set, EMPTY_COLLECTION);
170 }
171
172 public void testNewHashSetWithExpectedSizeLarge() {
173 HashSet<Integer> set = Sets.newHashSetWithExpectedSize(1000);
174 verifySetContents(set, EMPTY_COLLECTION);
175 }
176
177 public void testNewHashSetFromIterator() {
178 HashSet<Integer> set = Sets.newHashSet(SOME_COLLECTION.iterator());
179 verifySetContents(set, SOME_COLLECTION);
180 }
181
182 public void testNewConcurrentHashSetEmpty() {
183 Set<Integer> set = Sets.newConcurrentHashSet();
184 verifySetContents(set, EMPTY_COLLECTION);
185 }
186
187 public void testNewConcurrentHashSetFromCollection() {
188 Set<Integer> set = Sets.newConcurrentHashSet(SOME_COLLECTION);
189 verifySetContents(set, SOME_COLLECTION);
190 }
191
192 public void testNewLinkedHashSetEmpty() {
193 LinkedHashSet<Integer> set = Sets.newLinkedHashSet();
194 verifyLinkedHashSetContents(set, EMPTY_COLLECTION);
195 }
196
197 public void testNewLinkedHashSetFromCollection() {
198 LinkedHashSet<Integer> set = Sets.newLinkedHashSet(LONGER_LIST);
199 verifyLinkedHashSetContents(set, LONGER_LIST);
200 }
201
202 public void testNewLinkedHashSetFromIterable() {
203 LinkedHashSet<Integer> set = Sets.newLinkedHashSet(new Iterable<Integer>()
204 {
205 @Override
206 public Iterator<Integer> iterator() {
207 return LONGER_LIST.iterator();
208 }
209 });
210 verifyLinkedHashSetContents(set, LONGER_LIST);
211 }
212
213 public void testNewLinkedHashSetWithExpectedSizeSmall() {
214 LinkedHashSet<Integer> set = Sets.newLinkedHashSetWithExpectedSize(0);
215 verifySetContents(set, EMPTY_COLLECTION);
216 }
217
218 public void testNewLinkedHashSetWithExpectedSizeLarge() {
219 LinkedHashSet<Integer> set = Sets.newLinkedHashSetWithExpectedSize(1000);
220 verifySetContents(set, EMPTY_COLLECTION);
221 }
222
223 public void testNewTreeSetEmpty() {
224 TreeSet<Integer> set = Sets.newTreeSet();
225 verifySortedSetContents(set, EMPTY_COLLECTION, null);
226 }
227
228 public void testNewTreeSetEmptyDerived() {
229 TreeSet<Derived> set = Sets.newTreeSet();
230 assertTrue(set.isEmpty());
231 set.add(new Derived("foo"));
232 set.add(new Derived("bar"));
233 assertThat(set).has().exactly(new Derived("bar"), new Derived("foo")).inOrder();
234 }
235
236 public void testNewTreeSetEmptyNonGeneric() {
237 TreeSet<LegacyComparable> set = Sets.newTreeSet();
238 assertTrue(set.isEmpty());
239 set.add(new LegacyComparable("foo"));
240 set.add(new LegacyComparable("bar"));
241 assertThat(set).has()
242 .exactly(new LegacyComparable("bar"), new LegacyComparable("foo")).inOrder();
243 }
244
245 public void testNewTreeSetFromCollection() {
246 TreeSet<Integer> set = Sets.newTreeSet(SOME_COLLECTION);
247 verifySortedSetContents(set, SOME_COLLECTION, null);
248 }
249
250 public void testNewTreeSetFromIterable() {
251 TreeSet<Integer> set = Sets.newTreeSet(SOME_ITERABLE);
252 verifySortedSetContents(set, SOME_ITERABLE, null);
253 }
254
255 public void testNewTreeSetFromIterableDerived() {
256 Iterable<Derived> iterable =
257 Arrays.asList(new Derived("foo"), new Derived("bar"));
258 TreeSet<Derived> set = Sets.newTreeSet(iterable);
259 assertThat(set).has().exactly(
260 new Derived("bar"), new Derived("foo")).inOrder();
261 }
262
263 public void testNewTreeSetFromIterableNonGeneric() {
264 Iterable<LegacyComparable> iterable =
265 Arrays.asList(new LegacyComparable("foo"), new LegacyComparable("bar"));
266 TreeSet<LegacyComparable> set = Sets.newTreeSet(iterable);
267 assertThat(set).has().exactly(
268 new LegacyComparable("bar"), new LegacyComparable("foo")).inOrder();
269 }
270
271 public void testNewTreeSetEmptyWithComparator() {
272 TreeSet<Integer> set = Sets.newTreeSet(SOME_COMPARATOR);
273 verifySortedSetContents(set, EMPTY_COLLECTION, SOME_COMPARATOR);
274 }
275
276 public void testNewIdentityHashSet() {
277 Set<Integer> set = Sets.newIdentityHashSet();
278 Integer value1 = new Integer(12357);
279 Integer value2 = new Integer(12357);
280 assertTrue(set.add(value1));
281 assertFalse(set.contains(value2));
282 assertTrue(set.contains(value1));
283 assertTrue(set.add(value2));
284 assertEquals(2, set.size());
285 }
286
287 public void testComplementOfEnumSet() {
288 Set<SomeEnum> units = EnumSet.of(SomeEnum.B, SomeEnum.D);
289 EnumSet<SomeEnum> otherUnits = Sets.complementOf(units);
290 verifySetContents(otherUnits, EnumSet.of(SomeEnum.A, SomeEnum.C));
291 }
292
293 public void testComplementOfEnumSetWithType() {
294 Set<SomeEnum> units = EnumSet.of(SomeEnum.B, SomeEnum.D);
295 EnumSet<SomeEnum> otherUnits = Sets.complementOf(units, SomeEnum.class);
296 verifySetContents(otherUnits, EnumSet.of(SomeEnum.A, SomeEnum.C));
297 }
298
299 public void testComplementOfRegularSet() {
300 Set<SomeEnum> units = Sets.newHashSet(SomeEnum.B, SomeEnum.D);
301 EnumSet<SomeEnum> otherUnits = Sets.complementOf(units);
302 verifySetContents(otherUnits, EnumSet.of(SomeEnum.A, SomeEnum.C));
303 }
304
305 public void testComplementOfRegularSetWithType() {
306 Set<SomeEnum> units = Sets.newHashSet(SomeEnum.B, SomeEnum.D);
307 EnumSet<SomeEnum> otherUnits = Sets.complementOf(units, SomeEnum.class);
308 verifySetContents(otherUnits, EnumSet.of(SomeEnum.A, SomeEnum.C));
309 }
310
311 public void testComplementOfEmptySet() {
312 Set<SomeEnum> noUnits = Collections.emptySet();
313 EnumSet<SomeEnum> allUnits = Sets.complementOf(noUnits, SomeEnum.class);
314 verifySetContents(EnumSet.allOf(SomeEnum.class), allUnits);
315 }
316
317 public void testComplementOfFullSet() {
318 Set<SomeEnum> allUnits = Sets.newHashSet(SomeEnum.values());
319 EnumSet<SomeEnum> noUnits = Sets.complementOf(allUnits, SomeEnum.class);
320 verifySetContents(noUnits, EnumSet.noneOf(SomeEnum.class));
321 }
322
323 public void testComplementOfEmptyEnumSetWithoutType() {
324 Set<SomeEnum> noUnits = EnumSet.noneOf(SomeEnum.class);
325 EnumSet<SomeEnum> allUnits = Sets.complementOf(noUnits);
326 verifySetContents(allUnits, EnumSet.allOf(SomeEnum.class));
327 }
328
329 public void testComplementOfEmptySetWithoutTypeDoesntWork() {
330 Set<SomeEnum> set = Collections.emptySet();
331 try {
332 Sets.complementOf(set);
333 fail();
334 } catch (IllegalArgumentException expected) {}
335 }
336
337 public void testNewSetFromMap() {
338 Set<Integer> set = Sets.newSetFromMap(new HashMap<Integer, Boolean>());
339 set.addAll(SOME_COLLECTION);
340 verifySetContents(set, SOME_COLLECTION);
341 }
342
343 public void testNewSetFromMapIllegal() {
344 Map<Integer, Boolean> map = new LinkedHashMap<Integer, Boolean>();
345 map.put(2, true);
346 try {
347 Sets.newSetFromMap(map);
348 fail();
349 } catch (IllegalArgumentException expected) {}
350 }
351
352
353
354
355
356
357
358 @SuppressWarnings("unchecked")
359 public void testCartesianProduct_zeroary() {
360 assertThat(Sets.cartesianProduct()).has().exactly(list());
361 }
362
363
364
365
366
367 @SuppressWarnings("unchecked")
368 public void testCartesianProduct_unary() {
369 assertThat(Sets.cartesianProduct(set(1, 2))).has().exactly(list(1), list(2));
370 }
371
372 @SuppressWarnings("unchecked")
373 public void testCartesianProduct_binary0x0() {
374 Set<Integer> mt = emptySet();
375 assertEmpty(Sets.cartesianProduct(mt, mt));
376 }
377
378 @SuppressWarnings("unchecked")
379 public void testCartesianProduct_binary0x1() {
380 Set<Integer> mt = emptySet();
381 assertEmpty(Sets.cartesianProduct(mt, set(1)));
382 }
383
384 @SuppressWarnings("unchecked")
385 public void testCartesianProduct_binary1x0() {
386 Set<Integer> mt = emptySet();
387 assertEmpty(Sets.cartesianProduct(set(1), mt));
388 }
389
390 private static void assertEmpty(Set<? extends List<?>> set) {
391 assertTrue(set.isEmpty());
392 assertEquals(0, set.size());
393 assertFalse(set.iterator().hasNext());
394 }
395
396 @SuppressWarnings("unchecked")
397 public void testCartesianProduct_binary1x1() {
398 assertThat(Sets.cartesianProduct(set(1), set(2))).has().item(list(1, 2));
399 }
400
401 @SuppressWarnings("unchecked")
402 public void testCartesianProduct_binary1x2() {
403 assertThat(Sets.cartesianProduct(set(1), set(2, 3)))
404 .has().exactly(list(1, 2), list(1, 3)).inOrder();
405 }
406
407 @SuppressWarnings("unchecked")
408 public void testCartesianProduct_binary2x2() {
409 assertThat(Sets.cartesianProduct(set(1, 2), set(3, 4)))
410 .has().exactly(list(1, 3), list(1, 4), list(2, 3), list(2, 4)).inOrder();
411 }
412
413 @SuppressWarnings("unchecked")
414 public void testCartesianProduct_2x2x2() {
415 assertThat(Sets.cartesianProduct(set(0, 1), set(0, 1), set(0, 1))).has().exactly(
416 list(0, 0, 0), list(0, 0, 1), list(0, 1, 0), list(0, 1, 1),
417 list(1, 0, 0), list(1, 0, 1), list(1, 1, 0), list(1, 1, 1)).inOrder();
418 }
419
420 @SuppressWarnings("unchecked")
421 public void testCartesianProduct_contains() {
422 Set<List<Integer>> actual = Sets.cartesianProduct(set(1, 2), set(3, 4));
423 assertTrue(actual.contains(list(1, 3)));
424 assertTrue(actual.contains(list(1, 4)));
425 assertTrue(actual.contains(list(2, 3)));
426 assertTrue(actual.contains(list(2, 4)));
427 assertFalse(actual.contains(list(3, 1)));
428 }
429
430 @SuppressWarnings("unchecked")
431 public void testCartesianProduct_unrelatedTypes() {
432 Set<Integer> x = set(1, 2);
433 Set<String> y = set("3", "4");
434
435 List<Object> exp1 = list((Object) 1, "3");
436 List<Object> exp2 = list((Object) 1, "4");
437 List<Object> exp3 = list((Object) 2, "3");
438 List<Object> exp4 = list((Object) 2, "4");
439
440 assertThat(Sets.<Object>cartesianProduct(x, y))
441 .has().exactly(exp1, exp2, exp3, exp4).inOrder();
442 }
443
444 @SuppressWarnings("unchecked")
445 public void testCartesianProductTooBig() {
446 Set<Integer> set = ContiguousSet.create(Range.closed(0, 10000), DiscreteDomain.integers());
447 try {
448 Sets.cartesianProduct(set, set, set, set, set);
449 fail("Expected IAE");
450 } catch (IllegalArgumentException expected) {}
451 }
452
453 @SuppressWarnings("unchecked")
454 public void testCartesianProduct_hashCode() {
455
456
457 Set<List<Integer>> degenerate = Sets.cartesianProduct();
458 checkHashCode(degenerate);
459
460 checkHashCode(Sets.cartesianProduct(set(1, 2)));
461
462 int num = Integer.MAX_VALUE / 3 * 2;
463 checkHashCode(Sets.cartesianProduct(set(1, 2, num)));
464
465 Set<Integer> mt = emptySet();
466 checkHashCode(Sets.cartesianProduct(mt, mt));
467 checkHashCode(Sets.cartesianProduct(mt, set(num)));
468 checkHashCode(Sets.cartesianProduct(set(num), mt));
469 checkHashCode(Sets.cartesianProduct(set(num), set(1)));
470 checkHashCode(Sets.cartesianProduct(set(1), set(2, num)));
471 checkHashCode(Sets.cartesianProduct(set(1, num), set(2, num - 1)));
472 checkHashCode(Sets.cartesianProduct(
473 set(1, num), set(2, num - 1), set(3, num + 1)));
474
475
476 checkHashCode(Sets.cartesianProduct(
477 set(1, num, num + 1), set(2), set(3, num + 2), set(4, 5, 6, 7, 8)));
478 }
479
480 public void testPowerSetEmpty() {
481 ImmutableSet<Integer> elements = ImmutableSet.of();
482 Set<Set<Integer>> powerSet = powerSet(elements);
483 assertEquals(1, powerSet.size());
484 assertEquals(ImmutableSet.of(ImmutableSet.of()), powerSet);
485 assertEquals(0, powerSet.hashCode());
486 }
487
488 public void testPowerSetContents() {
489 ImmutableSet<Integer> elements = ImmutableSet.of(1, 2, 3);
490 Set<Set<Integer>> powerSet = powerSet(elements);
491 assertEquals(8, powerSet.size());
492 assertEquals(4 * 1 + 4 * 2 + 4 * 3, powerSet.hashCode());
493
494 Set<Set<Integer>> expected = newHashSet();
495 expected.add(ImmutableSet.<Integer>of());
496 expected.add(ImmutableSet.of(1));
497 expected.add(ImmutableSet.of(2));
498 expected.add(ImmutableSet.of(3));
499 expected.add(ImmutableSet.of(1, 2));
500 expected.add(ImmutableSet.of(1, 3));
501 expected.add(ImmutableSet.of(2, 3));
502 expected.add(ImmutableSet.of(1, 2, 3));
503
504 Set<Set<Integer>> almostPowerSet = newHashSet(expected);
505 almostPowerSet.remove(ImmutableSet.of(1, 2, 3));
506 almostPowerSet.add(ImmutableSet.of(1, 2, 4));
507
508 new EqualsTester()
509 .addEqualityGroup(expected, powerSet)
510 .addEqualityGroup(ImmutableSet.of(1, 2, 3))
511 .addEqualityGroup(almostPowerSet)
512 .testEquals();
513
514 for (Set<Integer> subset : expected) {
515 assertTrue(powerSet.contains(subset));
516 }
517 assertFalse(powerSet.contains(ImmutableSet.of(1, 2, 4)));
518 assertFalse(powerSet.contains(singleton(null)));
519 assertFalse(powerSet.contains(null));
520 assertFalse(powerSet.contains("notASet"));
521 }
522
523 public void testPowerSetIteration_manual() {
524 ImmutableSet<Integer> elements = ImmutableSet.of(1, 2, 3);
525 Set<Set<Integer>> powerSet = powerSet(elements);
526
527 Iterator<Set<Integer>> i = powerSet.iterator();
528 assertEquals(ImmutableSet.of(), i.next());
529 assertEquals(ImmutableSet.of(1), i.next());
530 assertEquals(ImmutableSet.of(2), i.next());
531 assertEquals(ImmutableSet.of(2, 1), i.next());
532 assertEquals(ImmutableSet.of(3), i.next());
533 assertEquals(ImmutableSet.of(3, 1), i.next());
534 assertEquals(ImmutableSet.of(3, 2), i.next());
535 assertEquals(ImmutableSet.of(3, 2, 1), i.next());
536 assertFalse(i.hasNext());
537 try {
538 i.next();
539 fail();
540 } catch (NoSuchElementException expected) {
541 }
542 }
543
544 public void testPowerSetIteration_iteratorTester_fast() {
545 ImmutableSet<Integer> elements = ImmutableSet.of(1, 2);
546
547 Set<Set<Integer>> expected = newLinkedHashSet();
548 expected.add(ImmutableSet.<Integer>of());
549 expected.add(ImmutableSet.of(1));
550 expected.add(ImmutableSet.of(2));
551 expected.add(ImmutableSet.of(1, 2));
552
553 final Set<Set<Integer>> powerSet = powerSet(elements);
554 new IteratorTester<Set<Integer>>(4, UNMODIFIABLE, expected, KNOWN_ORDER) {
555 @Override protected Iterator<Set<Integer>> newTargetIterator() {
556 return powerSet.iterator();
557 }
558 }.test();
559 }
560
561 public void testPowerSetSize() {
562 assertPowerSetSize(1);
563 assertPowerSetSize(2, 'a');
564 assertPowerSetSize(4, 'a', 'b');
565 assertPowerSetSize(8, 'a', 'b', 'c');
566 assertPowerSetSize(16, 'a', 'b', 'd', 'e');
567 assertPowerSetSize(1 << 30,
568 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
569 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '1', '2',
570 '3', '4');
571 }
572
573 public void testPowerSetCreationErrors() {
574 try {
575 powerSet(newHashSet('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
576 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
577 'y', 'z', '1', '2', '3', '4', '5'));
578 fail();
579 } catch (IllegalArgumentException expected) {
580 }
581
582 try {
583 powerSet(singleton(null));
584 fail();
585 } catch (NullPointerException expected) {
586 }
587 }
588
589 public void testPowerSetEqualsAndHashCode_verifyAgainstHashSet() {
590 ImmutableList<Integer> allElements = ImmutableList.of(4233352, 3284593,
591 3794208, 3849533, 4013967, 2902658, 1886275, 2131109, 985872, 1843868);
592 for (int i = 0; i < allElements.size(); i++) {
593 Set<Integer> elements = newHashSet(allElements.subList(0, i));
594 Set<Set<Integer>> powerSet1 = powerSet(elements);
595 Set<Set<Integer>> powerSet2 = powerSet(elements);
596 new EqualsTester()
597 .addEqualityGroup(powerSet1, powerSet2, toHashSets(powerSet1))
598 .addEqualityGroup(ImmutableSet.of())
599 .addEqualityGroup(ImmutableSet.of(9999999))
600 .addEqualityGroup("notASet")
601 .testEquals();
602 assertEquals(toHashSets(powerSet1).hashCode(), powerSet1.hashCode());
603 }
604 }
605
606
607
608
609
610 public void testPowerSetHashCode_inputHashCodeTimesTooFarValueIsZero() {
611 Set<Object> sumToEighthMaxIntElements =
612 newHashSet(objectWithHashCode(1 << 29), objectWithHashCode(0));
613 assertPowerSetHashCode(1 << 30, sumToEighthMaxIntElements);
614
615 Set<Object> sumToQuarterMaxIntElements =
616 newHashSet(objectWithHashCode(1 << 30), objectWithHashCode(0));
617 assertPowerSetHashCode(1 << 31, sumToQuarterMaxIntElements);
618 }
619
620 public void testPowerSetShowOff() {
621 Set<Object> zero = ImmutableSet.of();
622 Set<Set<Object>> one = powerSet(zero);
623 Set<Set<Set<Object>>> two = powerSet(one);
624 Set<Set<Set<Set<Object>>>> four = powerSet(two);
625 Set<Set<Set<Set<Set<Object>>>>> sixteen = powerSet(four);
626 Set<Set<Set<Set<Set<Set<Object>>>>>> sixtyFiveThousandish =
627 powerSet(sixteen);
628 assertEquals(1 << 16, sixtyFiveThousandish.size());
629
630 assertTrue(powerSet(makeSetOfZeroToTwentyNine())
631 .contains(makeSetOfZeroToTwentyNine()));
632 assertFalse(powerSet(makeSetOfZeroToTwentyNine())
633 .contains(ImmutableSet.of(30)));
634 }
635
636 private static Set<Integer> makeSetOfZeroToTwentyNine() {
637
638 Set<Integer> zeroToTwentyNine = newHashSet();
639 for (int i = 0; i < 30; i++) {
640 zeroToTwentyNine.add(i);
641 }
642 return zeroToTwentyNine;
643 }
644
645 private static <E> Set<Set<E>> toHashSets(Set<Set<E>> powerSet) {
646 Set<Set<E>> result = newHashSet();
647 for (Set<E> subset : powerSet) {
648 result.add(new HashSet<E>(subset));
649 }
650 return result;
651 }
652
653 private static Object objectWithHashCode(final int hashCode) {
654 return new Object() {
655 @Override public int hashCode() {
656 return hashCode;
657 }
658 };
659 }
660
661 private static void assertPowerSetHashCode(int expected, Set<?> elements) {
662 assertEquals(expected, powerSet(elements).hashCode());
663 }
664
665 private static void assertPowerSetSize(int i, Object... elements) {
666 assertEquals(i, powerSet(newHashSet(elements)).size());
667 }
668
669 private static void checkHashCode(Set<?> set) {
670 assertEquals(Sets.newHashSet(set).hashCode(), set.hashCode());
671 }
672
673 private static <E> Set<E> set(E... elements) {
674 return ImmutableSet.copyOf(elements);
675 }
676
677 private static <E> List<E> list(E... elements) {
678 return ImmutableList.copyOf(elements);
679 }
680
681
682
683
684
685
686
687 private static <E> void verifyLinkedHashSetContents(
688 LinkedHashSet<E> set, Collection<E> contents) {
689 assertEquals("LinkedHashSet should have preserved order for iteration",
690 new ArrayList<E>(set), new ArrayList<E>(contents));
691 verifySetContents(set, contents);
692 }
693
694
695
696
697
698
699
700 private static <E> void verifySortedSetContents(
701 SortedSet<E> set, Iterable<E> iterable,
702 @Nullable Comparator<E> comparator) {
703 assertSame(comparator, set.comparator());
704 verifySetContents(set, iterable);
705 }
706
707
708
709
710
711 private static <E> void verifySetContents(Set<E> set, Iterable<E> contents) {
712 Set<E> expected = null;
713 if (contents instanceof Set) {
714 expected = (Set<E>) contents;
715 } else {
716 expected = new HashSet<E>();
717 for (E element : contents) {
718 expected.add(element);
719 }
720 }
721 assertEquals(expected, set);
722 }
723
724
725
726
727 static class Base implements Comparable<Base>, Serializable {
728 private final String s;
729
730 public Base(String s) {
731 this.s = s;
732 }
733
734 @Override public int hashCode() {
735 return s.hashCode();
736 }
737
738 @Override public boolean equals(Object other) {
739 if (other == null) {
740 return false;
741 } else if (other instanceof Base) {
742 return s.equals(((Base) other).s);
743 } else {
744 return false;
745 }
746 }
747
748 @Override
749 public int compareTo(Base o) {
750 return s.compareTo(o.s);
751 }
752
753 private static final long serialVersionUID = 0;
754 }
755
756
757
758
759 static class Derived extends Base {
760 public Derived(String s) {
761 super(s);
762 }
763
764 private static final long serialVersionUID = 0;
765 }
766
767 void ensureNotDirectlyModifiable(SortedSet<Integer> unmod) {
768 try {
769 unmod.add(4);
770 fail("UnsupportedOperationException expected");
771 } catch (UnsupportedOperationException expected) {
772 }
773 try {
774 unmod.remove(4);
775 fail("UnsupportedOperationException expected");
776 } catch (UnsupportedOperationException expected) {
777 }
778 try {
779 unmod.addAll(Collections.singleton(4));
780 fail("UnsupportedOperationException expected");
781 } catch (UnsupportedOperationException expected) {
782 }
783 try {
784 Iterator<Integer> iterator = unmod.iterator();
785 iterator.next();
786 iterator.remove();
787 fail("UnsupportedOperationException expected");
788 } catch (UnsupportedOperationException expected) {
789 }
790 }
791 }