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