1 files changed, 172 insertions, 0 deletions
diff --git a/guava/src/com/google/common/collect/ContiguousSet.java b/guava/src/com/google/common/collect/ContiguousSet.java
new file mode 100644
index 0000000..11be93e
--- /dev/null
+++ b/guava/src/com/google/common/collect/ContiguousSet.java
@@ -0,0 +1,172 @@
+/*
+ * Copyright (C) 2010 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+ * in compliance with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software distributed under the License
+ * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing permissions and limitations under
+ * the License.
+ */
+
+package com.google.common.collect;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkNotNull;
+
+import com.google.common.annotations.Beta;
+import com.google.common.annotations.GwtCompatible;
+import com.google.common.annotations.GwtIncompatible;
+
+import java.util.Collections;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * A sorted set of contiguous values in a given {@link DiscreteDomain}.
+ *
+ * <p><b>Warning:</b> Be extremely careful what you do with conceptually large instances (such as
+ * {@code ContiguousSet.create(Ranges.greaterThan(0), DiscreteDomains.integers()}). Certain
+ * operations on such a set can be performed efficiently, but others (such as {@link Set#hashCode}
+ * or {@link Collections#frequency}) can cause major performance problems.
+ *
+ * @author Gregory Kick
+ * @since 10.0
+ */
+@Beta
+@GwtCompatible(emulated = true)
+@SuppressWarnings("rawtypes") // allow ungenerified Comparable types
+public abstract class ContiguousSet<C extends Comparable> extends ImmutableSortedSet<C> {
+  /**
+   * Returns a {@code ContiguousSet} containing the same values in the given domain
+   * {@linkplain Range#contains contained} by the range.
+   *
+   * @throws IllegalArgumentException if neither range nor the domain has a lower bound, or if
+   *     neither has an upper bound
+   *
+   * @since 13.0
+   */
+  public static <C extends Comparable> ContiguousSet<C> create(
+      Range<C> range, DiscreteDomain<C> domain) {
+    checkNotNull(range);
+    checkNotNull(domain);
+    Range<C> effectiveRange = range;
+    try {
+      if (!range.hasLowerBound()) {
+        effectiveRange = effectiveRange.intersection(Ranges.atLeast(domain.minValue()));
+      }
+      if (!range.hasUpperBound()) {
+        effectiveRange = effectiveRange.intersection(Ranges.atMost(domain.maxValue()));
+      }
+    } catch (NoSuchElementException e) {
+      throw new IllegalArgumentException(e);
+    }
+
+    // Per class spec, we are allowed to throw CCE if necessary
+    boolean empty = effectiveRange.isEmpty()
+        || Range.compareOrThrow(
+            range.lowerBound.leastValueAbove(domain),
+            range.upperBound.greatestValueBelow(domain)) > 0;
+
+    return empty
+        ? new EmptyContiguousSet<C>(domain)
+        : new RegularContiguousSet<C>(effectiveRange, domain);
+  }
+
+  final DiscreteDomain<C> domain;
+
+  ContiguousSet(DiscreteDomain<C> domain) {
+    super(Ordering.natural());
+    this.domain = domain;
+  }
+
+  @Override public ContiguousSet<C> headSet(C toElement) {
+    return headSetImpl(checkNotNull(toElement), false);
+  }
+
+  /**
+   * @since 12.0
+   */
+  @GwtIncompatible("NavigableSet")
+  @Override public ContiguousSet<C> headSet(C toElement, boolean inclusive) {
+    return headSetImpl(checkNotNull(toElement), inclusive);
+  }
+
+  @Override public ContiguousSet<C> subSet(C fromElement, C toElement) {
+    checkNotNull(fromElement);
+    checkNotNull(toElement);
+    checkArgument(comparator().compare(fromElement, toElement) <= 0);
+    return subSetImpl(fromElement, true, toElement, false);
+  }
+
+  /**
+   * @since 12.0
+   */
+  @GwtIncompatible("NavigableSet")
+  @Override public ContiguousSet<C> subSet(C fromElement, boolean fromInclusive, C toElement,
+      boolean toInclusive) {
+    checkNotNull(fromElement);
+    checkNotNull(toElement);
+    checkArgument(comparator().compare(fromElement, toElement) <= 0);
+    return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
+  }
+
+  @Override public ContiguousSet<C> tailSet(C fromElement) {
+    return tailSetImpl(checkNotNull(fromElement), true);
+  }
+
+  /**
+   * @since 12.0
+   */
+  @GwtIncompatible("NavigableSet")
+  @Override public ContiguousSet<C> tailSet(C fromElement, boolean inclusive) {
+    return tailSetImpl(checkNotNull(fromElement), inclusive);
+  }
+
+  /*
+   * These methods perform most headSet, subSet, and tailSet logic, besides parameter validation.
+   */
+  /*@Override*/ abstract ContiguousSet<C> headSetImpl(C toElement, boolean inclusive);
+
+  /*@Override*/ abstract ContiguousSet<C> subSetImpl(C fromElement, boolean fromInclusive,
+      C toElement, boolean toInclusive);
+
+  /*@Override*/ abstract ContiguousSet<C> tailSetImpl(C fromElement, boolean inclusive);
+
+  /**
+   * Returns the set of values that are contained in both this set and the other.
+   *
+   * <p>This method should always be used instead of
+   * {@link Sets#intersection} for {@link ContiguousSet} instances.
+   */
+  public abstract ContiguousSet<C> intersection(ContiguousSet<C> other);
+
+  /**
+   * Returns a range, closed on both ends, whose endpoints are the minimum and maximum values
+   * contained in this set.  This is equivalent to {@code range(CLOSED, CLOSED)}.
+   *
+   * @throws NoSuchElementException if this set is empty
+   */
+  public abstract Range<C> range();
+
+  /**
+   * Returns the minimal range with the given boundary types for which all values in this set are
+   * {@linkplain Range#contains(Comparable) contained} within the range.
+   *
+   * <p>Note that this method will return ranges with unbounded endpoints if {@link BoundType#OPEN}
+   * is requested for a domain minimum or maximum.  For example, if {@code set} was created from the
+   * range {@code [1..Integer.MAX_VALUE]} then {@code set.range(CLOSED, OPEN)} must return
+   * {@code [1..∞)}.
+   *
+   * @throws NoSuchElementException if this set is empty
+   */
+  public abstract Range<C> range(BoundType lowerBoundType, BoundType upperBoundType);
+
+  /** Returns a short-hand representation of the contents such as {@code "[1..100]"}. */
+  @Override public String toString() {
+    return range().toString();
+  }
+}