1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21 import static com.google.common.base.Predicates.compose;
22 import static com.google.common.base.Predicates.in;
23 import static com.google.common.base.Predicates.not;
24
25 import com.google.common.annotations.Beta;
26 import com.google.common.annotations.GwtIncompatible;
27 import com.google.common.base.Objects;
28 import com.google.common.base.Predicate;
29
30 import java.util.AbstractMap;
31 import java.util.AbstractSet;
32 import java.util.Collection;
33 import java.util.Collections;
34 import java.util.Iterator;
35 import java.util.List;
36 import java.util.Map;
37 import java.util.Map.Entry;
38 import java.util.NavigableMap;
39 import java.util.NoSuchElementException;
40 import java.util.Set;
41
42 import javax.annotation.Nullable;
43
44
45
46
47
48
49
50
51
52
53
54 @Beta
55 @GwtIncompatible("NavigableMap")
56 public final class TreeRangeMap<K extends Comparable, V> implements RangeMap<K, V> {
57
58 private final NavigableMap<Cut<K>, RangeMapEntry<K, V>> entriesByLowerBound;
59
60 public static <K extends Comparable, V> TreeRangeMap<K, V> create() {
61 return new TreeRangeMap<K, V>();
62 }
63
64 private TreeRangeMap() {
65 this.entriesByLowerBound = Maps.newTreeMap();
66 }
67
68 private static final class RangeMapEntry<K extends Comparable, V>
69 extends AbstractMapEntry<Range<K>, V> {
70 private final Range<K> range;
71 private final V value;
72
73 RangeMapEntry(Cut<K> lowerBound, Cut<K> upperBound, V value) {
74 this(Range.create(lowerBound, upperBound), value);
75 }
76
77 RangeMapEntry(Range<K> range, V value) {
78 this.range = range;
79 this.value = value;
80 }
81
82 @Override
83 public Range<K> getKey() {
84 return range;
85 }
86
87 @Override
88 public V getValue() {
89 return value;
90 }
91
92 public boolean contains(K value) {
93 return range.contains(value);
94 }
95
96 Cut<K> getLowerBound() {
97 return range.lowerBound;
98 }
99
100 Cut<K> getUpperBound() {
101 return range.upperBound;
102 }
103 }
104
105 @Override
106 @Nullable
107 public V get(K key) {
108 Entry<Range<K>, V> entry = getEntry(key);
109 return (entry == null) ? null : entry.getValue();
110 }
111
112 @Override
113 @Nullable
114 public Entry<Range<K>, V> getEntry(K key) {
115 Map.Entry<Cut<K>, RangeMapEntry<K, V>> mapEntry =
116 entriesByLowerBound.floorEntry(Cut.belowValue(key));
117 if (mapEntry != null && mapEntry.getValue().contains(key)) {
118 return mapEntry.getValue();
119 } else {
120 return null;
121 }
122 }
123
124 @Override
125 public void put(Range<K> range, V value) {
126 if (!range.isEmpty()) {
127 checkNotNull(value);
128 remove(range);
129 entriesByLowerBound.put(range.lowerBound, new RangeMapEntry<K, V>(range, value));
130 }
131 }
132
133 @Override
134 public void putAll(RangeMap<K, V> rangeMap) {
135 for (Map.Entry<Range<K>, V> entry : rangeMap.asMapOfRanges().entrySet()) {
136 put(entry.getKey(), entry.getValue());
137 }
138 }
139
140 @Override
141 public void clear() {
142 entriesByLowerBound.clear();
143 }
144
145 @Override
146 public Range<K> span() {
147 Entry<Cut<K>, RangeMapEntry<K, V>> firstEntry = entriesByLowerBound.firstEntry();
148 Entry<Cut<K>, RangeMapEntry<K, V>> lastEntry = entriesByLowerBound.lastEntry();
149 if (firstEntry == null) {
150 throw new NoSuchElementException();
151 }
152 return Range.create(
153 firstEntry.getValue().getKey().lowerBound,
154 lastEntry.getValue().getKey().upperBound);
155 }
156
157 private void putRangeMapEntry(Cut<K> lowerBound, Cut<K> upperBound, V value) {
158 entriesByLowerBound.put(lowerBound, new RangeMapEntry<K, V>(lowerBound, upperBound, value));
159 }
160
161 @Override
162 public void remove(Range<K> rangeToRemove) {
163 if (rangeToRemove.isEmpty()) {
164 return;
165 }
166
167
168
169
170
171 Map.Entry<Cut<K>, RangeMapEntry<K, V>> mapEntryBelowToTruncate =
172 entriesByLowerBound.lowerEntry(rangeToRemove.lowerBound);
173 if (mapEntryBelowToTruncate != null) {
174
175 RangeMapEntry<K, V> rangeMapEntry = mapEntryBelowToTruncate.getValue();
176 if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.lowerBound) > 0) {
177
178 if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.upperBound) > 0) {
179
180
181 putRangeMapEntry(rangeToRemove.upperBound, rangeMapEntry.getUpperBound(),
182 mapEntryBelowToTruncate.getValue().getValue());
183 }
184
185 putRangeMapEntry(rangeMapEntry.getLowerBound(), rangeToRemove.lowerBound,
186 mapEntryBelowToTruncate.getValue().getValue());
187 }
188 }
189
190 Map.Entry<Cut<K>, RangeMapEntry<K, V>> mapEntryAboveToTruncate =
191 entriesByLowerBound.lowerEntry(rangeToRemove.upperBound);
192 if (mapEntryAboveToTruncate != null) {
193
194 RangeMapEntry<K, V> rangeMapEntry = mapEntryAboveToTruncate.getValue();
195 if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.upperBound) > 0) {
196
197
198 putRangeMapEntry(rangeToRemove.upperBound, rangeMapEntry.getUpperBound(),
199 mapEntryAboveToTruncate.getValue().getValue());
200 entriesByLowerBound.remove(rangeToRemove.lowerBound);
201 }
202 }
203 entriesByLowerBound.subMap(rangeToRemove.lowerBound, rangeToRemove.upperBound).clear();
204 }
205
206 @Override
207 public Map<Range<K>, V> asMapOfRanges() {
208 return new AsMapOfRanges();
209 }
210
211 private final class AsMapOfRanges extends AbstractMap<Range<K>, V> {
212
213 @Override
214 public boolean containsKey(@Nullable Object key) {
215 return get(key) != null;
216 }
217
218 @Override
219 public V get(@Nullable Object key) {
220 if (key instanceof Range) {
221 Range<?> range = (Range<?>) key;
222 RangeMapEntry<K, V> rangeMapEntry = entriesByLowerBound.get(range.lowerBound);
223 if (rangeMapEntry != null && rangeMapEntry.getKey().equals(range)) {
224 return rangeMapEntry.getValue();
225 }
226 }
227 return null;
228 }
229
230 @Override
231 public Set<Entry<Range<K>, V>> entrySet() {
232 return new AbstractSet<Entry<Range<K>, V>>() {
233
234 @SuppressWarnings("unchecked")
235 @Override
236 public Iterator<Entry<Range<K>, V>> iterator() {
237 return (Iterator) entriesByLowerBound.values().iterator();
238 }
239
240 @Override
241 public int size() {
242 return entriesByLowerBound.size();
243 }
244 };
245 }
246 }
247
248 @Override
249 public RangeMap<K, V> subRangeMap(Range<K> subRange) {
250 if (subRange.equals(Range.all())) {
251 return this;
252 } else {
253 return new SubRangeMap(subRange);
254 }
255 }
256
257 @SuppressWarnings("unchecked")
258 private RangeMap<K, V> emptySubRangeMap() {
259 return EMPTY_SUB_RANGE_MAP;
260 }
261
262 private static final RangeMap EMPTY_SUB_RANGE_MAP =
263 new RangeMap() {
264 @Override
265 @Nullable
266 public Object get(Comparable key) {
267 return null;
268 }
269
270 @Override
271 @Nullable
272 public Entry<Range, Object> getEntry(Comparable key) {
273 return null;
274 }
275
276 @Override
277 public Range span() {
278 throw new NoSuchElementException();
279 }
280
281 @Override
282 public void put(Range range, Object value) {
283 checkNotNull(range);
284 throw new IllegalArgumentException(
285 "Cannot insert range " + range + " into an empty subRangeMap");
286 }
287
288 @Override
289 public void putAll(RangeMap rangeMap) {
290 if (!rangeMap.asMapOfRanges().isEmpty()) {
291 throw new IllegalArgumentException(
292 "Cannot putAll(nonEmptyRangeMap) into an empty " + "subRangeMap");
293 }
294 }
295
296 @Override
297 public void clear() {}
298
299 @Override
300 public void remove(Range range) {
301 checkNotNull(range);
302 }
303
304 @Override
305 public Map<Range, Object> asMapOfRanges() {
306 return Collections.emptyMap();
307 }
308
309 @Override
310 public RangeMap subRangeMap(Range range) {
311 checkNotNull(range);
312 return this;
313 }
314 };
315
316 private class SubRangeMap implements RangeMap<K, V> {
317
318 private final Range<K> subRange;
319
320 SubRangeMap(Range<K> subRange) {
321 this.subRange = subRange;
322 }
323
324 @Override
325 @Nullable
326 public V get(K key) {
327 return subRange.contains(key)
328 ? TreeRangeMap.this.get(key)
329 : null;
330 }
331
332 @Override
333 @Nullable
334 public Entry<Range<K>, V> getEntry(K key) {
335 if (subRange.contains(key)) {
336 Entry<Range<K>, V> entry = TreeRangeMap.this.getEntry(key);
337 if (entry != null) {
338 return Maps.immutableEntry(entry.getKey().intersection(subRange), entry.getValue());
339 }
340 }
341 return null;
342 }
343
344 @Override
345 public Range<K> span() {
346 Cut<K> lowerBound;
347 Entry<Cut<K>, RangeMapEntry<K, V>> lowerEntry =
348 entriesByLowerBound.floorEntry(subRange.lowerBound);
349 if (lowerEntry != null &&
350 lowerEntry.getValue().getUpperBound().compareTo(subRange.lowerBound) > 0) {
351 lowerBound = subRange.lowerBound;
352 } else {
353 lowerBound = entriesByLowerBound.ceilingKey(subRange.lowerBound);
354 if (lowerBound == null || lowerBound.compareTo(subRange.upperBound) >= 0) {
355 throw new NoSuchElementException();
356 }
357 }
358
359 Cut<K> upperBound;
360 Entry<Cut<K>, RangeMapEntry<K, V>> upperEntry =
361 entriesByLowerBound.lowerEntry(subRange.upperBound);
362 if (upperEntry == null) {
363 throw new NoSuchElementException();
364 } else if (upperEntry.getValue().getUpperBound().compareTo(subRange.upperBound) >= 0) {
365 upperBound = subRange.upperBound;
366 } else {
367 upperBound = upperEntry.getValue().getUpperBound();
368 }
369 return Range.create(lowerBound, upperBound);
370 }
371
372 @Override
373 public void put(Range<K> range, V value) {
374 checkArgument(subRange.encloses(range),
375 "Cannot put range %s into a subRangeMap(%s)", range, subRange);
376 TreeRangeMap.this.put(range, value);
377 }
378
379 @Override
380 public void putAll(RangeMap<K, V> rangeMap) {
381 if (rangeMap.asMapOfRanges().isEmpty()) {
382 return;
383 }
384 Range<K> span = rangeMap.span();
385 checkArgument(subRange.encloses(span),
386 "Cannot putAll rangeMap with span %s into a subRangeMap(%s)", span, subRange);
387 TreeRangeMap.this.putAll(rangeMap);
388 }
389
390 @Override
391 public void clear() {
392 TreeRangeMap.this.remove(subRange);
393 }
394
395 @Override
396 public void remove(Range<K> range) {
397 if (range.isConnected(subRange)) {
398 TreeRangeMap.this.remove(range.intersection(subRange));
399 }
400 }
401
402 @Override
403 public RangeMap<K, V> subRangeMap(Range<K> range) {
404 if (!range.isConnected(subRange)) {
405 return emptySubRangeMap();
406 } else {
407 return TreeRangeMap.this.subRangeMap(range.intersection(subRange));
408 }
409 }
410
411 @Override
412 public Map<Range<K>, V> asMapOfRanges() {
413 return new SubRangeMapAsMap();
414 }
415
416 @Override
417 public boolean equals(@Nullable Object o) {
418 if (o instanceof RangeMap) {
419 RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o;
420 return asMapOfRanges().equals(rangeMap.asMapOfRanges());
421 }
422 return false;
423 }
424
425 @Override
426 public int hashCode() {
427 return asMapOfRanges().hashCode();
428 }
429
430 @Override
431 public String toString() {
432 return asMapOfRanges().toString();
433 }
434
435 class SubRangeMapAsMap extends AbstractMap<Range<K>, V> {
436
437 @Override
438 public boolean containsKey(Object key) {
439 return get(key) != null;
440 }
441
442 @Override
443 public V get(Object key) {
444 try {
445 if (key instanceof Range) {
446 @SuppressWarnings("unchecked")
447 Range<K> r = (Range<K>) key;
448 if (!subRange.encloses(r) || r.isEmpty()) {
449 return null;
450 }
451 RangeMapEntry<K, V> candidate = null;
452 if (r.lowerBound.compareTo(subRange.lowerBound) == 0) {
453
454 Entry<Cut<K>, RangeMapEntry<K, V>> entry =
455 entriesByLowerBound.floorEntry(r.lowerBound);
456 if (entry != null) {
457 candidate = entry.getValue();
458 }
459 } else {
460 candidate = entriesByLowerBound.get(r.lowerBound);
461 }
462
463 if (candidate != null && candidate.getKey().isConnected(subRange)
464 && candidate.getKey().intersection(subRange).equals(r)) {
465 return candidate.getValue();
466 }
467 }
468 } catch (ClassCastException e) {
469 return null;
470 }
471 return null;
472 }
473
474 @Override
475 public V remove(Object key) {
476 V value = get(key);
477 if (value != null) {
478 @SuppressWarnings("unchecked")
479 Range<K> range = (Range<K>) key;
480 TreeRangeMap.this.remove(range);
481 return value;
482 }
483 return null;
484 }
485
486 @Override
487 public void clear() {
488 SubRangeMap.this.clear();
489 }
490
491 private boolean removeEntryIf(Predicate<? super Entry<Range<K>, V>> predicate) {
492 List<Range<K>> toRemove = Lists.newArrayList();
493 for (Entry<Range<K>, V> entry : entrySet()) {
494 if (predicate.apply(entry)) {
495 toRemove.add(entry.getKey());
496 }
497 }
498 for (Range<K> range : toRemove) {
499 TreeRangeMap.this.remove(range);
500 }
501 return !toRemove.isEmpty();
502 }
503
504 @Override
505 public Set<Range<K>> keySet() {
506 return new Maps.KeySet<Range<K>, V>(SubRangeMapAsMap.this) {
507 @Override
508 public boolean remove(@Nullable Object o) {
509 return SubRangeMapAsMap.this.remove(o) != null;
510 }
511
512 @Override
513 public boolean retainAll(Collection<?> c) {
514 return removeEntryIf(compose(not(in(c)), Maps.<Range<K>>keyFunction()));
515 }
516 };
517 }
518
519 @Override
520 public Set<Entry<Range<K>, V>> entrySet() {
521 return new Maps.EntrySet<Range<K>, V>() {
522 @Override
523 Map<Range<K>, V> map() {
524 return SubRangeMapAsMap.this;
525 }
526
527 @Override
528 public Iterator<Entry<Range<K>, V>> iterator() {
529 if (subRange.isEmpty()) {
530 return Iterators.emptyIterator();
531 }
532 Cut<K> cutToStart = Objects.firstNonNull(
533 entriesByLowerBound.floorKey(subRange.lowerBound),
534 subRange.lowerBound);
535 final Iterator<RangeMapEntry<K, V>> backingItr =
536 entriesByLowerBound.tailMap(cutToStart, true).values().iterator();
537 return new AbstractIterator<Entry<Range<K>, V>>() {
538
539 @Override
540 protected Entry<Range<K>, V> computeNext() {
541 while (backingItr.hasNext()) {
542 RangeMapEntry<K, V> entry = backingItr.next();
543 if (entry.getLowerBound().compareTo(subRange.upperBound) >= 0) {
544 break;
545 } else if (entry.getUpperBound().compareTo(subRange.lowerBound) > 0) {
546
547 return Maps.immutableEntry(
548 entry.getKey().intersection(subRange), entry.getValue());
549 }
550 }
551 return endOfData();
552 }
553 };
554 }
555
556 @Override
557 public boolean retainAll(Collection<?> c) {
558 return removeEntryIf(not(in(c)));
559 }
560
561 @Override
562 public int size() {
563 return Iterators.size(iterator());
564 }
565
566 @Override
567 public boolean isEmpty() {
568 return !iterator().hasNext();
569 }
570 };
571 }
572
573 @Override
574 public Collection<V> values() {
575 return new Maps.Values<Range<K>, V>(this) {
576 @Override
577 public boolean removeAll(Collection<?> c) {
578 return removeEntryIf(compose(in(c), Maps.<V>valueFunction()));
579 }
580
581 @Override
582 public boolean retainAll(Collection<?> c) {
583 return removeEntryIf(compose(not(in(c)), Maps.<V>valueFunction()));
584 }
585 };
586 }
587 }
588 }
589
590 @Override
591 public boolean equals(@Nullable Object o) {
592 if (o instanceof RangeMap) {
593 RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o;
594 return asMapOfRanges().equals(rangeMap.asMapOfRanges());
595 }
596 return false;
597 }
598
599 @Override
600 public int hashCode() {
601 return asMapOfRanges().hashCode();
602 }
603
604 @Override
605 public String toString() {
606 return entriesByLowerBound.values().toString();
607 }
608 }