1/*
2 * Copyright (C) 2010 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15package com.google.common.collect;
16
17import static com.google.common.base.Preconditions.checkArgument;
18import static com.google.common.base.Preconditions.checkNotNull;
19
20import com.google.common.annotations.Beta;
21import com.google.common.annotations.GwtCompatible;
22import com.google.common.annotations.GwtIncompatible;
23
24import java.util.Collections;
25import java.util.NoSuchElementException;
26import java.util.Set;
27
28/**
29 * A sorted set of contiguous values in a given {@link DiscreteDomain}.
30 *
31 * <p><b>Warning:</b> Be extremely careful what you do with conceptually large instances (such as
32 * {@code ContiguousSet.create(Range.greaterThan(0), DiscreteDomain.integers()}). Certain
33 * operations on such a set can be performed efficiently, but others (such as {@link Set#hashCode}
34 * or {@link Collections#frequency}) can cause major performance problems.
35 *
36 * @author Gregory Kick
37 * @since 10.0
38 */
39@Beta
40@GwtCompatible(emulated = true)
41@SuppressWarnings("rawtypes") // allow ungenerified Comparable types
42public abstract class ContiguousSet<C extends Comparable> extends ImmutableSortedSet<C> {
43  /**
44   * Returns a {@code ContiguousSet} containing the same values in the given domain
45   * {@linkplain Range#contains contained} by the range.
46   *
47   * @throws IllegalArgumentException if neither range nor the domain has a lower bound, or if
48   *     neither has an upper bound
49   *
50   * @since 13.0
51   */
52  public static <C extends Comparable> ContiguousSet<C> create(
53      Range<C> range, DiscreteDomain<C> domain) {
54    checkNotNull(range);
55    checkNotNull(domain);
56    Range<C> effectiveRange = range;
57    try {
58      if (!range.hasLowerBound()) {
59        effectiveRange = effectiveRange.intersection(Range.atLeast(domain.minValue()));
60      }
61      if (!range.hasUpperBound()) {
62        effectiveRange = effectiveRange.intersection(Range.atMost(domain.maxValue()));
63      }
64    } catch (NoSuchElementException e) {
65      throw new IllegalArgumentException(e);
66    }
67
68    // Per class spec, we are allowed to throw CCE if necessary
69    boolean empty = effectiveRange.isEmpty()
70        || Range.compareOrThrow(
71            range.lowerBound.leastValueAbove(domain),
72            range.upperBound.greatestValueBelow(domain)) > 0;
73
74    return empty
75        ? new EmptyContiguousSet<C>(domain)
76        : new RegularContiguousSet<C>(effectiveRange, domain);
77  }
78
79  final DiscreteDomain<C> domain;
80
81  ContiguousSet(DiscreteDomain<C> domain) {
82    super(Ordering.natural());
83    this.domain = domain;
84  }
85
86  @Override public ContiguousSet<C> headSet(C toElement) {
87    return headSetImpl(checkNotNull(toElement), false);
88  }
89
90  /**
91   * @since 12.0
92   */
93  @GwtIncompatible("NavigableSet")
94  @Override public ContiguousSet<C> headSet(C toElement, boolean inclusive) {
95    return headSetImpl(checkNotNull(toElement), inclusive);
96  }
97
98  @Override public ContiguousSet<C> subSet(C fromElement, C toElement) {
99    checkNotNull(fromElement);
100    checkNotNull(toElement);
101    checkArgument(comparator().compare(fromElement, toElement) <= 0);
102    return subSetImpl(fromElement, true, toElement, false);
103  }
104
105  /**
106   * @since 12.0
107   */
108  @GwtIncompatible("NavigableSet")
109  @Override public ContiguousSet<C> subSet(C fromElement, boolean fromInclusive, C toElement,
110      boolean toInclusive) {
111    checkNotNull(fromElement);
112    checkNotNull(toElement);
113    checkArgument(comparator().compare(fromElement, toElement) <= 0);
114    return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
115  }
116
117  @Override public ContiguousSet<C> tailSet(C fromElement) {
118    return tailSetImpl(checkNotNull(fromElement), true);
119  }
120
121  /**
122   * @since 12.0
123   */
124  @GwtIncompatible("NavigableSet")
125  @Override public ContiguousSet<C> tailSet(C fromElement, boolean inclusive) {
126    return tailSetImpl(checkNotNull(fromElement), inclusive);
127  }
128
129  /*
130   * These methods perform most headSet, subSet, and tailSet logic, besides parameter validation.
131   */
132  /*@Override*/ abstract ContiguousSet<C> headSetImpl(C toElement, boolean inclusive);
133
134  /*@Override*/ abstract ContiguousSet<C> subSetImpl(C fromElement, boolean fromInclusive,
135      C toElement, boolean toInclusive);
136
137  /*@Override*/ abstract ContiguousSet<C> tailSetImpl(C fromElement, boolean inclusive);
138
139  /**
140   * Returns the set of values that are contained in both this set and the other.
141   *
142   * <p>This method should always be used instead of
143   * {@link Sets#intersection} for {@link ContiguousSet} instances.
144   */
145  public abstract ContiguousSet<C> intersection(ContiguousSet<C> other);
146
147  /**
148   * Returns a range, closed on both ends, whose endpoints are the minimum and maximum values
149   * contained in this set.  This is equivalent to {@code range(CLOSED, CLOSED)}.
150   *
151   * @throws NoSuchElementException if this set is empty
152   */
153  public abstract Range<C> range();
154
155  /**
156   * Returns the minimal range with the given boundary types for which all values in this set are
157   * {@linkplain Range#contains(Comparable) contained} within the range.
158   *
159   * <p>Note that this method will return ranges with unbounded endpoints if {@link BoundType#OPEN}
160   * is requested for a domain minimum or maximum.  For example, if {@code set} was created from the
161   * range {@code [1..Integer.MAX_VALUE]} then {@code set.range(CLOSED, OPEN)} must return
162   * {@code [1..∞)}.
163   *
164   * @throws NoSuchElementException if this set is empty
165   */
166  public abstract Range<C> range(BoundType lowerBoundType, BoundType upperBoundType);
167
168  /** Returns a short-hand representation of the contents such as {@code "[1..100]"}. */
169  @Override public String toString() {
170    return range().toString();
171  }
172
173  /**
174   * Not supported. {@code ContiguousSet} instances are constructed with {@link #create}. This
175   * method exists only to hide {@link ImmutableSet#builder} from consumers of {@code
176   * ContiguousSet}.
177   *
178   * @throws UnsupportedOperationException always
179   * @deprecated Use {@link #create}.
180   */
181  @Deprecated public static <E> ImmutableSortedSet.Builder<E> builder() {
182    throw new UnsupportedOperationException();
183  }
184}
185