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