001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.apache.commons.collections; 018 019 import java.io.IOException; 020 import java.io.ObjectInputStream; 021 import java.util.AbstractCollection; 022 import java.util.ArrayList; 023 import java.util.Collection; 024 import java.util.HashMap; 025 import java.util.Iterator; 026 import java.util.Map; 027 import java.util.NoSuchElementException; 028 import java.util.Set; 029 030 import org.apache.commons.collections.iterators.EmptyIterator; 031 032 /** 033 * <code>MultiHashMap</code> is the default implementation of the 034 * {@link org.apache.commons.collections.MultiMap MultiMap} interface. 035 * <p> 036 * A <code>MultiMap</code> is a Map with slightly different semantics. 037 * Putting a value into the map will add the value to a Collection at that key. 038 * Getting a value will return a Collection, holding all the values put to that key. 039 * <p> 040 * This implementation uses an <code>ArrayList</code> as the collection. 041 * The internal storage list is made available without cloning via the 042 * <code>get(Object)</code> and <code>entrySet()</code> methods. 043 * The implementation returns <code>null</code> when there are no values mapped to a key. 044 * <p> 045 * For example: 046 * <pre> 047 * MultiMap mhm = new MultiHashMap(); 048 * mhm.put(key, "A"); 049 * mhm.put(key, "B"); 050 * mhm.put(key, "C"); 051 * List list = (List) mhm.get(key);</pre> 052 * <p> 053 * <code>list</code> will be a list containing "A", "B", "C". 054 * 055 * @deprecated Class now available as MultiValueMap in map subpackage. 056 * This version is due to be removed in collections v4.0. 057 * 058 * @since Commons Collections 2.0 059 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ 060 * 061 * @author Christopher Berry 062 * @author James Strachan 063 * @author Steve Downey 064 * @author Stephen Colebourne 065 * @author Julien Buret 066 * @author Serhiy Yevtushenko 067 * @author Robert Ribnitz 068 */ 069 public class MultiHashMap extends HashMap implements MultiMap { 070 071 // backed values collection 072 private transient Collection values = null; 073 074 // compatibility with commons-collection releases 2.0/2.1 075 private static final long serialVersionUID = 1943563828307035349L; 076 077 /** 078 * Constructor. 079 */ 080 public MultiHashMap() { 081 super(); 082 } 083 084 /** 085 * Constructor. 086 * 087 * @param initialCapacity the initial map capacity 088 */ 089 public MultiHashMap(int initialCapacity) { 090 super(initialCapacity); 091 } 092 093 /** 094 * Constructor. 095 * 096 * @param initialCapacity the initial map capacity 097 * @param loadFactor the amount 0.0-1.0 at which to resize the map 098 */ 099 public MultiHashMap(int initialCapacity, float loadFactor) { 100 super(initialCapacity, loadFactor); 101 } 102 103 /** 104 * Constructor that copies the input map creating an independent copy. 105 * <p> 106 * This method performs different behaviour depending on whether the map 107 * specified is a MultiMap or not. If a MultiMap is specified, each internal 108 * collection is also cloned. If the specified map only implements Map, then 109 * the values are not cloned. 110 * <p> 111 * NOTE: From Commons Collections 3.1 this method correctly copies a MultiMap 112 * to form a truly independent new map. 113 * NOTE: From Commons Collections 3.2 this method delegates to the newly 114 * added putAll(Map) override method. 115 * 116 * @param mapToCopy a Map to copy 117 */ 118 public MultiHashMap(Map mapToCopy) { 119 // be careful of JDK 1.3 vs 1.4 differences 120 super((int) (mapToCopy.size() * 1.4f)); 121 putAll(mapToCopy); 122 } 123 124 /** 125 * Read the object during deserialization. 126 */ 127 private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException { 128 // This method is needed because the 1.2/1.3 Java deserialisation called 129 // put and thus messed up that method 130 131 // default read object 132 s.defaultReadObject(); 133 134 // problem only with jvm <1.4 135 String version = "1.2"; 136 try { 137 version = System.getProperty("java.version"); 138 } catch (SecurityException ex) { 139 // ignore and treat as 1.2/1.3 140 } 141 142 if (version.startsWith("1.2") || version.startsWith("1.3")) { 143 for (Iterator iterator = entrySet().iterator(); iterator.hasNext();) { 144 Map.Entry entry = (Map.Entry) iterator.next(); 145 // put has created a extra collection level, remove it 146 super.put(entry.getKey(), ((Collection) entry.getValue()).iterator().next()); 147 } 148 } 149 } 150 151 //----------------------------------------------------------------------- 152 /** 153 * Gets the total size of the map by counting all the values. 154 * 155 * @return the total size of the map counting all values 156 * @since Commons Collections 3.1 157 */ 158 public int totalSize() { 159 int total = 0; 160 Collection values = super.values(); 161 for (Iterator it = values.iterator(); it.hasNext();) { 162 Collection coll = (Collection) it.next(); 163 total += coll.size(); 164 } 165 return total; 166 } 167 168 /** 169 * Gets the collection mapped to the specified key. 170 * This method is a convenience method to typecast the result of <code>get(key)</code>. 171 * 172 * @param key the key to retrieve 173 * @return the collection mapped to the key, null if no mapping 174 * @since Commons Collections 3.1 175 */ 176 public Collection getCollection(Object key) { 177 return (Collection) get(key); 178 } 179 180 /** 181 * Gets the size of the collection mapped to the specified key. 182 * 183 * @param key the key to get size for 184 * @return the size of the collection at the key, zero if key not in map 185 * @since Commons Collections 3.1 186 */ 187 public int size(Object key) { 188 Collection coll = getCollection(key); 189 if (coll == null) { 190 return 0; 191 } 192 return coll.size(); 193 } 194 195 /** 196 * Gets an iterator for the collection mapped to the specified key. 197 * 198 * @param key the key to get an iterator for 199 * @return the iterator of the collection at the key, empty iterator if key not in map 200 * @since Commons Collections 3.1 201 */ 202 public Iterator iterator(Object key) { 203 Collection coll = getCollection(key); 204 if (coll == null) { 205 return EmptyIterator.INSTANCE; 206 } 207 return coll.iterator(); 208 } 209 210 /** 211 * Adds the value to the collection associated with the specified key. 212 * <p> 213 * Unlike a normal <code>Map</code> the previous value is not replaced. 214 * Instead the new value is added to the collection stored against the key. 215 * 216 * @param key the key to store against 217 * @param value the value to add to the collection at the key 218 * @return the value added if the map changed and null if the map did not change 219 */ 220 public Object put(Object key, Object value) { 221 // NOTE:: put is called during deserialization in JDK < 1.4 !!!!!! 222 // so we must have a readObject() 223 Collection coll = getCollection(key); 224 if (coll == null) { 225 coll = createCollection(null); 226 super.put(key, coll); 227 } 228 boolean results = coll.add(value); 229 return (results ? value : null); 230 } 231 232 /** 233 * Override superclass to ensure that MultiMap instances are 234 * correctly handled. 235 * <p> 236 * NOTE: Prior to version 3.2, putAll(map) did not work properly 237 * when passed a MultiMap. 238 * 239 * @param map the map to copy (either a normal or multi map) 240 */ 241 public void putAll(Map map) { 242 if (map instanceof MultiMap) { 243 for (Iterator it = map.entrySet().iterator(); it.hasNext();) { 244 Map.Entry entry = (Map.Entry) it.next(); 245 Collection coll = (Collection) entry.getValue(); 246 putAll(entry.getKey(), coll); 247 } 248 } else { 249 for (Iterator it = map.entrySet().iterator(); it.hasNext();) { 250 Map.Entry entry = (Map.Entry) it.next(); 251 put(entry.getKey(), entry.getValue()); 252 } 253 } 254 } 255 256 /** 257 * Adds a collection of values to the collection associated with the specified key. 258 * 259 * @param key the key to store against 260 * @param values the values to add to the collection at the key, null ignored 261 * @return true if this map changed 262 * @since Commons Collections 3.1 263 */ 264 public boolean putAll(Object key, Collection values) { 265 if (values == null || values.size() == 0) { 266 return false; 267 } 268 Collection coll = getCollection(key); 269 if (coll == null) { 270 coll = createCollection(values); 271 if (coll.size() == 0) { 272 return false; 273 } 274 super.put(key, coll); 275 return true; 276 } else { 277 return coll.addAll(values); 278 } 279 } 280 281 /** 282 * Checks whether the map contains the value specified. 283 * <p> 284 * This checks all collections against all keys for the value, and thus could be slow. 285 * 286 * @param value the value to search for 287 * @return true if the map contains the value 288 */ 289 public boolean containsValue(Object value) { 290 Set pairs = super.entrySet(); 291 292 if (pairs == null) { 293 return false; 294 } 295 Iterator pairsIterator = pairs.iterator(); 296 while (pairsIterator.hasNext()) { 297 Map.Entry keyValuePair = (Map.Entry) pairsIterator.next(); 298 Collection coll = (Collection) keyValuePair.getValue(); 299 if (coll.contains(value)) { 300 return true; 301 } 302 } 303 return false; 304 } 305 306 /** 307 * Checks whether the collection at the specified key contains the value. 308 * 309 * @param value the value to search for 310 * @return true if the map contains the value 311 * @since Commons Collections 3.1 312 */ 313 public boolean containsValue(Object key, Object value) { 314 Collection coll = getCollection(key); 315 if (coll == null) { 316 return false; 317 } 318 return coll.contains(value); 319 } 320 321 /** 322 * Removes a specific value from map. 323 * <p> 324 * The item is removed from the collection mapped to the specified key. 325 * Other values attached to that key are unaffected. 326 * <p> 327 * If the last value for a key is removed, <code>null</code> will be returned 328 * from a subsequant <code>get(key)</code>. 329 * 330 * @param key the key to remove from 331 * @param item the value to remove 332 * @return the value removed (which was passed in), null if nothing removed 333 */ 334 public Object remove(Object key, Object item) { 335 Collection valuesForKey = getCollection(key); 336 if (valuesForKey == null) { 337 return null; 338 } 339 boolean removed = valuesForKey.remove(item); 340 if (removed == false) { 341 return null; 342 } 343 // remove the list if it is now empty 344 // (saves space, and allows equals to work) 345 if (valuesForKey.isEmpty()){ 346 remove(key); 347 } 348 return item; 349 } 350 351 /** 352 * Clear the map. 353 * <p> 354 * This clears each collection in the map, and so may be slow. 355 */ 356 public void clear() { 357 // For gc, clear each list in the map 358 Set pairs = super.entrySet(); 359 Iterator pairsIterator = pairs.iterator(); 360 while (pairsIterator.hasNext()) { 361 Map.Entry keyValuePair = (Map.Entry) pairsIterator.next(); 362 Collection coll = (Collection) keyValuePair.getValue(); 363 coll.clear(); 364 } 365 super.clear(); 366 } 367 368 /** 369 * Gets a collection containing all the values in the map. 370 * <p> 371 * This returns a collection containing the combination of values from all keys. 372 * 373 * @return a collection view of the values contained in this map 374 */ 375 public Collection values() { 376 Collection vs = values; 377 return (vs != null ? vs : (values = new Values())); 378 } 379 380 /** 381 * Gets the values iterator from the superclass, as used by inner class. 382 * 383 * @return iterator 384 */ 385 Iterator superValuesIterator() { 386 return super.values().iterator(); 387 } 388 389 //----------------------------------------------------------------------- 390 /** 391 * Inner class to view the elements. 392 */ 393 private class Values extends AbstractCollection { 394 395 public Iterator iterator() { 396 return new ValueIterator(); 397 } 398 399 public int size() { 400 int compt = 0; 401 Iterator it = iterator(); 402 while (it.hasNext()) { 403 it.next(); 404 compt++; 405 } 406 return compt; 407 } 408 409 public void clear() { 410 MultiHashMap.this.clear(); 411 } 412 413 } 414 415 /** 416 * Inner iterator to view the elements. 417 */ 418 private class ValueIterator implements Iterator { 419 private Iterator backedIterator; 420 private Iterator tempIterator; 421 422 private ValueIterator() { 423 backedIterator = MultiHashMap.this.superValuesIterator(); 424 } 425 426 private boolean searchNextIterator() { 427 while (tempIterator == null || tempIterator.hasNext() == false) { 428 if (backedIterator.hasNext() == false) { 429 return false; 430 } 431 tempIterator = ((Collection) backedIterator.next()).iterator(); 432 } 433 return true; 434 } 435 436 public boolean hasNext() { 437 return searchNextIterator(); 438 } 439 440 public Object next() { 441 if (searchNextIterator() == false) { 442 throw new NoSuchElementException(); 443 } 444 return tempIterator.next(); 445 } 446 447 public void remove() { 448 if (tempIterator == null) { 449 throw new IllegalStateException(); 450 } 451 tempIterator.remove(); 452 } 453 454 } 455 456 //----------------------------------------------------------------------- 457 /** 458 * Clones the map creating an independent copy. 459 * <p> 460 * The clone will shallow clone the collections as well as the map. 461 * 462 * @return the cloned map 463 */ 464 public Object clone() { 465 MultiHashMap cloned = (MultiHashMap) super.clone(); 466 467 // clone each Collection container 468 for (Iterator it = cloned.entrySet().iterator(); it.hasNext();) { 469 Map.Entry entry = (Map.Entry) it.next(); 470 Collection coll = (Collection) entry.getValue(); 471 Collection newColl = createCollection(coll); 472 entry.setValue(newColl); 473 } 474 return cloned; 475 } 476 477 /** 478 * Creates a new instance of the map value Collection container. 479 * <p> 480 * This method can be overridden to use your own collection type. 481 * 482 * @param coll the collection to copy, may be null 483 * @return the new collection 484 */ 485 protected Collection createCollection(Collection coll) { 486 if (coll == null) { 487 return new ArrayList(); 488 } else { 489 return new ArrayList(coll); 490 } 491 } 492 493 }