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 15package com.google.common.collect; 16 17import static com.google.common.base.Preconditions.checkArgument; 18import static com.google.common.base.Preconditions.checkElementIndex; 19import static com.google.common.base.Preconditions.checkNotNull; 20 21import com.google.common.annotations.Beta; 22import com.google.common.annotations.GwtIncompatible; 23import com.google.common.collect.SortedLists.KeyAbsentBehavior; 24import com.google.common.collect.SortedLists.KeyPresentBehavior; 25 26import java.util.Map; 27import java.util.Map.Entry; 28import java.util.NoSuchElementException; 29 30import javax.annotation.Nullable; 31 32/** 33 * An immutable implementation of {@code RangeMap}, supporting all query operations efficiently. 34 * 35 * <p>Like all {@code RangeMap} implementations, this supports neither null keys nor null values. 36 * 37 * @author Louis Wasserman 38 * @since 14.0 39 */ 40@Beta 41@GwtIncompatible("NavigableMap") 42public class ImmutableRangeMap<K extends Comparable<?>, V> implements RangeMap<K, V> { 43 44 private static final ImmutableRangeMap<Comparable<?>, Object> EMPTY = 45 new ImmutableRangeMap<Comparable<?>, Object>( 46 ImmutableList.<Range<Comparable<?>>>of(), ImmutableList.of()); 47 48 /** 49 * Returns an empty immutable range map. 50 */ 51 @SuppressWarnings("unchecked") 52 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of() { 53 return (ImmutableRangeMap<K, V>) EMPTY; 54 } 55 56 /** 57 * Returns an immutable range map mapping a single range to a single value. 58 */ 59 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of( 60 Range<K> range, V value) { 61 return new ImmutableRangeMap<K, V>(ImmutableList.of(range), ImmutableList.of(value)); 62 } 63 64 @SuppressWarnings("unchecked") 65 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> copyOf( 66 RangeMap<K, ? extends V> rangeMap) { 67 if (rangeMap instanceof ImmutableRangeMap) { 68 return (ImmutableRangeMap<K, V>) rangeMap; 69 } 70 Map<Range<K>, ? extends V> map = rangeMap.asMapOfRanges(); 71 ImmutableList.Builder<Range<K>> rangesBuilder = new ImmutableList.Builder<Range<K>>(map.size()); 72 ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(map.size()); 73 for (Entry<Range<K>, ? extends V> entry : map.entrySet()) { 74 rangesBuilder.add(entry.getKey()); 75 valuesBuilder.add(entry.getValue()); 76 } 77 return new ImmutableRangeMap<K, V>(rangesBuilder.build(), valuesBuilder.build()); 78 } 79 80 /** 81 * Returns a new builder for an immutable range map. 82 */ 83 public static <K extends Comparable<?>, V> Builder<K, V> builder() { 84 return new Builder<K, V>(); 85 } 86 87 /** 88 * A builder for immutable range maps. Overlapping ranges are prohibited. 89 */ 90 public static final class Builder<K extends Comparable<?>, V> { 91 private final RangeSet<K> keyRanges; 92 private final RangeMap<K, V> rangeMap; 93 94 public Builder() { 95 this.keyRanges = TreeRangeSet.create(); 96 this.rangeMap = TreeRangeMap.create(); 97 } 98 99 /** 100 * Associates the specified range with the specified value. 101 * 102 * @throws IllegalArgumentException if {@code range} overlaps with any other ranges inserted 103 * into this builder, or if {@code range} is empty 104 */ 105 public Builder<K, V> put(Range<K> range, V value) { 106 checkNotNull(range); 107 checkNotNull(value); 108 checkArgument(!range.isEmpty(), "Range must not be empty, but was %s", range); 109 if (!keyRanges.complement().encloses(range)) { 110 // it's an error case; we can afford an expensive lookup 111 for (Entry<Range<K>, V> entry : rangeMap.asMapOfRanges().entrySet()) { 112 Range<K> key = entry.getKey(); 113 if (key.isConnected(range) && !key.intersection(range).isEmpty()) { 114 throw new IllegalArgumentException( 115 "Overlapping ranges: range " + range + " overlaps with entry " + entry); 116 } 117 } 118 } 119 keyRanges.add(range); 120 rangeMap.put(range, value); 121 return this; 122 } 123 124 /** 125 * Copies all associations from the specified range map into this builder. 126 * 127 * @throws IllegalArgumentException if any of the ranges in {@code rangeMap} overlap with ranges 128 * already in this builder 129 */ 130 public Builder<K, V> putAll(RangeMap<K, ? extends V> rangeMap) { 131 for (Entry<Range<K>, ? extends V> entry : rangeMap.asMapOfRanges().entrySet()) { 132 put(entry.getKey(), entry.getValue()); 133 } 134 return this; 135 } 136 137 /** 138 * Returns an {@code ImmutableRangeMap} containing the associations previously added to this 139 * builder. 140 */ 141 public ImmutableRangeMap<K, V> build() { 142 Map<Range<K>, V> map = rangeMap.asMapOfRanges(); 143 ImmutableList.Builder<Range<K>> rangesBuilder = 144 new ImmutableList.Builder<Range<K>>(map.size()); 145 ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(map.size()); 146 for (Entry<Range<K>, V> entry : map.entrySet()) { 147 rangesBuilder.add(entry.getKey()); 148 valuesBuilder.add(entry.getValue()); 149 } 150 return new ImmutableRangeMap<K, V>(rangesBuilder.build(), valuesBuilder.build()); 151 } 152 } 153 154 private final ImmutableList<Range<K>> ranges; 155 private final ImmutableList<V> values; 156 157 ImmutableRangeMap(ImmutableList<Range<K>> ranges, ImmutableList<V> values) { 158 this.ranges = ranges; 159 this.values = values; 160 } 161 162 @Override 163 @Nullable 164 public V get(K key) { 165 int index = SortedLists.binarySearch(ranges, Range.<K>lowerBoundFn(), 166 Cut.belowValue(key), KeyPresentBehavior.ANY_PRESENT, KeyAbsentBehavior.NEXT_LOWER); 167 if (index == -1) { 168 return null; 169 } else { 170 Range<K> range = ranges.get(index); 171 return range.contains(key) ? values.get(index) : null; 172 } 173 } 174 175 @Override 176 @Nullable 177 public Map.Entry<Range<K>, V> getEntry(K key) { 178 int index = SortedLists.binarySearch(ranges, Range.<K>lowerBoundFn(), 179 Cut.belowValue(key), KeyPresentBehavior.ANY_PRESENT, KeyAbsentBehavior.NEXT_LOWER); 180 if (index == -1) { 181 return null; 182 } else { 183 Range<K> range = ranges.get(index); 184 return range.contains(key) ? Maps.immutableEntry(range, values.get(index)) : null; 185 } 186 } 187 188 @Override 189 public Range<K> span() { 190 if (ranges.isEmpty()) { 191 throw new NoSuchElementException(); 192 } 193 Range<K> firstRange = ranges.get(0); 194 Range<K> lastRange = ranges.get(ranges.size() - 1); 195 return Range.create(firstRange.lowerBound, lastRange.upperBound); 196 } 197 198 @Override 199 public void put(Range<K> range, V value) { 200 throw new UnsupportedOperationException(); 201 } 202 203 @Override 204 public void putAll(RangeMap<K, V> rangeMap) { 205 throw new UnsupportedOperationException(); 206 } 207 208 @Override 209 public void clear() { 210 throw new UnsupportedOperationException(); 211 } 212 213 @Override 214 public void remove(Range<K> range) { 215 throw new UnsupportedOperationException(); 216 } 217 218 @Override 219 public ImmutableMap<Range<K>, V> asMapOfRanges() { 220 if (ranges.isEmpty()) { 221 return ImmutableMap.of(); 222 } 223 RegularImmutableSortedSet<Range<K>> rangeSet = 224 new RegularImmutableSortedSet<Range<K>>(ranges, Range.RANGE_LEX_ORDERING); 225 return new RegularImmutableSortedMap<Range<K>, V>(rangeSet, values); 226 } 227 228 @Override 229 public ImmutableRangeMap<K, V> subRangeMap(final Range<K> range) { 230 if (checkNotNull(range).isEmpty()) { 231 return ImmutableRangeMap.of(); 232 } else if (ranges.isEmpty() || range.encloses(span())) { 233 return this; 234 } 235 int lowerIndex = SortedLists.binarySearch( 236 ranges, Range.<K>upperBoundFn(), range.lowerBound, 237 KeyPresentBehavior.FIRST_AFTER, KeyAbsentBehavior.NEXT_HIGHER); 238 int upperIndex = SortedLists.binarySearch(ranges, 239 Range.<K>lowerBoundFn(), range.upperBound, 240 KeyPresentBehavior.ANY_PRESENT, KeyAbsentBehavior.NEXT_HIGHER); 241 if (lowerIndex >= upperIndex) { 242 return ImmutableRangeMap.of(); 243 } 244 final int off = lowerIndex; 245 final int len = upperIndex - lowerIndex; 246 ImmutableList<Range<K>> subRanges = new ImmutableList<Range<K>>() { 247 @Override 248 public int size() { 249 return len; 250 } 251 252 @Override 253 public Range<K> get(int index) { 254 checkElementIndex(index, len); 255 if (index == 0 || index == len - 1) { 256 return ranges.get(index + off).intersection(range); 257 } else { 258 return ranges.get(index + off); 259 } 260 } 261 262 @Override 263 boolean isPartialView() { 264 return true; 265 } 266 }; 267 final ImmutableRangeMap<K, V> outer = this; 268 return new ImmutableRangeMap<K, V>( 269 subRanges, values.subList(lowerIndex, upperIndex)) { 270 @Override 271 public ImmutableRangeMap<K, V> subRangeMap(Range<K> subRange) { 272 if (range.isConnected(subRange)) { 273 return outer.subRangeMap(subRange.intersection(range)); 274 } else { 275 return ImmutableRangeMap.of(); 276 } 277 } 278 }; 279 } 280 281 @Override 282 public int hashCode() { 283 return asMapOfRanges().hashCode(); 284 } 285 286 @Override 287 public boolean equals(@Nullable Object o) { 288 if (o instanceof RangeMap) { 289 RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o; 290 return asMapOfRanges().equals(rangeMap.asMapOfRanges()); 291 } 292 return false; 293 } 294 295 @Override 296 public String toString() { 297 return asMapOfRanges().toString(); 298 } 299} 300