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