001/*
002 * Copyright (C) 2012 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.collect.Maps.keyOrNull;
020
021import com.google.common.annotations.Beta;
022import com.google.common.annotations.GwtIncompatible;
023import java.util.Iterator;
024import java.util.NavigableMap;
025import java.util.NavigableSet;
026import java.util.NoSuchElementException;
027import java.util.SortedMap;
028import java.util.function.BiFunction;
029import javax.annotation.CheckForNull;
030import org.checkerframework.checker.nullness.qual.Nullable;
031
032/**
033 * A navigable map which forwards all its method calls to another navigable map. Subclasses should
034 * override one or more methods to modify the behavior of the backing map as desired per the <a
035 * href="http://en.wikipedia.org/wiki/Decorator_pattern">decorator pattern</a>.
036 *
037 * <p><b>Warning:</b> The methods of {@code ForwardingNavigableMap} forward <i>indiscriminately</i>
038 * to the methods of the delegate. For example, overriding {@link #put} alone <i>will not</i> change
039 * the behavior of {@link #putAll}, which can lead to unexpected behavior. In this case, you should
040 * override {@code putAll} as well, either providing your own implementation, or delegating to the
041 * provided {@code standardPutAll} method.
042 *
043 * <p><b>{@code default} method warning:</b> This class does <i>not</i> forward calls to {@code
044 * default} methods. Instead, it inherits their default implementations. When those implementations
045 * invoke methods, they invoke methods on the {@code ForwardingNavigableMap}.
046 *
047 * <p>Each of the {@code standard} methods uses the map's comparator (or the natural ordering of the
048 * elements, if there is no comparator) to test element equality. As a result, if the comparator is
049 * not consistent with equals, some of the standard implementations may violate the {@code Map}
050 * contract.
051 *
052 * <p>The {@code standard} methods and the collection views they return are not guaranteed to be
053 * thread-safe, even when all of the methods that they depend on are thread-safe.
054 *
055 * @author Louis Wasserman
056 * @since 12.0
057 */
058@GwtIncompatible
059@ElementTypesAreNonnullByDefault
060public abstract class ForwardingNavigableMap<K extends @Nullable Object, V extends @Nullable Object>
061    extends ForwardingSortedMap<K, V> implements NavigableMap<K, V> {
062
063  /** Constructor for use by subclasses. */
064  protected ForwardingNavigableMap() {}
065
066  @Override
067  protected abstract NavigableMap<K, V> delegate();
068
069  @Override
070  @CheckForNull
071  public Entry<K, V> lowerEntry(@ParametricNullness K key) {
072    return delegate().lowerEntry(key);
073  }
074
075  /**
076   * A sensible definition of {@link #lowerEntry} in terms of the {@code lastEntry()} of {@link
077   * #headMap(Object, boolean)}. If you override {@code headMap}, you may wish to override {@code
078   * lowerEntry} to forward to this implementation.
079   */
080  @CheckForNull
081  protected Entry<K, V> standardLowerEntry(@ParametricNullness K key) {
082    return headMap(key, false).lastEntry();
083  }
084
085  @Override
086  @CheckForNull
087  public K lowerKey(@ParametricNullness K key) {
088    return delegate().lowerKey(key);
089  }
090
091  /**
092   * A sensible definition of {@link #lowerKey} in terms of {@code lowerEntry}. If you override
093   * {@link #lowerEntry}, you may wish to override {@code lowerKey} to forward to this
094   * implementation.
095   */
096  @CheckForNull
097  protected K standardLowerKey(@ParametricNullness K key) {
098    return keyOrNull(lowerEntry(key));
099  }
100
101  @Override
102  @CheckForNull
103  public Entry<K, V> floorEntry(@ParametricNullness K key) {
104    return delegate().floorEntry(key);
105  }
106
107  /**
108   * A sensible definition of {@link #floorEntry} in terms of the {@code lastEntry()} of {@link
109   * #headMap(Object, boolean)}. If you override {@code headMap}, you may wish to override {@code
110   * floorEntry} to forward to this implementation.
111   */
112  @CheckForNull
113  protected Entry<K, V> standardFloorEntry(@ParametricNullness K key) {
114    return headMap(key, true).lastEntry();
115  }
116
117  @Override
118  @CheckForNull
119  public K floorKey(@ParametricNullness K key) {
120    return delegate().floorKey(key);
121  }
122
123  /**
124   * A sensible definition of {@link #floorKey} in terms of {@code floorEntry}. If you override
125   * {@code floorEntry}, you may wish to override {@code floorKey} to forward to this
126   * implementation.
127   */
128  @CheckForNull
129  protected K standardFloorKey(@ParametricNullness K key) {
130    return keyOrNull(floorEntry(key));
131  }
132
133  @Override
134  @CheckForNull
135  public Entry<K, V> ceilingEntry(@ParametricNullness K key) {
136    return delegate().ceilingEntry(key);
137  }
138
139  /**
140   * A sensible definition of {@link #ceilingEntry} in terms of the {@code firstEntry()} of {@link
141   * #tailMap(Object, boolean)}. If you override {@code tailMap}, you may wish to override {@code
142   * ceilingEntry} to forward to this implementation.
143   */
144  @CheckForNull
145  protected Entry<K, V> standardCeilingEntry(@ParametricNullness K key) {
146    return tailMap(key, true).firstEntry();
147  }
148
149  @Override
150  @CheckForNull
151  public K ceilingKey(@ParametricNullness K key) {
152    return delegate().ceilingKey(key);
153  }
154
155  /**
156   * A sensible definition of {@link #ceilingKey} in terms of {@code ceilingEntry}. If you override
157   * {@code ceilingEntry}, you may wish to override {@code ceilingKey} to forward to this
158   * implementation.
159   */
160  @CheckForNull
161  protected K standardCeilingKey(@ParametricNullness K key) {
162    return keyOrNull(ceilingEntry(key));
163  }
164
165  @Override
166  @CheckForNull
167  public Entry<K, V> higherEntry(@ParametricNullness K key) {
168    return delegate().higherEntry(key);
169  }
170
171  /**
172   * A sensible definition of {@link #higherEntry} in terms of the {@code firstEntry()} of {@link
173   * #tailMap(Object, boolean)}. If you override {@code tailMap}, you may wish to override {@code
174   * higherEntry} to forward to this implementation.
175   */
176  @CheckForNull
177  protected Entry<K, V> standardHigherEntry(@ParametricNullness K key) {
178    return tailMap(key, false).firstEntry();
179  }
180
181  @Override
182  @CheckForNull
183  public K higherKey(@ParametricNullness K key) {
184    return delegate().higherKey(key);
185  }
186
187  /**
188   * A sensible definition of {@link #higherKey} in terms of {@code higherEntry}. If you override
189   * {@code higherEntry}, you may wish to override {@code higherKey} to forward to this
190   * implementation.
191   */
192  @CheckForNull
193  protected K standardHigherKey(@ParametricNullness K key) {
194    return keyOrNull(higherEntry(key));
195  }
196
197  @Override
198  @CheckForNull
199  public Entry<K, V> firstEntry() {
200    return delegate().firstEntry();
201  }
202
203  /**
204   * A sensible definition of {@link #firstEntry} in terms of the {@code iterator()} of {@link
205   * #entrySet}. If you override {@code entrySet}, you may wish to override {@code firstEntry} to
206   * forward to this implementation.
207   */
208  @CheckForNull
209  protected Entry<K, V> standardFirstEntry() {
210    return Iterables.getFirst(entrySet(), null);
211  }
212
213  /**
214   * A sensible definition of {@link #firstKey} in terms of {@code firstEntry}. If you override
215   * {@code firstEntry}, you may wish to override {@code firstKey} to forward to this
216   * implementation.
217   */
218  protected K standardFirstKey() {
219    Entry<K, V> entry = firstEntry();
220    if (entry == null) {
221      throw new NoSuchElementException();
222    } else {
223      return entry.getKey();
224    }
225  }
226
227  @Override
228  @CheckForNull
229  public Entry<K, V> lastEntry() {
230    return delegate().lastEntry();
231  }
232
233  /**
234   * A sensible definition of {@link #lastEntry} in terms of the {@code iterator()} of the {@link
235   * #entrySet} of {@link #descendingMap}. If you override {@code descendingMap}, you may wish to
236   * override {@code lastEntry} to forward to this implementation.
237   */
238  @CheckForNull
239  protected Entry<K, V> standardLastEntry() {
240    return Iterables.getFirst(descendingMap().entrySet(), null);
241  }
242
243  /**
244   * A sensible definition of {@link #lastKey} in terms of {@code lastEntry}. If you override {@code
245   * lastEntry}, you may wish to override {@code lastKey} to forward to this implementation.
246   */
247  protected K standardLastKey() {
248    Entry<K, V> entry = lastEntry();
249    if (entry == null) {
250      throw new NoSuchElementException();
251    } else {
252      return entry.getKey();
253    }
254  }
255
256  @Override
257  @CheckForNull
258  public Entry<K, V> pollFirstEntry() {
259    return delegate().pollFirstEntry();
260  }
261
262  /**
263   * A sensible definition of {@link #pollFirstEntry} in terms of the {@code iterator} of {@code
264   * entrySet}. If you override {@code entrySet}, you may wish to override {@code pollFirstEntry} to
265   * forward to this implementation.
266   */
267  @CheckForNull
268  protected Entry<K, V> standardPollFirstEntry() {
269    return Iterators.pollNext(entrySet().iterator());
270  }
271
272  @Override
273  @CheckForNull
274  public Entry<K, V> pollLastEntry() {
275    return delegate().pollLastEntry();
276  }
277
278  /**
279   * A sensible definition of {@link #pollFirstEntry} in terms of the {@code iterator} of the {@code
280   * entrySet} of {@code descendingMap}. If you override {@code descendingMap}, you may wish to
281   * override {@code pollFirstEntry} to forward to this implementation.
282   */
283  @CheckForNull
284  protected Entry<K, V> standardPollLastEntry() {
285    return Iterators.pollNext(descendingMap().entrySet().iterator());
286  }
287
288  @Override
289  public NavigableMap<K, V> descendingMap() {
290    return delegate().descendingMap();
291  }
292
293  /**
294   * A sensible implementation of {@link NavigableMap#descendingMap} in terms of the methods of this
295   * {@code NavigableMap}. In many cases, you may wish to override {@link
296   * ForwardingNavigableMap#descendingMap} to forward to this implementation or a subclass thereof.
297   *
298   * <p>In particular, this map iterates over entries with repeated calls to {@link
299   * NavigableMap#lowerEntry}. If a more efficient means of iteration is available, you may wish to
300   * override the {@code entryIterator()} method of this class.
301   *
302   * @since 12.0
303   */
304  @Beta
305  protected class StandardDescendingMap extends Maps.DescendingMap<K, V> {
306    /** Constructor for use by subclasses. */
307    public StandardDescendingMap() {}
308
309    @Override
310    NavigableMap<K, V> forward() {
311      return ForwardingNavigableMap.this;
312    }
313
314    @Override
315    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
316      forward().replaceAll(function);
317    }
318
319    @Override
320    protected Iterator<Entry<K, V>> entryIterator() {
321      return new Iterator<Entry<K, V>>() {
322        @CheckForNull private Entry<K, V> toRemove = null;
323        @CheckForNull private Entry<K, V> nextOrNull = forward().lastEntry();
324
325        @Override
326        public boolean hasNext() {
327          return nextOrNull != null;
328        }
329
330        @Override
331        public java.util.Map.Entry<K, V> next() {
332          if (nextOrNull == null) {
333            throw new NoSuchElementException();
334          }
335          try {
336            return nextOrNull;
337          } finally {
338            toRemove = nextOrNull;
339            nextOrNull = forward().lowerEntry(nextOrNull.getKey());
340          }
341        }
342
343        @Override
344        public void remove() {
345          if (toRemove == null) {
346            throw new IllegalStateException("no calls to next() since the last call to remove()");
347          }
348          forward().remove(toRemove.getKey());
349          toRemove = null;
350        }
351      };
352    }
353  }
354
355  @Override
356  public NavigableSet<K> navigableKeySet() {
357    return delegate().navigableKeySet();
358  }
359
360  /**
361   * A sensible implementation of {@link NavigableMap#navigableKeySet} in terms of the methods of
362   * this {@code NavigableMap}. In many cases, you may wish to override {@link
363   * ForwardingNavigableMap#navigableKeySet} to forward to this implementation or a subclass
364   * thereof.
365   *
366   * @since 12.0
367   */
368  @Beta
369  protected class StandardNavigableKeySet extends Maps.NavigableKeySet<K, V> {
370    /** Constructor for use by subclasses. */
371    public StandardNavigableKeySet() {
372      super(ForwardingNavigableMap.this);
373    }
374  }
375
376  @Override
377  public NavigableSet<K> descendingKeySet() {
378    return delegate().descendingKeySet();
379  }
380
381  /**
382   * A sensible definition of {@link #descendingKeySet} as the {@code navigableKeySet} of {@link
383   * #descendingMap}. (The {@link StandardDescendingMap} implementation implements {@code
384   * navigableKeySet} on its own, so as not to cause an infinite loop.) If you override {@code
385   * descendingMap}, you may wish to override {@code descendingKeySet} to forward to this
386   * implementation.
387   */
388  @Beta
389  protected NavigableSet<K> standardDescendingKeySet() {
390    return descendingMap().navigableKeySet();
391  }
392
393  /**
394   * A sensible definition of {@link #subMap(Object, Object)} in terms of {@link #subMap(Object,
395   * boolean, Object, boolean)}. If you override {@code subMap(K, boolean, K, boolean)}, you may
396   * wish to override {@code subMap} to forward to this implementation.
397   */
398  @Override
399  protected SortedMap<K, V> standardSubMap(
400      @ParametricNullness K fromKey, @ParametricNullness K toKey) {
401    return subMap(fromKey, true, toKey, false);
402  }
403
404  @Override
405  public NavigableMap<K, V> subMap(
406      @ParametricNullness K fromKey,
407      boolean fromInclusive,
408      @ParametricNullness K toKey,
409      boolean toInclusive) {
410    return delegate().subMap(fromKey, fromInclusive, toKey, toInclusive);
411  }
412
413  @Override
414  public NavigableMap<K, V> headMap(@ParametricNullness K toKey, boolean inclusive) {
415    return delegate().headMap(toKey, inclusive);
416  }
417
418  @Override
419  public NavigableMap<K, V> tailMap(@ParametricNullness K fromKey, boolean inclusive) {
420    return delegate().tailMap(fromKey, inclusive);
421  }
422
423  /**
424   * A sensible definition of {@link #headMap(Object)} in terms of {@link #headMap(Object,
425   * boolean)}. If you override {@code headMap(K, boolean)}, you may wish to override {@code
426   * headMap} to forward to this implementation.
427   */
428  protected SortedMap<K, V> standardHeadMap(@ParametricNullness K toKey) {
429    return headMap(toKey, false);
430  }
431
432  /**
433   * A sensible definition of {@link #tailMap(Object)} in terms of {@link #tailMap(Object,
434   * boolean)}. If you override {@code tailMap(K, boolean)}, you may wish to override {@code
435   * tailMap} to forward to this implementation.
436   */
437  protected SortedMap<K, V> standardTailMap(@ParametricNullness K fromKey) {
438    return tailMap(fromKey, true);
439  }
440}