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