/*
 * Copyright (C) 2011 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.GwtIncompatible;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.MoreObjects;
import java.io.Serializable;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.NavigableMap;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.TreeMap;
import org.checkerframework.checker.nullness.qual.MonotonicNonNull;
import org.checkerframework.checker.nullness.qual.Nullable;

An implementation of RangeSet backed by a TreeMap. 
Author:
Louis Wasserman
Since:
14.0/**
 * An implementation of {@link RangeSet} backed by a {@link TreeMap}.
 *
 * @author Louis Wasserman
 * @since 14.0
 */
@Beta
@GwtIncompatible // uses NavigableMap
public class TreeRangeSet<C extends Comparable<?>> extends AbstractRangeSet<C>
    implements Serializable {

  @VisibleForTesting final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;

  
Creates an empty TreeRangeSet instance. /** Creates an empty {@code TreeRangeSet} instance. */
  public static <C extends Comparable<?>> TreeRangeSet<C> create() {
    return new TreeRangeSet<C>(new TreeMap<Cut<C>, Range<C>>());
  }

  
Returns a TreeRangeSet initialized with the ranges in the specified range set. /** Returns a {@code TreeRangeSet} initialized with the ranges in the specified range set. */
  public static <C extends Comparable<?>> TreeRangeSet<C> create(RangeSet<C> rangeSet) {
    TreeRangeSet<C> result = create();
    result.addAll(rangeSet);
    return result;
  }

  
Returns a TreeRangeSet representing the union of the specified ranges. 
This is the smallest RangeSet which encloses each of the specified ranges. An element will be contained in this RangeSet if and only if it is contained in at least one Range in ranges. 
Since:
21.0/**
   * Returns a {@code TreeRangeSet} representing the union of the specified ranges.
   *
   * <p>This is the smallest {@code RangeSet} which encloses each of the specified ranges. An
   * element will be contained in this {@code RangeSet} if and only if it is contained in at least
   * one {@code Range} in {@code ranges}.
   *
   * @since 21.0
   */
  public static <C extends Comparable<?>> TreeRangeSet<C> create(Iterable<Range<C>> ranges) {
    TreeRangeSet<C> result = create();
    result.addAll(ranges);
    return result;
  }

  private TreeRangeSet(NavigableMap<Cut<C>, Range<C>> rangesByLowerCut) {
    this.rangesByLowerBound = rangesByLowerCut;
  }

  private transient @MonotonicNonNull Set<Range<C>> asRanges;
  private transient @MonotonicNonNull Set<Range<C>> asDescendingSetOfRanges;

  @Override
  public Set<Range<C>> asRanges() {
    Set<Range<C>> result = asRanges;
    return (result == null) ? asRanges = new AsRanges(rangesByLowerBound.values()) : result;
  }

  @Override
  public Set<Range<C>> asDescendingSetOfRanges() {
    Set<Range<C>> result = asDescendingSetOfRanges;
    return (result == null)
        ? asDescendingSetOfRanges = new AsRanges(rangesByLowerBound.descendingMap().values())
        : result;
  }

  final class AsRanges extends ForwardingCollection<Range<C>> implements Set<Range<C>> {

    final Collection<Range<C>> delegate;

    AsRanges(Collection<Range<C>> delegate) {
      this.delegate = delegate;
    }

    @Override
    protected Collection<Range<C>> delegate() {
      return delegate;
    }

    @Override
    public int hashCode() {
      return Sets.hashCodeImpl(this);
    }

    @Override
    public boolean equals(@Nullable Object o) {
      return Sets.equalsImpl(this, o);
    }
  }

  @Override
  public @Nullable Range<C> rangeContaining(C value) {
    checkNotNull(value);
    Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(Cut.belowValue(value));
    if (floorEntry != null && floorEntry.getValue().contains(value)) {
      return floorEntry.getValue();
    } else {
      // TODO(kevinb): revisit this design choice
      return null;
    }
  }

  @Override
  public boolean intersects(Range<C> range) {
    checkNotNull(range);
    Entry<Cut<C>, Range<C>> ceilingEntry = rangesByLowerBound.ceilingEntry(range.lowerBound);
    if (ceilingEntry != null
        && ceilingEntry.getValue().isConnected(range)
        && !ceilingEntry.getValue().intersection(range).isEmpty()) {
      return true;
    }
    Entry<Cut<C>, Range<C>> priorEntry = rangesByLowerBound.lowerEntry(range.lowerBound);
    return priorEntry != null
        && priorEntry.getValue().isConnected(range)
        && !priorEntry.getValue().intersection(range).isEmpty();
  }

  @Override
  public boolean encloses(Range<C> range) {
    checkNotNull(range);
    Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound);
    return floorEntry != null && floorEntry.getValue().encloses(range);
  }

  private @Nullable Range<C> rangeEnclosing(Range<C> range) {
    checkNotNull(range);
    Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound);
    return (floorEntry != null && floorEntry.getValue().encloses(range))
        ? floorEntry.getValue()
        : null;
  }

  @Override
  public Range<C> span() {
    Entry<Cut<C>, Range<C>> firstEntry = rangesByLowerBound.firstEntry();
    Entry<Cut<C>, Range<C>> lastEntry = rangesByLowerBound.lastEntry();
    if (firstEntry == null) {
      throw new NoSuchElementException();
    }
    return Range.create(firstEntry.getValue().lowerBound, lastEntry.getValue().upperBound);
  }

  @Override
  public void add(Range<C> rangeToAdd) {
    checkNotNull(rangeToAdd);

    if (rangeToAdd.isEmpty()) {
      return;
    }

    // We will use { } to illustrate ranges currently in the range set, and < >
    // to illustrate rangeToAdd.
    Cut<C> lbToAdd = rangeToAdd.lowerBound;
    Cut<C> ubToAdd = rangeToAdd.upperBound;

    Entry<Cut<C>, Range<C>> entryBelowLB = rangesByLowerBound.lowerEntry(lbToAdd);
    if (entryBelowLB != null) {
      // { <
      Range<C> rangeBelowLB = entryBelowLB.getValue();
      if (rangeBelowLB.upperBound.compareTo(lbToAdd) >= 0) {
        // { < }, and we will need to coalesce
        if (rangeBelowLB.upperBound.compareTo(ubToAdd) >= 0) {
          // { < > }
          ubToAdd = rangeBelowLB.upperBound;
          /*
           * TODO(cpovirk): can we just "return;" here? Or, can we remove this if() entirely? If
           * not, add tests to demonstrate the problem with each approach
           */
        }
        lbToAdd = rangeBelowLB.lowerBound;
      }
    }

    Entry<Cut<C>, Range<C>> entryBelowUB = rangesByLowerBound.floorEntry(ubToAdd);
    if (entryBelowUB != null) {
      // { >
      Range<C> rangeBelowUB = entryBelowUB.getValue();
      if (rangeBelowUB.upperBound.compareTo(ubToAdd) >= 0) {
        // { > }, and we need to coalesce
        ubToAdd = rangeBelowUB.upperBound;
      }
    }

    // Remove ranges which are strictly enclosed.
    rangesByLowerBound.subMap(lbToAdd, ubToAdd).clear();

    replaceRangeWithSameLowerBound(Range.create(lbToAdd, ubToAdd));
  }

  @Override
  public void remove(Range<C> rangeToRemove) {
    checkNotNull(rangeToRemove);

    if (rangeToRemove.isEmpty()) {
      return;
    }

    // We will use { } to illustrate ranges currently in the range set, and < >
    // to illustrate rangeToRemove.

    Entry<Cut<C>, Range<C>> entryBelowLB = rangesByLowerBound.lowerEntry(rangeToRemove.lowerBound);
    if (entryBelowLB != null) {
      // { <
      Range<C> rangeBelowLB = entryBelowLB.getValue();
      if (rangeBelowLB.upperBound.compareTo(rangeToRemove.lowerBound) >= 0) {
        // { < }, and we will need to subdivide
        if (rangeToRemove.hasUpperBound()
            && rangeBelowLB.upperBound.compareTo(rangeToRemove.upperBound) >= 0) {
          // { < > }
          replaceRangeWithSameLowerBound(
              Range.create(rangeToRemove.upperBound, rangeBelowLB.upperBound));
        }
        replaceRangeWithSameLowerBound(
            Range.create(rangeBelowLB.lowerBound, rangeToRemove.lowerBound));
      }
    }

    Entry<Cut<C>, Range<C>> entryBelowUB = rangesByLowerBound.floorEntry(rangeToRemove.upperBound);
    if (entryBelowUB != null) {
      // { >
      Range<C> rangeBelowUB = entryBelowUB.getValue();
      if (rangeToRemove.hasUpperBound()
          && rangeBelowUB.upperBound.compareTo(rangeToRemove.upperBound) >= 0) {
        // { > }
        replaceRangeWithSameLowerBound(
            Range.create(rangeToRemove.upperBound, rangeBelowUB.upperBound));
      }
    }

    rangesByLowerBound.subMap(rangeToRemove.lowerBound, rangeToRemove.upperBound).clear();
  }

  private void replaceRangeWithSameLowerBound(Range<C> range) {
    if (range.isEmpty()) {
      rangesByLowerBound.remove(range.lowerBound);
    } else {
      rangesByLowerBound.put(range.lowerBound, range);
    }
  }

  private transient @MonotonicNonNull RangeSet<C> complement;

  @Override
  public RangeSet<C> complement() {
    RangeSet<C> result = complement;
    return (result == null) ? complement = new Complement() : result;
  }

  @VisibleForTesting
  static final class RangesByUpperBound<C extends Comparable<?>>
      extends AbstractNavigableMap<Cut<C>, Range<C>> {
    private final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;

    
upperBoundWindow represents the headMap/subMap/tailMap view of the entire "ranges by upper
bound" map; it's a constraint on the *keys*, and does not affect the values.
/**
     * upperBoundWindow represents the headMap/subMap/tailMap view of the entire "ranges by upper
     * bound" map; it's a constraint on the *keys*, and does not affect the values.
     */
    private final Range<Cut<C>> upperBoundWindow;

    RangesByUpperBound(NavigableMap<Cut<C>, Range<C>> rangesByLowerBound) {
      this.rangesByLowerBound = rangesByLowerBound;
      this.upperBoundWindow = Range.all();
    }

    private RangesByUpperBound(
        NavigableMap<Cut<C>, Range<C>> rangesByLowerBound, Range<Cut<C>> upperBoundWindow) {
      this.rangesByLowerBound = rangesByLowerBound;
      this.upperBoundWindow = upperBoundWindow;
    }

    private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> window) {
      if (window.isConnected(upperBoundWindow)) {
        return new RangesByUpperBound<C>(rangesByLowerBound, window.intersection(upperBoundWindow));
      } else {
        return ImmutableSortedMap.of();
      }
    }

    @Override
    public NavigableMap<Cut<C>, Range<C>> subMap(
        Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) {
      return subMap(
          Range.range(
              fromKey, BoundType.forBoolean(fromInclusive),
              toKey, BoundType.forBoolean(toInclusive)));
    }

    @Override
    public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) {
      return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
    }

    @Override
    public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) {
      return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
    }

    @Override
    public Comparator<? super Cut<C>> comparator() {
      return Ordering.<Cut<C>>natural();
    }

    @Override
    public boolean containsKey(@Nullable Object key) {
      return get(key) != null;
    }

    @Override
    public Range<C> get(@Nullable Object key) {
      if (key instanceof Cut) {
        try {
          @SuppressWarnings("unchecked") // we catch CCEs
          Cut<C> cut = (Cut<C>) key;
          if (!upperBoundWindow.contains(cut)) {
            return null;
          }
          Entry<Cut<C>, Range<C>> candidate = rangesByLowerBound.lowerEntry(cut);
          if (candidate != null && candidate.getValue().upperBound.equals(cut)) {
            return candidate.getValue();
          }
        } catch (ClassCastException e) {
          return null;
        }
      }
      return null;
    }

    @Override
    Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
      /*
       * We want to start the iteration at the first range where the upper bound is in
       * upperBoundWindow.
       */
      final Iterator<Range<C>> backingItr;
      if (!upperBoundWindow.hasLowerBound()) {
        backingItr = rangesByLowerBound.values().iterator();
      } else {
        Entry<Cut<C>, Range<C>> lowerEntry =
            rangesByLowerBound.lowerEntry(upperBoundWindow.lowerEndpoint());
        if (lowerEntry == null) {
          backingItr = rangesByLowerBound.values().iterator();
        } else if (upperBoundWindow.lowerBound.isLessThan(lowerEntry.getValue().upperBound)) {
          backingItr = rangesByLowerBound.tailMap(lowerEntry.getKey(), true).values().iterator();
        } else {
          backingItr =
              rangesByLowerBound
                  .tailMap(upperBoundWindow.lowerEndpoint(), true)
                  .values()
                  .iterator();
        }
      }
      return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
        @Override
        protected Entry<Cut<C>, Range<C>> computeNext() {
          if (!backingItr.hasNext()) {
            return endOfData();
          }
          Range<C> range = backingItr.next();
          if (upperBoundWindow.upperBound.isLessThan(range.upperBound)) {
            return endOfData();
          } else {
            return Maps.immutableEntry(range.upperBound, range);
          }
        }
      };
    }

    @Override
    Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
      Collection<Range<C>> candidates;
      if (upperBoundWindow.hasUpperBound()) {
        candidates =
            rangesByLowerBound
                .headMap(upperBoundWindow.upperEndpoint(), false)
                .descendingMap()
                .values();
      } else {
        candidates = rangesByLowerBound.descendingMap().values();
      }
      final PeekingIterator<Range<C>> backingItr = Iterators.peekingIterator(candidates.iterator());
      if (backingItr.hasNext()
          && upperBoundWindow.upperBound.isLessThan(backingItr.peek().upperBound)) {
        backingItr.next();
      }
      return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
        @Override
        protected Entry<Cut<C>, Range<C>> computeNext() {
          if (!backingItr.hasNext()) {
            return endOfData();
          }
          Range<C> range = backingItr.next();
          return upperBoundWindow.lowerBound.isLessThan(range.upperBound)
              ? Maps.immutableEntry(range.upperBound, range)
              : endOfData();
        }
      };
    }

    @Override
    public int size() {
      if (upperBoundWindow.equals(Range.all())) {
        return rangesByLowerBound.size();
      }
      return Iterators.size(entryIterator());
    }

    @Override
    public boolean isEmpty() {
      return upperBoundWindow.equals(Range.all())
          ? rangesByLowerBound.isEmpty()
          : !entryIterator().hasNext();
    }
  }

  private static final class ComplementRangesByLowerBound<C extends Comparable<?>>
      extends AbstractNavigableMap<Cut<C>, Range<C>> {
    private final NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound;
    private final NavigableMap<Cut<C>, Range<C>> positiveRangesByUpperBound;

    
complementLowerBoundWindow represents the headMap/subMap/tailMap view of the entire
"complement ranges by lower bound" map; it's a constraint on the *keys*, and does not affect
the values.
/**
     * complementLowerBoundWindow represents the headMap/subMap/tailMap view of the entire
     * "complement ranges by lower bound" map; it's a constraint on the *keys*, and does not affect
     * the values.
     */
    private final Range<Cut<C>> complementLowerBoundWindow;

    ComplementRangesByLowerBound(NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound) {
      this(positiveRangesByLowerBound, Range.<Cut<C>>all());
    }

    private ComplementRangesByLowerBound(
        NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound, Range<Cut<C>> window) {
      this.positiveRangesByLowerBound = positiveRangesByLowerBound;
      this.positiveRangesByUpperBound = new RangesByUpperBound<C>(positiveRangesByLowerBound);
      this.complementLowerBoundWindow = window;
    }

    private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> subWindow) {
      if (!complementLowerBoundWindow.isConnected(subWindow)) {
        return ImmutableSortedMap.of();
      } else {
        subWindow = subWindow.intersection(complementLowerBoundWindow);
        return new ComplementRangesByLowerBound<C>(positiveRangesByLowerBound, subWindow);
      }
    }

    @Override
    public NavigableMap<Cut<C>, Range<C>> subMap(
        Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) {
      return subMap(
          Range.range(
              fromKey, BoundType.forBoolean(fromInclusive),
              toKey, BoundType.forBoolean(toInclusive)));
    }

    @Override
    public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) {
      return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
    }

    @Override
    public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) {
      return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
    }

    @Override
    public Comparator<? super Cut<C>> comparator() {
      return Ordering.<Cut<C>>natural();
    }

    @Override
    Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
      /*
       * firstComplementRangeLowerBound is the first complement range lower bound inside
       * complementLowerBoundWindow. Complement range lower bounds are either positive range upper
       * bounds, or Cut.belowAll().
       *
       * positiveItr starts at the first positive range with lower bound greater than
       * firstComplementRangeLowerBound. (Positive range lower bounds correspond to complement range
       * upper bounds.)
       */
      Collection<Range<C>> positiveRanges;
      if (complementLowerBoundWindow.hasLowerBound()) {
        positiveRanges =
            positiveRangesByUpperBound
                .tailMap(
                    complementLowerBoundWindow.lowerEndpoint(),
                    complementLowerBoundWindow.lowerBoundType() == BoundType.CLOSED)
                .values();
      } else {
        positiveRanges = positiveRangesByUpperBound.values();
      }
      final PeekingIterator<Range<C>> positiveItr =
          Iterators.peekingIterator(positiveRanges.iterator());
      final Cut<C> firstComplementRangeLowerBound;
      if (complementLowerBoundWindow.contains(Cut.<C>belowAll())
          && (!positiveItr.hasNext() || positiveItr.peek().lowerBound != Cut.<C>belowAll())) {
        firstComplementRangeLowerBound = Cut.belowAll();
      } else if (positiveItr.hasNext()) {
        firstComplementRangeLowerBound = positiveItr.next().upperBound;
      } else {
        return Iterators.emptyIterator();
      }
      return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
        Cut<C> nextComplementRangeLowerBound = firstComplementRangeLowerBound;

        @Override
        protected Entry<Cut<C>, Range<C>> computeNext() {
          if (complementLowerBoundWindow.upperBound.isLessThan(nextComplementRangeLowerBound)
              || nextComplementRangeLowerBound == Cut.<C>aboveAll()) {
            return endOfData();
          }
          Range<C> negativeRange;
          if (positiveItr.hasNext()) {
            Range<C> positiveRange = positiveItr.next();
            negativeRange = Range.create(nextComplementRangeLowerBound, positiveRange.lowerBound);
            nextComplementRangeLowerBound = positiveRange.upperBound;
          } else {
            negativeRange = Range.create(nextComplementRangeLowerBound, Cut.<C>aboveAll());
            nextComplementRangeLowerBound = Cut.aboveAll();
          }
          return Maps.immutableEntry(negativeRange.lowerBound, negativeRange);
        }
      };
    }

    @Override
    Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
      /*
       * firstComplementRangeUpperBound is the upper bound of the last complement range with lower
       * bound inside complementLowerBoundWindow.
       *
       * positiveItr starts at the first positive range with upper bound less than
       * firstComplementRangeUpperBound. (Positive range upper bounds correspond to complement range
       * lower bounds.)
       */
      Cut<C> startingPoint =
          complementLowerBoundWindow.hasUpperBound()
              ? complementLowerBoundWindow.upperEndpoint()
              : Cut.<C>aboveAll();
      boolean inclusive =
          complementLowerBoundWindow.hasUpperBound()
              && complementLowerBoundWindow.upperBoundType() == BoundType.CLOSED;
      final PeekingIterator<Range<C>> positiveItr =
          Iterators.peekingIterator(
              positiveRangesByUpperBound
                  .headMap(startingPoint, inclusive)
                  .descendingMap()
                  .values()
                  .iterator());
      Cut<C> cut;
      if (positiveItr.hasNext()) {
        cut =
            (positiveItr.peek().upperBound == Cut.<C>aboveAll())
                ? positiveItr.next().lowerBound
                : positiveRangesByLowerBound.higherKey(positiveItr.peek().upperBound);
      } else if (!complementLowerBoundWindow.contains(Cut.<C>belowAll())
          || positiveRangesByLowerBound.containsKey(Cut.belowAll())) {
        return Iterators.emptyIterator();
      } else {
        cut = positiveRangesByLowerBound.higherKey(Cut.<C>belowAll());
      }
      final Cut<C> firstComplementRangeUpperBound =
          MoreObjects.firstNonNull(cut, Cut.<C>aboveAll());
      return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
        Cut<C> nextComplementRangeUpperBound = firstComplementRangeUpperBound;

        @Override
        protected Entry<Cut<C>, Range<C>> computeNext() {
          if (nextComplementRangeUpperBound == Cut.<C>belowAll()) {
            return endOfData();
          } else if (positiveItr.hasNext()) {
            Range<C> positiveRange = positiveItr.next();
            Range<C> negativeRange =
                Range.create(positiveRange.upperBound, nextComplementRangeUpperBound);
            nextComplementRangeUpperBound = positiveRange.lowerBound;
            if (complementLowerBoundWindow.lowerBound.isLessThan(negativeRange.lowerBound)) {
              return Maps.immutableEntry(negativeRange.lowerBound, negativeRange);
            }
          } else if (complementLowerBoundWindow.lowerBound.isLessThan(Cut.<C>belowAll())) {
            Range<C> negativeRange = Range.create(Cut.<C>belowAll(), nextComplementRangeUpperBound);
            nextComplementRangeUpperBound = Cut.belowAll();
            return Maps.immutableEntry(Cut.<C>belowAll(), negativeRange);
          }
          return endOfData();
        }
      };
    }

    @Override
    public int size() {
      return Iterators.size(entryIterator());
    }

    @Override
    public @Nullable Range<C> get(Object key) {
      if (key instanceof Cut) {
        try {
          @SuppressWarnings("unchecked")
          Cut<C> cut = (Cut<C>) key;
          // tailMap respects the current window
          Entry<Cut<C>, Range<C>> firstEntry = tailMap(cut, true).firstEntry();
          if (firstEntry != null && firstEntry.getKey().equals(cut)) {
            return firstEntry.getValue();
          }
        } catch (ClassCastException e) {
          return null;
        }
      }
      return null;
    }

    @Override
    public boolean containsKey(Object key) {
      return get(key) != null;
    }
  }

  private final class Complement extends TreeRangeSet<C> {
    Complement() {
      super(new ComplementRangesByLowerBound<C>(TreeRangeSet.this.rangesByLowerBound));
    }

    @Override
    public void add(Range<C> rangeToAdd) {
      TreeRangeSet.this.remove(rangeToAdd);
    }

    @Override
    public void remove(Range<C> rangeToRemove) {
      TreeRangeSet.this.add(rangeToRemove);
    }

    @Override
    public boolean contains(C value) {
      return !TreeRangeSet.this.contains(value);
    }

    @Override
    public RangeSet<C> complement() {
      return TreeRangeSet.this;
    }
  }

  private static final class SubRangeSetRangesByLowerBound<C extends Comparable<?>>
      extends AbstractNavigableMap<Cut<C>, Range<C>> {
    
lowerBoundWindow is the headMap/subMap/tailMap view; it only restricts the keys, and does not
affect the values.
/**
     * lowerBoundWindow is the headMap/subMap/tailMap view; it only restricts the keys, and does not
     * affect the values.
     */
    private final Range<Cut<C>> lowerBoundWindow;

    
restriction is the subRangeSet view; ranges are truncated to their intersection with
restriction.
/**
     * restriction is the subRangeSet view; ranges are truncated to their intersection with
     * restriction.
     */
    private final Range<C> restriction;

    private final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;
    private final NavigableMap<Cut<C>, Range<C>> rangesByUpperBound;

    private SubRangeSetRangesByLowerBound(
        Range<Cut<C>> lowerBoundWindow,
        Range<C> restriction,
        NavigableMap<Cut<C>, Range<C>> rangesByLowerBound) {
      this.lowerBoundWindow = checkNotNull(lowerBoundWindow);
      this.restriction = checkNotNull(restriction);
      this.rangesByLowerBound = checkNotNull(rangesByLowerBound);
      this.rangesByUpperBound = new RangesByUpperBound<C>(rangesByLowerBound);
    }

    private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> window) {
      if (!window.isConnected(lowerBoundWindow)) {
        return ImmutableSortedMap.of();
      } else {
        return new SubRangeSetRangesByLowerBound<C>(
            lowerBoundWindow.intersection(window), restriction, rangesByLowerBound);
      }
    }

    @Override
    public NavigableMap<Cut<C>, Range<C>> subMap(
        Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) {
      return subMap(
          Range.range(
              fromKey,
              BoundType.forBoolean(fromInclusive),
              toKey,
              BoundType.forBoolean(toInclusive)));
    }

    @Override
    public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) {
      return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
    }

    @Override
    public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) {
      return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
    }

    @Override
    public Comparator<? super Cut<C>> comparator() {
      return Ordering.<Cut<C>>natural();
    }

    @Override
    public boolean containsKey(@Nullable Object key) {
      return get(key) != null;
    }

    @Override
    public @Nullable Range<C> get(@Nullable Object key) {
      if (key instanceof Cut) {
        try {
          @SuppressWarnings("unchecked") // we catch CCE's
          Cut<C> cut = (Cut<C>) key;
          if (!lowerBoundWindow.contains(cut)
              || cut.compareTo(restriction.lowerBound) < 0
              || cut.compareTo(restriction.upperBound) >= 0) {
            return null;
          } else if (cut.equals(restriction.lowerBound)) {
            // it might be present, truncated on the left
            Range<C> candidate = Maps.valueOrNull(rangesByLowerBound.floorEntry(cut));
            if (candidate != null && candidate.upperBound.compareTo(restriction.lowerBound) > 0) {
              return candidate.intersection(restriction);
            }
          } else {
            Range<C> result = rangesByLowerBound.get(cut);
            if (result != null) {
              return result.intersection(restriction);
            }
          }
        } catch (ClassCastException e) {
          return null;
        }
      }
      return null;
    }

    @Override
    Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
      if (restriction.isEmpty()) {
        return Iterators.emptyIterator();
      }
      final Iterator<Range<C>> completeRangeItr;
      if (lowerBoundWindow.upperBound.isLessThan(restriction.lowerBound)) {
        return Iterators.emptyIterator();
      } else if (lowerBoundWindow.lowerBound.isLessThan(restriction.lowerBound)) {
        // starts at the first range with upper bound strictly greater than restriction.lowerBound
        completeRangeItr =
            rangesByUpperBound.tailMap(restriction.lowerBound, false).values().iterator();
      } else {
        // starts at the first range with lower bound above lowerBoundWindow.lowerBound
        completeRangeItr =
            rangesByLowerBound
                .tailMap(
                    lowerBoundWindow.lowerBound.endpoint(),
                    lowerBoundWindow.lowerBoundType() == BoundType.CLOSED)
                .values()
                .iterator();
      }
      final Cut<Cut<C>> upperBoundOnLowerBounds =
          Ordering.natural()
              .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
      return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
        @Override
        protected Entry<Cut<C>, Range<C>> computeNext() {
          if (!completeRangeItr.hasNext()) {
            return endOfData();
          }
          Range<C> nextRange = completeRangeItr.next();
          if (upperBoundOnLowerBounds.isLessThan(nextRange.lowerBound)) {
            return endOfData();
          } else {
            nextRange = nextRange.intersection(restriction);
            return Maps.immutableEntry(nextRange.lowerBound, nextRange);
          }
        }
      };
    }

    @Override
    Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
      if (restriction.isEmpty()) {
        return Iterators.emptyIterator();
      }
      Cut<Cut<C>> upperBoundOnLowerBounds =
          Ordering.natural()
              .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
      final Iterator<Range<C>> completeRangeItr =
          rangesByLowerBound
              .headMap(
                  upperBoundOnLowerBounds.endpoint(),
                  upperBoundOnLowerBounds.typeAsUpperBound() == BoundType.CLOSED)
              .descendingMap()
              .values()
              .iterator();
      return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
        @Override
        protected Entry<Cut<C>, Range<C>> computeNext() {
          if (!completeRangeItr.hasNext()) {
            return endOfData();
          }
          Range<C> nextRange = completeRangeItr.next();
          if (restriction.lowerBound.compareTo(nextRange.upperBound) >= 0) {
            return endOfData();
          }
          nextRange = nextRange.intersection(restriction);
          if (lowerBoundWindow.contains(nextRange.lowerBound)) {
            return Maps.immutableEntry(nextRange.lowerBound, nextRange);
          } else {
            return endOfData();
          }
        }
      };
    }

    @Override
    public int size() {
      return Iterators.size(entryIterator());
    }
  }

  @Override
  public RangeSet<C> subRangeSet(Range<C> view) {
    return view.equals(Range.<C>all()) ? this : new SubRangeSet(view);
  }

  private final class SubRangeSet extends TreeRangeSet<C> {
    private final Range<C> restriction;

    SubRangeSet(Range<C> restriction) {
      super(
          new SubRangeSetRangesByLowerBound<C>(
              Range.<Cut<C>>all(), restriction, TreeRangeSet.this.rangesByLowerBound));
      this.restriction = restriction;
    }

    @Override
    public boolean encloses(Range<C> range) {
      if (!restriction.isEmpty() && restriction.encloses(range)) {
        Range<C> enclosing = TreeRangeSet.this.rangeEnclosing(range);
        return enclosing != null && !enclosing.intersection(restriction).isEmpty();
      }
      return false;
    }

    @Override
    public @Nullable Range<C> rangeContaining(C value) {
      if (!restriction.contains(value)) {
        return null;
      }
      Range<C> result = TreeRangeSet.this.rangeContaining(value);
      return (result == null) ? null : result.intersection(restriction);
    }

    @Override
    public void add(Range<C> rangeToAdd) {
      checkArgument(
          restriction.encloses(rangeToAdd),
          "Cannot add range %s to subRangeSet(%s)",
          rangeToAdd,
          restriction);
      super.add(rangeToAdd);
    }

    @Override
    public void remove(Range<C> rangeToRemove) {
      if (rangeToRemove.isConnected(restriction)) {
        TreeRangeSet.this.remove(rangeToRemove.intersection(restriction));
      }
    }

    @Override
    public boolean contains(C value) {
      return restriction.contains(value) && TreeRangeSet.this.contains(value);
    }

    @Override
    public void clear() {
      TreeRangeSet.this.remove(restriction);
    }

    @Override
    public RangeSet<C> subRangeSet(Range<C> view) {
      if (view.encloses(restriction)) {
        return this;
      } else if (view.isConnected(restriction)) {
        return new SubRangeSet(restriction.intersection(view));
      } else {
        return ImmutableRangeSet.of();
      }
    }
  }
}