guava/src/com/google/common/collect/TreeRangeMap.java - platform/external/guava - Git at Google

 /*
  * Copyright (C) 2012 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 static com.google.common.base.Predicates.compose;
 import static com.google.common.base.Predicates.in;
 import static com.google.common.base.Predicates.not;

 import com.google.common.annotations.Beta;
 import com.google.common.annotations.GwtIncompatible;
 import com.google.common.base.MoreObjects;
 import com.google.common.base.Predicate;

 import java.util.AbstractMap;
 import java.util.AbstractSet;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.NavigableMap;
 import java.util.NoSuchElementException;
 import java.util.Set;

 import javax.annotation.Nullable;

 /**
  * An implementation of {@code RangeMap} based on a {@code TreeMap}, supporting
  * all optional operations.
  *
  * <p>Like all {@code RangeMap} implementations, this supports neither null
  * keys nor null values.
  *
  * @author Louis Wasserman
  * @since 14.0
  */
 @Beta
 @GwtIncompatible("NavigableMap")
 public final class TreeRangeMap<K extends Comparable, V> implements RangeMap<K, V> {

   private final NavigableMap<Cut<K>, RangeMapEntry<K, V>> entriesByLowerBound;

   public static <K extends Comparable, V> TreeRangeMap<K, V> create() {
     return new TreeRangeMap<K, V>();
   }

   private TreeRangeMap() {
     this.entriesByLowerBound = Maps.newTreeMap();
   }

   private static final class RangeMapEntry<K extends Comparable, V>
       extends AbstractMapEntry<Range<K>, V> {
     private final Range<K> range;
     private final V value;

     RangeMapEntry(Cut<K> lowerBound, Cut<K> upperBound, V value) {
       this(Range.create(lowerBound, upperBound), value);
     }

     RangeMapEntry(Range<K> range, V value) {
       this.range = range;
       this.value = value;
     }

     @Override
     public Range<K> getKey() {
       return range;
     }

     @Override
     public V getValue() {
       return value;
     }

     public boolean contains(K value) {
       return range.contains(value);
     }

     Cut<K> getLowerBound() {
       return range.lowerBound;
     }

     Cut<K> getUpperBound() {
       return range.upperBound;
     }
   }

   @Override
   @Nullable
   public V get(K key) {
     Entry<Range<K>, V> entry = getEntry(key);
     return (entry == null) ? null : entry.getValue();
   }

   @Override
   @Nullable
   public Entry<Range<K>, V> getEntry(K key) {
     Map.Entry<Cut<K>, RangeMapEntry<K, V>> mapEntry =
         entriesByLowerBound.floorEntry(Cut.belowValue(key));
     if (mapEntry != null && mapEntry.getValue().contains(key)) {
       return mapEntry.getValue();
     } else {
       return null;
     }
   }

   @Override
   public void put(Range<K> range, V value) {
     if (!range.isEmpty()) {
       checkNotNull(value);
       remove(range);
       entriesByLowerBound.put(range.lowerBound, new RangeMapEntry<K, V>(range, value));
     }
   }

   @Override
   public void putAll(RangeMap<K, V> rangeMap) {
     for (Map.Entry<Range<K>, V> entry : rangeMap.asMapOfRanges().entrySet()) {
       put(entry.getKey(), entry.getValue());
     }
   }

   @Override
   public void clear() {
     entriesByLowerBound.clear();
   }

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

   private void putRangeMapEntry(Cut<K> lowerBound, Cut<K> upperBound, V value) {
     entriesByLowerBound.put(lowerBound, new RangeMapEntry<K, V>(lowerBound, upperBound, value));
   }

   @Override
   public void remove(Range<K> rangeToRemove) {
     if (rangeToRemove.isEmpty()) {
       return;
     }

     /*
      * The comments for this method will use [ ] to indicate the bounds of rangeToRemove and ( ) to
      * indicate the bounds of ranges in the range map.
      */
     Map.Entry<Cut<K>, RangeMapEntry<K, V>> mapEntryBelowToTruncate =
         entriesByLowerBound.lowerEntry(rangeToRemove.lowerBound);
     if (mapEntryBelowToTruncate != null) {
       // we know ( [
       RangeMapEntry<K, V> rangeMapEntry = mapEntryBelowToTruncate.getValue();
       if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.lowerBound) > 0) {
         // we know ( [ )
         if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.upperBound) > 0) {
           // we know ( [ ] ), so insert the range ] ) back into the map --
           // it's being split apart
           putRangeMapEntry(rangeToRemove.upperBound, rangeMapEntry.getUpperBound(),
               mapEntryBelowToTruncate.getValue().getValue());
         }
         // overwrite mapEntryToTruncateBelow with a truncated range
         putRangeMapEntry(rangeMapEntry.getLowerBound(), rangeToRemove.lowerBound,
             mapEntryBelowToTruncate.getValue().getValue());
       }
     }

     Map.Entry<Cut<K>, RangeMapEntry<K, V>> mapEntryAboveToTruncate =
         entriesByLowerBound.lowerEntry(rangeToRemove.upperBound);
     if (mapEntryAboveToTruncate != null) {
       // we know ( ]
       RangeMapEntry<K, V> rangeMapEntry = mapEntryAboveToTruncate.getValue();
       if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.upperBound) > 0) {
         // we know ( ] ), and since we dealt with truncating below already,
         // we know [ ( ] )
         putRangeMapEntry(rangeToRemove.upperBound, rangeMapEntry.getUpperBound(),
             mapEntryAboveToTruncate.getValue().getValue());
         entriesByLowerBound.remove(rangeToRemove.lowerBound);
       }
     }
     entriesByLowerBound.subMap(rangeToRemove.lowerBound, rangeToRemove.upperBound).clear();
   }

   @Override
   public Map<Range<K>, V> asMapOfRanges() {
     return new AsMapOfRanges();
   }

   private final class AsMapOfRanges extends AbstractMap<Range<K>, V> {

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

     @Override
     public V get(@Nullable Object key) {
       if (key instanceof Range) {
         Range<?> range = (Range<?>) key;
         RangeMapEntry<K, V> rangeMapEntry = entriesByLowerBound.get(range.lowerBound);
         if (rangeMapEntry != null && rangeMapEntry.getKey().equals(range)) {
           return rangeMapEntry.getValue();
         }
       }
       return null;
     }

     @Override
     public Set<Entry<Range<K>, V>> entrySet() {
       return new AbstractSet<Entry<Range<K>, V>>() {

         @SuppressWarnings("unchecked") // it's safe to upcast iterators
         @Override
         public Iterator<Entry<Range<K>, V>> iterator() {
           return (Iterator) entriesByLowerBound.values().iterator();
         }

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

   @Override
   public RangeMap<K, V> subRangeMap(Range<K> subRange) {
     if (subRange.equals(Range.all())) {
       return this;
     } else {
       return new SubRangeMap(subRange);
     }
   }

   @SuppressWarnings("unchecked")
   private RangeMap<K, V> emptySubRangeMap() {
     return EMPTY_SUB_RANGE_MAP;
   }

   private static final RangeMap EMPTY_SUB_RANGE_MAP =
       new RangeMap() {
         @Override
         @Nullable
         public Object get(Comparable key) {
           return null;
         }

         @Override
         @Nullable
         public Entry<Range, Object> getEntry(Comparable key) {
           return null;
         }

         @Override
         public Range span() {
           throw new NoSuchElementException();
         }

         @Override
         public void put(Range range, Object value) {
           checkNotNull(range);
           throw new IllegalArgumentException(
               "Cannot insert range " + range + " into an empty subRangeMap");
         }

         @Override
         public void putAll(RangeMap rangeMap) {
           if (!rangeMap.asMapOfRanges().isEmpty()) {
             throw new IllegalArgumentException(
                 "Cannot putAll(nonEmptyRangeMap) into an empty " + "subRangeMap");
           }
         }

         @Override
         public void clear() {}

         @Override
         public void remove(Range range) {
           checkNotNull(range);
         }

         @Override
         public Map<Range, Object> asMapOfRanges() {
           return Collections.emptyMap();
         }

         @Override
         public RangeMap subRangeMap(Range range) {
           checkNotNull(range);
           return this;
         }
       };

   private class SubRangeMap implements RangeMap<K, V> {

     private final Range<K> subRange;

     SubRangeMap(Range<K> subRange) {
       this.subRange = subRange;
     }

     @Override
     @Nullable
     public V get(K key) {
       return subRange.contains(key)
           ? TreeRangeMap.this.get(key)
           : null;
     }

     @Override
     @Nullable
     public Entry<Range<K>, V> getEntry(K key) {
       if (subRange.contains(key)) {
         Entry<Range<K>, V> entry = TreeRangeMap.this.getEntry(key);
         if (entry != null) {
           return Maps.immutableEntry(entry.getKey().intersection(subRange), entry.getValue());
         }
       }
       return null;
     }

     @Override
     public Range<K> span() {
       Cut<K> lowerBound;
       Entry<Cut<K>, RangeMapEntry<K, V>> lowerEntry =
           entriesByLowerBound.floorEntry(subRange.lowerBound);
       if (lowerEntry != null &&
           lowerEntry.getValue().getUpperBound().compareTo(subRange.lowerBound) > 0) {
         lowerBound = subRange.lowerBound;
       } else {
         lowerBound = entriesByLowerBound.ceilingKey(subRange.lowerBound);
         if (lowerBound == null || lowerBound.compareTo(subRange.upperBound) >= 0) {
           throw new NoSuchElementException();
         }
       }

       Cut<K> upperBound;
       Entry<Cut<K>, RangeMapEntry<K, V>> upperEntry =
           entriesByLowerBound.lowerEntry(subRange.upperBound);
       if (upperEntry == null) {
         throw new NoSuchElementException();
       } else if (upperEntry.getValue().getUpperBound().compareTo(subRange.upperBound) >= 0) {
         upperBound = subRange.upperBound;
       } else {
         upperBound = upperEntry.getValue().getUpperBound();
       }
       return Range.create(lowerBound, upperBound);
     }

     @Override
     public void put(Range<K> range, V value) {
       checkArgument(subRange.encloses(range),
           "Cannot put range %s into a subRangeMap(%s)", range, subRange);
       TreeRangeMap.this.put(range, value);
     }

     @Override
     public void putAll(RangeMap<K, V> rangeMap) {
       if (rangeMap.asMapOfRanges().isEmpty()) {
         return;
       }
       Range<K> span = rangeMap.span();
       checkArgument(subRange.encloses(span),
           "Cannot putAll rangeMap with span %s into a subRangeMap(%s)", span, subRange);
       TreeRangeMap.this.putAll(rangeMap);
     }

     @Override
     public void clear() {
       TreeRangeMap.this.remove(subRange);
     }

     @Override
     public void remove(Range<K> range) {
       if (range.isConnected(subRange)) {
         TreeRangeMap.this.remove(range.intersection(subRange));
       }
     }

     @Override
     public RangeMap<K, V> subRangeMap(Range<K> range) {
       if (!range.isConnected(subRange)) {
         return emptySubRangeMap();
       } else {
         return TreeRangeMap.this.subRangeMap(range.intersection(subRange));
       }
     }

     @Override
     public Map<Range<K>, V> asMapOfRanges() {
       return new SubRangeMapAsMap();
     }

     @Override
     public boolean equals(@Nullable Object o) {
       if (o instanceof RangeMap) {
         RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o;
         return asMapOfRanges().equals(rangeMap.asMapOfRanges());
       }
       return false;
     }

     @Override
     public int hashCode() {
       return asMapOfRanges().hashCode();
     }

     @Override
     public String toString() {
       return asMapOfRanges().toString();
     }

     class SubRangeMapAsMap extends AbstractMap<Range<K>, V> {

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

       @Override
       public V get(Object key) {
         try {
           if (key instanceof Range) {
             @SuppressWarnings("unchecked") // we catch ClassCastExceptions
             Range<K> r = (Range<K>) key;
             if (!subRange.encloses(r) || r.isEmpty()) {
               return null;
             }
             RangeMapEntry<K, V> candidate = null;
             if (r.lowerBound.compareTo(subRange.lowerBound) == 0) {
               // r could be truncated on the left
               Entry<Cut<K>, RangeMapEntry<K, V>> entry =
                   entriesByLowerBound.floorEntry(r.lowerBound);
               if (entry != null) {
                 candidate = entry.getValue();
               }
             } else {
               candidate = entriesByLowerBound.get(r.lowerBound);
             }

             if (candidate != null && candidate.getKey().isConnected(subRange)
                 && candidate.getKey().intersection(subRange).equals(r)) {
               return candidate.getValue();
             }
           }
         } catch (ClassCastException e) {
           return null;
         }
         return null;
       }

       @Override
       public V remove(Object key) {
         V value = get(key);
         if (value != null) {
           @SuppressWarnings("unchecked") // it's definitely in the map, so safe
           Range<K> range = (Range<K>) key;
           TreeRangeMap.this.remove(range);
           return value;
         }
         return null;
       }

       @Override
       public void clear() {
         SubRangeMap.this.clear();
       }

       private boolean removeEntryIf(Predicate<? super Entry<Range<K>, V>> predicate) {
         List<Range<K>> toRemove = Lists.newArrayList();
         for (Entry<Range<K>, V> entry : entrySet()) {
           if (predicate.apply(entry)) {
             toRemove.add(entry.getKey());
           }
         }
         for (Range<K> range : toRemove) {
           TreeRangeMap.this.remove(range);
         }
         return !toRemove.isEmpty();
       }

       @Override
       public Set<Range<K>> keySet() {
         return new Maps.KeySet<Range<K>, V>(SubRangeMapAsMap.this) {
           @Override
           public boolean remove(@Nullable Object o) {
             return SubRangeMapAsMap.this.remove(o) != null;
           }

           @Override
           public boolean retainAll(Collection<?> c) {
             return removeEntryIf(compose(not(in(c)), Maps.<Range<K>>keyFunction()));
           }
         };
       }

       @Override
       public Set<Entry<Range<K>, V>> entrySet() {
         return new Maps.EntrySet<Range<K>, V>() {
           @Override
           Map<Range<K>, V> map() {
             return SubRangeMapAsMap.this;
           }

           @Override
           public Iterator<Entry<Range<K>, V>> iterator() {
             if (subRange.isEmpty()) {
               return Iterators.emptyIterator();
             }
             Cut<K> cutToStart = MoreObjects.firstNonNull(
                 entriesByLowerBound.floorKey(subRange.lowerBound), subRange.lowerBound);
             final Iterator<RangeMapEntry<K, V>> backingItr =
                 entriesByLowerBound.tailMap(cutToStart, true).values().iterator();
             return new AbstractIterator<Entry<Range<K>, V>>() {

               @Override
               protected Entry<Range<K>, V> computeNext() {
                 while (backingItr.hasNext()) {
                   RangeMapEntry<K, V> entry = backingItr.next();
                   if (entry.getLowerBound().compareTo(subRange.upperBound) >= 0) {
                     break;
                   } else if (entry.getUpperBound().compareTo(subRange.lowerBound) > 0) {
                     // this might not be true e.g. at the start of the iteration
                     return Maps.immutableEntry(
                         entry.getKey().intersection(subRange), entry.getValue());
                   }
                 }
                 return endOfData();
               }
             };
           }

           @Override
           public boolean retainAll(Collection<?> c) {
             return removeEntryIf(not(in(c)));
           }

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

           @Override
           public boolean isEmpty() {
             return !iterator().hasNext();
           }
         };
       }

       @Override
       public Collection<V> values() {
         return new Maps.Values<Range<K>, V>(this) {
           @Override
           public boolean removeAll(Collection<?> c) {
             return removeEntryIf(compose(in(c), Maps.<V>valueFunction()));
           }

           @Override
           public boolean retainAll(Collection<?> c) {
             return removeEntryIf(compose(not(in(c)), Maps.<V>valueFunction()));
           }
         };
       }
     }
   }

   @Override
   public boolean equals(@Nullable Object o) {
     if (o instanceof RangeMap) {
       RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o;
       return asMapOfRanges().equals(rangeMap.asMapOfRanges());
     }
     return false;
   }

   @Override
   public int hashCode() {
     return asMapOfRanges().hashCode();
   }

   @Override
   public String toString() {
     return entriesByLowerBound.values().toString();
   }
 }
	/*
	* Copyright (C) 2012 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 static com.google.common.base.Predicates.compose;
	import static com.google.common.base.Predicates.in;
	import static com.google.common.base.Predicates.not;

	import com.google.common.annotations.Beta;
	import com.google.common.annotations.GwtIncompatible;
	import com.google.common.base.MoreObjects;
	import com.google.common.base.Predicate;

	import java.util.AbstractMap;
	import java.util.AbstractSet;
	import java.util.Collection;
	import java.util.Collections;
	import java.util.Iterator;
	import java.util.List;
	import java.util.Map;
	import java.util.Map.Entry;
	import java.util.NavigableMap;
	import java.util.NoSuchElementException;
	import java.util.Set;

	import javax.annotation.Nullable;

	/**
	* An implementation of {@code RangeMap} based on a {@code TreeMap}, supporting
	* all optional operations.
	*
	* <p>Like all {@code RangeMap} implementations, this supports neither null
	* keys nor null values.
	*
	* @author Louis Wasserman
	* @since 14.0
	*/
	@Beta
	@GwtIncompatible("NavigableMap")
	public final class TreeRangeMap<K extends Comparable, V> implements RangeMap<K, V> {

	private final NavigableMap<Cut<K>, RangeMapEntry<K, V>> entriesByLowerBound;

	public static <K extends Comparable, V> TreeRangeMap<K, V> create() {
	return new TreeRangeMap<K, V>();
	}

	private TreeRangeMap() {
	this.entriesByLowerBound = Maps.newTreeMap();
	}

	private static final class RangeMapEntry<K extends Comparable, V>
	extends AbstractMapEntry<Range<K>, V> {
	private final Range<K> range;
	private final V value;

	RangeMapEntry(Cut<K> lowerBound, Cut<K> upperBound, V value) {
	this(Range.create(lowerBound, upperBound), value);
	}

	RangeMapEntry(Range<K> range, V value) {
	this.range = range;
	this.value = value;
	}

	@Override
	public Range<K> getKey() {
	return range;
	}

	@Override
	public V getValue() {
	return value;
	}

	public boolean contains(K value) {
	return range.contains(value);
	}

	Cut<K> getLowerBound() {
	return range.lowerBound;
	}

	Cut<K> getUpperBound() {
	return range.upperBound;
	}
	}

	@Override
	@Nullable
	public V get(K key) {
	Entry<Range<K>, V> entry = getEntry(key);
	return (entry == null) ? null : entry.getValue();
	}

	@Override
	@Nullable
	public Entry<Range<K>, V> getEntry(K key) {
	Map.Entry<Cut<K>, RangeMapEntry<K, V>> mapEntry =
	entriesByLowerBound.floorEntry(Cut.belowValue(key));
	if (mapEntry != null && mapEntry.getValue().contains(key)) {
	return mapEntry.getValue();
	} else {
	return null;
	}
	}

	@Override
	public void put(Range<K> range, V value) {
	if (!range.isEmpty()) {
	checkNotNull(value);
	remove(range);
	entriesByLowerBound.put(range.lowerBound, new RangeMapEntry<K, V>(range, value));
	}
	}

	@Override
	public void putAll(RangeMap<K, V> rangeMap) {
	for (Map.Entry<Range<K>, V> entry : rangeMap.asMapOfRanges().entrySet()) {
	put(entry.getKey(), entry.getValue());
	}
	}

	@Override
	public void clear() {
	entriesByLowerBound.clear();
	}

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

	private void putRangeMapEntry(Cut<K> lowerBound, Cut<K> upperBound, V value) {
	entriesByLowerBound.put(lowerBound, new RangeMapEntry<K, V>(lowerBound, upperBound, value));
	}

	@Override
	public void remove(Range<K> rangeToRemove) {
	if (rangeToRemove.isEmpty()) {
	return;
	}

	/*
	* The comments for this method will use [ ] to indicate the bounds of rangeToRemove and ( ) to
	* indicate the bounds of ranges in the range map.
	*/
	Map.Entry<Cut<K>, RangeMapEntry<K, V>> mapEntryBelowToTruncate =
	entriesByLowerBound.lowerEntry(rangeToRemove.lowerBound);
	if (mapEntryBelowToTruncate != null) {
	// we know ( [
	RangeMapEntry<K, V> rangeMapEntry = mapEntryBelowToTruncate.getValue();
	if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.lowerBound) > 0) {
	// we know ( [ )
	if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.upperBound) > 0) {
	// we know ( [ ] ), so insert the range ] ) back into the map --
	// it's being split apart
	putRangeMapEntry(rangeToRemove.upperBound, rangeMapEntry.getUpperBound(),
	mapEntryBelowToTruncate.getValue().getValue());
	}
	// overwrite mapEntryToTruncateBelow with a truncated range
	putRangeMapEntry(rangeMapEntry.getLowerBound(), rangeToRemove.lowerBound,
	mapEntryBelowToTruncate.getValue().getValue());
	}
	}

	Map.Entry<Cut<K>, RangeMapEntry<K, V>> mapEntryAboveToTruncate =
	entriesByLowerBound.lowerEntry(rangeToRemove.upperBound);
	if (mapEntryAboveToTruncate != null) {
	// we know ( ]
	RangeMapEntry<K, V> rangeMapEntry = mapEntryAboveToTruncate.getValue();
	if (rangeMapEntry.getUpperBound().compareTo(rangeToRemove.upperBound) > 0) {
	// we know ( ] ), and since we dealt with truncating below already,
	// we know [ ( ] )
	putRangeMapEntry(rangeToRemove.upperBound, rangeMapEntry.getUpperBound(),
	mapEntryAboveToTruncate.getValue().getValue());
	entriesByLowerBound.remove(rangeToRemove.lowerBound);
	}
	}
	entriesByLowerBound.subMap(rangeToRemove.lowerBound, rangeToRemove.upperBound).clear();
	}

	@Override
	public Map<Range<K>, V> asMapOfRanges() {
	return new AsMapOfRanges();
	}

	private final class AsMapOfRanges extends AbstractMap<Range<K>, V> {

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

	@Override
	public V get(@Nullable Object key) {
	if (key instanceof Range) {
	Range<?> range = (Range<?>) key;
	RangeMapEntry<K, V> rangeMapEntry = entriesByLowerBound.get(range.lowerBound);
	if (rangeMapEntry != null && rangeMapEntry.getKey().equals(range)) {
	return rangeMapEntry.getValue();
	}
	}
	return null;
	}

	@Override
	public Set<Entry<Range<K>, V>> entrySet() {
	return new AbstractSet<Entry<Range<K>, V>>() {

	@SuppressWarnings("unchecked") // it's safe to upcast iterators
	@Override
	public Iterator<Entry<Range<K>, V>> iterator() {
	return (Iterator) entriesByLowerBound.values().iterator();
	}

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

	@Override
	public RangeMap<K, V> subRangeMap(Range<K> subRange) {
	if (subRange.equals(Range.all())) {
	return this;
	} else {
	return new SubRangeMap(subRange);
	}
	}

	@SuppressWarnings("unchecked")
	private RangeMap<K, V> emptySubRangeMap() {
	return EMPTY_SUB_RANGE_MAP;
	}

	private static final RangeMap EMPTY_SUB_RANGE_MAP =
	new RangeMap() {
	@Override
	@Nullable
	public Object get(Comparable key) {
	return null;
	}

	@Override
	@Nullable
	public Entry<Range, Object> getEntry(Comparable key) {
	return null;
	}

	@Override
	public Range span() {
	throw new NoSuchElementException();
	}

	@Override
	public void put(Range range, Object value) {
	checkNotNull(range);
	throw new IllegalArgumentException(
	"Cannot insert range " + range + " into an empty subRangeMap");
	}

	@Override
	public void putAll(RangeMap rangeMap) {
	if (!rangeMap.asMapOfRanges().isEmpty()) {
	throw new IllegalArgumentException(
	"Cannot putAll(nonEmptyRangeMap) into an empty " + "subRangeMap");
	}
	}

	@Override
	public void clear() {}

	@Override
	public void remove(Range range) {
	checkNotNull(range);
	}

	@Override
	public Map<Range, Object> asMapOfRanges() {
	return Collections.emptyMap();
	}

	@Override
	public RangeMap subRangeMap(Range range) {
	checkNotNull(range);
	return this;
	}
	};

	private class SubRangeMap implements RangeMap<K, V> {

	private final Range<K> subRange;

	SubRangeMap(Range<K> subRange) {
	this.subRange = subRange;
	}

	@Override
	@Nullable
	public V get(K key) {
	return subRange.contains(key)
	? TreeRangeMap.this.get(key)
	: null;
	}

	@Override
	@Nullable
	public Entry<Range<K>, V> getEntry(K key) {
	if (subRange.contains(key)) {
	Entry<Range<K>, V> entry = TreeRangeMap.this.getEntry(key);
	if (entry != null) {
	return Maps.immutableEntry(entry.getKey().intersection(subRange), entry.getValue());
	}
	}
	return null;
	}

	@Override
	public Range<K> span() {
	Cut<K> lowerBound;
	Entry<Cut<K>, RangeMapEntry<K, V>> lowerEntry =
	entriesByLowerBound.floorEntry(subRange.lowerBound);
	if (lowerEntry != null &&
	lowerEntry.getValue().getUpperBound().compareTo(subRange.lowerBound) > 0) {
	lowerBound = subRange.lowerBound;
	} else {
	lowerBound = entriesByLowerBound.ceilingKey(subRange.lowerBound);
	if (lowerBound == null \|\| lowerBound.compareTo(subRange.upperBound) >= 0) {
	throw new NoSuchElementException();
	}
	}

	Cut<K> upperBound;
	Entry<Cut<K>, RangeMapEntry<K, V>> upperEntry =
	entriesByLowerBound.lowerEntry(subRange.upperBound);
	if (upperEntry == null) {
	throw new NoSuchElementException();
	} else if (upperEntry.getValue().getUpperBound().compareTo(subRange.upperBound) >= 0) {
	upperBound = subRange.upperBound;
	} else {
	upperBound = upperEntry.getValue().getUpperBound();
	}
	return Range.create(lowerBound, upperBound);
	}

	@Override
	public void put(Range<K> range, V value) {
	checkArgument(subRange.encloses(range),
	"Cannot put range %s into a subRangeMap(%s)", range, subRange);
	TreeRangeMap.this.put(range, value);
	}

	@Override
	public void putAll(RangeMap<K, V> rangeMap) {
	if (rangeMap.asMapOfRanges().isEmpty()) {
	return;
	}
	Range<K> span = rangeMap.span();
	checkArgument(subRange.encloses(span),
	"Cannot putAll rangeMap with span %s into a subRangeMap(%s)", span, subRange);
	TreeRangeMap.this.putAll(rangeMap);
	}

	@Override
	public void clear() {
	TreeRangeMap.this.remove(subRange);
	}

	@Override
	public void remove(Range<K> range) {
	if (range.isConnected(subRange)) {
	TreeRangeMap.this.remove(range.intersection(subRange));
	}
	}

	@Override
	public RangeMap<K, V> subRangeMap(Range<K> range) {
	if (!range.isConnected(subRange)) {
	return emptySubRangeMap();
	} else {
	return TreeRangeMap.this.subRangeMap(range.intersection(subRange));
	}
	}

	@Override
	public Map<Range<K>, V> asMapOfRanges() {
	return new SubRangeMapAsMap();
	}

	@Override
	public boolean equals(@Nullable Object o) {
	if (o instanceof RangeMap) {
	RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o;
	return asMapOfRanges().equals(rangeMap.asMapOfRanges());
	}
	return false;
	}

	@Override
	public int hashCode() {
	return asMapOfRanges().hashCode();
	}

	@Override
	public String toString() {
	return asMapOfRanges().toString();
	}

	class SubRangeMapAsMap extends AbstractMap<Range<K>, V> {

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

	@Override
	public V get(Object key) {
	try {
	if (key instanceof Range) {
	@SuppressWarnings("unchecked") // we catch ClassCastExceptions
	Range<K> r = (Range<K>) key;
	if (!subRange.encloses(r) \|\| r.isEmpty()) {
	return null;
	}
	RangeMapEntry<K, V> candidate = null;
	if (r.lowerBound.compareTo(subRange.lowerBound) == 0) {
	// r could be truncated on the left
	Entry<Cut<K>, RangeMapEntry<K, V>> entry =
	entriesByLowerBound.floorEntry(r.lowerBound);
	if (entry != null) {
	candidate = entry.getValue();
	}
	} else {
	candidate = entriesByLowerBound.get(r.lowerBound);
	}

	if (candidate != null && candidate.getKey().isConnected(subRange)
	&& candidate.getKey().intersection(subRange).equals(r)) {
	return candidate.getValue();
	}
	}
	} catch (ClassCastException e) {
	return null;
	}
	return null;
	}

	@Override
	public V remove(Object key) {
	V value = get(key);
	if (value != null) {
	@SuppressWarnings("unchecked") // it's definitely in the map, so safe
	Range<K> range = (Range<K>) key;
	TreeRangeMap.this.remove(range);
	return value;
	}
	return null;
	}

	@Override
	public void clear() {
	SubRangeMap.this.clear();
	}

	private boolean removeEntryIf(Predicate<? super Entry<Range<K>, V>> predicate) {
	List<Range<K>> toRemove = Lists.newArrayList();
	for (Entry<Range<K>, V> entry : entrySet()) {
	if (predicate.apply(entry)) {
	toRemove.add(entry.getKey());
	}
	}
	for (Range<K> range : toRemove) {
	TreeRangeMap.this.remove(range);
	}
	return !toRemove.isEmpty();
	}

	@Override
	public Set<Range<K>> keySet() {
	return new Maps.KeySet<Range<K>, V>(SubRangeMapAsMap.this) {
	@Override
	public boolean remove(@Nullable Object o) {
	return SubRangeMapAsMap.this.remove(o) != null;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
	return removeEntryIf(compose(not(in(c)), Maps.<Range<K>>keyFunction()));
	}
	};
	}

	@Override
	public Set<Entry<Range<K>, V>> entrySet() {
	return new Maps.EntrySet<Range<K>, V>() {
	@Override
	Map<Range<K>, V> map() {
	return SubRangeMapAsMap.this;
	}

	@Override
	public Iterator<Entry<Range<K>, V>> iterator() {
	if (subRange.isEmpty()) {
	return Iterators.emptyIterator();
	}
	Cut<K> cutToStart = MoreObjects.firstNonNull(
	entriesByLowerBound.floorKey(subRange.lowerBound), subRange.lowerBound);
	final Iterator<RangeMapEntry<K, V>> backingItr =
	entriesByLowerBound.tailMap(cutToStart, true).values().iterator();
	return new AbstractIterator<Entry<Range<K>, V>>() {

	@Override
	protected Entry<Range<K>, V> computeNext() {
	while (backingItr.hasNext()) {
	RangeMapEntry<K, V> entry = backingItr.next();
	if (entry.getLowerBound().compareTo(subRange.upperBound) >= 0) {
	break;
	} else if (entry.getUpperBound().compareTo(subRange.lowerBound) > 0) {
	// this might not be true e.g. at the start of the iteration
	return Maps.immutableEntry(
	entry.getKey().intersection(subRange), entry.getValue());
	}
	}
	return endOfData();
	}
	};
	}

	@Override
	public boolean retainAll(Collection<?> c) {
	return removeEntryIf(not(in(c)));
	}

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

	@Override
	public boolean isEmpty() {
	return !iterator().hasNext();
	}
	};
	}

	@Override
	public Collection<V> values() {
	return new Maps.Values<Range<K>, V>(this) {
	@Override
	public boolean removeAll(Collection<?> c) {
	return removeEntryIf(compose(in(c), Maps.<V>valueFunction()));
	}

	@Override
	public boolean retainAll(Collection<?> c) {
	return removeEntryIf(compose(not(in(c)), Maps.<V>valueFunction()));
	}
	};
	}
	}
	}

	@Override
	public boolean equals(@Nullable Object o) {
	if (o instanceof RangeMap) {
	RangeMap<?, ?> rangeMap = (RangeMap<?, ?>) o;
	return asMapOfRanges().equals(rangeMap.asMapOfRanges());
	}
	return false;
	}

	@Override
	public int hashCode() {
	return asMapOfRanges().hashCode();
	}

	@Override
	public String toString() {
	return entriesByLowerBound.values().toString();
	}
	}