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