001/** A map that associates a key with multiple values.
002
003 Copyright (c) 1997-2013 The Regents of the University of California.
004 All rights reserved.
005 Permission is hereby granted, without written agreement and without
006 license or royalty fees, to use, copy, modify, and distribute this
007 software and its documentation for any purpose, provided that the above
008 copyright notice and the following two paragraphs appear in all copies
009 of this software.
010
011 IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY
012 FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
013 ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
014 THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF
015 SUCH DAMAGE.
016
017 THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
018 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
019 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
020 PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF
021 CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
022 ENHANCEMENTS, OR MODIFICATIONS.
023
024 PT_COPYRIGHT_VERSION_2
025 COPYRIGHTENDKEY
026
027 */
028package ptolemy.util;
029
030import java.util.ArrayList;
031import java.util.Collection;
032import java.util.HashMap;
033import java.util.Set;
034
035///////////////////////////////////////////////////////////////////
036//// MultiHashMap
037
038/**
039MultiHashMap is an implementation of the MultiMap interface. It
040associates a collection of objects to each key. Putting a new
041object under a key adds to the associated collection. Likewise,
042removing a object removes from the collection. It is possible
043that the given object to remove is not contained by the collection.
044In which case, no changes is made and null is returned. The items
045in each collection are ordered by insertion, and duplicates are
046stored in the collections.
047
048For example, given a key K and object O1, and O2:
049
050    MultiHashMap map = new MultiHashMap();
051    map.put(K, O1);
052    map.put(K, O1);
053    map.put(K, O2);
054
055then, map.size(K) would return 3. Iterating through the map returns
056O1, O1, and O2 in order.
057
058 @author Man-Kit Leung, Ben Lickly
059 @version $Id$
060 @param <K> The type of the keys of the multimap.
061 @param <V> The type of the values of the multimap.
062 @since Ptolemy II 8.0
063 @Pt.ProposedRating Red (mankit)
064 @Pt.AcceptedRating Red (mankit)
065 */
066
067public class MultiHashMap<K, V> {
068
069    ///////////////////////////////////////////////////////////////////
070    ////                         public methods                    ////
071
072    /** Get the collection of values mapped to by a given key.
073     *  @param key The index into the multimap.
074     *  @return The collection of values at that index.
075     */
076    public Collection<V> get(K key) {
077        return _map.get(key);
078    }
079
080    /** Return a set of all key values represented by this multimap.
081     *  @return A set of values that are keys of this multimap.
082     */
083    public Set<K> keySet() {
084        return _map.keySet();
085    }
086
087    /** Return whether or not this multimap is empty.
088     *  @return True, if the map is empty. False, otherwise.
089     */
090    public boolean isEmpty() {
091        return _map.isEmpty();
092    }
093
094    /** Add the value to the collection associated with the specified key.
095     *  @param key The specified key.
096     *  @param value The specified value to add to the collection.
097     */
098    public void put(K key, V value) {
099        Collection<V> values = _map.get(key);
100        if (values == null) {
101            values = new ArrayList<V>();
102            _map.put(key, values);
103        }
104        values.add(value);
105    }
106
107    /** Remove a specified value from the map. The value is removed
108     *  from the collection mapped to the specified key. If this is
109     *  the last value removed from the given key, the specified key
110     *  is also removed from the map. Subsequent call to get(key) will
111     *  return false.
112     *  @param key The specified key to remove the value from.
113     *  @param value The specified value to remove.
114     *  @return True, if the value was removed. False, otherwise.
115     */
116    public boolean remove(K key, V value) {
117        Collection<V> values = _map.get(key);
118
119        if (values == null) {
120            return false;
121        } else {
122            boolean removed = values.remove(value);
123            if (values.size() == 0) {
124                _map.remove(key);
125            }
126            return removed;
127        }
128    }
129
130    /** Return the size of the collection mapped to the specified key.
131     *  @param key The specified key.
132     *  @return The size of the collection, or zero if key is
133     *    not in the map.
134     */
135    public int size(Object key) {
136        Collection<V> values = _map.get(key);
137
138        if (values == null) {
139            return 0;
140        } else {
141            return values.size();
142        }
143    }
144
145    /** Return a view of the collection containing all values in the map.
146     *  This is a collection containing the union of each collection
147     *  mapped to the keys.
148     *  @return A view of all values contained in this map.
149     */
150    public Collection<V> values() {
151        Collection<V> result = new ArrayList<V>();
152        for (Collection<V> values : _map.values()) {
153            result.addAll(values);
154        }
155        return result;
156    }
157
158    ///////////////////////////////////////////////////////////////////
159    ////                         private variables                 ////
160
161    /** The HashMap that stores the mappings of this MultiMap.  The multimap
162     *  is constructed by having the values of the HashMap be collections.
163     */
164    private HashMap<K, Collection<V>> _map = new HashMap<K, Collection<V>>();
165}