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 
17 package com.google.common.collect;
18 
19 import static com.google.common.collect.BoundType.CLOSED;
20 import static com.google.common.collect.BoundType.OPEN;
21 import static com.google.common.collect.DiscreteDomain.integers;
22 import static com.google.common.testing.SerializableTester.reserialize;
23 import static com.google.common.testing.SerializableTester.reserializeAndAssert;
24 import static org.truth0.Truth.ASSERT;
25 
26 import com.google.common.annotations.GwtCompatible;
27 import com.google.common.annotations.GwtIncompatible;
28 import com.google.common.testing.EqualsTester;
29 
30 import junit.framework.Test;
31 import junit.framework.TestCase;
32 
33 import java.util.Set;
34 
35 /**
36  * @author Gregory Kick
37  */
38 @GwtCompatible(emulated = true)
39 public 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 
testEquals()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")
testSerialization()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 
testCreate_noMin()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 
testCreate_noMax()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 
testCreate_empty()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 
testHeadSet()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 
testHeadSet_tooSmall()147   public void testHeadSet_tooSmall() {
148     ASSERT.that(ContiguousSet.create(Range.closed(1, 3), integers()).headSet(0)).isEmpty();
149   }
150 
testTailSet()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 
testTailSet_tooLarge()163   public void testTailSet_tooLarge() {
164     ASSERT.that(ContiguousSet.create(Range.closed(1, 3), integers()).tailSet(4)).isEmpty();
165   }
166 
testSubSet()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 
testSubSet_outOfOrder()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 
testSubSet_tooLarge()192   public void testSubSet_tooLarge() {
193     ASSERT.that(ContiguousSet.create(Range.closed(1, 3), integers()).subSet(4, 6)).isEmpty();
194   }
195 
testSubSet_tooSmall()196   public void testSubSet_tooSmall() {
197     ASSERT.that(ContiguousSet.create(Range.closed(1, 3), integers()).subSet(-1, 0)).isEmpty();
198   }
199 
testFirst()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 
testLast()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 
testContains()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 
testContainsAll()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 
testRange()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 
testRange_unboundedRange()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 
testIntersection_empty()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 
testIntersection()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