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.GwtCompatible; 022import com.google.common.annotations.GwtIncompatible; 023import java.io.IOException; 024import java.io.ObjectInputStream; 025import java.io.ObjectOutputStream; 026import java.util.Collection; 027import java.util.Comparator; 028import java.util.NavigableMap; 029import java.util.NavigableSet; 030import java.util.SortedSet; 031import java.util.TreeMap; 032import java.util.TreeSet; 033import org.checkerframework.checker.nullness.compatqual.NullableDecl; 034 035/** 036 * Implementation of {@code Multimap} whose keys and values are ordered by their natural ordering or 037 * by supplied comparators. In all cases, this implementation uses {@link Comparable#compareTo} or 038 * {@link Comparator#compare} instead of {@link Object#equals} to determine equivalence of 039 * instances. 040 * 041 * <p><b>Warning:</b> The comparators or comparables used must be <i>consistent with equals</i> as 042 * explained by the {@link Comparable} class specification. Otherwise, the resulting multiset will 043 * violate the general contract of {@link SetMultimap}, which it is specified in terms of {@link 044 * Object#equals}. 045 * 046 * <p>The collections returned by {@code keySet} and {@code asMap} iterate through the keys 047 * according to the key comparator ordering or the natural ordering of the keys. Similarly, {@code 048 * get}, {@code removeAll}, and {@code replaceValues} return collections that iterate through the 049 * values according to the value comparator ordering or the natural ordering of the values. The 050 * collections generated by {@code entries}, {@code keys}, and {@code values} iterate across the 051 * keys according to the above key ordering, and for each key they iterate across the values 052 * according to the value ordering. 053 * 054 * <p>The multimap does not store duplicate key-value pairs. Adding a new key-value pair equal to an 055 * existing key-value pair has no effect. 056 * 057 * <p>Null keys and values are permitted (provided, of course, that the respective comparators 058 * support them). All optional multimap methods are supported, and all returned views are 059 * modifiable. 060 * 061 * <p>This class is not threadsafe when any concurrent operations update the multimap. Concurrent 062 * read operations will work correctly. To allow concurrent update operations, wrap your multimap 063 * with a call to {@link Multimaps#synchronizedSortedSetMultimap}. 064 * 065 * <p>See the Guava User Guide article on <a href= 066 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap"> {@code 067 * Multimap}</a>. 068 * 069 * @author Jared Levy 070 * @author Louis Wasserman 071 * @since 2.0 072 */ 073@GwtCompatible(serializable = true, emulated = true) 074public class TreeMultimap<K, V> extends AbstractSortedKeySortedSetMultimap<K, V> { 075 private transient Comparator<? super K> keyComparator; 076 private transient Comparator<? super V> valueComparator; 077 078 /** 079 * Creates an empty {@code TreeMultimap} ordered by the natural ordering of its keys and values. 080 */ 081 public static <K extends Comparable, V extends Comparable> TreeMultimap<K, V> create() { 082 return new TreeMultimap<>(Ordering.natural(), Ordering.natural()); 083 } 084 085 /** 086 * Creates an empty {@code TreeMultimap} instance using explicit comparators. Neither comparator 087 * may be null; use {@link Ordering#natural()} to specify natural order. 088 * 089 * @param keyComparator the comparator that determines the key ordering 090 * @param valueComparator the comparator that determines the value ordering 091 */ 092 public static <K, V> TreeMultimap<K, V> create( 093 Comparator<? super K> keyComparator, Comparator<? super V> valueComparator) { 094 return new TreeMultimap<>(checkNotNull(keyComparator), checkNotNull(valueComparator)); 095 } 096 097 /** 098 * Constructs a {@code TreeMultimap}, ordered by the natural ordering of its keys and values, with 099 * the same mappings as the specified multimap. 100 * 101 * @param multimap the multimap whose contents are copied to this multimap 102 */ 103 public static <K extends Comparable, V extends Comparable> TreeMultimap<K, V> create( 104 Multimap<? extends K, ? extends V> multimap) { 105 return new TreeMultimap<>(Ordering.natural(), Ordering.natural(), multimap); 106 } 107 108 TreeMultimap(Comparator<? super K> keyComparator, 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( 115 Comparator<? super K> keyComparator, 116 Comparator<? super V> valueComparator, 117 Multimap<? extends K, ? extends V> multimap) { 118 this(keyComparator, valueComparator); 119 putAll(multimap); 120 } 121 122 /** 123 * {@inheritDoc} 124 * 125 * <p>Creates an empty {@code TreeSet} for a collection of values for one key. 126 * 127 * @return a new {@code TreeSet} containing a collection of values for one key 128 */ 129 @Override 130 SortedSet<V> createCollection() { 131 return new TreeSet<V>(valueComparator); 132 } 133 134 @Override 135 Collection<V> createCollection(@NullableDecl K key) { 136 if (key == null) { 137 keyComparator().compare(key, key); 138 } 139 return super.createCollection(key); 140 } 141 142 /** 143 * Returns the comparator that orders the multimap keys. 144 * 145 * @deprecated Use {@code ((NavigableSet<K>) multimap.keySet()).comparator()} instead. 146 */ 147 @Deprecated 148 public Comparator<? super K> keyComparator() { 149 return keyComparator; 150 } 151 152 @Override 153 public Comparator<? super V> valueComparator() { 154 return valueComparator; 155 } 156 157 /** @since 14.0 (present with return type {@code SortedSet} since 2.0) */ 158 @Override 159 @GwtIncompatible // NavigableSet 160 public NavigableSet<V> get(@NullableDecl K key) { 161 return (NavigableSet<V>) super.get(key); 162 } 163 164 /** 165 * {@inheritDoc} 166 * 167 * <p>Because a {@code TreeMultimap} has unique sorted keys, this method returns a {@link 168 * NavigableSet}, instead of the {@link java.util.Set} specified in the {@link Multimap} 169 * interface. 170 * 171 * @since 14.0 (present with return type {@code SortedSet} since 2.0) 172 */ 173 @Override 174 public NavigableSet<K> keySet() { 175 return (NavigableSet<K>) super.keySet(); 176 } 177 178 /** 179 * {@inheritDoc} 180 * 181 * <p>Because a {@code TreeMultimap} has unique sorted keys, this method returns a {@link 182 * NavigableMap}, instead of the {@link java.util.Map} specified in the {@link Multimap} 183 * interface. 184 * 185 * @since 14.0 (present with return type {@code SortedMap} since 2.0) 186 */ 187 @Override 188 public NavigableMap<K, Collection<V>> asMap() { 189 return (NavigableMap<K, Collection<V>>) super.asMap(); 190 } 191 192 /** 193 * @serialData key comparator, value comparator, number of distinct keys, and then for each 194 * distinct key: the key, number of values for that key, and key values 195 */ 196 @GwtIncompatible // java.io.ObjectOutputStream 197 private void writeObject(ObjectOutputStream stream) throws IOException { 198 stream.defaultWriteObject(); 199 stream.writeObject(keyComparator()); 200 stream.writeObject(valueComparator()); 201 Serialization.writeMultimap(this, stream); 202 } 203 204 @GwtIncompatible // java.io.ObjectInputStream 205 @SuppressWarnings("unchecked") // reading data stored by writeObject 206 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 207 stream.defaultReadObject(); 208 keyComparator = checkNotNull((Comparator<? super K>) stream.readObject()); 209 valueComparator = checkNotNull((Comparator<? super V>) stream.readObject()); 210 setMap(new TreeMap<K, Collection<V>>(keyComparator)); 211 Serialization.populateMultimap(this, stream); 212 } 213 214 @GwtIncompatible // not needed in emulated source 215 private static final long serialVersionUID = 0; 216}