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 }