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.map;
018
019 import java.util.AbstractCollection;
020 import java.util.ArrayList;
021 import java.util.Collection;
022 import java.util.HashMap;
023 import java.util.Iterator;
024 import java.util.Map;
025 import java.util.Set;
026
027 import org.apache.commons.collections.Factory;
028 import org.apache.commons.collections.FunctorException;
029 import org.apache.commons.collections.MultiMap;
030 import org.apache.commons.collections.iterators.EmptyIterator;
031 import org.apache.commons.collections.iterators.IteratorChain;
032
033 /**
034 * A MultiValueMap decorates another map, allowing it to have
035 * more than one value for a key.
036 * <p>
037 * A <code>MultiMap</code> is a Map with slightly different semantics.
038 * Putting a value into the map will add the value to a Collection at that key.
039 * Getting a value will return a Collection, holding all the values put to that key.
040 * <p>
041 * This implementation is a decorator, allowing any Map implementation
042 * to be used as the base.
043 * <p>
044 * In addition, this implementation allows the type of collection used
045 * for the values to be controlled. By default, an <code>ArrayList</code>
046 * is used, however a <code>Class</code> to instantiate may be specified,
047 * or a factory that returns a <code>Collection</code> instance.
048 * <p>
049 * <strong>Note that MultiValueMap is not synchronized and is not thread-safe.</strong>
050 * If you wish to use this map from multiple threads concurrently, you must use
051 * appropriate synchronization. This class may throw exceptions when accessed
052 * by concurrent threads without synchronization.
053 *
054 * @author James Carman
055 * @author Christopher Berry
056 * @author James Strachan
057 * @author Steve Downey
058 * @author Stephen Colebourne
059 * @author Julien Buret
060 * @author Serhiy Yevtushenko
061 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
062 * @since Commons Collections 3.2
063 */
064 public class MultiValueMap extends AbstractMapDecorator implements MultiMap {
065
066 /** The factory for creating value collections. */
067 private final Factory collectionFactory;
068 /** The cached values. */
069 private transient Collection values;
070
071 /**
072 * Creates a map which wraps the given map and
073 * maps keys to ArrayLists.
074 *
075 * @param map the map to wrap
076 */
077 public static MultiValueMap decorate(Map map) {
078 return new MultiValueMap(map, new ReflectionFactory(ArrayList.class));
079 }
080
081 /**
082 * Creates a map which decorates the given <code>map</code> and
083 * maps keys to collections of type <code>collectionClass</code>.
084 *
085 * @param map the map to wrap
086 * @param collectionClass the type of the collection class
087 */
088 public static MultiValueMap decorate(Map map, Class collectionClass) {
089 return new MultiValueMap(map, new ReflectionFactory(collectionClass));
090 }
091
092 /**
093 * Creates a map which decorates the given <code>map</code> and
094 * creates the value collections using the supplied <code>collectionFactory</code>.
095 *
096 * @param map the map to decorate
097 * @param collectionFactory the collection factory (must return a Collection object).
098 */
099 public static MultiValueMap decorate(Map map, Factory collectionFactory) {
100 return new MultiValueMap(map, collectionFactory);
101 }
102
103 //-----------------------------------------------------------------------
104 /**
105 * Creates a MultiValueMap based on a <code>HashMap</code> and
106 * storing the multiple values in an <code>ArrayList</code>.
107 */
108 public MultiValueMap() {
109 this(new HashMap(), new ReflectionFactory(ArrayList.class));
110 }
111
112 /**
113 * Creates a MultiValueMap which decorates the given <code>map</code> and
114 * creates the value collections using the supplied <code>collectionFactory</code>.
115 *
116 * @param map the map to decorate
117 * @param collectionFactory the collection factory which must return a Collection instance
118 */
119 protected MultiValueMap(Map map, Factory collectionFactory) {
120 super(map);
121 if (collectionFactory == null) {
122 throw new IllegalArgumentException("The factory must not be null");
123 }
124 this.collectionFactory = collectionFactory;
125 }
126
127 //-----------------------------------------------------------------------
128 /**
129 * Clear the map.
130 */
131 public void clear() {
132 // If you believe that you have GC issues here, try uncommenting this code
133 // Set pairs = getMap().entrySet();
134 // Iterator pairsIterator = pairs.iterator();
135 // while (pairsIterator.hasNext()) {
136 // Map.Entry keyValuePair = (Map.Entry) pairsIterator.next();
137 // Collection coll = (Collection) keyValuePair.getValue();
138 // coll.clear();
139 // }
140 getMap().clear();
141 }
142
143 /**
144 * Removes a specific value from map.
145 * <p>
146 * The item is removed from the collection mapped to the specified key.
147 * Other values attached to that key are unaffected.
148 * <p>
149 * If the last value for a key is removed, <code>null</code> will be returned
150 * from a subsequant <code>get(key)</code>.
151 *
152 * @param key the key to remove from
153 * @param value the value to remove
154 * @return the value removed (which was passed in), null if nothing removed
155 */
156 public Object remove(Object key, Object value) {
157 Collection valuesForKey = getCollection(key);
158 if (valuesForKey == null) {
159 return null;
160 }
161 boolean removed = valuesForKey.remove(value);
162 if (removed == false) {
163 return null;
164 }
165 if (valuesForKey.isEmpty()) {
166 remove(key);
167 }
168 return value;
169 }
170
171 /**
172 * Checks whether the map contains the value specified.
173 * <p>
174 * This checks all collections against all keys for the value, and thus could be slow.
175 *
176 * @param value the value to search for
177 * @return true if the map contains the value
178 */
179 public boolean containsValue(Object value) {
180 Set pairs = getMap().entrySet();
181 if (pairs == null) {
182 return false;
183 }
184 Iterator pairsIterator = pairs.iterator();
185 while (pairsIterator.hasNext()) {
186 Map.Entry keyValuePair = (Map.Entry) pairsIterator.next();
187 Collection coll = (Collection) keyValuePair.getValue();
188 if (coll.contains(value)) {
189 return true;
190 }
191 }
192 return false;
193 }
194
195 /**
196 * Adds the value to the collection associated with the specified key.
197 * <p>
198 * Unlike a normal <code>Map</code> the previous value is not replaced.
199 * Instead the new value is added to the collection stored against the key.
200 *
201 * @param key the key to store against
202 * @param value the value to add to the collection at the key
203 * @return the value added if the map changed and null if the map did not change
204 */
205 public Object put(Object key, Object value) {
206 boolean result = false;
207 Collection coll = getCollection(key);
208 if (coll == null) {
209 coll = createCollection(1);
210 result = coll.add(value);
211 if (coll.size() > 0) {
212 // only add if non-zero size to maintain class state
213 getMap().put(key, coll);
214 result = false;
215 }
216 } else {
217 result = coll.add(value);
218 }
219 return (result ? value : null);
220 }
221
222 /**
223 * Override superclass to ensure that MultiMap instances are
224 * correctly handled.
225 * <p>
226 * If you call this method with a normal map, each entry is
227 * added using <code>put(Object,Object)</code>.
228 * If you call this method with a multi map, each entry is
229 * added using <code>putAll(Object,Collection)</code>.
230 *
231 * @param map the map to copy (either a normal or multi map)
232 */
233 public void putAll(Map map) {
234 if (map instanceof MultiMap) {
235 for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
236 Map.Entry entry = (Map.Entry) it.next();
237 Collection coll = (Collection) entry.getValue();
238 putAll(entry.getKey(), coll);
239 }
240 } else {
241 for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
242 Map.Entry entry = (Map.Entry) it.next();
243 put(entry.getKey(), entry.getValue());
244 }
245 }
246 }
247
248 /**
249 * Gets a collection containing all the values in the map.
250 * <p>
251 * This returns a collection containing the combination of values from all keys.
252 *
253 * @return a collection view of the values contained in this map
254 */
255 public Collection values() {
256 Collection vs = values;
257 return (vs != null ? vs : (values = new Values()));
258 }
259
260 /**
261 * Checks whether the collection at the specified key contains the value.
262 *
263 * @param value the value to search for
264 * @return true if the map contains the value
265 */
266 public boolean containsValue(Object key, Object value) {
267 Collection coll = getCollection(key);
268 if (coll == null) {
269 return false;
270 }
271 return coll.contains(value);
272 }
273
274 /**
275 * Gets the collection mapped to the specified key.
276 * This method is a convenience method to typecast the result of <code>get(key)</code>.
277 *
278 * @param key the key to retrieve
279 * @return the collection mapped to the key, null if no mapping
280 */
281 public Collection getCollection(Object key) {
282 return (Collection) getMap().get(key);
283 }
284
285 /**
286 * Gets the size of the collection mapped to the specified key.
287 *
288 * @param key the key to get size for
289 * @return the size of the collection at the key, zero if key not in map
290 */
291 public int size(Object key) {
292 Collection coll = getCollection(key);
293 if (coll == null) {
294 return 0;
295 }
296 return coll.size();
297 }
298
299 /**
300 * Adds a collection of values to the collection associated with
301 * the specified key.
302 *
303 * @param key the key to store against
304 * @param values the values to add to the collection at the key, null ignored
305 * @return true if this map changed
306 */
307 public boolean putAll(Object key, Collection values) {
308 if (values == null || values.size() == 0) {
309 return false;
310 }
311 Collection coll = getCollection(key);
312 if (coll == null) {
313 coll = createCollection(values.size());
314 boolean result = coll.addAll(values);
315 if (coll.size() > 0) {
316 // only add if non-zero size to maintain class state
317 getMap().put(key, coll);
318 result = false;
319 }
320 return result;
321 } else {
322 return coll.addAll(values);
323 }
324 }
325
326 /**
327 * Gets an iterator for the collection mapped to the specified key.
328 *
329 * @param key the key to get an iterator for
330 * @return the iterator of the collection at the key, empty iterator if key not in map
331 */
332 public Iterator iterator(Object key) {
333 if (!containsKey(key)) {
334 return EmptyIterator.INSTANCE;
335 } else {
336 return new ValuesIterator(key);
337 }
338 }
339
340 /**
341 * Gets the total size of the map by counting all the values.
342 *
343 * @return the total size of the map counting all values
344 */
345 public int totalSize() {
346 int total = 0;
347 Collection values = getMap().values();
348 for (Iterator it = values.iterator(); it.hasNext();) {
349 Collection coll = (Collection) it.next();
350 total += coll.size();
351 }
352 return total;
353 }
354
355 /**
356 * Creates a new instance of the map value Collection container
357 * using the factory.
358 * <p>
359 * This method can be overridden to perform your own processing
360 * instead of using the factory.
361 *
362 * @param size the collection size that is about to be added
363 * @return the new collection
364 */
365 protected Collection createCollection(int size) {
366 return (Collection) collectionFactory.create();
367 }
368
369 //-----------------------------------------------------------------------
370 /**
371 * Inner class that provides the values view.
372 */
373 private class Values extends AbstractCollection {
374 public Iterator iterator() {
375 final IteratorChain chain = new IteratorChain();
376 for (Iterator it = keySet().iterator(); it.hasNext();) {
377 chain.addIterator(new ValuesIterator(it.next()));
378 }
379 return chain;
380 }
381
382 public int size() {
383 return totalSize();
384 }
385
386 public void clear() {
387 MultiValueMap.this.clear();
388 }
389 }
390
391 /**
392 * Inner class that provides the values iterator.
393 */
394 private class ValuesIterator implements Iterator {
395 private final Object key;
396 private final Collection values;
397 private final Iterator iterator;
398
399 public ValuesIterator(Object key) {
400 this.key = key;
401 this.values = getCollection(key);
402 this.iterator = values.iterator();
403 }
404
405 public void remove() {
406 iterator.remove();
407 if (values.isEmpty()) {
408 MultiValueMap.this.remove(key);
409 }
410 }
411
412 public boolean hasNext() {
413 return iterator.hasNext();
414 }
415
416 public Object next() {
417 return iterator.next();
418 }
419 }
420
421 /**
422 * Inner class that provides a simple reflection factory.
423 */
424 private static class ReflectionFactory implements Factory {
425 private final Class clazz;
426
427 public ReflectionFactory(Class clazz) {
428 this.clazz = clazz;
429 }
430
431 public Object create() {
432 try {
433 return clazz.newInstance();
434 } catch (Exception ex) {
435 throw new FunctorException("Cannot instantiate class: " + clazz, ex);
436 }
437 }
438 }
439
440 }