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