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