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