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