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