Java example source code file (ImmutableRangeSet.java)

This example Java source code file (ImmutableRangeSet.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

annotation, builder, comparable, deprecated, discretedomain, immutablelist, immutablerangeset, immutablesortedset, object, override, range, suppresswarnings, unsupportedoperationexception, util

The ImmutableRangeSet.java Java example source code

/*
 * 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_HIGHER;
import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_LOWER;
import static com.google.common.collect.SortedLists.KeyPresentBehavior.ANY_PRESENT;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.collect.SortedLists.KeyAbsentBehavior;
import com.google.common.collect.SortedLists.KeyPresentBehavior;
import com.google.common.primitives.Ints;
import com.google.errorprone.annotations.CanIgnoreReturnValue;

import java.io.Serializable;
import java.util.Collections;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;

import javax.annotation.Nullable;

/**
 * A {@link RangeSet} whose contents will never change, with many other important properties
 * detailed at {@link ImmutableCollection}.
 *
 * @author Louis Wasserman
 * @since 14.0
 */
@Beta
@GwtIncompatible
public final class ImmutableRangeSet<C extends Comparable> extends AbstractRangeSet
    implements Serializable {

  private static final ImmutableRangeSet<Comparable EMPTY =
      new ImmutableRangeSet<Comparable(ImmutableList.>>of());

  private static final ImmutableRangeSet<Comparable ALL =
      new ImmutableRangeSet<Comparable(ImmutableList.of(Range.>all()));

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

  /**
   * Returns an immutable range set containing the single range {@link Range#all()}.
   */
  @SuppressWarnings("unchecked")
  static <C extends Comparable> ImmutableRangeSet all() {
    return (ImmutableRangeSet<C>) ALL;
  }

  /**
   * Returns an immutable range set containing the specified single range. If {@link Range#isEmpty()
   * range.isEmpty()}, this is equivalent to {@link ImmutableRangeSet#of()}.
   */
  public static <C extends Comparable> ImmutableRangeSet of(Range 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 {@code RangeSet}.
   */
  public static <C extends Comparable> ImmutableRangeSet copyOf(RangeSet 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) rangeSet;
      if (!immutableRangeSet.isPartialView()) {
        return immutableRangeSet;
      }
    }
    return new ImmutableRangeSet<C>(ImmutableList.copyOf(rangeSet.asRanges()));
  }

  ImmutableRangeSet(ImmutableList<Range ranges) {
    this.ranges = ranges;
  }

  private ImmutableRangeSet(ImmutableList<Range ranges, ImmutableRangeSet complement) {
    this.ranges = ranges;
    this.complement = complement;
  }

  private final transient ImmutableList<Range ranges;

  @Override
  public boolean intersects(Range<C> otherRange) {
    int ceilingIndex =
        SortedLists.binarySearch(
            ranges,
            Range.<C>lowerBoundFn(),
            otherRange.lowerBound,
            Ordering.natural(),
            ANY_PRESENT,
            NEXT_HIGHER);
    if (ceilingIndex < ranges.size()
        && ranges.get(ceilingIndex).isConnected(otherRange)
        && !ranges.get(ceilingIndex).intersection(otherRange).isEmpty()) {
      return true;
    }
    return ceilingIndex > 0
        && ranges.get(ceilingIndex - 1).isConnected(otherRange)
        && !ranges.get(ceilingIndex - 1).intersection(otherRange).isEmpty();
  }

  @Override
  public boolean encloses(Range<C> otherRange) {
    int index =
        SortedLists.binarySearch(
            ranges,
            Range.<C>lowerBoundFn(),
            otherRange.lowerBound,
            Ordering.natural(),
            ANY_PRESENT,
            NEXT_LOWER);
    return index != -1 && ranges.get(index).encloses(otherRange);
  }

  @Override
  public Range<C> rangeContaining(C value) {
    int index =
        SortedLists.binarySearch(
            ranges,
            Range.<C>lowerBoundFn(),
            Cut.belowValue(value),
            Ordering.natural(),
            ANY_PRESENT,
            NEXT_LOWER);
    if (index != -1) {
      Range<C> range = ranges.get(index);
      return range.contains(value) ? range : null;
    }
    return null;
  }

  @Override
  public Range<C> span() {
    if (ranges.isEmpty()) {
      throw new NoSuchElementException();
    }
    return Range.create(ranges.get(0).lowerBound, ranges.get(ranges.size() - 1).upperBound);
  }

  @Override
  public boolean isEmpty() {
    return ranges.isEmpty();
  }

  /**
   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
   *
   * @throws UnsupportedOperationException always
   * @deprecated Unsupported operation.
   */
  @Deprecated
  @Override
  public void add(Range<C> range) {
    throw new UnsupportedOperationException();
  }

  /**
   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
   *
   * @throws UnsupportedOperationException always
   * @deprecated Unsupported operation.
   */
  @Deprecated
  @Override
  public void addAll(RangeSet<C> other) {
    throw new UnsupportedOperationException();
  }

  /**
   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
   *
   * @throws UnsupportedOperationException always
   * @deprecated Unsupported operation.
   */
  @Deprecated
  @Override
  public void remove(Range<C> range) {
    throw new UnsupportedOperationException();
  }

  /**
   * Guaranteed to throw an exception and leave the {@code RangeSet} unmodified.
   *
   * @throws UnsupportedOperationException always
   * @deprecated Unsupported operation.
   */
  @Deprecated
  @Override
  public void removeAll(RangeSet<C> other) {
    throw new UnsupportedOperationException();
  }

  @Override
  public ImmutableSet<Range asRanges() {
    if (ranges.isEmpty()) {
      return ImmutableSet.of();
    }
    return new RegularImmutableSortedSet<Range(ranges, Range.RANGE_LEX_ORDERING);
  }

  @Override
  public ImmutableSet<Range asDescendingSetOfRanges() {
    if (ranges.isEmpty()) {
      return ImmutableSet.of();
    }
    return new RegularImmutableSortedSet<Range(
        ranges.reverse(), Range.RANGE_LEX_ORDERING.reverse());
  }

  private transient ImmutableRangeSet<C> complement;

  private final class ComplementRanges extends ImmutableList<Range {
    // 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.positiveBoundedBelow = ranges.get(0).hasLowerBound();
      this.positiveBoundedAbove = Iterables.getLast(ranges).hasUpperBound();

      int size = ranges.size() - 1;
      if (positiveBoundedBelow) {
        size++;
      }
      if (positiveBoundedAbove) {
        size++;
      }
      this.size = size;
    }

    @Override
    public int size() {
      return size;
    }

    @Override
    public Range<C> get(int index) {
      checkElementIndex(index, size);

      Cut<C> lowerBound;
      if (positiveBoundedBelow) {
        lowerBound = (index == 0) ? Cut.<C>belowAll() : ranges.get(index - 1).upperBound;
      } else {
        lowerBound = ranges.get(index).upperBound;
      }

      Cut<C> upperBound;
      if (positiveBoundedAbove && index == size - 1) {
        upperBound = Cut.<C>aboveAll();
      } else {
        upperBound = ranges.get(index + (positiveBoundedBelow ? 0 : 1)).lowerBound;
      }

      return Range.create(lowerBound, upperBound);
    }

    @Override
    boolean isPartialView() {
      return true;
    }
  }

  @Override
  public ImmutableRangeSet<C> complement() {
    ImmutableRangeSet<C> result = complement;
    if (result != null) {
      return result;
    } else if (ranges.isEmpty()) {
      return complement = all();
    } else if (ranges.size() == 1 && ranges.get(0).equals(Range.all())) {
      return complement = of();
    } else {
      ImmutableList<Range complementRanges = new ComplementRanges();
      result = complement = new ImmutableRangeSet<C>(complementRanges, this);
    }
    return result;
  }

  /**
   * Returns a list containing the nonempty intersections of {@code range}
   * with the ranges in this range set.
   */
  private ImmutableList<Range intersectRanges(final Range range) {
    if (ranges.isEmpty() || range.isEmpty()) {
      return ImmutableList.of();
    } else if (range.encloses(span())) {
      return ranges;
    }

    final int fromIndex;
    if (range.hasLowerBound()) {
      fromIndex =
          SortedLists.binarySearch(
              ranges,
              Range.<C>upperBoundFn(),
              range.lowerBound,
              KeyPresentBehavior.FIRST_AFTER,
              KeyAbsentBehavior.NEXT_HIGHER);
    } else {
      fromIndex = 0;
    }

    int toIndex;
    if (range.hasUpperBound()) {
      toIndex =
          SortedLists.binarySearch(
              ranges,
              Range.<C>lowerBoundFn(),
              range.upperBound,
              KeyPresentBehavior.FIRST_PRESENT,
              KeyAbsentBehavior.NEXT_HIGHER);
    } else {
      toIndex = ranges.size();
    }
    final int length = toIndex - fromIndex;
    if (length == 0) {
      return ImmutableList.of();
    } else {
      return new ImmutableList<Range() {
        @Override
        public int size() {
          return length;
        }

        @Override
        public Range<C> get(int index) {
          checkElementIndex(index, length);
          if (index == 0 || index == length - 1) {
            return ranges.get(index + fromIndex).intersection(range);
          } else {
            return ranges.get(index + fromIndex);
          }
        }

        @Override
        boolean isPartialView() {
          return true;
        }
      };
    }
  }

  /**
   * Returns a view of the intersection of this range set with the given range.
   */
  @Override
  public ImmutableRangeSet<C> subRangeSet(Range 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 {@link ImmutableSortedSet} containing the same values in the given domain
   * {@linkplain RangeSet#contains contained} by this range set.
   *
   * <p>Note: {@code a.asSet(d).equals(b.asSet(d))} does not imply {@code a.equals(b)}! For
   * example, {@code a} and {@code b} could be {@code [2..4]} and {@code (1..5)}, or the empty
   * ranges {@code [3..3)} and {@code [4..4)}.
   *
   * <p>Warning: Be extremely careful what you do with the {@code asSet} view of a large
   * range set (such as {@code ImmutableRangeSet.of(Range.greaterThan(0))}). Certain operations on
   * such a set can be performed efficiently, but others (such as {@link Set#hashCode} or
   * {@link Collections#frequency}) can cause major performance problems.
   *
   * <p>The returned set's {@link Object#toString} method returns a short-hand form of the set's
   * contents, such as {@code "[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 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 = domain;
    }

    private transient Integer size;

    @Override
    public int size() {
      // racy single-check idiom
      Integer result = size;
      if (result == null) {
        long total = 0;
        for (Range<C> range : ranges) {
          total += ContiguousSet.create(range, domain).size();
          if (total >= Integer.MAX_VALUE) {
            break;
          }
        }
        result = size = Ints.saturatedCast(total);
      }
      return result.intValue();
    }

    @Override
    public UnmodifiableIterator<C> iterator() {
      return new AbstractIterator<C>() {
        final Iterator<Range rangeItr = ranges.iterator();
        Iterator<C> elemItr = Iterators.emptyIterator();

        @Override
        protected C computeNext() {
          while (!elemItr.hasNext()) {
            if (rangeItr.hasNext()) {
              elemItr = ContiguousSet.create(rangeItr.next(), domain).iterator();
            } else {
              return endOfData();
            }
          }
          return elemItr.next();
        }
      };
    }

    @Override
    @GwtIncompatible("NavigableSet")
    public UnmodifiableIterator<C> descendingIterator() {
      return new AbstractIterator<C>() {
        final Iterator<Range rangeItr = ranges.reverse().iterator();
        Iterator<C> elemItr = Iterators.emptyIterator();

        @Override
        protected C computeNext() {
          while (!elemItr.hasNext()) {
            if (rangeItr.hasNext()) {
              elemItr = ContiguousSet.create(rangeItr.next(), domain).descendingIterator();
            } else {
              return endOfData();
            }
          }
          return elemItr.next();
        }
      };
    }

    ImmutableSortedSet<C> subSet(Range range) {
      return subRangeSet(range).asSet(domain);
    }

    @Override
    ImmutableSortedSet<C> headSetImpl(C toElement, boolean inclusive) {
      return subSet(Range.upTo(toElement, BoundType.forBoolean(inclusive)));
    }

    @Override
    ImmutableSortedSet<C> subSetImpl(
        C fromElement, boolean fromInclusive, C toElement, boolean toInclusive) {
      if (!fromInclusive && !toInclusive && Range.compareOrThrow(fromElement, toElement) == 0) {
        return ImmutableSortedSet.of();
      }
      return subSet(
          Range.range(
              fromElement, BoundType.forBoolean(fromInclusive),
              toElement, BoundType.forBoolean(toInclusive)));
    }

    @Override
    ImmutableSortedSet<C> tailSetImpl(C fromElement, boolean 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 : ranges) {
          if (range.contains(c)) {
            return Ints.saturatedCast(total + ContiguousSet.create(range, domain).indexOf(c));
          } else {
            total += ContiguousSet.create(range, domain).size();
          }
        }
        throw new AssertionError("impossible");
      }
      return -1;
    }

    @Override
    boolean isPartialView() {
      return ranges.isPartialView();
    }

    @Override
    public String toString() {
      return ranges.toString();
    }

    @Override
    Object writeReplace() {
      return new AsSetSerializedForm<C>(ranges, domain);
    }
  }

  private static class AsSetSerializedForm<C extends Comparable> implements Serializable {
    private final ImmutableList<Range ranges;
    private final DiscreteDomain<C> domain;

    AsSetSerializedForm(ImmutableList<Range ranges, DiscreteDomain domain) {
      this.ranges = ranges;
      this.domain = domain;
    }

    Object readResolve() {
      return new ImmutableRangeSet<C>(ranges).asSet(domain);
    }
  }

  /**
   * Returns {@code 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 {@code copyOf} implementations should make an explicit copy to avoid
   * memory leaks.
   */
  boolean isPartialView() {
    return ranges.isPartialView();
  }

  /**
   * Returns a new builder for an immutable range set.
   */
  public static <C extends Comparable Builder 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.rangeSet = 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 {@code range} is empty or has nonempty intersection with
     *         any ranges already added to the builder
     */
    @CanIgnoreReturnValue
    public Builder<C> add(Range range) {
      if (range.isEmpty()) {
        throw new IllegalArgumentException("range must not be empty, but was " + range);
      } else if (!rangeSet.complement().encloses(range)) {
        for (Range<C> currentRange : rangeSet.asRanges()) {
          checkArgument(
              !currentRange.isConnected(range) || currentRange.intersection(range).isEmpty(),
              "Ranges may not overlap, but received %s and %s",
              currentRange,
              range);
        }
        throw new AssertionError("should have thrown an IAE above");
      }
      rangeSet.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.
     */
    @CanIgnoreReturnValue
    public Builder<C> addAll(RangeSet ranges) {
      for (Range<C> range : ranges.asRanges()) {
        add(range);
      }
      return this;
    }

    /**
     * Returns an {@code ImmutableRangeSet} containing the ranges added to this builder.
     */
    public ImmutableRangeSet<C> build() {
      return copyOf(rangeSet);
    }
  }

  private static final class SerializedForm<C extends Comparable> implements Serializable {
    private final ImmutableList<Range ranges;

    SerializedForm(ImmutableList<Range ranges) {
      this.ranges = ranges;
    }

    Object readResolve() {
      if (ranges.isEmpty()) {
        return of();
      } else if (ranges.equals(ImmutableList.of(Range.all()))) {
        return all();
      } else {
        return new ImmutableRangeSet<C>(ranges);
      }
    }
  }

  Object writeReplace() {
    return new SerializedForm<C>(ranges);
  }
}