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; 22import com.google.common.annotations.GwtIncompatible; 23 24import java.io.IOException; 25import java.io.ObjectInputStream; 26import java.io.ObjectOutputStream; 27import java.util.Collection; 28import java.util.Comparator; 29import java.util.SortedMap; 30import java.util.SortedSet; 31import java.util.TreeMap; 32import java.util.TreeSet; 33 34/** 35 * Implementation of {@code Multimap} whose keys and values are ordered by 36 * their natural ordering or by supplied comparators. In all cases, this 37 * implementation uses {@link Comparable#compareTo} or {@link 38 * Comparator#compare} instead of {@link Object#equals} to determine 39 * equivalence of instances. 40 * 41 * <p><b>Warning:</b> The comparators or comparables used must be <i>consistent 42 * with equals</i> as explained by the {@link Comparable} class specification. 43 * Otherwise, the resulting multiset will violate the general contract of {@link 44 * SetMultimap}, which it is specified in terms of {@link Object#equals}. 45 * 46 * <p>The collections returned by {@code keySet} and {@code asMap} iterate 47 * through the keys according to the key comparator ordering or the natural 48 * ordering of the keys. Similarly, {@code get}, {@code removeAll}, and {@code 49 * replaceValues} return collections that iterate through the values according 50 * to the value comparator ordering or the natural ordering of the values. The 51 * collections generated by {@code entries}, {@code keys}, and {@code values} 52 * iterate across the keys according to the above key ordering, and for each 53 * key they iterate across the values according to the value ordering. 54 * 55 * <p>The multimap does not store duplicate key-value pairs. Adding a new 56 * key-value pair equal to an existing key-value pair has no effect. 57 * 58 * <p>Null keys and values are permitted (provided, of course, that the 59 * respective comparators support them). All optional multimap methods are 60 * supported, and all returned views are modifiable. 61 * 62 * <p>This class is not threadsafe when any concurrent operations update the 63 * multimap. Concurrent read operations will work correctly. To allow concurrent 64 * update operations, wrap your multimap with a call to {@link 65 * Multimaps#synchronizedSortedSetMultimap}. 66 * 67 * @author Jared Levy 68 * @since 2.0 (imported from Google Collections Library) 69 */ 70@GwtCompatible(serializable = true, emulated = true) 71public class TreeMultimap<K, V> extends AbstractSortedSetMultimap<K, V> { 72 private transient Comparator<? super K> keyComparator; 73 private transient Comparator<? super V> valueComparator; 74 75 /** 76 * Creates an empty {@code TreeMultimap} ordered by the natural ordering of 77 * its keys and values. 78 */ 79 public static <K extends Comparable, V extends Comparable> 80 TreeMultimap<K, V> create() { 81 return new TreeMultimap<K, V>(Ordering.natural(), Ordering.natural()); 82 } 83 84 /** 85 * Creates an empty {@code TreeMultimap} instance using explicit comparators. 86 * Neither comparator may be null; use {@link Ordering#natural()} to specify 87 * natural order. 88 * 89 * @param keyComparator the comparator that determines the key ordering 90 * @param valueComparator the comparator that determines the value ordering 91 */ 92 public static <K, V> TreeMultimap<K, V> create( 93 Comparator<? super K> keyComparator, 94 Comparator<? super V> valueComparator) { 95 return new TreeMultimap<K, V>(checkNotNull(keyComparator), 96 checkNotNull(valueComparator)); 97 } 98 99 /** 100 * Constructs a {@code TreeMultimap}, ordered by the natural ordering of its 101 * keys and values, with the same mappings as the specified multimap. 102 * 103 * @param multimap the multimap whose contents are copied to this multimap 104 */ 105 public static <K extends Comparable, V extends Comparable> 106 TreeMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) { 107 return new TreeMultimap<K, V>(Ordering.natural(), Ordering.natural(), 108 multimap); 109 } 110 111 TreeMultimap(Comparator<? super K> keyComparator, 112 Comparator<? super V> valueComparator) { 113 super(new TreeMap<K, Collection<V>>(keyComparator)); 114 this.keyComparator = keyComparator; 115 this.valueComparator = valueComparator; 116 } 117 118 private TreeMultimap(Comparator<? super K> keyComparator, 119 Comparator<? super V> valueComparator, 120 Multimap<? extends K, ? extends V> multimap) { 121 this(keyComparator, valueComparator); 122 putAll(multimap); 123 } 124 125 /** 126 * {@inheritDoc} 127 * 128 * <p>Creates an empty {@code TreeSet} for a collection of values for one key. 129 * 130 * @return a new {@code TreeSet} containing a collection of values for one 131 * key 132 */ 133 @Override SortedSet<V> createCollection() { 134 return new TreeSet<V>(valueComparator); 135 } 136 137 /** 138 * Returns the comparator that orders the multimap keys. 139 */ 140 public Comparator<? super K> keyComparator() { 141 return keyComparator; 142 } 143 144 @Override 145 public Comparator<? super V> valueComparator() { 146 return valueComparator; 147 } 148 149 /** 150 * {@inheritDoc} 151 * 152 * <p>Because a {@code TreeMultimap} has unique sorted keys, this method 153 * returns a {@link SortedSet}, instead of the {@link java.util.Set} specified 154 * in the {@link Multimap} interface. 155 */ 156 @Override public SortedSet<K> keySet() { 157 return (SortedSet<K>) super.keySet(); 158 } 159 160 /** 161 * {@inheritDoc} 162 * 163 * <p>Because a {@code TreeMultimap} has unique sorted keys, this method 164 * returns a {@link SortedMap}, instead of the {@link java.util.Map} specified 165 * in the {@link Multimap} interface. 166 */ 167 @Override public SortedMap<K, Collection<V>> asMap() { 168 return (SortedMap<K, Collection<V>>) super.asMap(); 169 } 170 171 /** 172 * @serialData key comparator, value comparator, number of distinct keys, and 173 * then for each distinct key: the key, number of values for that key, and 174 * key values 175 */ 176 @GwtIncompatible("java.io.ObjectOutputStream") 177 private void writeObject(ObjectOutputStream stream) throws IOException { 178 stream.defaultWriteObject(); 179 stream.writeObject(keyComparator()); 180 stream.writeObject(valueComparator()); 181 Serialization.writeMultimap(this, stream); 182 } 183 184 @GwtIncompatible("java.io.ObjectInputStream") 185 @SuppressWarnings("unchecked") // reading data stored by writeObject 186 private void readObject(ObjectInputStream stream) 187 throws IOException, ClassNotFoundException { 188 stream.defaultReadObject(); 189 keyComparator = checkNotNull((Comparator<? super K>) stream.readObject()); 190 valueComparator = checkNotNull((Comparator<? super V>) stream.readObject()); 191 setMap(new TreeMap<K, Collection<V>>(keyComparator)); 192 Serialization.populateMultimap(this, stream); 193 } 194 195 @GwtIncompatible("not needed in emulated source") 196 private static final long serialVersionUID = 0; 197} 198