001/** 002 * 003 * Copyright © 2015 Florian Schmaus 004 * 005 * Licensed under the Apache License, Version 2.0 (the "License"); 006 * you may not use this file except in compliance with the License. 007 * 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 */ 017package org.jivesoftware.smack.util; 018 019import java.util.ArrayList; 020import java.util.Collections; 021import java.util.LinkedHashMap; 022import java.util.LinkedHashSet; 023import java.util.List; 024import java.util.Map; 025import java.util.Set; 026 027/** 028 * A lightweight implementation of a MultiMap, that is a Map that is able to hold multiple values for every key. 029 * <p> 030 * This MultiMap uses a {@link LinkedHashMap} together with a {@link ArrayList} in order to keep the order of its entries. 031 * </p> 032 * 033 * @param <K> the type of the keys the map uses. 034 * @param <V> the type of the values the map uses. 035 */ 036public class MultiMap<K,V> { 037 038 /** 039 * The constant value {@value}. 040 */ 041 public static final int DEFAULT_MAP_SIZE = 6; 042 043 private static final int ENTRY_LIST_SIZE = 3; 044 045 private final Map<K, List<V>> map; 046 047 /** 048 * Constructs a new MultiMap with a initial capacity of {@link #DEFAULT_MAP_SIZE}. 049 */ 050 public MultiMap() { 051 this(DEFAULT_MAP_SIZE); 052 } 053 054 /** 055 * Constructs a new MultiMap. 056 * 057 * @param size the initial capacity. 058 */ 059 public MultiMap(int size) { 060 map = new LinkedHashMap<>(size); 061 } 062 063 public int size() { 064 int size = 0; 065 for (List<V> list : map.values()) { 066 size += list.size(); 067 } 068 return size; 069 } 070 071 public boolean isEmpty() { 072 return map.isEmpty(); 073 } 074 075 public boolean containsKey(Object key) { 076 return map.containsKey(key); 077 } 078 079 public boolean containsValue(Object value) { 080 for (List<V> list : map.values()) { 081 if (list.contains(value)) { 082 return true; 083 } 084 } 085 return false; 086 } 087 088 /** 089 * Get the first value for the given key, or <code>null</code> if there are no entries. 090 * 091 * @param key 092 * @return the first value or null. 093 */ 094 public V getFirst(Object key) { 095 List<V> res = getAll(key); 096 if (res.isEmpty()) { 097 return null; 098 } else { 099 return res.iterator().next(); 100 } 101 } 102 103 /** 104 * Get all values for the given key. Returns the empty set if there are none. 105 * <p> 106 * Changes to the returned set will update the underlying MultiMap if the return set is not empty. 107 * </p> 108 * 109 * @param key 110 * @return all values for the given key. 111 */ 112 public List<V> getAll(Object key) { 113 List<V> res = map.get(key); 114 if (res == null) { 115 res = Collections.emptyList(); 116 } 117 return res; 118 } 119 120 public boolean put(K key, V value) { 121 boolean keyExisted; 122 List<V> list = map.get(key); 123 if (list == null) { 124 list = new ArrayList<>(ENTRY_LIST_SIZE); 125 list.add(value); 126 map.put(key, list); 127 keyExisted = false; 128 } else { 129 list.add(value); 130 keyExisted = true; 131 } 132 return keyExisted; 133 } 134 135 /** 136 * Removes all mappings for the given key and returns the first value if there where mappings or <code>null</code> if not. 137 * 138 * @param key 139 * @return the first value of the given key or null. 140 */ 141 public V remove(Object key) { 142 List<V> res = map.remove(key); 143 if (res == null) { 144 return null; 145 } 146 assert (!res.isEmpty()); 147 return res.iterator().next(); 148 } 149 150 /** 151 * Remove the mapping of the given key to the value. 152 * <p> 153 * Returns <code>true</code> if the mapping was removed and <code>false</code> if the mapping did not exist. 154 * </p> 155 * 156 * @param key 157 * @param value 158 * @return true if the mapping was removed, false otherwise. 159 */ 160 public boolean removeOne(Object key, V value) { 161 List<V> list = map.get(key); 162 if (list == null) { 163 return false; 164 } 165 boolean res = list.remove(value); 166 if (list.isEmpty()) { 167 // Remove the key also if the value set is now empty 168 map.remove(key); 169 } 170 return res; 171 } 172 173 public void putAll(Map<? extends K, ? extends V> map) { 174 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 175 put(entry.getKey(), entry.getValue()); 176 } 177 } 178 179 public void clear() { 180 map.clear(); 181 } 182 183 public Set<K> keySet() { 184 return map.keySet(); 185 } 186 187 /** 188 * Returns a new list containing all values of this multi map. 189 * 190 * @return a new list with all values. 191 */ 192 public List<V> values() { 193 List<V> values = new ArrayList<>(size()); 194 for (List<V> list : map.values()) { 195 values.addAll(list); 196 } 197 return values; 198 } 199 200 public Set<Map.Entry<K, V>> entrySet() { 201 Set<Map.Entry<K, V>> entrySet = new LinkedHashSet<>(size()); 202 for (Map.Entry<K, List<V>> entries : map.entrySet()) { 203 K key = entries.getKey(); 204 for (V value : entries.getValue()) { 205 entrySet.add(new SimpleMapEntry<>(key, value)); 206 } 207 } 208 return entrySet; 209 } 210 211 private static final class SimpleMapEntry<K, V> implements Map.Entry<K, V> { 212 213 private final K key; 214 private V value; 215 216 private SimpleMapEntry(K key, V value) { 217 this.key = key; 218 this.value = value; 219 } 220 221 @Override 222 public K getKey() { 223 return key; 224 } 225 226 @Override 227 public V getValue() { 228 return value; 229 } 230 231 @Override 232 public V setValue(V value) { 233 V tmp = this.value; 234 this.value = value; 235 return tmp; 236 } 237 } 238 239}