001    /*--------------------------------------------------------------------------+
002    $Id: TwoDimHashMap.java 26283 2010-02-18 11:18:57Z juergens $
003    |                                                                          |
004    | Copyright 2005-2010 Technische Universitaet Muenchen                     |
005    |                                                                          |
006    | Licensed under the Apache License, Version 2.0 (the "License");          |
007    | you may not use this file except in compliance with the License.         |
008    | You may obtain a copy of the License at                                  |
009    |                                                                          |
010    |    http://www.apache.org/licenses/LICENSE-2.0                            |
011    |                                                                          |
012    | Unless required by applicable law or agreed to in writing, software      |
013    | distributed under the License is distributed on an "AS IS" BASIS,        |
014    | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
015    | See the License for the specific language governing permissions and      |
016    | limitations under the License.                                           |
017    +--------------------------------------------------------------------------*/
018    package edu.tum.cs.commons.collections;
019    
020    import java.util.ArrayList;
021    import java.util.Collection;
022    import java.util.HashMap;
023    import java.util.List;
024    import java.util.Map;
025    import java.util.Set;
026    
027    /**
028     * A 2-dimensional hash map. Allows storage of items identified by two different
029     * keys. This can be used to store the following data structure:
030     * <ul>
031     * <li>Project A
032     * <ul>
033     * <li>Dan &mdash; <b>Testing </b></li>
034     * <li>Flo &mdash; <b>Documentation </b></li>
035     * </ul>
036     * </li>
037     * <li>Project B
038     * <ul>
039     * <li>Flo &mdash; <b>Design </b></li>
040     * <li>Dan &mdash; <b>QA </b></li>
041     * <li>Markus &mdash; <b>CM </b></li>
042     * <li>Jorge &mdash; <b>Testing </b></li>
043     * </ul>
044     * </li>
045     * </ul>
046     * 
047     * @author Florian Deissenboeck
048     * @author $Author: juergens $
049     * @version $Revision: 26283 $
050     * @levd.rating GREEN Hash: 884229989F2777EFC722AAF38C87BBDD
051     */
052    public class TwoDimHashMap<K1, K2, I> {
053    
054            /** The first level map. */
055            private final Map<K1, Map<K2, I>> main;
056    
057            /** Create a new doubly hashed map. */
058            public TwoDimHashMap() {
059                    main = new HashMap<K1, Map<K2, I>>();
060            }
061    
062            /** Create a new doubly hashed using the provided map as outer map. */
063            public TwoDimHashMap(Map<K1, Map<K2, I>> outerMap) {
064                    main = outerMap;
065            }
066    
067            /** Put all values of another TwoDimHashMap into this map. */
068            public void putAll(TwoDimHashMap<K1, K2, I> otherMap) {
069                    for (K1 key1 : otherMap.getFirstKeys()) {
070                            for (K2 key2 : otherMap.getSecondKeys(key1)) {
071                                    I value = otherMap.getValue(key1, key2);
072                                    putValue(key1, key2, value);
073                            }
074                    }
075            }
076    
077            /**
078             * Put a doubly hashed value. Potentially existing value will be
079             * overwritten.
080             * 
081             * @param key1
082             *            first level key
083             * @param key2
084             *            second level key
085             * @param value
086             *            the value
087             */
088            public void putValue(K1 key1, K2 key2, I value) {
089                    Map<K2, I> map = main.get(key1);
090                    if (map == null) {
091                            map = new HashMap<K2, I>();
092                            main.put(key1, map);
093                    }
094                    map.put(key2, value);
095            }
096    
097            /**
098             * Get a value by specifying first and second level key.
099             * <p>
100             * <i>Examples: </i>
101             * <ul>
102             * <li><code>get("Project A", "Flo") => "Documentation"</code></li>
103             * <li><code>get("Project B", "Dan") => "QA"</code></li>
104             * </ul>
105             * 
106             * @param firstKey
107             *            first level key
108             * @param secondKey
109             *            second level key
110             * @return the value. Is <code>null</code> if first or second level key
111             *         does not exist or if <code>null</code> was explicitly stored.
112             */
113            public I getValue(K1 firstKey, K2 secondKey) {
114                    Map<K2, I> map = main.get(firstKey);
115                    if (map == null) {
116                            return null;
117                    }
118                    return map.get(secondKey);
119            }
120    
121            /**
122             * Returns whether the given key combination is available in the map.
123             * <p>
124             * <i>Example: </i>
125             * <ul>
126             * <li><code>containsKey("Project A", "Flo") => true</code></li>
127             * <li><code>containsKey("Project X", "Flo") => false</code></li>
128             * </ul>
129             * 
130             * @param firstKey
131             *            first level key
132             * @param secondKey
133             *            second level key
134             */
135            public boolean containsKey(K1 firstKey, K2 secondKey) {
136                    Map<K2, I> map = main.get(firstKey);
137                    if (map == null) {
138                            return false;
139                    }
140                    return map.containsKey(secondKey);
141            }
142    
143            /**
144             * Get all values referenced by a first level key.
145             * <p>
146             * <i>Examples: </i>
147             * <ul>
148             * <li>
149             * <code>getValuesByFirstKey("Project A") => ("Testing", "Documentation")</code>
150             * </li>
151             * </ul>
152             * 
153             * @param firstKey
154             *            the first level key
155             * @return a list of values referenced by the specified first level key
156             */
157            public Collection<I> getValuesByFirstKey(K1 firstKey) {
158                    Map<K2, I> map = main.get(firstKey);
159                    if (map == null) {
160                            return null;
161                    }
162                    return map.values();
163    
164            }
165    
166            /**
167             * Get all first level keys. <i>Examples: </i>
168             * <ul>
169             * <li><code>getFirstKeys() => ("Project A", "Project B")</code></li>
170             * </ul>
171             * 
172             * @return all first level keys.
173             */
174            public Set<K1> getFirstKeys() {
175                    return main.keySet();
176            }
177    
178            /**
179             * Get all the second level keys for a first key. <i>Examples: </i>
180             * <ul>
181             * <li><code>getFirstKeys("Project A") => ("Dan", "Flo")</code></li>
182             * </ul>
183             * 
184             * @param firstKey
185             *            the first level key.
186             * @return all second level keys for a first level key.
187             */
188            public Set<K2> getSecondKeys(K1 firstKey) {
189                    Map<K2, I> map = main.get(firstKey);
190                    if (map == null) {
191                            return CollectionUtils.emptySet();
192                    }
193                    return map.keySet();
194            }
195    
196            /**
197             * Get all values referenced by a second level key.
198             * <p>
199             * <i>Examples: </i>
200             * <ul>
201             * <li>
202             * <code>getValuesBySecondKey("Flo") => ("Documentation", "Design")</code>
203             * </li>
204             * </ul>
205             * <b>Note: </b> This method's complexity is linear in the number of first
206             * level keys.
207             * 
208             * @param secondKey
209             *            the second level key
210             * @return a new list of values referenced by the specified second level key
211             */
212            public List<I> getValuesBySecondKey(K2 secondKey) {
213                    ArrayList<I> result = new ArrayList<I>();
214    
215                    for (Map<K2, I> map : main.values()) {
216                            if (map.containsKey(secondKey)) {
217                                    result.add(map.get(secondKey));
218                            }
219                    }
220    
221                    return result;
222            }
223    
224            /**
225             * Get all values stored in the map.
226             * 
227             * @return a new list of all values.
228             */
229            public List<I> getValues() {
230                    ArrayList<I> result = new ArrayList<I>();
231    
232                    for (Map<K2, I> map : main.values()) {
233                            result.addAll(map.values());
234                    }
235    
236                    return result;
237            }
238    
239            /**
240             * Get size of the map.
241             * 
242             * @return the number of values stored in this map.
243             */
244            public int getSize() {
245                    int size = 0;
246                    for (Map<K2, I> map : main.values()) {
247                            size += map.size();
248                    }
249                    return size;
250            }
251    
252            /**
253             * Check if the map is empty.
254             */
255            public boolean isEmpty() {
256                    return getSize() == 0;
257            }
258    
259            /**
260             * Get the size of the (second) map stored for a first key.
261             * 
262             * @return the size or 0 if key wasn't found.
263             */
264            public int getSecondSize(K1 key1) {
265                    Map<K2, I> map = main.get(key1);
266                    if (map == null) {
267                            return 0;
268                    }
269                    return map.size();
270            }
271    
272            /**
273             * Clear the whole map.
274             * 
275             */
276            public void clear() {
277                    main.clear();
278            }
279    
280            /**
281             * Removes the value associated to the key combination of key1 and key2.
282             * 
283             * @param key1
284             * @param key2
285             * @return previous value associated with specified key, or null if there
286             *         was no mapping for key. A null return can also indicate that the
287             *         map previously associated null with the specified key.
288             */
289            public I remove(K1 key1, K2 key2) {
290                    Map<K2, I> map = main.get(key1);
291                    if (map == null) {
292                            return null;
293                    }
294    
295                    if (!map.containsKey(key2)) {
296                            return null;
297                    }
298    
299                    I result = map.remove(key2);
300    
301                    if (map.isEmpty()) {
302                            main.remove(key1);
303                    }
304    
305                    return result;
306            }
307    
308            /**
309             * Remove all values specified by first key.
310             * 
311             * @param key
312             *            first level key
313             * @return <code>true</code> if key was present, <code>false</code>
314             *         otherwise
315             */
316            public boolean remove(K1 key) {
317                    Map<K2, I> result = main.remove(key);
318                    return (result != null);
319            }
320    }