1/* 2 * Copyright (C) 2007 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.google.common.collect; 18 19import static com.google.common.base.Preconditions.checkNotNull; 20 21import com.google.common.annotations.GwtCompatible; 22 23import java.util.Collection; 24import java.util.Comparator; 25import java.util.SortedMap; 26import java.util.SortedSet; 27import java.util.TreeMap; 28import java.util.TreeSet; 29 30/** 31 * Implementation of {@code Multimap} whose keys and values are ordered by 32 * their natural ordering or by supplied comparators. In all cases, this 33 * implementation uses {@link Comparable#compareTo} or {@link 34 * Comparator#compare} instead of {@link Object#equals} to determine 35 * equivalence of instances. 36 * 37 * <p><b>Warning:</b> The comparators or comparables used must be <i>consistent 38 * with equals</i> as explained by the {@link Comparable} class specification. 39 * Otherwise, the resulting multiset will violate the general contract of {@link 40 * SetMultimap}, which it is specified in terms of {@link Object#equals}. 41 * 42 * <p>The collections returned by {@code keySet} and {@code asMap} iterate 43 * through the keys according to the key comparator ordering or the natural 44 * ordering of the keys. Similarly, {@code get}, {@code removeAll}, and {@code 45 * replaceValues} return collections that iterate through the values according 46 * to the value comparator ordering or the natural ordering of the values. The 47 * collections generated by {@code entries}, {@code keys}, and {@code values} 48 * iterate across the keys according to the above key ordering, and for each 49 * key they iterate across the values according to the value ordering. 50 * 51 * <p>The multimap does not store duplicate key-value pairs. Adding a new 52 * key-value pair equal to an existing key-value pair has no effect. 53 * 54 * <p>Null keys and values are permitted (provided, of course, that the 55 * respective comparators support them). All optional multimap methods are 56 * supported, and all returned views are modifiable. 57 * 58 * <p>This class is not threadsafe when any concurrent operations update the 59 * multimap. Concurrent read operations will work correctly. To allow concurrent 60 * update operations, wrap your multimap with a call to {@link 61 * Multimaps#synchronizedSortedSetMultimap}. 62 * 63 * @author Jared Levy 64 * @since 2.0 (imported from Google Collections Library) 65 */ 66@GwtCompatible(serializable = true, emulated = true) 67public class TreeMultimap<K, V> extends AbstractSortedSetMultimap<K, V> { 68 private transient Comparator<? super K> keyComparator; 69 private transient Comparator<? super V> valueComparator; 70 71 /** 72 * Creates an empty {@code TreeMultimap} ordered by the natural ordering of 73 * its keys and values. 74 */ 75 public static <K extends Comparable, V extends Comparable> 76 TreeMultimap<K, V> create() { 77 return new TreeMultimap<K, V>(Ordering.natural(), Ordering.natural()); 78 } 79 80 /** 81 * Creates an empty {@code TreeMultimap} instance using explicit comparators. 82 * Neither comparator may be null; use {@link Ordering#natural()} to specify 83 * natural order. 84 * 85 * @param keyComparator the comparator that determines the key ordering 86 * @param valueComparator the comparator that determines the value ordering 87 */ 88 public static <K, V> TreeMultimap<K, V> create( 89 Comparator<? super K> keyComparator, 90 Comparator<? super V> valueComparator) { 91 return new TreeMultimap<K, V>(checkNotNull(keyComparator), 92 checkNotNull(valueComparator)); 93 } 94 95 /** 96 * Constructs a {@code TreeMultimap}, ordered by the natural ordering of its 97 * keys and values, with the same mappings as the specified multimap. 98 * 99 * @param multimap the multimap whose contents are copied to this multimap 100 */ 101 public static <K extends Comparable, V extends Comparable> 102 TreeMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) { 103 return new TreeMultimap<K, V>(Ordering.natural(), Ordering.natural(), 104 multimap); 105 } 106 107 TreeMultimap(Comparator<? super K> keyComparator, 108 Comparator<? super V> valueComparator) { 109 super(new TreeMap<K, Collection<V>>(keyComparator)); 110 this.keyComparator = keyComparator; 111 this.valueComparator = valueComparator; 112 } 113 114 private TreeMultimap(Comparator<? super K> keyComparator, 115 Comparator<? super V> valueComparator, 116 Multimap<? extends K, ? extends V> multimap) { 117 this(keyComparator, valueComparator); 118 putAll(multimap); 119 } 120 121 /** 122 * {@inheritDoc} 123 * 124 * <p>Creates an empty {@code TreeSet} for a collection of values for one key. 125 * 126 * @return a new {@code TreeSet} containing a collection of values for one 127 * key 128 */ 129 @Override SortedSet<V> createCollection() { 130 return new TreeSet<V>(valueComparator); 131 } 132 133 /** 134 * Returns the comparator that orders the multimap keys. 135 */ 136 public Comparator<? super K> keyComparator() { 137 return keyComparator; 138 } 139 140 @Override 141 public Comparator<? super V> valueComparator() { 142 return valueComparator; 143 } 144 145 /** 146 * {@inheritDoc} 147 * 148 * <p>Because a {@code TreeMultimap} has unique sorted keys, this method 149 * returns a {@link SortedSet}, instead of the {@link java.util.Set} specified 150 * in the {@link Multimap} interface. 151 */ 152 @Override public SortedSet<K> keySet() { 153 return (SortedSet<K>) super.keySet(); 154 } 155 156 /** 157 * {@inheritDoc} 158 * 159 * <p>Because a {@code TreeMultimap} has unique sorted keys, this method 160 * returns a {@link SortedMap}, instead of the {@link java.util.Map} specified 161 * in the {@link Multimap} interface. 162 */ 163 @Override public SortedMap<K, Collection<V>> asMap() { 164 return (SortedMap<K, Collection<V>>) super.asMap(); 165 } 166} 167 168