/*
 * 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 DiscreteDomain. Example: 

ContiguousSet.create(Range.closed(5, 42), DiscreteDomain.integers())

Note that because bounded ranges over int and long values are so common, this particular example can be written as just: 

ContiguousSet.closed(5, 42)

Warning: Be extremely careful what you do with conceptually large instances (such as ContiguousSet.create(Range.greaterThan(0), DiscreteDomain.integers()). Certain operations on such a set can be performed efficiently, but others (such as Set.hashCode or Collections.frequency) can cause major performance problems. 
Author:
Gregory Kick
Since:
10.0/**
 * A sorted set of contiguous values in a given {@link DiscreteDomain}. Example:
 *
 * <pre>{@code
 * ContiguousSet.create(Range.closed(5, 42), DiscreteDomain.integers())
 * }</pre>
 *
 * <p>Note that because bounded ranges over {@code int} and {@code long} values are so common, this
 * particular example can be written as just:
 *
 * <pre>{@code
 * ContiguousSet.closed(5, 42)
 * }</pre>
 *
 * <p><b>Warning:</b> Be extremely careful what you do with conceptually large instances (such as
 * {@code ContiguousSet.create(Range.greaterThan(0), DiscreteDomain.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
 */
@GwtCompatible(emulated = true)
@SuppressWarnings("rawtypes") // allow ungenerified Comparable types
public abstract class ContiguousSet<C extends Comparable> extends ImmutableSortedSet<C> {
  
Returns a ContiguousSet containing the same values in the given domain 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/**
   * 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(Range.atLeast(domain.minValue()));
      }
      if (!range.hasUpperBound()) {
        effectiveRange = effectiveRange.intersection(Range.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);
  }

  
Returns a nonempty contiguous set containing all int values from lower (inclusive) to upper (inclusive). (These are the same values contained in 
Range.closed(lower, upper).) 
Throws:
IllegalArgumentException – if lower is greater than upper
Since:
23.0/**
   * Returns a nonempty contiguous set containing all {@code int} values from {@code lower}
   * (inclusive) to {@code upper} (inclusive). (These are the same values contained in {@code
   * Range.closed(lower, upper)}.)
   *
   * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
   * @since 23.0
   */
  @Beta
  public static ContiguousSet<Integer> closed(int lower, int upper) {
    return create(Range.closed(lower, upper), DiscreteDomain.integers());
  }

  
Returns a nonempty contiguous set containing all long values from lower (inclusive) to upper (inclusive). (These are the same values contained in 
Range.closed(lower, upper).) 
Throws:
IllegalArgumentException – if lower is greater than upper
Since:
23.0/**
   * Returns a nonempty contiguous set containing all {@code long} values from {@code lower}
   * (inclusive) to {@code upper} (inclusive). (These are the same values contained in {@code
   * Range.closed(lower, upper)}.)
   *
   * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
   * @since 23.0
   */
  @Beta
  public static ContiguousSet<Long> closed(long lower, long upper) {
    return create(Range.closed(lower, upper), DiscreteDomain.longs());
  }

  
Returns a contiguous set containing all int values from lower (inclusive) to upper (exclusive). If the endpoints are equal, an empty set is returned. (These are the same values contained in Range.closedOpen(lower, upper).) 
Throws:
IllegalArgumentException – if lower is greater than upper
Since:
23.0/**
   * Returns a contiguous set containing all {@code int} values from {@code lower} (inclusive) to
   * {@code upper} (exclusive). If the endpoints are equal, an empty set is returned. (These are the
   * same values contained in {@code Range.closedOpen(lower, upper)}.)
   *
   * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
   * @since 23.0
   */
  @Beta
  public static ContiguousSet<Integer> closedOpen(int lower, int upper) {
    return create(Range.closedOpen(lower, upper), DiscreteDomain.integers());
  }

  
Returns a contiguous set containing all long values from lower (inclusive) to upper (exclusive). If the endpoints are equal, an empty set is returned. (These are the same values contained in Range.closedOpen(lower, upper).) 
Throws:
IllegalArgumentException – if lower is greater than upper
Since:
23.0/**
   * Returns a contiguous set containing all {@code long} values from {@code lower} (inclusive) to
   * {@code upper} (exclusive). If the endpoints are equal, an empty set is returned. (These are the
   * same values contained in {@code Range.closedOpen(lower, upper)}.)
   *
   * @throws IllegalArgumentException if {@code lower} is greater than {@code upper}
   * @since 23.0
   */
  @Beta
  public static ContiguousSet<Long> closedOpen(long lower, long upper) {
    return create(Range.closedOpen(lower, upper), DiscreteDomain.longs());
  }

  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/** @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/** @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/** @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.
   */
  // TODO(kevinb): we can probably make these real @Overrides now
  /* @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.
This method should always be used instead of Sets.intersection for ContiguousSet instances. /**
   * 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 range(CLOSED, CLOSED). 
Throws:
NoSuchElementException – if this set is empty/**
   * 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 contained within the range. 
Note that this method will return ranges with unbounded endpoints if BoundType.OPEN is requested for a domain minimum or maximum. For example, if set was created from the range [1..Integer.MAX_VALUE] then set.range(CLOSED, OPEN) must return 
[1..∞). 
Throws:
NoSuchElementException – if this set is empty/**
   * 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);

  @Override
  @GwtIncompatible // NavigableSet
  ImmutableSortedSet<C> createDescendingSet() {
    return new DescendingImmutableSortedSet<C>(this);
  }

  
Returns a short-hand representation of the contents such as "[1..100]". /** Returns a short-hand representation of the contents such as {@code "[1..100]"}. */
  @Override
  public String toString() {
    return range().toString();
  }

  
Not supported. ContiguousSet instances are constructed with create. This method exists only to hide ImmutableSet.builder from consumers of 
ContiguousSet. 
Throws:
UnsupportedOperationException – always
Deprecated:
Use create./**
   * Not supported. {@code ContiguousSet} instances are constructed with {@link #create}. This
   * method exists only to hide {@link ImmutableSet#builder} from consumers of {@code
   * ContiguousSet}.
   *
   * @throws UnsupportedOperationException always
   * @deprecated Use {@link #create}.
   */
  @Deprecated
  public static <E> ImmutableSortedSet.Builder<E> builder() {
    throw new UnsupportedOperationException();
  }
}