001/*
002 * Copyright (C) 2010 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 */
014
015package com.google.common.collect;
016
017import static com.google.common.base.Preconditions.checkArgument;
018import static com.google.common.base.Preconditions.checkNotNull;
019
020import com.google.common.annotations.GwtCompatible;
021import com.google.common.annotations.GwtIncompatible;
022import java.util.Collections;
023import java.util.NoSuchElementException;
024import java.util.Set;
025
026/**
027 * A sorted set of contiguous values in a given {@link DiscreteDomain}.
028 *
029 * <p><b>Warning:</b> Be extremely careful what you do with conceptually large instances (such as
030 * {@code ContiguousSet.create(Range.greaterThan(0), DiscreteDomain.integers()}). Certain
031 * operations on such a set can be performed efficiently, but others (such as {@link Set#hashCode}
032 * or {@link Collections#frequency}) can cause major performance problems.
033 *
034 * @author Gregory Kick
035 * @since 10.0
036 */
037@GwtCompatible(emulated = true)
038@SuppressWarnings("rawtypes") // allow ungenerified Comparable types
039public abstract class ContiguousSet<C extends Comparable> extends ImmutableSortedSet<C> {
040  /**
041   * Returns a {@code ContiguousSet} containing the same values in the given domain
042   * {@linkplain Range#contains contained} by the range.
043   *
044   * @throws IllegalArgumentException if neither range nor the domain has a lower bound, or if
045   *     neither has an upper bound
046   *
047   * @since 13.0
048   */
049  public static <C extends Comparable> ContiguousSet<C> create(
050      Range<C> range, DiscreteDomain<C> domain) {
051    checkNotNull(range);
052    checkNotNull(domain);
053    Range<C> effectiveRange = range;
054    try {
055      if (!range.hasLowerBound()) {
056        effectiveRange = effectiveRange.intersection(Range.atLeast(domain.minValue()));
057      }
058      if (!range.hasUpperBound()) {
059        effectiveRange = effectiveRange.intersection(Range.atMost(domain.maxValue()));
060      }
061    } catch (NoSuchElementException e) {
062      throw new IllegalArgumentException(e);
063    }
064
065    // Per class spec, we are allowed to throw CCE if necessary
066    boolean empty =
067        effectiveRange.isEmpty()
068            || Range.compareOrThrow(
069                    range.lowerBound.leastValueAbove(domain),
070                    range.upperBound.greatestValueBelow(domain))
071                > 0;
072
073    return empty
074        ? new EmptyContiguousSet<C>(domain)
075        : new RegularContiguousSet<C>(effectiveRange, domain);
076  }
077
078  final DiscreteDomain<C> domain;
079
080  ContiguousSet(DiscreteDomain<C> domain) {
081    super(Ordering.natural());
082    this.domain = domain;
083  }
084
085  @Override
086  public ContiguousSet<C> headSet(C toElement) {
087    return headSetImpl(checkNotNull(toElement), false);
088  }
089
090  /**
091   * @since 12.0
092   */
093  @GwtIncompatible // NavigableSet
094  @Override
095  public ContiguousSet<C> headSet(C toElement, boolean inclusive) {
096    return headSetImpl(checkNotNull(toElement), inclusive);
097  }
098
099  @Override
100  public ContiguousSet<C> subSet(C fromElement, C toElement) {
101    checkNotNull(fromElement);
102    checkNotNull(toElement);
103    checkArgument(comparator().compare(fromElement, toElement) <= 0);
104    return subSetImpl(fromElement, true, toElement, false);
105  }
106
107  /**
108   * @since 12.0
109   */
110  @GwtIncompatible // NavigableSet
111  @Override
112  public ContiguousSet<C> subSet(
113      C fromElement, boolean fromInclusive, C toElement, boolean toInclusive) {
114    checkNotNull(fromElement);
115    checkNotNull(toElement);
116    checkArgument(comparator().compare(fromElement, toElement) <= 0);
117    return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
118  }
119
120  @Override
121  public ContiguousSet<C> tailSet(C fromElement) {
122    return tailSetImpl(checkNotNull(fromElement), true);
123  }
124
125  /**
126   * @since 12.0
127   */
128  @GwtIncompatible // NavigableSet
129  @Override
130  public ContiguousSet<C> tailSet(C fromElement, boolean inclusive) {
131    return tailSetImpl(checkNotNull(fromElement), inclusive);
132  }
133
134  /*
135   * These methods perform most headSet, subSet, and tailSet logic, besides parameter validation.
136   */
137  // TODO(kevinb): we can probably make these real @Overrides now
138  /* @Override */
139  abstract ContiguousSet<C> headSetImpl(C toElement, boolean inclusive);
140
141  /* @Override */
142  abstract ContiguousSet<C> subSetImpl(
143      C fromElement, boolean fromInclusive, C toElement, boolean toInclusive);
144
145  /* @Override */
146  abstract ContiguousSet<C> tailSetImpl(C fromElement, boolean inclusive);
147
148  /**
149   * Returns the set of values that are contained in both this set and the other.
150   *
151   * <p>This method should always be used instead of
152   * {@link Sets#intersection} for {@link ContiguousSet} instances.
153   */
154  public abstract ContiguousSet<C> intersection(ContiguousSet<C> other);
155
156  /**
157   * Returns a range, closed on both ends, whose endpoints are the minimum and maximum values
158   * contained in this set.  This is equivalent to {@code range(CLOSED, CLOSED)}.
159   *
160   * @throws NoSuchElementException if this set is empty
161   */
162  public abstract Range<C> range();
163
164  /**
165   * Returns the minimal range with the given boundary types for which all values in this set are
166   * {@linkplain Range#contains(Comparable) contained} within the range.
167   *
168   * <p>Note that this method will return ranges with unbounded endpoints if {@link BoundType#OPEN}
169   * is requested for a domain minimum or maximum.  For example, if {@code set} was created from the
170   * range {@code [1..Integer.MAX_VALUE]} then {@code set.range(CLOSED, OPEN)} must return
171   * {@code [1..∞)}.
172   *
173   * @throws NoSuchElementException if this set is empty
174   */
175  public abstract Range<C> range(BoundType lowerBoundType, BoundType upperBoundType);
176
177  @Override
178  @GwtIncompatible // NavigableSet
179  ImmutableSortedSet<C> createDescendingSet() {
180    return new DescendingImmutableSortedSet<C>(this);
181  }
182
183  /** Returns a short-hand representation of the contents such as {@code "[1..100]"}. */
184  @Override
185  public String toString() {
186    return range().toString();
187  }
188
189  /**
190   * Not supported. {@code ContiguousSet} instances are constructed with {@link #create}. This
191   * method exists only to hide {@link ImmutableSet#builder} from consumers of {@code
192   * ContiguousSet}.
193   *
194   * @throws UnsupportedOperationException always
195   * @deprecated Use {@link #create}.
196   */
197  @Deprecated
198  public static <E> ImmutableSortedSet.Builder<E> builder() {
199    throw new UnsupportedOperationException();
200  }
201}