1 package org.djutils.multikeymap;
2
3 import java.util.Arrays;
4 import java.util.LinkedHashMap;
5 import java.util.List;
6 import java.util.Map;
7 import java.util.Set;
8 import java.util.function.Supplier;
9
10 import org.djutils.exceptions.Throw;
11
12 /**
13 * Store for data indexed by a combination of objects. An important difference with a normal (Linked-)HashMap is that the
14 * <code>getValue</code> method has a <code>Supplier</code> argument that will be invoked when no value was stored under the
15 * provided combination of keys. The value yielded by the <code>Supplier</code> is then stored under that key combination. If
16 * this behavior is not wanted, the user can provide the null value for the <code>Supplier</code> argument. The map can store
17 * null values, but on retrieval these are indistinguishable from values that were never set. No key values may be null.
18 * <p>
19 * Copyright (c) 2013-2023 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
20 * BSD-style license. See <a href="https://djutils.org/docs/current/djutils/licenses.html">DJUTILS License</a>.
21 * <p>
22 * @version $Revision$, $LastChangedDate$, by $Author$, initial version 20 apr. 2018 <br>
23 * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
24 * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
25 * @author <a href="http://www.transport.citg.tudelft.nl">Wouter Schakel</a>
26 * @param <T> value type
27 */
28 public class MultiKeyMap<T>
29 {
30
31 /** Array of key types. */
32 private final Class<?>[] keyTypes;
33
34 /** Map with keys and values at this level. */
35 private final Map<Object, Object> map = new LinkedHashMap<>();
36
37 /**
38 * Construct a new MultiKeyMap.
39 * @param keyTypes Class<?>...; the types of the keys
40 */
41 public MultiKeyMap(final Class<?>... keyTypes)
42 {
43 Throw.when(keyTypes.length < 1, IllegalArgumentException.class, "keyTypes may not be empty");
44 this.keyTypes = keyTypes;
45 }
46
47 /**
48 * Retrieve a value from this MultiKeyMap. Can create a new entry if it does not exist yet.
49 * @param supplier Supplier<T>; supplier of {@code T} in case the leaf does not exist yet. Set this to
50 * <code>null</code> to suppress creation of new branches and a new leaf
51 * @param keys Object...; list of key objects
52 * @return T; the existing value, or the value that was obtained through the <code>supplier</code>. Returns
53 * <code>null</code> if the leaf does not exist and <code>supplier</code> is <code>null</code>
54 */
55 public T get(final Supplier<T> supplier, final Object... keys)
56 {
57 return getValue(supplier, Arrays.asList(keys));
58 }
59
60 /**
61 * Retrieve a value from this MultiKeyMap.
62 * @param keys Object...; the key objects
63 * @return T; value, or null if no value is stored under the provided key objects
64 */
65 public T get(final Object... keys)
66 {
67 return getValue(null, Arrays.asList(keys));
68 }
69
70 /**
71 * Retrieve a sub map.
72 * @param keys Object...; the key objects (must be at least one item shorter than the full depth)
73 * @return MultiKeyMap<T>; the sub map
74 */
75 public MultiKeyMap<T> getSubMap(final Object... keys)
76 {
77 Throw.when(keys.length >= this.keyTypes.length, IllegalArgumentException.class, "Too many keys");
78 return getSubMap(false, Arrays.asList(keys));
79 }
80
81 /**
82 * Put (add or replace) a value in this MultiKeyMap.
83 * @param newValue T; the new value
84 * @param keys Object...; the key objects
85 * @return T; the previous value stored under the key objects, or null if no value was currently stored under the key
86 * objects
87 */
88 public T put(final T newValue, final Object... keys)
89 {
90 List<Object> keyList = Arrays.asList(keys);
91 Map<Object, T> branch = getFinalMap(true, keyList);
92 Object key = getFinalKey(keyList);
93 return branch.put(key, newValue);
94 }
95
96 /**
97 * Select and verify the type of the last key.
98 * @param keys List<Object>; the keys
99 * @return Object; the last element of keys
100 */
101 private Object getFinalKey(final List<Object> keys)
102 {
103 Object key = keys.get(keys.size() - 1);
104 Throw.whenNull(key, "key may not be null");
105 Throw.when(key != null && !this.keyTypes[keys.size() - 1].isAssignableFrom(key.getClass()),
106 IllegalArgumentException.class, "Key %s is not of %s.", key, this.keyTypes[keys.size() - 1]);
107 return key;
108 }
109
110 /**
111 * Walk the tree up to (but not including) the last level.
112 * @param createBranches boolean; if true; missing branches are constructed; if false; missing branches cause this method to
113 * return null;
114 * @param keys List<Object>; the keys.
115 * @return Map<T>; the lowest level map
116 */
117 @SuppressWarnings("unchecked")
118 private Map<Object, T> getFinalMap(final boolean createBranches, final List<Object> keys)
119 {
120 Throw.when(keys.size() != this.keyTypes.length, IllegalArgumentException.class, "Incorrect number of keys.");
121 MultiKeyMap<T> finalMap = getSubMap(createBranches, keys.subList(0, keys.size() - 1));
122 if (null == finalMap)
123 {
124 return null;
125 }
126 return (Map<Object, T>) finalMap.map;
127 }
128
129 /**
130 * Retrieve a value. This uses a {@code List} rather than an array because that is easier to slice.
131 * @param supplier Supplier<T>; supplier of {@code T} for if it wasn't cached yet. Set <code>supplier</code> to null
132 * to suppress construction of missing branches and a leaf
133 * @param keys List<Object>; list of key objects
134 * @return T; value, or null if no value was stored under the specified list of keys and <code>supplier</code> was null
135 */
136 private T getValue(final Supplier<T> supplier, final List<Object> keys)
137 {
138 Throw.when(keys.size() != this.keyTypes.length, IllegalArgumentException.class, "Wrong number of keys");
139 Map<Object, T> branch = getFinalMap(null != supplier, keys);
140 if (null == branch)
141 {
142 return null;
143 }
144 Object key = getFinalKey(keys);
145 T leaf = branch.get(key);
146 if (leaf == null) // Leaf does not exist, yet
147 {
148 if (null == supplier)
149 {
150 return null; // Caller does not want to create a new leaf
151 }
152 // Create a new leaf
153 leaf = supplier.get();
154 branch.put(key, leaf);
155 }
156 return leaf;
157 }
158
159 /**
160 * Return set of key objects on this level.
161 * @param keys Object...; list of key objects (may be empty to select the key set at the top level
162 * @return Set; set of key objects on this level. This is not a safe copy; this set reflects subsequent changes in this
163 * MultiKeyMap and modifying this set would modify this MultiKeyMap (potentially making it inconsistent).
164 */
165 public Set<Object> getKeys(final Object... keys)
166 {
167 return getSubMap(false, Arrays.asList(keys)).map.keySet();
168 }
169
170 /**
171 * Walk the tree to the requested branch.
172 * @param createMissingBranches boolean; if true; missing branches will be created.
173 * @param keys List<Object>; the keys
174 * @return MultiKeyMap<T>; the branch at the end of the list of keys, or null if that branch does not exist and
175 * <code>createMissingBranches</code> is false
176 */
177 @SuppressWarnings("unchecked")
178 private MultiKeyMap<T> getSubMap(final boolean createMissingBranches, final List<Object> keys)
179 {
180 if (keys.size() == 0)
181 {
182 return this;
183 }
184 Throw.when(keys.size() > this.keyTypes.length, IllegalArgumentException.class, "Too many keys");
185 Throw.when(keys.get(0) != null && !this.keyTypes[0].isAssignableFrom(keys.get(0).getClass()),
186 IllegalArgumentException.class, "Key %s is not of %s.", keys.get(0), this.keyTypes[0]);
187 MultiKeyMap<T> subMap = (MultiKeyMap<T>) this.map.get(keys.get(0));
188 if (null == subMap && !createMissingBranches)
189 {
190 return null; // Caller does not want to create new branches
191 }
192 if (null == subMap)
193 {
194 // Create branch with 1 less key
195 Class<Object>[] subTypes = new Class[this.keyTypes.length - 1];
196 System.arraycopy(this.keyTypes, 1, subTypes, 0, this.keyTypes.length - 1);
197 subMap = new MultiKeyMap<T>(subTypes);
198 this.map.put(keys.get(0), subMap);
199 }
200 return (subMap.getSubMap(createMissingBranches, keys.subList(1, keys.size())));
201 }
202
203 /**
204 * Clears the mapping for a key combination.
205 * @param keys Object...; key combination to clear the map for
206 * @return Object; object that was previously mapped to the key combination, or {@code null} if it was not cached.
207 */
208 public Object clear(final Object... keys)
209 {
210 return clear(Arrays.asList(keys));
211
212 }
213
214 /**
215 * Clear the mapping for a key combination.
216 * @param keys List<Object>; key combination to clear the map for
217 * @return Object; object that was previously mapped to the key combination, or {@code null} if it was not cached.
218 */
219 @SuppressWarnings("unchecked")
220 private Object clear(final List<Object> keys)
221 {
222 if (keys.size() == 0)
223 {
224 this.map.clear();
225 return this;
226 }
227 MultiKeyMap<T> subMap = getSubMap(false, keys.subList(0, keys.size() - 1));
228 if (null == subMap)
229 {
230 return null;
231 }
232 if (keys.size() == this.keyTypes.length)
233 {
234 Map<Object, T> endMap = (Map<Object, T>) subMap.map;
235 return endMap.remove(keys.get(keys.size() - 1));
236 }
237 return subMap.map.remove(keys.get(keys.size() - 1));
238 }
239
240 /** {@inheritDoc} */
241 @Override
242 public String toString()
243 {
244 return "MultiKeyMap [types=" + Arrays.toString(this.keyTypes) + ", map=" + this.map + "]";
245 }
246
247 }