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