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
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020
021import com.google.common.annotations.Beta;
022import com.google.common.annotations.GwtCompatible;
023import com.google.common.annotations.GwtIncompatible;
024import com.google.common.base.Function;
025import com.google.common.base.Objects;
026import com.google.common.base.Predicate;
027import com.google.common.base.Predicates;
028import com.google.common.collect.MapDifference.ValueDifference;
029import com.google.common.collect.Maps.EntryTransformer;
030import com.google.common.collect.Maps.MapDifferenceImpl;
031import com.google.common.collect.Maps.TransformedEntriesMap;
032import com.google.common.collect.Maps.ValueDifferenceImpl;
033
034import java.util.Collections;
035import java.util.Comparator;
036import java.util.Map;
037import java.util.Map.Entry;
038import java.util.SortedMap;
039
040import 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
050public 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}