path: root/guava/src/com/google/common/collect/TreeRangeSet.java

/*
 * 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.Objects;

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 javax.annotation.Nullable;

/**
 * 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> {

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

  /**
   * 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 {@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;
  }

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

  private transient Set<Range<C>> asRanges;

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

  final class AsRanges extends ForwardingCollection<Range<C>> implements Set<Range<C>> {
    @Override
    protected Collection<Range<C>> delegate() {
      return rangesByLowerBound.values();
    }

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

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

  @Override
  @Nullable
  public 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 encloses(Range<C> range) {
    checkNotNull(range);
    Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound);
    return floorEntry != null && floorEntry.getValue().encloses(range);
  }
  
  @Nullable
  private 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 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.
     */
    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.
     */
    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() {
      Iterator<Range<C>> itr;
      /*
       * 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 = Objects.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
    @Nullable
    public 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.
     */
    private final Range<Cut<C>> lowerBoundWindow;

    /**
     * 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
    @Nullable
    public 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
    @Nullable
    public 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();
      }
    }
  }
}