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