001 /*
002 * Copyright (C) 2010 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
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkNotNull;
020
021 import java.util.Comparator;
022 import java.util.Map;
023 import java.util.Map.Entry;
024 import java.util.SortedMap;
025
026 import javax.annotation.Nullable;
027
028 import com.google.common.annotations.Beta;
029 import com.google.common.annotations.GwtCompatible;
030 import com.google.common.annotations.GwtIncompatible;
031 import com.google.common.base.Function;
032 import com.google.common.base.Predicate;
033 import com.google.common.base.Predicates;
034 import com.google.common.collect.Maps.EntryTransformer;
035
036 /**
037 * Static utility methods pertaining to {@link SortedMap} instances.
038 *
039 * @author Louis Wasserman
040 * @since 8.0
041 * @deprecated Use the identical methods in {@link Maps}. This class is
042 * scheduled for deletion from Guava in Guava release 12.0.
043 */
044 @Beta
045 @Deprecated
046 @GwtCompatible
047 public final class SortedMaps {
048 private SortedMaps() {}
049
050 /**
051 * Returns a view of a sorted map where each value is transformed by a
052 * function. All other properties of the map, such as iteration order, are
053 * left intact. For example, the code: <pre> {@code
054 *
055 * SortedMap<String, Integer> map = ImmutableSortedMap.of("a", 4, "b", 9);
056 * Function<Integer, Double> sqrt =
057 * new Function<Integer, Double>() {
058 * public Double apply(Integer in) {
059 * return Math.sqrt((int) in);
060 * }
061 * };
062 * SortedMap<String, Double> transformed =
063 * Maps.transformSortedValues(map, sqrt);
064 * System.out.println(transformed);}</pre>
065 *
066 * ... prints {@code {a=2.0, b=3.0}}.
067 *
068 * <p>Changes in the underlying map are reflected in this view. Conversely,
069 * this view supports removal operations, and these are reflected in the
070 * underlying map.
071 *
072 * <p>It's acceptable for the underlying map to contain null keys, and even
073 * null values provided that the function is capable of accepting null input.
074 * The transformed map might contain null values, if the function sometimes
075 * gives a null result.
076 *
077 * <p>The returned map is not thread-safe or serializable, even if the
078 * underlying map is.
079 *
080 * <p>The function is applied lazily, invoked when needed. This is necessary
081 * for the returned map to be a view, but it means that the function will be
082 * applied many times for bulk operations like {@link Map#containsValue} and
083 * {@code Map.toString()}. For this to perform well, {@code function} should
084 * be fast. To avoid lazy evaluation when the returned map doesn't need to be
085 * a view, copy the returned map into a new map of your choosing.
086 *
087 * @deprecated Use {@link Maps#transformValues(SortedMap, Function)}
088 */
089 @Deprecated public static <K, V1, V2> SortedMap<K, V2> transformValues(
090 SortedMap<K, V1> fromMap, final Function<? super V1, V2> function) {
091 return Maps.transformValues(fromMap, function);
092 }
093
094 /**
095 * Returns a view of a sorted map whose values are derived from the original
096 * sorted map's entries. In contrast to {@link #transformValues}, this
097 * method's entry-transformation logic may depend on the key as well as the
098 * value.
099 *
100 * <p>All other properties of the transformed map, such as iteration order,
101 * are left intact. For example, the code: <pre> {@code
102 *
103 * Map<String, Boolean> options =
104 * ImmutableSortedMap.of("verbose", true, "sort", false);
105 * EntryTransformer<String, Boolean, String> flagPrefixer =
106 * new EntryTransformer<String, Boolean, String>() {
107 * public String transformEntry(String key, Boolean value) {
108 * return value ? key : "yes" + key;
109 * }
110 * };
111 * SortedMap<String, String> transformed =
112 * LabsMaps.transformSortedEntries(options, flagPrefixer);
113 * System.out.println(transformed);}</pre>
114 *
115 * ... prints {@code {sort=yessort, verbose=verbose}}.
116 *
117 * <p>Changes in the underlying map are reflected in this view. Conversely,
118 * this view supports removal operations, and these are reflected in the
119 * underlying map.
120 *
121 * <p>It's acceptable for the underlying map to contain null keys and null
122 * values provided that the transformer is capable of accepting null inputs.
123 * The transformed map might contain null values if the transformer sometimes
124 * gives a null result.
125 *
126 * <p>The returned map is not thread-safe or serializable, even if the
127 * underlying map is.
128 *
129 * <p>The transformer is applied lazily, invoked when needed. This is
130 * necessary for the returned map to be a view, but it means that the
131 * transformer will be applied many times for bulk operations like {@link
132 * Map#containsValue} and {@link Object#toString}. For this to perform well,
133 * {@code transformer} should be fast. To avoid lazy evaluation when the
134 * returned map doesn't need to be a view, copy the returned map into a new
135 * map of your choosing.
136 *
137 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
138 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
139 * that {@code k2} is also of type {@code K}. Using an {@code
140 * EntryTransformer} key type for which this may not hold, such as {@code
141 * ArrayList}, may risk a {@code ClassCastException} when calling methods on
142 * the transformed map.
143 *
144 * @deprecated Use {@link Maps#transformEntries(SortedMap, EntryTransformer)}
145 */
146 @Deprecated public static <K, V1, V2> SortedMap<K, V2> transformEntries(
147 final SortedMap<K, V1> fromMap,
148 EntryTransformer<? super K, ? super V1, V2> transformer) {
149 return Maps.transformEntries(fromMap, transformer);
150 }
151
152 /**
153 * Computes the difference between two sorted maps, using the comparator of
154 * the left map, or {@code Ordering.natural()} if the left map uses the
155 * natural ordering of its elements. This difference is an immutable snapshot
156 * of the state of the maps at the time this method is called. It will never
157 * change, even if the maps change at a later time.
158 *
159 * <p>Since this method uses {@code TreeMap} instances internally, the keys of
160 * the right map must all compare as distinct according to the comparator
161 * of the left map.
162 *
163 * <p><b>Note:</b>If you only need to know whether two sorted maps have the
164 * same mappings, call {@code left.equals(right)} instead of this method.
165 *
166 * @param left the map to treat as the "left" map for purposes of comparison
167 * @param right the map to treat as the "right" map for purposes of comparison
168 * @return the difference between the two maps
169 * @deprecated Use {@link Maps#difference(SortedMap, Map)}
170 */
171 @Deprecated public static <K, V> SortedMapDifference<K, V> difference(
172 SortedMap<K, ? extends V> left, Map<? extends K, ? extends V> right) {
173 return Maps.difference(left, right);
174 }
175
176 /**
177 * Returns the specified comparator if not null; otherwise returns {@code
178 * Ordering.natural()}. This method is an abomination of generics; the only
179 * purpose of this method is to contain the ugly type-casting in one place.
180 */
181 @SuppressWarnings("unchecked")
182 static <E> Comparator<? super E> orNaturalOrder(
183 @Nullable Comparator<? super E> comparator) {
184 if (comparator != null) { // can't use ? : because of javac bug 5080917
185 return comparator;
186 }
187 return (Comparator<E>) Ordering.natural();
188 }
189
190 /**
191 * Returns a sorted map containing the mappings in {@code unfiltered} whose
192 * keys satisfy a predicate. The returned map is a live view of {@code
193 * unfiltered}; changes to one affect the other.
194 *
195 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
196 * values()} views have iterators that don't support {@code remove()}, but all
197 * other methods are supported by the map and its views. When given a key that
198 * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()}
199 * methods throw an {@link IllegalArgumentException}.
200 *
201 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
202 * on the filtered map or its views, only mappings whose keys satisfy the
203 * filter will be removed from the underlying map.
204 *
205 * <p>The returned map isn't threadsafe or serializable, even if {@code
206 * unfiltered} is.
207 *
208 * <p>Many of the filtered map's methods, such as {@code size()},
209 * iterate across every key/value mapping in the underlying map and determine
210 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
211 * faster to copy the filtered map and use the copy.
212 *
213 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with
214 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
215 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
216 * inconsistent with equals.
217 */
218 @GwtIncompatible("untested")
219 public static <K, V> SortedMap<K, V> filterKeys(
220 SortedMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
221 // TODO: Return a subclass of Maps.FilteredKeyMap for slightly better
222 // performance.
223 checkNotNull(keyPredicate);
224 Predicate<Entry<K, V>> entryPredicate = new Predicate<Entry<K, V>>() {
225 @Override
226 public boolean apply(Entry<K, V> input) {
227 return keyPredicate.apply(input.getKey());
228 }
229 };
230 return filterEntries(unfiltered, entryPredicate);
231 }
232
233 /**
234 * Returns a sorted map containing the mappings in {@code unfiltered} whose
235 * values satisfy a predicate. The returned map is a live view of {@code
236 * unfiltered}; changes to one affect the other.
237 *
238 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
239 * values()} views have iterators that don't support {@code remove()}, but all
240 * other methods are supported by the map and its views. When given a value
241 * that doesn't satisfy the predicate, the map's {@code put()}, {@code
242 * putAll()}, and {@link Entry#setValue} methods throw an {@link
243 * IllegalArgumentException}.
244 *
245 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
246 * on the filtered map or its views, only mappings whose values satisfy the
247 * filter will be removed from the underlying map.
248 *
249 * <p>The returned map isn't threadsafe or serializable, even if {@code
250 * unfiltered} is.
251 *
252 * <p>Many of the filtered map's methods, such as {@code size()},
253 * iterate across every key/value mapping in the underlying map and determine
254 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
255 * faster to copy the filtered map and use the copy.
256 *
257 * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
258 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
259 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
260 * inconsistent with equals.
261 */
262 @GwtIncompatible("untested")
263 public static <K, V> SortedMap<K, V> filterValues(
264 SortedMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
265 checkNotNull(valuePredicate);
266 Predicate<Entry<K, V>> entryPredicate =
267 new Predicate<Entry<K, V>>() {
268 @Override
269 public boolean apply(Entry<K, V> input) {
270 return valuePredicate.apply(input.getValue());
271 }
272 };
273 return filterEntries(unfiltered, entryPredicate);
274 }
275
276 /**
277 * Returns a sorted map containing the mappings in {@code unfiltered} that
278 * satisfy a predicate. The returned map is a live view of {@code unfiltered};
279 * changes to one affect the other.
280 *
281 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
282 * values()} views have iterators that don't support {@code remove()}, but all
283 * other methods are supported by the map and its views. When given a
284 * key/value pair that doesn't satisfy the predicate, the map's {@code put()}
285 * and {@code putAll()} methods throw an {@link IllegalArgumentException}.
286 * Similarly, the map's entries have a {@link Entry#setValue} method that
287 * throws an {@link IllegalArgumentException} when the existing key and the
288 * provided value don't satisfy the predicate.
289 *
290 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
291 * on the filtered map or its views, only mappings that satisfy the filter
292 * will be removed from the underlying map.
293 *
294 * <p>The returned map isn't threadsafe or serializable, even if {@code
295 * unfiltered} is.
296 *
297 * <p>Many of the filtered map's methods, such as {@code size()},
298 * iterate across every key/value mapping in the underlying map and determine
299 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
300 * faster to copy the filtered map and use the copy.
301 *
302 * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
303 * equals</i>, as documented at {@link Predicate#apply}.
304 */
305 @GwtIncompatible("untested")
306 public static <K, V> SortedMap<K, V> filterEntries(
307 SortedMap<K, V> unfiltered,
308 Predicate<? super Entry<K, V>> entryPredicate) {
309 checkNotNull(entryPredicate);
310 return (unfiltered instanceof FilteredSortedMap)
311 ? filterFiltered((FilteredSortedMap<K, V>) unfiltered, entryPredicate)
312 : new FilteredSortedMap<K, V>(checkNotNull(unfiltered), entryPredicate);
313 }
314
315 /**
316 * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
317 * filtering a filtered sorted map.
318 */
319 private static <K, V> SortedMap<K, V> filterFiltered(
320 FilteredSortedMap<K, V> map,
321 Predicate<? super Entry<K, V>> entryPredicate) {
322 Predicate<Entry<K, V>> predicate
323 = Predicates.and(map.predicate, entryPredicate);
324 return new FilteredSortedMap<K, V>(map.sortedMap(), predicate);
325 }
326
327 private static class FilteredSortedMap<K, V>
328 extends Maps.FilteredEntryMap<K, V> implements SortedMap<K, V> {
329
330 FilteredSortedMap(SortedMap<K, V> unfiltered,
331 Predicate<? super Entry<K, V>> entryPredicate) {
332 super(unfiltered, entryPredicate);
333 }
334
335 SortedMap<K, V> sortedMap() {
336 return (SortedMap<K, V>) unfiltered;
337 }
338
339 @Override public Comparator<? super K> comparator() {
340 return sortedMap().comparator();
341 }
342
343 @Override public K firstKey() {
344 // correctly throws NoSuchElementException when filtered map is empty.
345 return keySet().iterator().next();
346 }
347
348 @Override public K lastKey() {
349 SortedMap<K, V> headMap = sortedMap();
350 while (true) {
351 // correctly throws NoSuchElementException when filtered map is empty.
352 K key = headMap.lastKey();
353 if (apply(key, unfiltered.get(key))) {
354 return key;
355 }
356 headMap = sortedMap().headMap(key);
357 }
358 }
359
360 @Override public SortedMap<K, V> headMap(K toKey) {
361 return new FilteredSortedMap<K, V>(sortedMap().headMap(toKey), predicate);
362 }
363
364 @Override public SortedMap<K, V> subMap(K fromKey, K toKey) {
365 return new FilteredSortedMap<K, V>(
366 sortedMap().subMap(fromKey, toKey), predicate);
367 }
368
369 @Override public SortedMap<K, V> tailMap(K fromKey) {
370 return new FilteredSortedMap<K, V>(
371 sortedMap().tailMap(fromKey), predicate);
372 }
373 }
374 }