13ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin/* 23ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Copyright (C) 2012 The Guava Authors 33ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 43ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 53ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * in compliance with the License. You may obtain a copy of the License at 63ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 73ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * http://www.apache.org/licenses/LICENSE-2.0 83ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 93ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Unless required by applicable law or agreed to in writing, software distributed under the License 103ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 113ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * or implied. See the License for the specific language governing permissions and limitations under 123ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * the License. 133ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 143ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 153ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinpackage com.google.common.collect; 163ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 173ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport static com.google.common.base.Preconditions.checkArgument; 183ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport static com.google.common.base.Preconditions.checkElementIndex; 193ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport static com.google.common.base.Preconditions.checkNotNull; 203ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 213ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport com.google.common.annotations.Beta; 223ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport com.google.common.annotations.GwtIncompatible; 233ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport com.google.common.collect.SortedLists.KeyAbsentBehavior; 243ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport com.google.common.collect.SortedLists.KeyPresentBehavior; 253ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 263ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport java.util.Map; 273ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport java.util.Map.Entry; 283ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport java.util.NoSuchElementException; 293ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 303ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport javax.annotation.Nullable; 313ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 323ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin/** 333ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * An immutable implementation of {@code RangeMap}, supporting all query operations efficiently. 343ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 353ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>Like all {@code RangeMap} implementations, this supports neither null keys nor null values. 363ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 373ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @author Louis Wasserman 383ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @since 14.0 393ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 403ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin@Beta 413ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin@GwtIncompatible("NavigableMap") 423ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinpublic class ImmutableRangeMap<K extends Comparable<?>, V> implements RangeMap<K, V> { 433ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 443ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin private static final ImmutableRangeMap<Comparable<?>, Object> EMPTY = 453ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin new ImmutableRangeMap<Comparable<?>, Object>( 463ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin ImmutableList.<Range<Comparable<?>>>of(), ImmutableList.of()); 473ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 483ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 493ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns an empty immutable range map. 503ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 513ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @SuppressWarnings("unchecked") 523ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of() { 533ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return (ImmutableRangeMap<K, V>) EMPTY; 543ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 553ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 563ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 573ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns an immutable range map mapping a single range to a single value. 583ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 593ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of( 603ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Range<K> range, V value) { 613ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new ImmutableRangeMap<K, V>(ImmutableList.of(range), ImmutableList.of(value)); 623ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 633ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 643ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @SuppressWarnings("unchecked") 653ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> copyOf( 663ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin RangeMap<K, ? extends V> rangeMap) { 673ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (rangeMap instanceof ImmutableRangeMap) { 683ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return (ImmutableRangeMap<K, V>) rangeMap; 693ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 703ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Map<Range<K>, ? extends V> map = rangeMap.asMapOfRanges(); 713ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin ImmutableList.Builder<Range<K>> rangesBuilder = new ImmutableList.Builder<Range<K>>(map.size()); 723ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(map.size()); 733ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin for (Entry<Range<K>, ? extends V> entry : map.entrySet()) { 743ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin rangesBuilder.add(entry.getKey()); 753ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin valuesBuilder.add(entry.getValue()); 763ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 773ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new ImmutableRangeMap<K, V>(rangesBuilder.build(), valuesBuilder.build()); 783ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 793ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 803ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 813ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns a new builder for an immutable range map. 823ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 833ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public static <K extends Comparable<?>, V> Builder<K, V> builder() { 843ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new Builder<K, V>(); 853ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 863ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 873ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 883ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * A builder for immutable range maps. Overlapping ranges are prohibited. 893ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 903ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public static final class Builder<K extends Comparable<?>, V> { 913ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin private final RangeSet<K> keyRanges; 923ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin private final RangeMap<K, V> rangeMap; 933ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 943ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public Builder() { 953ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin this.keyRanges = TreeRangeSet.create(); 963ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin this.rangeMap = TreeRangeMap.create(); 973ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 983ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 993ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1003ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Associates the specified range with the specified value. 1013ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1023ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @throws IllegalArgumentException if {@code range} overlaps with any other ranges inserted 1033ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * into this builder, or if {@code range} is empty 1043ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1053ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public Builder<K, V> put(Range<K> range, V value) { 1063ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin checkNotNull(range); 1073ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin checkNotNull(value); 1083ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin checkArgument(!range.isEmpty(), "Range must not be empty, but was %s", range); 1093ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (!keyRanges.complement().encloses(range)) { 1103ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin // it's an error case; we can afford an expensive lookup 1113ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin for (Entry<Range<K>, V> entry : rangeMap.asMapOfRanges().entrySet()) { 1123ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Range<K> key = entry.getKey(); 1133ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (key.isConnected(range) && !key.intersection(range).isEmpty()) { 1143ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin throw new IllegalArgumentException( 1153ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin "Overlapping ranges: range " + range + " overlaps with entry " + entry); 1163ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1173ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1183ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1193ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin keyRanges.add(range); 1203ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin rangeMap.put(range, value); 1213ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return this; 1223ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1233ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1243ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1253ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Copies all associations from the specified range map into this builder. 1263ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1273ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @throws IllegalArgumentException if any of the ranges in {@code rangeMap} overlap with ranges 1283ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * already in this builder 1293ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1303ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public Builder<K, V> putAll(RangeMap<K, ? extends V> rangeMap) { 1313ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin for (Entry<Range<K>, ? extends V> entry : rangeMap.asMapOfRanges().entrySet()) { 1323ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin put(entry.getKey(), entry.getValue()); 1333ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1343ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return this; 1353ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1363ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1373ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1383ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns an {@code ImmutableRangeMap} containing the associations previously added to this 1393ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * builder. 1403ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1413ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public ImmutableRangeMap<K, V> build() { 1423ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Map<Range<K>, V> map = rangeMap.asMapOfRanges(); 1433ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin ImmutableList.Builder<Range<K>> rangesBuilder = 1443ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin new ImmutableList.Builder<Range<K>>(map.size()); 1453ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(map.size()); 1463ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin for (Entry<Range<K>, V> entry : map.entrySet()) { 1473ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin rangesBuilder.add(entry.getKey()); 1483ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin valuesBuilder.add(entry.getValue()); 1493ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1503ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new ImmutableRangeMap<K, V>(rangesBuilder.build(), valuesBuilder.build()); 1513ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1523ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1533ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1543ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin private final ImmutableList<Range<K>> ranges; 1553ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin private final ImmutableList<V> values; 1563ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1573ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin ImmutableRangeMap(ImmutableList<Range<K>> ranges, ImmutableList<V> values) { 1583ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin this.ranges = ranges; 1593ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin this.values = values; 1603ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1613ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1623ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1633ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Nullable 1643ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public V get(K key) { 1653ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin int index = SortedLists.binarySearch(ranges, Range.<K>lowerBoundFn(), 1663ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Cut.belowValue(key), KeyPresentBehavior.ANY_PRESENT, KeyAbsentBehavior.NEXT_LOWER); 1673ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (index == -1) { 1683ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return null; 1693ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } else { 1703ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Range<K> range = ranges.get(index); 1713ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return range.contains(key) ? values.get(index) : null; 1723ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1733ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1743ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1753ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1763ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Nullable 1773ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public Map.Entry<Range<K>, V> getEntry(K key) { 1783ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin int index = SortedLists.binarySearch(ranges, Range.<K>lowerBoundFn(), 1793ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Cut.belowValue(key), KeyPresentBehavior.ANY_PRESENT, KeyAbsentBehavior.NEXT_LOWER); 1803ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (index == -1) { 1813ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return null; 1823ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } else { 1833ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Range<K> range = ranges.get(index); 1843ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return range.contains(key) ? Maps.immutableEntry(range, values.get(index)) : null; 1853ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1863ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1873ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1883ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1893ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public Range<K> span() { 1903ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (ranges.isEmpty()) { 1913ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin throw new NoSuchElementException(); 1923ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1933ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Range<K> firstRange = ranges.get(0); 1943ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Range<K> lastRange = ranges.get(ranges.size() - 1); 1953ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return Range.create(firstRange.lowerBound, lastRange.upperBound); 1963ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1973ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1983ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1993ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public void put(Range<K> range, V value) { 2003ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin throw new UnsupportedOperationException(); 2013ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2023ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 2033ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 2043ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public void putAll(RangeMap<K, V> rangeMap) { 2053ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin throw new UnsupportedOperationException(); 2063ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2073ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 2083ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 2093ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public void clear() { 2103ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin throw new UnsupportedOperationException(); 2113ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2123ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 2133ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 2143ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public void remove(Range<K> range) { 2153ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin throw new UnsupportedOperationException(); 2163ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2173ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 2183ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 2193ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public ImmutableMap<Range<K>, V> asMapOfRanges() { 2203ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (ranges.isEmpty()) { 2213ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return ImmutableMap.of(); 2223ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2233ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin RegularImmutableSortedSet<Range<K>> rangeSet = 2243ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin new RegularImmutableSortedSet<Range<K>>(ranges, Range.RANGE_LEX_ORDERING); 2253ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new RegularImmutableSortedMap<Range<K>, V>(rangeSet, values); 2263ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2273ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 2283ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 2293ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public ImmutableRangeMap<K, V> subRangeMap(final Range<K> range) { 2303ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (checkNotNull(range).isEmpty()) { 2313ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return ImmutableRangeMap.of(); 2323ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } else if (ranges.isEmpty() || range.encloses(span())) { 2333ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return this; 2343ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2353ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin int lowerIndex = SortedLists.binarySearch( 2363ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin ranges, Range.<K>upperBoundFn(), range.lowerBound, 2373ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin KeyPresentBehavior.FIRST_AFTER, KeyAbsentBehavior.NEXT_HIGHER); 2383ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin int upperIndex = SortedLists.binarySearch(ranges, 2393ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Range.<K>lowerBoundFn(), range.upperBound, 2403ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin KeyPresentBehavior.ANY_PRESENT, KeyAbsentBehavior.NEXT_HIGHER); 2413ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (lowerIndex >= upperIndex) { 2423ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return ImmutableRangeMap.of(); 2433ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2443ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin final int off = lowerIndex; 2453ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin final int len = upperIndex - lowerIndex; 2463ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin ImmutableList<Range<K>> subRanges = new ImmutableList<Range<K>>() { 2473ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 2483ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public int size() { 2493ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return len; 2503ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2513ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 2523ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 2533ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public Range<K> get(int index) { 2543ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin checkElementIndex(index, len); 2553ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (index == 0 || index == len - 1) { 2563ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return ranges.get(index + off).intersection(range); 2573ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } else { 2583ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return ranges.get(index + off); 2593ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2603ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2613ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 2623ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 2633ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin boolean isPartialView() { 2643ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return true; 2653ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2663ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin }; 2673ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin final ImmutableRangeMap<K, V> outer = this; 2683ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new ImmutableRangeMap<K, V>( 2693ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin subRanges, values.subList(lowerIndex, upperIndex)) { 2703ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 2713ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public ImmutableRangeMap<K, V> subRangeMap(Range<K> subRange) { 2723ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (range.isConnected(subRange)) { 2733ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return outer.subRangeMap(subRange.intersection(range)); 2743ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } else { 2753ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return ImmutableRangeMap.of(); 2763ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2773ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2783ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin }; 2793ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2803ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 2813ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 2823ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public int hashCode() { 2833ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return asMapOfRanges().hashCode(); 2843ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2853ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 2863ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 2873ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public boolean equals(@Nullable Object o) { 2883ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (o instanceof RangeMap) { 2893ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o; 2903ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return asMapOfRanges().equals(rangeMap.asMapOfRanges()); 2913ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2923ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return false; 2933ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2943ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 2953ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 2963ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public String toString() { 2973ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return asMapOfRanges().toString(); 2983ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 2993ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin} 300