1/*
2 * Copyright (C) 2011 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.BoundType.CLOSED;
20import static com.google.common.collect.BoundType.OPEN;
21import static com.google.common.collect.DiscreteDomain.integers;
22import static com.google.common.testing.SerializableTester.reserialize;
23import static com.google.common.testing.SerializableTester.reserializeAndAssert;
24import static org.truth0.Truth.ASSERT;
25
26import com.google.common.annotations.GwtCompatible;
27import com.google.common.annotations.GwtIncompatible;
28import com.google.common.testing.EqualsTester;
29
30import junit.framework.Test;
31import junit.framework.TestCase;
32
33import java.util.Set;
34
35/**
36 * @author Gregory Kick
37 */
38@GwtCompatible(emulated = true)
39public class ContiguousSetTest extends TestCase {
40  private static DiscreteDomain<Integer> NOT_EQUAL_TO_INTEGERS = new DiscreteDomain<Integer>() {
41    @Override public Integer next(Integer value) {
42      return integers().next(value);
43    }
44
45    @Override public Integer previous(Integer value) {
46      return integers().previous(value);
47    }
48
49    @Override public long distance(Integer start, Integer end) {
50      return integers().distance(start, end);
51    }
52
53    @Override public Integer minValue() {
54      return integers().minValue();
55    }
56
57    @Override public Integer maxValue() {
58      return integers().maxValue();
59    }
60  };
61
62  public void testEquals() {
63    new EqualsTester()
64        .addEqualityGroup(
65            ContiguousSet.create(Range.closed(1, 3), integers()),
66            ContiguousSet.create(Range.closedOpen(1, 4), integers()),
67            ContiguousSet.create(Range.openClosed(0, 3), integers()),
68            ContiguousSet.create(Range.open(0, 4), integers()),
69            ContiguousSet.create(Range.closed(1, 3), NOT_EQUAL_TO_INTEGERS),
70            ContiguousSet.create(Range.closedOpen(1, 4), NOT_EQUAL_TO_INTEGERS),
71            ContiguousSet.create(Range.openClosed(0, 3), NOT_EQUAL_TO_INTEGERS),
72            ContiguousSet.create(Range.open(0, 4), NOT_EQUAL_TO_INTEGERS),
73            ImmutableSortedSet.of(1, 2, 3))
74        .testEquals();
75    // not testing hashCode for these because it takes forever to compute
76    assertEquals(
77        ContiguousSet.create(Range.closed(Integer.MIN_VALUE, Integer.MAX_VALUE), integers()),
78        ContiguousSet.create(Range.<Integer>all(), integers()));
79    assertEquals(
80        ContiguousSet.create(Range.closed(Integer.MIN_VALUE, Integer.MAX_VALUE), integers()),
81        ContiguousSet.create(Range.atLeast(Integer.MIN_VALUE), integers()));
82    assertEquals(
83        ContiguousSet.create(Range.closed(Integer.MIN_VALUE, Integer.MAX_VALUE), integers()),
84        ContiguousSet.create(Range.atMost(Integer.MAX_VALUE), integers()));
85  }
86
87  @GwtIncompatible("SerializableTester")
88  public void testSerialization() {
89    ContiguousSet<Integer> empty = ContiguousSet.create(Range.closedOpen(1, 1), integers());
90    assertTrue(empty instanceof EmptyContiguousSet);
91    reserializeAndAssert(empty);
92
93    ContiguousSet<Integer> regular = ContiguousSet.create(Range.closed(1, 3), integers());
94    assertTrue(regular instanceof RegularContiguousSet);
95    reserializeAndAssert(regular);
96
97    /*
98     * Make sure that we're using RegularContiguousSet.SerializedForm and not
99     * ImmutableSet.SerializedForm, which would be enormous.
100     */
101    ContiguousSet<Integer> enormous = ContiguousSet.create(Range.<Integer>all(), integers());
102    assertTrue(enormous instanceof RegularContiguousSet);
103    // We can't use reserializeAndAssert because it calls hashCode, which is enormously slow.
104    ContiguousSet<Integer> enormousReserialized = reserialize(enormous);
105    assertEquals(enormous, enormousReserialized);
106  }
107
108  public void testCreate_noMin() {
109    Range<Integer> range = Range.lessThan(0);
110    try {
111      ContiguousSet.create(range, RangeTest.UNBOUNDED_DOMAIN);
112      fail();
113    } catch (IllegalArgumentException expected) {}
114  }
115
116  public void testCreate_noMax() {
117    Range<Integer> range = Range.greaterThan(0);
118    try {
119      ContiguousSet.create(range, RangeTest.UNBOUNDED_DOMAIN);
120      fail();
121    } catch (IllegalArgumentException expected) {}
122  }
123
124  public void testCreate_empty() {
125    assertEquals(ImmutableSet.of(), ContiguousSet.create(Range.closedOpen(1, 1), integers()));
126    assertEquals(ImmutableSet.of(), ContiguousSet.create(Range.openClosed(5, 5), integers()));
127    assertEquals(ImmutableSet.of(),
128        ContiguousSet.create(Range.lessThan(Integer.MIN_VALUE), integers()));
129    assertEquals(ImmutableSet.of(),
130        ContiguousSet.create(Range.greaterThan(Integer.MAX_VALUE), integers()));
131  }
132
133  public void testHeadSet() {
134    ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
135    ASSERT.that(set.headSet(1)).isEmpty();
136    ASSERT.that(set.headSet(2)).has().item(1);
137    ASSERT.that(set.headSet(3)).has().exactly(1, 2).inOrder();
138    ASSERT.that(set.headSet(4)).has().exactly(1, 2, 3).inOrder();
139    ASSERT.that(set.headSet(Integer.MAX_VALUE)).has().exactly(1, 2, 3).inOrder();
140    ASSERT.that(set.headSet(1, true)).has().item(1);
141    ASSERT.that(set.headSet(2, true)).has().exactly(1, 2).inOrder();
142    ASSERT.that(set.headSet(3, true)).has().exactly(1, 2, 3).inOrder();
143    ASSERT.that(set.headSet(4, true)).has().exactly(1, 2, 3).inOrder();
144    ASSERT.that(set.headSet(Integer.MAX_VALUE, true)).has().exactly(1, 2, 3).inOrder();
145  }
146
147  public void testHeadSet_tooSmall() {
148    ASSERT.that(ContiguousSet.create(Range.closed(1, 3), integers()).headSet(0)).isEmpty();
149  }
150
151  public void testTailSet() {
152    ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
153    ASSERT.that(set.tailSet(Integer.MIN_VALUE)).has().exactly(1, 2, 3).inOrder();
154    ASSERT.that(set.tailSet(1)).has().exactly(1, 2, 3).inOrder();
155    ASSERT.that(set.tailSet(2)).has().exactly(2, 3).inOrder();
156    ASSERT.that(set.tailSet(3)).has().item(3);
157    ASSERT.that(set.tailSet(Integer.MIN_VALUE, false)).has().exactly(1, 2, 3).inOrder();
158    ASSERT.that(set.tailSet(1, false)).has().exactly(2, 3).inOrder();
159    ASSERT.that(set.tailSet(2, false)).has().item(3);
160    ASSERT.that(set.tailSet(3, false)).isEmpty();
161  }
162
163  public void testTailSet_tooLarge() {
164    ASSERT.that(ContiguousSet.create(Range.closed(1, 3), integers()).tailSet(4)).isEmpty();
165  }
166
167  public void testSubSet() {
168    ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
169    ASSERT.that(set.subSet(1, 4)).has().exactly(1, 2, 3).inOrder();
170    ASSERT.that(set.subSet(2, 4)).has().exactly(2, 3).inOrder();
171    ASSERT.that(set.subSet(3, 4)).has().item(3);
172    ASSERT.that(set.subSet(3, 3)).isEmpty();
173    ASSERT.that(set.subSet(2, 3)).has().item(2);
174    ASSERT.that(set.subSet(1, 3)).has().exactly(1, 2).inOrder();
175    ASSERT.that(set.subSet(1, 2)).has().item(1);
176    ASSERT.that(set.subSet(2, 2)).isEmpty();
177    ASSERT.that(set.subSet(Integer.MIN_VALUE, Integer.MAX_VALUE)).has().exactly(1, 2, 3).inOrder();
178    ASSERT.that(set.subSet(1, true, 3, true)).has().exactly(1, 2, 3).inOrder();
179    ASSERT.that(set.subSet(1, false, 3, true)).has().exactly(2, 3).inOrder();
180    ASSERT.that(set.subSet(1, true, 3, false)).has().exactly(1, 2).inOrder();
181    ASSERT.that(set.subSet(1, false, 3, false)).has().item(2);
182  }
183
184  public void testSubSet_outOfOrder() {
185    ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
186    try {
187      set.subSet(3, 2);
188      fail();
189    } catch (IllegalArgumentException expected) {}
190  }
191
192  public void testSubSet_tooLarge() {
193    ASSERT.that(ContiguousSet.create(Range.closed(1, 3), integers()).subSet(4, 6)).isEmpty();
194  }
195
196  public void testSubSet_tooSmall() {
197    ASSERT.that(ContiguousSet.create(Range.closed(1, 3), integers()).subSet(-1, 0)).isEmpty();
198  }
199
200  public void testFirst() {
201    assertEquals(1, ContiguousSet.create(Range.closed(1, 3), integers()).first().intValue());
202    assertEquals(1, ContiguousSet.create(Range.open(0, 4), integers()).first().intValue());
203    assertEquals(Integer.MIN_VALUE,
204        ContiguousSet.create(Range.<Integer>all(), integers()).first().intValue());
205  }
206
207  public void testLast() {
208    assertEquals(3, ContiguousSet.create(Range.closed(1, 3), integers()).last().intValue());
209    assertEquals(3, ContiguousSet.create(Range.open(0, 4), integers()).last().intValue());
210    assertEquals(Integer.MAX_VALUE,
211        ContiguousSet.create(Range.<Integer>all(), integers()).last().intValue());
212  }
213
214  public void testContains() {
215    ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
216    assertFalse(set.contains(0));
217    assertTrue(set.contains(1));
218    assertTrue(set.contains(2));
219    assertTrue(set.contains(3));
220    assertFalse(set.contains(4));
221    set = ContiguousSet.create(Range.open(0, 4), integers());
222    assertFalse(set.contains(0));
223    assertTrue(set.contains(1));
224    assertTrue(set.contains(2));
225    assertTrue(set.contains(3));
226    assertFalse(set.contains(4));
227    assertFalse(set.contains("blah"));
228  }
229
230  public void testContainsAll() {
231    ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
232    for (Set<Integer> subset : Sets.powerSet(ImmutableSet.of(1, 2, 3))) {
233      assertTrue(set.containsAll(subset));
234    }
235    for (Set<Integer> subset : Sets.powerSet(ImmutableSet.of(1, 2, 3))) {
236      assertFalse(set.containsAll(Sets.union(subset, ImmutableSet.of(9))));
237    }
238    assertFalse(set.containsAll(ImmutableSet.of("blah")));
239  }
240
241  public void testRange() {
242    assertEquals(Range.closed(1, 3),
243        ContiguousSet.create(Range.closed(1, 3), integers()).range());
244    assertEquals(Range.closed(1, 3),
245        ContiguousSet.create(Range.closedOpen(1, 4), integers()).range());
246    assertEquals(Range.closed(1, 3), ContiguousSet.create(Range.open(0, 4), integers()).range());
247    assertEquals(Range.closed(1, 3),
248        ContiguousSet.create(Range.openClosed(0, 3), integers()).range());
249
250    assertEquals(Range.openClosed(0, 3),
251        ContiguousSet.create(Range.closed(1, 3), integers()).range(OPEN, CLOSED));
252    assertEquals(Range.openClosed(0, 3),
253        ContiguousSet.create(Range.closedOpen(1, 4), integers()).range(OPEN, CLOSED));
254    assertEquals(Range.openClosed(0, 3),
255        ContiguousSet.create(Range.open(0, 4), integers()).range(OPEN, CLOSED));
256    assertEquals(Range.openClosed(0, 3),
257        ContiguousSet.create(Range.openClosed(0, 3), integers()).range(OPEN, CLOSED));
258
259    assertEquals(Range.open(0, 4),
260        ContiguousSet.create(Range.closed(1, 3), integers()).range(OPEN, OPEN));
261    assertEquals(Range.open(0, 4),
262        ContiguousSet.create(Range.closedOpen(1, 4), integers()).range(OPEN, OPEN));
263    assertEquals(Range.open(0, 4),
264        ContiguousSet.create(Range.open(0, 4), integers()).range(OPEN, OPEN));
265    assertEquals(Range.open(0, 4),
266        ContiguousSet.create(Range.openClosed(0, 3), integers()).range(OPEN, OPEN));
267
268    assertEquals(Range.closedOpen(1, 4),
269        ContiguousSet.create(Range.closed(1, 3), integers()).range(CLOSED, OPEN));
270    assertEquals(Range.closedOpen(1, 4),
271        ContiguousSet.create(Range.closedOpen(1, 4), integers()).range(CLOSED, OPEN));
272    assertEquals(Range.closedOpen(1, 4),
273        ContiguousSet.create(Range.open(0, 4), integers()).range(CLOSED, OPEN));
274    assertEquals(Range.closedOpen(1, 4),
275        ContiguousSet.create(Range.openClosed(0, 3), integers()).range(CLOSED, OPEN));
276  }
277
278  public void testRange_unboundedRange() {
279    assertEquals(Range.closed(Integer.MIN_VALUE, Integer.MAX_VALUE),
280        ContiguousSet.create(Range.<Integer>all(), integers()).range());
281    assertEquals(Range.atLeast(Integer.MIN_VALUE),
282        ContiguousSet.create(Range.<Integer>all(), integers()).range(CLOSED, OPEN));
283    assertEquals(Range.all(),
284        ContiguousSet.create(Range.<Integer>all(), integers()).range(OPEN, OPEN));
285    assertEquals(Range.atMost(Integer.MAX_VALUE),
286        ContiguousSet.create(Range.<Integer>all(), integers()).range(OPEN, CLOSED));
287  }
288
289  public void testIntersection_empty() {
290    ContiguousSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
291    ContiguousSet<Integer> emptySet = ContiguousSet.create(Range.closedOpen(2, 2), integers());
292    assertEquals(ImmutableSet.of(), set.intersection(emptySet));
293    assertEquals(ImmutableSet.of(), emptySet.intersection(set));
294    assertEquals(ImmutableSet.of(),
295        ContiguousSet.create(Range.closed(-5, -1), integers()).intersection(
296            ContiguousSet.create(Range.open(3, 64), integers())));
297  }
298
299  public void testIntersection() {
300    ContiguousSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
301    assertEquals(ImmutableSet.of(1, 2, 3),
302        ContiguousSet.create(Range.open(-1, 4), integers()).intersection(set));
303    assertEquals(ImmutableSet.of(1, 2, 3),
304        set.intersection(ContiguousSet.create(Range.open(-1, 4), integers())));
305  }
306}
307