001/*
002 * Copyright (C) 2007 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;
023
024import java.io.Serializable;
025import java.util.Collection;
026import java.util.Comparator;
027import java.util.Iterator;
028import java.util.LinkedHashMap;
029import java.util.List;
030import java.util.Map;
031import java.util.Map.Entry;
032import java.util.Set;
033import java.util.SortedSet;
034
035import javax.annotation.Nullable;
036
037/**
038 * Factory and utilities pertaining to the {@code MapConstraint} interface.
039 *
040 * @see Constraints
041 * @author Mike Bostock
042 * @since 3.0
043 */
044@Beta
045@GwtCompatible
046public final class MapConstraints {
047  private MapConstraints() {}
048
049  /**
050   * Returns a constraint that verifies that neither the key nor the value is
051   * null. If either is null, a {@link NullPointerException} is thrown.
052   */
053  public static MapConstraint<Object, Object> notNull() {
054    return NotNullMapConstraint.INSTANCE;
055  }
056
057  // enum singleton pattern
058  private enum NotNullMapConstraint implements MapConstraint<Object, Object> {
059    INSTANCE;
060
061    @Override
062    public void checkKeyValue(Object key, Object value) {
063      checkNotNull(key);
064      checkNotNull(value);
065    }
066
067    @Override public String toString() {
068      return "Not null";
069    }
070  }
071
072  /**
073   * Returns a constrained view of the specified map, using the specified
074   * constraint. Any operations that add new mappings will call the provided
075   * constraint. However, this method does not verify that existing mappings
076   * satisfy the constraint.
077   *
078   * <p>The returned map is not serializable.
079   *
080   * @param map the map to constrain
081   * @param constraint the constraint that validates added entries
082   * @return a constrained view of the specified map
083   */
084  public static <K, V> Map<K, V> constrainedMap(
085      Map<K, V> map, MapConstraint<? super K, ? super V> constraint) {
086    return new ConstrainedMap<K, V>(map, constraint);
087  }
088
089  /**
090   * Returns a constrained view of the specified multimap, using the specified
091   * constraint. Any operations that add new mappings will call the provided
092   * constraint. However, this method does not verify that existing mappings
093   * satisfy the constraint.
094   *
095   * <p>Note that the generated multimap's {@link Multimap#removeAll} and
096   * {@link Multimap#replaceValues} methods return collections that are not
097   * constrained.
098   *
099   * <p>The returned multimap is not serializable.
100   *
101   * @param multimap the multimap to constrain
102   * @param constraint the constraint that validates added entries
103   * @return a constrained view of the multimap
104   */
105  public static <K, V> Multimap<K, V> constrainedMultimap(
106      Multimap<K, V> multimap, MapConstraint<? super K, ? super V> constraint) {
107    return new ConstrainedMultimap<K, V>(multimap, constraint);
108  }
109
110  /**
111   * Returns a constrained view of the specified list multimap, using the
112   * specified constraint. Any operations that add new mappings will call the
113   * provided constraint. However, this method does not verify that existing
114   * mappings satisfy the constraint.
115   *
116   * <p>Note that the generated multimap's {@link Multimap#removeAll} and
117   * {@link Multimap#replaceValues} methods return collections that are not
118   * constrained.
119   *
120   * <p>The returned multimap is not serializable.
121   *
122   * @param multimap the multimap to constrain
123   * @param constraint the constraint that validates added entries
124   * @return a constrained view of the specified multimap
125   */
126  public static <K, V> ListMultimap<K, V> constrainedListMultimap(
127      ListMultimap<K, V> multimap,
128      MapConstraint<? super K, ? super V> constraint) {
129    return new ConstrainedListMultimap<K, V>(multimap, constraint);
130  }
131
132  /**
133   * Returns a constrained view of the specified set multimap, using the
134   * specified constraint. Any operations that add new mappings will call the
135   * provided constraint. However, this method does not verify that existing
136   * mappings satisfy the constraint.
137   *
138   * <p>Note that the generated multimap's {@link Multimap#removeAll} and
139   * {@link Multimap#replaceValues} methods return collections that are not
140   * constrained.
141   * <p>The returned multimap is not serializable.
142   *
143   * @param multimap the multimap to constrain
144   * @param constraint the constraint that validates added entries
145   * @return a constrained view of the specified multimap
146   */
147  public static <K, V> SetMultimap<K, V> constrainedSetMultimap(
148      SetMultimap<K, V> multimap,
149      MapConstraint<? super K, ? super V> constraint) {
150    return new ConstrainedSetMultimap<K, V>(multimap, constraint);
151  }
152
153  /**
154   * Returns a constrained view of the specified sorted-set multimap, using the
155   * specified constraint. Any operations that add new mappings will call the
156   * provided constraint. However, this method does not verify that existing
157   * mappings satisfy the constraint.
158   *
159   * <p>Note that the generated multimap's {@link Multimap#removeAll} and
160   * {@link Multimap#replaceValues} methods return collections that are not
161   * constrained.
162   * <p>The returned multimap is not serializable.
163   *
164   * @param multimap the multimap to constrain
165   * @param constraint the constraint that validates added entries
166   * @return a constrained view of the specified multimap
167   */
168  public static <K, V> SortedSetMultimap<K, V> constrainedSortedSetMultimap(
169      SortedSetMultimap<K, V> multimap,
170      MapConstraint<? super K, ? super V> constraint) {
171    return new ConstrainedSortedSetMultimap<K, V>(multimap, constraint);
172  }
173
174  /**
175   * Returns a constrained view of the specified entry, using the specified
176   * constraint. The {@link Entry#setValue} operation will be verified with the
177   * constraint.
178   *
179   * @param entry the entry to constrain
180   * @param constraint the constraint for the entry
181   * @return a constrained view of the specified entry
182   */
183  private static <K, V> Entry<K, V> constrainedEntry(
184      final Entry<K, V> entry,
185      final MapConstraint<? super K, ? super V> constraint) {
186    checkNotNull(entry);
187    checkNotNull(constraint);
188    return new ForwardingMapEntry<K, V>() {
189      @Override protected Entry<K, V> delegate() {
190        return entry;
191      }
192      @Override public V setValue(V value) {
193        constraint.checkKeyValue(getKey(), value);
194        return entry.setValue(value);
195      }
196    };
197  }
198
199  /**
200   * Returns a constrained view of the specified {@code asMap} entry, using the
201   * specified constraint. The {@link Entry#setValue} operation will be verified
202   * with the constraint, and the collection returned by {@link Entry#getValue}
203   * will be similarly constrained.
204   *
205   * @param entry the {@code asMap} entry to constrain
206   * @param constraint the constraint for the entry
207   * @return a constrained view of the specified entry
208   */
209  private static <K, V> Entry<K, Collection<V>> constrainedAsMapEntry(
210      final Entry<K, Collection<V>> entry,
211      final MapConstraint<? super K, ? super V> constraint) {
212    checkNotNull(entry);
213    checkNotNull(constraint);
214    return new ForwardingMapEntry<K, Collection<V>>() {
215      @Override protected Entry<K, Collection<V>> delegate() {
216        return entry;
217      }
218      @Override public Collection<V> getValue() {
219        return Constraints.constrainedTypePreservingCollection(
220            entry.getValue(), new Constraint<V>() {
221          @Override
222          public V checkElement(V value) {
223            constraint.checkKeyValue(getKey(), value);
224            return value;
225          }
226        });
227      }
228    };
229  }
230
231  /**
232   * Returns a constrained view of the specified set of {@code asMap} entries,
233   * using the specified constraint. The {@link Entry#setValue} operation will
234   * be verified with the constraint, and the collection returned by {@link
235   * Entry#getValue} will be similarly constrained. The {@code add} and {@code
236   * addAll} operations simply forward to the underlying set, which throws an
237   * {@link UnsupportedOperationException} per the multimap specification.
238   *
239   * @param entries the entries to constrain
240   * @param constraint the constraint for the entries
241   * @return a constrained view of the entries
242   */
243  private static <K, V> Set<Entry<K, Collection<V>>> constrainedAsMapEntries(
244      Set<Entry<K, Collection<V>>> entries,
245      MapConstraint<? super K, ? super V> constraint) {
246    return new ConstrainedAsMapEntries<K, V>(entries, constraint);
247  }
248
249  /**
250   * Returns a constrained view of the specified collection (or set) of entries,
251   * using the specified constraint. The {@link Entry#setValue} operation will
252   * be verified with the constraint, along with add operations on the returned
253   * collection. The {@code add} and {@code addAll} operations simply forward to
254   * the underlying collection, which throws an {@link
255   * UnsupportedOperationException} per the map and multimap specification.
256   *
257   * @param entries the entries to constrain
258   * @param constraint the constraint for the entries
259   * @return a constrained view of the specified entries
260   */
261  private static <K, V> Collection<Entry<K, V>> constrainedEntries(
262      Collection<Entry<K, V>> entries,
263      MapConstraint<? super K, ? super V> constraint) {
264    if (entries instanceof Set) {
265      return constrainedEntrySet((Set<Entry<K, V>>) entries, constraint);
266    }
267    return new ConstrainedEntries<K, V>(entries, constraint);
268  }
269
270  /**
271   * Returns a constrained view of the specified set of entries, using the
272   * specified constraint. The {@link Entry#setValue} operation will be verified
273   * with the constraint, along with add operations on the returned set. The
274   * {@code add} and {@code addAll} operations simply forward to the underlying
275   * set, which throws an {@link UnsupportedOperationException} per the map and
276   * multimap specification.
277   *
278   * <p>The returned multimap is not serializable.
279   *
280   * @param entries the entries to constrain
281   * @param constraint the constraint for the entries
282   * @return a constrained view of the specified entries
283   */
284  private static <K, V> Set<Entry<K, V>> constrainedEntrySet(
285      Set<Entry<K, V>> entries,
286      MapConstraint<? super K, ? super V> constraint) {
287    return new ConstrainedEntrySet<K, V>(entries, constraint);
288  }
289
290  /** @see MapConstraints#constrainedMap */
291  static class ConstrainedMap<K, V> extends ForwardingMap<K, V> {
292    private final Map<K, V> delegate;
293    final MapConstraint<? super K, ? super V> constraint;
294    private transient Set<Entry<K, V>> entrySet;
295
296    ConstrainedMap(
297        Map<K, V> delegate, MapConstraint<? super K, ? super V> constraint) {
298      this.delegate = checkNotNull(delegate);
299      this.constraint = checkNotNull(constraint);
300    }
301    @Override protected Map<K, V> delegate() {
302      return delegate;
303    }
304    @Override public Set<Entry<K, V>> entrySet() {
305      Set<Entry<K, V>> result = entrySet;
306      if (result == null) {
307        entrySet = result =
308            constrainedEntrySet(delegate.entrySet(), constraint);
309      }
310      return result;
311    }
312    @Override public V put(K key, V value) {
313      constraint.checkKeyValue(key, value);
314      return delegate.put(key, value);
315    }
316    @Override public void putAll(Map<? extends K, ? extends V> map) {
317      delegate.putAll(checkMap(map, constraint));
318    }
319  }
320
321  /**
322   * Returns a constrained view of the specified bimap, using the specified
323   * constraint. Any operations that modify the bimap will have the associated
324   * keys and values verified with the constraint.
325   *
326   * <p>The returned bimap is not serializable.
327   *
328   * @param map the bimap to constrain
329   * @param constraint the constraint that validates added entries
330   * @return a constrained view of the specified bimap
331   */
332  public static <K, V> BiMap<K, V> constrainedBiMap(
333      BiMap<K, V> map, MapConstraint<? super K, ? super V> constraint) {
334    return new ConstrainedBiMap<K, V>(map, null, constraint);
335  }
336
337  /** @see MapConstraints#constrainedBiMap */
338  private static class ConstrainedBiMap<K, V> extends ConstrainedMap<K, V>
339      implements BiMap<K, V> {
340    /*
341     * We could switch to racy single-check lazy init and remove volatile, but
342     * there's a downside. That's because this field is also written in the
343     * constructor. Without volatile, the constructor's write of the existing
344     * inverse BiMap could occur after inverse()'s read of the field's initial
345     * null value, leading inverse() to overwrite the existing inverse with a
346     * doubly indirect version. This wouldn't be catastrophic, but it's
347     * something to keep in mind if we make the change.
348     *
349     * Note that UnmodifiableBiMap *does* use racy single-check lazy init.
350     * TODO(cpovirk): pick one and standardize
351     */
352    volatile BiMap<V, K> inverse;
353
354    ConstrainedBiMap(BiMap<K, V> delegate, @Nullable BiMap<V, K> inverse,
355        MapConstraint<? super K, ? super V> constraint) {
356      super(delegate, constraint);
357      this.inverse = inverse;
358    }
359
360    @Override protected BiMap<K, V> delegate() {
361      return (BiMap<K, V>) super.delegate();
362    }
363
364    @Override
365    public V forcePut(K key, V value) {
366      constraint.checkKeyValue(key, value);
367      return delegate().forcePut(key, value);
368    }
369
370    @Override
371    public BiMap<V, K> inverse() {
372      if (inverse == null) {
373        inverse = new ConstrainedBiMap<V, K>(delegate().inverse(), this,
374            new InverseConstraint<V, K>(constraint));
375      }
376      return inverse;
377    }
378
379    @Override public Set<V> values() {
380      return delegate().values();
381    }
382  }
383
384  /** @see MapConstraints#constrainedBiMap */
385  private static class InverseConstraint<K, V> implements MapConstraint<K, V> {
386    final MapConstraint<? super V, ? super K> constraint;
387
388    public InverseConstraint(MapConstraint<? super V, ? super K> constraint) {
389      this.constraint = checkNotNull(constraint);
390    }
391    @Override
392    public void checkKeyValue(K key, V value) {
393      constraint.checkKeyValue(value, key);
394    }
395  }
396
397  /** @see MapConstraints#constrainedMultimap */
398  private static class ConstrainedMultimap<K, V>
399      extends ForwardingMultimap<K, V> implements Serializable {
400    final MapConstraint<? super K, ? super V> constraint;
401    final Multimap<K, V> delegate;
402    transient Collection<Entry<K, V>> entries;
403    transient Map<K, Collection<V>> asMap;
404
405    public ConstrainedMultimap(Multimap<K, V> delegate,
406        MapConstraint<? super K, ? super V> constraint) {
407      this.delegate = checkNotNull(delegate);
408      this.constraint = checkNotNull(constraint);
409    }
410
411    @Override protected Multimap<K, V> delegate() {
412      return delegate;
413    }
414
415    @Override public Map<K, Collection<V>> asMap() {
416      Map<K, Collection<V>> result = asMap;
417      if (result == null) {
418        final Map<K, Collection<V>> asMapDelegate = delegate.asMap();
419
420        asMap = result = new ForwardingMap<K, Collection<V>>() {
421          Set<Entry<K, Collection<V>>> entrySet;
422          Collection<Collection<V>> values;
423
424          @Override protected Map<K, Collection<V>> delegate() {
425            return asMapDelegate;
426          }
427
428          @Override public Set<Entry<K, Collection<V>>> entrySet() {
429            Set<Entry<K, Collection<V>>> result = entrySet;
430            if (result == null) {
431              entrySet = result = constrainedAsMapEntries(
432                  asMapDelegate.entrySet(), constraint);
433            }
434            return result;
435          }
436
437          @SuppressWarnings("unchecked")
438          @Override public Collection<V> get(Object key) {
439            try {
440              Collection<V> collection = ConstrainedMultimap.this.get((K) key);
441              return collection.isEmpty() ? null : collection;
442            } catch (ClassCastException e) {
443              return null; // key wasn't a K
444            }
445          }
446
447          @Override public Collection<Collection<V>> values() {
448            Collection<Collection<V>> result = values;
449            if (result == null) {
450              values = result = new ConstrainedAsMapValues<K, V>(
451                  delegate().values(), entrySet());
452            }
453            return result;
454          }
455
456          @Override public boolean containsValue(Object o) {
457            return values().contains(o);
458          }
459        };
460      }
461      return result;
462    }
463
464    @Override public Collection<Entry<K, V>> entries() {
465      Collection<Entry<K, V>> result = entries;
466      if (result == null) {
467        entries = result = constrainedEntries(delegate.entries(), constraint);
468      }
469      return result;
470    }
471
472    @Override public Collection<V> get(final K key) {
473      return Constraints.constrainedTypePreservingCollection(
474          delegate.get(key), new Constraint<V>() {
475        @Override
476        public V checkElement(V value) {
477          constraint.checkKeyValue(key, value);
478          return value;
479        }
480      });
481    }
482
483    @Override public boolean put(K key, V value) {
484      constraint.checkKeyValue(key, value);
485      return delegate.put(key, value);
486    }
487
488    @Override public boolean putAll(K key, Iterable<? extends V> values) {
489      return delegate.putAll(key, checkValues(key, values, constraint));
490    }
491
492    @Override public boolean putAll(
493        Multimap<? extends K, ? extends V> multimap) {
494      boolean changed = false;
495      for (Entry<? extends K, ? extends V> entry : multimap.entries()) {
496        changed |= put(entry.getKey(), entry.getValue());
497      }
498      return changed;
499    }
500
501    @Override public Collection<V> replaceValues(
502        K key, Iterable<? extends V> values) {
503      return delegate.replaceValues(key, checkValues(key, values, constraint));
504    }
505  }
506
507  /** @see ConstrainedMultimap#asMap */
508  private static class ConstrainedAsMapValues<K, V>
509      extends ForwardingCollection<Collection<V>> {
510    final Collection<Collection<V>> delegate;
511    final Set<Entry<K, Collection<V>>> entrySet;
512
513    /**
514     * @param entrySet map entries, linking each key with its corresponding
515     *     values, that already enforce the constraint
516     */
517    ConstrainedAsMapValues(Collection<Collection<V>> delegate,
518        Set<Entry<K, Collection<V>>> entrySet) {
519      this.delegate = delegate;
520      this.entrySet = entrySet;
521    }
522    @Override protected Collection<Collection<V>> delegate() {
523      return delegate;
524    }
525
526    @Override public Iterator<Collection<V>> iterator() {
527      final Iterator<Entry<K, Collection<V>>> iterator = entrySet.iterator();
528      return new Iterator<Collection<V>>() {
529        @Override
530        public boolean hasNext() {
531          return iterator.hasNext();
532        }
533        @Override
534        public Collection<V> next() {
535          return iterator.next().getValue();
536        }
537        @Override
538        public void remove() {
539          iterator.remove();
540        }
541      };
542    }
543
544    @Override public Object[] toArray() {
545      return standardToArray();
546    }
547    @Override public <T> T[] toArray(T[] array) {
548      return standardToArray(array);
549    }
550    @Override public boolean contains(Object o) {
551      return standardContains(o);
552    }
553    @Override public boolean containsAll(Collection<?> c) {
554      return standardContainsAll(c);
555    }
556    @Override public boolean remove(Object o) {
557      return standardRemove(o);
558    }
559    @Override public boolean removeAll(Collection<?> c) {
560      return standardRemoveAll(c);
561    }
562    @Override public boolean retainAll(Collection<?> c) {
563      return standardRetainAll(c);
564    }
565  }
566
567  /** @see MapConstraints#constrainedEntries */
568  private static class ConstrainedEntries<K, V>
569      extends ForwardingCollection<Entry<K, V>> {
570    final MapConstraint<? super K, ? super V> constraint;
571    final Collection<Entry<K, V>> entries;
572
573    ConstrainedEntries(Collection<Entry<K, V>> entries,
574        MapConstraint<? super K, ? super V> constraint) {
575      this.entries = entries;
576      this.constraint = constraint;
577    }
578    @Override protected Collection<Entry<K, V>> delegate() {
579      return entries;
580    }
581
582    @Override public Iterator<Entry<K, V>> iterator() {
583      final Iterator<Entry<K, V>> iterator = entries.iterator();
584      return new ForwardingIterator<Entry<K, V>>() {
585        @Override public Entry<K, V> next() {
586          return constrainedEntry(iterator.next(), constraint);
587        }
588        @Override protected Iterator<Entry<K, V>> delegate() {
589          return iterator;
590        }
591      };
592    }
593
594    // See Collections.CheckedMap.CheckedEntrySet for details on attacks.
595
596    @Override public Object[] toArray() {
597      return standardToArray();
598    }
599    @Override public <T> T[] toArray(T[] array) {
600      return standardToArray(array);
601    }
602    @Override public boolean contains(Object o) {
603      return Maps.containsEntryImpl(delegate(), o);
604    }
605    @Override public boolean containsAll(Collection<?> c) {
606      return standardContainsAll(c);
607    }
608    @Override public boolean remove(Object o) {
609      return Maps.removeEntryImpl(delegate(), o);
610    }
611    @Override public boolean removeAll(Collection<?> c) {
612      return standardRemoveAll(c);
613    }
614    @Override public boolean retainAll(Collection<?> c) {
615      return standardRetainAll(c);
616    }
617  }
618
619  /** @see MapConstraints#constrainedEntrySet */
620  static class ConstrainedEntrySet<K, V>
621      extends ConstrainedEntries<K, V> implements Set<Entry<K, V>> {
622    ConstrainedEntrySet(Set<Entry<K, V>> entries,
623        MapConstraint<? super K, ? super V> constraint) {
624      super(entries, constraint);
625    }
626
627    // See Collections.CheckedMap.CheckedEntrySet for details on attacks.
628
629    @Override public boolean equals(@Nullable Object object) {
630      return Sets.equalsImpl(this, object);
631    }
632
633    @Override public int hashCode() {
634      return Sets.hashCodeImpl(this);
635    }
636  }
637
638  /** @see MapConstraints#constrainedAsMapEntries */
639  static class ConstrainedAsMapEntries<K, V>
640      extends ForwardingSet<Entry<K, Collection<V>>> {
641    private final MapConstraint<? super K, ? super V> constraint;
642    private final Set<Entry<K, Collection<V>>> entries;
643
644    ConstrainedAsMapEntries(Set<Entry<K, Collection<V>>> entries,
645        MapConstraint<? super K, ? super V> constraint) {
646      this.entries = entries;
647      this.constraint = constraint;
648    }
649
650    @Override protected Set<Entry<K, Collection<V>>> delegate() {
651      return entries;
652    }
653
654    @Override public Iterator<Entry<K, Collection<V>>> iterator() {
655      final Iterator<Entry<K, Collection<V>>> iterator = entries.iterator();
656      return new ForwardingIterator<Entry<K, Collection<V>>>() {
657        @Override public Entry<K, Collection<V>> next() {
658          return constrainedAsMapEntry(iterator.next(), constraint);
659        }
660        @Override protected Iterator<Entry<K, Collection<V>>> delegate() {
661          return iterator;
662        }
663      };
664    }
665
666    // See Collections.CheckedMap.CheckedEntrySet for details on attacks.
667
668    @Override public Object[] toArray() {
669      return standardToArray();
670    }
671
672    @Override public <T> T[] toArray(T[] array) {
673      return standardToArray(array);
674    }
675
676    @Override public boolean contains(Object o) {
677      return Maps.containsEntryImpl(delegate(), o);
678    }
679
680    @Override public boolean containsAll(Collection<?> c) {
681      return standardContainsAll(c);
682    }
683
684    @Override public boolean equals(@Nullable Object object) {
685      return standardEquals(object);
686    }
687
688    @Override public int hashCode() {
689      return standardHashCode();
690    }
691
692    @Override public boolean remove(Object o) {
693      return Maps.removeEntryImpl(delegate(), o);
694    }
695
696    @Override public boolean removeAll(Collection<?> c) {
697      return standardRemoveAll(c);
698    }
699
700    @Override public boolean retainAll(Collection<?> c) {
701      return standardRetainAll(c);
702    }
703  }
704
705  private static class ConstrainedListMultimap<K, V>
706      extends ConstrainedMultimap<K, V> implements ListMultimap<K, V> {
707    ConstrainedListMultimap(ListMultimap<K, V> delegate,
708        MapConstraint<? super K, ? super V> constraint) {
709      super(delegate, constraint);
710    }
711    @Override public List<V> get(K key) {
712      return (List<V>) super.get(key);
713    }
714    @Override public List<V> removeAll(Object key) {
715      return (List<V>) super.removeAll(key);
716    }
717    @Override public List<V> replaceValues(
718        K key, Iterable<? extends V> values) {
719      return (List<V>) super.replaceValues(key, values);
720    }
721  }
722
723  private static class ConstrainedSetMultimap<K, V>
724      extends ConstrainedMultimap<K, V> implements SetMultimap<K, V> {
725    ConstrainedSetMultimap(SetMultimap<K, V> delegate,
726        MapConstraint<? super K, ? super V> constraint) {
727      super(delegate, constraint);
728    }
729    @Override public Set<V> get(K key) {
730      return (Set<V>) super.get(key);
731    }
732    @Override public Set<Map.Entry<K, V>> entries() {
733      return (Set<Map.Entry<K, V>>) super.entries();
734    }
735    @Override public Set<V> removeAll(Object key) {
736      return (Set<V>) super.removeAll(key);
737    }
738    @Override public Set<V> replaceValues(
739        K key, Iterable<? extends V> values) {
740      return (Set<V>) super.replaceValues(key, values);
741    }
742  }
743
744  private static class ConstrainedSortedSetMultimap<K, V>
745      extends ConstrainedSetMultimap<K, V> implements SortedSetMultimap<K, V> {
746    ConstrainedSortedSetMultimap(SortedSetMultimap<K, V> delegate,
747        MapConstraint<? super K, ? super V> constraint) {
748      super(delegate, constraint);
749    }
750    @Override public SortedSet<V> get(K key) {
751      return (SortedSet<V>) super.get(key);
752    }
753    @Override public SortedSet<V> removeAll(Object key) {
754      return (SortedSet<V>) super.removeAll(key);
755    }
756    @Override public SortedSet<V> replaceValues(
757        K key, Iterable<? extends V> values) {
758      return (SortedSet<V>) super.replaceValues(key, values);
759    }
760    @Override
761    public Comparator<? super V> valueComparator() {
762      return ((SortedSetMultimap<K, V>) delegate()).valueComparator();
763    }
764  }
765
766  private static <K, V> Collection<V> checkValues(K key,
767      Iterable<? extends V> values,
768      MapConstraint<? super K, ? super V> constraint) {
769    Collection<V> copy = Lists.newArrayList(values);
770    for (V value : copy) {
771      constraint.checkKeyValue(key, value);
772    }
773    return copy;
774  }
775
776  private static <K, V> Map<K, V> checkMap(Map<? extends K, ? extends V> map,
777      MapConstraint<? super K, ? super V> constraint) {
778    Map<K, V> copy = new LinkedHashMap<K, V>(map);
779    for (Entry<K, V> entry : copy.entrySet()) {
780      constraint.checkKeyValue(entry.getKey(), entry.getValue());
781    }
782    return copy;
783  }
784}