1/*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect;
18
19import static com.google.common.collect.testing.IteratorFeature.UNMODIFIABLE;
20import static com.google.common.truth.Truth.assertThat;
21import static java.util.Arrays.asList;
22
23import com.google.common.annotations.GwtCompatible;
24import com.google.common.annotations.GwtIncompatible;
25import com.google.common.collect.testing.Helpers;
26import com.google.common.collect.testing.IteratorTester;
27import com.google.common.collect.testing.MinimalCollection;
28import com.google.common.collect.testing.MinimalIterable;
29
30import junit.framework.TestCase;
31
32import java.util.Collection;
33import java.util.Collections;
34import java.util.Iterator;
35import java.util.List;
36import java.util.Set;
37
38/**
39 * Base class for {@link ImmutableSet} and  {@link ImmutableSortedSet} tests.
40 *
41 * @author Kevin Bourrillion
42 * @author Jared Levy
43 */
44@GwtCompatible(emulated = true)
45public abstract class AbstractImmutableSetTest extends TestCase {
46
47  protected abstract Set<String> of();
48  protected abstract Set<String> of(String e);
49  protected abstract Set<String> of(String e1, String e2);
50  protected abstract Set<String> of(String e1, String e2, String e3);
51  protected abstract Set<String> of(String e1, String e2, String e3, String e4);
52  protected abstract Set<String> of(String e1, String e2, String e3, String e4,
53      String e5);
54  protected abstract Set<String> of(String e1, String e2, String e3, String e4,
55      String e5, String e6, String... rest);
56  protected abstract Set<String> copyOf(String[] elements);
57  protected abstract Set<String> copyOf(Collection<String> elements);
58  protected abstract Set<String> copyOf(Iterable<String> elements);
59  protected abstract Set<String> copyOf(Iterator<String> elements);
60
61  public void testCreation_noArgs() {
62    Set<String> set = of();
63    assertEquals(Collections.<String>emptySet(), set);
64    assertSame(of(), set);
65  }
66
67  public void testCreation_oneElement() {
68    Set<String> set = of("a");
69    assertEquals(Collections.singleton("a"), set);
70  }
71
72  public void testCreation_twoElements() {
73    Set<String> set = of("a", "b");
74    assertEquals(Sets.newHashSet("a", "b"), set);
75  }
76
77  public void testCreation_threeElements() {
78    Set<String> set = of("a", "b", "c");
79    assertEquals(Sets.newHashSet("a", "b", "c"), set);
80  }
81
82  public void testCreation_fourElements() {
83    Set<String> set = of("a", "b", "c", "d");
84    assertEquals(Sets.newHashSet("a", "b", "c", "d"), set);
85  }
86
87  public void testCreation_fiveElements() {
88    Set<String> set = of("a", "b", "c", "d", "e");
89    assertEquals(Sets.newHashSet("a", "b", "c", "d", "e"), set);
90  }
91
92  public void testCreation_sixElements() {
93    Set<String> set = of("a", "b", "c", "d", "e", "f");
94    assertEquals(Sets.newHashSet("a", "b", "c", "d", "e", "f"), set);
95  }
96
97  public void testCreation_sevenElements() {
98    Set<String> set = of("a", "b", "c", "d", "e", "f", "g");
99    assertEquals(Sets.newHashSet("a", "b", "c", "d", "e", "f", "g"), set);
100  }
101
102  public void testCreation_eightElements() {
103    Set<String> set = of("a", "b", "c", "d", "e", "f", "g", "h");
104    assertEquals(Sets.newHashSet("a", "b", "c", "d", "e", "f", "g", "h"), set);
105  }
106
107  public void testCopyOf_emptyArray() {
108    String[] array = new String[0];
109    Set<String> set = copyOf(array);
110    assertEquals(Collections.<String>emptySet(), set);
111    assertSame(of(), set);
112  }
113
114  public void testCopyOf_arrayOfOneElement() {
115    String[] array = new String[] { "a" };
116    Set<String> set = copyOf(array);
117    assertEquals(Collections.singleton("a"), set);
118  }
119
120  public void testCopyOf_nullArray() {
121    try {
122      copyOf((String[]) null);
123      fail();
124    } catch (NullPointerException expected) {
125    }
126  }
127
128  public void testCopyOf_arrayContainingOnlyNull() {
129    String[] array = new String[] { null };
130    try {
131      copyOf(array);
132      fail();
133    } catch (NullPointerException expected) {
134    }
135  }
136
137  public void testCopyOf_collection_empty() {
138    // "<String>" is required to work around a javac 1.5 bug.
139    Collection<String> c = MinimalCollection.<String>of();
140    Set<String> set = copyOf(c);
141    assertEquals(Collections.<String>emptySet(), set);
142    assertSame(of(), set);
143  }
144
145  public void testCopyOf_collection_oneElement() {
146    Collection<String> c = MinimalCollection.of("a");
147    Set<String> set = copyOf(c);
148    assertEquals(Collections.singleton("a"), set);
149  }
150
151  public void testCopyOf_collection_oneElementRepeated() {
152    Collection<String> c = MinimalCollection.of("a", "a", "a");
153    Set<String> set = copyOf(c);
154    assertEquals(Collections.singleton("a"), set);
155  }
156
157  public void testCopyOf_collection_general() {
158    Collection<String> c = MinimalCollection.of("a", "b", "a");
159    Set<String> set = copyOf(c);
160    assertEquals(2, set.size());
161    assertTrue(set.contains("a"));
162    assertTrue(set.contains("b"));
163  }
164
165  public void testCopyOf_collectionContainingNull() {
166    Collection<String> c = MinimalCollection.of("a", null, "b");
167    try {
168      copyOf(c);
169      fail();
170    } catch (NullPointerException expected) {
171    }
172  }
173
174  public void testCopyOf_iterator_empty() {
175    Iterator<String> iterator = Iterators.emptyIterator();
176    Set<String> set = copyOf(iterator);
177    assertEquals(Collections.<String>emptySet(), set);
178    assertSame(of(), set);
179  }
180
181  public void testCopyOf_iterator_oneElement() {
182    Iterator<String> iterator = Iterators.singletonIterator("a");
183    Set<String> set = copyOf(iterator);
184    assertEquals(Collections.singleton("a"), set);
185  }
186
187  public void testCopyOf_iterator_oneElementRepeated() {
188    Iterator<String> iterator = Iterators.forArray("a", "a", "a");
189    Set<String> set = copyOf(iterator);
190    assertEquals(Collections.singleton("a"), set);
191  }
192
193  public void testCopyOf_iterator_general() {
194    Iterator<String> iterator = Iterators.forArray("a", "b", "a");
195    Set<String> set = copyOf(iterator);
196    assertEquals(2, set.size());
197    assertTrue(set.contains("a"));
198    assertTrue(set.contains("b"));
199  }
200
201  public void testCopyOf_iteratorContainingNull() {
202    Iterator<String> c = Iterators.forArray("a", null, "b");
203    try {
204      copyOf(c);
205      fail();
206    } catch (NullPointerException expected) {
207    }
208  }
209
210  private static class CountingIterable implements Iterable<String> {
211    int count = 0;
212    @Override
213    public Iterator<String> iterator() {
214      count++;
215      return Iterators.forArray("a", "b", "a");
216    }
217  }
218
219  public void testCopyOf_plainIterable() {
220    CountingIterable iterable = new CountingIterable();
221    Set<String> set = copyOf(iterable);
222    assertEquals(2, set.size());
223    assertTrue(set.contains("a"));
224    assertTrue(set.contains("b"));
225  }
226
227  public void testCopyOf_plainIterable_iteratesOnce() {
228    CountingIterable iterable = new CountingIterable();
229    copyOf(iterable);
230    assertEquals(1, iterable.count);
231  }
232
233  public void testCopyOf_shortcut_empty() {
234    Collection<String> c = of();
235    assertEquals(Collections.<String>emptySet(), copyOf(c));
236    assertSame(c, copyOf(c));
237  }
238
239  public void testCopyOf_shortcut_singleton() {
240    Collection<String> c = of("a");
241    assertEquals(Collections.singleton("a"), copyOf(c));
242    assertSame(c, copyOf(c));
243  }
244
245  public void testCopyOf_shortcut_sameType() {
246    Collection<String> c = of("a", "b", "c");
247    assertSame(c, copyOf(c));
248  }
249
250  public void testToString() {
251    Set<String> set = of("a", "b", "c", "d", "e", "f", "g");
252    assertEquals("[a, b, c, d, e, f, g]", set.toString());
253  }
254
255  @GwtIncompatible("slow (~40s)")
256  public void testIterator_oneElement() {
257    new IteratorTester<String>(5, UNMODIFIABLE, Collections.singleton("a"),
258        IteratorTester.KnownOrder.KNOWN_ORDER) {
259      @Override protected Iterator<String> newTargetIterator() {
260        return of("a").iterator();
261      }
262    }.test();
263  }
264
265  @GwtIncompatible("slow (~30s)")
266  public void testIterator_general() {
267    new IteratorTester<String>(5, UNMODIFIABLE, asList("a", "b", "c"),
268        IteratorTester.KnownOrder.KNOWN_ORDER) {
269      @Override protected Iterator<String> newTargetIterator() {
270        return of("a", "b", "c").iterator();
271      }
272    }.test();
273  }
274
275  public void testContainsAll_sameType() {
276    Collection<String> c = of("a", "b", "c");
277    assertFalse(c.containsAll(of("a", "b", "c", "d")));
278    assertFalse(c.containsAll(of("a", "d")));
279    assertTrue(c.containsAll(of("a", "c")));
280    assertTrue(c.containsAll(of("a", "b", "c")));
281  }
282
283  public void testEquals_sameType() {
284    Collection<String> c = of("a", "b", "c");
285    assertTrue(c.equals(of("a", "b", "c")));
286    assertFalse(c.equals(of("a", "b", "d")));
287  }
288
289  abstract <E extends Comparable<E>> ImmutableSet.Builder<E> builder();
290
291  public void testBuilderWithNonDuplicateElements() {
292    ImmutableSet<String> set = this.<String>builder()
293        .add("a")
294        .add("b", "c")
295        .add("d", "e", "f")
296        .add("g", "h", "i", "j")
297        .build();
298    assertThat(set).has().exactly(
299        "a", "b", "c", "d", "e", "f", "g", "h", "i", "j").inOrder();
300  }
301
302  public void testReuseBuilderWithNonDuplicateElements() {
303    ImmutableSet.Builder<String> builder = this.<String>builder()
304        .add("a")
305        .add("b");
306    assertThat(builder.build()).has().exactly("a", "b").inOrder();
307    builder.add("c", "d");
308    assertThat(builder.build()).has().exactly("a", "b", "c", "d").inOrder();
309  }
310
311  public void testBuilderWithDuplicateElements() {
312    ImmutableSet<String> set = this.<String>builder()
313        .add("a")
314        .add("a", "a")
315        .add("a", "a", "a")
316        .add("a", "a", "a", "a")
317        .build();
318    assertTrue(set.contains("a"));
319    assertFalse(set.contains("b"));
320    assertEquals(1, set.size());
321  }
322
323  public void testReuseBuilderWithDuplicateElements() {
324    ImmutableSet.Builder<String> builder = this.<String>builder()
325        .add("a")
326        .add("a", "a")
327        .add("b");
328    assertThat(builder.build()).has().exactly("a", "b").inOrder();
329    builder.add("a", "b", "c", "c");
330    assertThat(builder.build()).has().exactly("a", "b", "c").inOrder();
331  }
332
333  public void testBuilderAddAll() {
334    List<String> a = asList("a", "b", "c");
335    List<String> b = asList("c", "d", "e");
336    ImmutableSet<String> set = this.<String>builder()
337        .addAll(a)
338        .addAll(b)
339        .build();
340    assertThat(set).has().exactly("a", "b", "c", "d", "e").inOrder();
341  }
342
343  static final int LAST_COLOR_ADDED = 0x00BFFF;
344
345  public void testComplexBuilder() {
346    List<Integer> colorElem = asList(0x00, 0x33, 0x66, 0x99, 0xCC, 0xFF);
347    // javac won't compile this without "this.<Integer>"
348    ImmutableSet.Builder<Integer> webSafeColorsBuilder
349        = this.<Integer>builder();
350    for (Integer red : colorElem) {
351      for (Integer green : colorElem) {
352        for (Integer blue : colorElem) {
353          webSafeColorsBuilder.add((red << 16) + (green << 8) + blue);
354        }
355      }
356    }
357    ImmutableSet<Integer> webSafeColors = webSafeColorsBuilder.build();
358    assertEquals(216, webSafeColors.size());
359    Integer[] webSafeColorArray =
360        webSafeColors.toArray(new Integer[webSafeColors.size()]);
361    assertEquals(0x000000, (int) webSafeColorArray[0]);
362    assertEquals(0x000033, (int) webSafeColorArray[1]);
363    assertEquals(0x000066, (int) webSafeColorArray[2]);
364    assertEquals(0x003300, (int) webSafeColorArray[6]);
365    assertEquals(0x330000, (int) webSafeColorArray[36]);
366    ImmutableSet<Integer> addedColor
367        = webSafeColorsBuilder.add(LAST_COLOR_ADDED).build();
368    assertEquals(
369        "Modifying the builder should not have changed any already built sets",
370        216, webSafeColors.size());
371    assertEquals("the new array should be one bigger than webSafeColors",
372        217, addedColor.size());
373    Integer[] appendColorArray =
374        addedColor.toArray(new Integer[addedColor.size()]);
375    assertEquals(
376        getComplexBuilderSetLastElement(), (int) appendColorArray[216]);
377  }
378
379  abstract int getComplexBuilderSetLastElement();
380
381  public void testBuilderAddHandlesNullsCorrectly() {
382    ImmutableSet.Builder<String> builder = this.<String>builder();
383    try {
384      builder.add((String) null);
385      fail("expected NullPointerException");  // COV_NF_LINE
386    } catch (NullPointerException expected) {
387    }
388
389    builder = this.<String>builder();
390    try {
391      builder.add((String[]) null);
392      fail("expected NullPointerException");  // COV_NF_LINE
393    } catch (NullPointerException expected) {
394    }
395
396    builder = this.<String>builder();
397    try {
398      builder.add("a", (String) null);
399      fail("expected NullPointerException");  // COV_NF_LINE
400    } catch (NullPointerException expected) {
401    }
402
403    builder = this.<String>builder();
404    try {
405      builder.add("a", "b", (String) null);
406      fail("expected NullPointerException");  // COV_NF_LINE
407    } catch (NullPointerException expected) {
408    }
409
410    builder = this.<String>builder();
411    try {
412      builder.add("a", "b", "c", null);
413      fail("expected NullPointerException");  // COV_NF_LINE
414    } catch (NullPointerException expected) {
415    }
416
417    builder = this.<String>builder();
418    try {
419      builder.add("a", "b", null, "c");
420      fail("expected NullPointerException");  // COV_NF_LINE
421    } catch (NullPointerException expected) {
422    }
423  }
424
425  public void testBuilderAddAllHandlesNullsCorrectly() {
426    ImmutableSet.Builder<String> builder = this.<String>builder();
427    try {
428      builder.addAll((Iterable<String>) null);
429      fail("expected NullPointerException");  // COV_NF_LINE
430    } catch (NullPointerException expected) {
431    }
432
433    try {
434      builder.addAll((Iterator<String>) null);
435      fail("expected NullPointerException");  // COV_NF_LINE
436    } catch (NullPointerException expected) {
437    }
438
439    builder = this.<String>builder();
440    List<String> listWithNulls = asList("a", null, "b");
441    try {
442      builder.addAll(listWithNulls);
443      fail("expected NullPointerException");  // COV_NF_LINE
444    } catch (NullPointerException expected) {
445    }
446
447    Iterable<String> iterableWithNulls = MinimalIterable.of("a", null, "b");
448    try {
449      builder.addAll(iterableWithNulls);
450      fail("expected NullPointerException");  // COV_NF_LINE
451    } catch (NullPointerException expected) {
452    }
453  }
454
455  /**
456   * Verify thread safety by using a collection whose size() may be inconsistent
457   * with the actual number of elements.  Tests using this method might fail in
458   * GWT because the GWT emulations might count on size() during copy.  It is
459   * safe to do so in GWT because javascript is single-threaded.
460   */
461  // TODO(benyu): turn this into a test once all copyOf(Collection) are
462  // thread-safe
463  @GwtIncompatible("GWT is single threaded")
464  void verifyThreadSafe() {
465    List<String> sample = Lists.newArrayList("a", "b", "c");
466    for (int delta : new int[] {-1, 0, 1}) {
467      for (int i = 0; i < sample.size(); i++) {
468        Collection<String> misleading = Helpers.misleadingSizeCollection(delta);
469        List<String> expected = sample.subList(0, i);
470        misleading.addAll(expected);
471        assertEquals("delta: " + delta + " sample size: " + i,
472            Sets.newHashSet(expected), copyOf(misleading));
473      }
474    }
475  }
476}
477