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