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