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 import java.util.Collection;
42 import java.util.Set;
43 import junit.framework.Test;
44 import junit.framework.TestCase;
45 import junit.framework.TestSuite;
46 
47 /** @author Gregory Kick */
48 @GwtCompatible(emulated = true)
49 public class ContiguousSetTest extends TestCase {
50   private static final DiscreteDomain<Integer> NOT_EQUAL_TO_INTEGERS =
51       new DiscreteDomain<Integer>() {
52         @Override
53         public Integer next(Integer value) {
54           return integers().next(value);
55         }
56 
57         @Override
58         public Integer previous(Integer value) {
59           return integers().previous(value);
60         }
61 
62         @Override
63         public long distance(Integer start, Integer end) {
64           return integers().distance(start, end);
65         }
66 
67         @Override
68         public Integer minValue() {
69           return integers().minValue();
70         }
71 
72         @Override
73         public Integer maxValue() {
74           return integers().maxValue();
75         }
76       };
77 
testInvalidIntRange()78   public void testInvalidIntRange() {
79     try {
80       ContiguousSet.closed(2, 1);
81       fail();
82     } catch (IllegalArgumentException expected) {
83     }
84     try {
85       ContiguousSet.closedOpen(2, 1);
86       fail();
87     } catch (IllegalArgumentException expected) {
88     }
89   }
90 
testInvalidLongRange()91   public void testInvalidLongRange() {
92     try {
93       ContiguousSet.closed(2L, 1L);
94       fail();
95     } catch (IllegalArgumentException expected) {
96     }
97     try {
98       ContiguousSet.closedOpen(2L, 1L);
99       fail();
100     } catch (IllegalArgumentException expected) {
101     }
102   }
103 
testEquals()104   public void testEquals() {
105     new EqualsTester()
106         .addEqualityGroup(
107             ContiguousSet.create(Range.closed(1, 3), integers()),
108             ContiguousSet.closed(1, 3),
109             ContiguousSet.create(Range.closedOpen(1, 4), integers()),
110             ContiguousSet.closedOpen(1, 4),
111             ContiguousSet.create(Range.openClosed(0, 3), integers()),
112             ContiguousSet.create(Range.open(0, 4), integers()),
113             ContiguousSet.create(Range.closed(1, 3), NOT_EQUAL_TO_INTEGERS),
114             ContiguousSet.create(Range.closedOpen(1, 4), NOT_EQUAL_TO_INTEGERS),
115             ContiguousSet.create(Range.openClosed(0, 3), NOT_EQUAL_TO_INTEGERS),
116             ContiguousSet.create(Range.open(0, 4), NOT_EQUAL_TO_INTEGERS),
117             ImmutableSortedSet.of(1, 2, 3))
118         .addEqualityGroup(
119             ContiguousSet.create(Range.closedOpen(1, 1), integers()),
120             ContiguousSet.closedOpen(1, 1),
121             ContiguousSet.closedOpen(Integer.MIN_VALUE, Integer.MIN_VALUE),
122             ImmutableSortedSet.of(),
123             ImmutableSet.of())
124         .testEquals();
125     // not testing hashCode for these because it takes forever to compute
126     assertEquals(
127         ContiguousSet.closed(Integer.MIN_VALUE, Integer.MAX_VALUE),
128         ContiguousSet.create(Range.<Integer>all(), integers()));
129     assertEquals(
130         ContiguousSet.closed(Integer.MIN_VALUE, Integer.MAX_VALUE),
131         ContiguousSet.create(Range.atLeast(Integer.MIN_VALUE), integers()));
132     assertEquals(
133         ContiguousSet.closed(Integer.MIN_VALUE, Integer.MAX_VALUE),
134         ContiguousSet.create(Range.atMost(Integer.MAX_VALUE), integers()));
135   }
136 
137   @GwtIncompatible // SerializableTester
testSerialization()138   public void testSerialization() {
139     ContiguousSet<Integer> empty = ContiguousSet.create(Range.closedOpen(1, 1), integers());
140     assertTrue(empty instanceof EmptyContiguousSet);
141     reserializeAndAssert(empty);
142 
143     ContiguousSet<Integer> regular = ContiguousSet.create(Range.closed(1, 3), integers());
144     assertTrue(regular instanceof RegularContiguousSet);
145     reserializeAndAssert(regular);
146 
147     /*
148      * Make sure that we're using RegularContiguousSet.SerializedForm and not
149      * ImmutableSet.SerializedForm, which would be enormous.
150      */
151     ContiguousSet<Integer> enormous = ContiguousSet.create(Range.<Integer>all(), integers());
152     assertTrue(enormous instanceof RegularContiguousSet);
153     // We can't use reserializeAndAssert because it calls hashCode, which is enormously slow.
154     ContiguousSet<Integer> enormousReserialized = reserialize(enormous);
155     assertEquals(enormous, enormousReserialized);
156   }
157 
testCreate_noMin()158   public void testCreate_noMin() {
159     Range<Integer> range = Range.lessThan(0);
160     try {
161       ContiguousSet.create(range, RangeTest.UNBOUNDED_DOMAIN);
162       fail();
163     } catch (IllegalArgumentException expected) {
164     }
165   }
166 
testCreate_noMax()167   public void testCreate_noMax() {
168     Range<Integer> range = Range.greaterThan(0);
169     try {
170       ContiguousSet.create(range, RangeTest.UNBOUNDED_DOMAIN);
171       fail();
172     } catch (IllegalArgumentException expected) {
173     }
174   }
175 
testCreate_empty()176   public void testCreate_empty() {
177     assertEquals(ImmutableSet.of(), ContiguousSet.create(Range.closedOpen(1, 1), integers()));
178     assertEquals(ImmutableSet.of(), ContiguousSet.closedOpen(1, 1));
179     assertEquals(ImmutableSet.of(), ContiguousSet.create(Range.openClosed(5, 5), integers()));
180     assertEquals(
181         ImmutableSet.of(), ContiguousSet.create(Range.lessThan(Integer.MIN_VALUE), integers()));
182     assertEquals(
183         ImmutableSet.of(), ContiguousSet.create(Range.greaterThan(Integer.MAX_VALUE), integers()));
184   }
185 
testHeadSet()186   public void testHeadSet() {
187     ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
188     assertThat(set.headSet(1)).isEmpty();
189     assertThat(set.headSet(2)).containsExactly(1).inOrder();
190     assertThat(set.headSet(3)).containsExactly(1, 2).inOrder();
191     assertThat(set.headSet(4)).containsExactly(1, 2, 3).inOrder();
192     assertThat(set.headSet(Integer.MAX_VALUE)).containsExactly(1, 2, 3).inOrder();
193     assertThat(set.headSet(1, true)).containsExactly(1).inOrder();
194     assertThat(set.headSet(2, true)).containsExactly(1, 2).inOrder();
195     assertThat(set.headSet(3, true)).containsExactly(1, 2, 3).inOrder();
196     assertThat(set.headSet(4, true)).containsExactly(1, 2, 3).inOrder();
197     assertThat(set.headSet(Integer.MAX_VALUE, true)).containsExactly(1, 2, 3).inOrder();
198   }
199 
testHeadSet_tooSmall()200   public void testHeadSet_tooSmall() {
201     assertThat(ContiguousSet.create(Range.closed(1, 3), integers()).headSet(0)).isEmpty();
202   }
203 
testTailSet()204   public void testTailSet() {
205     ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
206     assertThat(set.tailSet(Integer.MIN_VALUE)).containsExactly(1, 2, 3).inOrder();
207     assertThat(set.tailSet(1)).containsExactly(1, 2, 3).inOrder();
208     assertThat(set.tailSet(2)).containsExactly(2, 3).inOrder();
209     assertThat(set.tailSet(3)).containsExactly(3).inOrder();
210     assertThat(set.tailSet(Integer.MIN_VALUE, false)).containsExactly(1, 2, 3).inOrder();
211     assertThat(set.tailSet(1, false)).containsExactly(2, 3).inOrder();
212     assertThat(set.tailSet(2, false)).containsExactly(3).inOrder();
213     assertThat(set.tailSet(3, false)).isEmpty();
214   }
215 
testTailSet_tooLarge()216   public void testTailSet_tooLarge() {
217     assertThat(ContiguousSet.create(Range.closed(1, 3), integers()).tailSet(4)).isEmpty();
218   }
219 
testSubSet()220   public void testSubSet() {
221     ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
222     assertThat(set.subSet(1, 4)).containsExactly(1, 2, 3).inOrder();
223     assertThat(set.subSet(2, 4)).containsExactly(2, 3).inOrder();
224     assertThat(set.subSet(3, 4)).containsExactly(3).inOrder();
225     assertThat(set.subSet(3, 3)).isEmpty();
226     assertThat(set.subSet(2, 3)).containsExactly(2).inOrder();
227     assertThat(set.subSet(1, 3)).containsExactly(1, 2).inOrder();
228     assertThat(set.subSet(1, 2)).containsExactly(1).inOrder();
229     assertThat(set.subSet(2, 2)).isEmpty();
230     assertThat(set.subSet(Integer.MIN_VALUE, Integer.MAX_VALUE)).containsExactly(1, 2, 3).inOrder();
231     assertThat(set.subSet(1, true, 3, true)).containsExactly(1, 2, 3).inOrder();
232     assertThat(set.subSet(1, false, 3, true)).containsExactly(2, 3).inOrder();
233     assertThat(set.subSet(1, true, 3, false)).containsExactly(1, 2).inOrder();
234     assertThat(set.subSet(1, false, 3, false)).containsExactly(2).inOrder();
235   }
236 
testSubSet_outOfOrder()237   public void testSubSet_outOfOrder() {
238     ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
239     try {
240       set.subSet(3, 2);
241       fail();
242     } catch (IllegalArgumentException expected) {
243     }
244   }
245 
testSubSet_tooLarge()246   public void testSubSet_tooLarge() {
247     assertThat(ContiguousSet.create(Range.closed(1, 3), integers()).subSet(4, 6)).isEmpty();
248   }
249 
testSubSet_tooSmall()250   public void testSubSet_tooSmall() {
251     assertThat(ContiguousSet.create(Range.closed(1, 3), integers()).subSet(-1, 0)).isEmpty();
252   }
253 
testFirst()254   public void testFirst() {
255     assertEquals(1, ContiguousSet.create(Range.closed(1, 3), integers()).first().intValue());
256     assertEquals(1, ContiguousSet.create(Range.open(0, 4), integers()).first().intValue());
257     assertEquals(
258         Integer.MIN_VALUE,
259         ContiguousSet.create(Range.<Integer>all(), integers()).first().intValue());
260   }
261 
testLast()262   public void testLast() {
263     assertEquals(3, ContiguousSet.create(Range.closed(1, 3), integers()).last().intValue());
264     assertEquals(3, ContiguousSet.create(Range.open(0, 4), integers()).last().intValue());
265     assertEquals(
266         Integer.MAX_VALUE,
267         ContiguousSet.create(Range.<Integer>all(), integers()).last().intValue());
268   }
269 
testContains()270   public void testContains() {
271     ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
272     assertFalse(set.contains(0));
273     assertTrue(set.contains(1));
274     assertTrue(set.contains(2));
275     assertTrue(set.contains(3));
276     assertFalse(set.contains(4));
277     set = ContiguousSet.create(Range.open(0, 4), integers());
278     assertFalse(set.contains(0));
279     assertTrue(set.contains(1));
280     assertTrue(set.contains(2));
281     assertTrue(set.contains(3));
282     assertFalse(set.contains(4));
283     assertFalse(set.contains((Object) "blah"));
284   }
285 
testContainsAll()286   public void testContainsAll() {
287     ImmutableSortedSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
288     for (Set<Integer> subset : Sets.powerSet(ImmutableSet.of(1, 2, 3))) {
289       assertTrue(set.containsAll(subset));
290     }
291     for (Set<Integer> subset : Sets.powerSet(ImmutableSet.of(1, 2, 3))) {
292       assertFalse(set.containsAll(Sets.union(subset, ImmutableSet.of(9))));
293     }
294     assertFalse(set.containsAll((Collection<?>) ImmutableSet.of("blah")));
295   }
296 
testRange()297   public void testRange() {
298     assertEquals(Range.closed(1, 3), ContiguousSet.create(Range.closed(1, 3), integers()).range());
299     assertEquals(Range.closed(1, 3), ContiguousSet.closed(1, 3).range());
300     assertEquals(
301         Range.closed(1, 3), ContiguousSet.create(Range.closedOpen(1, 4), integers()).range());
302     assertEquals(Range.closed(1, 3), ContiguousSet.closedOpen(1, 4).range());
303     assertEquals(Range.closed(1, 3), ContiguousSet.create(Range.open(0, 4), integers()).range());
304     assertEquals(
305         Range.closed(1, 3), ContiguousSet.create(Range.openClosed(0, 3), integers()).range());
306 
307     assertEquals(
308         Range.openClosed(0, 3),
309         ContiguousSet.create(Range.closed(1, 3), integers()).range(OPEN, CLOSED));
310     assertEquals(
311         Range.openClosed(0, 3),
312         ContiguousSet.create(Range.closedOpen(1, 4), integers()).range(OPEN, CLOSED));
313     assertEquals(
314         Range.openClosed(0, 3),
315         ContiguousSet.create(Range.open(0, 4), integers()).range(OPEN, CLOSED));
316     assertEquals(
317         Range.openClosed(0, 3),
318         ContiguousSet.create(Range.openClosed(0, 3), integers()).range(OPEN, CLOSED));
319 
320     assertEquals(
321         Range.open(0, 4), ContiguousSet.create(Range.closed(1, 3), integers()).range(OPEN, OPEN));
322     assertEquals(
323         Range.open(0, 4),
324         ContiguousSet.create(Range.closedOpen(1, 4), integers()).range(OPEN, OPEN));
325     assertEquals(
326         Range.open(0, 4), ContiguousSet.create(Range.open(0, 4), integers()).range(OPEN, OPEN));
327     assertEquals(
328         Range.open(0, 4),
329         ContiguousSet.create(Range.openClosed(0, 3), integers()).range(OPEN, OPEN));
330 
331     assertEquals(
332         Range.closedOpen(1, 4),
333         ContiguousSet.create(Range.closed(1, 3), integers()).range(CLOSED, OPEN));
334     assertEquals(
335         Range.closedOpen(1, 4),
336         ContiguousSet.create(Range.closedOpen(1, 4), integers()).range(CLOSED, OPEN));
337     assertEquals(
338         Range.closedOpen(1, 4),
339         ContiguousSet.create(Range.open(0, 4), integers()).range(CLOSED, OPEN));
340     assertEquals(
341         Range.closedOpen(1, 4),
342         ContiguousSet.create(Range.openClosed(0, 3), integers()).range(CLOSED, OPEN));
343   }
344 
testRange_unboundedRange()345   public void testRange_unboundedRange() {
346     assertEquals(
347         Range.closed(Integer.MIN_VALUE, Integer.MAX_VALUE),
348         ContiguousSet.create(Range.<Integer>all(), integers()).range());
349     assertEquals(
350         Range.atLeast(Integer.MIN_VALUE),
351         ContiguousSet.create(Range.<Integer>all(), integers()).range(CLOSED, OPEN));
352     assertEquals(
353         Range.all(), ContiguousSet.create(Range.<Integer>all(), integers()).range(OPEN, OPEN));
354     assertEquals(
355         Range.atMost(Integer.MAX_VALUE),
356         ContiguousSet.create(Range.<Integer>all(), integers()).range(OPEN, CLOSED));
357   }
358 
testIntersection_empty()359   public void testIntersection_empty() {
360     ContiguousSet<Integer> set = ContiguousSet.closed(1, 3);
361     ContiguousSet<Integer> emptySet = ContiguousSet.closedOpen(2, 2);
362     assertEquals(ImmutableSet.of(), set.intersection(emptySet));
363     assertEquals(ImmutableSet.of(), emptySet.intersection(set));
364     assertEquals(
365         ImmutableSet.of(),
366         ContiguousSet.create(Range.closed(-5, -1), integers())
367             .intersection(ContiguousSet.create(Range.open(3, 64), integers())));
368   }
369 
testIntersection()370   public void testIntersection() {
371     ContiguousSet<Integer> set = ContiguousSet.create(Range.closed(1, 3), integers());
372     assertEquals(
373         ImmutableSet.of(1, 2, 3),
374         ContiguousSet.create(Range.open(-1, 4), integers()).intersection(set));
375     assertEquals(
376         ImmutableSet.of(1, 2, 3),
377         set.intersection(ContiguousSet.create(Range.open(-1, 4), integers())));
378     assertEquals(
379         ImmutableSet.of(3), set.intersection(ContiguousSet.create(Range.closed(3, 5), integers())));
380   }
381 
testAsList()382   public void testAsList() {
383     ImmutableList<Integer> list = ContiguousSet.create(Range.closed(1, 3), integers()).asList();
384     for (int i = 0; i < 3; i++) {
385       assertEquals(i + 1, list.get(i).intValue());
386     }
387     assertEquals(ImmutableList.of(1, 2, 3), ImmutableList.copyOf(list.iterator()));
388     assertEquals(ImmutableList.of(1, 2, 3), ImmutableList.copyOf(list.toArray(new Integer[0])));
389   }
390 
391   @GwtIncompatible // suite
392   public static class BuiltTests extends TestCase {
suite()393     public static Test suite() {
394       TestSuite suite = new TestSuite();
395 
396       suite.addTest(
397           NavigableSetTestSuiteBuilder.using(new ContiguousSetGenerator())
398               .named("Range.asSet")
399               .withFeatures(
400                   CollectionSize.ANY,
401                   KNOWN_ORDER,
402                   ALLOWS_NULL_QUERIES,
403                   NON_STANDARD_TOSTRING,
404                   RESTRICTS_ELEMENTS)
405               .suppressing(getHoleMethods())
406               .createTestSuite());
407 
408       suite.addTest(
409           NavigableSetTestSuiteBuilder.using(new ContiguousSetHeadsetGenerator())
410               .named("Range.asSet, headset")
411               .withFeatures(
412                   CollectionSize.ANY,
413                   KNOWN_ORDER,
414                   ALLOWS_NULL_QUERIES,
415                   NON_STANDARD_TOSTRING,
416                   RESTRICTS_ELEMENTS)
417               .suppressing(getHoleMethods())
418               .createTestSuite());
419 
420       suite.addTest(
421           NavigableSetTestSuiteBuilder.using(new ContiguousSetTailsetGenerator())
422               .named("Range.asSet, tailset")
423               .withFeatures(
424                   CollectionSize.ANY,
425                   KNOWN_ORDER,
426                   ALLOWS_NULL_QUERIES,
427                   NON_STANDARD_TOSTRING,
428                   RESTRICTS_ELEMENTS)
429               .suppressing(getHoleMethods())
430               .createTestSuite());
431 
432       suite.addTest(
433           NavigableSetTestSuiteBuilder.using(new ContiguousSetSubsetGenerator())
434               .named("Range.asSet, subset")
435               .withFeatures(
436                   CollectionSize.ANY,
437                   KNOWN_ORDER,
438                   ALLOWS_NULL_QUERIES,
439                   NON_STANDARD_TOSTRING,
440                   RESTRICTS_ELEMENTS)
441               .suppressing(getHoleMethods())
442               .createTestSuite());
443 
444       suite.addTest(
445           NavigableSetTestSuiteBuilder.using(new ContiguousSetDescendingGenerator())
446               .named("Range.asSet.descendingSet")
447               .withFeatures(
448                   CollectionSize.ANY,
449                   KNOWN_ORDER,
450                   ALLOWS_NULL_QUERIES,
451                   NON_STANDARD_TOSTRING,
452                   RESTRICTS_ELEMENTS)
453               .suppressing(getHoleMethods())
454               .createTestSuite());
455 
456       return suite;
457     }
458   }
459 }
460