13ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin/* 23ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Copyright (C) 2011 The Guava Authors 33ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 43ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 53ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * in compliance with the License. You may obtain a copy of the License at 63ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 73ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * http://www.apache.org/licenses/LICENSE-2.0 83ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 93ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Unless required by applicable law or agreed to in writing, software distributed under the 103ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 113ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * express or implied. See the License for the specific language governing permissions and 123ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * limitations under the License. 133ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 143ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 153ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinpackage com.google.common.collect; 163ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 173ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport com.google.common.annotations.Beta; 183ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 193ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport java.util.NoSuchElementException; 203ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport java.util.Set; 213ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 223ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport javax.annotation.Nullable; 233ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 243ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin/** 253ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * A set comprising zero or more {@linkplain Range#isEmpty nonempty}, 263ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@linkplain Range#isConnected(Range) disconnected} ranges of type {@code C}. 273ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 283ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>Implementations that choose to support the {@link #add(Range)} operation are required to 293ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * ignore empty ranges and coalesce connected ranges. For example: <pre> {@code 303ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 313ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * RangeSet<Integer> rangeSet = TreeRangeSet.create(); 323ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * rangeSet.add(Range.closed(1, 10)); // {[1, 10]} 333ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * rangeSet.add(Range.closedOpen(11, 15)); // disconnected range; {[1, 10], [11, 15)} 343ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * rangeSet.add(Range.closedOpen(15, 20)); // connected range; {[1, 10], [11, 20)} 353ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * rangeSet.add(Range.openClosed(0, 0)); // empty range; {[1, 10], [11, 20)} 363ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * rangeSet.remove(Range.open(5, 10)); // splits [1, 10]; {[1, 5], [10, 10], [11, 20)}}</pre> 373ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 383ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>Note that the behavior of {@link Range#isEmpty()} and {@link Range#isConnected(Range)} may 393ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * not be as expected on discrete ranges. See the Javadoc of those methods for details. 403ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 413ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>For a {@link Set} whose contents are specified by a {@link Range}, see {@link ContiguousSet}. 423ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 433ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @author Kevin Bourrillion 443ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @author Louis Wasserman 453ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @since 14.0 463ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 473ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin@Beta 483ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinpublic interface RangeSet<C extends Comparable> { 493ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 503ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin // Query methods 513ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 523ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 533ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Determines whether any of this range set's member ranges contains {@code value}. 543ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 553ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin boolean contains(C value); 563ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 573ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 583ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns the unique range from this range set that {@linkplain Range#contains contains} 593ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@code value}, or {@code null} if this range set does not contain {@code value}. 603ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 613ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Range<C> rangeContaining(C value); 623ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 633ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 643ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns {@code true} if there exists a member range in this range set which 653ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@linkplain Range#encloses encloses} the specified range. 663ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 673ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin boolean encloses(Range<C> otherRange); 683ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 693ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 703ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns {@code true} if for each member range in {@code other} there exists a member range in 713ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * this range set which {@linkplain Range#encloses encloses} it. It follows that 723ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@code this.contains(value)} whenever {@code other.contains(value)}. Returns {@code true} if 733ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@code other} is empty. 743ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 753ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>This is equivalent to checking if this range set {@link #encloses} each of the ranges in 763ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@code other}. 773ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 783ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin boolean enclosesAll(RangeSet<C> other); 793ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 803ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 813ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns {@code true} if this range set contains no ranges. 823ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 833ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin boolean isEmpty(); 843ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 853ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 863ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns the minimal range which {@linkplain Range#encloses(Range) encloses} all ranges 873ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * in this range set. 883ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 893ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @throws NoSuchElementException if this range set is {@linkplain #isEmpty() empty} 903ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 913ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Range<C> span(); 923ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 933ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin // Views 943ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 953ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 963ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns a view of the {@linkplain Range#isConnected disconnected} ranges that make up this 973ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * range set. The returned set may be empty. The iterators returned by its 983ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@link Iterable#iterator} method return the ranges in increasing order of lower bound 993ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * (equivalently, of upper bound). 1003ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1013ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Set<Range<C>> asRanges(); 1023ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1033ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1043ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns a view of the complement of this {@code RangeSet}. 1053ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1063ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>The returned view supports the {@link #add} operation if this {@code RangeSet} supports 1073ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@link #remove}, and vice versa. 1083ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1093ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin RangeSet<C> complement(); 1103ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1113ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1123ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns a view of the intersection of this {@code RangeSet} with the specified range. 1133ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1143ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>The returned view supports all optional operations supported by this {@code RangeSet}, with 1153ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * the caveat that an {@link IllegalArgumentException} is thrown on an attempt to 1163ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@linkplain #add(Range) add} any range not {@linkplain Range#encloses(Range) enclosed} by 1173ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@code view}. 1183ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1193ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin RangeSet<C> subRangeSet(Range<C> view); 1203ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1213ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin // Modification 1223ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1233ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1243ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Adds the specified range to this {@code RangeSet} (optional operation). That is, for equal 1253ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * range sets a and b, the result of {@code a.add(range)} is that {@code a} will be the minimal 1263ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * range set for which both {@code a.enclosesAll(b)} and {@code a.encloses(range)}. 1273ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1283ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>Note that {@code range} will be {@linkplain Range#span(Range) coalesced} with any ranges in 1293ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * the range set that are {@linkplain Range#isConnected(Range) connected} with it. Moreover, 1303ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * if {@code range} is empty, this is a no-op. 1313ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1323ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @throws UnsupportedOperationException if this range set does not support the {@code add} 1333ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * operation 1343ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1353ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin void add(Range<C> range); 1363ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1373ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1383ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Removes the specified range from this {@code RangeSet} (optional operation). After this 1393ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * operation, if {@code range.contains(c)}, {@code this.contains(c)} will return {@code false}. 1403ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1413ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>If {@code range} is empty, this is a no-op. 1423ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1433ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @throws UnsupportedOperationException if this range set does not support the {@code remove} 1443ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * operation 1453ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1463ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin void remove(Range<C> range); 1473ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1483ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1493ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Removes all ranges from this {@code RangeSet} (optional operation). After this operation, 1503ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@code this.contains(c)} will return false for all {@code c}. 1513ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1523ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>This is equivalent to {@code remove(Range.all())}. 1533ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1543ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @throws UnsupportedOperationException if this range set does not support the {@code clear} 1553ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * operation 1563ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1573ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin void clear(); 1583ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1593ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1603ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Adds all of the ranges from the specified range set to this range set (optional operation). 1613ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * After this operation, this range set is the minimal range set that 1623ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@linkplain #enclosesAll(RangeSet) encloses} both the original range set and {@code other}. 1633ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1643ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>This is equivalent to calling {@link #add} on each of the ranges in {@code other} in turn. 1653ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1663ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @throws UnsupportedOperationException if this range set does not support the {@code addAll} 1673ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * operation 1683ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1693ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin void addAll(RangeSet<C> other); 1703ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1713ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1723ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Removes all of the ranges from the specified range set from this range set (optional 1733ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * operation). After this operation, if {@code other.contains(c)}, {@code this.contains(c)} will 1743ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * return {@code false}. 1753ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1763ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>This is equivalent to calling {@link #remove} on each of the ranges in {@code other} in 1773ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * turn. 1783ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1793ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @throws UnsupportedOperationException if this range set does not support the {@code removeAll} 1803ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * operation 1813ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1823ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin void removeAll(RangeSet<C> other); 1833ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1843ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin // Object methods 1853ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1863ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1873ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns {@code true} if {@code obj} is another {@code RangeSet} that contains the same ranges 1883ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * according to {@link Range#equals(Object)}. 1893ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1903ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1913ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin boolean equals(@Nullable Object obj); 1923ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1933ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1943ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns {@code asRanges().hashCode()}. 1953ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1963ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1973ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin int hashCode(); 1983ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1993ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 2003ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns a readable string representation of this range set. For example, if this 2013ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * {@code RangeSet} consisted of {@code Range.closed(1, 3)} and {@code Range.greaterThan(4)}, 2023ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * this might return {@code " [1‥3](4‥+∞)}"}. 2033ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 2043ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 2053ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin String toString(); 2063ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin} 207