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; 019import static java.util.Objects.requireNonNull; 020 021import com.google.common.annotations.GwtCompatible; 022import com.google.common.annotations.GwtIncompatible; 023import com.google.errorprone.annotations.DoNotCall; 024import java.util.Collections; 025import java.util.NoSuchElementException; 026import java.util.Set; 027 028/** 029 * A sorted set of contiguous values in a given {@link DiscreteDomain}. Example: 030 * 031 * <pre>{@code 032 * ContiguousSet.create(Range.closed(5, 42), DiscreteDomain.integers()) 033 * }</pre> 034 * 035 * <p>Note that because bounded ranges over {@code int} and {@code long} values are so common, this 036 * particular example can be written as just: 037 * 038 * <pre>{@code 039 * ContiguousSet.closed(5, 42) 040 * }</pre> 041 * 042 * <p><b>Warning:</b> Be extremely careful what you do with conceptually large instances (such as 043 * {@code ContiguousSet.create(Range.greaterThan(0), DiscreteDomain.integers()}). Certain operations 044 * on such a set can be performed efficiently, but others (such as {@link Set#hashCode} or {@link 045 * Collections#frequency}) can cause major performance problems. 046 * 047 * @author Gregory Kick 048 * @since 10.0 049 */ 050@GwtCompatible(emulated = true) 051@SuppressWarnings("rawtypes") // allow ungenerified Comparable types 052@ElementTypesAreNonnullByDefault 053public abstract class ContiguousSet<C extends Comparable> extends ImmutableSortedSet<C> { 054 /** 055 * Returns a {@code ContiguousSet} containing the same values in the given domain {@linkplain 056 * Range#contains contained} by the range. 057 * 058 * @throws IllegalArgumentException if neither range nor the domain has a lower bound, or if 059 * neither has an upper bound 060 * @since 13.0 061 */ 062 public static <C extends Comparable> ContiguousSet<C> create( 063 Range<C> range, DiscreteDomain<C> domain) { 064 checkNotNull(range); 065 checkNotNull(domain); 066 Range<C> effectiveRange = range; 067 try { 068 if (!range.hasLowerBound()) { 069 effectiveRange = effectiveRange.intersection(Range.atLeast(domain.minValue())); 070 } 071 if (!range.hasUpperBound()) { 072 effectiveRange = effectiveRange.intersection(Range.atMost(domain.maxValue())); 073 } 074 } catch (NoSuchElementException e) { 075 throw new IllegalArgumentException(e); 076 } 077 078 boolean empty; 079 if (effectiveRange.isEmpty()) { 080 empty = true; 081 } else { 082 /* 083 * requireNonNull is safe because the effectiveRange operations above would have thrown or 084 * effectiveRange.isEmpty() would have returned true. 085 */ 086 C afterLower = requireNonNull(range.lowerBound.leastValueAbove(domain)); 087 C beforeUpper = requireNonNull(range.upperBound.greatestValueBelow(domain)); 088 // Per class spec, we are allowed to throw CCE if necessary 089 empty = Range.compareOrThrow(afterLower, beforeUpper) > 0; 090 } 091 092 return empty 093 ? new EmptyContiguousSet<C>(domain) 094 : new RegularContiguousSet<C>(effectiveRange, domain); 095 } 096 097 /** 098 * Returns a nonempty contiguous set containing all {@code int} values from {@code lower} 099 * (inclusive) to {@code upper} (inclusive). (These are the same values contained in {@code 100 * Range.closed(lower, upper)}.) 101 * 102 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper} 103 * @since 23.0 104 */ 105 public static ContiguousSet<Integer> closed(int lower, int upper) { 106 return create(Range.closed(lower, upper), DiscreteDomain.integers()); 107 } 108 109 /** 110 * Returns a nonempty contiguous set containing all {@code long} values from {@code lower} 111 * (inclusive) to {@code upper} (inclusive). (These are the same values contained in {@code 112 * Range.closed(lower, upper)}.) 113 * 114 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper} 115 * @since 23.0 116 */ 117 public static ContiguousSet<Long> closed(long lower, long upper) { 118 return create(Range.closed(lower, upper), DiscreteDomain.longs()); 119 } 120 121 /** 122 * Returns a contiguous set containing all {@code int} values from {@code lower} (inclusive) to 123 * {@code upper} (exclusive). If the endpoints are equal, an empty set is returned. (These are the 124 * same values contained in {@code Range.closedOpen(lower, upper)}.) 125 * 126 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper} 127 * @since 23.0 128 */ 129 public static ContiguousSet<Integer> closedOpen(int lower, int upper) { 130 return create(Range.closedOpen(lower, upper), DiscreteDomain.integers()); 131 } 132 133 /** 134 * Returns a contiguous set containing all {@code long} values from {@code lower} (inclusive) to 135 * {@code upper} (exclusive). If the endpoints are equal, an empty set is returned. (These are the 136 * same values contained in {@code Range.closedOpen(lower, upper)}.) 137 * 138 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper} 139 * @since 23.0 140 */ 141 public static ContiguousSet<Long> closedOpen(long lower, long upper) { 142 return create(Range.closedOpen(lower, upper), DiscreteDomain.longs()); 143 } 144 145 final DiscreteDomain<C> domain; 146 147 ContiguousSet(DiscreteDomain<C> domain) { 148 super(Ordering.natural()); 149 this.domain = domain; 150 } 151 152 @Override 153 public ContiguousSet<C> headSet(C toElement) { 154 return headSetImpl(checkNotNull(toElement), false); 155 } 156 157 /** @since 12.0 */ 158 @GwtIncompatible // NavigableSet 159 @Override 160 public ContiguousSet<C> headSet(C toElement, boolean inclusive) { 161 return headSetImpl(checkNotNull(toElement), inclusive); 162 } 163 164 @Override 165 public ContiguousSet<C> subSet(C fromElement, C toElement) { 166 checkNotNull(fromElement); 167 checkNotNull(toElement); 168 checkArgument(comparator().compare(fromElement, toElement) <= 0); 169 return subSetImpl(fromElement, true, toElement, false); 170 } 171 172 /** @since 12.0 */ 173 @GwtIncompatible // NavigableSet 174 @Override 175 public ContiguousSet<C> subSet( 176 C fromElement, boolean fromInclusive, C toElement, boolean toInclusive) { 177 checkNotNull(fromElement); 178 checkNotNull(toElement); 179 checkArgument(comparator().compare(fromElement, toElement) <= 0); 180 return subSetImpl(fromElement, fromInclusive, toElement, toInclusive); 181 } 182 183 @Override 184 public ContiguousSet<C> tailSet(C fromElement) { 185 return tailSetImpl(checkNotNull(fromElement), true); 186 } 187 188 /** @since 12.0 */ 189 @GwtIncompatible // NavigableSet 190 @Override 191 public ContiguousSet<C> tailSet(C fromElement, boolean inclusive) { 192 return tailSetImpl(checkNotNull(fromElement), inclusive); 193 } 194 195 /* 196 * These methods perform most headSet, subSet, and tailSet logic, besides parameter validation. 197 */ 198 @SuppressWarnings("MissingOverride") // Supermethod does not exist under GWT. 199 abstract ContiguousSet<C> headSetImpl(C toElement, boolean inclusive); 200 201 @SuppressWarnings("MissingOverride") // Supermethod does not exist under GWT. 202 abstract ContiguousSet<C> subSetImpl( 203 C fromElement, boolean fromInclusive, C toElement, boolean toInclusive); 204 205 @SuppressWarnings("MissingOverride") // Supermethod does not exist under GWT. 206 abstract ContiguousSet<C> tailSetImpl(C fromElement, boolean inclusive); 207 208 /** 209 * Returns the set of values that are contained in both this set and the other. 210 * 211 * <p>This method should always be used instead of {@link Sets#intersection} for {@link 212 * ContiguousSet} instances. 213 */ 214 public abstract ContiguousSet<C> intersection(ContiguousSet<C> other); 215 216 /** 217 * Returns a range, closed on both ends, whose endpoints are the minimum and maximum values 218 * contained in this set. This is equivalent to {@code range(CLOSED, CLOSED)}. 219 * 220 * @throws NoSuchElementException if this set is empty 221 */ 222 public abstract Range<C> range(); 223 224 /** 225 * Returns the minimal range with the given boundary types for which all values in this set are 226 * {@linkplain Range#contains(Comparable) contained} within the range. 227 * 228 * <p>Note that this method will return ranges with unbounded endpoints if {@link BoundType#OPEN} 229 * is requested for a domain minimum or maximum. For example, if {@code set} was created from the 230 * range {@code [1..Integer.MAX_VALUE]} then {@code set.range(CLOSED, OPEN)} must return {@code 231 * [1..∞)}. 232 * 233 * @throws NoSuchElementException if this set is empty 234 */ 235 public abstract Range<C> range(BoundType lowerBoundType, BoundType upperBoundType); 236 237 @Override 238 @GwtIncompatible // NavigableSet 239 ImmutableSortedSet<C> createDescendingSet() { 240 return new DescendingImmutableSortedSet<>(this); 241 } 242 243 /** Returns a shorthand representation of the contents such as {@code "[1..100]"}. */ 244 @Override 245 public String toString() { 246 return range().toString(); 247 } 248 249 /** 250 * Not supported. {@code ContiguousSet} instances are constructed with {@link #create}. This 251 * method exists only to hide {@link ImmutableSet#builder} from consumers of {@code 252 * ContiguousSet}. 253 * 254 * @throws UnsupportedOperationException always 255 * @deprecated Use {@link #create}. 256 */ 257 @Deprecated 258 @DoNotCall("Always throws UnsupportedOperationException") 259 public static <E> ImmutableSortedSet.Builder<E> builder() { 260 throw new UnsupportedOperationException(); 261 } 262}