/*
 * 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.collect.CollectPreconditions.checkRemove;
import static com.google.common.collect.Maps.keyOrNull;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtIncompatible;
import java.util.Iterator;
import java.util.NavigableMap;
import java.util.NavigableSet;
import java.util.NoSuchElementException;
import java.util.SortedMap;
import java.util.function.BiFunction;

A navigable map which forwards all its method calls to another navigable map. Subclasses should
override one or more methods to modify the behavior of the backing map as desired per the decorator pattern.
Warning: The methods of ForwardingNavigableMap forward indiscriminately to the methods of the delegate. For example, overriding ForwardingMap.put alone will not change the behavior of ForwardingMap.putAll, which can lead to unexpected behavior. In this case, you should override putAll as well, either providing your own implementation, or delegating to the provided standardPutAll method. 
default method warning: This class does not forward calls to 
default methods. Instead, it inherits their default implementations. When those implementations invoke methods, they invoke methods on the ForwardingNavigableMap. 
Each of the standard methods uses the map's comparator (or the natural ordering of the elements, if there is no comparator) to test element equality. As a result, if the comparator is not consistent with equals, some of the standard implementations may violate the Map contract. 
The standard methods and the collection views they return are not guaranteed to be thread-safe, even when all of the methods that they depend on are thread-safe. 
Author:
Louis Wasserman
Since:
12.0/**
 * A navigable map which forwards all its method calls to another navigable map. Subclasses should
 * override one or more methods to modify the behavior of the backing map as desired per the <a
 * href="http://en.wikipedia.org/wiki/Decorator_pattern">decorator pattern</a>.
 *
 * <p><b>Warning:</b> The methods of {@code ForwardingNavigableMap} forward <i>indiscriminately</i>
 * to the methods of the delegate. For example, overriding {@link #put} alone <i>will not</i> change
 * the behavior of {@link #putAll}, which can lead to unexpected behavior. In this case, you should
 * override {@code putAll} as well, either providing your own implementation, or delegating to the
 * provided {@code standardPutAll} method.
 *
 * <p><b>{@code default} method warning:</b> This class does <i>not</i> forward calls to {@code
 * default} methods. Instead, it inherits their default implementations. When those implementations
 * invoke methods, they invoke methods on the {@code ForwardingNavigableMap}.
 *
 * <p>Each of the {@code standard} methods uses the map's comparator (or the natural ordering of the
 * elements, if there is no comparator) to test element equality. As a result, if the comparator is
 * not consistent with equals, some of the standard implementations may violate the {@code Map}
 * contract.
 *
 * <p>The {@code standard} methods and the collection views they return are not guaranteed to be
 * thread-safe, even when all of the methods that they depend on are thread-safe.
 *
 * @author Louis Wasserman
 * @since 12.0
 */
@GwtIncompatible
public abstract class ForwardingNavigableMap<K, V> extends ForwardingSortedMap<K, V>
    implements NavigableMap<K, V> {

  
Constructor for use by subclasses. /** Constructor for use by subclasses. */
  protected ForwardingNavigableMap() {}

  @Override
  protected abstract NavigableMap<K, V> delegate();

  @Override
  public Entry<K, V> lowerEntry(K key) {
    return delegate().lowerEntry(key);
  }

  
A sensible definition of lowerEntry in terms of the lastEntry() of headMap(Object, boolean). If you override headMap, you may wish to override 
lowerEntry to forward to this implementation. /**
   * A sensible definition of {@link #lowerEntry} in terms of the {@code lastEntry()} of {@link
   * #headMap(Object, boolean)}. If you override {@code headMap}, you may wish to override {@code
   * lowerEntry} to forward to this implementation.
   */
  protected Entry<K, V> standardLowerEntry(K key) {
    return headMap(key, false).lastEntry();
  }

  @Override
  public K lowerKey(K key) {
    return delegate().lowerKey(key);
  }

  
A sensible definition of lowerKey in terms of lowerEntry. If you override lowerEntry, you may wish to override lowerKey to forward to this implementation. /**
   * A sensible definition of {@link #lowerKey} in terms of {@code lowerEntry}. If you override
   * {@link #lowerEntry}, you may wish to override {@code lowerKey} to forward to this
   * implementation.
   */
  protected K standardLowerKey(K key) {
    return keyOrNull(lowerEntry(key));
  }

  @Override
  public Entry<K, V> floorEntry(K key) {
    return delegate().floorEntry(key);
  }

  
A sensible definition of floorEntry in terms of the lastEntry() of headMap(Object, boolean). If you override headMap, you may wish to override 
floorEntry to forward to this implementation. /**
   * A sensible definition of {@link #floorEntry} in terms of the {@code lastEntry()} of {@link
   * #headMap(Object, boolean)}. If you override {@code headMap}, you may wish to override {@code
   * floorEntry} to forward to this implementation.
   */
  protected Entry<K, V> standardFloorEntry(K key) {
    return headMap(key, true).lastEntry();
  }

  @Override
  public K floorKey(K key) {
    return delegate().floorKey(key);
  }

  
A sensible definition of floorKey in terms of floorEntry. If you override floorEntry, you may wish to override floorKey to forward to this implementation. /**
   * A sensible definition of {@link #floorKey} in terms of {@code floorEntry}. If you override
   * {@code floorEntry}, you may wish to override {@code floorKey} to forward to this
   * implementation.
   */
  protected K standardFloorKey(K key) {
    return keyOrNull(floorEntry(key));
  }

  @Override
  public Entry<K, V> ceilingEntry(K key) {
    return delegate().ceilingEntry(key);
  }

  
A sensible definition of ceilingEntry in terms of the firstEntry() of tailMap(Object, boolean). If you override tailMap, you may wish to override 
ceilingEntry to forward to this implementation. /**
   * A sensible definition of {@link #ceilingEntry} in terms of the {@code firstEntry()} of {@link
   * #tailMap(Object, boolean)}. If you override {@code tailMap}, you may wish to override {@code
   * ceilingEntry} to forward to this implementation.
   */
  protected Entry<K, V> standardCeilingEntry(K key) {
    return tailMap(key, true).firstEntry();
  }

  @Override
  public K ceilingKey(K key) {
    return delegate().ceilingKey(key);
  }

  
A sensible definition of ceilingKey in terms of ceilingEntry. If you override ceilingEntry, you may wish to override ceilingKey to forward to this implementation. /**
   * A sensible definition of {@link #ceilingKey} in terms of {@code ceilingEntry}. If you override
   * {@code ceilingEntry}, you may wish to override {@code ceilingKey} to forward to this
   * implementation.
   */
  protected K standardCeilingKey(K key) {
    return keyOrNull(ceilingEntry(key));
  }

  @Override
  public Entry<K, V> higherEntry(K key) {
    return delegate().higherEntry(key);
  }

  
A sensible definition of higherEntry in terms of the firstEntry() of tailMap(Object, boolean). If you override tailMap, you may wish to override 
higherEntry to forward to this implementation. /**
   * A sensible definition of {@link #higherEntry} in terms of the {@code firstEntry()} of {@link
   * #tailMap(Object, boolean)}. If you override {@code tailMap}, you may wish to override {@code
   * higherEntry} to forward to this implementation.
   */
  protected Entry<K, V> standardHigherEntry(K key) {
    return tailMap(key, false).firstEntry();
  }

  @Override
  public K higherKey(K key) {
    return delegate().higherKey(key);
  }

  
A sensible definition of higherKey in terms of higherEntry. If you override higherEntry, you may wish to override higherKey to forward to this implementation. /**
   * A sensible definition of {@link #higherKey} in terms of {@code higherEntry}. If you override
   * {@code higherEntry}, you may wish to override {@code higherKey} to forward to this
   * implementation.
   */
  protected K standardHigherKey(K key) {
    return keyOrNull(higherEntry(key));
  }

  @Override
  public Entry<K, V> firstEntry() {
    return delegate().firstEntry();
  }

  
A sensible definition of firstEntry in terms of the iterator() of ForwardingMap.entrySet. If you override entrySet, you may wish to override firstEntry to forward to this implementation. /**
   * A sensible definition of {@link #firstEntry} in terms of the {@code iterator()} of {@link
   * #entrySet}. If you override {@code entrySet}, you may wish to override {@code firstEntry} to
   * forward to this implementation.
   */
  protected Entry<K, V> standardFirstEntry() {
    return Iterables.getFirst(entrySet(), null);
  }

  
A sensible definition of ForwardingSortedMap.firstKey in terms of firstEntry. If you override firstEntry, you may wish to override firstKey to forward to this implementation. /**
   * A sensible definition of {@link #firstKey} in terms of {@code firstEntry}. If you override
   * {@code firstEntry}, you may wish to override {@code firstKey} to forward to this
   * implementation.
   */
  protected K standardFirstKey() {
    Entry<K, V> entry = firstEntry();
    if (entry == null) {
      throw new NoSuchElementException();
    } else {
      return entry.getKey();
    }
  }

  @Override
  public Entry<K, V> lastEntry() {
    return delegate().lastEntry();
  }

  
A sensible definition of lastEntry in terms of the iterator() of the ForwardingMap.entrySet of descendingMap. If you override descendingMap, you may wish to override lastEntry to forward to this implementation. /**
   * A sensible definition of {@link #lastEntry} in terms of the {@code iterator()} of the {@link
   * #entrySet} of {@link #descendingMap}. If you override {@code descendingMap}, you may wish to
   * override {@code lastEntry} to forward to this implementation.
   */
  protected Entry<K, V> standardLastEntry() {
    return Iterables.getFirst(descendingMap().entrySet(), null);
  }

  
A sensible definition of ForwardingSortedMap.lastKey in terms of lastEntry. If you override 
lastEntry, you may wish to override lastKey to forward to this implementation. /**
   * A sensible definition of {@link #lastKey} in terms of {@code lastEntry}. If you override {@code
   * lastEntry}, you may wish to override {@code lastKey} to forward to this implementation.
   */
  protected K standardLastKey() {
    Entry<K, V> entry = lastEntry();
    if (entry == null) {
      throw new NoSuchElementException();
    } else {
      return entry.getKey();
    }
  }

  @Override
  public Entry<K, V> pollFirstEntry() {
    return delegate().pollFirstEntry();
  }

  
A sensible definition of pollFirstEntry in terms of the iterator of 
entrySet. If you override entrySet, you may wish to override pollFirstEntry to forward to this implementation. /**
   * A sensible definition of {@link #pollFirstEntry} in terms of the {@code iterator} of {@code
   * entrySet}. If you override {@code entrySet}, you may wish to override {@code pollFirstEntry} to
   * forward to this implementation.
   */
  protected Entry<K, V> standardPollFirstEntry() {
    return Iterators.pollNext(entrySet().iterator());
  }

  @Override
  public Entry<K, V> pollLastEntry() {
    return delegate().pollLastEntry();
  }

  
A sensible definition of pollFirstEntry in terms of the iterator of the 
entrySet of descendingMap. If you override descendingMap, you may wish to override pollFirstEntry to forward to this implementation. /**
   * A sensible definition of {@link #pollFirstEntry} in terms of the {@code iterator} of the {@code
   * entrySet} of {@code descendingMap}. If you override {@code descendingMap}, you may wish to
   * override {@code pollFirstEntry} to forward to this implementation.
   */
  protected Entry<K, V> standardPollLastEntry() {
    return Iterators.pollNext(descendingMap().entrySet().iterator());
  }

  @Override
  public NavigableMap<K, V> descendingMap() {
    return delegate().descendingMap();
  }

  
A sensible implementation of NavigableMap.descendingMap in terms of the methods of this NavigableMap. In many cases, you may wish to override ForwardingNavigableMap.descendingMap to forward to this implementation or a subclass thereof. 
In particular, this map iterates over entries with repeated calls to NavigableMap.lowerEntry. If a more efficient means of iteration is available, you may wish to override the entryIterator() method of this class. 
Since:
12.0/**
   * A sensible implementation of {@link NavigableMap#descendingMap} in terms of the methods of this
   * {@code NavigableMap}. In many cases, you may wish to override {@link
   * ForwardingNavigableMap#descendingMap} to forward to this implementation or a subclass thereof.
   *
   * <p>In particular, this map iterates over entries with repeated calls to {@link
   * NavigableMap#lowerEntry}. If a more efficient means of iteration is available, you may wish to
   * override the {@code entryIterator()} method of this class.
   *
   * @since 12.0
   */
  @Beta
  protected class StandardDescendingMap extends Maps.DescendingMap<K, V> {
    
Constructor for use by subclasses. /** Constructor for use by subclasses. */
    public StandardDescendingMap() {}

    @Override
    NavigableMap<K, V> forward() {
      return ForwardingNavigableMap.this;
    }

    @Override
    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
      forward().replaceAll(function);
    }

    @Override
    protected Iterator<Entry<K, V>> entryIterator() {
      return new Iterator<Entry<K, V>>() {
        private Entry<K, V> toRemove = null;
        private Entry<K, V> nextOrNull = forward().lastEntry();

        @Override
        public boolean hasNext() {
          return nextOrNull != null;
        }

        @Override
        public java.util.Map.Entry<K, V> next() {
          if (!hasNext()) {
            throw new NoSuchElementException();
          }
          try {
            return nextOrNull;
          } finally {
            toRemove = nextOrNull;
            nextOrNull = forward().lowerEntry(nextOrNull.getKey());
          }
        }

        @Override
        public void remove() {
          checkRemove(toRemove != null);
          forward().remove(toRemove.getKey());
          toRemove = null;
        }
      };
    }
  }

  @Override
  public NavigableSet<K> navigableKeySet() {
    return delegate().navigableKeySet();
  }

  
A sensible implementation of NavigableMap.navigableKeySet in terms of the methods of this NavigableMap. In many cases, you may wish to override ForwardingNavigableMap.navigableKeySet to forward to this implementation or a subclass thereof. 
Since:
12.0/**
   * A sensible implementation of {@link NavigableMap#navigableKeySet} in terms of the methods of
   * this {@code NavigableMap}. In many cases, you may wish to override {@link
   * ForwardingNavigableMap#navigableKeySet} to forward to this implementation or a subclass
   * thereof.
   *
   * @since 12.0
   */
  @Beta
  protected class StandardNavigableKeySet extends Maps.NavigableKeySet<K, V> {
    
Constructor for use by subclasses. /** Constructor for use by subclasses. */
    public StandardNavigableKeySet() {
      super(ForwardingNavigableMap.this);
    }
  }

  @Override
  public NavigableSet<K> descendingKeySet() {
    return delegate().descendingKeySet();
  }

  
A sensible definition of descendingKeySet as the navigableKeySet of descendingMap. (The StandardDescendingMap implementation implements 
navigableKeySet on its own, so as not to cause an infinite loop.) If you override 
descendingMap, you may wish to override descendingKeySet to forward to this implementation. /**
   * A sensible definition of {@link #descendingKeySet} as the {@code navigableKeySet} of {@link
   * #descendingMap}. (The {@link StandardDescendingMap} implementation implements {@code
   * navigableKeySet} on its own, so as not to cause an infinite loop.) If you override {@code
   * descendingMap}, you may wish to override {@code descendingKeySet} to forward to this
   * implementation.
   */
  @Beta
  protected NavigableSet<K> standardDescendingKeySet() {
    return descendingMap().navigableKeySet();
  }

  
A sensible definition of ForwardingSortedMap.subMap(Object, Object) in terms of subMap(Object, boolean, Object, boolean). If you override subMap(K, boolean, K, boolean), you may wish to override subMap to forward to this implementation. /**
   * A sensible definition of {@link #subMap(Object, Object)} in terms of {@link #subMap(Object,
   * boolean, Object, boolean)}. If you override {@code subMap(K, boolean, K, boolean)}, you may
   * wish to override {@code subMap} to forward to this implementation.
   */
  @Override
  protected SortedMap<K, V> standardSubMap(K fromKey, K toKey) {
    return subMap(fromKey, true, toKey, false);
  }

  @Override
  public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
    return delegate().subMap(fromKey, fromInclusive, toKey, toInclusive);
  }

  @Override
  public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
    return delegate().headMap(toKey, inclusive);
  }

  @Override
  public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
    return delegate().tailMap(fromKey, inclusive);
  }

  
A sensible definition of ForwardingSortedMap.headMap(Object) in terms of headMap(Object, boolean). If you override headMap(K, boolean), you may wish to override 
headMap to forward to this implementation. /**
   * A sensible definition of {@link #headMap(Object)} in terms of {@link #headMap(Object,
   * boolean)}. If you override {@code headMap(K, boolean)}, you may wish to override {@code
   * headMap} to forward to this implementation.
   */
  protected SortedMap<K, V> standardHeadMap(K toKey) {
    return headMap(toKey, false);
  }

  
A sensible definition of ForwardingSortedMap.tailMap(Object) in terms of tailMap(Object, boolean). If you override tailMap(K, boolean), you may wish to override 
tailMap to forward to this implementation. /**
   * A sensible definition of {@link #tailMap(Object)} in terms of {@link #tailMap(Object,
   * boolean)}. If you override {@code tailMap(K, boolean)}, you may wish to override {@code
   * tailMap} to forward to this implementation.
   */
  protected SortedMap<K, V> standardTailMap(K fromKey) {
    return tailMap(fromKey, true);
  }
}