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