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