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