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 javax.annotation.CheckForNull;
041import org.checkerframework.checker.nullness.qual.Nullable;
042
043/**
044 * A {@link RangeMap} whose contents will never change, with many other important properties
045 * detailed at {@link ImmutableCollection}.
046 *
047 * @author Louis Wasserman
048 * @since 14.0
049 */
050@GwtIncompatible // NavigableMap
051@ElementTypesAreNonnullByDefault
052public class ImmutableRangeMap<K extends Comparable<?>, V> implements RangeMap<K, V>, Serializable {
053
054  private static final ImmutableRangeMap<Comparable<?>, Object> EMPTY =
055      new ImmutableRangeMap<>(ImmutableList.<Range<Comparable<?>>>of(), ImmutableList.of());
056
057  /**
058   * Returns a {@code Collector} that accumulates the input elements into a new {@code
059   * ImmutableRangeMap}. As in {@link Builder}, overlapping ranges are not permitted.
060   *
061   * @since 23.1
062   */
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  /**
294   * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified.
295   *
296   * @throws UnsupportedOperationException always
297   * @deprecated Unsupported operation.
298   * @since 28.1
299   */
300  @Deprecated
301  @Override
302  @DoNotCall("Always throws UnsupportedOperationException")
303  public final void merge(
304      Range<K> range,
305      @CheckForNull V value,
306      BiFunction<? super V, ? super @Nullable V, ? extends @Nullable V> remappingFunction) {
307    throw new UnsupportedOperationException();
308  }
309
310  @Override
311  public ImmutableMap<Range<K>, V> asMapOfRanges() {
312    if (ranges.isEmpty()) {
313      return ImmutableMap.of();
314    }
315    RegularImmutableSortedSet<Range<K>> rangeSet =
316        new RegularImmutableSortedSet<>(ranges, Range.<K>rangeLexOrdering());
317    return new ImmutableSortedMap<>(rangeSet, values);
318  }
319
320  @Override
321  public ImmutableMap<Range<K>, V> asDescendingMapOfRanges() {
322    if (ranges.isEmpty()) {
323      return ImmutableMap.of();
324    }
325    RegularImmutableSortedSet<Range<K>> rangeSet =
326        new RegularImmutableSortedSet<>(ranges.reverse(), Range.<K>rangeLexOrdering().reverse());
327    return new ImmutableSortedMap<>(rangeSet, values.reverse());
328  }
329
330  @Override
331  public ImmutableRangeMap<K, V> subRangeMap(final Range<K> range) {
332    if (checkNotNull(range).isEmpty()) {
333      return ImmutableRangeMap.of();
334    } else if (ranges.isEmpty() || range.encloses(span())) {
335      return this;
336    }
337    int lowerIndex =
338        SortedLists.binarySearch(
339            ranges,
340            Range::upperBound,
341            range.lowerBound,
342            KeyPresentBehavior.FIRST_AFTER,
343            KeyAbsentBehavior.NEXT_HIGHER);
344    int upperIndex =
345        SortedLists.binarySearch(
346            ranges,
347            Range::lowerBound,
348            range.upperBound,
349            KeyPresentBehavior.ANY_PRESENT,
350            KeyAbsentBehavior.NEXT_HIGHER);
351    if (lowerIndex >= upperIndex) {
352      return ImmutableRangeMap.of();
353    }
354    final int off = lowerIndex;
355    final int len = upperIndex - lowerIndex;
356    ImmutableList<Range<K>> subRanges =
357        new ImmutableList<Range<K>>() {
358          @Override
359          public int size() {
360            return len;
361          }
362
363          @Override
364          public Range<K> get(int index) {
365            checkElementIndex(index, len);
366            if (index == 0 || index == len - 1) {
367              return ranges.get(index + off).intersection(range);
368            } else {
369              return ranges.get(index + off);
370            }
371          }
372
373          @Override
374          boolean isPartialView() {
375            return true;
376          }
377
378          // redeclare to help optimizers with b/310253115
379          @SuppressWarnings("RedundantOverride")
380          @Override
381          @J2ktIncompatible // serialization
382          Object writeReplace() {
383            return super.writeReplace();
384          }
385        };
386    final ImmutableRangeMap<K, V> outer = this;
387    return new ImmutableRangeMap<K, V>(subRanges, values.subList(lowerIndex, upperIndex)) {
388      @Override
389      public ImmutableRangeMap<K, V> subRangeMap(Range<K> subRange) {
390        if (range.isConnected(subRange)) {
391          return outer.subRangeMap(subRange.intersection(range));
392        } else {
393          return ImmutableRangeMap.of();
394        }
395      }
396
397      // redeclare to help optimizers with b/310253115
398      @SuppressWarnings("RedundantOverride")
399      @Override
400      @J2ktIncompatible // serialization
401      Object writeReplace() {
402        return super.writeReplace();
403      }
404    };
405  }
406
407  @Override
408  public int hashCode() {
409    return asMapOfRanges().hashCode();
410  }
411
412  @Override
413  public boolean equals(@CheckForNull Object o) {
414    if (o instanceof RangeMap) {
415      RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o;
416      return asMapOfRanges().equals(rangeMap.asMapOfRanges());
417    }
418    return false;
419  }
420
421  @Override
422  public String toString() {
423    return asMapOfRanges().toString();
424  }
425
426  /**
427   * This class is used to serialize ImmutableRangeMap instances. Serializes the {@link
428   * #asMapOfRanges()} form.
429   */
430  private static class SerializedForm<K extends Comparable<?>, V> implements Serializable {
431
432    private final ImmutableMap<Range<K>, V> mapOfRanges;
433
434    SerializedForm(ImmutableMap<Range<K>, V> mapOfRanges) {
435      this.mapOfRanges = mapOfRanges;
436    }
437
438    Object readResolve() {
439      if (mapOfRanges.isEmpty()) {
440        return of();
441      } else {
442        return createRangeMap();
443      }
444    }
445
446    Object createRangeMap() {
447      Builder<K, V> builder = new Builder<>();
448      for (Entry<Range<K>, V> entry : mapOfRanges.entrySet()) {
449        builder.put(entry.getKey(), entry.getValue());
450      }
451      return builder.build();
452    }
453
454    private static final long serialVersionUID = 0;
455  }
456
457  Object writeReplace() {
458    return new SerializedForm<>(asMapOfRanges());
459  }
460
461  @J2ktIncompatible // java.io.ObjectInputStream
462  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
463    throw new InvalidObjectException("Use SerializedForm");
464  }
465
466  private static final long serialVersionUID = 0;
467}