UnmodifiableMap.java
/*
* Copyright (C) 2018 Stein Eldar Johnsen
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package net.morimekta.collect;
import net.morimekta.collect.collectors.UnmodifiableMapCollector;
import java.util.AbstractMap;
import java.util.Map;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collector;
import static java.lang.Integer.highestOneBit;
import static java.lang.Math.max;
import static java.util.Objects.requireNonNull;
/**
* Simple unmodifiable map that preserves entry order when iterating. This data
* structure is essentially the same as an associative array, but not modifiable.
* Backing lookup mechanism is a simple hash table.
* <p>
* Note that the builder for this differs from the guava immutable map simply
* by accepting values to be overwritten, and differs from the java.util
* {@link java.util.HashMap} by being unmodifiable and order preserving, more
* like an unmodifiable {@link java.util.LinkedHashMap}.
* <p>
* Since the map is not modifiable it is possible to achieve full compatibility with
* the {@link Map} interface with much simpler backing structures and logic. By
* requiring all values to be non-null, some of the logic can be even simpler.
*
* @param <K> The entry key type.
* @param <V> The entry value type.
*/
public final class UnmodifiableMap<K, V> extends UnmodifiableMapBase<K, V> implements Map<K, V> {
// -------- Collectors --------
/**
* @param toKey Function to map entry to key.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The unmodifiable map collector.
*/
public static <K, V> Collector<V, ?, UnmodifiableMap<K, V>>
toMap(Function<V, K> toKey) {
return new UnmodifiableMapCollector<>(toKey, i -> i);
}
/**
* @param toKey Function to map entry to key.
* @param toValue Function to map entry to value.
* @param <K> The map key type.
* @param <V> The map value type.
* @param <E> The stream element type.
* @return The unmodifiable map collector.
*/
public static <K, V, E> Collector<E, ?, UnmodifiableMap<K, V>>
toMap(Function<E, K> toKey, Function<E, V> toValue) {
return new UnmodifiableMapCollector<>(toKey, toValue);
}
// -------- Constructors --------
/**
* @param map Map to make unmodifiable version of.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The unmodifiable map.
*/
public static <K, V> UnmodifiableMap<K, V> asMap(Map<K, V> map) {
if (map.isEmpty()) {
return mapOf();
}
if (map instanceof UnmodifiableMap) {
return (UnmodifiableMap<K, V>) map;
}
if (map instanceof UnmodifiableSortedMap) {
UnmodifiableSortedMap<K, V> other = (UnmodifiableSortedMap<K, V>) map;
return new UnmodifiableMap<>(other.size, other.entries, makeHashTable(other.entries, other.size));
}
UnmodifiableMap.Builder<K, V> builder = new Builder<>(map.size());
builder.putAll(map);
return builder.build();
}
/**
* @param <K> The map key type.
* @param <V> The map value type.
* @return The unmodifiable empty map.
*/
@SuppressWarnings("unchecked")
public static <K, V> UnmodifiableMap<K, V> mapOf() {
return (UnmodifiableMap<K, V>) EMPTY;
}
/**
* @param key The entry key.
* @param value The entry value.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The unmodifiable singleton map.
*/
public static <K, V> UnmodifiableMap<K, V> mapOf(K key, V value) {
return construct(entry(key, value));
}
/**
* @param k1 The first entry key.
* @param v1 The first entry value.
* @param k2 The second entry key.
* @param v2 The second entry value.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The unmodifiable singleton map.
*/
public static <K, V> UnmodifiableMap<K, V> mapOf(K k1, V v1,
K k2, V v2) {
return construct(entry(k1, v1),
entry(k2, v2));
}
/**
* @param k1 The first entry key.
* @param v1 The first entry value.
* @param k2 The second entry key.
* @param v2 The second entry value.
* @param k3 The third entry key.
* @param v3 The third entry value.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The unmodifiable singleton map.
*/
public static <K, V> UnmodifiableMap<K, V> mapOf(K k1, V v1,
K k2, V v2,
K k3, V v3) {
return construct(entry(k1, v1),
entry(k2, v2),
entry(k3, v3));
}
/**
* @param k1 The first entry key.
* @param v1 The first entry value.
* @param k2 The second entry key.
* @param v2 The second entry value.
* @param k3 The third entry key.
* @param v3 The third entry value.
* @param k4 The fourth entry key.
* @param v4 The fourth entry value.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The unmodifiable singleton map.
*/
public static <K, V> UnmodifiableMap<K, V> mapOf(K k1, V v1,
K k2, V v2,
K k3, V v3,
K k4, V v4) {
return construct(entry(k1, v1),
entry(k2, v2),
entry(k3, v3),
entry(k4, v4));
}
/**
* @param k1 The first entry key.
* @param v1 The first entry value.
* @param k2 The second entry key.
* @param v2 The second entry value.
* @param k3 The third entry key.
* @param v3 The third entry value.
* @param k4 The fourth entry key.
* @param v4 The fourth entry value.
* @param k5 The fifth entry key.
* @param v5 The fifth entry value.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The unmodifiable singleton map.
*/
public static <K, V> UnmodifiableMap<K, V> mapOf(K k1, V v1,
K k2, V v2,
K k3, V v3,
K k4, V v4,
K k5, V v5) {
return construct(entry(k1, v1),
entry(k2, v2),
entry(k3, v3),
entry(k4, v4),
entry(k5, v5));
}
/**
* @param k1 The first entry key.
* @param v1 The first entry value.
* @param k2 The second entry key.
* @param v2 The second entry value.
* @param k3 The third entry key.
* @param v3 The third entry value.
* @param k4 The fourth entry key.
* @param v4 The fourth entry value.
* @param k5 The fifth entry key.
* @param v5 The fifth entry value.
* @param k6 The sixth entry key.
* @param v6 The sixth entry value.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The unmodifiable singleton map.
*/
public static <K, V> UnmodifiableMap<K, V> mapOf(K k1, V v1,
K k2, V v2,
K k3, V v3,
K k4, V v4,
K k5, V v5,
K k6, V v6) {
return construct(entry(k1, v1),
entry(k2, v2),
entry(k3, v3),
entry(k4, v4),
entry(k5, v5),
entry(k6, v6));
}
/**
* @param k1 The first entry key.
* @param v1 The first entry value.
* @param k2 The second entry key.
* @param v2 The second entry value.
* @param k3 The third entry key.
* @param v3 The third entry value.
* @param k4 The fourth entry key.
* @param v4 The fourth entry value.
* @param k5 The fifth entry key.
* @param v5 The fifth entry value.
* @param k6 The sixth entry key.
* @param v6 The sixth entry value.
* @param k7 The seventh entry key.
* @param v7 The seventh entry value.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The unmodifiable singleton map.
*/
public static <K, V> UnmodifiableMap<K, V> mapOf(K k1, V v1,
K k2, V v2,
K k3, V v3,
K k4, V v4,
K k5, V v5,
K k6, V v6,
K k7, V v7) {
return construct(entry(k1, v1),
entry(k2, v2),
entry(k3, v3),
entry(k4, v4),
entry(k5, v5),
entry(k6, v6),
entry(k7, v7));
}
/**
* @param k1 The first entry key.
* @param v1 The first entry value.
* @param k2 The second entry key.
* @param v2 The second entry value.
* @param k3 The third entry key.
* @param v3 The third entry value.
* @param k4 The fourth entry key.
* @param v4 The fourth entry value.
* @param k5 The fifth entry key.
* @param v5 The fifth entry value.
* @param k6 The sixth entry key.
* @param v6 The sixth entry value.
* @param k7 The seventh entry key.
* @param v7 The seventh entry value.
* @param k8 The eighth entry key.
* @param v8 The eighth entry value.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The unmodifiable singleton map.
*/
public static <K, V> UnmodifiableMap<K, V> mapOf(K k1, V v1,
K k2, V v2,
K k3, V v3,
K k4, V v4,
K k5, V v5,
K k6, V v6,
K k7, V v7,
K k8, V v8) {
return construct(entry(k1, v1),
entry(k2, v2),
entry(k3, v3),
entry(k4, v4),
entry(k5, v5),
entry(k6, v6),
entry(k7, v7),
entry(k8, v8));
}
/**
* @param k1 The first entry key.
* @param v1 The first entry value.
* @param k2 The second entry key.
* @param v2 The second entry value.
* @param k3 The third entry key.
* @param v3 The third entry value.
* @param k4 The fourth entry key.
* @param v4 The fourth entry value.
* @param k5 The fifth entry key.
* @param v5 The fifth entry value.
* @param k6 The sixth entry key.
* @param v6 The sixth entry value.
* @param k7 The seventh entry key.
* @param v7 The seventh entry value.
* @param k8 The eighth entry key.
* @param v8 The eighth entry value.
* @param k9 The ninth entry key.
* @param v9 The ninth entry value.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The unmodifiable singleton map.
*/
public static <K, V> UnmodifiableMap<K, V> mapOf(K k1, V v1,
K k2, V v2,
K k3, V v3,
K k4, V v4,
K k5, V v5,
K k6, V v6,
K k7, V v7,
K k8, V v8,
K k9, V v9) {
return construct(entry(k1, v1),
entry(k2, v2),
entry(k3, v3),
entry(k4, v4),
entry(k5, v5),
entry(k6, v6),
entry(k7, v7),
entry(k8, v8),
entry(k9, v9));
}
/**
* @param k1 The first entry key.
* @param v1 The first entry value.
* @param k2 The second entry key.
* @param v2 The second entry value.
* @param k3 The third entry key.
* @param v3 The third entry value.
* @param k4 The fourth entry key.
* @param v4 The fourth entry value.
* @param k5 The fifth entry key.
* @param v5 The fifth entry value.
* @param k6 The sixth entry key.
* @param v6 The sixth entry value.
* @param k7 The seventh entry key.
* @param v7 The seventh entry value.
* @param k8 The eighth entry key.
* @param v8 The eighth entry value.
* @param k9 The ninth entry key.
* @param v9 The ninth entry value.
* @param k10 The tenth entry key.
* @param v10 The tenth entry value.
* @param <K> The map key type.
* @param <V> The map value type.
* @return The unmodifiable singleton map.
*/
public static <K, V> UnmodifiableMap<K, V> mapOf(K k1, V v1,
K k2, V v2,
K k3, V v3,
K k4, V v4,
K k5, V v5,
K k6, V v6,
K k7, V v7,
K k8, V v8,
K k9, V v9,
K k10, V v10) {
return construct(entry(k1, v1),
entry(k2, v2),
entry(k3, v3),
entry(k4, v4),
entry(k5, v5),
entry(k6, v6),
entry(k7, v7),
entry(k8, v8),
entry(k9, v9),
entry(k10, v10));
}
/**
* @param <K> The map key type.
* @param <V> The map value type.
* @return A builder for making an unmodifiable map.
*/
public static <K, V> UnmodifiableMap.Builder<K, V> newBuilder() {
return new Builder<>(4);
}
/**
* @param initialCapacity Initial capacity of the builder.
* @param <K> The map key type.
* @param <V> The map value type.
* @return A builder for making an unmodifiable map.
*/
public static <K, V> UnmodifiableMap.Builder<K, V> newBuilder(int initialCapacity) {
return new Builder<>(max(1, initialCapacity));
}
// --- Map
@Override
public boolean containsKey(Object key) {
requireNonNull(key, "key == null");
int hash = key.hashCode();
for (int hp = hash & mask; ; hp = ++hp & mask) {
Entry<K, V> p = hashTable[hp];
if (p == null) {
return false;
}
if (p.getKey().equals(key)) {
return true;
}
}
}
@Override
public V get(Object key) {
requireNonNull(key, "key == null");
int hash = key.hashCode();
for (int hp = hash & mask; ; hp = ++hp & mask) {
Entry<K, V> p = hashTable[hp];
if (p == null) {
return null;
}
if (p.getKey().equals(key)) {
return p.getValue();
}
}
}
// -------- UnmodifiableMapBase --------
@Override
public UnmodifiableMap<K, V> withEntry(K key, V value) {
requireNonNull(key, "key == null");
requireNonNull(value, "value == null");
if (isEmpty()) {
return mapOf(key, value);
}
return new Builder<K, V>(size + 1)
.putAll(this)
.put(key, value)
.build();
}
@Override
@SuppressWarnings("unchecked")
public UnmodifiableMap<K, V> withEntries(Map<? extends K, ? extends V> map) {
requireNonNull(map, "map == null");
if (map.isEmpty()) {
return this;
}
if (isEmpty()) {
return asMap((Map<K, V>) map);
}
return new Builder<K, V>(size + map.size())
.putAll(this)
.putAll(map)
.build();
}
// -------- Builder --------
/**
* Builder for making an unmodifiable map.
*
* @param <K> The map key type.
* @param <V> The map value type.
*/
public final static class Builder<K, V>
extends UnmodifiableMapBuilder<K, V, UnmodifiableMap<K, V>, Builder<K, V>>
implements MapBuilder<K, V> {
private Entry<K, V>[] entries;
private int size;
private Entry<K, V>[] hashTable;
private int mask;
Builder(int initialSize) {
entries = makeEntryArray(initialSize);
size = 0;
hashTable = makeEntryArray(hashTableSizeFor(initialSize, MIN_HASH_TABLE_SIZE));
mask = hashTable.length - 1;
}
@Override
public Builder<K, V> put(K key, V value) {
requireNonNull(key, "null key");
requireNonNull(value, "null value");
ensureCapacity(size + 1);
findAndInsert(key, value);
return this;
}
@Override
public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
requireNonNull(map, "null map");
ensureCapacity(size + map.size());
for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
findAndInsert(requireNonNull(entry.getKey(), "null key"),
requireNonNull(entry.getValue(), "null value"));
}
return this;
}
@Override
public UnmodifiableMap<K, V> build() {
if (size == 0) {
return mapOf();
}
Entry<K, V>[] array = makeEntryArray(size);
for (int i = 0; i < size; ++i) {
array[i] = new AbstractMap.SimpleImmutableEntry<>(entries[i].getKey(),
entries[i].getValue());
}
Entry<K, V>[] table = makeHashTable(array, size);
return new UnmodifiableMap<>(size, array, table);
}
private void ensureCapacity(int minSize) {
if (minSize > entries.length) {
Entry<K, V>[] array = makeEntryArray(max(minSize, entries.length * 2));
System.arraycopy(entries, 0, array, 0, size);
entries = array;
hashTable = makeHashTable(entries, size,
hashTableSizeFor(entries.length, hashTable.length));
mask = hashTable.length - 1;
}
}
private void findAndInsert(K key, V value) {
int hash = key.hashCode();
for (int hp = hash & mask; ; hp = ++hp & mask) {
Entry<K, V> p = hashTable[hp];
if (p == null) {
p = new AbstractMap.SimpleEntry<>(key, value);
hashTable[hp] = p;
entries[size++] = p;
break;
} else if (p.getKey().equals(key)) {
p.setValue(value);
break;
}
}
}
}
// -------- UnmodifiableMapBase : Protected --------
@Override
protected Set<Entry<K, V>> makeEntrySet() {
if (size == 0) {
return UnmodifiableSet.setOf();
}
return new UnmodifiableSet<>(size, entries, UnmodifiableSet.makeHashTable(entries, size));
}
@Override
@SuppressWarnings("unchecked")
protected Set<K> makeKeySet() {
if (size == 0) {
return UnmodifiableSet.setOf();
}
Object[] keys = new Object[size];
for (int i = 0; i < size; ++i) {
keys[i] = entries[i].getKey();
}
return (Set<K>) UnmodifiableSet.construct(keys);
}
// -------- Private --------
UnmodifiableMap(int size, Entry<K, V>[] entries, Entry<K, V>[] hashTable) {
super(size, entries);
this.hashTable = hashTable;
this.mask = hashTable.length - 1;
}
private static int hashTableSizeFor(final int arraySize, int currentHashTableSize) {
int tableSize = max(highestOneBit(arraySize) << 1, max(MIN_HASH_TABLE_SIZE, currentHashTableSize));
if (tableSize < (int) (MIN_OVER_CAPACITY * (double) arraySize)) {
tableSize <<= 1;
}
return tableSize;
}
@SafeVarargs
@SuppressWarnings("varargs")
private static <K, V> UnmodifiableMap<K, V> construct(Entry<K, V>... entries) {
return new UnmodifiableMap<>(entries.length, entries, makeHashTable(entries, entries.length));
}
private static <K, V> Entry<K, V>[] makeHashTable(Entry<K, V>[] array, int size) {
return makeHashTable(array, size, hashTableSizeFor(size, MIN_HASH_TABLE_SIZE));
}
private static <K, V> Entry<K, V>[] makeHashTable(Entry<K, V>[] array, int size, int hashTableSize) {
int mask = hashTableSize - 1;
Entry<K, V>[] hashTable = makeEntryArray(hashTableSize);
for (int i = 0; i < size; ++i) {
Entry<K, V> o = array[i];
int hash = o.getKey().hashCode();
int hp = hash & mask;
for (; ; ) {
Entry<K, V> p = hashTable[hp];
if (p == null) {
hashTable[hp] = o;
break;
}
hp = ++hp & mask;
}
}
return hashTable;
}
private static final double MIN_OVER_CAPACITY = 1.38;
private static final int MIN_HASH_TABLE_SIZE = 2;
private static final UnmodifiableMap<Object, Object> EMPTY = new UnmodifiableMap<>(
0, NO_ENTRIES, makeEntryArray(MIN_HASH_TABLE_SIZE));
private final transient Entry<K, V>[] hashTable;
private final transient int mask;
}