1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2007 The Guava Authors 3090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * you may not use this file except in compliance with the License. 6090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * You may obtain a copy of the License at 7090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 8090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 10090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * See the License for the specific language governing permissions and 14090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * limitations under the License. 15090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 16090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 17090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpackage com.google.common.collect; 18090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 19090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkNotNull; 20090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtIncompatible; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 24090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.IOException; 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.ObjectInputStream; 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.ObjectOutputStream; 27090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Comparator; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.SortedMap; 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.SortedSet; 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.TreeMap; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.TreeSet; 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Implementation of {@code Multimap} whose keys and values are ordered by 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * their natural ordering or by supplied comparators. In all cases, this 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implementation uses {@link Comparable#compareTo} or {@link 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Comparator#compare} instead of {@link Object#equals} to determine 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * equivalence of instances. 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Warning:</b> The comparators or comparables used must be <i>consistent 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * with equals</i> as explained by the {@link Comparable} class specification. 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Otherwise, the resulting multiset will violate the general contract of {@link 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * SetMultimap}, which it is specified in terms of {@link Object#equals}. 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The collections returned by {@code keySet} and {@code asMap} iterate 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * through the keys according to the key comparator ordering or the natural 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ordering of the keys. Similarly, {@code get}, {@code removeAll}, and {@code 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * replaceValues} return collections that iterate through the values according 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * to the value comparator ordering or the natural ordering of the values. The 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * collections generated by {@code entries}, {@code keys}, and {@code values} 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iterate across the keys according to the above key ordering, and for each 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key they iterate across the values according to the value ordering. 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The multimap does not store duplicate key-value pairs. Adding a new 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key-value pair equal to an existing key-value pair has no effect. 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Null keys and values are permitted (provided, of course, that the 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * respective comparators support them). All optional multimap methods are 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * supported, and all returned views are modifiable. 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This class is not threadsafe when any concurrent operations update the 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap. Concurrent read operations will work correctly. To allow concurrent 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * update operations, wrap your multimap with a call to {@link 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Multimaps#synchronizedSortedSetMultimap}. 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Jared Levy 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(serializable = true, emulated = true) 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpublic class TreeMultimap<K, V> extends AbstractSortedSetMultimap<K, V> { 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Comparator<? super K> keyComparator; 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Comparator<? super V> valueComparator; 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates an empty {@code TreeMultimap} ordered by the natural ordering of 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * its keys and values. 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K extends Comparable, V extends Comparable> 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson TreeMultimap<K, V> create() { 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new TreeMultimap<K, V>(Ordering.natural(), Ordering.natural()); 82090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 83090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates an empty {@code TreeMultimap} instance using explicit comparators. 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Neither comparator may be null; use {@link Ordering#natural()} to specify 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * natural order. 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param keyComparator the comparator that determines the key ordering 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param valueComparator the comparator that determines the value ordering 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> TreeMultimap<K, V> create( 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Comparator<? super K> keyComparator, 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Comparator<? super V> valueComparator) { 95090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new TreeMultimap<K, V>(checkNotNull(keyComparator), 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(valueComparator)); 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Constructs a {@code TreeMultimap}, ordered by the natural ordering of its 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * keys and values, with the same mappings as the specified multimap. 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param multimap the multimap whose contents are copied to this multimap 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K extends Comparable, V extends Comparable> 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson TreeMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) { 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new TreeMultimap<K, V>(Ordering.natural(), Ordering.natural(), 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson multimap); 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert TreeMultimap(Comparator<? super K> keyComparator, 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super V> valueComparator) { 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super(new TreeMap<K, Collection<V>>(keyComparator)); 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.keyComparator = keyComparator; 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.valueComparator = valueComparator; 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private TreeMultimap(Comparator<? super K> keyComparator, 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Comparator<? super V> valueComparator, 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Multimap<? extends K, ? extends V> multimap) { 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this(keyComparator, valueComparator); 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson putAll(multimap); 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 127090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 128090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Creates an empty {@code TreeSet} for a collection of values for one key. 129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 130090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new {@code TreeSet} containing a collection of values for one 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override SortedSet<V> createCollection() { 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new TreeSet<V>(valueComparator); 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the comparator that orders the multimap keys. 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Comparator<? super K> keyComparator() { 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyComparator; 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Comparator<? super V> valueComparator() { 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return valueComparator; 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Because a {@code TreeMultimap} has unique sorted keys, this method 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * returns a {@link SortedSet}, instead of the {@link java.util.Set} specified 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in the {@link Multimap} interface. 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public SortedSet<K> keySet() { 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (SortedSet<K>) super.keySet(); 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Because a {@code TreeMultimap} has unique sorted keys, this method 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * returns a {@link SortedMap}, instead of the {@link java.util.Map} specified 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * in the {@link Multimap} interface. 166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public SortedMap<K, Collection<V>> asMap() { 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (SortedMap<K, Collection<V>>) super.asMap(); 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @serialData key comparator, value comparator, number of distinct keys, and 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * then for each distinct key: the key, number of values for that key, and 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key values 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("java.io.ObjectOutputStream") 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void writeObject(ObjectOutputStream stream) throws IOException { 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.defaultWriteObject(); 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.writeObject(keyComparator()); 180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.writeObject(valueComparator()); 181090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Serialization.writeMultimap(this, stream); 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("java.io.ObjectInputStream") 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") // reading data stored by writeObject 186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void readObject(ObjectInputStream stream) 187090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throws IOException, ClassNotFoundException { 188090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.defaultReadObject(); 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert keyComparator = checkNotNull((Comparator<? super K>) stream.readObject()); 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert valueComparator = checkNotNull((Comparator<? super V>) stream.readObject()); 191090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson setMap(new TreeMap<K, Collection<V>>(keyComparator)); 192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Serialization.populateMultimap(this, stream); 193090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 194090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("not needed in emulated source") 196090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final long serialVersionUID = 0; 197090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 198