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    
017    package com.google.common.collect;
018    
019    import static com.google.common.collect.Maps.keyOrNull;
020    
021    import com.google.common.annotations.Beta;
022    
023    import java.util.Iterator;
024    import java.util.NavigableMap;
025    import java.util.NavigableSet;
026    import java.util.NoSuchElementException;
027    import java.util.SortedMap;
028    
029    import 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
054    public 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    }