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 — <b>Testing </b></li>
034 * <li>Flo — <b>Documentation </b></li>
035 * </ul>
036 * </li>
037 * <li>Project B
038 * <ul>
039 * <li>Flo — <b>Design </b></li>
040 * <li>Dan — <b>QA </b></li>
041 * <li>Markus — <b>CM </b></li>
042 * <li>Jorge — <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 }