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