• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2011 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 import static com.google.common.collect.testing.Helpers.mapEntry;
19 
20 import com.google.common.annotations.GwtIncompatible;
21 import com.google.common.collect.testing.MapTestSuiteBuilder;
22 import com.google.common.collect.testing.SampleElements;
23 import com.google.common.collect.testing.TestMapGenerator;
24 import com.google.common.collect.testing.features.CollectionFeature;
25 import com.google.common.collect.testing.features.CollectionSize;
26 import com.google.common.collect.testing.features.MapFeature;
27 
28 import junit.framework.Test;
29 import junit.framework.TestCase;
30 import junit.framework.TestSuite;
31 
32 import java.util.List;
33 import java.util.Map;
34 import java.util.Map.Entry;
35 import java.util.NoSuchElementException;
36 
37 /**
38  * Tests for {@code TreeRangeMap}.
39  *
40  * @author Louis Wasserman
41  */
42 @GwtIncompatible("NavigableMap")
43 public class TreeRangeMapTest extends TestCase {
suite()44   public static Test suite() {
45     TestSuite suite = new TestSuite();
46     suite.addTestSuite(TreeRangeMapTest.class);
47     suite.addTest(MapTestSuiteBuilder.using(new TestMapGenerator<Range<Integer>, String>() {
48         @Override
49         public SampleElements<Entry<Range<Integer>, String>> samples() {
50           return new SampleElements<Entry<Range<Integer>, String>>(
51               mapEntry(Range.singleton(0), "banana"),
52               mapEntry(Range.closedOpen(3, 5), "frisbee"),
53               mapEntry(Range.atMost(-1), "fruitcake"),
54               mapEntry(Range.open(10, 15), "elephant"),
55               mapEntry(Range.closed(20, 22), "umbrella"));
56         }
57 
58         @Override
59         public Map<Range<Integer>, String> create(Object... elements) {
60           RangeMap<Integer, String> rangeMap = TreeRangeMap.create();
61           for (Object o : elements) {
62             @SuppressWarnings("unchecked")
63             Entry<Range<Integer>, String> entry = (Entry<Range<Integer>, String>) o;
64             rangeMap.put(entry.getKey(), entry.getValue());
65           }
66           return rangeMap.asMapOfRanges();
67         }
68 
69         @SuppressWarnings("unchecked")
70         @Override
71         public Entry<Range<Integer>, String>[] createArray(int length) {
72           return new Entry[length];
73         }
74 
75         @Override
76         public Iterable<Entry<Range<Integer>, String>> order(
77             List<Entry<Range<Integer>, String>> insertionOrder) {
78           return Range.RANGE_LEX_ORDERING.<Range<Integer>>onKeys()
79               .sortedCopy(insertionOrder);
80         }
81 
82         @SuppressWarnings("unchecked")
83         @Override
84         public Range<Integer>[] createKeyArray(int length) {
85           return new Range[length];
86         }
87 
88         @Override
89         public String[] createValueArray(int length) {
90           return new String[length];
91         }
92       })
93       .named("TreeRangeMap.asMapOfRanges")
94       .withFeatures(
95           CollectionSize.ANY,
96           MapFeature.SUPPORTS_REMOVE,
97           MapFeature.ALLOWS_ANY_NULL_QUERIES,
98           CollectionFeature.KNOWN_ORDER,
99           CollectionFeature.SUPPORTS_ITERATOR_REMOVE)
100       .createTestSuite());
101 
102     suite.addTest(MapTestSuiteBuilder.using(new TestMapGenerator<Range<Integer>, String>() {
103         @Override
104         public SampleElements<Entry<Range<Integer>, String>> samples() {
105           return new SampleElements<Entry<Range<Integer>, String>>(
106               mapEntry(Range.singleton(0), "banana"),
107               mapEntry(Range.closedOpen(3, 5), "frisbee"),
108               mapEntry(Range.atMost(-1), "fruitcake"),
109               mapEntry(Range.open(10, 15), "elephant"),
110               mapEntry(Range.closed(20, 22), "umbrella"));
111         }
112 
113         @Override
114         public Map<Range<Integer>, String> create(Object... elements) {
115           RangeMap<Integer, String> rangeMap = TreeRangeMap.create();
116           for (Object o : elements) {
117             @SuppressWarnings("unchecked")
118             Entry<Range<Integer>, String> entry = (Entry<Range<Integer>, String>) o;
119             rangeMap.put(entry.getKey(), entry.getValue());
120           }
121           return rangeMap.subRangeMap(Range.atMost(22)).asMapOfRanges();
122         }
123 
124         @SuppressWarnings("unchecked")
125         @Override
126         public Entry<Range<Integer>, String>[] createArray(int length) {
127           return new Entry[length];
128         }
129 
130         @Override
131         public Iterable<Entry<Range<Integer>, String>> order(
132             List<Entry<Range<Integer>, String>> insertionOrder) {
133           return Range.RANGE_LEX_ORDERING.<Range<Integer>>onKeys()
134               .sortedCopy(insertionOrder);
135         }
136 
137         @SuppressWarnings("unchecked")
138         @Override
139         public Range<Integer>[] createKeyArray(int length) {
140           return new Range[length];
141         }
142 
143         @Override
144         public String[] createValueArray(int length) {
145           return new String[length];
146         }
147       })
148       .named("TreeRangeMap.subRangeMap.asMapOfRanges")
149       .withFeatures(
150           CollectionSize.ANY,
151           MapFeature.SUPPORTS_REMOVE,
152           MapFeature.ALLOWS_ANY_NULL_QUERIES,
153           CollectionFeature.KNOWN_ORDER)
154       .createTestSuite());
155     return suite;
156   }
157 
158   private static final ImmutableList<Range<Integer>> RANGES;
159   private static final int MIN_BOUND = -2;
160   private static final int MAX_BOUND = 2;
161   static {
162     ImmutableList.Builder<Range<Integer>> builder = ImmutableList.builder();
163 
all()164     builder.add(Range.<Integer>all());
165 
166     // Add one-ended ranges
167     for (int i = MIN_BOUND; i <= MAX_BOUND; i++) {
168       for (BoundType type : BoundType.values()) {
Range.upTo(i, type)169         builder.add(Range.upTo(i, type));
Range.downTo(i, type)170         builder.add(Range.downTo(i, type));
171       }
172     }
173 
174     // Add two-ended ranges
175     for (int i = MIN_BOUND; i <= MAX_BOUND; i++) {
176       for (int j = i; j <= MAX_BOUND; j++) {
177         for (BoundType lowerType : BoundType.values()) {
178           for (BoundType upperType : BoundType.values()) {
179             if (i == j & lowerType == OPEN & upperType == OPEN) {
180               continue;
181             }
Range.range(i, lowerType, j, upperType)182             builder.add(Range.range(i, lowerType, j, upperType));
183           }
184         }
185       }
186     }
187     RANGES = builder.build();
188   }
189 
testSpanSingleRange()190   public void testSpanSingleRange() {
191     for (Range<Integer> range : RANGES) {
192       RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
193       rangeMap.put(range, 1);
194 
195       try {
196         assertEquals(range, rangeMap.span());
197         assertFalse(range.isEmpty());
198       } catch (NoSuchElementException e) {
199         assertTrue(range.isEmpty());
200       }
201     }
202   }
203 
testSpanTwoRanges()204   public void testSpanTwoRanges() {
205     for (Range<Integer> range1 : RANGES) {
206       for (Range<Integer> range2 : RANGES) {
207         RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
208         rangeMap.put(range1, 1);
209         rangeMap.put(range2, 2);
210 
211         Range<Integer> expected;
212         if (range1.isEmpty()) {
213           if (range2.isEmpty()) {
214             expected = null;
215           } else {
216             expected = range2;
217           }
218         } else {
219           if (range2.isEmpty()) {
220             expected = range1;
221           } else {
222             expected = range1.span(range2);
223           }
224         }
225 
226         try {
227           assertEquals(expected, rangeMap.span());
228           assertNotNull(expected);
229         } catch (NoSuchElementException e) {
230           assertNull(expected);
231         }
232       }
233     }
234   }
235 
testAllRangesAlone()236   public void testAllRangesAlone() {
237     for (Range<Integer> range : RANGES) {
238       Map<Integer, Integer> model = Maps.newHashMap();
239       putModel(model, range, 1);
240       RangeMap<Integer, Integer> test = TreeRangeMap.create();
241       test.put(range, 1);
242       verify(model, test);
243     }
244   }
245 
testAllRangePairs()246   public void testAllRangePairs() {
247     for (Range<Integer> range1 : RANGES) {
248       for (Range<Integer> range2 : RANGES) {
249         Map<Integer, Integer> model = Maps.newHashMap();
250         putModel(model, range1, 1);
251         putModel(model, range2, 2);
252         RangeMap<Integer, Integer> test = TreeRangeMap.create();
253         test.put(range1, 1);
254         test.put(range2, 2);
255         verify(model, test);
256       }
257     }
258   }
259 
testAllRangeTriples()260   public void testAllRangeTriples() {
261     for (Range<Integer> range1 : RANGES) {
262       for (Range<Integer> range2 : RANGES) {
263         for (Range<Integer> range3 : RANGES) {
264           Map<Integer, Integer> model = Maps.newHashMap();
265           putModel(model, range1, 1);
266           putModel(model, range2, 2);
267           putModel(model, range3, 3);
268           RangeMap<Integer, Integer> test = TreeRangeMap.create();
269           test.put(range1, 1);
270           test.put(range2, 2);
271           test.put(range3, 3);
272           verify(model, test);
273         }
274       }
275     }
276   }
277 
testPutAll()278   public void testPutAll() {
279     for (Range<Integer> range1 : RANGES) {
280       for (Range<Integer> range2 : RANGES) {
281         for (Range<Integer> range3 : RANGES) {
282           Map<Integer, Integer> model = Maps.newHashMap();
283           putModel(model, range1, 1);
284           putModel(model, range2, 2);
285           putModel(model, range3, 3);
286           RangeMap<Integer, Integer> test = TreeRangeMap.create();
287           RangeMap<Integer, Integer> test2 = TreeRangeMap.create();
288           // put range2 and range3 into test2, and then put test2 into test
289           test.put(range1, 1);
290           test2.put(range2, 2);
291           test2.put(range3, 3);
292           test.putAll(test2);
293           verify(model, test);
294         }
295       }
296     }
297   }
298 
testPutAndRemove()299   public void testPutAndRemove() {
300     for (Range<Integer> rangeToPut : RANGES) {
301       for (Range<Integer> rangeToRemove : RANGES) {
302         Map<Integer, Integer> model = Maps.newHashMap();
303         putModel(model, rangeToPut, 1);
304         removeModel(model, rangeToRemove);
305         RangeMap<Integer, Integer> test = TreeRangeMap.create();
306         test.put(rangeToPut, 1);
307         test.remove(rangeToRemove);
308         verify(model, test);
309       }
310     }
311   }
312 
testPutTwoAndRemove()313   public void testPutTwoAndRemove() {
314     for (Range<Integer> rangeToPut1 : RANGES) {
315       for (Range<Integer> rangeToPut2 : RANGES) {
316         for (Range<Integer> rangeToRemove : RANGES) {
317           Map<Integer, Integer> model = Maps.newHashMap();
318           putModel(model, rangeToPut1, 1);
319           putModel(model, rangeToPut2, 2);
320           removeModel(model, rangeToRemove);
321           RangeMap<Integer, Integer> test = TreeRangeMap.create();
322           test.put(rangeToPut1, 1);
323           test.put(rangeToPut2, 2);
324           test.remove(rangeToRemove);
325           verify(model, test);
326         }
327       }
328     }
329   }
330 
testSubRangeMapExhaustive()331   public void testSubRangeMapExhaustive() {
332     for (Range<Integer> range1 : RANGES) {
333       for (Range<Integer> range2 : RANGES) {
334         RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
335         rangeMap.put(range1, 1);
336         rangeMap.put(range2, 2);
337 
338         for (Range<Integer> subRange : RANGES) {
339           RangeMap<Integer, Integer> expected = TreeRangeMap.create();
340           for (Map.Entry<Range<Integer>, Integer> entry : rangeMap.asMapOfRanges().entrySet()) {
341             if (entry.getKey().isConnected(subRange)) {
342               expected.put(entry.getKey().intersection(subRange), entry.getValue());
343             }
344           }
345           RangeMap<Integer, Integer> subRangeMap = rangeMap.subRangeMap(subRange);
346           assertEquals(expected, subRangeMap);
347           assertEquals(expected.asMapOfRanges(), subRangeMap.asMapOfRanges());
348 
349           if (!expected.asMapOfRanges().isEmpty()) {
350             assertEquals(expected.span(), subRangeMap.span());
351           }
352 
353           for (int i = MIN_BOUND; i <= MAX_BOUND; i++) {
354             assertEquals(expected.get(i), subRangeMap.get(i));
355           }
356 
357           for (Range<Integer> query : RANGES) {
358             assertEquals(
359                 expected.asMapOfRanges().get(query),
360                 subRangeMap.asMapOfRanges().get(query));
361           }
362         }
363       }
364     }
365   }
366 
testSubSubRangeMap()367   public void testSubSubRangeMap() {
368     RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
369     rangeMap.put(Range.open(3, 7), 1);
370     rangeMap.put(Range.closed(9, 10), 2);
371     rangeMap.put(Range.closed(12, 16), 3);
372     RangeMap<Integer, Integer> sub1 = rangeMap.subRangeMap(Range.closed(5, 11));
373     assertEquals(ImmutableMap.of(Range.closedOpen(5, 7), 1, Range.closed(9, 10), 2),
374         sub1.asMapOfRanges());
375     RangeMap<Integer, Integer> sub2 = sub1.subRangeMap(Range.open(6, 15));
376     assertEquals(ImmutableMap.of(Range.open(6, 7), 1, Range.closed(9, 10), 2),
377         sub2.asMapOfRanges());
378   }
379 
testSubRangeMapPut()380   public void testSubRangeMapPut() {
381     RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
382     rangeMap.put(Range.open(3, 7), 1);
383     rangeMap.put(Range.closed(9, 10), 2);
384     rangeMap.put(Range.closed(12, 16), 3);
385     RangeMap<Integer, Integer> sub = rangeMap.subRangeMap(Range.closed(5, 11));
386     assertEquals(ImmutableMap.of(Range.closedOpen(5, 7), 1, Range.closed(9, 10), 2),
387         sub.asMapOfRanges());
388     sub.put(Range.closed(7, 9), 4);
389     assertEquals(
390         ImmutableMap.of(
391             Range.closedOpen(5, 7), 1, Range.closed(7, 9), 4, Range.openClosed(9, 10), 2),
392         sub.asMapOfRanges());
393     assertEquals(
394         ImmutableMap.of(Range.open(3, 7), 1, Range.closed(7, 9), 4, Range.openClosed(9, 10), 2,
395             Range.closed(12, 16), 3),
396         rangeMap.asMapOfRanges());
397 
398     try {
399       sub.put(Range.open(9, 12), 5);
400       fail("Expected IllegalArgumentException");
401     } catch (IllegalArgumentException expected) {
402     }
403 
404     sub = sub.subRangeMap(Range.closedOpen(5, 5));
405     sub.put(Range.closedOpen(5, 5), 6); // should be a no-op
406     assertEquals(
407         ImmutableMap.of(Range.open(3, 7), 1, Range.closed(7, 9), 4, Range.openClosed(9, 10), 2,
408             Range.closed(12, 16), 3),
409         rangeMap.asMapOfRanges());
410   }
411 
testSubRangeMapRemove()412   public void testSubRangeMapRemove() {
413     RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
414     rangeMap.put(Range.open(3, 7), 1);
415     rangeMap.put(Range.closed(9, 10), 2);
416     rangeMap.put(Range.closed(12, 16), 3);
417     RangeMap<Integer, Integer> sub = rangeMap.subRangeMap(Range.closed(5, 11));
418     assertEquals(ImmutableMap.of(Range.closedOpen(5, 7), 1, Range.closed(9, 10), 2),
419         sub.asMapOfRanges());
420     sub.remove(Range.closed(7, 9));
421     assertEquals(
422         ImmutableMap.of(Range.closedOpen(5, 7), 1, Range.openClosed(9, 10), 2),
423         sub.asMapOfRanges());
424     assertEquals(
425         ImmutableMap.of(Range.open(3, 7), 1, Range.openClosed(9, 10), 2, Range.closed(12, 16), 3),
426         rangeMap.asMapOfRanges());
427 
428     sub.remove(Range.closed(3, 9));
429     assertEquals(
430         ImmutableMap.of(Range.openClosed(9, 10), 2),
431         sub.asMapOfRanges());
432     assertEquals(
433         ImmutableMap.of(Range.open(3, 5), 1, Range.openClosed(9, 10), 2, Range.closed(12, 16), 3),
434         rangeMap.asMapOfRanges());
435   }
436 
testSubRangeMapClear()437   public void testSubRangeMapClear() {
438     RangeMap<Integer, Integer> rangeMap = TreeRangeMap.create();
439     rangeMap.put(Range.open(3, 7), 1);
440     rangeMap.put(Range.closed(9, 10), 2);
441     rangeMap.put(Range.closed(12, 16), 3);
442     RangeMap<Integer, Integer> sub = rangeMap.subRangeMap(Range.closed(5, 11));
443     sub.clear();
444     assertEquals(
445         ImmutableMap.of(Range.open(3, 5), 1, Range.closed(12, 16), 3),
446         rangeMap.asMapOfRanges());
447   }
448 
verify(Map<Integer, Integer> model, RangeMap<Integer, Integer> test)449   private void verify(Map<Integer, Integer> model, RangeMap<Integer, Integer> test) {
450     for (int i = MIN_BOUND - 1; i <= MAX_BOUND + 1; i++) {
451       assertEquals(model.get(i), test.get(i));
452 
453       Map.Entry<Range<Integer>, Integer> entry = test.getEntry(i);
454       assertEquals(model.containsKey(i), entry != null);
455       if (entry != null) {
456         assertTrue(test.asMapOfRanges().entrySet().contains(entry));
457       }
458     }
459     for (Range<Integer> range : test.asMapOfRanges().keySet()) {
460       assertFalse(range.isEmpty());
461     }
462   }
463 
putModel(Map<Integer, Integer> model, Range<Integer> range, int value)464   private void putModel(Map<Integer, Integer> model, Range<Integer> range, int value) {
465     for (int i = MIN_BOUND - 1; i <= MAX_BOUND + 1; i++) {
466       if (range.contains(i)) {
467         model.put(i, value);
468       }
469     }
470   }
471 
removeModel(Map<Integer, Integer> model, Range<Integer> range)472   private void removeModel(Map<Integer, Integer> model, Range<Integer> range) {
473     for (int i = MIN_BOUND - 1; i <= MAX_BOUND + 1; i++) {
474       if (range.contains(i)) {
475         model.remove(i);
476       }
477     }
478   }
479 }
480