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 com.google.errorprone.annotations.DoNotCall;
27 import com.google.errorprone.annotations.DoNotMock;
28 import java.io.Serializable;
29 import java.util.Collections;
30 import java.util.List;
31 import java.util.Map;
32 import java.util.Map.Entry;
33 import java.util.NoSuchElementException;
34 import java.util.function.BiFunction;
35 import java.util.function.Function;
36 import java.util.stream.Collector;
37 import org.checkerframework.checker.nullness.qual.Nullable;
38
39 /**
40 * A {@link RangeMap} whose contents will never change, with many other important properties
41 * detailed at {@link ImmutableCollection}.
42 *
43 * @author Louis Wasserman
44 * @since 14.0
45 */
46 @Beta
47 @GwtIncompatible // NavigableMap
48 public class ImmutableRangeMap<K extends Comparable<?>, V> implements RangeMap<K, V>, Serializable {
49
50 private static final ImmutableRangeMap<Comparable<?>, Object> EMPTY =
51 new ImmutableRangeMap<>(ImmutableList.<Range<Comparable<?>>>of(), ImmutableList.of());
52
53 /**
54 * Returns a {@code Collector} that accumulates the input elements into a new {@code
55 * ImmutableRangeMap}. As in {@link Builder}, overlapping ranges are not permitted.
56 *
57 * @since 23.1
58 */
59 public static <T, K extends Comparable<? super K>, V>
60 Collector<T, ?, ImmutableRangeMap<K, V>> toImmutableRangeMap(
61 Function<? super T, Range<K>> keyFunction,
62 Function<? super T, ? extends V> valueFunction) {
63 return CollectCollectors.toImmutableRangeMap(keyFunction, valueFunction);
64 }
65
66 /**
67 * Returns an empty immutable range map.
68 *
69 * <p><b>Performance note:</b> the instance returned is a singleton.
70 */
71 @SuppressWarnings("unchecked")
72 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of() {
73 return (ImmutableRangeMap<K, V>) EMPTY;
74 }
75
76 /** Returns an immutable range map mapping a single range to a single value. */
77 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of(Range<K> range, V value) {
78 return new ImmutableRangeMap<>(ImmutableList.of(range), ImmutableList.of(value));
79 }
80
81 @SuppressWarnings("unchecked")
82 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> copyOf(
83 RangeMap<K, ? extends V> rangeMap) {
84 if (rangeMap instanceof ImmutableRangeMap) {
85 return (ImmutableRangeMap<K, V>) rangeMap;
86 }
87 Map<Range<K>, ? extends V> map = rangeMap.asMapOfRanges();
88 ImmutableList.Builder<Range<K>> rangesBuilder = new ImmutableList.Builder<>(map.size());
89 ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(map.size());
90 for (Entry<Range<K>, ? extends V> entry : map.entrySet()) {
91 rangesBuilder.add(entry.getKey());
92 valuesBuilder.add(entry.getValue());
93 }
94 return new ImmutableRangeMap<>(rangesBuilder.build(), valuesBuilder.build());
95 }
96
97 /** Returns a new builder for an immutable range map. */
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 * @since 14.0
106 */
107 @DoNotMock
108 public static final class Builder<K extends Comparable<?>, V> {
109 private final List<Entry<Range<K>, V>> entries;
110
111 public Builder() {
112 this.entries = Lists.newArrayList();
113 }
114
115 /**
116 * Associates the specified range with the specified value.
117 *
118 * @throws IllegalArgumentException if {@code range} is empty
119 */
120 @CanIgnoreReturnValue
121 public Builder<K, V> put(Range<K> range, V value) {
122 checkNotNull(range);
123 checkNotNull(value);
124 checkArgument(!range.isEmpty(), "Range must not be empty, but was %s", range);
125 entries.add(Maps.immutableEntry(range, value));
126 return this;
127 }
128
129 /** Copies all associations from the specified range map into this builder. */
130 @CanIgnoreReturnValue
131 public Builder<K, V> putAll(RangeMap<K, ? extends V> rangeMap) {
132 for (Entry<Range<K>, ? extends V> entry : rangeMap.asMapOfRanges().entrySet()) {
133 put(entry.getKey(), entry.getValue());
134 }
135 return this;
136 }
137
138 @CanIgnoreReturnValue
139 Builder<K, V> combine(Builder<K, V> builder) {
140 entries.addAll(builder.entries);
141 return this;
142 }
143
144 /**
145 * Returns an {@code ImmutableRangeMap} containing the associations previously added to this
146 * builder.
147 *
148 * @throws IllegalArgumentException if any two ranges inserted into this builder overlap
149 */
150 public ImmutableRangeMap<K, V> build() {
151 Collections.sort(entries, Range.<K>rangeLexOrdering().onKeys());
152 ImmutableList.Builder<Range<K>> rangesBuilder = new ImmutableList.Builder<>(entries.size());
153 ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(entries.size());
154 for (int i = 0; i < entries.size(); i++) {
155 Range<K> range = entries.get(i).getKey();
156 if (i > 0) {
157 Range<K> prevRange = entries.get(i - 1).getKey();
158 if (range.isConnected(prevRange) && !range.intersection(prevRange).isEmpty()) {
159 throw new IllegalArgumentException(
160 "Overlapping ranges: range " + prevRange + " overlaps with entry " + range);
161 }
162 }
163 rangesBuilder.add(range);
164 valuesBuilder.add(entries.get(i).getValue());
165 }
166 return new ImmutableRangeMap<>(rangesBuilder.build(), valuesBuilder.build());
167 }
168 }
169
170 private final transient ImmutableList<Range<K>> ranges;
171 private final transient ImmutableList<V> values;
172
173 ImmutableRangeMap(ImmutableList<Range<K>> ranges, ImmutableList<V> values) {
174 this.ranges = ranges;
175 this.values = values;
176 }
177
178 @Override
179 public @Nullable 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 public @Nullable Entry<Range<K>, V> getEntry(K key) {
197 int index =
198 SortedLists.binarySearch(
199 ranges,
200 Range.<K>lowerBoundFn(),
201 Cut.belowValue(key),
202 KeyPresentBehavior.ANY_PRESENT,
203 KeyAbsentBehavior.NEXT_LOWER);
204 if (index == -1) {
205 return null;
206 } else {
207 Range<K> range = ranges.get(index);
208 return range.contains(key) ? Maps.immutableEntry(range, values.get(index)) : null;
209 }
210 }
211
212 @Override
213 public Range<K> span() {
214 if (ranges.isEmpty()) {
215 throw new NoSuchElementException();
216 }
217 Range<K> firstRange = ranges.get(0);
218 Range<K> lastRange = ranges.get(ranges.size() - 1);
219 return Range.create(firstRange.lowerBound, lastRange.upperBound);
220 }
221
222 /**
223 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified.
224 *
225 * @throws UnsupportedOperationException always
226 * @deprecated Unsupported operation.
227 */
228 @Deprecated
229 @Override
230 @DoNotCall("Always throws UnsupportedOperationException")
231 public final 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 @DoNotCall("Always throws UnsupportedOperationException")
244 public final void putCoalescing(Range<K> range, V value) {
245 throw new UnsupportedOperationException();
246 }
247
248 /**
249 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified.
250 *
251 * @throws UnsupportedOperationException always
252 * @deprecated Unsupported operation.
253 */
254 @Deprecated
255 @Override
256 @DoNotCall("Always throws UnsupportedOperationException")
257 public final void putAll(RangeMap<K, V> rangeMap) {
258 throw new UnsupportedOperationException();
259 }
260
261 /**
262 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified.
263 *
264 * @throws UnsupportedOperationException always
265 * @deprecated Unsupported operation.
266 */
267 @Deprecated
268 @Override
269 @DoNotCall("Always throws UnsupportedOperationException")
270 public final void clear() {
271 throw new UnsupportedOperationException();
272 }
273
274 /**
275 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified.
276 *
277 * @throws UnsupportedOperationException always
278 * @deprecated Unsupported operation.
279 */
280 @Deprecated
281 @Override
282 @DoNotCall("Always throws UnsupportedOperationException")
283 public final void remove(Range<K> range) {
284 throw new UnsupportedOperationException();
285 }
286
287 /**
288 * Guaranteed to throw an exception and leave the {@code RangeMap} unmodified.
289 *
290 * @throws UnsupportedOperationException always
291 * @deprecated Unsupported operation.
292 */
293 @Deprecated
294 @Override
295 @DoNotCall("Always throws UnsupportedOperationException")
296 public final void merge(
297 Range<K> range,
298 @Nullable V value,
299 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
300 throw new UnsupportedOperationException();
301 }
302
303 @Override
304 public ImmutableMap<Range<K>, V> asMapOfRanges() {
305 if (ranges.isEmpty()) {
306 return ImmutableMap.of();
307 }
308 RegularImmutableSortedSet<Range<K>> rangeSet =
309 new RegularImmutableSortedSet<>(ranges, Range.<K>rangeLexOrdering());
310 return new ImmutableSortedMap<>(rangeSet, values);
311 }
312
313 @Override
314 public ImmutableMap<Range<K>, V> asDescendingMapOfRanges() {
315 if (ranges.isEmpty()) {
316 return ImmutableMap.of();
317 }
318 RegularImmutableSortedSet<Range<K>> rangeSet =
319 new RegularImmutableSortedSet<>(ranges.reverse(), Range.<K>rangeLexOrdering().reverse());
320 return new ImmutableSortedMap<>(rangeSet, values.reverse());
321 }
322
323 @Override
324 public ImmutableRangeMap<K, V> subRangeMap(final Range<K> range) {
325 if (checkNotNull(range).isEmpty()) {
326 return ImmutableRangeMap.of();
327 } else if (ranges.isEmpty() || range.encloses(span())) {
328 return this;
329 }
330 int lowerIndex =
331 SortedLists.binarySearch(
332 ranges,
333 Range.<K>upperBoundFn(),
334 range.lowerBound,
335 KeyPresentBehavior.FIRST_AFTER,
336 KeyAbsentBehavior.NEXT_HIGHER);
337 int upperIndex =
338 SortedLists.binarySearch(
339 ranges,
340 Range.<K>lowerBoundFn(),
341 range.upperBound,
342 KeyPresentBehavior.ANY_PRESENT,
343 KeyAbsentBehavior.NEXT_HIGHER);
344 if (lowerIndex >= upperIndex) {
345 return ImmutableRangeMap.of();
346 }
347 final int off = lowerIndex;
348 final int len = upperIndex - lowerIndex;
349 ImmutableList<Range<K>> subRanges =
350 new ImmutableList<Range<K>>() {
351 @Override
352 public int size() {
353 return len;
354 }
355
356 @Override
357 public Range<K> get(int index) {
358 checkElementIndex(index, len);
359 if (index == 0 || index == len - 1) {
360 return ranges.get(index + off).intersection(range);
361 } else {
362 return ranges.get(index + off);
363 }
364 }
365
366 @Override
367 boolean isPartialView() {
368 return true;
369 }
370 };
371 final ImmutableRangeMap<K, V> outer = this;
372 return new ImmutableRangeMap<K, V>(subRanges, values.subList(lowerIndex, upperIndex)) {
373 @Override
374 public ImmutableRangeMap<K, V> subRangeMap(Range<K> subRange) {
375 if (range.isConnected(subRange)) {
376 return outer.subRangeMap(subRange.intersection(range));
377 } else {
378 return ImmutableRangeMap.of();
379 }
380 }
381 };
382 }
383
384 @Override
385 public int hashCode() {
386 return asMapOfRanges().hashCode();
387 }
388
389 @Override
390 public boolean equals(@Nullable Object o) {
391 if (o instanceof RangeMap) {
392 RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o;
393 return asMapOfRanges().equals(rangeMap.asMapOfRanges());
394 }
395 return false;
396 }
397
398 @Override
399 public String toString() {
400 return asMapOfRanges().toString();
401 }
402
403 /**
404 * This class is used to serialize ImmutableRangeMap instances. Serializes the {@link
405 * #asMapOfRanges()} form.
406 */
407 private static class SerializedForm<K extends Comparable<?>, V> implements Serializable {
408
409 private final ImmutableMap<Range<K>, V> mapOfRanges;
410
411 SerializedForm(ImmutableMap<Range<K>, V> mapOfRanges) {
412 this.mapOfRanges = mapOfRanges;
413 }
414
415 Object readResolve() {
416 if (mapOfRanges.isEmpty()) {
417 return of();
418 } else {
419 return createRangeMap();
420 }
421 }
422
423 Object createRangeMap() {
424 Builder<K, V> builder = new Builder<>();
425 for (Entry<Range<K>, V> entry : mapOfRanges.entrySet()) {
426 builder.put(entry.getKey(), entry.getValue());
427 }
428 return builder.build();
429 }
430
431 private static final long serialVersionUID = 0;
432 }
433
434 Object writeReplace() {
435 return new SerializedForm<>(asMapOfRanges());
436 }
437
438 private static final long serialVersionUID = 0;
439 }