Java example source code file (TreeRangeSet.java)

This example Java source code file (TreeRangeSet.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

abstractiterator, annotation, comparable, complementrangesbylowerbound, cut, entry, iterator, navigablemap, nullable, object, override, range, rangesbyupperbound, subrangesetrangesbylowerbound, treerangeset, util

The TreeRangeSet.java Java example source code

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

  @VisibleForTesting final NavigableMap<Cut> rangesByLowerBound;

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

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

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

  private transient Set<Range asRanges;
  private transient Set<Range asDescendingSetOfRanges;

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

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

  final class AsRanges extends ForwardingCollection<Range implements Set> {

    final Collection<Range delegate;

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

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

    @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> 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> ceilingEntry = rangesByLowerBound.ceilingEntry(range.lowerBound);
    if (ceilingEntry != null
        && ceilingEntry.getValue().isConnected(range)
        && !ceilingEntry.getValue().intersection(range).isEmpty()) {
      return true;
    }
    Entry<Cut> 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> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound);
    return floorEntry != null && floorEntry.getValue().encloses(range);
  }

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

  @Override
  public Range<C> span() {
    Entry<Cut> firstEntry = rangesByLowerBound.firstEntry();
    Entry<Cut> 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> 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> 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> 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> 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> {
    private final NavigableMap<Cut> 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 upperBoundWindow;

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

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

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

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

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

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

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

    @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) key;
          if (!upperBoundWindow.contains(cut)) {
            return null;
          }
          Entry<Cut> 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>> entryIterator() {
      /*
       * We want to start the iteration at the first range where the upper bound is in
       * upperBoundWindow.
       */
      final Iterator<Range backingItr;
      if (!upperBoundWindow.hasLowerBound()) {
        backingItr = rangesByLowerBound.values().iterator();
      } else {
        Entry<Cut> 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>>() {
        @Override
        protected Entry<Cut> 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>> descendingEntryIterator() {
      Collection<Range candidates;
      if (upperBoundWindow.hasUpperBound()) {
        candidates =
            rangesByLowerBound
                .headMap(upperBoundWindow.upperEndpoint(), false)
                .descendingMap()
                .values();
      } else {
        candidates = rangesByLowerBound.descendingMap().values();
      }
      final PeekingIterator<Range backingItr = Iterators.peekingIterator(candidates.iterator());
      if (backingItr.hasNext()
          && upperBoundWindow.upperBound.isLessThan(backingItr.peek().upperBound)) {
        backingItr.next();
      }
      return new AbstractIterator<Entry>>() {
        @Override
        protected Entry<Cut> 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> {
    private final NavigableMap<Cut> positiveRangesByLowerBound;
    private final NavigableMap<Cut> 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 complementLowerBoundWindow;

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

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

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

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

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

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

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

    @Override
    Iterator<Entry>> 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 positiveRanges;
      if (complementLowerBoundWindow.hasLowerBound()) {
        positiveRanges =
            positiveRangesByUpperBound
                .tailMap(
                    complementLowerBoundWindow.lowerEndpoint(),
                    complementLowerBoundWindow.lowerBoundType() == BoundType.CLOSED)
                .values();
      } else {
        positiveRanges = positiveRangesByUpperBound.values();
      }
      final PeekingIterator<Range 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> nextComplementRangeLowerBound = firstComplementRangeLowerBound;

        @Override
        protected Entry<Cut> 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>> 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 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> nextComplementRangeUpperBound = firstComplementRangeUpperBound;

        @Override
        protected Entry<Cut> 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.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) key;
          // tailMap respects the current window
          Entry<Cut> 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> {
    /**
     * lowerBoundWindow is the headMap/subMap/tailMap view; it only restricts the keys, and does not
     * affect the values.
     */
    private final Range<Cut lowerBoundWindow;

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

    private final NavigableMap<Cut> rangesByLowerBound;
    private final NavigableMap<Cut> rangesByUpperBound;

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

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

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

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

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

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

    @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) 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>> entryIterator() {
      if (restriction.isEmpty()) {
        return Iterators.emptyIterator();
      }
      final Iterator<Range 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 upperBoundOnLowerBounds =
          Ordering.natural()
              .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
      return new AbstractIterator<Entry>>() {
        @Override
        protected Entry<Cut> 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>> descendingEntryIterator() {
      if (restriction.isEmpty()) {
        return Iterators.emptyIterator();
      }
      Cut<Cut upperBoundOnLowerBounds =
          Ordering.natural()
              .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
      final Iterator<Range completeRangeItr =
          rangesByLowerBound
              .headMap(
                  upperBoundOnLowerBounds.endpoint(),
                  upperBoundOnLowerBounds.typeAsUpperBound() == BoundType.CLOSED)
              .descendingMap()
              .values()
              .iterator();
      return new AbstractIterator<Entry>>() {
        @Override
        protected Entry<Cut> 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 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.<Cutall(), 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 view) {
      if (view.encloses(restriction)) {
        return this;
      } else if (view.isConnected(restriction)) {
        return new SubRangeSet(restriction.intersection(view));
      } else {
        return ImmutableRangeSet.of();
      }
    }
  }
}