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
15package com.google.common.collect;
16
17import static com.google.common.collect.BoundType.OPEN;
18import static com.google.common.collect.testing.Helpers.mapEntry;
19
20import com.google.common.annotations.GwtIncompatible;
21import com.google.common.collect.testing.MapTestSuiteBuilder;
22import com.google.common.collect.testing.SampleElements;
23import com.google.common.collect.testing.TestMapGenerator;
24import com.google.common.collect.testing.features.CollectionFeature;
25import com.google.common.collect.testing.features.CollectionSize;
26import com.google.common.collect.testing.features.MapFeature;
27
28import junit.framework.Test;
29import junit.framework.TestCase;
30import junit.framework.TestSuite;
31
32import java.util.List;
33import java.util.Map;
34import java.util.Map.Entry;
35import java.util.NoSuchElementException;
36
37/**
38 * Tests for {@code TreeRangeMap}.
39 *
40 * @author Louis Wasserman
41 */
42@GwtIncompatible("NavigableMap")
43public class TreeRangeMapTest extends TestCase {
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
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()) {
169        builder.add(Range.upTo(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            }
182            builder.add(Range.range(i, lowerType, j, upperType));
183          }
184        }
185      }
186    }
187    RANGES = builder.build();
188  }
189
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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