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