1 /*
2  * Copyright (C) 2011 The Android Open Source Project
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 package com.android.tradefed.util;
17 
18 import com.android.tradefed.build.BuildSerializedVersion;
19 
20 import com.google.common.base.Objects;
21 
22 import java.io.Serializable;
23 import java.util.AbstractMap;
24 import java.util.ArrayList;
25 import java.util.Collection;
26 import java.util.Collections;
27 import java.util.HashMap;
28 import java.util.LinkedList;
29 import java.util.List;
30 import java.util.Map;
31 import java.util.Set;
32 
33 /** A {@link Map} that supports multiple values per key. */
34 public class MultiMap<K, V> implements Serializable {
35 
36     private static final long serialVersionUID = BuildSerializedVersion.VERSION;
37     private final Map<K, List<V>> mInternalMap;
38 
MultiMap()39     public MultiMap() {
40         mInternalMap = new HashMap<K, List<V>>();
41     }
42 
MultiMap(MultiMap<K, V> map)43     public MultiMap(MultiMap<K, V> map) {
44         this();
45         for (K key : map.keySet()) {
46             List<V> value = map.get(key);
47             mInternalMap.put(key, value);
48         }
49     }
50 
MultiMap(Map<K, V> map)51     public MultiMap(Map<K, V> map) {
52         this();
53         for (K key : map.keySet()) {
54             put(key, map.get(key));
55         }
56     }
57 
58     /**
59      * Clears the map.
60      */
clear()61     public void clear() {
62         mInternalMap.clear();
63     }
64 
65     /**
66      * Checks whether the map contains the specified key.
67      *
68      * @see Map#containsKey(Object)
69      */
containsKey(K key)70     public boolean containsKey(K key) {
71         return mInternalMap.containsKey(key);
72     }
73 
74     /**
75      * Checks whether the map contains the specified value.
76      *
77      * @see Map#containsValue(Object)
78      */
containsValue(V value)79     public boolean containsValue(V value) {
80         for (List<V> valueList : mInternalMap.values()) {
81             if (valueList.contains(value)) {
82                 return true;
83             }
84         }
85         return false;
86     }
87 
88     /**
89      * Gets the list of values associated with each key.
90      */
get(K key)91     public List<V> get(K key) {
92         return mInternalMap.get(key);
93     }
94 
95     /**
96      * @see Map#isEmpty()
97      */
isEmpty()98     public boolean isEmpty() {
99         return mInternalMap.isEmpty();
100     }
101 
102     /** Returns a collection of all distinct keys contained in this multimap. */
keySet()103     public Set<K> keySet() {
104         return mInternalMap.keySet();
105     }
106 
107     /**
108      * Returns a collection of all key-value pairs in this MultiMap as <code>Map.Entry</code>
109      * instances.
110      */
entries()111     public Collection<Map.Entry<K, V>> entries() {
112         ArrayList<Map.Entry<K, V>> entries = new ArrayList<>();
113         for (K key : keySet()) {
114             for (V value : get(key)) {
115                 entries.add(new AbstractMap.SimpleImmutableEntry<>(key, value));
116             }
117         }
118         return Collections.unmodifiableList(entries);
119     }
120 
121     /**
122      * Adds the value to the list associated with a key.
123      *
124      * @see Map#put(Object, Object)
125      */
put(K key, V value)126     public V put(K key, V value) {
127         List<V> valueList = mInternalMap.get(key);
128         if (valueList == null) {
129             valueList = new LinkedList<V>();
130             mInternalMap.put(key, valueList);
131         }
132         valueList.add(value);
133         return value;
134     }
135 
136     /**
137      *
138      * Adds all entries in given {@link Map} to this {@link MultiMap}.
139      */
putAll(Map<? extends K, ? extends V> m)140     public void putAll(Map<? extends K, ? extends V> m) {
141         for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {
142             put(entry.getKey(), entry.getValue());
143         }
144     }
145 
146    /**
147     * Adds all entries in given {@link MultiMap} to this {@link MultiMap}.
148     */
putAll(MultiMap<K, ? extends V> m)149    public void putAll(MultiMap<K, ? extends V> m) {
150        for (K key : m.keySet()) {
151            for (V value : m.get(key)) {
152                put(key, value);
153            }
154        }
155    }
156 
157     /**
158      * Removes all values associated with the specified key.
159      */
remove(K key)160     public List<V> remove(K key) {
161         return mInternalMap.remove(key);
162     }
163 
164     /**
165      * Returns the number of keys in the map
166      */
size()167     public int size() {
168         return mInternalMap.size();
169     }
170 
171     /**
172      * Returns list of all values.
173      */
values()174     public List<V> values() {
175         List<V> allValues = new LinkedList<V>();
176         for (List<V> valueList : mInternalMap.values()) {
177             allValues.addAll(valueList);
178         }
179         return allValues;
180     }
181 
182     /**
183      * Construct a new map, that contains a unique String key for each value.
184      *
185      * Current algorithm will construct unique key by appending a unique position number to
186      * key's toString() value
187      *
188      * @return a {@link Map}
189      */
getUniqueMap()190     public Map<String, V> getUniqueMap() {
191         Map<String, V> uniqueMap = new HashMap<String, V>();
192         for (Map.Entry<K, List<V>> entry : mInternalMap.entrySet()) {
193             int count = 1;
194             for (V value : entry.getValue()) {
195                 if (count == 1) {
196                     addUniqueEntry(uniqueMap, entry.getKey().toString(), value);
197                 } else {
198                     // append unique number to key for each value
199                     addUniqueEntry(uniqueMap, String.format("%s%d", entry.getKey(), count), value);
200                 }
201                 count++;
202             }
203         }
204         return uniqueMap;
205     }
206 
207     /**
208      * Recursive method that will append characters to proposedKey until its unique. Used in case
209      * there are collisions with generated key values.
210      *
211      * @param uniqueMap
212      * @param proposedKey
213      * @param value
214      */
addUniqueEntry(Map<String, V> uniqueMap, String proposedKey, V value)215     private String addUniqueEntry(Map<String, V> uniqueMap, String proposedKey, V value) {
216         // not the most efficient algorithm, but should work
217         if (uniqueMap.containsKey(proposedKey)) {
218             return addUniqueEntry(uniqueMap, String.format("%s%s", proposedKey, "X"), value);
219         } else {
220             uniqueMap.put(proposedKey, value);
221             return proposedKey;
222         }
223     }
224 
225     /**
226      * {@inheritDoc}
227      */
228     @Override
hashCode()229     public int hashCode() {
230         return mInternalMap.hashCode();
231     }
232 
233     /**
234      * {@inheritDoc}
235      */
236     @Override
equals(Object obj)237     public boolean equals(Object obj) {
238         if (this == obj) {
239             return true;
240         }
241         if (obj == null) {
242             return false;
243         }
244         if (getClass() != obj.getClass()) {
245             return false;
246         }
247         MultiMap<?, ?> other = (MultiMap<?, ?>) obj;
248         return Objects.equal(mInternalMap, other.mInternalMap);
249     }
250 }
251