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