1 /*
2 * Copyright (C) 2011 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.checkNotNull;
19
20 import com.google.common.annotations.Beta;
21 import com.google.common.annotations.GwtIncompatible;
22 import com.google.common.annotations.VisibleForTesting;
23 import com.google.common.base.MoreObjects;
24 import java.io.Serializable;
25 import java.util.Collection;
26 import java.util.Comparator;
27 import java.util.Iterator;
28 import java.util.Map.Entry;
29 import java.util.NavigableMap;
30 import java.util.NoSuchElementException;
31 import java.util.Set;
32 import java.util.TreeMap;
33 import org.checkerframework.checker.nullness.qual.Nullable;
34
35 /**
36 * An implementation of {@link RangeSet} backed by a {@link TreeMap}.
37 *
38 * @author Louis Wasserman
39 * @since 14.0
40 */
41 @Beta
42 @GwtIncompatible // uses NavigableMap
43 public class TreeRangeSet<C extends Comparable<?>> extends AbstractRangeSet<C>
44 implements Serializable {
45
46 @VisibleForTesting final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;
47
48 /** Creates an empty {@code TreeRangeSet} instance. */
49 public static <C extends Comparable<?>> TreeRangeSet<C> create() {
50 return new TreeRangeSet<C>(new TreeMap<Cut<C>, Range<C>>());
51 }
52
53 /** Returns a {@code TreeRangeSet} initialized with the ranges in the specified range set. */
54 public static <C extends Comparable<?>> TreeRangeSet<C> create(RangeSet<C> rangeSet) {
55 TreeRangeSet<C> result = create();
56 result.addAll(rangeSet);
57 return result;
58 }
59
60 /**
61 * Returns a {@code TreeRangeSet} representing the union of the specified ranges.
62 *
63 * <p>This is the smallest {@code RangeSet} which encloses each of the specified ranges. An
64 * element will be contained in this {@code RangeSet} if and only if it is contained in at least
65 * one {@code Range} in {@code ranges}.
66 *
67 * @since 21.0
68 */
69 public static <C extends Comparable<?>> TreeRangeSet<C> create(Iterable<Range<C>> ranges) {
70 TreeRangeSet<C> result = create();
71 result.addAll(ranges);
72 return result;
73 }
74
75 private TreeRangeSet(NavigableMap<Cut<C>, Range<C>> rangesByLowerCut) {
76 this.rangesByLowerBound = rangesByLowerCut;
77 }
78
79 private transient @Nullable Set<Range<C>> asRanges;
80 private transient @Nullable Set<Range<C>> asDescendingSetOfRanges;
81
82 @Override
83 public Set<Range<C>> asRanges() {
84 Set<Range<C>> result = asRanges;
85 return (result == null) ? asRanges = new AsRanges(rangesByLowerBound.values()) : result;
86 }
87
88 @Override
89 public Set<Range<C>> asDescendingSetOfRanges() {
90 Set<Range<C>> result = asDescendingSetOfRanges;
91 return (result == null)
92 ? asDescendingSetOfRanges = new AsRanges(rangesByLowerBound.descendingMap().values())
93 : result;
94 }
95
96 final class AsRanges extends ForwardingCollection<Range<C>> implements Set<Range<C>> {
97
98 final Collection<Range<C>> delegate;
99
100 AsRanges(Collection<Range<C>> delegate) {
101 this.delegate = delegate;
102 }
103
104 @Override
105 protected Collection<Range<C>> delegate() {
106 return delegate;
107 }
108
109 @Override
110 public int hashCode() {
111 return Sets.hashCodeImpl(this);
112 }
113
114 @Override
115 public boolean equals(@Nullable Object o) {
116 return Sets.equalsImpl(this, o);
117 }
118 }
119
120 @Override
121 public @Nullable Range<C> rangeContaining(C value) {
122 checkNotNull(value);
123 Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(Cut.belowValue(value));
124 if (floorEntry != null && floorEntry.getValue().contains(value)) {
125 return floorEntry.getValue();
126 } else {
127 // TODO(kevinb): revisit this design choice
128 return null;
129 }
130 }
131
132 @Override
133 public boolean intersects(Range<C> range) {
134 checkNotNull(range);
135 Entry<Cut<C>, Range<C>> ceilingEntry = rangesByLowerBound.ceilingEntry(range.lowerBound);
136 if (ceilingEntry != null
137 && ceilingEntry.getValue().isConnected(range)
138 && !ceilingEntry.getValue().intersection(range).isEmpty()) {
139 return true;
140 }
141 Entry<Cut<C>, Range<C>> priorEntry = rangesByLowerBound.lowerEntry(range.lowerBound);
142 return priorEntry != null
143 && priorEntry.getValue().isConnected(range)
144 && !priorEntry.getValue().intersection(range).isEmpty();
145 }
146
147 @Override
148 public boolean encloses(Range<C> range) {
149 checkNotNull(range);
150 Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound);
151 return floorEntry != null && floorEntry.getValue().encloses(range);
152 }
153
154 private @Nullable Range<C> rangeEnclosing(Range<C> range) {
155 checkNotNull(range);
156 Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound);
157 return (floorEntry != null && floorEntry.getValue().encloses(range))
158 ? floorEntry.getValue()
159 : null;
160 }
161
162 @Override
163 public Range<C> span() {
164 Entry<Cut<C>, Range<C>> firstEntry = rangesByLowerBound.firstEntry();
165 Entry<Cut<C>, Range<C>> lastEntry = rangesByLowerBound.lastEntry();
166 if (firstEntry == null) {
167 throw new NoSuchElementException();
168 }
169 return Range.create(firstEntry.getValue().lowerBound, lastEntry.getValue().upperBound);
170 }
171
172 @Override
173 public void add(Range<C> rangeToAdd) {
174 checkNotNull(rangeToAdd);
175
176 if (rangeToAdd.isEmpty()) {
177 return;
178 }
179
180 // We will use { } to illustrate ranges currently in the range set, and < >
181 // to illustrate rangeToAdd.
182 Cut<C> lbToAdd = rangeToAdd.lowerBound;
183 Cut<C> ubToAdd = rangeToAdd.upperBound;
184
185 Entry<Cut<C>, Range<C>> entryBelowLB = rangesByLowerBound.lowerEntry(lbToAdd);
186 if (entryBelowLB != null) {
187 // { <
188 Range<C> rangeBelowLB = entryBelowLB.getValue();
189 if (rangeBelowLB.upperBound.compareTo(lbToAdd) >= 0) {
190 // { < }, and we will need to coalesce
191 if (rangeBelowLB.upperBound.compareTo(ubToAdd) >= 0) {
192 // { < > }
193 ubToAdd = rangeBelowLB.upperBound;
194 /*
195 * TODO(cpovirk): can we just "return;" here? Or, can we remove this if() entirely? If
196 * not, add tests to demonstrate the problem with each approach
197 */
198 }
199 lbToAdd = rangeBelowLB.lowerBound;
200 }
201 }
202
203 Entry<Cut<C>, Range<C>> entryBelowUB = rangesByLowerBound.floorEntry(ubToAdd);
204 if (entryBelowUB != null) {
205 // { >
206 Range<C> rangeBelowUB = entryBelowUB.getValue();
207 if (rangeBelowUB.upperBound.compareTo(ubToAdd) >= 0) {
208 // { > }, and we need to coalesce
209 ubToAdd = rangeBelowUB.upperBound;
210 }
211 }
212
213 // Remove ranges which are strictly enclosed.
214 rangesByLowerBound.subMap(lbToAdd, ubToAdd).clear();
215
216 replaceRangeWithSameLowerBound(Range.create(lbToAdd, ubToAdd));
217 }
218
219 @Override
220 public void remove(Range<C> rangeToRemove) {
221 checkNotNull(rangeToRemove);
222
223 if (rangeToRemove.isEmpty()) {
224 return;
225 }
226
227 // We will use { } to illustrate ranges currently in the range set, and < >
228 // to illustrate rangeToRemove.
229
230 Entry<Cut<C>, Range<C>> entryBelowLB = rangesByLowerBound.lowerEntry(rangeToRemove.lowerBound);
231 if (entryBelowLB != null) {
232 // { <
233 Range<C> rangeBelowLB = entryBelowLB.getValue();
234 if (rangeBelowLB.upperBound.compareTo(rangeToRemove.lowerBound) >= 0) {
235 // { < }, and we will need to subdivide
236 if (rangeToRemove.hasUpperBound()
237 && rangeBelowLB.upperBound.compareTo(rangeToRemove.upperBound) >= 0) {
238 // { < > }
239 replaceRangeWithSameLowerBound(
240 Range.create(rangeToRemove.upperBound, rangeBelowLB.upperBound));
241 }
242 replaceRangeWithSameLowerBound(
243 Range.create(rangeBelowLB.lowerBound, rangeToRemove.lowerBound));
244 }
245 }
246
247 Entry<Cut<C>, Range<C>> entryBelowUB = rangesByLowerBound.floorEntry(rangeToRemove.upperBound);
248 if (entryBelowUB != null) {
249 // { >
250 Range<C> rangeBelowUB = entryBelowUB.getValue();
251 if (rangeToRemove.hasUpperBound()
252 && rangeBelowUB.upperBound.compareTo(rangeToRemove.upperBound) >= 0) {
253 // { > }
254 replaceRangeWithSameLowerBound(
255 Range.create(rangeToRemove.upperBound, rangeBelowUB.upperBound));
256 }
257 }
258
259 rangesByLowerBound.subMap(rangeToRemove.lowerBound, rangeToRemove.upperBound).clear();
260 }
261
262 private void replaceRangeWithSameLowerBound(Range<C> range) {
263 if (range.isEmpty()) {
264 rangesByLowerBound.remove(range.lowerBound);
265 } else {
266 rangesByLowerBound.put(range.lowerBound, range);
267 }
268 }
269
270 private transient @Nullable RangeSet<C> complement;
271
272 @Override
273 public RangeSet<C> complement() {
274 RangeSet<C> result = complement;
275 return (result == null) ? complement = new Complement() : result;
276 }
277
278 @VisibleForTesting
279 static final class RangesByUpperBound<C extends Comparable<?>>
280 extends AbstractNavigableMap<Cut<C>, Range<C>> {
281 private final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;
282
283 /**
284 * upperBoundWindow represents the headMap/subMap/tailMap view of the entire "ranges by upper
285 * bound" map; it's a constraint on the *keys*, and does not affect the values.
286 */
287 private final Range<Cut<C>> upperBoundWindow;
288
289 RangesByUpperBound(NavigableMap<Cut<C>, Range<C>> rangesByLowerBound) {
290 this.rangesByLowerBound = rangesByLowerBound;
291 this.upperBoundWindow = Range.all();
292 }
293
294 private RangesByUpperBound(
295 NavigableMap<Cut<C>, Range<C>> rangesByLowerBound, Range<Cut<C>> upperBoundWindow) {
296 this.rangesByLowerBound = rangesByLowerBound;
297 this.upperBoundWindow = upperBoundWindow;
298 }
299
300 private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> window) {
301 if (window.isConnected(upperBoundWindow)) {
302 return new RangesByUpperBound<C>(rangesByLowerBound, window.intersection(upperBoundWindow));
303 } else {
304 return ImmutableSortedMap.of();
305 }
306 }
307
308 @Override
309 public NavigableMap<Cut<C>, Range<C>> subMap(
310 Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) {
311 return subMap(
312 Range.range(
313 fromKey, BoundType.forBoolean(fromInclusive),
314 toKey, BoundType.forBoolean(toInclusive)));
315 }
316
317 @Override
318 public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) {
319 return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
320 }
321
322 @Override
323 public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) {
324 return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
325 }
326
327 @Override
328 public Comparator<? super Cut<C>> comparator() {
329 return Ordering.<Cut<C>>natural();
330 }
331
332 @Override
333 public boolean containsKey(@Nullable Object key) {
334 return get(key) != null;
335 }
336
337 @Override
338 public Range<C> get(@Nullable Object key) {
339 if (key instanceof Cut) {
340 try {
341 @SuppressWarnings("unchecked") // we catch CCEs
342 Cut<C> cut = (Cut<C>) key;
343 if (!upperBoundWindow.contains(cut)) {
344 return null;
345 }
346 Entry<Cut<C>, Range<C>> candidate = rangesByLowerBound.lowerEntry(cut);
347 if (candidate != null && candidate.getValue().upperBound.equals(cut)) {
348 return candidate.getValue();
349 }
350 } catch (ClassCastException e) {
351 return null;
352 }
353 }
354 return null;
355 }
356
357 @Override
358 Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
359 /*
360 * We want to start the iteration at the first range where the upper bound is in
361 * upperBoundWindow.
362 */
363 final Iterator<Range<C>> backingItr;
364 if (!upperBoundWindow.hasLowerBound()) {
365 backingItr = rangesByLowerBound.values().iterator();
366 } else {
367 Entry<Cut<C>, Range<C>> lowerEntry =
368 rangesByLowerBound.lowerEntry(upperBoundWindow.lowerEndpoint());
369 if (lowerEntry == null) {
370 backingItr = rangesByLowerBound.values().iterator();
371 } else if (upperBoundWindow.lowerBound.isLessThan(lowerEntry.getValue().upperBound)) {
372 backingItr = rangesByLowerBound.tailMap(lowerEntry.getKey(), true).values().iterator();
373 } else {
374 backingItr =
375 rangesByLowerBound
376 .tailMap(upperBoundWindow.lowerEndpoint(), true)
377 .values()
378 .iterator();
379 }
380 }
381 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
382 @Override
383 protected Entry<Cut<C>, Range<C>> computeNext() {
384 if (!backingItr.hasNext()) {
385 return endOfData();
386 }
387 Range<C> range = backingItr.next();
388 if (upperBoundWindow.upperBound.isLessThan(range.upperBound)) {
389 return endOfData();
390 } else {
391 return Maps.immutableEntry(range.upperBound, range);
392 }
393 }
394 };
395 }
396
397 @Override
398 Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
399 Collection<Range<C>> candidates;
400 if (upperBoundWindow.hasUpperBound()) {
401 candidates =
402 rangesByLowerBound
403 .headMap(upperBoundWindow.upperEndpoint(), false)
404 .descendingMap()
405 .values();
406 } else {
407 candidates = rangesByLowerBound.descendingMap().values();
408 }
409 final PeekingIterator<Range<C>> backingItr = Iterators.peekingIterator(candidates.iterator());
410 if (backingItr.hasNext()
411 && upperBoundWindow.upperBound.isLessThan(backingItr.peek().upperBound)) {
412 backingItr.next();
413 }
414 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
415 @Override
416 protected Entry<Cut<C>, Range<C>> computeNext() {
417 if (!backingItr.hasNext()) {
418 return endOfData();
419 }
420 Range<C> range = backingItr.next();
421 return upperBoundWindow.lowerBound.isLessThan(range.upperBound)
422 ? Maps.immutableEntry(range.upperBound, range)
423 : endOfData();
424 }
425 };
426 }
427
428 @Override
429 public int size() {
430 if (upperBoundWindow.equals(Range.all())) {
431 return rangesByLowerBound.size();
432 }
433 return Iterators.size(entryIterator());
434 }
435
436 @Override
437 public boolean isEmpty() {
438 return upperBoundWindow.equals(Range.all())
439 ? rangesByLowerBound.isEmpty()
440 : !entryIterator().hasNext();
441 }
442 }
443
444 private static final class ComplementRangesByLowerBound<C extends Comparable<?>>
445 extends AbstractNavigableMap<Cut<C>, Range<C>> {
446 private final NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound;
447 private final NavigableMap<Cut<C>, Range<C>> positiveRangesByUpperBound;
448
449 /**
450 * complementLowerBoundWindow represents the headMap/subMap/tailMap view of the entire
451 * "complement ranges by lower bound" map; it's a constraint on the *keys*, and does not affect
452 * the values.
453 */
454 private final Range<Cut<C>> complementLowerBoundWindow;
455
456 ComplementRangesByLowerBound(NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound) {
457 this(positiveRangesByLowerBound, Range.<Cut<C>>all());
458 }
459
460 private ComplementRangesByLowerBound(
461 NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound, Range<Cut<C>> window) {
462 this.positiveRangesByLowerBound = positiveRangesByLowerBound;
463 this.positiveRangesByUpperBound = new RangesByUpperBound<C>(positiveRangesByLowerBound);
464 this.complementLowerBoundWindow = window;
465 }
466
467 private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> subWindow) {
468 if (!complementLowerBoundWindow.isConnected(subWindow)) {
469 return ImmutableSortedMap.of();
470 } else {
471 subWindow = subWindow.intersection(complementLowerBoundWindow);
472 return new ComplementRangesByLowerBound<C>(positiveRangesByLowerBound, subWindow);
473 }
474 }
475
476 @Override
477 public NavigableMap<Cut<C>, Range<C>> subMap(
478 Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) {
479 return subMap(
480 Range.range(
481 fromKey, BoundType.forBoolean(fromInclusive),
482 toKey, BoundType.forBoolean(toInclusive)));
483 }
484
485 @Override
486 public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) {
487 return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
488 }
489
490 @Override
491 public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) {
492 return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
493 }
494
495 @Override
496 public Comparator<? super Cut<C>> comparator() {
497 return Ordering.<Cut<C>>natural();
498 }
499
500 @Override
501 Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
502 /*
503 * firstComplementRangeLowerBound is the first complement range lower bound inside
504 * complementLowerBoundWindow. Complement range lower bounds are either positive range upper
505 * bounds, or Cut.belowAll().
506 *
507 * positiveItr starts at the first positive range with lower bound greater than
508 * firstComplementRangeLowerBound. (Positive range lower bounds correspond to complement range
509 * upper bounds.)
510 */
511 Collection<Range<C>> positiveRanges;
512 if (complementLowerBoundWindow.hasLowerBound()) {
513 positiveRanges =
514 positiveRangesByUpperBound
515 .tailMap(
516 complementLowerBoundWindow.lowerEndpoint(),
517 complementLowerBoundWindow.lowerBoundType() == BoundType.CLOSED)
518 .values();
519 } else {
520 positiveRanges = positiveRangesByUpperBound.values();
521 }
522 final PeekingIterator<Range<C>> positiveItr =
523 Iterators.peekingIterator(positiveRanges.iterator());
524 final Cut<C> firstComplementRangeLowerBound;
525 if (complementLowerBoundWindow.contains(Cut.<C>belowAll())
526 && (!positiveItr.hasNext() || positiveItr.peek().lowerBound != Cut.<C>belowAll())) {
527 firstComplementRangeLowerBound = Cut.belowAll();
528 } else if (positiveItr.hasNext()) {
529 firstComplementRangeLowerBound = positiveItr.next().upperBound;
530 } else {
531 return Iterators.emptyIterator();
532 }
533 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
534 Cut<C> nextComplementRangeLowerBound = firstComplementRangeLowerBound;
535
536 @Override
537 protected Entry<Cut<C>, Range<C>> computeNext() {
538 if (complementLowerBoundWindow.upperBound.isLessThan(nextComplementRangeLowerBound)
539 || nextComplementRangeLowerBound == Cut.<C>aboveAll()) {
540 return endOfData();
541 }
542 Range<C> negativeRange;
543 if (positiveItr.hasNext()) {
544 Range<C> positiveRange = positiveItr.next();
545 negativeRange = Range.create(nextComplementRangeLowerBound, positiveRange.lowerBound);
546 nextComplementRangeLowerBound = positiveRange.upperBound;
547 } else {
548 negativeRange = Range.create(nextComplementRangeLowerBound, Cut.<C>aboveAll());
549 nextComplementRangeLowerBound = Cut.aboveAll();
550 }
551 return Maps.immutableEntry(negativeRange.lowerBound, negativeRange);
552 }
553 };
554 }
555
556 @Override
557 Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
558 /*
559 * firstComplementRangeUpperBound is the upper bound of the last complement range with lower
560 * bound inside complementLowerBoundWindow.
561 *
562 * positiveItr starts at the first positive range with upper bound less than
563 * firstComplementRangeUpperBound. (Positive range upper bounds correspond to complement range
564 * lower bounds.)
565 */
566 Cut<C> startingPoint =
567 complementLowerBoundWindow.hasUpperBound()
568 ? complementLowerBoundWindow.upperEndpoint()
569 : Cut.<C>aboveAll();
570 boolean inclusive =
571 complementLowerBoundWindow.hasUpperBound()
572 && complementLowerBoundWindow.upperBoundType() == BoundType.CLOSED;
573 final PeekingIterator<Range<C>> positiveItr =
574 Iterators.peekingIterator(
575 positiveRangesByUpperBound
576 .headMap(startingPoint, inclusive)
577 .descendingMap()
578 .values()
579 .iterator());
580 Cut<C> cut;
581 if (positiveItr.hasNext()) {
582 cut =
583 (positiveItr.peek().upperBound == Cut.<C>aboveAll())
584 ? positiveItr.next().lowerBound
585 : positiveRangesByLowerBound.higherKey(positiveItr.peek().upperBound);
586 } else if (!complementLowerBoundWindow.contains(Cut.<C>belowAll())
587 || positiveRangesByLowerBound.containsKey(Cut.belowAll())) {
588 return Iterators.emptyIterator();
589 } else {
590 cut = positiveRangesByLowerBound.higherKey(Cut.<C>belowAll());
591 }
592 final Cut<C> firstComplementRangeUpperBound =
593 MoreObjects.firstNonNull(cut, Cut.<C>aboveAll());
594 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
595 Cut<C> nextComplementRangeUpperBound = firstComplementRangeUpperBound;
596
597 @Override
598 protected Entry<Cut<C>, Range<C>> computeNext() {
599 if (nextComplementRangeUpperBound == Cut.<C>belowAll()) {
600 return endOfData();
601 } else if (positiveItr.hasNext()) {
602 Range<C> positiveRange = positiveItr.next();
603 Range<C> negativeRange =
604 Range.create(positiveRange.upperBound, nextComplementRangeUpperBound);
605 nextComplementRangeUpperBound = positiveRange.lowerBound;
606 if (complementLowerBoundWindow.lowerBound.isLessThan(negativeRange.lowerBound)) {
607 return Maps.immutableEntry(negativeRange.lowerBound, negativeRange);
608 }
609 } else if (complementLowerBoundWindow.lowerBound.isLessThan(Cut.<C>belowAll())) {
610 Range<C> negativeRange = Range.create(Cut.<C>belowAll(), nextComplementRangeUpperBound);
611 nextComplementRangeUpperBound = Cut.belowAll();
612 return Maps.immutableEntry(Cut.<C>belowAll(), negativeRange);
613 }
614 return endOfData();
615 }
616 };
617 }
618
619 @Override
620 public int size() {
621 return Iterators.size(entryIterator());
622 }
623
624 @Override
625 public @Nullable Range<C> get(Object key) {
626 if (key instanceof Cut) {
627 try {
628 @SuppressWarnings("unchecked")
629 Cut<C> cut = (Cut<C>) key;
630 // tailMap respects the current window
631 Entry<Cut<C>, Range<C>> firstEntry = tailMap(cut, true).firstEntry();
632 if (firstEntry != null && firstEntry.getKey().equals(cut)) {
633 return firstEntry.getValue();
634 }
635 } catch (ClassCastException e) {
636 return null;
637 }
638 }
639 return null;
640 }
641
642 @Override
643 public boolean containsKey(Object key) {
644 return get(key) != null;
645 }
646 }
647
648 private final class Complement extends TreeRangeSet<C> {
649 Complement() {
650 super(new ComplementRangesByLowerBound<C>(TreeRangeSet.this.rangesByLowerBound));
651 }
652
653 @Override
654 public void add(Range<C> rangeToAdd) {
655 TreeRangeSet.this.remove(rangeToAdd);
656 }
657
658 @Override
659 public void remove(Range<C> rangeToRemove) {
660 TreeRangeSet.this.add(rangeToRemove);
661 }
662
663 @Override
664 public boolean contains(C value) {
665 return !TreeRangeSet.this.contains(value);
666 }
667
668 @Override
669 public RangeSet<C> complement() {
670 return TreeRangeSet.this;
671 }
672 }
673
674 private static final class SubRangeSetRangesByLowerBound<C extends Comparable<?>>
675 extends AbstractNavigableMap<Cut<C>, Range<C>> {
676 /**
677 * lowerBoundWindow is the headMap/subMap/tailMap view; it only restricts the keys, and does not
678 * affect the values.
679 */
680 private final Range<Cut<C>> lowerBoundWindow;
681
682 /**
683 * restriction is the subRangeSet view; ranges are truncated to their intersection with
684 * restriction.
685 */
686 private final Range<C> restriction;
687
688 private final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;
689 private final NavigableMap<Cut<C>, Range<C>> rangesByUpperBound;
690
691 private SubRangeSetRangesByLowerBound(
692 Range<Cut<C>> lowerBoundWindow,
693 Range<C> restriction,
694 NavigableMap<Cut<C>, Range<C>> rangesByLowerBound) {
695 this.lowerBoundWindow = checkNotNull(lowerBoundWindow);
696 this.restriction = checkNotNull(restriction);
697 this.rangesByLowerBound = checkNotNull(rangesByLowerBound);
698 this.rangesByUpperBound = new RangesByUpperBound<C>(rangesByLowerBound);
699 }
700
701 private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> window) {
702 if (!window.isConnected(lowerBoundWindow)) {
703 return ImmutableSortedMap.of();
704 } else {
705 return new SubRangeSetRangesByLowerBound<C>(
706 lowerBoundWindow.intersection(window), restriction, rangesByLowerBound);
707 }
708 }
709
710 @Override
711 public NavigableMap<Cut<C>, Range<C>> subMap(
712 Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) {
713 return subMap(
714 Range.range(
715 fromKey,
716 BoundType.forBoolean(fromInclusive),
717 toKey,
718 BoundType.forBoolean(toInclusive)));
719 }
720
721 @Override
722 public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) {
723 return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
724 }
725
726 @Override
727 public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) {
728 return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
729 }
730
731 @Override
732 public Comparator<? super Cut<C>> comparator() {
733 return Ordering.<Cut<C>>natural();
734 }
735
736 @Override
737 public boolean containsKey(@Nullable Object key) {
738 return get(key) != null;
739 }
740
741 @Override
742 public @Nullable Range<C> get(@Nullable Object key) {
743 if (key instanceof Cut) {
744 try {
745 @SuppressWarnings("unchecked") // we catch CCE's
746 Cut<C> cut = (Cut<C>) key;
747 if (!lowerBoundWindow.contains(cut)
748 || cut.compareTo(restriction.lowerBound) < 0
749 || cut.compareTo(restriction.upperBound) >= 0) {
750 return null;
751 } else if (cut.equals(restriction.lowerBound)) {
752 // it might be present, truncated on the left
753 Range<C> candidate = Maps.valueOrNull(rangesByLowerBound.floorEntry(cut));
754 if (candidate != null && candidate.upperBound.compareTo(restriction.lowerBound) > 0) {
755 return candidate.intersection(restriction);
756 }
757 } else {
758 Range<C> result = rangesByLowerBound.get(cut);
759 if (result != null) {
760 return result.intersection(restriction);
761 }
762 }
763 } catch (ClassCastException e) {
764 return null;
765 }
766 }
767 return null;
768 }
769
770 @Override
771 Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
772 if (restriction.isEmpty()) {
773 return Iterators.emptyIterator();
774 }
775 final Iterator<Range<C>> completeRangeItr;
776 if (lowerBoundWindow.upperBound.isLessThan(restriction.lowerBound)) {
777 return Iterators.emptyIterator();
778 } else if (lowerBoundWindow.lowerBound.isLessThan(restriction.lowerBound)) {
779 // starts at the first range with upper bound strictly greater than restriction.lowerBound
780 completeRangeItr =
781 rangesByUpperBound.tailMap(restriction.lowerBound, false).values().iterator();
782 } else {
783 // starts at the first range with lower bound above lowerBoundWindow.lowerBound
784 completeRangeItr =
785 rangesByLowerBound
786 .tailMap(
787 lowerBoundWindow.lowerBound.endpoint(),
788 lowerBoundWindow.lowerBoundType() == BoundType.CLOSED)
789 .values()
790 .iterator();
791 }
792 final Cut<Cut<C>> upperBoundOnLowerBounds =
793 Ordering.natural()
794 .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
795 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
796 @Override
797 protected Entry<Cut<C>, Range<C>> computeNext() {
798 if (!completeRangeItr.hasNext()) {
799 return endOfData();
800 }
801 Range<C> nextRange = completeRangeItr.next();
802 if (upperBoundOnLowerBounds.isLessThan(nextRange.lowerBound)) {
803 return endOfData();
804 } else {
805 nextRange = nextRange.intersection(restriction);
806 return Maps.immutableEntry(nextRange.lowerBound, nextRange);
807 }
808 }
809 };
810 }
811
812 @Override
813 Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
814 if (restriction.isEmpty()) {
815 return Iterators.emptyIterator();
816 }
817 Cut<Cut<C>> upperBoundOnLowerBounds =
818 Ordering.natural()
819 .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
820 final Iterator<Range<C>> completeRangeItr =
821 rangesByLowerBound
822 .headMap(
823 upperBoundOnLowerBounds.endpoint(),
824 upperBoundOnLowerBounds.typeAsUpperBound() == BoundType.CLOSED)
825 .descendingMap()
826 .values()
827 .iterator();
828 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
829 @Override
830 protected Entry<Cut<C>, Range<C>> computeNext() {
831 if (!completeRangeItr.hasNext()) {
832 return endOfData();
833 }
834 Range<C> nextRange = completeRangeItr.next();
835 if (restriction.lowerBound.compareTo(nextRange.upperBound) >= 0) {
836 return endOfData();
837 }
838 nextRange = nextRange.intersection(restriction);
839 if (lowerBoundWindow.contains(nextRange.lowerBound)) {
840 return Maps.immutableEntry(nextRange.lowerBound, nextRange);
841 } else {
842 return endOfData();
843 }
844 }
845 };
846 }
847
848 @Override
849 public int size() {
850 return Iterators.size(entryIterator());
851 }
852 }
853
854 @Override
855 public RangeSet<C> subRangeSet(Range<C> view) {
856 return view.equals(Range.<C>all()) ? this : new SubRangeSet(view);
857 }
858
859 private final class SubRangeSet extends TreeRangeSet<C> {
860 private final Range<C> restriction;
861
862 SubRangeSet(Range<C> restriction) {
863 super(
864 new SubRangeSetRangesByLowerBound<C>(
865 Range.<Cut<C>>all(), restriction, TreeRangeSet.this.rangesByLowerBound));
866 this.restriction = restriction;
867 }
868
869 @Override
870 public boolean encloses(Range<C> range) {
871 if (!restriction.isEmpty() && restriction.encloses(range)) {
872 Range<C> enclosing = TreeRangeSet.this.rangeEnclosing(range);
873 return enclosing != null && !enclosing.intersection(restriction).isEmpty();
874 }
875 return false;
876 }
877
878 @Override
879 public @Nullable Range<C> rangeContaining(C value) {
880 if (!restriction.contains(value)) {
881 return null;
882 }
883 Range<C> result = TreeRangeSet.this.rangeContaining(value);
884 return (result == null) ? null : result.intersection(restriction);
885 }
886
887 @Override
888 public void add(Range<C> rangeToAdd) {
889 checkArgument(
890 restriction.encloses(rangeToAdd),
891 "Cannot add range %s to subRangeSet(%s)",
892 rangeToAdd,
893 restriction);
894 TreeRangeSet.this.add(rangeToAdd);
895 }
896
897 @Override
898 public void remove(Range<C> rangeToRemove) {
899 if (rangeToRemove.isConnected(restriction)) {
900 TreeRangeSet.this.remove(rangeToRemove.intersection(restriction));
901 }
902 }
903
904 @Override
905 public boolean contains(C value) {
906 return restriction.contains(value) && TreeRangeSet.this.contains(value);
907 }
908
909 @Override
910 public void clear() {
911 TreeRangeSet.this.remove(restriction);
912 }
913
914 @Override
915 public RangeSet<C> subRangeSet(Range<C> view) {
916 if (view.encloses(restriction)) {
917 return this;
918 } else if (view.isConnected(restriction)) {
919 return new SubRangeSet(restriction.intersection(view));
920 } else {
921 return ImmutableRangeSet.of();
922 }
923 }
924 }
925 }