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