1 /*******************************************************************************
\r
2 * Copyright (c) 2016 Association for Decentralized Information Management
\r
3 * in Industry THTH ry.
\r
4 * All rights reserved. This program and the accompanying materials
\r
5 * are made available under the terms of the Eclipse Public License v1.0
\r
6 * which accompanies this distribution, and is available at
\r
7 * http://www.eclipse.org/legal/epl-v10.html
\r
10 * Semantum Oy - initial API and implementation
\r
11 *******************************************************************************/
\r
12 package org.simantics.utils.datastructures;
\r
14 import java.lang.reflect.Array;
\r
15 import java.util.Arrays;
\r
16 import java.util.Collection;
\r
17 import java.util.Iterator;
\r
18 import java.util.List;
\r
19 import java.util.Map;
\r
20 import java.util.NoSuchElementException;
\r
21 import java.util.Set;
\r
24 * A space-optimized immutable Map implementation where keys and values are
\r
25 * interlaced in one Object array.
\r
28 * Both map keys and values are specified as separate typed arrays that must be
\r
29 * equally sized. This provides for space-optimization by allowing reusable key
\r
30 * array instances since the keys cannot be modified.
\r
33 * The map should be considered immutable, but it does allow modification of a
\r
34 * value for an existing key as this only changes the value, the key will remain
\r
37 * The nested class {@link InterlacedArrayMapBuilder} allows easy and
\r
38 * minimal-allocation construction of an {@link InterlacedArrayMap}. Use
\r
39 * {@link InterlacedArrayMap#builder()} or
\r
40 * {@link InterlacedArrayMap#builder(int)} to create the builder. The idea is to
\r
41 * minimize the space allocated for the {@link #data} field in the built map
\r
42 * instance. If the builder is completely filled up, i.e. its capacity matches
\r
43 * added key, value pair count, the array it contains is directly transferred to
\r
44 * the built map instance without creating any extra copies. So if possible, set
\r
45 * the correct initial capacity for the builder.
\r
47 * @author Tuukka Lehtonen
\r
54 public class InterlacedArrayMap<K, V> implements Map<K, V> {
\r
56 final Object[] data;
\r
57 Set<Map.Entry<K, V>> entrySet;
\r
59 Collection<V> valueSet;
\r
61 public static class InterlacedArrayMapBuilder<K, V> {
\r
63 private Object[] elementData;
\r
64 private int count = 0;
\r
66 private InterlacedArrayMapBuilder(int initialCapacity) {
\r
67 this.elementData = new Object[initialCapacity*2];
\r
70 public void add(K key, V v) {
\r
71 ensureCapacityInternal(count + 2);
\r
72 elementData[count] = key;
\r
73 elementData[count+1] = v;
\r
77 private void ensureCapacityInternal(int minCapacity) {
\r
78 // overflow-conscious code
\r
79 if (minCapacity - elementData.length > 0)
\r
84 * The maximum size of array to allocate.
\r
85 * Some VMs reserve some header words in an array.
\r
86 * Attempts to allocate larger arrays may result in
\r
87 * OutOfMemoryError: Requested array size exceeds VM limit
\r
89 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
\r
92 * Increases the capacity to ensure that it can hold at least the
\r
93 * number of elements specified by the minimum capacity argument.
\r
95 * @param minCapacity the desired minimum capacity
\r
97 private void grow(int minCapacity) {
\r
98 // overflow-conscious code
\r
99 int oldCapacity = elementData.length;
\r
100 int newCapacity = oldCapacity + (oldCapacity >> 1);
\r
101 if (newCapacity - minCapacity < 0)
\r
102 newCapacity = minCapacity;
\r
103 if (newCapacity - MAX_ARRAY_SIZE > 0)
\r
104 newCapacity = hugeCapacity(minCapacity);
\r
105 // minCapacity is usually close to size, so this is a win:
\r
106 elementData = Arrays.copyOf(elementData, newCapacity);
\r
109 private static int hugeCapacity(int minCapacity) {
\r
110 if (minCapacity < 0) // overflow
\r
111 throw new OutOfMemoryError();
\r
112 return (minCapacity > MAX_ARRAY_SIZE) ?
\r
113 Integer.MAX_VALUE :
\r
117 public InterlacedArrayMap<K, V> build() {
\r
118 return count == elementData.length
\r
119 ? new InterlacedArrayMap<>(elementData)
\r
120 : new InterlacedArrayMap<>(Arrays.copyOf(elementData, count));
\r
126 * Default initial capacity.
\r
128 private static final int DEFAULT_CAPACITY = 10;
\r
131 * @return a map builder with the default initial capacity of
\r
132 * {@value #DEFAULT_CAPACITY} key,value pairs.
\r
134 public static <K, V> InterlacedArrayMapBuilder<K, V> builder() {
\r
135 return new InterlacedArrayMapBuilder<K, V>(DEFAULT_CAPACITY);
\r
139 * @param initialCapacity
\r
140 * the amount of key,value pairs to fit into the builder
\r
141 * initially without having to reallocate anything
\r
142 * @return a map builder with the specified initial key,value pair capacity
\r
144 public static <K, V> InterlacedArrayMapBuilder<K, V> builder(int initialCapacity) {
\r
145 return new InterlacedArrayMapBuilder<K, V>(initialCapacity);
\r
149 * Just like {@link #InterlacedArrayMap(Object[])} but takes the array of
\r
150 * objects as a collection.
\r
152 * @param keysAndValues
\r
153 * an interlaced array where where (key, value) pairs are
\r
154 * repeated in consecutive indexes of the array
\r
155 * @throws IllegalArgumentException
\r
156 * if the array size is not divisible by two
\r
157 * @throws NullPointerException
\r
158 * if either parameter is <code>null</code>
\r
160 public InterlacedArrayMap(List<?> keysAndValues) {
\r
161 this(keysAndValues.toArray());
\r
165 * Constructs new ArrayMap based on an interlaced array of keys and values.
\r
166 * The array size must be divisible by two.
\r
168 * @param keysAndValues
\r
169 * an interlaced array where where (key, value) pairs are
\r
170 * repeated in consecutive indexes of the array
\r
171 * @throws IllegalArgumentException
\r
172 * if the array size is not divisible by two
\r
173 * @throws NullPointerException
\r
174 * if either parameter is <code>null</code>
\r
176 public InterlacedArrayMap(Object[] keysAndValues) {
\r
177 // NPE is caught by this.
\r
178 if ((keysAndValues.length & 1) != 0)
\r
179 throw new IllegalArgumentException("key and value array size (" + keysAndValues.length + ") is not divisible by 2");
\r
180 this.data = keysAndValues;
\r
184 public Set<Map.Entry<K, V>> entrySet() {
\r
185 return (entrySet != null) ? entrySet : (entrySet = new EntrySet());
\r
189 public void clear() {
\r
190 throw new UnsupportedOperationException();
\r
194 public boolean containsKey(Object key) {
\r
195 return contains(0, key);
\r
199 public boolean containsValue(Object value) {
\r
200 return contains(1, value);
\r
203 @SuppressWarnings("unchecked")
\r
205 public V get(Object key) {
\r
207 for (int i = 0; i < data.length; i += 2) {
\r
208 if (data[i] == null) {
\r
209 return (V) data[i+1];
\r
214 int hash = key.hashCode();
\r
215 for (int i = 0; i < data.length; i += 2) {
\r
216 Object k = data[i];
\r
217 if (k == key || (hash == k.hashCode() && key.equals(k))) {
\r
218 return (V) data[i+1];
\r
225 public boolean isEmpty() {
\r
226 return data.length == 0;
\r
230 public Set<K> keySet() {
\r
231 return (keySet != null) ? keySet : (keySet = new OffsetSet<K>(0));
\r
234 @SuppressWarnings("unchecked")
\r
236 public V put(K key, V value) {
\r
238 for (int i = 0; i < data.length; i += 2) {
\r
239 if (data[i] == null) {
\r
240 V old = (V) data[i+1];
\r
245 throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");
\r
247 int hash = key.hashCode();
\r
248 for (int i = 0; i < data.length; i += 2) {
\r
250 if (k == key || (hash == k.hashCode() && key.equals(k))) {
\r
251 V old = (V) data[i+1];
\r
256 throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");
\r
260 public void putAll(Map<? extends K, ? extends V> m) {
\r
261 for (K k : m.keySet()) {
\r
262 if (!containsKey(k))
\r
263 throw new UnsupportedOperationException("key " + k + " not present in ArrayMap");
\r
265 for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {
\r
266 put(entry.getKey(), entry.getValue());
\r
271 public V remove(Object key) {
\r
272 throw new UnsupportedOperationException();
\r
276 public int size() {
\r
277 return data.length >> 1;
\r
281 public Collection<V> values() {
\r
282 return valueSet != null ? valueSet : (valueSet = new OffsetSet<V>(1));
\r
285 private boolean contains(int offset, Object o) {
\r
286 int len = data.length;
\r
288 for (int i = offset; i < len; i += 2)
\r
289 if (data[i] == null)
\r
293 int hash = o.hashCode();
\r
294 for (int i = offset; i < len; i += 2) {
\r
295 Object k = data[i];
\r
296 if (o == k || (hash == k.hashCode() && o.equals(k)))
\r
302 class OffsetSet<T> extends ImmutableSet<T> implements Set<T> {
\r
304 private final int offset;
\r
306 public OffsetSet(int offset) {
\r
307 this.offset = offset;
\r
311 public boolean contains(Object o) {
\r
312 return InterlacedArrayMap.this.contains(offset, o);
\r
316 public boolean containsAll(Collection<?> c) {
\r
324 public boolean isEmpty() {
\r
325 return data.length == 0;
\r
329 public Iterator<T> iterator() {
\r
330 return new ImmutableIterator<T>() {
\r
334 public boolean hasNext() {
\r
335 return i < data.length;
\r
340 if (i >= data.length)
\r
341 throw new NoSuchElementException("no more elements (" + data.length + " walked)");
\r
342 @SuppressWarnings("unchecked")
\r
351 public int size() {
\r
352 return data.length >> 1;
\r
356 public Object[] toArray() {
\r
357 int len = data.length >> 1;
\r
358 Object[] a = new Object[len];
\r
359 for (int i = 0; i < len; ++i)
\r
360 a[i] = data[i*2+offset];
\r
364 @SuppressWarnings("unchecked")
\r
366 public <TT> TT[] toArray(TT[] a) {
\r
367 int len = data.length >> 1;
\r
368 if (a.length < len) {
\r
369 Class<?> clazz = a.getClass();
\r
370 // Make a new array of a's runtime type, but my contents:
\r
371 a = ((Object)clazz == (Object)Object[].class)
\r
372 ? (TT[]) new Object[len]
\r
373 : (TT[]) Array.newInstance(clazz.getComponentType(), len);
\r
375 for (int i = 0; i < len; ++i)
\r
376 a[i] = (TT) data[i*2+offset];
\r
377 if (a.length > len)
\r
383 class EntrySet extends ImmutableSet<Map.Entry<K, V>> implements Set<Map.Entry<K, V>> {
\r
386 public boolean contains(Object o) {
\r
387 throw new UnsupportedOperationException("TODO");
\r
391 public boolean containsAll(Collection<?> c) {
\r
399 public boolean isEmpty() {
\r
400 return data.length == 0;
\r
404 public Iterator<Map.Entry<K, V>> iterator() {
\r
405 return new ImmutableIterator<Map.Entry<K, V>>() {
\r
409 public boolean hasNext() {
\r
410 return i < data.length;
\r
414 public Map.Entry<K, V> next() {
\r
415 if (i >= data.length)
\r
416 throw new NoSuchElementException("no more elements (" + (data.length >> 1) + " walked)");
\r
417 @SuppressWarnings("unchecked")
\r
418 Map.Entry<K, V> entry = new ArrayMapEntry<K, V>(i, (K) data[i], (V) data[i+1]);
\r
426 public int size() {
\r
427 return data.length >> 1;
\r
433 * Returns the hash code value for this map. The hash code of a map is
\r
434 * defined to be the sum of the hash codes of each entry in the map's
\r
435 * <tt>entrySet()</tt> view. This ensures that <tt>m1.equals(m2)</tt>
\r
436 * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two maps
\r
437 * <tt>m1</tt> and <tt>m2</tt>, as required by the general contract of
\r
438 * {@link Object#hashCode}.
\r
440 * <p>This implementation iterates over <tt>entrySet()</tt>, calling
\r
441 * {@link Map.Entry#hashCode hashCode()} on each element (entry) in the
\r
442 * set, and adding up the results.
\r
444 * @return the hash code value for this map
\r
445 * @see Map.Entry#hashCode()
\r
446 * @see Object#equals(Object)
\r
447 * @see Set#equals(Object)
\r
450 @SuppressWarnings("unchecked")
\r
451 public int hashCode() {
\r
453 int l = data.length;
\r
454 for (int i = 0; i < l; i += 2) {
\r
455 K key = (K) data[i];
\r
456 V value = (V) data[i+1];
\r
457 int hash = (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());
\r
464 * Compares the specified object with this map for equality. Returns
\r
465 * <tt>true</tt> if the given object is also a map and the two maps
\r
466 * represent the same mappings. More formally, two maps <tt>m1</tt> and
\r
467 * <tt>m2</tt> represent the same mappings if
\r
468 * <tt>m1.entrySet().equals(m2.entrySet())</tt>. This ensures that the
\r
469 * <tt>equals</tt> method works properly across different implementations
\r
470 * of the <tt>Map</tt> interface.
\r
472 * <p>This implementation first checks if the specified object is this map;
\r
473 * if so it returns <tt>true</tt>. Then, it checks if the specified
\r
474 * object is a map whose size is identical to the size of this map; if
\r
475 * not, it returns <tt>false</tt>. If so, it iterates over this map's
\r
476 * <tt>entrySet</tt> collection, and checks that the specified map
\r
477 * contains each mapping that this map contains. If the specified map
\r
478 * fails to contain such a mapping, <tt>false</tt> is returned. If the
\r
479 * iteration completes, <tt>true</tt> is returned.
\r
481 * @param o object to be compared for equality with this map
\r
482 * @return <tt>true</tt> if the specified object is equal to this map
\r
485 @SuppressWarnings("unchecked")
\r
486 public boolean equals(Object o) {
\r
490 if (!(o instanceof Map))
\r
492 Map<K, V> m = (Map<K, V>) o;
\r
493 if (m.size() != size())
\r
497 int l = data.length;
\r
498 for (int i = 0; i < l; i += 2) {
\r
499 K key = (K) data[i];
\r
500 V value = (V) data[i+1];
\r
501 if (value == null) {
\r
502 if (!(m.get(key)==null && m.containsKey(key)))
\r
505 if (!value.equals(m.get(key)))
\r
509 } catch (ClassCastException unused) {
\r
511 } catch (NullPointerException unused) {
\r
519 public String toString() {
\r
520 Iterator<Map.Entry<K,V>> i = entrySet().iterator();
\r
524 StringBuilder sb = new StringBuilder();
\r
527 Map.Entry<K,V> e = i.next();
\r
528 K key = e.getKey();
\r
529 V value = e.getValue();
\r
530 sb.append(key == this ? "(this Map)" : key);
\r
532 sb.append(value == this ? "(this Map)" : value);
\r
534 return sb.append('}').toString();
\r