001/* 002 * Copyright (C) 2012 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 005 * in compliance with the License. You may obtain a copy of the License at 006 * 007 * http://www.apache.org/licenses/LICENSE-2.0 008 * 009 * Unless required by applicable law or agreed to in writing, software distributed under the License 010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 011 * or implied. See the License for the specific language governing permissions and limitations under 012 * the License. 013 */ 014 015package com.google.common.collect; 016 017import static com.google.common.base.Preconditions.checkArgument; 018import static com.google.common.base.Preconditions.checkElementIndex; 019import static com.google.common.base.Preconditions.checkNotNull; 020 021import com.google.common.annotations.GwtIncompatible; 022import com.google.common.annotations.J2ktIncompatible; 023import com.google.common.collect.SortedLists.KeyAbsentBehavior; 024import com.google.common.collect.SortedLists.KeyPresentBehavior; 025import com.google.errorprone.annotations.CanIgnoreReturnValue; 026import com.google.errorprone.annotations.DoNotCall; 027import com.google.errorprone.annotations.DoNotMock; 028import java.io.InvalidObjectException; 029import java.io.ObjectInputStream; 030import java.io.Serializable; 031import java.util.Collections; 032import java.util.List; 033import java.util.Map; 034import java.util.Map.Entry; 035import java.util.NoSuchElementException; 036import java.util.function.BiFunction; 037import java.util.function.Function; 038import java.util.stream.Collector; 039import javax.annotation.CheckForNull; 040import org.checkerframework.checker.nullness.qual.Nullable; 041 042/** 043 * A {@link RangeMap} whose contents will never change, with many other important properties 044 * detailed at {@link ImmutableCollection}. 045 * 046 * @author Louis Wasserman 047 * @since 14.0 048 */ 049@GwtIncompatible // NavigableMap 050@ElementTypesAreNonnullByDefault 051public class ImmutableRangeMap<K extends Comparable<?>, V> implements RangeMap<K, V>, Serializable { 052 053 private static final ImmutableRangeMap<Comparable<?>, Object> EMPTY = 054 new ImmutableRangeMap<>(ImmutableList.<Range<Comparable<?>>>of(), ImmutableList.of()); 055 056 /** 057 * Returns a {@code Collector} that accumulates the input elements into a new {@code 058 * ImmutableRangeMap}. As in {@link Builder}, overlapping ranges are not permitted. 059 * 060 * @since 23.1 061 */ 062 public static <T extends @Nullable Object, K extends Comparable<? super K>, V> 063 Collector<T, ?, ImmutableRangeMap<K, V>> toImmutableRangeMap( 064 Function<? super T, Range<K>> keyFunction, 065 Function<? super T, ? extends V> valueFunction) { 066 return CollectCollectors.toImmutableRangeMap(keyFunction, valueFunction); 067 } 068 069 /** 070 * Returns an empty immutable range map. 071 * 072 * <p><b>Performance note:</b> the instance returned is a singleton. 073 */ 074 @SuppressWarnings("unchecked") 075 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of() { 076 return (ImmutableRangeMap<K, V>) EMPTY; 077 } 078 079 /** Returns an immutable range map mapping a single range to a single value. */ 080 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of(Range<K> range, V value) { 081 return new ImmutableRangeMap<>(ImmutableList.of(range), ImmutableList.of(value)); 082 } 083 084 @SuppressWarnings("unchecked") 085 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> copyOf( 086 RangeMap<K, ? extends V> rangeMap) { 087 if (rangeMap instanceof ImmutableRangeMap) { 088 return (ImmutableRangeMap<K, V>) rangeMap; 089 } 090 Map<Range<K>, ? extends V> map = rangeMap.asMapOfRanges(); 091 ImmutableList.Builder<Range<K>> rangesBuilder = new ImmutableList.Builder<>(map.size()); 092 ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(map.size()); 093 for (Entry<Range<K>, ? extends V> entry : map.entrySet()) { 094 rangesBuilder.add(entry.getKey()); 095 valuesBuilder.add(entry.getValue()); 096 } 097 return new ImmutableRangeMap<>(rangesBuilder.build(), valuesBuilder.build()); 098 } 099 100 /** Returns a new builder for an immutable range map. */ 101 public static <K extends Comparable<?>, V> Builder<K, V> builder() { 102 return new Builder<>(); 103 } 104 105 /** 106 * A builder for immutable range maps. Overlapping ranges are prohibited. 107 * 108 * @since 14.0 109 */ 110 @DoNotMock 111 public static final class Builder<K extends Comparable<?>, V> { 112 private final List<Entry<Range<K>, V>> entries; 113 114 public Builder() { 115 this.entries = Lists.newArrayList(); 116 } 117 118 /** 119 * Associates the specified range with the specified value. 120 * 121 * @throws IllegalArgumentException if {@code range} is empty 122 */ 123 @CanIgnoreReturnValue 124 public Builder<K, V> put(Range<K> range, V value) { 125 checkNotNull(range); 126 checkNotNull(value); 127 checkArgument(!range.isEmpty(), "Range must not be empty, but was %s", range); 128 entries.add(Maps.immutableEntry(range, value)); 129 return this; 130 } 131 132 /** Copies all associations from the specified range map into this builder. */ 133 @CanIgnoreReturnValue 134 public Builder<K, V> putAll(RangeMap<K, ? extends V> rangeMap) { 135 for (Entry<Range<K>, ? extends V> entry : rangeMap.asMapOfRanges().entrySet()) { 136 put(entry.getKey(), entry.getValue()); 137 } 138 return this; 139 } 140 141 @CanIgnoreReturnValue 142 Builder<K, V> combine(Builder<K, V> builder) { 143 entries.addAll(builder.entries); 144 return this; 145 } 146 147 /** 148 * Returns an {@code ImmutableRangeMap} containing the associations previously added to this 149 * builder. 150 * 151 * @throws IllegalArgumentException if any two ranges inserted into this builder overlap 152 */ 153 public ImmutableRangeMap<K, V> build() { 154 Collections.sort(entries, Range.<K>rangeLexOrdering().onKeys()); 155 ImmutableList.Builder<Range<K>> rangesBuilder = new ImmutableList.Builder<>(entries.size()); 156 ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(entries.size()); 157 for (int i = 0; i < entries.size(); i++) { 158 Range<K> range = entries.get(i).getKey(); 159 if (i > 0) { 160 Range<K> prevRange = entries.get(i - 1).getKey(); 161 if (range.isConnected(prevRange) && !range.intersection(prevRange).isEmpty()) { 162 throw new IllegalArgumentException( 163 "Overlapping ranges: range " + prevRange + " overlaps with entry " + range); 164 } 165 } 166 rangesBuilder.add(range); 167 valuesBuilder.add(entries.get(i).getValue()); 168 } 169 return new ImmutableRangeMap<>(rangesBuilder.build(), valuesBuilder.build()); 170 } 171 } 172 173 private final transient ImmutableList<Range<K>> ranges; 174 private final transient ImmutableList<V> values; 175 176 ImmutableRangeMap(ImmutableList<Range<K>> ranges, ImmutableList<V> values) { 177 this.ranges = ranges; 178 this.values = values; 179 } 180 181 @Override 182 @CheckForNull 183 public V get(K key) { 184 int index = 185 SortedLists.binarySearch( 186 ranges, 187 Range.<K>lowerBoundFn(), 188 Cut.belowValue(key), 189 KeyPresentBehavior.ANY_PRESENT, 190 KeyAbsentBehavior.NEXT_LOWER); 191 if (index == -1) { 192 return null; 193 } else { 194 Range<K> range = ranges.get(index); 195 return range.contains(key) ? values.get(index) : null; 196 } 197 } 198 199 @Override 200 @CheckForNull 201 public Entry<Range<K>, V> getEntry(K key) { 202 int index = 203 SortedLists.binarySearch( 204 ranges, 205 Range.<K>lowerBoundFn(), 206 Cut.belowValue(key), 207 KeyPresentBehavior.ANY_PRESENT, 208 KeyAbsentBehavior.NEXT_LOWER); 209 if (index == -1) { 210 return null; 211 } else { 212 Range<K> range = ranges.get(index); 213 return range.contains(key) ? Maps.immutableEntry(range, values.get(index)) : null; 214 } 215 } 216 217 @Override 218 public Range<K> span() { 219 if (ranges.isEmpty()) { 220 throw new NoSuchElementException(); 221 } 222 Range<K> firstRange = ranges.get(0); 223 Range<K> lastRange = ranges.get(ranges.size() - 1); 224 return Range.create(firstRange.lowerBound, lastRange.upperBound); 225 } 226 227 /** 228 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified. 229 * 230 * @throws UnsupportedOperationException always 231 * @deprecated Unsupported operation. 232 */ 233 @Deprecated 234 @Override 235 @DoNotCall("Always throws UnsupportedOperationException") 236 public final void put(Range<K> range, V value) { 237 throw new UnsupportedOperationException(); 238 } 239 240 /** 241 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified. 242 * 243 * @throws UnsupportedOperationException always 244 * @deprecated Unsupported operation. 245 */ 246 @Deprecated 247 @Override 248 @DoNotCall("Always throws UnsupportedOperationException") 249 public final void putCoalescing(Range<K> range, V value) { 250 throw new UnsupportedOperationException(); 251 } 252 253 /** 254 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified. 255 * 256 * @throws UnsupportedOperationException always 257 * @deprecated Unsupported operation. 258 */ 259 @Deprecated 260 @Override 261 @DoNotCall("Always throws UnsupportedOperationException") 262 public final void putAll(RangeMap<K, ? extends V> rangeMap) { 263 throw new UnsupportedOperationException(); 264 } 265 266 /** 267 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified. 268 * 269 * @throws UnsupportedOperationException always 270 * @deprecated Unsupported operation. 271 */ 272 @Deprecated 273 @Override 274 @DoNotCall("Always throws UnsupportedOperationException") 275 public final void clear() { 276 throw new UnsupportedOperationException(); 277 } 278 279 /** 280 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified. 281 * 282 * @throws UnsupportedOperationException always 283 * @deprecated Unsupported operation. 284 */ 285 @Deprecated 286 @Override 287 @DoNotCall("Always throws UnsupportedOperationException") 288 public final void remove(Range<K> range) { 289 throw new UnsupportedOperationException(); 290 } 291 292 /** 293 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified. 294 * 295 * @throws UnsupportedOperationException always 296 * @deprecated Unsupported operation. 297 */ 298 @Deprecated 299 @Override 300 @DoNotCall("Always throws UnsupportedOperationException") 301 public final void merge( 302 Range<K> range, 303 @CheckForNull V value, 304 BiFunction<? super V, ? super @Nullable V, ? extends @Nullable V> remappingFunction) { 305 throw new UnsupportedOperationException(); 306 } 307 308 @Override 309 public ImmutableMap<Range<K>, V> asMapOfRanges() { 310 if (ranges.isEmpty()) { 311 return ImmutableMap.of(); 312 } 313 RegularImmutableSortedSet<Range<K>> rangeSet = 314 new RegularImmutableSortedSet<>(ranges, Range.<K>rangeLexOrdering()); 315 return new ImmutableSortedMap<>(rangeSet, values); 316 } 317 318 @Override 319 public ImmutableMap<Range<K>, V> asDescendingMapOfRanges() { 320 if (ranges.isEmpty()) { 321 return ImmutableMap.of(); 322 } 323 RegularImmutableSortedSet<Range<K>> rangeSet = 324 new RegularImmutableSortedSet<>(ranges.reverse(), Range.<K>rangeLexOrdering().reverse()); 325 return new ImmutableSortedMap<>(rangeSet, values.reverse()); 326 } 327 328 @Override 329 public ImmutableRangeMap<K, V> subRangeMap(final Range<K> range) { 330 if (checkNotNull(range).isEmpty()) { 331 return ImmutableRangeMap.of(); 332 } else if (ranges.isEmpty() || range.encloses(span())) { 333 return this; 334 } 335 int lowerIndex = 336 SortedLists.binarySearch( 337 ranges, 338 Range.<K>upperBoundFn(), 339 range.lowerBound, 340 KeyPresentBehavior.FIRST_AFTER, 341 KeyAbsentBehavior.NEXT_HIGHER); 342 int upperIndex = 343 SortedLists.binarySearch( 344 ranges, 345 Range.<K>lowerBoundFn(), 346 range.upperBound, 347 KeyPresentBehavior.ANY_PRESENT, 348 KeyAbsentBehavior.NEXT_HIGHER); 349 if (lowerIndex >= upperIndex) { 350 return ImmutableRangeMap.of(); 351 } 352 final int off = lowerIndex; 353 final int len = upperIndex - lowerIndex; 354 ImmutableList<Range<K>> subRanges = 355 new ImmutableList<Range<K>>() { 356 @Override 357 public int size() { 358 return len; 359 } 360 361 @Override 362 public Range<K> get(int index) { 363 checkElementIndex(index, len); 364 if (index == 0 || index == len - 1) { 365 return ranges.get(index + off).intersection(range); 366 } else { 367 return ranges.get(index + off); 368 } 369 } 370 371 @Override 372 boolean isPartialView() { 373 return true; 374 } 375 }; 376 final ImmutableRangeMap<K, V> outer = this; 377 return new ImmutableRangeMap<K, V>(subRanges, values.subList(lowerIndex, upperIndex)) { 378 @Override 379 public ImmutableRangeMap<K, V> subRangeMap(Range<K> subRange) { 380 if (range.isConnected(subRange)) { 381 return outer.subRangeMap(subRange.intersection(range)); 382 } else { 383 return ImmutableRangeMap.of(); 384 } 385 } 386 }; 387 } 388 389 @Override 390 public int hashCode() { 391 return asMapOfRanges().hashCode(); 392 } 393 394 @Override 395 public boolean equals(@CheckForNull Object o) { 396 if (o instanceof RangeMap) { 397 RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o; 398 return asMapOfRanges().equals(rangeMap.asMapOfRanges()); 399 } 400 return false; 401 } 402 403 @Override 404 public String toString() { 405 return asMapOfRanges().toString(); 406 } 407 408 /** 409 * This class is used to serialize ImmutableRangeMap instances. Serializes the {@link 410 * #asMapOfRanges()} form. 411 */ 412 private static class SerializedForm<K extends Comparable<?>, V> implements Serializable { 413 414 private final ImmutableMap<Range<K>, V> mapOfRanges; 415 416 SerializedForm(ImmutableMap<Range<K>, V> mapOfRanges) { 417 this.mapOfRanges = mapOfRanges; 418 } 419 420 Object readResolve() { 421 if (mapOfRanges.isEmpty()) { 422 return of(); 423 } else { 424 return createRangeMap(); 425 } 426 } 427 428 Object createRangeMap() { 429 Builder<K, V> builder = new Builder<>(); 430 for (Entry<Range<K>, V> entry : mapOfRanges.entrySet()) { 431 builder.put(entry.getKey(), entry.getValue()); 432 } 433 return builder.build(); 434 } 435 436 private static final long serialVersionUID = 0; 437 } 438 439 Object writeReplace() { 440 return new SerializedForm<>(asMapOfRanges()); 441 } 442 443 @J2ktIncompatible // java.io.ObjectInputStream 444 private void readObject(ObjectInputStream stream) throws InvalidObjectException { 445 throw new InvalidObjectException("Use SerializedForm"); 446 } 447 448 private static final long serialVersionUID = 0; 449}