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