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 com.google.errorprone.annotations.DoNotCall; 027import com.google.errorprone.annotations.DoNotMock; 028import java.io.Serializable; 029import java.util.Collections; 030import java.util.List; 031import java.util.Map; 032import java.util.Map.Entry; 033import java.util.NoSuchElementException; 034import javax.annotation.CheckForNull; 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 045@ElementTypesAreNonnullByDefault 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 an empty immutable range map. 053 * 054 * <p><b>Performance note:</b> the instance returned is a singleton. 055 */ 056 @SuppressWarnings("unchecked") 057 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of() { 058 return (ImmutableRangeMap<K, V>) EMPTY; 059 } 060 061 /** Returns an immutable range map mapping a single range to a single value. */ 062 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of(Range<K> range, V value) { 063 return new ImmutableRangeMap<>(ImmutableList.of(range), ImmutableList.of(value)); 064 } 065 066 @SuppressWarnings("unchecked") 067 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> copyOf( 068 RangeMap<K, ? extends V> rangeMap) { 069 if (rangeMap instanceof ImmutableRangeMap) { 070 return (ImmutableRangeMap<K, V>) rangeMap; 071 } 072 Map<Range<K>, ? extends V> map = rangeMap.asMapOfRanges(); 073 ImmutableList.Builder<Range<K>> rangesBuilder = new ImmutableList.Builder<>(map.size()); 074 ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(map.size()); 075 for (Entry<Range<K>, ? extends V> entry : map.entrySet()) { 076 rangesBuilder.add(entry.getKey()); 077 valuesBuilder.add(entry.getValue()); 078 } 079 return new ImmutableRangeMap<>(rangesBuilder.build(), valuesBuilder.build()); 080 } 081 082 /** Returns a new builder for an immutable range map. */ 083 public static <K extends Comparable<?>, V> Builder<K, V> builder() { 084 return new Builder<>(); 085 } 086 087 /** 088 * A builder for immutable range maps. Overlapping ranges are prohibited. 089 * 090 * @since 14.0 091 */ 092 @DoNotMock 093 public static final class Builder<K extends Comparable<?>, V> { 094 private final List<Entry<Range<K>, V>> entries; 095 096 public Builder() { 097 this.entries = Lists.newArrayList(); 098 } 099 100 /** 101 * Associates the specified range with the specified value. 102 * 103 * @throws IllegalArgumentException if {@code range} is empty 104 */ 105 @CanIgnoreReturnValue 106 public Builder<K, V> put(Range<K> range, V value) { 107 checkNotNull(range); 108 checkNotNull(value); 109 checkArgument(!range.isEmpty(), "Range must not be empty, but was %s", range); 110 entries.add(Maps.immutableEntry(range, value)); 111 return this; 112 } 113 114 /** Copies all associations from the specified range map into this builder. */ 115 @CanIgnoreReturnValue 116 public Builder<K, V> putAll(RangeMap<K, ? extends V> rangeMap) { 117 for (Entry<Range<K>, ? extends V> entry : rangeMap.asMapOfRanges().entrySet()) { 118 put(entry.getKey(), entry.getValue()); 119 } 120 return this; 121 } 122 123 @CanIgnoreReturnValue 124 Builder<K, V> combine(Builder<K, V> builder) { 125 entries.addAll(builder.entries); 126 return this; 127 } 128 129 /** 130 * Returns an {@code ImmutableRangeMap} containing the associations previously added to this 131 * builder. 132 * 133 * @throws IllegalArgumentException if any two ranges inserted into this builder overlap 134 */ 135 public ImmutableRangeMap<K, V> build() { 136 Collections.sort(entries, Range.<K>rangeLexOrdering().onKeys()); 137 ImmutableList.Builder<Range<K>> rangesBuilder = new ImmutableList.Builder<>(entries.size()); 138 ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(entries.size()); 139 for (int i = 0; i < entries.size(); i++) { 140 Range<K> range = entries.get(i).getKey(); 141 if (i > 0) { 142 Range<K> prevRange = entries.get(i - 1).getKey(); 143 if (range.isConnected(prevRange) && !range.intersection(prevRange).isEmpty()) { 144 throw new IllegalArgumentException( 145 "Overlapping ranges: range " + prevRange + " overlaps with entry " + range); 146 } 147 } 148 rangesBuilder.add(range); 149 valuesBuilder.add(entries.get(i).getValue()); 150 } 151 return new ImmutableRangeMap<>(rangesBuilder.build(), valuesBuilder.build()); 152 } 153 } 154 155 private final transient ImmutableList<Range<K>> ranges; 156 private final transient ImmutableList<V> values; 157 158 ImmutableRangeMap(ImmutableList<Range<K>> ranges, ImmutableList<V> values) { 159 this.ranges = ranges; 160 this.values = values; 161 } 162 163 @Override 164 @CheckForNull 165 public V get(K key) { 166 int index = 167 SortedLists.binarySearch( 168 ranges, 169 Range.<K>lowerBoundFn(), 170 Cut.belowValue(key), 171 KeyPresentBehavior.ANY_PRESENT, 172 KeyAbsentBehavior.NEXT_LOWER); 173 if (index == -1) { 174 return null; 175 } else { 176 Range<K> range = ranges.get(index); 177 return range.contains(key) ? values.get(index) : null; 178 } 179 } 180 181 @Override 182 @CheckForNull 183 public Entry<Range<K>, V> getEntry(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) ? Maps.immutableEntry(range, values.get(index)) : null; 196 } 197 } 198 199 @Override 200 public Range<K> span() { 201 if (ranges.isEmpty()) { 202 throw new NoSuchElementException(); 203 } 204 Range<K> firstRange = ranges.get(0); 205 Range<K> lastRange = ranges.get(ranges.size() - 1); 206 return Range.create(firstRange.lowerBound, lastRange.upperBound); 207 } 208 209 /** 210 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified. 211 * 212 * @throws UnsupportedOperationException always 213 * @deprecated Unsupported operation. 214 */ 215 @Deprecated 216 @Override 217 @DoNotCall("Always throws UnsupportedOperationException") 218 public final void put(Range<K> range, V value) { 219 throw new UnsupportedOperationException(); 220 } 221 222 /** 223 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified. 224 * 225 * @throws UnsupportedOperationException always 226 * @deprecated Unsupported operation. 227 */ 228 @Deprecated 229 @Override 230 @DoNotCall("Always throws UnsupportedOperationException") 231 public final void putCoalescing(Range<K> range, V value) { 232 throw new UnsupportedOperationException(); 233 } 234 235 /** 236 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified. 237 * 238 * @throws UnsupportedOperationException always 239 * @deprecated Unsupported operation. 240 */ 241 @Deprecated 242 @Override 243 @DoNotCall("Always throws UnsupportedOperationException") 244 public final void putAll(RangeMap<K, V> rangeMap) { 245 throw new UnsupportedOperationException(); 246 } 247 248 /** 249 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified. 250 * 251 * @throws UnsupportedOperationException always 252 * @deprecated Unsupported operation. 253 */ 254 @Deprecated 255 @Override 256 @DoNotCall("Always throws UnsupportedOperationException") 257 public final void clear() { 258 throw new UnsupportedOperationException(); 259 } 260 261 /** 262 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified. 263 * 264 * @throws UnsupportedOperationException always 265 * @deprecated Unsupported operation. 266 */ 267 @Deprecated 268 @Override 269 @DoNotCall("Always throws UnsupportedOperationException") 270 public final 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(@CheckForNull 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}