Java example source code file (Multimaps.java)

   {@code
   *
   *   {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]}}</pre>
   *
   * <p>The returned multimap is serializable if its keys and values are all
   * serializable.
   *
   * @param values the values to use when constructing the {@code
   *     ImmutableListMultimap}
   * @param keyFunction the function used to produce the key for each value
   * @return {@code ImmutableListMultimap} mapping the result of evaluating the
   *     function {@code keyFunction} on each value in the input collection to
   *     that value
   * @throws NullPointerException if any of the following cases is true:
   *     <ul>
   *     <li>{@code values} is null
   *     <li>{@code keyFunction} is null
   *     <li>An element in {@code values} is null
   *     <li>{@code keyFunction} returns {@code null} for any element of {@code
   *         values}
   *     </ul>
   * @since 10.0
   */
  public static <K, V> ImmutableListMultimap index(
      Iterator<V> values, Function keyFunction) {
    checkNotNull(keyFunction);
    ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder();
    while (values.hasNext()) {
      V value = values.next();
      checkNotNull(value, values);
      builder.put(keyFunction.apply(value), value);
    }
    return builder.build();
  }

  static class Keys<K, V> extends AbstractMultiset {
    @Weak final Multimap<K, V> multimap;

    Keys(Multimap<K, V> multimap) {
      this.multimap = multimap;
    }

    @Override
    Iterator<Multiset.Entry entryIterator() {
      return new TransformedIterator<Map.Entry, Multiset.Entry>(
          multimap.asMap().entrySet().iterator()) {
        @Override
        Multiset.Entry<K> transform(final Map.Entry> backingEntry) {
          return new Multisets.AbstractEntry<K>() {
            @Override
            public K getElement() {
              return backingEntry.getKey();
            }

            @Override
            public int getCount() {
              return backingEntry.getValue().size();
            }
          };
        }
      };
    }

    @Override
    int distinctElements() {
      return multimap.asMap().size();
    }

    @Override
    Set<Multiset.Entry createEntrySet() {
      return new KeysEntrySet();
    }

    @WeakOuter
    class KeysEntrySet extends Multisets.EntrySet<K> {
      @Override
      Multiset<K> multiset() {
        return Keys.this;
      }

      @Override
      public Iterator<Multiset.Entry iterator() {
        return entryIterator();
      }

      @Override
      public int size() {
        return distinctElements();
      }

      @Override
      public boolean isEmpty() {
        return multimap.isEmpty();
      }

      @Override
      public boolean contains(@Nullable Object o) {
        if (o instanceof Multiset.Entry) {
          Multiset.Entry<?> entry = (Multiset.Entry) o;
          Collection<V> collection = multimap.asMap().get(entry.getElement());
          return collection != null && collection.size() == entry.getCount();
        }
        return false;
      }

      @Override
      public boolean remove(@Nullable Object o) {
        if (o instanceof Multiset.Entry) {
          Multiset.Entry<?> entry = (Multiset.Entry) o;
          Collection<V> collection = multimap.asMap().get(entry.getElement());
          if (collection != null && collection.size() == entry.getCount()) {
            collection.clear();
            return true;
          }
        }
        return false;
      }
    }

    @Override
    public boolean contains(@Nullable Object element) {
      return multimap.containsKey(element);
    }

    @Override
    public Iterator<K> iterator() {
      return Maps.keyIterator(multimap.entries().iterator());
    }

    @Override
    public int count(@Nullable Object element) {
      Collection<V> values = Maps.safeGet(multimap.asMap(), element);
      return (values == null) ? 0 : values.size();
    }

    @Override
    public int remove(@Nullable Object element, int occurrences) {
      checkNonnegative(occurrences, "occurrences");
      if (occurrences == 0) {
        return count(element);
      }

      Collection<V> values = Maps.safeGet(multimap.asMap(), element);

      if (values == null) {
        return 0;
      }

      int oldCount = values.size();
      if (occurrences >= oldCount) {
        values.clear();
      } else {
        Iterator<V> iterator = values.iterator();
        for (int i = 0; i < occurrences; i++) {
          iterator.next();
          iterator.remove();
        }
      }
      return oldCount;
    }

    @Override
    public void clear() {
      multimap.clear();
    }

    @Override
    public Set<K> elementSet() {
      return multimap.keySet();
    }
  }

  /**
   * A skeleton implementation of {@link Multimap#entries()}.
   */
  abstract static class Entries<K, V> extends AbstractCollection> {
    abstract Multimap<K, V> multimap();

    @Override
    public int size() {
      return multimap().size();
    }

    @Override
    public boolean contains(@Nullable Object o) {
      if (o instanceof Map.Entry) {
        Map.Entry<?, ?> entry = (Map.Entry) o;
        return multimap().containsEntry(entry.getKey(), entry.getValue());
      }
      return false;
    }

    @Override
    public boolean remove(@Nullable Object o) {
      if (o instanceof Map.Entry) {
        Map.Entry<?, ?> entry = (Map.Entry) o;
        return multimap().remove(entry.getKey(), entry.getValue());
      }
      return false;
    }

    @Override
    public void clear() {
      multimap().clear();
    }
  }

  /**
   * A skeleton implementation of {@link Multimap#asMap()}.
   */
  static final class AsMap<K, V> extends Maps.ViewCachingAbstractMap> {
    @Weak private final Multimap<K, V> multimap;

    AsMap(Multimap<K, V> multimap) {
      this.multimap = checkNotNull(multimap);
    }

    @Override
    public int size() {
      return multimap.keySet().size();
    }

    @Override
    protected Set<Entry> createEntrySet() {
      return new EntrySet();
    }

    void removeValuesForKey(Object key) {
      multimap.keySet().remove(key);
    }

    @WeakOuter
    class EntrySet extends Maps.EntrySet<K, Collection {
      @Override
      Map<K, Collection map() {
        return AsMap.this;
      }

      @Override
      public Iterator<Entry> iterator() {
        return Maps.asMapEntryIterator(
            multimap.keySet(),
            new Function<K, Collection() {
              @Override
              public Collection<V> apply(K key) {
                return multimap.get(key);
              }
            });
      }

      @Override
      public boolean remove(Object o) {
        if (!contains(o)) {
          return false;
        }
        Map.Entry<?, ?> entry = (Map.Entry) o;
        removeValuesForKey(entry.getKey());
        return true;
      }
    }

    @SuppressWarnings("unchecked")
    @Override
    public Collection<V> get(Object key) {
      return containsKey(key) ? multimap.get((K) key) : null;
    }

    @Override
    public Collection<V> remove(Object key) {
      return containsKey(key) ? multimap.removeAll(key) : null;
    }

    @Override
    public Set<K> keySet() {
      return multimap.keySet();
    }

    @Override
    public boolean isEmpty() {
      return multimap.isEmpty();
    }

    @Override
    public boolean containsKey(Object key) {
      return multimap.containsKey(key);
    }

    @Override
    public void clear() {
      multimap.clear();
    }
  }

  /**
   * Returns a multimap containing the mappings in {@code unfiltered} whose keys
   * satisfy a predicate. The returned multimap is a live view of
   * {@code unfiltered}; changes to one affect the other.
   *
   * <p>The resulting multimap's views have iterators that don't support
   * {@code remove()}, but all other methods are supported by the multimap and
   * its views. When adding a key that doesn't satisfy the predicate, the
   * multimap's {@code put()}, {@code putAll()}, and {@code replaceValues()}
   * methods throw an {@link IllegalArgumentException}.
   *
   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on
   * the filtered multimap or its views, only mappings whose keys satisfy the
   * filter will be removed from the underlying multimap.
   *
   * <p>The returned multimap isn't threadsafe or serializable, even if
   * {@code unfiltered} is.
   *
   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate
   * across every key/value mapping in the underlying multimap and determine
   * which satisfy the filter. When a live view is <i>not needed, it may be
   * faster to copy the filtered multimap and use the copy.
   *
   * <p>Warning: {@code keyPredicate} must be consistent with equals,
   * as documented at {@link Predicate#apply}. Do not provide a predicate such
   * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent
   * with equals.
   *
   * @since 11.0
   */
  public static <K, V> Multimap filterKeys(
      Multimap<K, V> unfiltered, final Predicate keyPredicate) {
    if (unfiltered instanceof SetMultimap) {
      return filterKeys((SetMultimap<K, V>) unfiltered, keyPredicate);
    } else if (unfiltered instanceof ListMultimap) {
      return filterKeys((ListMultimap<K, V>) unfiltered, keyPredicate);
    } else if (unfiltered instanceof FilteredKeyMultimap) {
      FilteredKeyMultimap<K, V> prev = (FilteredKeyMultimap) unfiltered;
      return new FilteredKeyMultimap<K, V>(
          prev.unfiltered, Predicates.<K>and(prev.keyPredicate, keyPredicate));
    } else if (unfiltered instanceof FilteredMultimap) {
      FilteredMultimap<K, V> prev = (FilteredMultimap) unfiltered;
      return filterFiltered(prev, Maps.<K>keyPredicateOnEntries(keyPredicate));
    } else {
      return new FilteredKeyMultimap<K, V>(unfiltered, keyPredicate);
    }
  }

  /**
   * Returns a multimap containing the mappings in {@code unfiltered} whose keys
   * satisfy a predicate. The returned multimap is a live view of
   * {@code unfiltered}; changes to one affect the other.
   *
   * <p>The resulting multimap's views have iterators that don't support
   * {@code remove()}, but all other methods are supported by the multimap and
   * its views. When adding a key that doesn't satisfy the predicate, the
   * multimap's {@code put()}, {@code putAll()}, and {@code replaceValues()}
   * methods throw an {@link IllegalArgumentException}.
   *
   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on
   * the filtered multimap or its views, only mappings whose keys satisfy the
   * filter will be removed from the underlying multimap.
   *
   * <p>The returned multimap isn't threadsafe or serializable, even if
   * {@code unfiltered} is.
   *
   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate
   * across every key/value mapping in the underlying multimap and determine
   * which satisfy the filter. When a live view is <i>not needed, it may be
   * faster to copy the filtered multimap and use the copy.
   *
   * <p>Warning: {@code keyPredicate} must be consistent with equals,
   * as documented at {@link Predicate#apply}. Do not provide a predicate such
   * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent
   * with equals.
   *
   * @since 14.0
   */
  public static <K, V> SetMultimap filterKeys(
      SetMultimap<K, V> unfiltered, final Predicate keyPredicate) {
    if (unfiltered instanceof FilteredKeySetMultimap) {
      FilteredKeySetMultimap<K, V> prev = (FilteredKeySetMultimap) unfiltered;
      return new FilteredKeySetMultimap<K, V>(
          prev.unfiltered(), Predicates.<K>and(prev.keyPredicate, keyPredicate));
    } else if (unfiltered instanceof FilteredSetMultimap) {
      FilteredSetMultimap<K, V> prev = (FilteredSetMultimap) unfiltered;
      return filterFiltered(prev, Maps.<K>keyPredicateOnEntries(keyPredicate));
    } else {
      return new FilteredKeySetMultimap<K, V>(unfiltered, keyPredicate);
    }
  }

  /**
   * Returns a multimap containing the mappings in {@code unfiltered} whose keys
   * satisfy a predicate. The returned multimap is a live view of
   * {@code unfiltered}; changes to one affect the other.
   *
   * <p>The resulting multimap's views have iterators that don't support
   * {@code remove()}, but all other methods are supported by the multimap and
   * its views. When adding a key that doesn't satisfy the predicate, the
   * multimap's {@code put()}, {@code putAll()}, and {@code replaceValues()}
   * methods throw an {@link IllegalArgumentException}.
   *
   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on
   * the filtered multimap or its views, only mappings whose keys satisfy the
   * filter will be removed from the underlying multimap.
   *
   * <p>The returned multimap isn't threadsafe or serializable, even if
   * {@code unfiltered} is.
   *
   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate
   * across every key/value mapping in the underlying multimap and determine
   * which satisfy the filter. When a live view is <i>not needed, it may be
   * faster to copy the filtered multimap and use the copy.
   *
   * <p>Warning: {@code keyPredicate} must be consistent with equals,
   * as documented at {@link Predicate#apply}. Do not provide a predicate such
   * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent
   * with equals.
   *
   * @since 14.0
   */
  public static <K, V> ListMultimap filterKeys(
      ListMultimap<K, V> unfiltered, final Predicate keyPredicate) {
    if (unfiltered instanceof FilteredKeyListMultimap) {
      FilteredKeyListMultimap<K, V> prev = (FilteredKeyListMultimap) unfiltered;
      return new FilteredKeyListMultimap<K, V>(
          prev.unfiltered(), Predicates.<K>and(prev.keyPredicate, keyPredicate));
    } else {
      return new FilteredKeyListMultimap<K, V>(unfiltered, keyPredicate);
    }
  }

  /**
   * Returns a multimap containing the mappings in {@code unfiltered} whose values
   * satisfy a predicate. The returned multimap is a live view of
   * {@code unfiltered}; changes to one affect the other.
   *
   * <p>The resulting multimap's views have iterators that don't support
   * {@code remove()}, but all other methods are supported by the multimap and
   * its views. When adding a value that doesn't satisfy the predicate, the
   * multimap's {@code put()}, {@code putAll()}, and {@code replaceValues()}
   * methods throw an {@link IllegalArgumentException}.
   *
   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on
   * the filtered multimap or its views, only mappings whose value satisfy the
   * filter will be removed from the underlying multimap.
   *
   * <p>The returned multimap isn't threadsafe or serializable, even if
   * {@code unfiltered} is.
   *
   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate
   * across every key/value mapping in the underlying multimap and determine
   * which satisfy the filter. When a live view is <i>not needed, it may be
   * faster to copy the filtered multimap and use the copy.
   *
   * <p>Warning: {@code valuePredicate} must be consistent with
   * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
   * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
   * inconsistent with equals.
   *
   * @since 11.0
   */
  public static <K, V> Multimap filterValues(
      Multimap<K, V> unfiltered, final Predicate valuePredicate) {
    return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
  }

  /**
   * Returns a multimap containing the mappings in {@code unfiltered} whose values
   * satisfy a predicate. The returned multimap is a live view of
   * {@code unfiltered}; changes to one affect the other.
   *
   * <p>The resulting multimap's views have iterators that don't support
   * {@code remove()}, but all other methods are supported by the multimap and
   * its views. When adding a value that doesn't satisfy the predicate, the
   * multimap's {@code put()}, {@code putAll()}, and {@code replaceValues()}
   * methods throw an {@link IllegalArgumentException}.
   *
   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on
   * the filtered multimap or its views, only mappings whose value satisfy the
   * filter will be removed from the underlying multimap.
   *
   * <p>The returned multimap isn't threadsafe or serializable, even if
   * {@code unfiltered} is.
   *
   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate
   * across every key/value mapping in the underlying multimap and determine
   * which satisfy the filter. When a live view is <i>not needed, it may be
   * faster to copy the filtered multimap and use the copy.
   *
   * <p>Warning: {@code valuePredicate} must be consistent with
   * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
   * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
   * inconsistent with equals.
   *
   * @since 14.0
   */
  public static <K, V> SetMultimap filterValues(
      SetMultimap<K, V> unfiltered, final Predicate valuePredicate) {
    return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
  }

  /**
   * Returns a multimap containing the mappings in {@code unfiltered} that
   * satisfy a predicate. The returned multimap is a live view of
   * {@code unfiltered}; changes to one affect the other.
   *
   * <p>The resulting multimap's views have iterators that don't support
   * {@code remove()}, but all other methods are supported by the multimap and
   * its views. When adding a key/value pair that doesn't satisfy the predicate,
   * multimap's {@code put()}, {@code putAll()}, and {@code replaceValues()}
   * methods throw an {@link IllegalArgumentException}.
   *
   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on
   * the filtered multimap or its views, only mappings whose keys satisfy the
   * filter will be removed from the underlying multimap.
   *
   * <p>The returned multimap isn't threadsafe or serializable, even if
   * {@code unfiltered} is.
   *
   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate
   * across every key/value mapping in the underlying multimap and determine
   * which satisfy the filter. When a live view is <i>not needed, it may be
   * faster to copy the filtered multimap and use the copy.
   *
   * <p>Warning: {@code entryPredicate} must be consistent with
   * equals</i>, as documented at {@link Predicate#apply}.
   *
   * @since 11.0
   */
  public static <K, V> Multimap filterEntries(
      Multimap<K, V> unfiltered, Predicate> entryPredicate) {
    checkNotNull(entryPredicate);
    if (unfiltered instanceof SetMultimap) {
      return filterEntries((SetMultimap<K, V>) unfiltered, entryPredicate);
    }
    return (unfiltered instanceof FilteredMultimap)
        ? filterFiltered((FilteredMultimap<K, V>) unfiltered, entryPredicate)
        : new FilteredEntryMultimap<K, V>(checkNotNull(unfiltered), entryPredicate);
  }

  /**
   * Returns a multimap containing the mappings in {@code unfiltered} that
   * satisfy a predicate. The returned multimap is a live view of
   * {@code unfiltered}; changes to one affect the other.
   *
   * <p>The resulting multimap's views have iterators that don't support
   * {@code remove()}, but all other methods are supported by the multimap and
   * its views. When adding a key/value pair that doesn't satisfy the predicate,
   * multimap's {@code put()}, {@code putAll()}, and {@code replaceValues()}
   * methods throw an {@link IllegalArgumentException}.
   *
   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on
   * the filtered multimap or its views, only mappings whose keys satisfy the
   * filter will be removed from the underlying multimap.
   *
   * <p>The returned multimap isn't threadsafe or serializable, even if
   * {@code unfiltered} is.
   *
   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate
   * across every key/value mapping in the underlying multimap and determine
   * which satisfy the filter. When a live view is <i>not needed, it may be
   * faster to copy the filtered multimap and use the copy.
   *
   * <p>Warning: {@code entryPredicate} must be consistent with
   * equals</i>, as documented at {@link Predicate#apply}.
   *
   * @since 14.0
   */
  public static <K, V> SetMultimap filterEntries(
      SetMultimap<K, V> unfiltered, Predicate> entryPredicate) {
    checkNotNull(entryPredicate);
    return (unfiltered instanceof FilteredSetMultimap)
        ? filterFiltered((FilteredSetMultimap<K, V>) unfiltered, entryPredicate)
        : new FilteredEntrySetMultimap<K, V>(checkNotNull(unfiltered), entryPredicate);
  }

  /**
   * Support removal operations when filtering a filtered multimap. Since a
   * filtered multimap has iterators that don't support remove, passing one to
   * the FilteredEntryMultimap constructor would lead to a multimap whose removal
   * operations would fail. This method combines the predicates to avoid that
   * problem.
   */
  private static <K, V> Multimap filterFiltered(
      FilteredMultimap<K, V> multimap, Predicate> entryPredicate) {
    Predicate<Entry predicate =
        Predicates.<Entryand(multimap.entryPredicate(), entryPredicate);
    return new FilteredEntryMultimap<K, V>(multimap.unfiltered(), predicate);
  }

  /**
   * Support removal operations when filtering a filtered multimap. Since a filtered multimap has
   * iterators that don't support remove, passing one to the FilteredEntryMultimap constructor would
   * lead to a multimap whose removal operations would fail. This method combines the predicates to
   * avoid that problem.
   */
  private static <K, V> SetMultimap filterFiltered(
      FilteredSetMultimap<K, V> multimap, Predicate> entryPredicate) {
    Predicate<Entry predicate =
        Predicates.<Entryand(multimap.entryPredicate(), entryPredicate);
    return new FilteredEntrySetMultimap<K, V>(multimap.unfiltered(), predicate);
  }

  static boolean equalsImpl(Multimap<?, ?> multimap, @Nullable Object object) {
    if (object == multimap) {
      return true;
    }
    if (object instanceof Multimap) {
      Multimap<?, ?> that = (Multimap) object;
      return multimap.asMap().equals(that.asMap());
    }
    return false;
  }

  // TODO(jlevy): Create methods that filter a SortedSetMultimap.
}