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