assertNull(navigableMap.lowerEntry(k0()));
    assertNull(navigableMap.lowerKey(k0()));
    assertNull(navigableMap.floorEntry(k0()));
    assertNull(navigableMap.floorKey(k0()));
    assertNull(navigableMap.ceilingEntry(k0()));
    assertNull(navigableMap.ceilingKey(k0()));
    assertNull(navigableMap.higherEntry(k0()));
    assertNull(navigableMap.higherKey(k0()));
  }

  @CollectionSize.Require(ZERO)

    assertThrows(NoSuchElementException.class, () -> assertNull(navigableMap.lastKey()));
  }

  @CollectionSize.Require(ONE)
  public void testSingletonMapFirst() {
    assertEquals(a.getKey(), navigableMap.firstKey());
  }

  @CollectionSize.Require(ONE)
  public void testSingletonMapLast() {
    assertEquals(a.getKey(), navigableMap.lastKey());
  }

  @CollectionSize.Require(SEVERAL)

        TestSortedMapGenerator<K, V> delegate, Bound to, Bound from) {
      super(delegate, to, from);
    }

    @Override
    NavigableMap<K, V> createSubMap(SortedMap<K, V> sortedMap, K firstExclusive, K lastExclusive) {
      NavigableMap<K, V> map = (NavigableMap<K, V>) sortedMap;
      if (from == Bound.NO_BOUND && to == Bound.INCLUSIVE) {
        return map.headMap(lastInclusive, true);

   * @since 12.0
   */
  @GwtIncompatible // NavigableMap
  public static <K extends @Nullable Object, V extends @Nullable Object>
      NavigableMap<K, V> unmodifiableNavigableMap(NavigableMap<K, ? extends V> map) {
    checkNotNull(map);
    if (map instanceof UnmodifiableNavigableMap) {
      @SuppressWarnings("unchecked") // covariant
      NavigableMap<K, V> result = (NavigableMap<K, V>) map;
      return result;
    } else {

   * @since 12.0
   */
  @GwtIncompatible // NavigableMap
  public static <K extends @Nullable Object, V extends @Nullable Object>
      NavigableMap<K, V> unmodifiableNavigableMap(NavigableMap<K, ? extends V> map) {
    checkNotNull(map);
    if (map instanceof UnmodifiableNavigableMap) {
      @SuppressWarnings("unchecked") // covariant
      NavigableMap<K, V> result = (NavigableMap<K, V>) map;
      return result;
    } else {

    assertThrows(NoSuchElementException.class, () -> assertNull(navigableMap.lastKey()));
  }

  @CollectionSize.Require(ONE)
  public void testSingletonMapFirst() {
    assertEquals(a.getKey(), navigableMap.firstKey());
  }

  @CollectionSize.Require(ONE)
  public void testSingletonMapLast() {
    assertEquals(a.getKey(), navigableMap.lastKey());
  }

  @CollectionSize.Require(SEVERAL)

  }

  <K, V> void testNavigationAgainstExpected(
      NavigableMap<K, V> expected, NavigableMap<K, V> navigableMap, Iterable<K> keysToTest) {
    for (K key : keysToTest) {
      assertEquals(expected.lowerEntry(key), navigableMap.lowerEntry(key));
      assertEquals(expected.floorEntry(key), navigableMap.floorEntry(key));
      assertEquals(expected.ceilingEntry(key), navigableMap.ceilingEntry(key));

        TestSortedMapGenerator<K, V> delegate, Bound to, Bound from) {
      super(delegate, to, from);
    }

    @Override
    NavigableMap<K, V> createSubMap(SortedMap<K, V> sortedMap, K firstExclusive, K lastExclusive) {
      NavigableMap<K, V> map = (NavigableMap<K, V>) sortedMap;
      if (from == Bound.NO_BOUND && to == Bound.INCLUSIVE) {
        return map.headMap(lastInclusive, true);

    return SortedMapTestSuiteBuilder.using(
            new TestStringSortedMapGenerator() {
              @Override
              protected NavigableMap<String, String> create(Entry<String, String>[] entries) {
                NavigableMap<String, String> map = populate(new TreeMap<String, String>(), entries);
                return Collections.checkedNavigableMap(map, String.class, String.class);
              }

 * @author Louis Wasserman
 * @since 14.0
 */
@SuppressWarnings("rawtypes") // https://github.com/google/guava/issues/989
@GwtIncompatible // NavigableMap
@ElementTypesAreNonnullByDefault
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() {