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