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