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