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