/*******************************************************************************
* Copyright (c) 2016 Association for Decentralized Information Management
* in Industry THTH ry.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* http://www.eclipse.org/legal/epl-v10.html
*
* Contributors:
* Semantum Oy - initial API and implementation
*******************************************************************************/
package org.simantics.utils.datastructures;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
/**
* A space-optimized immutable Map implementation where keys and values are
* interlaced in one Object array.
*
*
* Both map keys and values are specified as separate typed arrays that must be
* equally sized. This provides for space-optimization by allowing reusable key
* array instances since the keys cannot be modified.
*
*
* The map should be considered immutable, but it does allow modification of a
* value for an existing key as this only changes the value, the key will remain
* untouched.
*
* The nested class {@link InterlacedArrayMapBuilder} allows easy and
* minimal-allocation construction of an {@link InterlacedArrayMap}. Use
* {@link InterlacedArrayMap#builder()} or
* {@link InterlacedArrayMap#builder(int)} to create the builder. The idea is to
* minimize the space allocated for the {@link #data} field in the built map
* instance. If the builder is completely filled up, i.e. its capacity matches
* added key, value pair count, the array it contains is directly transferred to
* the built map instance without creating any extra copies. So if possible, set
* the correct initial capacity for the builder.
*
* @author Tuukka Lehtonen
*
* @param
* key class
* @param
* value class
*/
public class InterlacedArrayMap implements Map {
final Object[] data;
Set> entrySet;
Set keySet;
Collection valueSet;
public static class InterlacedArrayMapBuilder {
private Object[] elementData;
private int count = 0;
private InterlacedArrayMapBuilder(int initialCapacity) {
this.elementData = new Object[initialCapacity*2];
}
public void add(K key, V v) {
ensureCapacityInternal(count + 2);
elementData[count] = key;
elementData[count+1] = v;
count += 2;
}
private void ensureCapacityInternal(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
public InterlacedArrayMap build() {
return count == elementData.length
? new InterlacedArrayMap<>(elementData)
: new InterlacedArrayMap<>(Arrays.copyOf(elementData, count));
}
}
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* @return a map builder with the default initial capacity of
* {@value #DEFAULT_CAPACITY} key,value pairs.
*/
public static InterlacedArrayMapBuilder builder() {
return new InterlacedArrayMapBuilder(DEFAULT_CAPACITY);
}
/**
* @param initialCapacity
* the amount of key,value pairs to fit into the builder
* initially without having to reallocate anything
* @return a map builder with the specified initial key,value pair capacity
*/
public static InterlacedArrayMapBuilder builder(int initialCapacity) {
return new InterlacedArrayMapBuilder(initialCapacity);
}
/**
* Just like {@link #InterlacedArrayMap(Object[])} but takes the array of
* objects as a collection.
*
* @param keysAndValues
* an interlaced array where where (key, value) pairs are
* repeated in consecutive indexes of the array
* @throws IllegalArgumentException
* if the array size is not divisible by two
* @throws NullPointerException
* if either parameter is null
*/
public InterlacedArrayMap(List> keysAndValues) {
this(keysAndValues.toArray());
}
/**
* Constructs new ArrayMap based on an interlaced array of keys and values.
* The array size must be divisible by two.
*
* @param keysAndValues
* an interlaced array where where (key, value) pairs are
* repeated in consecutive indexes of the array
* @throws IllegalArgumentException
* if the array size is not divisible by two
* @throws NullPointerException
* if either parameter is null
*/
public InterlacedArrayMap(Object[] keysAndValues) {
// NPE is caught by this.
if ((keysAndValues.length & 1) != 0)
throw new IllegalArgumentException("key and value array size (" + keysAndValues.length + ") is not divisible by 2");
this.data = keysAndValues;
}
@Override
public Set> entrySet() {
return (entrySet != null) ? entrySet : (entrySet = new EntrySet());
}
@Override
public void clear() {
throw new UnsupportedOperationException();
}
@Override
public boolean containsKey(Object key) {
return contains(0, key);
}
@Override
public boolean containsValue(Object value) {
return contains(1, value);
}
@SuppressWarnings("unchecked")
@Override
public V get(Object key) {
if (key == null) {
for (int i = 0; i < data.length; i += 2) {
if (data[i] == null) {
return (V) data[i+1];
}
}
return null;
}
int hash = key.hashCode();
for (int i = 0; i < data.length; i += 2) {
Object k = data[i];
if (k == key || (hash == k.hashCode() && key.equals(k))) {
return (V) data[i+1];
}
}
return null;
}
@Override
public boolean isEmpty() {
return data.length == 0;
}
@Override
public Set keySet() {
return (keySet != null) ? keySet : (keySet = new OffsetSet(0));
}
@SuppressWarnings("unchecked")
@Override
public V put(K key, V value) {
if (key == null) {
for (int i = 0; i < data.length; i += 2) {
if (data[i] == null) {
V old = (V) data[i+1];
data[i+1] = value;
return old;
}
}
throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");
}
int hash = key.hashCode();
for (int i = 0; i < data.length; i += 2) {
K k = (K) data[i];
if (k == key || (hash == k.hashCode() && key.equals(k))) {
V old = (V) data[i+1];
data[i+1] = value;
return old;
}
}
throw new UnsupportedOperationException("key " + key + " not present in ArrayMap");
}
@Override
public void putAll(Map extends K, ? extends V> m) {
for (K k : m.keySet()) {
if (!containsKey(k))
throw new UnsupportedOperationException("key " + k + " not present in ArrayMap");
}
for (Map.Entry extends K, ? extends V> entry : m.entrySet()) {
put(entry.getKey(), entry.getValue());
}
}
@Override
public V remove(Object key) {
throw new UnsupportedOperationException();
}
@Override
public int size() {
return data.length >> 1;
}
@Override
public Collection values() {
return valueSet != null ? valueSet : (valueSet = new OffsetSet(1));
}
private boolean contains(int offset, Object o) {
int len = data.length;
if (o == null) {
for (int i = offset; i < len; i += 2)
if (data[i] == null)
return true;
return false;
}
int hash = o.hashCode();
for (int i = offset; i < len; i += 2) {
Object k = data[i];
if (o == k || (hash == k.hashCode() && o.equals(k)))
return true;
}
return false;
}
class OffsetSet extends ImmutableSet implements Set {
private final int offset;
public OffsetSet(int offset) {
this.offset = offset;
}
@Override
public boolean contains(Object o) {
return InterlacedArrayMap.this.contains(offset, o);
}
@Override
public boolean containsAll(Collection> c) {
for (Object o : c)
if (!contains(o))
return false;
return true;
}
@Override
public boolean isEmpty() {
return data.length == 0;
}
@Override
public Iterator iterator() {
return new ImmutableIterator() {
int i = offset;
@Override
public boolean hasNext() {
return i < data.length;
}
@Override
public T next() {
if (i >= data.length)
throw new NoSuchElementException("no more elements (" + data.length + " walked)");
@SuppressWarnings("unchecked")
T t = (T) data[i];
++i;
return t;
}
};
}
@Override
public int size() {
return data.length >> 1;
}
@Override
public Object[] toArray() {
int len = data.length >> 1;
Object[] a = new Object[len];
for (int i = 0; i < len; ++i)
a[i] = data[i*2+offset];
return a;
}
@SuppressWarnings("unchecked")
@Override
public TT[] toArray(TT[] a) {
int len = data.length >> 1;
if (a.length < len) {
Class> clazz = a.getClass();
// Make a new array of a's runtime type, but my contents:
a = ((Object)clazz == (Object)Object[].class)
? (TT[]) new Object[len]
: (TT[]) Array.newInstance(clazz.getComponentType(), len);
}
for (int i = 0; i < len; ++i)
a[i] = (TT) data[i*2+offset];
if (a.length > len)
a[len] = null;
return a;
}
}
class EntrySet extends ImmutableSet> implements Set> {
@Override
public boolean contains(Object o) {
throw new UnsupportedOperationException("TODO");
}
@Override
public boolean containsAll(Collection> c) {
for (Object o : c)
if (!contains(o))
return false;
return true;
}
@Override
public boolean isEmpty() {
return data.length == 0;
}
@Override
public Iterator> iterator() {
return new ImmutableIterator>() {
int i = 0;
@Override
public boolean hasNext() {
return i < data.length;
}
@Override
public Map.Entry next() {
if (i >= data.length)
throw new NoSuchElementException("no more elements (" + (data.length >> 1) + " walked)");
@SuppressWarnings("unchecked")
Map.Entry entry = new ArrayMapEntry(i, (K) data[i], (V) data[i+1]);
i += 2;
return entry;
}
};
}
@Override
public int size() {
return data.length >> 1;
}
}
/**
* Returns the hash code value for this map. The hash code of a map is
* defined to be the sum of the hash codes of each entry in the map's
* entrySet() view. This ensures that m1.equals(m2)
* implies that m1.hashCode()==m2.hashCode() for any two maps
* m1 and m2, as required by the general contract of
* {@link Object#hashCode}.
*
* This implementation iterates over entrySet(), calling
* {@link Map.Entry#hashCode hashCode()} on each element (entry) in the
* set, and adding up the results.
*
* @return the hash code value for this map
* @see Map.Entry#hashCode()
* @see Object#equals(Object)
* @see Set#equals(Object)
*/
@Override
@SuppressWarnings("unchecked")
public int hashCode() {
int h = 0;
int l = data.length;
for (int i = 0; i < l; i += 2) {
K key = (K) data[i];
V value = (V) data[i+1];
int hash = (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());
h += hash;
}
return h;
}
/**
* Compares the specified object with this map for equality. Returns
* true if the given object is also a map and the two maps
* represent the same mappings. More formally, two maps m1 and
* m2 represent the same mappings if
* m1.entrySet().equals(m2.entrySet()). This ensures that the
* equals method works properly across different implementations
* of the Map interface.
*
*
This implementation first checks if the specified object is this map;
* if so it returns true. Then, it checks if the specified
* object is a map whose size is identical to the size of this map; if
* not, it returns false. If so, it iterates over this map's
* entrySet collection, and checks that the specified map
* contains each mapping that this map contains. If the specified map
* fails to contain such a mapping, false is returned. If the
* iteration completes, true is returned.
*
* @param o object to be compared for equality with this map
* @return true if the specified object is equal to this map
*/
@Override
@SuppressWarnings("unchecked")
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Map))
return false;
Map m = (Map) o;
if (m.size() != size())
return false;
try {
int l = data.length;
for (int i = 0; i < l; i += 2) {
K key = (K) data[i];
V value = (V) data[i+1];
if (value == null) {
if (!(m.get(key)==null && m.containsKey(key)))
return false;
} else {
if (!value.equals(m.get(key)))
return false;
}
}
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
return true;
}
@Override
public String toString() {
Iterator> i = entrySet().iterator();
if (! i.hasNext())
return "{}";
StringBuilder sb = new StringBuilder();
sb.append('{');
for (;;) {
Map.Entry e = i.next();
K key = e.getKey();
V value = e.getValue();
sb.append(key == this ? "(this Map)" : key);
sb.append('=');
sb.append(value == this ? "(this Map)" : value);
if (! i.hasNext())
return sb.append('}').toString();
sb.append(", ");
}
}
}