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