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.Beta;
022import com.google.common.annotations.GwtIncompatible;
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@Beta
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<V>(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(Maps.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      Collections.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<V>(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.<K>lowerBoundFn(),
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.<K>lowerBoundFn(),
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) ? Maps.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   */
299  @Deprecated
300  @Override
301  @DoNotCall("Always throws UnsupportedOperationException")
302  public final void merge(
303      Range<K> range,
304      @CheckForNull V value,
305      BiFunction<? super V, ? super @Nullable V, ? extends @Nullable V> remappingFunction) {
306    throw new UnsupportedOperationException();
307  }
308
309  @Override
310  public ImmutableMap<Range<K>, V> asMapOfRanges() {
311    if (ranges.isEmpty()) {
312      return ImmutableMap.of();
313    }
314    RegularImmutableSortedSet<Range<K>> rangeSet =
315        new RegularImmutableSortedSet<>(ranges, Range.<K>rangeLexOrdering());
316    return new ImmutableSortedMap<>(rangeSet, values);
317  }
318
319  @Override
320  public ImmutableMap<Range<K>, V> asDescendingMapOfRanges() {
321    if (ranges.isEmpty()) {
322      return ImmutableMap.of();
323    }
324    RegularImmutableSortedSet<Range<K>> rangeSet =
325        new RegularImmutableSortedSet<>(ranges.reverse(), Range.<K>rangeLexOrdering().reverse());
326    return new ImmutableSortedMap<>(rangeSet, values.reverse());
327  }
328
329  @Override
330  public ImmutableRangeMap<K, V> subRangeMap(final Range<K> range) {
331    if (checkNotNull(range).isEmpty()) {
332      return ImmutableRangeMap.of();
333    } else if (ranges.isEmpty() || range.encloses(span())) {
334      return this;
335    }
336    int lowerIndex =
337        SortedLists.binarySearch(
338            ranges,
339            Range.<K>upperBoundFn(),
340            range.lowerBound,
341            KeyPresentBehavior.FIRST_AFTER,
342            KeyAbsentBehavior.NEXT_HIGHER);
343    int upperIndex =
344        SortedLists.binarySearch(
345            ranges,
346            Range.<K>lowerBoundFn(),
347            range.upperBound,
348            KeyPresentBehavior.ANY_PRESENT,
349            KeyAbsentBehavior.NEXT_HIGHER);
350    if (lowerIndex >= upperIndex) {
351      return ImmutableRangeMap.of();
352    }
353    final int off = lowerIndex;
354    final int len = upperIndex - lowerIndex;
355    ImmutableList<Range<K>> subRanges =
356        new ImmutableList<Range<K>>() {
357          @Override
358          public int size() {
359            return len;
360          }
361
362          @Override
363          public Range<K> get(int index) {
364            checkElementIndex(index, len);
365            if (index == 0 || index == len - 1) {
366              return ranges.get(index + off).intersection(range);
367            } else {
368              return ranges.get(index + off);
369            }
370          }
371
372          @Override
373          boolean isPartialView() {
374            return true;
375          }
376        };
377    final ImmutableRangeMap<K, V> outer = this;
378    return new ImmutableRangeMap<K, V>(subRanges, values.subList(lowerIndex, upperIndex)) {
379      @Override
380      public ImmutableRangeMap<K, V> subRangeMap(Range<K> subRange) {
381        if (range.isConnected(subRange)) {
382          return outer.subRangeMap(subRange.intersection(range));
383        } else {
384          return ImmutableRangeMap.of();
385        }
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  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
445    throw new InvalidObjectException("Use SerializedForm");
446  }
447
448  private static final long serialVersionUID = 0;
449}