1 /* 2 * Copyright (C) 2011 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 10 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 11 * express or implied. See the License for the specific language governing permissions and 12 * limitations under the License. 13 */ 14 15 package com.google.common.collect; 16 17 import com.google.common.annotations.GwtIncompatible; 18 import com.google.errorprone.annotations.DoNotMock; 19 import java.util.NoSuchElementException; 20 import java.util.Set; 21 import javax.annotation.CheckForNull; 22 23 /** 24 * A set comprising zero or more {@linkplain Range#isEmpty nonempty}, {@linkplain 25 * Range#isConnected(Range) disconnected} ranges of type {@code C}. 26 * 27 * <p>Implementations that choose to support the {@link #add(Range)} operation are required to 28 * ignore empty ranges and coalesce connected ranges. For example: 29 * 30 * <pre>{@code 31 * RangeSet<Integer> rangeSet = TreeRangeSet.create(); 32 * rangeSet.add(Range.closed(1, 10)); // {[1, 10]} 33 * rangeSet.add(Range.closedOpen(11, 15)); // disconnected range; {[1, 10], [11, 15)} 34 * rangeSet.add(Range.closedOpen(15, 20)); // connected range; {[1, 10], [11, 20)} 35 * rangeSet.add(Range.openClosed(0, 0)); // empty range; {[1, 10], [11, 20)} 36 * rangeSet.remove(Range.open(5, 10)); // splits [1, 10]; {[1, 5], [10, 10], [11, 20)} 37 * }</pre> 38 * 39 * <p>Note that the behavior of {@link Range#isEmpty()} and {@link Range#isConnected(Range)} may not 40 * be as expected on discrete ranges. See the Javadoc of those methods for details. 41 * 42 * <p>For a {@link Set} whose contents are specified by a {@link Range}, see {@link ContiguousSet}. 43 * 44 * <p>See the Guava User Guide article on <a href= 45 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#rangeset">RangeSets</a>. 46 * 47 * @author Kevin Bourrillion 48 * @author Louis Wasserman 49 * @since 14.0 50 */ 51 @SuppressWarnings("rawtypes") // https://github.com/google/guava/issues/989 52 @DoNotMock("Use ImmutableRangeSet or TreeRangeSet") 53 @GwtIncompatible 54 @ElementTypesAreNonnullByDefault 55 public interface RangeSet<C extends Comparable> { 56 // TODO(lowasser): consider adding default implementations of some of these methods 57 58 // Query methods 59 60 /** Determines whether any of this range set's member ranges contains {@code value}. */ contains(C value)61 boolean contains(C value); 62 63 /** 64 * Returns the unique range from this range set that {@linkplain Range#contains contains} {@code 65 * value}, or {@code null} if this range set does not contain {@code value}. 66 */ 67 @CheckForNull rangeContaining(C value)68 Range<C> rangeContaining(C value); 69 70 /** 71 * Returns {@code true} if there exists a non-empty range enclosed by both a member range in this 72 * range set and the specified range. This is equivalent to calling {@code 73 * subRangeSet(otherRange)} and testing whether the resulting range set is non-empty. 74 * 75 * @since 20.0 76 */ intersects(Range<C> otherRange)77 boolean intersects(Range<C> otherRange); 78 79 /** 80 * Returns {@code true} if there exists a member range in this range set which {@linkplain 81 * Range#encloses encloses} the specified range. 82 */ encloses(Range<C> otherRange)83 boolean encloses(Range<C> otherRange); 84 85 /** 86 * Returns {@code true} if for each member range in {@code other} there exists a member range in 87 * this range set which {@linkplain Range#encloses encloses} it. It follows that {@code 88 * this.contains(value)} whenever {@code other.contains(value)}. Returns {@code true} if {@code 89 * other} is empty. 90 * 91 * <p>This is equivalent to checking if this range set {@link #encloses} each of the ranges in 92 * {@code other}. 93 */ enclosesAll(RangeSet<C> other)94 boolean enclosesAll(RangeSet<C> other); 95 96 /** 97 * Returns {@code true} if for each range in {@code other} there exists a member range in this 98 * range set which {@linkplain Range#encloses encloses} it. Returns {@code true} if {@code other} 99 * is empty. 100 * 101 * <p>This is equivalent to checking if this range set {@link #encloses} each range in {@code 102 * other}. 103 * 104 * @since 21.0 105 */ enclosesAll(Iterable<Range<C>> other)106 default boolean enclosesAll(Iterable<Range<C>> other) { 107 for (Range<C> range : other) { 108 if (!encloses(range)) { 109 return false; 110 } 111 } 112 return true; 113 } 114 115 /** Returns {@code true} if this range set contains no ranges. */ isEmpty()116 boolean isEmpty(); 117 118 /** 119 * Returns the minimal range which {@linkplain Range#encloses(Range) encloses} all ranges in this 120 * range set. 121 * 122 * @throws NoSuchElementException if this range set is {@linkplain #isEmpty() empty} 123 */ span()124 Range<C> span(); 125 126 // Views 127 128 /** 129 * Returns a view of the {@linkplain Range#isConnected disconnected} ranges that make up this 130 * range set. The returned set may be empty. The iterators returned by its {@link 131 * Iterable#iterator} method return the ranges in increasing order of lower bound (equivalently, 132 * of upper bound). 133 */ asRanges()134 Set<Range<C>> asRanges(); 135 136 /** 137 * Returns a descending view of the {@linkplain Range#isConnected disconnected} ranges that make 138 * up this range set. The returned set may be empty. The iterators returned by its {@link 139 * Iterable#iterator} method return the ranges in decreasing order of lower bound (equivalently, 140 * of upper bound). 141 * 142 * @since 19.0 143 */ asDescendingSetOfRanges()144 Set<Range<C>> asDescendingSetOfRanges(); 145 146 /** 147 * Returns a view of the complement of this {@code RangeSet}. 148 * 149 * <p>The returned view supports the {@link #add} operation if this {@code RangeSet} supports 150 * {@link #remove}, and vice versa. 151 */ complement()152 RangeSet<C> complement(); 153 154 /** 155 * Returns a view of the intersection of this {@code RangeSet} with the specified range. 156 * 157 * <p>The returned view supports all optional operations supported by this {@code RangeSet}, with 158 * the caveat that an {@link IllegalArgumentException} is thrown on an attempt to {@linkplain 159 * #add(Range) add} any range not {@linkplain Range#encloses(Range) enclosed} by {@code view}. 160 */ subRangeSet(Range<C> view)161 RangeSet<C> subRangeSet(Range<C> view); 162 163 // Modification 164 165 /** 166 * Adds the specified range to this {@code RangeSet} (optional operation). That is, for equal 167 * range sets a and b, the result of {@code a.add(range)} is that {@code a} will be the minimal 168 * range set for which both {@code a.enclosesAll(b)} and {@code a.encloses(range)}. 169 * 170 * <p>Note that {@code range} will be {@linkplain Range#span(Range) coalesced} with any ranges in 171 * the range set that are {@linkplain Range#isConnected(Range) connected} with it. Moreover, if 172 * {@code range} is empty, this is a no-op. 173 * 174 * @throws UnsupportedOperationException if this range set does not support the {@code add} 175 * operation 176 */ add(Range<C> range)177 void add(Range<C> range); 178 179 /** 180 * Removes the specified range from this {@code RangeSet} (optional operation). After this 181 * operation, if {@code range.contains(c)}, {@code this.contains(c)} will return {@code false}. 182 * 183 * <p>If {@code range} is empty, this is a no-op. 184 * 185 * @throws UnsupportedOperationException if this range set does not support the {@code remove} 186 * operation 187 */ remove(Range<C> range)188 void remove(Range<C> range); 189 190 /** 191 * Removes all ranges from this {@code RangeSet} (optional operation). After this operation, 192 * {@code this.contains(c)} will return false for all {@code c}. 193 * 194 * <p>This is equivalent to {@code remove(Range.all())}. 195 * 196 * @throws UnsupportedOperationException if this range set does not support the {@code clear} 197 * operation 198 */ clear()199 void clear(); 200 201 /** 202 * Adds all of the ranges from the specified range set to this range set (optional operation). 203 * After this operation, this range set is the minimal range set that {@linkplain 204 * #enclosesAll(RangeSet) encloses} both the original range set and {@code other}. 205 * 206 * <p>This is equivalent to calling {@link #add} on each of the ranges in {@code other} in turn. 207 * 208 * @throws UnsupportedOperationException if this range set does not support the {@code addAll} 209 * operation 210 */ addAll(RangeSet<C> other)211 void addAll(RangeSet<C> other); 212 213 /** 214 * Adds all of the specified ranges to this range set (optional operation). After this operation, 215 * this range set is the minimal range set that {@linkplain #enclosesAll(RangeSet) encloses} both 216 * the original range set and each range in {@code other}. 217 * 218 * <p>This is equivalent to calling {@link #add} on each of the ranges in {@code other} in turn. 219 * 220 * @throws UnsupportedOperationException if this range set does not support the {@code addAll} 221 * operation 222 * @since 21.0 223 */ addAll(Iterable<Range<C>> ranges)224 default void addAll(Iterable<Range<C>> ranges) { 225 for (Range<C> range : ranges) { 226 add(range); 227 } 228 } 229 230 /** 231 * Removes all of the ranges from the specified range set from this range set (optional 232 * operation). After this operation, if {@code other.contains(c)}, {@code this.contains(c)} will 233 * return {@code false}. 234 * 235 * <p>This is equivalent to calling {@link #remove} on each of the ranges in {@code other} in 236 * turn. 237 * 238 * @throws UnsupportedOperationException if this range set does not support the {@code removeAll} 239 * operation 240 */ removeAll(RangeSet<C> other)241 void removeAll(RangeSet<C> other); 242 243 /** 244 * Removes all of the specified ranges from this range set (optional operation). 245 * 246 * <p>This is equivalent to calling {@link #remove} on each of the ranges in {@code other} in 247 * turn. 248 * 249 * @throws UnsupportedOperationException if this range set does not support the {@code removeAll} 250 * operation 251 * @since 21.0 252 */ removeAll(Iterable<Range<C>> ranges)253 default void removeAll(Iterable<Range<C>> ranges) { 254 for (Range<C> range : ranges) { 255 remove(range); 256 } 257 } 258 259 // Object methods 260 261 /** 262 * Returns {@code true} if {@code obj} is another {@code RangeSet} that contains the same ranges 263 * according to {@link Range#equals(Object)}. 264 */ 265 @Override equals(@heckForNull Object obj)266 boolean equals(@CheckForNull Object obj); 267 268 /** Returns {@code asRanges().hashCode()}. */ 269 @Override hashCode()270 int hashCode(); 271 272 /** 273 * Returns a readable string representation of this range set. For example, if this {@code 274 * RangeSet} consisted of {@code Range.closed(1, 3)} and {@code Range.greaterThan(4)}, this might 275 * return {@code " [1..3](4..+∞)}"}. 276 */ 277 @Override toString()278 String toString(); 279 } 280