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