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 java.util.Arrays.asList;
21import static org.junit.contrib.truth.Truth.ASSERT;
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    ASSERT.that(set).hasContentsInOrder(
299        "a", "b", "c", "d", "e", "f", "g", "h", "i", "j");
300  }
301
302  public void testBuilderWithDuplicateElements() {
303    ImmutableSet<String> set = this.<String>builder()
304        .add("a")
305        .add("a", "a")
306        .add("a", "a", "a")
307        .add("a", "a", "a", "a")
308        .build();
309    assertTrue(set.contains("a"));
310    assertFalse(set.contains("b"));
311    assertEquals(1, set.size());
312  }
313
314  public void testBuilderAddAll() {
315    List<String> a = asList("a", "b", "c");
316    List<String> b = asList("c", "d", "e");
317    ImmutableSet<String> set = this.<String>builder()
318        .addAll(a)
319        .addAll(b)
320        .build();
321    ASSERT.that(set).hasContentsInOrder("a", "b", "c", "d", "e");
322  }
323
324  static final int LAST_COLOR_ADDED = 0x00BFFF;
325
326  public void testComplexBuilder() {
327    List<Integer> colorElem = asList(0x00, 0x33, 0x66, 0x99, 0xCC, 0xFF);
328    // javac won't compile this without "this.<Integer>"
329    ImmutableSet.Builder<Integer> webSafeColorsBuilder
330        = this.<Integer>builder();
331    for (Integer red : colorElem) {
332      for (Integer green : colorElem) {
333        for (Integer blue : colorElem) {
334          webSafeColorsBuilder.add((red << 16) + (green << 8) + blue);
335        }
336      }
337    }
338    ImmutableSet<Integer> webSafeColors = webSafeColorsBuilder.build();
339    assertEquals(216, webSafeColors.size());
340    Integer[] webSafeColorArray =
341        webSafeColors.toArray(new Integer[webSafeColors.size()]);
342    assertEquals(0x000000, (int) webSafeColorArray[0]);
343    assertEquals(0x000033, (int) webSafeColorArray[1]);
344    assertEquals(0x000066, (int) webSafeColorArray[2]);
345    assertEquals(0x003300, (int) webSafeColorArray[6]);
346    assertEquals(0x330000, (int) webSafeColorArray[36]);
347    ImmutableSet<Integer> addedColor
348        = webSafeColorsBuilder.add(LAST_COLOR_ADDED).build();
349    assertEquals(
350        "Modifying the builder should not have changed any already built sets",
351        216, webSafeColors.size());
352    assertEquals("the new array should be one bigger than webSafeColors",
353        217, addedColor.size());
354    Integer[] appendColorArray =
355        addedColor.toArray(new Integer[addedColor.size()]);
356    assertEquals(
357        getComplexBuilderSetLastElement(), (int) appendColorArray[216]);
358  }
359
360  abstract int getComplexBuilderSetLastElement();
361
362  public void testBuilderAddHandlesNullsCorrectly() {
363    ImmutableSet.Builder<String> builder = this.<String>builder();
364    try {
365      builder.add((String) null);
366      fail("expected NullPointerException");  // COV_NF_LINE
367    } catch (NullPointerException expected) {
368    }
369
370    builder = this.<String>builder();
371    try {
372      builder.add((String[]) null);
373      fail("expected NullPointerException");  // COV_NF_LINE
374    } catch (NullPointerException expected) {
375    }
376
377    builder = this.<String>builder();
378    try {
379      builder.add("a", (String) null);
380      fail("expected NullPointerException");  // COV_NF_LINE
381    } catch (NullPointerException expected) {
382    }
383
384    builder = this.<String>builder();
385    try {
386      builder.add("a", "b", (String) null);
387      fail("expected NullPointerException");  // COV_NF_LINE
388    } catch (NullPointerException expected) {
389    }
390
391    builder = this.<String>builder();
392    try {
393      builder.add("a", "b", "c", null);
394      fail("expected NullPointerException");  // COV_NF_LINE
395    } catch (NullPointerException expected) {
396    }
397
398    builder = this.<String>builder();
399    try {
400      builder.add("a", "b", null, "c");
401      fail("expected NullPointerException");  // COV_NF_LINE
402    } catch (NullPointerException expected) {
403    }
404  }
405
406  public void testBuilderAddAllHandlesNullsCorrectly() {
407    ImmutableSet.Builder<String> builder = this.<String>builder();
408    try {
409      builder.addAll((Iterable<String>) null);
410      fail("expected NullPointerException");  // COV_NF_LINE
411    } catch (NullPointerException expected) {
412    }
413
414    try {
415      builder.addAll((Iterator<String>) null);
416      fail("expected NullPointerException");  // COV_NF_LINE
417    } catch (NullPointerException expected) {
418    }
419
420    builder = this.<String>builder();
421    List<String> listWithNulls = asList("a", null, "b");
422    try {
423      builder.addAll(listWithNulls);
424      fail("expected NullPointerException");  // COV_NF_LINE
425    } catch (NullPointerException expected) {
426    }
427
428    Iterable<String> iterableWithNulls = MinimalIterable.of("a", null, "b");
429    try {
430      builder.addAll(iterableWithNulls);
431      fail("expected NullPointerException");  // COV_NF_LINE
432    } catch (NullPointerException expected) {
433    }
434  }
435
436  /**
437   * Verify thread safety by using a collection whose size() may be inconsistent
438   * with the actual number of elements.  Tests using this method might fail in
439   * GWT because the GWT emulations might count on size() during copy.  It is
440   * safe to do so in GWT because javascript is single-threaded.
441   */
442  // TODO(benyu): turn this into a test once all copyOf(Collection) are
443  // thread-safe
444  @GwtIncompatible("GWT is single threaded")
445  void verifyThreadSafe() {
446    List<String> sample = Lists.newArrayList("a", "b", "c");
447    for (int delta : new int[] {-1, 0, 1}) {
448      for (int i = 0; i < sample.size(); i++) {
449        Collection<String> misleading = Helpers.misleadingSizeCollection(delta);
450        List<String> expected = sample.subList(0, i);
451        misleading.addAll(expected);
452        assertEquals("delta: " + delta + " sample size: " + i,
453            Sets.newHashSet(expected), copyOf(misleading));
454      }
455    }
456  }
457}
458