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