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