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.0
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, ValueDifferenceImpl.create(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    }