1
2
3
4
5
6
7
8
9
10
11
12
13
14 package com.google.common.collect;
15
16 import static com.google.common.base.Preconditions.checkArgument;
17 import static com.google.common.base.Preconditions.checkElementIndex;
18 import static com.google.common.base.Preconditions.checkNotNull;
19 import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_LOWER;
20 import static com.google.common.collect.SortedLists.KeyPresentBehavior.ANY_PRESENT;
21
22 import com.google.common.annotations.Beta;
23 import com.google.common.annotations.GwtIncompatible;
24 import com.google.common.collect.SortedLists.KeyAbsentBehavior;
25 import com.google.common.collect.SortedLists.KeyPresentBehavior;
26 import com.google.common.primitives.Ints;
27
28 import java.io.Serializable;
29 import java.util.Collections;
30 import java.util.Iterator;
31 import java.util.NoSuchElementException;
32 import java.util.Set;
33
34 import javax.annotation.Nullable;
35
36
37
38
39
40
41
42 @Beta
43 public final class ImmutableRangeSet<C extends Comparable> extends AbstractRangeSet<C>
44 implements Serializable {
45
46 private static final ImmutableRangeSet<Comparable<?>> EMPTY =
47 new ImmutableRangeSet<Comparable<?>>(ImmutableList.<Range<Comparable<?>>>of());
48
49 private static final ImmutableRangeSet<Comparable<?>> ALL =
50 new ImmutableRangeSet<Comparable<?>>(ImmutableList.of(Range.<Comparable<?>>all()));
51
52
53
54
55 @SuppressWarnings("unchecked")
56 public static <C extends Comparable> ImmutableRangeSet<C> of() {
57 return (ImmutableRangeSet<C>) EMPTY;
58 }
59
60
61
62
63 @SuppressWarnings("unchecked")
64 static <C extends Comparable> ImmutableRangeSet<C> all() {
65 return (ImmutableRangeSet<C>) ALL;
66 }
67
68
69
70
71
72 public static <C extends Comparable> ImmutableRangeSet<C> of(Range<C> range) {
73 checkNotNull(range);
74 if (range.isEmpty()) {
75 return of();
76 } else if (range.equals(Range.all())) {
77 return all();
78 } else {
79 return new ImmutableRangeSet<C>(ImmutableList.of(range));
80 }
81 }
82
83
84
85
86 public static <C extends Comparable> ImmutableRangeSet<C> copyOf(RangeSet<C> rangeSet) {
87 checkNotNull(rangeSet);
88 if (rangeSet.isEmpty()) {
89 return of();
90 } else if (rangeSet.encloses(Range.<C>all())) {
91 return all();
92 }
93
94 if (rangeSet instanceof ImmutableRangeSet) {
95 ImmutableRangeSet<C> immutableRangeSet = (ImmutableRangeSet<C>) rangeSet;
96 if (!immutableRangeSet.isPartialView()) {
97 return immutableRangeSet;
98 }
99 }
100 return new ImmutableRangeSet<C>(ImmutableList.copyOf(rangeSet.asRanges()));
101 }
102
103 ImmutableRangeSet(ImmutableList<Range<C>> ranges) {
104 this.ranges = ranges;
105 }
106
107 private ImmutableRangeSet(ImmutableList<Range<C>> ranges, ImmutableRangeSet<C> complement) {
108 this.ranges = ranges;
109 this.complement = complement;
110 }
111
112 private transient final ImmutableList<Range<C>> ranges;
113
114 @Override
115 public boolean encloses(Range<C> otherRange) {
116 int index = SortedLists.binarySearch(ranges,
117 Range.<C>lowerBoundFn(),
118 otherRange.lowerBound,
119 Ordering.natural(),
120 ANY_PRESENT,
121 NEXT_LOWER);
122 return index != -1 && ranges.get(index).encloses(otherRange);
123 }
124
125 @Override
126 public Range<C> rangeContaining(C value) {
127 int index = SortedLists.binarySearch(ranges,
128 Range.<C>lowerBoundFn(),
129 Cut.belowValue(value),
130 Ordering.natural(),
131 ANY_PRESENT,
132 NEXT_LOWER);
133 if (index != -1) {
134 Range<C> range = ranges.get(index);
135 return range.contains(value) ? range : null;
136 }
137 return null;
138 }
139
140 @Override
141 public Range<C> span() {
142 if (ranges.isEmpty()) {
143 throw new NoSuchElementException();
144 }
145 return Range.create(
146 ranges.get(0).lowerBound,
147 ranges.get(ranges.size() - 1).upperBound);
148 }
149
150 @Override
151 public boolean isEmpty() {
152 return ranges.isEmpty();
153 }
154
155 @Override
156 public void add(Range<C> range) {
157 throw new UnsupportedOperationException();
158 }
159
160 @Override
161 public void addAll(RangeSet<C> other) {
162 throw new UnsupportedOperationException();
163 }
164
165 @Override
166 public void remove(Range<C> range) {
167 throw new UnsupportedOperationException();
168 }
169
170 @Override
171 public void removeAll(RangeSet<C> other) {
172 throw new UnsupportedOperationException();
173 }
174
175 @Override
176 public ImmutableSet<Range<C>> asRanges() {
177 if (ranges.isEmpty()) {
178 return ImmutableSet.of();
179 }
180 return new RegularImmutableSortedSet<Range<C>>(ranges, Range.RANGE_LEX_ORDERING);
181 }
182
183 private transient ImmutableRangeSet<C> complement;
184
185 private final class ComplementRanges extends ImmutableList<Range<C>> {
186
187 private final boolean positiveBoundedBelow;
188
189
190 private final boolean positiveBoundedAbove;
191
192 private final int size;
193
194 ComplementRanges() {
195 this.positiveBoundedBelow = ranges.get(0).hasLowerBound();
196 this.positiveBoundedAbove = Iterables.getLast(ranges).hasUpperBound();
197
198 int size = ranges.size() - 1;
199 if (positiveBoundedBelow) {
200 size++;
201 }
202 if (positiveBoundedAbove) {
203 size++;
204 }
205 this.size = size;
206 }
207
208 @Override
209 public int size() {
210 return size;
211 }
212
213 @Override
214 public Range<C> get(int index) {
215 checkElementIndex(index, size);
216
217 Cut<C> lowerBound;
218 if (positiveBoundedBelow) {
219 lowerBound = (index == 0) ? Cut.<C>belowAll() : ranges.get(index - 1).upperBound;
220 } else {
221 lowerBound = ranges.get(index).upperBound;
222 }
223
224 Cut<C> upperBound;
225 if (positiveBoundedAbove && index == size - 1) {
226 upperBound = Cut.<C>aboveAll();
227 } else {
228 upperBound = ranges.get(index + (positiveBoundedBelow ? 0 : 1)).lowerBound;
229 }
230
231 return Range.create(lowerBound, upperBound);
232 }
233
234 @Override
235 boolean isPartialView() {
236 return true;
237 }
238 }
239
240 @Override
241 public ImmutableRangeSet<C> complement() {
242 ImmutableRangeSet<C> result = complement;
243 if (result != null) {
244 return result;
245 } else if (ranges.isEmpty()) {
246 return complement = all();
247 } else if (ranges.size() == 1 && ranges.get(0).equals(Range.all())) {
248 return complement = of();
249 } else {
250 ImmutableList<Range<C>> complementRanges = new ComplementRanges();
251 result = complement = new ImmutableRangeSet<C>(complementRanges, this);
252 }
253 return result;
254 }
255
256
257
258
259
260 private ImmutableList<Range<C>> intersectRanges(final Range<C> range) {
261 if (ranges.isEmpty() || range.isEmpty()) {
262 return ImmutableList.of();
263 } else if (range.encloses(span())) {
264 return ranges;
265 }
266
267 final int fromIndex;
268 if (range.hasLowerBound()) {
269 fromIndex = SortedLists.binarySearch(
270 ranges, Range.<C>upperBoundFn(), range.lowerBound, KeyPresentBehavior.FIRST_AFTER,
271 KeyAbsentBehavior.NEXT_HIGHER);
272 } else {
273 fromIndex = 0;
274 }
275
276 int toIndex;
277 if (range.hasUpperBound()) {
278 toIndex = SortedLists.binarySearch(
279 ranges, Range.<C>lowerBoundFn(), range.upperBound, KeyPresentBehavior.FIRST_PRESENT,
280 KeyAbsentBehavior.NEXT_HIGHER);
281 } else {
282 toIndex = ranges.size();
283 }
284 final int length = toIndex - fromIndex;
285 if (length == 0) {
286 return ImmutableList.of();
287 } else {
288 return new ImmutableList<Range<C>>() {
289 @Override
290 public int size() {
291 return length;
292 }
293
294 @Override
295 public Range<C> get(int index) {
296 checkElementIndex(index, length);
297 if (index == 0 || index == length - 1) {
298 return ranges.get(index + fromIndex).intersection(range);
299 } else {
300 return ranges.get(index + fromIndex);
301 }
302 }
303
304 @Override
305 boolean isPartialView() {
306 return true;
307 }
308 };
309 }
310 }
311
312
313
314
315 @Override
316 public ImmutableRangeSet<C> subRangeSet(Range<C> range) {
317 if (!isEmpty()) {
318 Range<C> span = span();
319 if (range.encloses(span)) {
320 return this;
321 } else if (range.isConnected(span)) {
322 return new ImmutableRangeSet<C>(intersectRanges(range));
323 }
324 }
325 return of();
326 }
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347 public ImmutableSortedSet<C> asSet(DiscreteDomain<C> domain) {
348 checkNotNull(domain);
349 if (isEmpty()) {
350 return ImmutableSortedSet.of();
351 }
352 Range<C> span = span().canonical(domain);
353 if (!span.hasLowerBound()) {
354
355
356 throw new IllegalArgumentException(
357 "Neither the DiscreteDomain nor this range set are bounded below");
358 } else if (!span.hasUpperBound()) {
359 try {
360 domain.maxValue();
361 } catch (NoSuchElementException e) {
362 throw new IllegalArgumentException(
363 "Neither the DiscreteDomain nor this range set are bounded above");
364 }
365 }
366
367 return new AsSet(domain);
368 }
369
370 private final class AsSet extends ImmutableSortedSet<C> {
371 private final DiscreteDomain<C> domain;
372
373 AsSet(DiscreteDomain<C> domain) {
374 super(Ordering.natural());
375 this.domain = domain;
376 }
377
378 private transient Integer size;
379
380 @Override
381 public int size() {
382
383 Integer result = size;
384 if (result == null) {
385 long total = 0;
386 for (Range<C> range : ranges) {
387 total += ContiguousSet.create(range, domain).size();
388 if (total >= Integer.MAX_VALUE) {
389 break;
390 }
391 }
392 result = size = Ints.saturatedCast(total);
393 }
394 return result.intValue();
395 }
396
397 @Override
398 public UnmodifiableIterator<C> iterator() {
399 return new AbstractIterator<C>() {
400 final Iterator<Range<C>> rangeItr = ranges.iterator();
401 Iterator<C> elemItr = Iterators.emptyIterator();
402
403 @Override
404 protected C computeNext() {
405 while (!elemItr.hasNext()) {
406 if (rangeItr.hasNext()) {
407 elemItr = ContiguousSet.create(rangeItr.next(), domain).iterator();
408 } else {
409 return endOfData();
410 }
411 }
412 return elemItr.next();
413 }
414 };
415 }
416
417 @Override
418 @GwtIncompatible("NavigableSet")
419 public UnmodifiableIterator<C> descendingIterator() {
420 return new AbstractIterator<C>() {
421 final Iterator<Range<C>> rangeItr = ranges.reverse().iterator();
422 Iterator<C> elemItr = Iterators.emptyIterator();
423
424 @Override
425 protected C computeNext() {
426 while (!elemItr.hasNext()) {
427 if (rangeItr.hasNext()) {
428 elemItr = ContiguousSet.create(rangeItr.next(), domain).descendingIterator();
429 } else {
430 return endOfData();
431 }
432 }
433 return elemItr.next();
434 }
435 };
436 }
437
438 ImmutableSortedSet<C> subSet(Range<C> range) {
439 return subRangeSet(range).asSet(domain);
440 }
441
442 @Override
443 ImmutableSortedSet<C> headSetImpl(C toElement, boolean inclusive) {
444 return subSet(Range.upTo(toElement, BoundType.forBoolean(inclusive)));
445 }
446
447 @Override
448 ImmutableSortedSet<C> subSetImpl(
449 C fromElement, boolean fromInclusive, C toElement, boolean toInclusive) {
450 if (!fromInclusive && !toInclusive && Range.compareOrThrow(fromElement, toElement) == 0) {
451 return ImmutableSortedSet.of();
452 }
453 return subSet(Range.range(
454 fromElement, BoundType.forBoolean(fromInclusive),
455 toElement, BoundType.forBoolean(toInclusive)));
456 }
457
458 @Override
459 ImmutableSortedSet<C> tailSetImpl(C fromElement, boolean inclusive) {
460 return subSet(Range.downTo(fromElement, BoundType.forBoolean(inclusive)));
461 }
462
463 @Override
464 public boolean contains(@Nullable Object o) {
465 if (o == null) {
466 return false;
467 }
468 try {
469 @SuppressWarnings("unchecked")
470 C c = (C) o;
471 return ImmutableRangeSet.this.contains(c);
472 } catch (ClassCastException e) {
473 return false;
474 }
475 }
476
477 @Override
478 int indexOf(Object target) {
479 if (contains(target)) {
480 @SuppressWarnings("unchecked")
481 C c = (C) target;
482 long total = 0;
483 for (Range<C> range : ranges) {
484 if (range.contains(c)) {
485 return Ints.saturatedCast(total + ContiguousSet.create(range, domain).indexOf(c));
486 } else {
487 total += ContiguousSet.create(range, domain).size();
488 }
489 }
490 throw new AssertionError("impossible");
491 }
492 return -1;
493 }
494
495 @Override
496 boolean isPartialView() {
497 return ranges.isPartialView();
498 }
499
500 @Override
501 public String toString() {
502 return ranges.toString();
503 }
504
505 @Override
506 Object writeReplace() {
507 return new AsSetSerializedForm<C>(ranges, domain);
508 }
509 }
510
511 private static class AsSetSerializedForm<C extends Comparable> implements Serializable {
512 private final ImmutableList<Range<C>> ranges;
513 private final DiscreteDomain<C> domain;
514
515 AsSetSerializedForm(ImmutableList<Range<C>> ranges, DiscreteDomain<C> domain) {
516 this.ranges = ranges;
517 this.domain = domain;
518 }
519
520 Object readResolve() {
521 return new ImmutableRangeSet<C>(ranges).asSet(domain);
522 }
523 }
524
525
526
527
528
529
530
531 boolean isPartialView() {
532 return ranges.isPartialView();
533 }
534
535
536
537
538 public static <C extends Comparable<?>> Builder<C> builder() {
539 return new Builder<C>();
540 }
541
542
543
544
545 public static class Builder<C extends Comparable<?>> {
546 private final RangeSet<C> rangeSet;
547
548 public Builder() {
549 this.rangeSet = TreeRangeSet.create();
550 }
551
552
553
554
555
556
557
558
559 public Builder<C> add(Range<C> range) {
560 if (range.isEmpty()) {
561 throw new IllegalArgumentException("range must not be empty, but was " + range);
562 } else if (!rangeSet.complement().encloses(range)) {
563 for (Range<C> currentRange : rangeSet.asRanges()) {
564 checkArgument(
565 !currentRange.isConnected(range) || currentRange.intersection(range).isEmpty(),
566 "Ranges may not overlap, but received %s and %s", currentRange, range);
567 }
568 throw new AssertionError("should have thrown an IAE above");
569 }
570 rangeSet.add(range);
571 return this;
572 }
573
574
575
576
577
578 public Builder<C> addAll(RangeSet<C> ranges) {
579 for (Range<C> range : ranges.asRanges()) {
580 add(range);
581 }
582 return this;
583 }
584
585
586
587
588 public ImmutableRangeSet<C> build() {
589 return copyOf(rangeSet);
590 }
591 }
592
593 private static final class SerializedForm<C extends Comparable> implements Serializable {
594 private final ImmutableList<Range<C>> ranges;
595
596 SerializedForm(ImmutableList<Range<C>> ranges) {
597 this.ranges = ranges;
598 }
599
600 Object readResolve() {
601 if (ranges.isEmpty()) {
602 return of();
603 } else if (ranges.equals(ImmutableList.of(Range.all()))) {
604 return all();
605 } else {
606 return new ImmutableRangeSet<C>(ranges);
607 }
608 }
609 }
610
611 Object writeReplace() {
612 return new SerializedForm<C>(ranges);
613 }
614 }