1/* 2 * Copyright (C) 2007 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 17package com.google.common.collect; 18 19import com.google.common.annotations.Beta; 20import com.google.common.annotations.GwtCompatible; 21 22import java.util.Comparator; 23import java.util.Iterator; 24import java.util.NoSuchElementException; 25import java.util.SortedMap; 26 27import javax.annotation.Nullable; 28 29/** 30 * A sorted map which forwards all its method calls to another sorted map. 31 * Subclasses should override one or more methods to modify the behavior of 32 * the backing sorted map as desired per the <a 33 * href="http://en.wikipedia.org/wiki/Decorator_pattern">decorator pattern</a>. 34 * 35 * <p><i>Warning:</i> The methods of {@code ForwardingSortedMap} forward 36 * <i>indiscriminately</i> to the methods of the delegate. For example, 37 * overriding {@link #put} alone <i>will not</i> change the behavior of {@link 38 * #putAll}, which can lead to unexpected behavior. In this case, you should 39 * override {@code putAll} as well, either providing your own implementation, or 40 * delegating to the provided {@code standardPutAll} method. 41 * 42 * <p>Each of the {@code standard} methods, where appropriate, use the 43 * comparator of the map to test equality for both keys and values, unlike 44 * {@code ForwardingMap}. 45 * 46 * <p>The {@code standard} methods and the collection views they return are not 47 * guaranteed to be thread-safe, even when all of the methods that they depend 48 * on are thread-safe. 49 * 50 * @author Mike Bostock 51 * @author Louis Wasserman 52 * @since 2.0 (imported from Google Collections Library) 53 */ 54@GwtCompatible 55public abstract class ForwardingSortedMap<K, V> extends ForwardingMap<K, V> 56 implements SortedMap<K, V> { 57 // TODO(user): identify places where thread safety is actually lost 58 59 /** Constructor for use by subclasses. */ 60 protected ForwardingSortedMap() {} 61 62 @Override protected abstract SortedMap<K, V> delegate(); 63 64 @Override 65 public Comparator<? super K> comparator() { 66 return delegate().comparator(); 67 } 68 69 @Override 70 public K firstKey() { 71 return delegate().firstKey(); 72 } 73 74 @Override 75 public SortedMap<K, V> headMap(K toKey) { 76 return delegate().headMap(toKey); 77 } 78 79 @Override 80 public K lastKey() { 81 return delegate().lastKey(); 82 } 83 84 @Override 85 public SortedMap<K, V> subMap(K fromKey, K toKey) { 86 return delegate().subMap(fromKey, toKey); 87 } 88 89 @Override 90 public SortedMap<K, V> tailMap(K fromKey) { 91 return delegate().tailMap(fromKey); 92 } 93 94 // unsafe, but worst case is a CCE is thrown, which callers will be expecting 95 @SuppressWarnings("unchecked") 96 private int unsafeCompare(Object k1, Object k2) { 97 Comparator<? super K> comparator = comparator(); 98 if (comparator == null) { 99 return ((Comparable<Object>) k1).compareTo(k2); 100 } else { 101 return ((Comparator<Object>) comparator).compare(k1, k2); 102 } 103 } 104 105 /** 106 * A sensible definition of {@link #containsKey} in terms of the {@code 107 * firstKey()} method of {@link #tailMap}. If you override {@link #tailMap}, 108 * you may wish to override {@link #containsKey} to forward to this 109 * implementation. 110 * 111 * @since 7.0 112 */ 113 @Override @Beta protected boolean standardContainsKey(@Nullable Object key) { 114 try { 115 // any CCE will be caught 116 @SuppressWarnings("unchecked") 117 SortedMap<Object, V> self = (SortedMap<Object, V>) this; 118 Object ceilingKey = self.tailMap(key).firstKey(); 119 return unsafeCompare(ceilingKey, key) == 0; 120 } catch (ClassCastException e) { 121 return false; 122 } catch (NoSuchElementException e) { 123 return false; 124 } catch (NullPointerException e) { 125 return false; 126 } 127 } 128 129 /** 130 * A sensible definition of {@link #remove} in terms of the {@code 131 * iterator()} of the {@code entrySet()} of {@link #tailMap}. If you override 132 * {@link #tailMap}, you may wish to override {@link #remove} to forward 133 * to this implementation. 134 * 135 * @since 7.0 136 */ 137 @Override @Beta protected V standardRemove(@Nullable Object key) { 138 try { 139 // any CCE will be caught 140 @SuppressWarnings("unchecked") 141 SortedMap<Object, V> self = (SortedMap<Object, V>) this; 142 Iterator<Entry<Object, V>> entryIterator = 143 self.tailMap(key).entrySet().iterator(); 144 if (entryIterator.hasNext()) { 145 Entry<Object, V> ceilingEntry = entryIterator.next(); 146 if (unsafeCompare(ceilingEntry.getKey(), key) == 0) { 147 V value = ceilingEntry.getValue(); 148 entryIterator.remove(); 149 return value; 150 } 151 } 152 } catch (ClassCastException e) { 153 return null; 154 } catch (NullPointerException e) { 155 return null; 156 } 157 return null; 158 } 159 160 /** 161 * A sensible default implementation of {@link #subMap(Object, Object)} in 162 * terms of {@link #headMap(Object)} and {@link #tailMap(Object)}. In some 163 * situations, you may wish to override {@link #subMap(Object, Object)} to 164 * forward to this implementation. 165 * 166 * @since 7.0 167 */ 168 @Beta protected SortedMap<K, V> standardSubMap(K fromKey, K toKey) { 169 return tailMap(fromKey).headMap(toKey); 170 } 171} 172