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