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