Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Copyright (C) 2012 The Guava Authors
   *
   * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
   * in compliance with the License. You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software distributed under the License
  * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
  * or implied. See the License for the specific language governing permissions and limitations under
  * the License.
  */
 package com.google.common.collect;
 
 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkElementIndex;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_LOWER;
 import static com.google.common.collect.SortedLists.KeyPresentBehavior.ANY_PRESENT;
 
 
 import java.util.Set;
 
 import  javax.annotation.Nullable;

An efficient immutable implementation of a RangeSet.

Author(s):
Louis Wasserman
Since:
14.0
 
 public final class ImmutableRangeSet<C extends Comparableextends AbstractRangeSet<C>
     implements Serializable {
 
   @SuppressWarnings("unchecked")
   private static final ImmutableRangeSet EMPTY = new ImmutableRangeSet(ImmutableList.of());
 
   @SuppressWarnings("unchecked")
   private static final ImmutableRangeSet ALL = new ImmutableRangeSet(ImmutableList.of(Range.all()));

  
Returns an empty immutable range set.
 
   @SuppressWarnings("unchecked")
   public static <C extends ComparableImmutableRangeSet<C> of() {
     return ;
   }

  
Returns an immutable range set containing the single range Range.all().
 
   @SuppressWarnings("unchecked")
   static <C extends ComparableImmutableRangeSet<C> all() {
     return ;
   }

  
Returns an immutable range set containing the specified single range. If range.isEmpty(), this is equivalent to ImmutableRangeSet.of().
 
   public static <C extends ComparableImmutableRangeSet<C> of(Range<C> range) {
     checkNotNull(range);
     if (range.isEmpty()) {
       return of();
     } else if (range.equals(Range.all())) {
       return all();
     } else {
       return new ImmutableRangeSet<C>(ImmutableList.of(range));
     }
   }

  
Returns an immutable copy of the specified RangeSet.
 
   public static <C extends ComparableImmutableRangeSet<C> copyOf(RangeSet<C> rangeSet) {
     checkNotNull(rangeSet);
     if (rangeSet.isEmpty()) {
       return of();
     } else if (rangeSet.encloses(Range.<C>all())) {
       return all();
     }
 
     if (rangeSet instanceof ImmutableRangeSet) {
       ImmutableRangeSet<C> immutableRangeSet = (ImmutableRangeSet<C>) rangeSet;
       if (!immutableRangeSet.isPartialView()) {
         return immutableRangeSet;
       }
     }
    return new ImmutableRangeSet<C>(ImmutableList.copyOf(rangeSet.asRanges()));
  }
    this. = ranges;
  }
  private ImmutableRangeSet(ImmutableList<Range<C>> rangesImmutableRangeSet<C> complement) {
    this. = ranges;
    this. = complement;
  }
  private transient final ImmutableList<Range<C>> ranges;
  public boolean encloses(Range<C> otherRange) {
    int index = SortedLists.binarySearch(,
        Range.<C>lowerBoundFn(),
        otherRange.lowerBound,
        Ordering.natural(),
        ,
        );
    return index != -1 && .get(index).encloses(otherRange);
  }
  public Range<C> rangeContaining(C value) {
    int index = SortedLists.binarySearch(,
        Range.<C>lowerBoundFn(),
        Cut.belowValue(value),
        Ordering.natural(),
        ,
        );
    if (index != -1) {
      Range<C> range = .get(index);
      return range.contains(value) ? range : null;
    }
    return null;
  }
  public Range<C> span() {
    if (.isEmpty()) {
      throw new NoSuchElementException();
    }
    return Range.create(
        .get(0).,
        .get(.size() - 1).);
  }
  public boolean isEmpty() {
    return .isEmpty();
  }
  public void add(Range<C> range) {
    throw new UnsupportedOperationException();
  }
  public void addAll(RangeSet<C> other) {
    throw new UnsupportedOperationException();
  }
  public void remove(Range<C> range) {
    throw new UnsupportedOperationException();
  }
  public void removeAll(RangeSet<C> other) {
    throw new UnsupportedOperationException();
  }
  public ImmutableSet<Range<C>> asRanges() {
    if (.isEmpty()) {
      return ImmutableSet.of();
    }
  }
  private transient ImmutableRangeSet<C> complement;
  private final class ComplementRanges extends ImmutableList<Range<C>> {
    // True if the "positive" range set is empty or bounded below.
    private final boolean positiveBoundedBelow;
    // True if the "positive" range set is empty or bounded above.
    private final boolean positiveBoundedAbove;
    private final int size;
    ComplementRanges() {
      this. = .get(0).hasLowerBound();
      this. = Iterables.getLast().hasUpperBound();
      int size = .size() - 1;
      if () {
        size++;
      }
      if () {
        size++;
      }
      this. = size;
    }
    @Override
    public int size() {
      return ;
    }
    @Override
    public Range<C> get(int index) {
      checkElementIndex(index);
      Cut<C> lowerBound;
      if () {
        lowerBound = (index == 0) ? Cut.<C>belowAll() : .get(index - 1).;
      } else {
        lowerBound = .get(index).;
      }
      Cut<C> upperBound;
      if ( && index ==  - 1) {
        upperBound = Cut.<C>aboveAll();
      } else {
        upperBound = .get(index + ( ? 0 : 1)).;
      }
      return Range.create(lowerBoundupperBound);
    }
    @Override
    boolean isPartialView() {
      return true;
    }
  }
  public ImmutableRangeSet<C> complement() {
    ImmutableRangeSet<C> result = ;
    if (result != null) {
      return result;
    } else if (.isEmpty()) {
      return  = all();
    } else if (.size() == 1 && .get(0).equals(Range.all())) {
      return  = of();
    } else {
      ImmutableList<Range<C>> complementRanges = new ComplementRanges();
      result =  = new ImmutableRangeSet<C>(complementRangesthis);
    }
    return result;
  }

  
Returns a list containing the nonempty intersections of range with the ranges in this range set.
  private ImmutableList<Range<C>> intersectRanges(final Range<C> range) {
    if (.isEmpty() || range.isEmpty()) {
      return ImmutableList.of();
    } else if (range.encloses(span())) {
      return ;
    }
    final int fromIndex;
    if (range.hasLowerBound()) {
      fromIndex = SortedLists.binarySearch(
          , Range.<C>upperBoundFn(), range.lowerBound.,
          .);
    } else {
      fromIndex = 0;
    }
    int toIndex;
    if (range.hasUpperBound()) {
      toIndex = SortedLists.binarySearch(
          , Range.<C>lowerBoundFn(), range.upperBound.,
          .);
    } else {
      toIndex = .size();
    }
    final int length = toIndex - fromIndex;
    if (length == 0) {
      return ImmutableList.of();
    } else {
      return new ImmutableList<Range<C>>() {
        @Override
        public int size() {
          return length;
        }
        @Override
        public Range<C> get(int index) {
          checkElementIndex(indexlength);
          if (index == 0 || index == length - 1) {
            return .get(index + fromIndex).intersection(range);
          } else {
            return .get(index + fromIndex);
          }
        }
        @Override
        boolean isPartialView() {
          return true;
        }
      };
    }
  }
  
  
Returns a view of the intersection of this range set with the given range.
  public ImmutableRangeSet<C> subRangeSet(Range<C> range) {
    if (!isEmpty()) {
      Range<C> span = span();
      if (range.encloses(span)) {
        return this;
      } else if (range.isConnected(span)) {
        return new ImmutableRangeSet<C>(intersectRanges(range));
      }
    }
    return of();
  }

  
Returns an ImmutableSortedSet containing the same values in the given domain contained by this range set.

Note: a.asSet(d).equals(b.asSet(d)) does not imply a.equals(b)! For example, a and b could be [2..4] and (1..5), or the empty ranges [3..3) and [4..4).

Warning: Be extremely careful what you do with the asSet view of a large range set (such as ImmutableRangeSet.of(Range.greaterThan(0))). Certain operations on such a set can be performed efficiently, but others (such as Set.hashCode or Collections.frequency) can cause major performance problems.

The returned set's Object.toString method returns a short-hand form of the set's contents, such as "[1..100]"}.

Throws:
IllegalArgumentException if neither this range nor the domain has a lower bound, or if neither has an upper bound
  public ImmutableSortedSet<C> asSet(DiscreteDomain<C> domain) {
    checkNotNull(domain);
    if (isEmpty()) {
      return ImmutableSortedSet.of();
    }
    Range<C> span = span().canonical(domain);
    if (!span.hasLowerBound()) {
      // according to the spec of canonical, neither this ImmutableRangeSet nor
      // the range have a lower bound
      throw new IllegalArgumentException(
          "Neither the DiscreteDomain nor this range set are bounded below");
    } else if (!span.hasUpperBound()) {
      try {
        domain.maxValue();
      } catch (NoSuchElementException e) {
        throw new IllegalArgumentException(
            "Neither the DiscreteDomain nor this range set are bounded above");
      }
    }
    return new AsSet(domain);
  }
  private final class AsSet extends ImmutableSortedSet<C> {
    private final DiscreteDomain<C> domain;
    AsSet(DiscreteDomain<C> domain) {
      super(Ordering.natural());
      this. = domain;
    }
    private transient Integer size;
    @Override
    public int size() {
      // racy single-check idiom
      Integer result = ;
      if (result == null) {
        long total = 0;
        for (Range<C> range : ) {
          total += ContiguousSet.create(range).size();
          if (total >= .) {
            break;
          }
        }
        result =  = Ints.saturatedCast(total);
      }
      return result.intValue();
    }
    @Override
    public UnmodifiableIterator<C> iterator() {
      return new AbstractIterator<C>() {
        final Iterator<Range<C>> rangeItr = .iterator();
        Iterator<C> elemItr = Iterators.emptyIterator();
        @Override
        protected C computeNext() {
          while (!.hasNext()) {
            if (.hasNext()) {
               = ContiguousSet.create(.next(), ).iterator();
            } else {
              return endOfData();
            }
          }
          return .next();
        }
      };
    }
    @Override
    @GwtIncompatible("NavigableSet")
      return new AbstractIterator<C>() {
        final Iterator<Range<C>> rangeItr = .reverse().iterator();
        Iterator<C> elemItr = Iterators.emptyIterator();
        @Override
        protected C computeNext() {
          while (!.hasNext()) {
            if (.hasNext()) {
               = ContiguousSet.create(.next(), ).descendingIterator();
            } else {
              return endOfData();
            }
          }
          return .next();
        }
      };
    }
    ImmutableSortedSet<C> subSet(Range<C> range) {
      return subRangeSet(range).asSet();
    }
    @Override
    ImmutableSortedSet<C> headSetImpl(C toElementboolean inclusive) {
      return subSet(Range.upTo(toElement, BoundType.forBoolean(inclusive)));
    }
    @Override
        C fromElementboolean fromInclusive, C toElementboolean toInclusive) {
      if (!fromInclusive && !toInclusive && Range.compareOrThrow(fromElementtoElement) == 0) {
        return ImmutableSortedSet.of();
      }
      return subSet(Range.range(
          fromElement, BoundType.forBoolean(fromInclusive),
          toElement, BoundType.forBoolean(toInclusive)));
    }
    @Override
    ImmutableSortedSet<C> tailSetImpl(C fromElementboolean inclusive) {
      return subSet(Range.downTo(fromElement, BoundType.forBoolean(inclusive)));
    }
    @Override
    public boolean contains(@Nullable Object o) {
      if (o == null) {
        return false;
      }
      try {
        @SuppressWarnings("unchecked"// we catch CCE's
        C c = (C) o;
        return ImmutableRangeSet.this.contains(c);
      } catch (ClassCastException e) {
        return false;
      }
    }
    @Override
    int indexOf(Object target) {
      if (contains(target)) {
        @SuppressWarnings("unchecked"// if it's contained, it's definitely a C
        C c = (C) target;
        long total = 0;
        for (Range<C> range : ) {
          if (range.contains(c)) {
            return Ints.saturatedCast(total + ContiguousSet.create(range).indexOf(c));
          } else {
            total += ContiguousSet.create(range).size();
          }
        }
        throw new AssertionError("impossible");
      }
      return -1;
    }
    @Override
    boolean isPartialView() {
      return .isPartialView();
    }
    @Override
    public String toString() {
      return .toString();
    }
    @Override
    Object writeReplace() {
      return new AsSetSerializedForm<C>();
    }
  }
  private static class AsSetSerializedForm<C extends Comparableimplements Serializable {
    private final ImmutableList<Range<C>> ranges;
    private final DiscreteDomain<C> domain;
    AsSetSerializedForm(ImmutableList<Range<C>> rangesDiscreteDomain<C> domain) {
      this. = ranges;
      this. = domain;
    }
    Object readResolve() {
      return new ImmutableRangeSet<C>().asSet();
    }
  }

  
Returns true if this immutable range set's implementation contains references to user-created objects that aren't accessible via this range set's methods. This is generally used to determine whether copyOf implementations should make an explicit copy to avoid memory leaks.
  boolean isPartialView() {
    return .isPartialView();
  }

  
Returns a new builder for an immutable range set.
  public static <C extends Comparable<?>> Builder<C> builder() {
    return new Builder<C>();
  }

  
A builder for immutable range sets.
  public static class Builder<C extends Comparable<?>> {
    private final RangeSet<C> rangeSet;
    public Builder() {
      this. = TreeRangeSet.create();
    }

    
Add the specified range to this builder. Adjacent/abutting ranges are permitted, but empty ranges, or ranges with nonempty overlap, are forbidden.

Throws:
IllegalArgumentException if range is empty or has nonempty intersection with any ranges already added to the builder
    public Builder<C> add(Range<C> range) {
      if (range.isEmpty()) {
        throw new IllegalArgumentException("range must not be empty, but was " + range);
      } else if (!.complement().encloses(range)) {
        for (Range<C> currentRange : .asRanges()) {
          checkArgument(
              !currentRange.isConnected(range) || currentRange.intersection(range).isEmpty(),
              "Ranges may not overlap, but received %s and %s"currentRangerange);
        }
        throw new AssertionError("should have thrown an IAE above");
      }
      .add(range);
      return this;
    }

    
Add all ranges from the specified range set to this builder. Duplicate or connected ranges are permitted, and will be merged in the resulting immutable range set.
    public Builder<C> addAll(RangeSet<C> ranges) {
      for (Range<C> range : ranges.asRanges()) {
        add(range);
      }
      return this;
    }

    
Returns an ImmutableRangeSet containing the ranges added to this builder.
    public ImmutableRangeSet<C> build() {
      return copyOf();
    }
  }
  private static final class SerializedForm<C extends Comparableimplements Serializable {
    private final ImmutableList<Range<C>> ranges;
    SerializedForm(ImmutableList<Range<C>> ranges) {
      this. = ranges;
    }
    Object readResolve() {
      if (.isEmpty()) {
        return of();
      } else if (.equals(ImmutableList.of(Range.all()))) {
        return all();
      } else {
        return new ImmutableRangeSet<C>();
      }
    }
  }
    return new SerializedForm<C>();
  }
New to GrepCode? Check out our FAQ X