1
2
3
4
5
6
7
8
9
10
11
12
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
26 import java.util.Map;
27 import java.util.Map.Entry;
28 import java.util.NoSuchElementException;
29
30 import javax.annotation.Nullable;
31
32
33
34
35
36
37
38
39
40 @Beta
41 @GwtIncompatible("NavigableMap")
42 public class ImmutableRangeMap<K extends Comparable<?>, V> implements RangeMap<K, V> {
43
44 private static final ImmutableRangeMap<Comparable<?>, Object> EMPTY =
45 new ImmutableRangeMap<Comparable<?>, Object>(
46 ImmutableList.<Range<Comparable<?>>>of(), ImmutableList.of());
47
48
49
50
51 @SuppressWarnings("unchecked")
52 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of() {
53 return (ImmutableRangeMap<K, V>) EMPTY;
54 }
55
56
57
58
59 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> of(
60 Range<K> range, V value) {
61 return new ImmutableRangeMap<K, V>(ImmutableList.of(range), ImmutableList.of(value));
62 }
63
64 @SuppressWarnings("unchecked")
65 public static <K extends Comparable<?>, V> ImmutableRangeMap<K, V> copyOf(
66 RangeMap<K, ? extends V> rangeMap) {
67 if (rangeMap instanceof ImmutableRangeMap) {
68 return (ImmutableRangeMap<K, V>) rangeMap;
69 }
70 Map<Range<K>, ? extends V> map = rangeMap.asMapOfRanges();
71 ImmutableList.Builder<Range<K>> rangesBuilder = new ImmutableList.Builder<Range<K>>(map.size());
72 ImmutableList.Builder<V> valuesBuilder = new ImmutableList.Builder<V>(map.size());
73 for (Entry<Range<K>, ? extends V> entry : map.entrySet()) {
74 rangesBuilder.add(entry.getKey());
75 valuesBuilder.add(entry.getValue());
76 }
77 return new ImmutableRangeMap<K, V>(rangesBuilder.build(), valuesBuilder.build());
78 }
79
80
81
82
83 public static <K extends Comparable<?>, V> Builder<K, V> builder() {
84 return new Builder<K, V>();
85 }
86
87
88
89
90 public static final class Builder<K extends Comparable<?>, V> {
91 private final RangeSet<K> keyRanges;
92 private final RangeMap<K, V> rangeMap;
93
94 public Builder() {
95 this.keyRanges = TreeRangeSet.create();
96 this.rangeMap = TreeRangeMap.create();
97 }
98
99
100
101
102
103
104
105 public Builder<K, V> put(Range<K> range, V value) {
106 checkNotNull(range);
107 checkNotNull(value);
108 checkArgument(!range.isEmpty(), "Range must not be empty, but was %s", range);
109 if (!keyRanges.complement().encloses(range)) {
110
111 for (Entry<Range<K>, V> entry : rangeMap.asMapOfRanges().entrySet()) {
112 Range<K> key = entry.getKey();
113 if (key.isConnected(range) && !key.intersection(range).isEmpty()) {
114 throw new IllegalArgumentException(
115 "Overlapping ranges: range " + range + " overlaps with entry " + entry);
116 }
117 }
118 }
119 keyRanges.add(range);
120 rangeMap.put(range, value);
121 return this;
122 }
123
124
125
126
127
128
129
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
139
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 ImmutableList<Range<K>> ranges;
155 private final 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 = SortedLists.binarySearch(ranges, Range.<K>lowerBoundFn(),
166 Cut.belowValue(key), KeyPresentBehavior.ANY_PRESENT, 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 = SortedLists.binarySearch(ranges, Range.<K>lowerBoundFn(),
179 Cut.belowValue(key), KeyPresentBehavior.ANY_PRESENT, KeyAbsentBehavior.NEXT_LOWER);
180 if (index == -1) {
181 return null;
182 } else {
183 Range<K> range = ranges.get(index);
184 return range.contains(key) ? Maps.immutableEntry(range, values.get(index)) : null;
185 }
186 }
187
188 @Override
189 public Range<K> span() {
190 if (ranges.isEmpty()) {
191 throw new NoSuchElementException();
192 }
193 Range<K> firstRange = ranges.get(0);
194 Range<K> lastRange = ranges.get(ranges.size() - 1);
195 return Range.create(firstRange.lowerBound, lastRange.upperBound);
196 }
197
198 @Override
199 public void put(Range<K> range, V value) {
200 throw new UnsupportedOperationException();
201 }
202
203 @Override
204 public void putAll(RangeMap<K, V> rangeMap) {
205 throw new UnsupportedOperationException();
206 }
207
208 @Override
209 public void clear() {
210 throw new UnsupportedOperationException();
211 }
212
213 @Override
214 public void remove(Range<K> range) {
215 throw new UnsupportedOperationException();
216 }
217
218 @Override
219 public ImmutableMap<Range<K>, V> asMapOfRanges() {
220 if (ranges.isEmpty()) {
221 return ImmutableMap.of();
222 }
223 RegularImmutableSortedSet<Range<K>> rangeSet =
224 new RegularImmutableSortedSet<Range<K>>(ranges, Range.RANGE_LEX_ORDERING);
225 return new RegularImmutableSortedMap<Range<K>, V>(rangeSet, values);
226 }
227
228 @Override
229 public ImmutableRangeMap<K, V> subRangeMap(final Range<K> range) {
230 if (checkNotNull(range).isEmpty()) {
231 return ImmutableRangeMap.of();
232 } else if (ranges.isEmpty() || range.encloses(span())) {
233 return this;
234 }
235 int lowerIndex = SortedLists.binarySearch(
236 ranges, Range.<K>upperBoundFn(), range.lowerBound,
237 KeyPresentBehavior.FIRST_AFTER, KeyAbsentBehavior.NEXT_HIGHER);
238 int upperIndex = SortedLists.binarySearch(ranges,
239 Range.<K>lowerBoundFn(), range.upperBound,
240 KeyPresentBehavior.ANY_PRESENT, KeyAbsentBehavior.NEXT_HIGHER);
241 if (lowerIndex >= upperIndex) {
242 return ImmutableRangeMap.of();
243 }
244 final int off = lowerIndex;
245 final int len = upperIndex - lowerIndex;
246 ImmutableList<Range<K>> subRanges = new ImmutableList<Range<K>>() {
247 @Override
248 public int size() {
249 return len;
250 }
251
252 @Override
253 public Range<K> get(int index) {
254 checkElementIndex(index, len);
255 if (index == 0 || index == len - 1) {
256 return ranges.get(index + off).intersection(range);
257 } else {
258 return ranges.get(index + off);
259 }
260 }
261
262 @Override
263 boolean isPartialView() {
264 return true;
265 }
266 };
267 final ImmutableRangeMap<K, V> outer = this;
268 return new ImmutableRangeMap<K, V>(
269 subRanges, values.subList(lowerIndex, upperIndex)) {
270 @Override
271 public ImmutableRangeMap<K, V> subRangeMap(Range<K> subRange) {
272 if (range.isConnected(subRange)) {
273 return outer.subRangeMap(subRange.intersection(range));
274 } else {
275 return ImmutableRangeMap.of();
276 }
277 }
278 };
279 }
280
281 @Override
282 public int hashCode() {
283 return asMapOfRanges().hashCode();
284 }
285
286 @Override
287 public boolean equals(@Nullable Object o) {
288 if (o instanceof RangeMap) {
289 RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o;
290 return asMapOfRanges().equals(rangeMap.asMapOfRanges());
291 }
292 return false;
293 }
294
295 @Override
296 public String toString() {
297 return asMapOfRanges().toString();
298 }
299 }