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