1 /*
2  * Copyright (C) 2012 The Guava Authors
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5  * in compliance with the License. You may obtain a copy of the License at
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software distributed under the License
10  * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11  * or implied. See the License for the specific language governing permissions and limitations under
12  * the License.
13  */
14 
15 package com.google.common.collect;
16 
17 import static com.google.common.collect.BoundType.OPEN;
18 
19 import com.google.common.annotations.GwtIncompatible;
20 
21 import junit.framework.TestCase;
22 
23 import java.util.Map;
24 import java.util.Map.Entry;
25 import java.util.NoSuchElementException;
26 
27 /**
28  * Tests for {@code ImmutableRangeMap}.
29  *
30  * @author Louis Wasserman
31  */
32 @GwtIncompatible("NavigableMap")
33 public class ImmutableRangeMapTest extends TestCase {
34   private static final ImmutableList<Range<Integer>> RANGES;
35   private static final int MIN_BOUND = 0;
36   private static final int MAX_BOUND = 10;
37   static {
38     ImmutableList.Builder<Range<Integer>> builder = ImmutableList.builder();
39 
all()40     builder.add(Range.<Integer>all());
41 
42     // Add one-ended ranges
43     for (int i = MIN_BOUND; i <= MAX_BOUND; i++) {
44       for (BoundType type : BoundType.values()) {
Range.upTo(i, type)45         builder.add(Range.upTo(i, type));
Range.downTo(i, type)46         builder.add(Range.downTo(i, type));
47       }
48     }
49 
50     // Add two-ended ranges
51     for (int i = MIN_BOUND; i <= MAX_BOUND; i++) {
52       for (int j = i + 1; j <= MAX_BOUND; j++) {
53         for (BoundType lowerType : BoundType.values()) {
54           for (BoundType upperType : BoundType.values()) {
55             if (i == j & lowerType == OPEN & upperType == OPEN) {
56               continue;
57             }
Range.range(i, lowerType, j, upperType)58             builder.add(Range.range(i, lowerType, j, upperType));
59           }
60         }
61       }
62     }
63     RANGES = builder.build();
64   }
65 
testBuilderRejectsEmptyRanges()66   public void testBuilderRejectsEmptyRanges() {
67     for (int i = MIN_BOUND; i <= MAX_BOUND; i++) {
68       ImmutableRangeMap.Builder<Integer, Integer> builder = ImmutableRangeMap.builder();
69       try {
70         builder.put(Range.closedOpen(i, i), 1);
71         fail("Expected IllegalArgumentException");
72       } catch (IllegalArgumentException expected) {
73         // success
74       }
75       try {
76         builder.put(Range.openClosed(i, i), 1);
77         fail("Expected IllegalArgumentException");
78       } catch (IllegalArgumentException expected) {
79       }
80     }
81   }
82 
testOverlapRejection()83   public void testOverlapRejection() {
84     for (Range<Integer> range1 : RANGES) {
85       for (Range<Integer> range2 : RANGES) {
86         boolean expectRejection =
87             range1.isConnected(range2) && !range1.intersection(range2).isEmpty();
88         ImmutableRangeMap.Builder<Integer, Integer> builder = ImmutableRangeMap.builder();
89         builder.put(range1, 1);
90         try {
91           builder.put(range2, 2);
92           assertFalse(expectRejection);
93         } catch (IllegalArgumentException e) {
94           assertTrue(expectRejection);
95         }
96       }
97     }
98   }
99 
testGet()100   public void testGet() {
101     for (Range<Integer> range1 : RANGES) {
102       for (Range<Integer> range2 : RANGES) {
103         if (!range1.isConnected(range2) || range1.intersection(range2).isEmpty()) {
104           ImmutableRangeMap<Integer, Integer> rangeMap =
105               ImmutableRangeMap.<Integer, Integer>builder().put(range1, 1).put(range2, 2).build();
106 
107           for (int i = MIN_BOUND; i <= MAX_BOUND; i++) {
108             Integer expectedValue = null;
109             if (range1.contains(i)) {
110               expectedValue = 1;
111             } else if (range2.contains(i)) {
112               expectedValue = 2;
113             }
114 
115             assertEquals(expectedValue, rangeMap.get(i));
116           }
117         }
118       }
119     }
120   }
121 
testSpanEmpty()122   public void testSpanEmpty() {
123     try {
124       ImmutableRangeMap.of().span();
125       fail("Expected NoSuchElementException");
126     } catch (NoSuchElementException expected) {
127     }
128   }
129 
testSpanSingleRange()130   public void testSpanSingleRange() {
131     for (Range<Integer> range : RANGES) {
132       RangeMap<Integer, Integer> rangemap =
133           ImmutableRangeMap.<Integer, Integer>builder().put(range, 1).build();
134       assertEquals(range, rangemap.span());
135     }
136   }
137 
testSpanTwoRanges()138   public void testSpanTwoRanges() {
139     for (Range<Integer> range1 : RANGES) {
140       for (Range<Integer> range2 : RANGES) {
141         if (!range1.isConnected(range2) || range1.intersection(range2).isEmpty()) {
142           RangeMap<Integer, Integer> rangemap =
143               ImmutableRangeMap.<Integer, Integer>builder().put(range1, 1).put(range2, 2).build();
144           assertEquals(range1.span(range2), rangemap.span());
145         }
146       }
147     }
148   }
149 
testGetEntry()150   public void testGetEntry() {
151     for (Range<Integer> range1 : RANGES) {
152       for (Range<Integer> range2 : RANGES) {
153         if (!range1.isConnected(range2) || range1.intersection(range2).isEmpty()) {
154           ImmutableRangeMap<Integer, Integer> rangeMap =
155               ImmutableRangeMap.<Integer, Integer>builder().put(range1, 1).put(range2, 2).build();
156 
157           for (int i = MIN_BOUND; i <= MAX_BOUND; i++) {
158             Entry<Range<Integer>, Integer> expectedEntry = null;
159             if (range1.contains(i)) {
160               expectedEntry = Maps.immutableEntry(range1, 1);
161             } else if (range2.contains(i)) {
162               expectedEntry = Maps.immutableEntry(range2, 2);
163             }
164 
165             assertEquals(expectedEntry, rangeMap.getEntry(i));
166           }
167         }
168       }
169     }
170   }
171 
testGetLargeRangeMap()172   public void testGetLargeRangeMap() {
173     ImmutableRangeMap.Builder<Integer, Integer> builder = ImmutableRangeMap.builder();
174     for (int i = 0; i < 100; i++) {
175       builder.put(Range.closedOpen(i, i + 1), i);
176     }
177     ImmutableRangeMap<Integer, Integer> map = builder.build();
178     for (int i = 0; i < 100; i++) {
179       assertEquals(Integer.valueOf(i), map.get(i));
180     }
181   }
182 
testAsMapOfRanges()183   public void testAsMapOfRanges() {
184     for (Range<Integer> range1 : RANGES) {
185       for (Range<Integer> range2 : RANGES) {
186         if (!range1.isConnected(range2) || range1.intersection(range2).isEmpty()) {
187           ImmutableRangeMap<Integer, Integer> rangeMap =
188               ImmutableRangeMap.<Integer, Integer>builder().put(range1, 1).put(range2, 2).build();
189 
190           ImmutableMap<Range<Integer>, Integer> expectedAsMap =
191               ImmutableMap.of(range1, 1, range2, 2);
192           ImmutableMap<Range<Integer>, Integer> asMap = rangeMap.asMapOfRanges();
193           assertEquals(expectedAsMap, asMap);
194 
195           for (Range<Integer> query : RANGES) {
196             assertEquals(expectedAsMap.get(query), asMap.get(query));
197           }
198         }
199       }
200     }
201   }
202 
testSubRangeMap()203   public void testSubRangeMap() {
204     for (Range<Integer> range1 : RANGES) {
205       for (Range<Integer> range2 : RANGES) {
206         if (!range1.isConnected(range2) || range1.intersection(range2).isEmpty()) {
207           for (Range<Integer> subRange : RANGES) {
208             ImmutableRangeMap<Integer, Integer> rangeMap =
209                 ImmutableRangeMap.<Integer, Integer>builder()
210                   .put(range1, 1).put(range2, 2).build();
211 
212             ImmutableRangeMap.Builder<Integer, Integer> expectedBuilder =
213                 ImmutableRangeMap.builder();
214             for (Map.Entry<Range<Integer>, Integer> entry : rangeMap.asMapOfRanges().entrySet()) {
215               if (entry.getKey().isConnected(subRange)
216                   && !entry.getKey().intersection(subRange).isEmpty()) {
217                 expectedBuilder.put(entry.getKey().intersection(subRange), entry.getValue());
218               }
219             }
220 
221             ImmutableRangeMap<Integer, Integer> expected = expectedBuilder.build();
222             assertEquals(expected, rangeMap.subRangeMap(subRange));
223           }
224         }
225       }
226     }
227   }
228 }
229