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