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.Beta; 022import com.google.common.annotations.GwtCompatible; 023import com.google.common.annotations.GwtIncompatible; 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 @Beta 107 public static ContiguousSet<Integer> closed(int lower, int upper) { 108 return create(Range.closed(lower, upper), DiscreteDomain.integers()); 109 } 110 111 /** 112 * Returns a nonempty contiguous set containing all {@code long} values from {@code lower} 113 * (inclusive) to {@code upper} (inclusive). (These are the same values contained in {@code 114 * Range.closed(lower, upper)}.) 115 * 116 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper} 117 * @since 23.0 118 */ 119 @Beta 120 public static ContiguousSet<Long> closed(long lower, long upper) { 121 return create(Range.closed(lower, upper), DiscreteDomain.longs()); 122 } 123 124 /** 125 * Returns a contiguous set containing all {@code int} values from {@code lower} (inclusive) to 126 * {@code upper} (exclusive). If the endpoints are equal, an empty set is returned. (These are the 127 * same values contained in {@code Range.closedOpen(lower, upper)}.) 128 * 129 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper} 130 * @since 23.0 131 */ 132 @Beta 133 public static ContiguousSet<Integer> closedOpen(int lower, int upper) { 134 return create(Range.closedOpen(lower, upper), DiscreteDomain.integers()); 135 } 136 137 /** 138 * Returns a contiguous set containing all {@code long} values from {@code lower} (inclusive) to 139 * {@code upper} (exclusive). If the endpoints are equal, an empty set is returned. (These are the 140 * same values contained in {@code Range.closedOpen(lower, upper)}.) 141 * 142 * @throws IllegalArgumentException if {@code lower} is greater than {@code upper} 143 * @since 23.0 144 */ 145 @Beta 146 public static ContiguousSet<Long> closedOpen(long lower, long upper) { 147 return create(Range.closedOpen(lower, upper), DiscreteDomain.longs()); 148 } 149 150 final DiscreteDomain<C> domain; 151 152 ContiguousSet(DiscreteDomain<C> domain) { 153 super(Ordering.natural()); 154 this.domain = domain; 155 } 156 157 @Override 158 public ContiguousSet<C> headSet(C toElement) { 159 return headSetImpl(checkNotNull(toElement), false); 160 } 161 162 /** @since 12.0 */ 163 @GwtIncompatible // NavigableSet 164 @Override 165 public ContiguousSet<C> headSet(C toElement, boolean inclusive) { 166 return headSetImpl(checkNotNull(toElement), inclusive); 167 } 168 169 @Override 170 public ContiguousSet<C> subSet(C fromElement, C toElement) { 171 checkNotNull(fromElement); 172 checkNotNull(toElement); 173 checkArgument(comparator().compare(fromElement, toElement) <= 0); 174 return subSetImpl(fromElement, true, toElement, false); 175 } 176 177 /** @since 12.0 */ 178 @GwtIncompatible // NavigableSet 179 @Override 180 public ContiguousSet<C> subSet( 181 C fromElement, boolean fromInclusive, C toElement, boolean toInclusive) { 182 checkNotNull(fromElement); 183 checkNotNull(toElement); 184 checkArgument(comparator().compare(fromElement, toElement) <= 0); 185 return subSetImpl(fromElement, fromInclusive, toElement, toInclusive); 186 } 187 188 @Override 189 public ContiguousSet<C> tailSet(C fromElement) { 190 return tailSetImpl(checkNotNull(fromElement), true); 191 } 192 193 /** @since 12.0 */ 194 @GwtIncompatible // NavigableSet 195 @Override 196 public ContiguousSet<C> tailSet(C fromElement, boolean inclusive) { 197 return tailSetImpl(checkNotNull(fromElement), inclusive); 198 } 199 200 /* 201 * These methods perform most headSet, subSet, and tailSet logic, besides parameter validation. 202 */ 203 @SuppressWarnings("MissingOverride") // Supermethod does not exist under GWT. 204 abstract ContiguousSet<C> headSetImpl(C toElement, boolean inclusive); 205 206 @SuppressWarnings("MissingOverride") // Supermethod does not exist under GWT. 207 abstract ContiguousSet<C> subSetImpl( 208 C fromElement, boolean fromInclusive, C toElement, boolean toInclusive); 209 210 @SuppressWarnings("MissingOverride") // Supermethod does not exist under GWT. 211 abstract ContiguousSet<C> tailSetImpl(C fromElement, boolean inclusive); 212 213 /** 214 * Returns the set of values that are contained in both this set and the other. 215 * 216 * <p>This method should always be used instead of {@link Sets#intersection} for {@link 217 * ContiguousSet} instances. 218 */ 219 public abstract ContiguousSet<C> intersection(ContiguousSet<C> other); 220 221 /** 222 * Returns a range, closed on both ends, whose endpoints are the minimum and maximum values 223 * contained in this set. This is equivalent to {@code range(CLOSED, CLOSED)}. 224 * 225 * @throws NoSuchElementException if this set is empty 226 */ 227 public abstract Range<C> range(); 228 229 /** 230 * Returns the minimal range with the given boundary types for which all values in this set are 231 * {@linkplain Range#contains(Comparable) contained} within the range. 232 * 233 * <p>Note that this method will return ranges with unbounded endpoints if {@link BoundType#OPEN} 234 * is requested for a domain minimum or maximum. For example, if {@code set} was created from the 235 * range {@code [1..Integer.MAX_VALUE]} then {@code set.range(CLOSED, OPEN)} must return {@code 236 * [1..∞)}. 237 * 238 * @throws NoSuchElementException if this set is empty 239 */ 240 public abstract Range<C> range(BoundType lowerBoundType, BoundType upperBoundType); 241 242 @Override 243 @GwtIncompatible // NavigableSet 244 ImmutableSortedSet<C> createDescendingSet() { 245 return new DescendingImmutableSortedSet<>(this); 246 } 247 248 /** Returns a short-hand representation of the contents such as {@code "[1..100]"}. */ 249 @Override 250 public String toString() { 251 return range().toString(); 252 } 253 254 /** 255 * Not supported. {@code ContiguousSet} instances are constructed with {@link #create}. This 256 * method exists only to hide {@link ImmutableSet#builder} from consumers of {@code 257 * ContiguousSet}. 258 * 259 * @throws UnsupportedOperationException always 260 * @deprecated Use {@link #create}. 261 */ 262 @Deprecated 263 @DoNotCall("Always throws UnsupportedOperationException") 264 public static <E> ImmutableSortedSet.Builder<E> builder() { 265 throw new UnsupportedOperationException(); 266 } 267}