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