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