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