001 package biweekly.util;
002
003 import java.util.ArrayList;
004 import java.util.Collection;
005 import java.util.Collections;
006 import java.util.Iterator;
007 import java.util.LinkedHashMap;
008 import java.util.List;
009 import java.util.Map;
010 import java.util.Set;
011
012 /*
013 Copyright (c) 2013, Michael Angstadt
014 All rights reserved.
015
016 Redistribution and use in source and binary forms, with or without
017 modification, are permitted provided that the following conditions are met:
018
019 1. Redistributions of source code must retain the above copyright notice, this
020 list of conditions and the following disclaimer.
021 2. Redistributions in binary form must reproduce the above copyright notice,
022 this list of conditions and the following disclaimer in the documentation
023 and/or other materials provided with the distribution.
024
025 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
026 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
027 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
028 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
029 ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
030 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
031 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
032 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
033 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
034 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
035 */
036
037 /**
038 * A multimap that uses {@link List} objects to store its values. The internal
039 * {@link Map} implementation is a {@link LinkedHashMap} that uses
040 * {@link ArrayList} for its values.
041 * @author Michael Angstadt
042 * @param <K> the key
043 * @param <V> the value
044 */
045 public class ListMultimap<K, V> implements Iterable<Map.Entry<K, List<V>>> {
046 private final Map<K, List<V>> map;
047
048 /**
049 * Creates a new multi map.
050 */
051 public ListMultimap() {
052 map = new LinkedHashMap<K, List<V>>();
053 }
054
055 /**
056 * Creates a new multi map.
057 * @param initialCapacity the initial capacity of the underlying map.
058 */
059 public ListMultimap(int initialCapacity) {
060 map = new LinkedHashMap<K, List<V>>(initialCapacity);
061 }
062
063 /**
064 * Copy constructor.
065 * @param orig the multimap to copy from
066 */
067 public ListMultimap(ListMultimap<K, V> orig) {
068 this();
069 for (Map.Entry<K, List<V>> entry : orig) {
070 List<V> values = new ArrayList<V>(entry.getValue());
071 map.put(entry.getKey(), values);
072 }
073 }
074
075 /**
076 * Adds a value to the multimap.
077 * @param key the key
078 * @param value the value to add
079 */
080 public void put(K key, V value) {
081 List<V> values = get(key, true);
082 values.add(value);
083 }
084
085 /**
086 * Adds multiple values to the multimap.
087 * @param key the key
088 * @param values the values to add
089 */
090 public void putAll(K key, Collection<V> values) {
091 List<V> existingValues = get(key, true);
092 existingValues.addAll(values);
093 }
094
095 /**
096 * Gets the values associated with the key.
097 * @param key the key
098 * @return the list of values or empty list if the key doesn't exist
099 */
100 public List<V> get(K key) {
101 return get(key, false);
102 }
103
104 /**
105 * Gets the values associated with the key.
106 * @param key the key
107 * @param add true to add an empty element to the map if the key doesn't
108 * exist, false not to
109 * @return the list of values or empty list if the key doesn't exist
110 */
111 private List<V> get(K key, boolean add) {
112 key = sanitizeKey(key);
113 List<V> values = map.get(key);
114 if (values == null) {
115 values = new ArrayList<V>();
116 if (add) {
117 map.put(key, values);
118 }
119 }
120 return values;
121 }
122
123 /**
124 * Gets the first value that's associated with a key.
125 * @param key the key
126 * @return the first value or null if the key doesn't exist
127 */
128 public V first(K key) {
129 List<V> values = get(key);
130 return (values == null || values.isEmpty()) ? null : values.get(0);
131 }
132
133 /**
134 * Determines whether the given key exists.
135 * @param key the key
136 * @return true if the key exists, false if not
137 */
138 public boolean containsKey(K key) {
139 return map.containsKey(key);
140 }
141
142 /**
143 * Removes a particular value.
144 * @param key the key
145 * @param value the value to remove
146 * @return true if the multimap contained the value, false if not
147 */
148 public boolean remove(K key, V value) {
149 List<V> values = map.get(sanitizeKey(key));
150 if (values != null) {
151 return values.remove(value);
152 }
153 return false;
154 }
155
156 /**
157 * Removes all the values associated with a key
158 * @param key the key to remove
159 * @return the removed values or empty list if the key doesn't exist
160 */
161 public List<V> removeAll(K key) {
162 List<V> removed = map.remove(sanitizeKey(key));
163 return (removed == null) ? Collections.<V> emptyList() : removed;
164 }
165
166 /**
167 * Replaces all values with the given value.
168 * @param key the key
169 * @param value the value with which to replace all existing values, or null
170 * will remove all values
171 * @return the values that were replaced
172 */
173 public List<V> replace(K key, V value) {
174 List<V> replaced = removeAll(key);
175 if (value != null) {
176 put(key, value);
177 }
178 return replaced;
179 }
180
181 /**
182 * Replaces all values with the given values.
183 * @param key the key
184 * @param values the values with which to replace all existing values
185 * @return the values that were replaced
186 */
187 public List<V> replace(K key, Collection<V> values) {
188 List<V> replaced = removeAll(key);
189 if (values != null && !values.isEmpty()) {
190 putAll(key, values);
191 }
192 return replaced;
193 }
194
195 /**
196 * Clears all entries from the multimap.
197 */
198 public void clear() {
199 map.clear();
200 }
201
202 /**
203 * Returns all the keys.
204 * @return all the keys
205 */
206 public Set<K> keySet() {
207 return map.keySet();
208 }
209
210 /**
211 * Returns all the values.
212 * @return all the values
213 */
214 public Collection<V> values() {
215 Collection<V> list = new ArrayList<V>();
216 for (List<V> value : map.values()) {
217 list.addAll(value);
218 }
219 return list;
220 }
221
222 /**
223 * Determines if the multimap is empty or not.
224 * @return true if it's empty, false if not
225 */
226 public boolean isEmpty() {
227 return size() == 0;
228 }
229
230 /**
231 * Returns the number of values in the map.
232 * @return the number of values
233 */
234 public int size() {
235 int size = 0;
236 for (List<V> value : map.values()) {
237 size += value.size();
238 }
239 return size;
240 }
241
242 /**
243 * Gets the underlying {@link Map} object.
244 * @return the underlying {@link Map} object
245 */
246 public Map<K, List<V>> getMap() {
247 return map;
248 }
249
250 /**
251 * Modifies a given key before it is used to interact with the internal map.
252 * This method is meant to be overridden by child classes if necessary.
253 * @param key the key
254 * @return the modified key (by default, the key is returned as-is)
255 */
256 protected K sanitizeKey(K key) {
257 return key;
258 }
259
260 //@Override
261 public Iterator<Map.Entry<K, List<V>>> iterator() {
262 return map.entrySet().iterator();
263 }
264
265 @Override
266 public String toString() {
267 return map.toString();
268 }
269 }