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; 022import com.google.common.annotations.GwtIncompatible; 023import java.util.Iterator; 024import java.util.NavigableMap; 025import java.util.NavigableSet; 026import java.util.NoSuchElementException; 027import java.util.SortedMap; 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 @Beta 304 protected class StandardDescendingMap extends Maps.DescendingMap<K, V> { 305 /** Constructor for use by subclasses. */ 306 public StandardDescendingMap() {} 307 308 @Override 309 NavigableMap<K, V> forward() { 310 return ForwardingNavigableMap.this; 311 } 312 313 @Override 314 protected Iterator<Entry<K, V>> entryIterator() { 315 return new Iterator<Entry<K, V>>() { 316 @CheckForNull private Entry<K, V> toRemove = null; 317 @CheckForNull private Entry<K, V> nextOrNull = forward().lastEntry(); 318 319 @Override 320 public boolean hasNext() { 321 return nextOrNull != null; 322 } 323 324 @Override 325 public java.util.Map.Entry<K, V> next() { 326 if (nextOrNull == null) { 327 throw new NoSuchElementException(); 328 } 329 try { 330 return nextOrNull; 331 } finally { 332 toRemove = nextOrNull; 333 nextOrNull = forward().lowerEntry(nextOrNull.getKey()); 334 } 335 } 336 337 @Override 338 public void remove() { 339 if (toRemove == null) { 340 throw new IllegalStateException("no calls to next() since the last call to remove()"); 341 } 342 forward().remove(toRemove.getKey()); 343 toRemove = null; 344 } 345 }; 346 } 347 } 348 349 @Override 350 public NavigableSet<K> navigableKeySet() { 351 return delegate().navigableKeySet(); 352 } 353 354 /** 355 * A sensible implementation of {@link NavigableMap#navigableKeySet} in terms of the methods of 356 * this {@code NavigableMap}. In many cases, you may wish to override {@link 357 * ForwardingNavigableMap#navigableKeySet} to forward to this implementation or a subclass 358 * thereof. 359 * 360 * @since 12.0 361 */ 362 @Beta 363 protected class StandardNavigableKeySet extends Maps.NavigableKeySet<K, V> { 364 /** Constructor for use by subclasses. */ 365 public StandardNavigableKeySet() { 366 super(ForwardingNavigableMap.this); 367 } 368 } 369 370 @Override 371 public NavigableSet<K> descendingKeySet() { 372 return delegate().descendingKeySet(); 373 } 374 375 /** 376 * A sensible definition of {@link #descendingKeySet} as the {@code navigableKeySet} of {@link 377 * #descendingMap}. (The {@link StandardDescendingMap} implementation implements {@code 378 * navigableKeySet} on its own, so as not to cause an infinite loop.) If you override {@code 379 * descendingMap}, you may wish to override {@code descendingKeySet} to forward to this 380 * implementation. 381 */ 382 @Beta 383 protected NavigableSet<K> standardDescendingKeySet() { 384 return descendingMap().navigableKeySet(); 385 } 386 387 /** 388 * A sensible definition of {@link #subMap(Object, Object)} in terms of {@link #subMap(Object, 389 * boolean, Object, boolean)}. If you override {@code subMap(K, boolean, K, boolean)}, you may 390 * wish to override {@code subMap} to forward to this implementation. 391 */ 392 @Override 393 protected SortedMap<K, V> standardSubMap( 394 @ParametricNullness K fromKey, @ParametricNullness K toKey) { 395 return subMap(fromKey, true, toKey, false); 396 } 397 398 @Override 399 public NavigableMap<K, V> subMap( 400 @ParametricNullness K fromKey, 401 boolean fromInclusive, 402 @ParametricNullness K toKey, 403 boolean toInclusive) { 404 return delegate().subMap(fromKey, fromInclusive, toKey, toInclusive); 405 } 406 407 @Override 408 public NavigableMap<K, V> headMap(@ParametricNullness K toKey, boolean inclusive) { 409 return delegate().headMap(toKey, inclusive); 410 } 411 412 @Override 413 public NavigableMap<K, V> tailMap(@ParametricNullness K fromKey, boolean inclusive) { 414 return delegate().tailMap(fromKey, inclusive); 415 } 416 417 /** 418 * A sensible definition of {@link #headMap(Object)} in terms of {@link #headMap(Object, 419 * boolean)}. If you override {@code headMap(K, boolean)}, you may wish to override {@code 420 * headMap} to forward to this implementation. 421 */ 422 protected SortedMap<K, V> standardHeadMap(@ParametricNullness K toKey) { 423 return headMap(toKey, false); 424 } 425 426 /** 427 * A sensible definition of {@link #tailMap(Object)} in terms of {@link #tailMap(Object, 428 * boolean)}. If you override {@code tailMap(K, boolean)}, you may wish to override {@code 429 * tailMap} to forward to this implementation. 430 */ 431 protected SortedMap<K, V> standardTailMap(@ParametricNullness K fromKey) { 432 return tailMap(fromKey, true); 433 } 434}