View Javadoc
1   /*
2    * Copyright (C) 2012 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5    * in compliance with the License. You may obtain a copy of the License at
6    *
7    * http://www.apache.org/licenses/LICENSE-2.0
8    *
9    * Unless required by applicable law or agreed to in writing, software distributed under the License
10   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11   * or implied. See the License for the specific language governing permissions and limitations under
12   * the License.
13   */
14  
15  package com.google.common.collect;
16  
17  import static com.google.common.base.Preconditions.checkArgument;
18  import static com.google.common.base.Preconditions.checkElementIndex;
19  import static com.google.common.base.Preconditions.checkNotNull;
20  
21  import com.google.common.annotations.Beta;
22  import com.google.common.annotations.GwtIncompatible;
23  import com.google.common.collect.SortedLists.KeyAbsentBehavior;
24  import com.google.common.collect.SortedLists.KeyPresentBehavior;
25  import com.google.errorprone.annotations.CanIgnoreReturnValue;
26  import java.io.Serializable;
27  import java.util.Collections;
28  import java.util.List;
29  import java.util.Map;
30  import java.util.Map.Entry;
31  import java.util.NoSuchElementException;
32  import java.util.function.Function;
33  import java.util.stream.Collector;
34  import javax.annotation.Nullable;
35  
36  /**
37   * A {@link RangeMap} whose contents will never change, with many other important properties
38   * detailed at {@link ImmutableCollection}.
39   *
40   * @author Louis Wasserman
41   * @since 14.0
42   */
43  @Beta
44  @GwtIncompatible // NavigableMap
45  public class ImmutableRangeMap<K extends Comparable<?>, V> implements RangeMap<K, V>, Serializable {
46  
47    private static final ImmutableRangeMap<Comparable<?>, Object> EMPTY =
48        new ImmutableRangeMap<>(ImmutableList.<Range<Comparable<?>>>of(), ImmutableList.of());
49  
50    /**
51     * Returns a {@code Collector} that accumulates the input elements into a new {@code
52     * ImmutableRangeMap}. As in {@link Builder}, overlapping ranges are not permitted.
53     *
54     * @since 23.1
55     */
56    @Beta
57    public static <T, K extends Comparable<? super K>, V>
58        Collector<T, ?, ImmutableRangeMap<K, V>> toImmutableRangeMap(
59            Function<? super T, Range<K>> keyFunction,
60            Function<? super T, ? extends V> valueFunction) {
61      return CollectCollectors.toImmutableRangeMap(keyFunction, valueFunction);
62    }
63  
64    /**
65     * Returns an empty immutable range map.
66     */
67    @SuppressWarnings("unchecked")
68    public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of() {
69      return (ImmutableRangeMap<K, V>) EMPTY;
70    }
71  
72    /**
73     * Returns an immutable range map mapping a single range to a single value.
74     */
75    public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of(Range<K> range, V value) {
76      return new ImmutableRangeMap<>(ImmutableList.of(range), ImmutableList.of(value));
77    }
78  
79    @SuppressWarnings("unchecked")
80    public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> copyOf(
81        RangeMap<K, ? extends V> rangeMap) {
82      if (rangeMap instanceof ImmutableRangeMap) {
83        return (ImmutableRangeMap<K, V>) rangeMap;
84      }
85      Map<Range<K>, ? extends V> map = rangeMap.asMapOfRanges();
86      ImmutableList.Builder<Range<K>> rangesBuilder = new ImmutableList.Builder<>(map.size());
87      ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(map.size());
88      for (Entry<Range<K>, ? extends V> entry : map.entrySet()) {
89        rangesBuilder.add(entry.getKey());
90        valuesBuilder.add(entry.getValue());
91      }
92      return new ImmutableRangeMap<>(rangesBuilder.build(), valuesBuilder.build());
93    }
94  
95    /**
96     * Returns a new builder for an immutable range map.
97     */
98    public static <K extends Comparable<?>, V> Builder<K, V> builder() {
99      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 }