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 java.io.Serializable;
027import java.util.Collections;
028import java.util.List;
029import java.util.Map;
030import java.util.Map.Entry;
031import java.util.NoSuchElementException;
032import java.util.function.Function;
033import java.util.stream.Collector;
034import org.checkerframework.checker.nullness.qual.Nullable;
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  /**
051   * Returns a {@code Collector} that accumulates the input elements into a new {@code
052   * ImmutableRangeMap}. As in {@link Builder}, overlapping ranges are not permitted.
053   *
054   * @since 23.1
055   */
056  public static <T, K extends Comparable<? super K>, V>
057      Collector<T, ?, ImmutableRangeMap<K, V>> toImmutableRangeMap(
058          Function<? super T, Range<K>> keyFunction,
059          Function<? super T, ? extends V> valueFunction) {
060    return CollectCollectors.toImmutableRangeMap(keyFunction, valueFunction);
061  }
062
063  /** Returns an empty immutable range map. */
064  @SuppressWarnings("unchecked")
065  public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of() {
066    return (ImmutableRangeMap<K, V>) EMPTY;
067  }
068
069  /** Returns an immutable range map mapping a single range to a single value. */
070  public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of(Range<K> range, V value) {
071    return new ImmutableRangeMap<>(ImmutableList.of(range), ImmutableList.of(value));
072  }
073
074  @SuppressWarnings("unchecked")
075  public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> copyOf(
076      RangeMap<K, ? extends V> rangeMap) {
077    if (rangeMap instanceof ImmutableRangeMap) {
078      return (ImmutableRangeMap<K, V>) rangeMap;
079    }
080    Map<Range<K>, ? extends V> map = rangeMap.asMapOfRanges();
081    ImmutableList.Builder<Range<K>> rangesBuilder = new ImmutableList.Builder<>(map.size());
082    ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(map.size());
083    for (Entry<Range<K>, ? extends V> entry : map.entrySet()) {
084      rangesBuilder.add(entry.getKey());
085      valuesBuilder.add(entry.getValue());
086    }
087    return new ImmutableRangeMap<>(rangesBuilder.build(), valuesBuilder.build());
088  }
089
090  /** Returns a new builder for an immutable range map. */
091  public static <K extends Comparable<?>, V> Builder<K, V> builder() {
092    return new Builder<>();
093  }
094
095  /**
096   * A builder for immutable range maps. Overlapping ranges are prohibited.
097   *
098   * @since 14.0
099   */
100  public static final class Builder<K extends Comparable<?>, V> {
101    private final List<Entry<Range<K>, V>> entries;
102
103    public Builder() {
104      this.entries = Lists.newArrayList();
105    }
106
107    /**
108     * Associates the specified range with the specified value.
109     *
110     * @throws IllegalArgumentException if {@code range} is empty
111     */
112    @CanIgnoreReturnValue
113    public Builder<K, V> put(Range<K> range, V value) {
114      checkNotNull(range);
115      checkNotNull(value);
116      checkArgument(!range.isEmpty(), "Range must not be empty, but was %s", range);
117      entries.add(Maps.immutableEntry(range, value));
118      return this;
119    }
120
121    /** Copies all associations from the specified range map into this builder. */
122    @CanIgnoreReturnValue
123    public Builder<K, V> putAll(RangeMap<K, ? extends V> rangeMap) {
124      for (Entry<Range<K>, ? extends V> entry : rangeMap.asMapOfRanges().entrySet()) {
125        put(entry.getKey(), entry.getValue());
126      }
127      return this;
128    }
129
130    @CanIgnoreReturnValue
131    Builder<K, V> combine(Builder<K, V> builder) {
132      entries.addAll(builder.entries);
133      return this;
134    }
135
136    /**
137     * Returns an {@code ImmutableRangeMap} containing the associations previously added to this
138     * builder.
139     *
140     * @throws IllegalArgumentException if any two ranges inserted into this builder overlap
141     */
142    public ImmutableRangeMap<K, V> build() {
143      Collections.sort(entries, Range.<K>rangeLexOrdering().onKeys());
144      ImmutableList.Builder<Range<K>> rangesBuilder = new ImmutableList.Builder<>(entries.size());
145      ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(entries.size());
146      for (int i = 0; i < entries.size(); i++) {
147        Range<K> range = entries.get(i).getKey();
148        if (i > 0) {
149          Range<K> prevRange = entries.get(i - 1).getKey();
150          if (range.isConnected(prevRange) && !range.intersection(prevRange).isEmpty()) {
151            throw new IllegalArgumentException(
152                "Overlapping ranges: range " + prevRange + " overlaps with entry " + range);
153          }
154        }
155        rangesBuilder.add(range);
156        valuesBuilder.add(entries.get(i).getValue());
157      }
158      return new ImmutableRangeMap<>(rangesBuilder.build(), valuesBuilder.build());
159    }
160  }
161
162  private final transient ImmutableList<Range<K>> ranges;
163  private final transient ImmutableList<V> values;
164
165  ImmutableRangeMap(ImmutableList<Range<K>> ranges, ImmutableList<V> values) {
166    this.ranges = ranges;
167    this.values = values;
168  }
169
170  @Override
171  public @Nullable V get(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) ? values.get(index) : null;
184    }
185  }
186
187  @Override
188  public @Nullable Entry<Range<K>, V> getEntry(K key) {
189    int index =
190        SortedLists.binarySearch(
191            ranges,
192            Range.<K>lowerBoundFn(),
193            Cut.belowValue(key),
194            KeyPresentBehavior.ANY_PRESENT,
195            KeyAbsentBehavior.NEXT_LOWER);
196    if (index == -1) {
197      return null;
198    } else {
199      Range<K> range = ranges.get(index);
200      return range.contains(key) ? Maps.immutableEntry(range, values.get(index)) : null;
201    }
202  }
203
204  @Override
205  public Range<K> span() {
206    if (ranges.isEmpty()) {
207      throw new NoSuchElementException();
208    }
209    Range<K> firstRange = ranges.get(0);
210    Range<K> lastRange = ranges.get(ranges.size() - 1);
211    return Range.create(firstRange.lowerBound, lastRange.upperBound);
212  }
213
214  /**
215   * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified.
216   *
217   * @throws UnsupportedOperationException always
218   * @deprecated Unsupported operation.
219   */
220  @Deprecated
221  @Override
222  public void put(Range<K> range, V value) {
223    throw new UnsupportedOperationException();
224  }
225
226  /**
227   * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified.
228   *
229   * @throws UnsupportedOperationException always
230   * @deprecated Unsupported operation.
231   */
232  @Deprecated
233  @Override
234  public 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  public void putAll(RangeMap<K, V> rangeMap) {
247    throw new UnsupportedOperationException();
248  }
249
250  /**
251   * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified.
252   *
253   * @throws UnsupportedOperationException always
254   * @deprecated Unsupported operation.
255   */
256  @Deprecated
257  @Override
258  public 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  public 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(@Nullable 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}