Source code

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