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