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 * An efficient immutable implementation of a {@link RangeSet}.
038 *
039 * @author Louis Wasserman
040 * @since 14.0
041 */
042@Beta
043public final class ImmutableRangeSet<C extends Comparable> extends AbstractRangeSet<C>
044    implements Serializable {
045
046  private static final ImmutableRangeSet<Comparable<?>> EMPTY =
047      new ImmutableRangeSet<Comparable<?>>(ImmutableList.<Range<Comparable<?>>>of());
048
049  private static final ImmutableRangeSet<Comparable<?>> ALL =
050      new ImmutableRangeSet<Comparable<?>>(ImmutableList.of(Range.<Comparable<?>>all()));
051
052  /**
053   * Returns an empty immutable range set.
054   */
055  @SuppressWarnings("unchecked")
056  public static <C extends Comparable> ImmutableRangeSet<C> of() {
057    return (ImmutableRangeSet<C>) EMPTY;
058  }
059
060  /**
061   * Returns an immutable range set containing the single range {@link Range#all()}.
062   */
063  @SuppressWarnings("unchecked")
064  static <C extends Comparable> ImmutableRangeSet<C> all() {
065    return (ImmutableRangeSet<C>) ALL;
066  }
067
068  /**
069   * Returns an immutable range set containing the specified single range. If {@link Range#isEmpty()
070   * range.isEmpty()}, this is equivalent to {@link ImmutableRangeSet#of()}.
071   */
072  public static <C extends Comparable> ImmutableRangeSet<C> of(Range<C> range) {
073    checkNotNull(range);
074    if (range.isEmpty()) {
075      return of();
076    } else if (range.equals(Range.all())) {
077      return all();
078    } else {
079      return new ImmutableRangeSet<C>(ImmutableList.of(range));
080    }
081  }
082
083  /**
084   * Returns an immutable copy of the specified {@code RangeSet}.
085   */
086  public static <C extends Comparable> ImmutableRangeSet<C> copyOf(RangeSet<C> rangeSet) {
087    checkNotNull(rangeSet);
088    if (rangeSet.isEmpty()) {
089      return of();
090    } else if (rangeSet.encloses(Range.<C>all())) {
091      return all();
092    }
093
094    if (rangeSet instanceof ImmutableRangeSet) {
095      ImmutableRangeSet<C> immutableRangeSet = (ImmutableRangeSet<C>) rangeSet;
096      if (!immutableRangeSet.isPartialView()) {
097        return immutableRangeSet;
098      }
099    }
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    // True if the "positive" range set is empty or bounded below.
187    private final boolean positiveBoundedBelow;
188
189    // True if the "positive" range set is empty or bounded above.
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   * Returns a list containing the nonempty intersections of {@code range}
258   * with the ranges in this range set.
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   * Returns a view of the intersection of this range set with the given range.
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   * Returns an {@link ImmutableSortedSet} containing the same values in the given domain
330   * {@linkplain RangeSet#contains contained} by this range set.
331   *
332   * <p><b>Note:</b> {@code a.asSet(d).equals(b.asSet(d))} does not imply {@code a.equals(b)}! For
333   * example, {@code a} and {@code b} could be {@code [2..4]} and {@code (1..5)}, or the empty
334   * ranges {@code [3..3)} and {@code [4..4)}.
335   *
336   * <p><b>Warning:</b> Be extremely careful what you do with the {@code asSet} view of a large
337   * range set (such as {@code ImmutableRangeSet.of(Range.greaterThan(0))}). Certain operations on
338   * such a set can be performed efficiently, but others (such as {@link Set#hashCode} or
339   * {@link Collections#frequency}) can cause major performance problems.
340   *
341   * <p>The returned set's {@link Object#toString} method returns a short-hand form of the set's
342   * contents, such as {@code "[1..100]}"}.
343   *
344   * @throws IllegalArgumentException if neither this range nor the domain has a lower bound, or if
345   *         neither has an upper bound
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      // according to the spec of canonical, neither this ImmutableRangeSet nor
355      // the range have a lower bound
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      // racy single-check idiom
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") // we catch CCE's
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") // if it's contained, it's definitely a C
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   * Returns {@code true} if this immutable range set's implementation contains references to
527   * user-created objects that aren't accessible via this range set's methods. This is generally
528   * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid
529   * memory leaks.
530   */
531  boolean isPartialView() {
532    return ranges.isPartialView();
533  }
534
535  /**
536   * Returns a new builder for an immutable range set.
537   */
538  public static <C extends Comparable<?>> Builder<C> builder() {
539    return new Builder<C>();
540  }
541
542  /**
543   * A builder for immutable range sets.
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     * Add the specified range to this builder.  Adjacent/abutting ranges are permitted, but
554     * empty ranges, or ranges with nonempty overlap, are forbidden.
555     *
556     * @throws IllegalArgumentException if {@code range} is empty or has nonempty intersection with
557     *         any ranges already added to the builder
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     * Add all ranges from the specified range set to this builder. Duplicate or connected ranges
576     * are permitted, and will be merged in the resulting immutable range set.
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     * Returns an {@code ImmutableRangeSet} containing the ranges added to this builder.
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}