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