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