1/*
2 * Copyright (C) 2012 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.AbstractCollection;
24import java.util.Collection;
25import java.util.Iterator;
26import java.util.Map;
27import java.util.Map.Entry;
28import java.util.Set;
29
30import javax.annotation.Nullable;
31
32/**
33 * A skeleton {@code Multimap} implementation, not necessarily in terms of a {@code Map}.
34 *
35 * @author Louis Wasserman
36 */
37@GwtCompatible
38abstract class AbstractMultimap<K, V> implements Multimap<K, V> {
39  @Override
40  public boolean isEmpty() {
41    return size() == 0;
42  }
43
44  @Override
45  public boolean containsValue(@Nullable Object value) {
46    for (Collection<V> collection : asMap().values()) {
47      if (collection.contains(value)) {
48        return true;
49      }
50    }
51
52    return false;
53  }
54
55  @Override
56  public boolean containsEntry(@Nullable Object key, @Nullable Object value) {
57    Collection<V> collection = asMap().get(key);
58    return collection != null && collection.contains(value);
59  }
60
61  @Override
62  public boolean remove(@Nullable Object key, @Nullable Object value) {
63    Collection<V> collection = asMap().get(key);
64    return collection != null && collection.remove(value);
65  }
66
67  @Override
68  public boolean put(@Nullable K key, @Nullable V value) {
69    return get(key).add(value);
70  }
71
72  @Override
73  public boolean putAll(@Nullable K key, Iterable<? extends V> values) {
74    checkNotNull(values);
75    // make sure we only call values.iterator() once
76    // and we only call get(key) if values is nonempty
77    if (values instanceof Collection) {
78      Collection<? extends V> valueCollection = (Collection<? extends V>) values;
79      return !valueCollection.isEmpty() && get(key).addAll(valueCollection);
80    } else {
81      Iterator<? extends V> valueItr = values.iterator();
82      return valueItr.hasNext() && Iterators.addAll(get(key), valueItr);
83    }
84  }
85
86  @Override
87  public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
88    boolean changed = false;
89    for (Map.Entry<? extends K, ? extends V> entry : multimap.entries()) {
90      changed |= put(entry.getKey(), entry.getValue());
91    }
92    return changed;
93  }
94
95  @Override
96  public Collection<V> replaceValues(@Nullable K key, Iterable<? extends V> values) {
97    checkNotNull(values);
98    Collection<V> result = removeAll(key);
99    putAll(key, values);
100    return result;
101  }
102
103  private transient Collection<Entry<K, V>> entries;
104
105  @Override
106  public Collection<Entry<K, V>> entries() {
107    Collection<Entry<K, V>> result = entries;
108    return (result == null) ? entries = createEntries() : result;
109  }
110
111  Collection<Entry<K, V>> createEntries() {
112    if (this instanceof SetMultimap) {
113      return new EntrySet();
114    } else {
115      return new Entries();
116    }
117  }
118
119  private class Entries extends Multimaps.Entries<K, V> {
120    @Override
121    Multimap<K, V> multimap() {
122      return AbstractMultimap.this;
123    }
124
125    @Override
126    public Iterator<Entry<K, V>> iterator() {
127      return entryIterator();
128    }
129  }
130
131  private class EntrySet extends Entries implements Set<Entry<K, V>> {
132    @Override
133    public int hashCode() {
134      return Sets.hashCodeImpl(this);
135    }
136
137    @Override
138    public boolean equals(@Nullable Object obj) {
139      return Sets.equalsImpl(this, obj);
140    }
141  }
142
143  abstract Iterator<Entry<K, V>> entryIterator();
144
145  private transient Set<K> keySet;
146
147  @Override
148  public Set<K> keySet() {
149    Set<K> result = keySet;
150    return (result == null) ? keySet = createKeySet() : result;
151  }
152
153  Set<K> createKeySet() {
154    return new Maps.KeySet<K, Collection<V>>(asMap());
155  }
156
157  private transient Multiset<K> keys;
158
159  @Override
160  public Multiset<K> keys() {
161    Multiset<K> result = keys;
162    return (result == null) ? keys = createKeys() : result;
163  }
164
165  Multiset<K> createKeys() {
166    return new Multimaps.Keys<K, V>(this);
167  }
168
169  private transient Collection<V> values;
170
171  @Override
172  public Collection<V> values() {
173    Collection<V> result = values;
174    return (result == null) ? values = createValues() : result;
175  }
176
177  Collection<V> createValues() {
178    return new Values();
179  }
180
181  class Values extends AbstractCollection<V> {
182    @Override public Iterator<V> iterator() {
183      return valueIterator();
184    }
185
186    @Override public int size() {
187      return AbstractMultimap.this.size();
188    }
189
190    @Override public boolean contains(@Nullable Object o) {
191      return AbstractMultimap.this.containsValue(o);
192    }
193
194    @Override public void clear() {
195      AbstractMultimap.this.clear();
196    }
197  }
198
199  Iterator<V> valueIterator() {
200    return Maps.valueIterator(entries().iterator());
201  }
202
203  private transient Map<K, Collection<V>> asMap;
204
205  @Override
206  public Map<K, Collection<V>> asMap() {
207    Map<K, Collection<V>> result = asMap;
208    return (result == null) ? asMap = createAsMap() : result;
209  }
210
211  abstract Map<K, Collection<V>> createAsMap();
212
213  // Comparison and hashing
214
215  @Override public boolean equals(@Nullable Object object) {
216    return Multimaps.equalsImpl(this, object);
217  }
218
219  /**
220   * Returns the hash code for this multimap.
221   *
222   * <p>The hash code of a multimap is defined as the hash code of the map view,
223   * as returned by {@link Multimap#asMap}.
224   *
225   * @see Map#hashCode
226   */
227  @Override public int hashCode() {
228    return asMap().hashCode();
229  }
230
231  /**
232   * Returns a string representation of the multimap, generated by calling
233   * {@code toString} on the map returned by {@link Multimap#asMap}.
234   *
235   * @return a string representation of the multimap
236   */
237  @Override
238  public String toString() {
239    return asMap().toString();
240  }
241}
242