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