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