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 }