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