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