001/*
002 * Copyright (C) 2012 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014package com.google.common.collect;
015
016import static com.google.common.base.Preconditions.checkArgument;
017import static com.google.common.base.Preconditions.checkElementIndex;
018import static com.google.common.base.Preconditions.checkNotNull;
019import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_HIGHER;
020import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_LOWER;
021import static com.google.common.collect.SortedLists.KeyPresentBehavior.ANY_PRESENT;
022
023import com.google.common.annotations.Beta;
024import com.google.common.annotations.GwtIncompatible;
025import com.google.common.collect.SortedLists.KeyAbsentBehavior;
026import com.google.common.collect.SortedLists.KeyPresentBehavior;
027import com.google.common.primitives.Ints;
028import com.google.errorprone.annotations.CanIgnoreReturnValue;
029import com.google.errorprone.annotations.concurrent.LazyInit;
030import java.io.Serializable;
031import java.util.Collections;
032import java.util.Iterator;
033import java.util.NoSuchElementException;
034import java.util.Set;
035import javax.annotation.Nullable;
036
037/**
038 * A {@link RangeSet} whose contents will never change, with many other important properties
039 * detailed at {@link ImmutableCollection}.
040 *
041 * @author Louis Wasserman
042 * @since 14.0
043 */
044@Beta
045@GwtIncompatible
046public final class ImmutableRangeSet<C extends Comparable> extends AbstractRangeSet<C>
047    implements Serializable {
048
049  private static final ImmutableRangeSet<Comparable<?>> EMPTY =
050      new ImmutableRangeSet<Comparable<?>>(ImmutableList.<Range<Comparable<?>>>of());
051
052  private static final ImmutableRangeSet<Comparable<?>> ALL =
053      new ImmutableRangeSet<Comparable<?>>(ImmutableList.of(Range.<Comparable<?>>all()));
054
055  /**
056   * Returns an empty immutable range set.
057   */
058  @SuppressWarnings("unchecked")
059  public static <C extends Comparable> ImmutableRangeSet<C> of() {
060    return (ImmutableRangeSet<C>) EMPTY;
061  }
062
063  /**
064   * Returns an immutable range set containing the single range {@link Range#all()}.
065   */
066  @SuppressWarnings("unchecked")
067  static <C extends Comparable> ImmutableRangeSet<C> all() {
068    return (ImmutableRangeSet<C>) ALL;
069  }
070
071  /**
072   * Returns an immutable range set containing the specified single range. If {@link Range#isEmpty()
073   * range.isEmpty()}, this is equivalent to {@link ImmutableRangeSet#of()}.
074   */
075  public static <C extends Comparable> ImmutableRangeSet<C> of(Range<C> range) {
076    checkNotNull(range);
077    if (range.isEmpty()) {
078      return of();
079    } else if (range.equals(Range.all())) {
080      return all();
081    } else {
082      return new ImmutableRangeSet<C>(ImmutableList.of(range));
083    }
084  }
085
086  /**
087   * Returns an immutable copy of the specified {@code RangeSet}.
088   */
089  public static <C extends Comparable> ImmutableRangeSet<C> copyOf(RangeSet<C> rangeSet) {
090    checkNotNull(rangeSet);
091    if (rangeSet.isEmpty()) {
092      return of();
093    } else if (rangeSet.encloses(Range.<C>all())) {
094      return all();
095    }
096
097    if (rangeSet instanceof ImmutableRangeSet) {
098      ImmutableRangeSet<C> immutableRangeSet = (ImmutableRangeSet<C>) rangeSet;
099      if (!immutableRangeSet.isPartialView()) {
100        return immutableRangeSet;
101      }
102    }
103    return new ImmutableRangeSet<C>(ImmutableList.copyOf(rangeSet.asRanges()));
104  }
105
106  ImmutableRangeSet(ImmutableList<Range<C>> ranges) {
107    this.ranges = ranges;
108  }
109
110  private ImmutableRangeSet(ImmutableList<Range<C>> ranges, ImmutableRangeSet<C> complement) {
111    this.ranges = ranges;
112    this.complement = complement;
113  }
114
115  private final transient ImmutableList<Range<C>> ranges;
116
117  @Override
118  public boolean intersects(Range<C> otherRange) {
119    int ceilingIndex =
120        SortedLists.binarySearch(
121            ranges,
122            Range.<C>lowerBoundFn(),
123            otherRange.lowerBound,
124            Ordering.natural(),
125            ANY_PRESENT,
126            NEXT_HIGHER);
127    if (ceilingIndex < ranges.size()
128        && ranges.get(ceilingIndex).isConnected(otherRange)
129        && !ranges.get(ceilingIndex).intersection(otherRange).isEmpty()) {
130      return true;
131    }
132    return ceilingIndex > 0
133        && ranges.get(ceilingIndex - 1).isConnected(otherRange)
134        && !ranges.get(ceilingIndex - 1).intersection(otherRange).isEmpty();
135  }
136
137  @Override
138  public boolean encloses(Range<C> otherRange) {
139    int index =
140        SortedLists.binarySearch(
141            ranges,
142            Range.<C>lowerBoundFn(),
143            otherRange.lowerBound,
144            Ordering.natural(),
145            ANY_PRESENT,
146            NEXT_LOWER);
147    return index != -1 && ranges.get(index).encloses(otherRange);
148  }
149
150  @Override
151  public Range<C> rangeContaining(C value) {
152    int index =
153        SortedLists.binarySearch(
154            ranges,
155            Range.<C>lowerBoundFn(),
156            Cut.belowValue(value),
157            Ordering.natural(),
158            ANY_PRESENT,
159            NEXT_LOWER);
160    if (index != -1) {
161      Range<C> range = ranges.get(index);
162      return range.contains(value) ? range : null;
163    }
164    return null;
165  }
166
167  @Override
168  public Range<C> span() {
169    if (ranges.isEmpty()) {
170      throw new NoSuchElementException();
171    }
172    return Range.create(ranges.get(0).lowerBound, ranges.get(ranges.size() - 1).upperBound);
173  }
174
175  @Override
176  public boolean isEmpty() {
177    return ranges.isEmpty();
178  }
179
180  /**
181   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
182   *
183   * @throws UnsupportedOperationException always
184   * @deprecated Unsupported operation.
185   */
186  @Deprecated
187  @Override
188  public void add(Range<C> range) {
189    throw new UnsupportedOperationException();
190  }
191
192  /**
193   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
194   *
195   * @throws UnsupportedOperationException always
196   * @deprecated Unsupported operation.
197   */
198  @Deprecated
199  @Override
200  public void addAll(RangeSet<C> other) {
201    throw new UnsupportedOperationException();
202  }
203
204  /**
205   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
206   *
207   * @throws UnsupportedOperationException always
208   * @deprecated Unsupported operation.
209   */
210  @Deprecated
211  @Override
212  public void remove(Range<C> range) {
213    throw new UnsupportedOperationException();
214  }
215
216  /**
217   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
218   *
219   * @throws UnsupportedOperationException always
220   * @deprecated Unsupported operation.
221   */
222  @Deprecated
223  @Override
224  public void removeAll(RangeSet<C> other) {
225    throw new UnsupportedOperationException();
226  }
227
228  @Override
229  public ImmutableSet<Range<C>> asRanges() {
230    if (ranges.isEmpty()) {
231      return ImmutableSet.of();
232    }
233    return new RegularImmutableSortedSet<Range<C>>(ranges, Range.RANGE_LEX_ORDERING);
234  }
235
236  @Override
237  public ImmutableSet<Range<C>> asDescendingSetOfRanges() {
238    if (ranges.isEmpty()) {
239      return ImmutableSet.of();
240    }
241    return new RegularImmutableSortedSet<Range<C>>(
242        ranges.reverse(), Range.RANGE_LEX_ORDERING.reverse());
243  }
244
245  @LazyInit
246  private transient ImmutableRangeSet<C> complement;
247
248  private final class ComplementRanges extends ImmutableList<Range<C>> {
249    // True if the "positive" range set is empty or bounded below.
250    private final boolean positiveBoundedBelow;
251
252    // True if the "positive" range set is empty or bounded above.
253    private final boolean positiveBoundedAbove;
254
255    private final int size;
256
257    ComplementRanges() {
258      this.positiveBoundedBelow = ranges.get(0).hasLowerBound();
259      this.positiveBoundedAbove = Iterables.getLast(ranges).hasUpperBound();
260
261      int size = ranges.size() - 1;
262      if (positiveBoundedBelow) {
263        size++;
264      }
265      if (positiveBoundedAbove) {
266        size++;
267      }
268      this.size = size;
269    }
270
271    @Override
272    public int size() {
273      return size;
274    }
275
276    @Override
277    public Range<C> get(int index) {
278      checkElementIndex(index, size);
279
280      Cut<C> lowerBound;
281      if (positiveBoundedBelow) {
282        lowerBound = (index == 0) ? Cut.<C>belowAll() : ranges.get(index - 1).upperBound;
283      } else {
284        lowerBound = ranges.get(index).upperBound;
285      }
286
287      Cut<C> upperBound;
288      if (positiveBoundedAbove && index == size - 1) {
289        upperBound = Cut.<C>aboveAll();
290      } else {
291        upperBound = ranges.get(index + (positiveBoundedBelow ? 0 : 1)).lowerBound;
292      }
293
294      return Range.create(lowerBound, upperBound);
295    }
296
297    @Override
298    boolean isPartialView() {
299      return true;
300    }
301  }
302
303  @Override
304  public ImmutableRangeSet<C> complement() {
305    ImmutableRangeSet<C> result = complement;
306    if (result != null) {
307      return result;
308    } else if (ranges.isEmpty()) {
309      return complement = all();
310    } else if (ranges.size() == 1 && ranges.get(0).equals(Range.all())) {
311      return complement = of();
312    } else {
313      ImmutableList<Range<C>> complementRanges = new ComplementRanges();
314      result = complement = new ImmutableRangeSet<C>(complementRanges, this);
315    }
316    return result;
317  }
318
319  /**
320   * Returns a list containing the nonempty intersections of {@code range}
321   * with the ranges in this range set.
322   */
323  private ImmutableList<Range<C>> intersectRanges(final Range<C> range) {
324    if (ranges.isEmpty() || range.isEmpty()) {
325      return ImmutableList.of();
326    } else if (range.encloses(span())) {
327      return ranges;
328    }
329
330    final int fromIndex;
331    if (range.hasLowerBound()) {
332      fromIndex =
333          SortedLists.binarySearch(
334              ranges,
335              Range.<C>upperBoundFn(),
336              range.lowerBound,
337              KeyPresentBehavior.FIRST_AFTER,
338              KeyAbsentBehavior.NEXT_HIGHER);
339    } else {
340      fromIndex = 0;
341    }
342
343    int toIndex;
344    if (range.hasUpperBound()) {
345      toIndex =
346          SortedLists.binarySearch(
347              ranges,
348              Range.<C>lowerBoundFn(),
349              range.upperBound,
350              KeyPresentBehavior.FIRST_PRESENT,
351              KeyAbsentBehavior.NEXT_HIGHER);
352    } else {
353      toIndex = ranges.size();
354    }
355    final int length = toIndex - fromIndex;
356    if (length == 0) {
357      return ImmutableList.of();
358    } else {
359      return new ImmutableList<Range<C>>() {
360        @Override
361        public int size() {
362          return length;
363        }
364
365        @Override
366        public Range<C> get(int index) {
367          checkElementIndex(index, length);
368          if (index == 0 || index == length - 1) {
369            return ranges.get(index + fromIndex).intersection(range);
370          } else {
371            return ranges.get(index + fromIndex);
372          }
373        }
374
375        @Override
376        boolean isPartialView() {
377          return true;
378        }
379      };
380    }
381  }
382
383  /**
384   * Returns a view of the intersection of this range set with the given range.
385   */
386  @Override
387  public ImmutableRangeSet<C> subRangeSet(Range<C> range) {
388    if (!isEmpty()) {
389      Range<C> span = span();
390      if (range.encloses(span)) {
391        return this;
392      } else if (range.isConnected(span)) {
393        return new ImmutableRangeSet<C>(intersectRanges(range));
394      }
395    }
396    return of();
397  }
398
399  /**
400   * Returns an {@link ImmutableSortedSet} containing the same values in the given domain
401   * {@linkplain RangeSet#contains contained} by this range set.
402   *
403   * <p><b>Note:</b> {@code a.asSet(d).equals(b.asSet(d))} does not imply {@code a.equals(b)}! For
404   * example, {@code a} and {@code b} could be {@code [2..4]} and {@code (1..5)}, or the empty
405   * ranges {@code [3..3)} and {@code [4..4)}.
406   *
407   * <p><b>Warning:</b> Be extremely careful what you do with the {@code asSet} view of a large
408   * range set (such as {@code ImmutableRangeSet.of(Range.greaterThan(0))}). Certain operations on
409   * such a set can be performed efficiently, but others (such as {@link Set#hashCode} or
410   * {@link Collections#frequency}) can cause major performance problems.
411   *
412   * <p>The returned set's {@link Object#toString} method returns a short-hand form of the set's
413   * contents, such as {@code "[1..100]}"}.
414   *
415   * @throws IllegalArgumentException if neither this range nor the domain has a lower bound, or if
416   *         neither has an upper bound
417   */
418  public ImmutableSortedSet<C> asSet(DiscreteDomain<C> domain) {
419    checkNotNull(domain);
420    if (isEmpty()) {
421      return ImmutableSortedSet.of();
422    }
423    Range<C> span = span().canonical(domain);
424    if (!span.hasLowerBound()) {
425      // according to the spec of canonical, neither this ImmutableRangeSet nor
426      // the range have a lower bound
427      throw new IllegalArgumentException(
428          "Neither the DiscreteDomain nor this range set are bounded below");
429    } else if (!span.hasUpperBound()) {
430      try {
431        domain.maxValue();
432      } catch (NoSuchElementException e) {
433        throw new IllegalArgumentException(
434            "Neither the DiscreteDomain nor this range set are bounded above");
435      }
436    }
437
438    return new AsSet(domain);
439  }
440
441  private final class AsSet extends ImmutableSortedSet<C> {
442    private final DiscreteDomain<C> domain;
443
444    AsSet(DiscreteDomain<C> domain) {
445      super(Ordering.natural());
446      this.domain = domain;
447    }
448
449    private transient Integer size;
450
451    @Override
452    public int size() {
453      // racy single-check idiom
454      Integer result = size;
455      if (result == null) {
456        long total = 0;
457        for (Range<C> range : ranges) {
458          total += ContiguousSet.create(range, domain).size();
459          if (total >= Integer.MAX_VALUE) {
460            break;
461          }
462        }
463        result = size = Ints.saturatedCast(total);
464      }
465      return result.intValue();
466    }
467
468    @Override
469    public UnmodifiableIterator<C> iterator() {
470      return new AbstractIterator<C>() {
471        final Iterator<Range<C>> rangeItr = ranges.iterator();
472        Iterator<C> elemItr = Iterators.emptyIterator();
473
474        @Override
475        protected C computeNext() {
476          while (!elemItr.hasNext()) {
477            if (rangeItr.hasNext()) {
478              elemItr = ContiguousSet.create(rangeItr.next(), domain).iterator();
479            } else {
480              return endOfData();
481            }
482          }
483          return elemItr.next();
484        }
485      };
486    }
487
488    @Override
489    @GwtIncompatible("NavigableSet")
490    public UnmodifiableIterator<C> descendingIterator() {
491      return new AbstractIterator<C>() {
492        final Iterator<Range<C>> rangeItr = ranges.reverse().iterator();
493        Iterator<C> elemItr = Iterators.emptyIterator();
494
495        @Override
496        protected C computeNext() {
497          while (!elemItr.hasNext()) {
498            if (rangeItr.hasNext()) {
499              elemItr = ContiguousSet.create(rangeItr.next(), domain).descendingIterator();
500            } else {
501              return endOfData();
502            }
503          }
504          return elemItr.next();
505        }
506      };
507    }
508
509    ImmutableSortedSet<C> subSet(Range<C> range) {
510      return subRangeSet(range).asSet(domain);
511    }
512
513    @Override
514    ImmutableSortedSet<C> headSetImpl(C toElement, boolean inclusive) {
515      return subSet(Range.upTo(toElement, BoundType.forBoolean(inclusive)));
516    }
517
518    @Override
519    ImmutableSortedSet<C> subSetImpl(
520        C fromElement, boolean fromInclusive, C toElement, boolean toInclusive) {
521      if (!fromInclusive && !toInclusive && Range.compareOrThrow(fromElement, toElement) == 0) {
522        return ImmutableSortedSet.of();
523      }
524      return subSet(
525          Range.range(
526              fromElement, BoundType.forBoolean(fromInclusive),
527              toElement, BoundType.forBoolean(toInclusive)));
528    }
529
530    @Override
531    ImmutableSortedSet<C> tailSetImpl(C fromElement, boolean inclusive) {
532      return subSet(Range.downTo(fromElement, BoundType.forBoolean(inclusive)));
533    }
534
535    @Override
536    public boolean contains(@Nullable Object o) {
537      if (o == null) {
538        return false;
539      }
540      try {
541        @SuppressWarnings("unchecked") // we catch CCE's
542        C c = (C) o;
543        return ImmutableRangeSet.this.contains(c);
544      } catch (ClassCastException e) {
545        return false;
546      }
547    }
548
549    @Override
550    int indexOf(Object target) {
551      if (contains(target)) {
552        @SuppressWarnings("unchecked") // if it's contained, it's definitely a C
553        C c = (C) target;
554        long total = 0;
555        for (Range<C> range : ranges) {
556          if (range.contains(c)) {
557            return Ints.saturatedCast(total + ContiguousSet.create(range, domain).indexOf(c));
558          } else {
559            total += ContiguousSet.create(range, domain).size();
560          }
561        }
562        throw new AssertionError("impossible");
563      }
564      return -1;
565    }
566
567    @Override
568    boolean isPartialView() {
569      return ranges.isPartialView();
570    }
571
572    @Override
573    public String toString() {
574      return ranges.toString();
575    }
576
577    @Override
578    Object writeReplace() {
579      return new AsSetSerializedForm<C>(ranges, domain);
580    }
581  }
582
583  private static class AsSetSerializedForm<C extends Comparable> implements Serializable {
584    private final ImmutableList<Range<C>> ranges;
585    private final DiscreteDomain<C> domain;
586
587    AsSetSerializedForm(ImmutableList<Range<C>> ranges, DiscreteDomain<C> domain) {
588      this.ranges = ranges;
589      this.domain = domain;
590    }
591
592    Object readResolve() {
593      return new ImmutableRangeSet<C>(ranges).asSet(domain);
594    }
595  }
596
597  /**
598   * Returns {@code true} if this immutable range set's implementation contains references to
599   * user-created objects that aren't accessible via this range set's methods. This is generally
600   * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid
601   * memory leaks.
602   */
603  boolean isPartialView() {
604    return ranges.isPartialView();
605  }
606
607  /**
608   * Returns a new builder for an immutable range set.
609   */
610  public static <C extends Comparable<?>> Builder<C> builder() {
611    return new Builder<C>();
612  }
613
614  /**
615   * A builder for immutable range sets.
616   */
617  public static class Builder<C extends Comparable<?>> {
618    private final RangeSet<C> rangeSet;
619
620    public Builder() {
621      this.rangeSet = TreeRangeSet.create();
622    }
623
624    /**
625     * Add the specified range to this builder.  Adjacent/abutting ranges are permitted, but
626     * empty ranges, or ranges with nonempty overlap, are forbidden.
627     *
628     * @throws IllegalArgumentException if {@code range} is empty or has nonempty intersection with
629     *         any ranges already added to the builder
630     */
631    @CanIgnoreReturnValue
632    public Builder<C> add(Range<C> range) {
633      if (range.isEmpty()) {
634        throw new IllegalArgumentException("range must not be empty, but was " + range);
635      } else if (!rangeSet.complement().encloses(range)) {
636        for (Range<C> currentRange : rangeSet.asRanges()) {
637          checkArgument(
638              !currentRange.isConnected(range) || currentRange.intersection(range).isEmpty(),
639              "Ranges may not overlap, but received %s and %s",
640              currentRange,
641              range);
642        }
643        throw new AssertionError("should have thrown an IAE above");
644      }
645      rangeSet.add(range);
646      return this;
647    }
648
649    /**
650     * Add all ranges from the specified range set to this builder. Duplicate or connected ranges
651     * are permitted, and will be merged in the resulting immutable range set.
652     */
653    @CanIgnoreReturnValue
654    public Builder<C> addAll(RangeSet<C> ranges) {
655      for (Range<C> range : ranges.asRanges()) {
656        add(range);
657      }
658      return this;
659    }
660
661    /**
662     * Returns an {@code ImmutableRangeSet} containing the ranges added to this builder.
663     */
664    public ImmutableRangeSet<C> build() {
665      return copyOf(rangeSet);
666    }
667  }
668
669  private static final class SerializedForm<C extends Comparable> implements Serializable {
670    private final ImmutableList<Range<C>> ranges;
671
672    SerializedForm(ImmutableList<Range<C>> ranges) {
673      this.ranges = ranges;
674    }
675
676    Object readResolve() {
677      if (ranges.isEmpty()) {
678        return of();
679      } else if (ranges.equals(ImmutableList.of(Range.all()))) {
680        return all();
681      } else {
682        return new ImmutableRangeSet<C>(ranges);
683      }
684    }
685  }
686
687  Object writeReplace() {
688    return new SerializedForm<C>(ranges);
689  }
690}