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.CollectPreconditions.checkRemove; 020import static com.google.common.collect.Maps.keyOrNull; 021 022import com.google.common.annotations.Beta; 023import com.google.common.annotations.GwtIncompatible; 024import java.util.Iterator; 025import java.util.NavigableMap; 026import java.util.NavigableSet; 027import java.util.NoSuchElementException; 028import java.util.SortedMap; 029import java.util.function.BiFunction; 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 058public abstract class ForwardingNavigableMap<K, V> extends ForwardingSortedMap<K, V> 059 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 public Entry<K, V> lowerEntry(K key) { 069 return delegate().lowerEntry(key); 070 } 071 072 /** 073 * A sensible definition of {@link #lowerEntry} in terms of the {@code lastEntry()} of {@link 074 * #headMap(Object, boolean)}. If you override {@code headMap}, you may wish to override {@code 075 * lowerEntry} to forward to this implementation. 076 */ 077 protected Entry<K, V> standardLowerEntry(K key) { 078 return headMap(key, false).lastEntry(); 079 } 080 081 @Override 082 public K lowerKey(K key) { 083 return delegate().lowerKey(key); 084 } 085 086 /** 087 * A sensible definition of {@link #lowerKey} in terms of {@code lowerEntry}. If you override 088 * {@link #lowerEntry}, you may wish to override {@code lowerKey} to forward to this 089 * implementation. 090 */ 091 protected K standardLowerKey(K key) { 092 return keyOrNull(lowerEntry(key)); 093 } 094 095 @Override 096 public Entry<K, V> floorEntry(K key) { 097 return delegate().floorEntry(key); 098 } 099 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}