1 /*
2 * Copyright (C) 2012 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.collect.CollectPreconditions.checkRemove;
20 import static com.google.common.collect.Maps.keyOrNull;
21
22 import com.google.common.annotations.Beta;
23 import com.google.common.annotations.GwtIncompatible;
24 import java.util.Iterator;
25 import java.util.NavigableMap;
26 import java.util.NavigableSet;
27 import java.util.NoSuchElementException;
28 import java.util.SortedMap;
29 import java.util.function.BiFunction;
30
31 /**
32 * A navigable map which forwards all its method calls to another navigable map. Subclasses should
33 * override one or more methods to modify the behavior of the backing map as desired per the <a
34 * href="http://en.wikipedia.org/wiki/Decorator_pattern">decorator pattern</a>.
35 *
36 * <p><b>Warning:</b> The methods of {@code ForwardingNavigableMap} forward <i>indiscriminately</i>
37 * to the methods of the delegate. For example, overriding {@link #put} alone <i>will not</i> change
38 * the behavior of {@link #putAll}, which can lead to unexpected behavior. In this case, you should
39 * override {@code putAll} as well, either providing your own implementation, or delegating to the
40 * provided {@code standardPutAll} method.
41 *
42 * <p><b>{@code default} method warning:</b> This class does <i>not</i> forward calls to {@code
43 * default} methods. Instead, it inherits their default implementations. When those implementations
44 * invoke methods, they invoke methods on the {@code ForwardingNavigableMap}.
45 *
46 * <p>Each of the {@code standard} methods uses the map's comparator (or the natural ordering of the
47 * elements, if there is no comparator) to test element equality. As a result, if the comparator is
48 * not consistent with equals, some of the standard implementations may violate the {@code Map}
49 * contract.
50 *
51 * <p>The {@code standard} methods and the collection views they return are not guaranteed to be
52 * thread-safe, even when all of the methods that they depend on are thread-safe.
53 *
54 * @author Louis Wasserman
55 * @since 12.0
56 */
57 @GwtIncompatible
58 public abstract class ForwardingNavigableMap<K, V> extends ForwardingSortedMap<K, V>
59 implements NavigableMap<K, V> {
60
61 /** Constructor for use by subclasses. */
62 protected ForwardingNavigableMap() {}
63
64 @Override
65 protected abstract NavigableMap<K, V> delegate();
66
67 @Override
68 public Entry<K, V> lowerEntry(K key) {
69 return delegate().lowerEntry(key);
70 }
71
72 /**
73 * A sensible definition of {@link #lowerEntry} in terms of the {@code lastEntry()} of {@link
74 * #headMap(Object, boolean)}. If you override {@code headMap}, you may wish to override {@code
75 * lowerEntry} to forward to this implementation.
76 */
77 protected Entry<K, V> standardLowerEntry(K key) {
78 return headMap(key, false).lastEntry();
79 }
80
81 @Override
82 public K lowerKey(K key) {
83 return delegate().lowerKey(key);
84 }
85
86 /**
87 * A sensible definition of {@link #lowerKey} in terms of {@code lowerEntry}. If you override
88 * {@link #lowerEntry}, you may wish to override {@code lowerKey} to forward to this
89 * implementation.
90 */
91 protected K standardLowerKey(K key) {
92 return keyOrNull(lowerEntry(key));
93 }
94
95 @Override
96 public Entry<K, V> floorEntry(K key) {
97 return delegate().floorEntry(key);
98 }
99
100 /**
101 * A sensible definition of {@link #floorEntry} in terms of the {@code lastEntry()} of {@link
102 * #headMap(Object, boolean)}. If you override {@code headMap}, you may wish to override {@code
103 * 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 {@link
130 * #tailMap(Object, boolean)}. If you override {@code tailMap}, you may wish to override {@code
131 * 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 {@link
158 * #tailMap(Object, boolean)}. If you override {@code tailMap}, you may wish to override {@code
159 * 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 {@link
186 * #entrySet}. If you override {@code entrySet}, you may wish to override {@code firstEntry} to
187 * 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 {@link
214 * #entrySet} of {@link #descendingMap}. If you override {@code descendingMap}, you may wish to
215 * 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 {@code
223 * 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 {@code
241 * entrySet}. If you override {@code entrySet}, you may wish to override {@code pollFirstEntry} to
242 * 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 {@code
255 * entrySet} of {@code descendingMap}. If you override {@code descendingMap}, you may wish to
256 * 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 this
269 * {@code NavigableMap}. In many cases, you may wish to override {@link
270 * ForwardingNavigableMap#descendingMap} to forward to this implementation or a subclass thereof.
271 *
272 * <p>In particular, this map iterates over entries with repeated calls to {@link
273 * NavigableMap#lowerEntry}. If a more efficient means of iteration is available, you may wish to
274 * override the {@code entryIterator()} method of this class.
275 *
276 * @since 12.0
277 */
278 @Beta
279 protected class StandardDescendingMap extends Maps.DescendingMap<K, V> {
280 /** Constructor for use by subclasses. */
281 public StandardDescendingMap() {}
282
283 @Override
284 NavigableMap<K, V> forward() {
285 return ForwardingNavigableMap.this;
286 }
287
288 @Override
289 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
290 forward().replaceAll(function);
291 }
292
293 @Override
294 protected Iterator<Entry<K, V>> entryIterator() {
295 return new Iterator<Entry<K, V>>() {
296 private Entry<K, V> toRemove = null;
297 private Entry<K, V> nextOrNull = forward().lastEntry();
298
299 @Override
300 public boolean hasNext() {
301 return nextOrNull != null;
302 }
303
304 @Override
305 public java.util.Map.Entry<K, V> next() {
306 if (!hasNext()) {
307 throw new NoSuchElementException();
308 }
309 try {
310 return nextOrNull;
311 } finally {
312 toRemove = nextOrNull;
313 nextOrNull = forward().lowerEntry(nextOrNull.getKey());
314 }
315 }
316
317 @Override
318 public void remove() {
319 checkRemove(toRemove != null);
320 forward().remove(toRemove.getKey());
321 toRemove = null;
322 }
323 };
324 }
325 }
326
327 @Override
328 public NavigableSet<K> navigableKeySet() {
329 return delegate().navigableKeySet();
330 }
331
332 /**
333 * A sensible implementation of {@link NavigableMap#navigableKeySet} in terms of the methods of
334 * this {@code NavigableMap}. In many cases, you may wish to override {@link
335 * ForwardingNavigableMap#navigableKeySet} to forward to this implementation or a subclass
336 * thereof.
337 *
338 * @since 12.0
339 */
340 @Beta
341 protected class StandardNavigableKeySet extends Maps.NavigableKeySet<K, V> {
342 /** Constructor for use by subclasses. */
343 public StandardNavigableKeySet() {
344 super(ForwardingNavigableMap.this);
345 }
346 }
347
348 @Override
349 public NavigableSet<K> descendingKeySet() {
350 return delegate().descendingKeySet();
351 }
352
353 /**
354 * A sensible definition of {@link #descendingKeySet} as the {@code navigableKeySet} of {@link
355 * #descendingMap}. (The {@link StandardDescendingMap} implementation implements {@code
356 * navigableKeySet} on its own, so as not to cause an infinite loop.) If you override {@code
357 * descendingMap}, you may wish to override {@code descendingKeySet} to forward to this
358 * implementation.
359 */
360 @Beta
361 protected NavigableSet<K> standardDescendingKeySet() {
362 return descendingMap().navigableKeySet();
363 }
364
365 /**
366 * A sensible definition of {@link #subMap(Object, Object)} in terms of {@link #subMap(Object,
367 * boolean, Object, boolean)}. If you override {@code subMap(K, boolean, K, boolean)}, you may
368 * wish to override {@code subMap} to forward to this implementation.
369 */
370 @Override
371 protected SortedMap<K, V> standardSubMap(K fromKey, K toKey) {
372 return subMap(fromKey, true, toKey, false);
373 }
374
375 @Override
376 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
377 return delegate().subMap(fromKey, fromInclusive, toKey, toInclusive);
378 }
379
380 @Override
381 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
382 return delegate().headMap(toKey, inclusive);
383 }
384
385 @Override
386 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
387 return delegate().tailMap(fromKey, inclusive);
388 }
389
390 /**
391 * A sensible definition of {@link #headMap(Object)} in terms of {@link #headMap(Object,
392 * boolean)}. If you override {@code headMap(K, boolean)}, you may wish to override {@code
393 * headMap} to forward to this implementation.
394 */
395 protected SortedMap<K, V> standardHeadMap(K toKey) {
396 return headMap(toKey, false);
397 }
398
399 /**
400 * A sensible definition of {@link #tailMap(Object)} in terms of {@link #tailMap(Object,
401 * boolean)}. If you override {@code tailMap(K, boolean)}, you may wish to override {@code
402 * tailMap} to forward to this implementation.
403 */
404 protected SortedMap<K, V> standardTailMap(K fromKey) {
405 return tailMap(fromKey, true);
406 }
407 }