package com.carrotsearch.hppc;
import java.util.*;
import com.carrotsearch.hppc.cursors.*;
import com.carrotsearch.hppc.predicates.*;
import com.carrotsearch.hppc.procedures.*;
import static com.carrotsearch.hppc.HashContainers.*;
import static com.carrotsearch.hppc.Containers.*;
@SuppressWarnings("unchecked")
@com.carrotsearch.hppc.Generated(
date = "2018-05-21T12:24:05+0200",
value = "KTypeVTypeHashMap.java")
public class CharObjectHashMap<VType>
implements
CharObjectMap<VType>,
Preallocable,
Cloneable
{
public char []
keys;
public
Object []
values;
protected int keyMixer;
protected int assigned;
protected int mask;
protected int resizeAt;
protected boolean hasEmptyKey;
protected double loadFactor;
protected HashOrderMixingStrategy orderMixer;
public CharObjectHashMap() {
this(DEFAULT_EXPECTED_ELEMENTS);
}
public CharObjectHashMap(int expectedElements) {
this(expectedElements, DEFAULT_LOAD_FACTOR);
}
public CharObjectHashMap(int expectedElements, double loadFactor) {
this(expectedElements, loadFactor, HashOrderMixing.defaultStrategy());
}
public CharObjectHashMap(int expectedElements, double loadFactor, HashOrderMixingStrategy orderMixer) {
this.orderMixer = orderMixer;
this.loadFactor = verifyLoadFactor(loadFactor);
ensureCapacity(expectedElements);
}
public CharObjectHashMap(CharObjectAssociativeContainer<? extends VType> container) {
this(container.size());
putAll(container);
}
@Override
public VType put(char key, VType value) {
assert assigned < mask + 1;
final int mask = this.mask;
if (((key) == 0)) {
hasEmptyKey = true;
VType previousValue = (VType) values[mask + 1];
values[mask + 1] = value;
return previousValue;
} else {
final char[] keys = this.keys;
int slot = hashKey(key) & mask;
char existing;
while (!((existing = keys[slot]) == 0)) {
if (((existing) == ( key))) {
final VType previousValue = (VType) values[slot];
values[slot] = value;
return previousValue;
}
slot = (slot + 1) & mask;
}
if (assigned == resizeAt) {
allocateThenInsertThenRehash(slot, key, value);
} else {
keys[slot] = key;
values[slot] = value;
}
assigned++;
return null;
}
}
@Override
public int putAll(CharObjectAssociativeContainer<? extends VType> container) {
final int count = size();
for (CharObjectCursor<? extends VType> c : container) {
put(c.key, c.value);
}
return size() - count;
}
@Override
public int putAll(Iterable<? extends CharObjectCursor<? extends VType>> iterable){
final int count = size();
for (CharObjectCursor<? extends VType> c : iterable) {
put(c.key, c.value);
}
return size() - count;
}
public boolean putIfAbsent(char key, VType value) {
int keyIndex = indexOf(key);
if (!indexExists(keyIndex)) {
indexInsert(keyIndex, key, value);
return true;
} else {
return false;
}
}
@Override
public VType remove(char key) {
final int mask = this.mask;
if (((key) == 0)) {
hasEmptyKey = false;
VType previousValue = (VType) values[mask + 1];
values[mask + 1] = null;
return previousValue;
} else {
final char[] keys = this.keys;
int slot = hashKey(key) & mask;
char existing;
while (!((existing = keys[slot]) == 0)) {
if (((existing) == ( key))) {
final VType previousValue = (VType) values[slot];
shiftConflictingKeys(slot);
return previousValue;
}
slot = (slot + 1) & mask;
}
return null;
}
}
@Override
public int removeAll(CharContainer other) {
final int before = size();
if (other.size() >= size() &&
other instanceof CharLookupContainer) {
if (hasEmptyKey) {
if (other.contains(((char) 0))) {
hasEmptyKey = false;
values[mask + 1] = null;
}
}
final char[] keys = this.keys;
for (int slot = 0, max = this.mask; slot <= max;) {
char existing;
if (!((existing = keys[slot]) == 0) && other.contains(existing)) {
shiftConflictingKeys(slot);
} else {
slot++;
}
}
} else {
for (CharCursor c : other) {
this.remove( c.value);
}
}
return before - size();
}
@Override
public int removeAll(CharObjectPredicate<? super VType> predicate) {
final int before = size();
final int mask = this.mask;
if (hasEmptyKey) {
if (predicate.apply(((char) 0), (VType) values[mask + 1])) {
hasEmptyKey = false;
values[mask + 1] = null;
}
}
final char[] keys = this.keys;
final VType[] values = (VType[]) this.values;
for (int slot = 0; slot <= mask;) {
char existing;
if (!((existing = keys[slot]) == 0) &&
predicate.apply(existing, values[slot])) {
shiftConflictingKeys(slot);
} else {
slot++;
}
}
return before - size();
}
@Override
public int removeAll(CharPredicate predicate) {
final int before = size();
if (hasEmptyKey) {
if (predicate.apply(((char) 0))) {
hasEmptyKey = false;
values[mask + 1] = null;
}
}
final char[] keys = this.keys;
for (int slot = 0, max = this.mask; slot <= max;) {
char existing;
if (!((existing = keys[slot]) == 0) &&
predicate.apply(existing)) {
shiftConflictingKeys(slot);
} else {
slot++;
}
}
return before - size();
}
@Override
public VType get(char key) {
if (((key) == 0)) {
return hasEmptyKey ? (VType) values[mask + 1] : null;
} else {
final char[] keys = this.keys;
final int mask = this.mask;
int slot = hashKey(key) & mask;
char existing;
while (!((existing = keys[slot]) == 0)) {
if (((existing) == ( key))) {
return (VType) values[slot];
}
slot = (slot + 1) & mask;
}
return null;
}
}
@Override
public VType getOrDefault(char key, VType defaultValue) {
if (((key) == 0)) {
return hasEmptyKey ? (VType) values[mask + 1] : defaultValue;
} else {
final char[] keys = this.keys;
final int mask = this.mask;
int slot = hashKey(key) & mask;
char existing;
while (!((existing = keys[slot]) == 0)) {
if (((existing) == ( key))) {
return (VType) values[slot];
}
slot = (slot + 1) & mask;
}
return defaultValue;
}
}
@Override
public boolean containsKey(char key) {
if (((key) == 0)) {
return hasEmptyKey;
} else {
final char[] keys = this.keys;
final int mask = this.mask;
int slot = hashKey(key) & mask;
char existing;
while (!((existing = keys[slot]) == 0)) {
if (((existing) == ( key))) {
return true;
}
slot = (slot + 1) & mask;
}
return false;
}
}
@Override
public int indexOf(char key) {
final int mask = this.mask;
if (((key) == 0)) {
return hasEmptyKey ? mask + 1 : ~(mask + 1);
} else {
final char[] keys = this.keys;
int slot = hashKey(key) & mask;
char existing;
while (!((existing = keys[slot]) == 0)) {
if (((existing) == ( key))) {
return slot;
}
slot = (slot + 1) & mask;
}
return ~slot;
}
}
@Override
public boolean indexExists(int index) {
assert index < 0 ||
(index >= 0 && index <= mask) ||
(index == mask + 1 && hasEmptyKey);
return index >= 0;
}
@Override
public VType indexGet(int index) {
assert index >= 0 : "The index must point at an existing key.";
assert index <= mask ||
(index == mask + 1 && hasEmptyKey);
return (VType) values[index];
}
@Override
public VType indexReplace(int index, VType newValue) {
assert index >= 0 : "The index must point at an existing key.";
assert index <= mask ||
(index == mask + 1 && hasEmptyKey);
VType previousValue = (VType) values[index];
values[index] = newValue;
return previousValue;
}
@Override
public void indexInsert(int index, char key, VType value) {
assert index < 0 : "The index must not point at an existing key.";
index = ~index;
if (((key) == 0)) {
assert index == mask + 1;
values[index] = value;
hasEmptyKey = true;
} else {
assert ((keys[index]) == 0);
if (assigned == resizeAt) {
allocateThenInsertThenRehash(index, key, value);
} else {
keys[index] = key;
values[index] = value;
}
assigned++;
}
}
@Override
public void clear() {
assigned = 0;
hasEmptyKey = false;
Arrays.fill(keys, ((char) 0));
Arrays.fill(values, null);
}
@Override
public void release() {
assigned = 0;
hasEmptyKey = false;
keys = null;
values = null;
ensureCapacity(Containers.DEFAULT_EXPECTED_ELEMENTS);
}
@Override
public int size() {
return assigned + (hasEmptyKey ? 1 : 0);
}
public boolean isEmpty() {
return size() == 0;
}
@Override
public int hashCode() {
int h = hasEmptyKey ? 0xDEADBEEF : 0;
for (CharObjectCursor<VType> c : this) {
h += BitMixer.mix(c.key) +
BitMixer.mix(c.value);
}
return h;
}
@Override
public boolean equals(Object obj) {
return obj != null &&
getClass() == obj.getClass() &&
equalElements(getClass().cast(obj));
}
protected boolean equalElements(CharObjectHashMap<?> other) {
if (other.size() != size()) {
return false;
}
for (CharObjectCursor<?> c : other) {
char key = c.key;
if (!containsKey(key) ||
!java.util.Objects.equals(get(key), c.value)) {
return false;
}
}
return true;
}
@Override
public void ensureCapacity(int expectedElements) {
if (expectedElements > resizeAt || keys == null) {
final char[] prevKeys = this.keys;
final VType[] prevValues = (VType[]) this.values;
allocateBuffers(minBufferSize(expectedElements, loadFactor));
if (prevKeys != null && !isEmpty()) {
rehash(prevKeys, prevValues);
}
}
}
private final class EntryIterator extends AbstractIterator<CharObjectCursor<VType>> {
private final CharObjectCursor<VType> cursor;
private final int max = mask + 1;
private int slot = -1;
public EntryIterator() {
cursor = new CharObjectCursor<VType>();
}
@Override
protected CharObjectCursor<VType> fetch() {
if (slot < max) {
char existing;
for (slot++; slot < max; slot++) {
if (!((existing = keys[slot]) == 0)) {
cursor.index = slot;
cursor.key = existing;
cursor.value = (VType) values[slot];
return cursor;
}
}
}
if (slot == max && hasEmptyKey) {
cursor.index = slot;
cursor.key = ((char) 0);
cursor.value = (VType) values[max];
slot++;
return cursor;
}
return done();
}
}
@Override
public Iterator<CharObjectCursor<VType>> iterator() {
return new EntryIterator();
}
@Override
public <T extends CharObjectProcedure<? super VType>> T forEach(T procedure) {
final char[] keys = this.keys;
final VType[] values = (VType[]) this.values;
if (hasEmptyKey) {
procedure.apply(((char) 0), (VType) values[mask + 1]);
}
for (int slot = 0, max = this.mask; slot <= max; slot++) {
if (!((keys[slot]) == 0)) {
procedure.apply(keys[slot], values[slot]);
}
}
return procedure;
}
@Override
public <T extends CharObjectPredicate<? super VType>> T forEach(T predicate) {
final char[] keys = this.keys;
final VType[] values = (VType[]) this.values;
if (hasEmptyKey) {
if (!predicate.apply(((char) 0), (VType) values[mask + 1])) {
return predicate;
}
}
for (int slot = 0, max = this.mask; slot <= max; slot++) {
if (!((keys[slot]) == 0)) {
if (!predicate.apply(keys[slot], values[slot])) {
break;
}
}
}
return predicate;
}
public KeysContainer keys() {
return new KeysContainer();
}
public final class KeysContainer extends AbstractCharCollection
implements CharLookupContainer {
private final CharObjectHashMap<VType> owner = CharObjectHashMap.this;
@Override
public boolean contains(char e) {
return owner.containsKey(e);
}
@Override
public <T extends CharProcedure> T forEach(final T procedure) {
owner.forEach(new CharObjectProcedure<VType>() {
@Override
public void apply(char key, VType value) {
procedure.apply(key);
}
});
return procedure;
}
@Override
public <T extends CharPredicate> T forEach(final T predicate) {
owner.forEach(new CharObjectPredicate<VType>() {
@Override
public boolean apply(char key, VType value) {
return predicate.apply(key);
}
});
return predicate;
}
@Override
public boolean isEmpty() {
return owner.isEmpty();
}
@Override
public Iterator<CharCursor> iterator() {
return new KeysIterator();
}
@Override
public int size() {
return owner.size();
}
@Override
public void clear() {
owner.clear();
}
@Override
public void release() {
owner.release();
}
@Override
public int removeAll(CharPredicate predicate) {
return owner.removeAll(predicate);
}
@Override
public int removeAll(final char e) {
final boolean hasKey = owner.containsKey(e);
if (hasKey) {
owner.remove(e);
return 1;
} else {
return 0;
}
}
};
private final class KeysIterator extends AbstractIterator<CharCursor> {
private final CharCursor cursor;
private final int max = mask + 1;
private int slot = -1;
public KeysIterator() {
cursor = new CharCursor();
}
@Override
protected CharCursor fetch() {
if (slot < max) {
char existing;
for (slot++; slot < max; slot++) {
if (!((existing = keys[slot]) == 0)) {
cursor.index = slot;
cursor.value = existing;
return cursor;
}
}
}
if (slot == max && hasEmptyKey) {
cursor.index = slot;
cursor.value = ((char) 0);
slot++;
return cursor;
}
return done();
}
}
@Override
public ObjectCollection<VType> values() {
return new ValuesContainer();
}
private final class ValuesContainer extends AbstractObjectCollection<VType> {
private final CharObjectHashMap<VType> owner = CharObjectHashMap.this;
@Override
public int size() {
return owner.size();
}
@Override
public boolean isEmpty() {
return owner.isEmpty();
}
@Override
public boolean contains(VType value) {
for (CharObjectCursor<VType> c : owner) {
if (java.util.Objects.equals(c.value, value)) {
return true;
}
}
return false;
}
@Override
public <T extends ObjectProcedure<? super VType>> T forEach(T procedure) {
for (CharObjectCursor<VType> c : owner) {
procedure.apply(c.value);
}
return procedure;
}
@Override
public <T extends ObjectPredicate<? super VType>> T forEach(T predicate) {
for (CharObjectCursor<VType> c : owner) {
if (!predicate.apply(c.value)) {
break;
}
}
return predicate;
}
@Override
public Iterator<ObjectCursor<VType>> iterator() {
return new ValuesIterator();
}
@Override
public int removeAll(final VType e) {
return owner.removeAll(new CharObjectPredicate<VType>() {
@Override
public boolean apply(char key, VType value) {
return java.util.Objects.equals(value, e);
}
});
}
@Override
public int removeAll(final ObjectPredicate<? super VType> predicate) {
return owner.removeAll(new CharObjectPredicate<VType>() {
@Override
public boolean apply(char key, VType value) {
return predicate.apply(value);
}
});
}
@Override
public void clear() {
owner.clear();
}
@Override
public void release() {
owner.release();
}
}
private final class ValuesIterator extends AbstractIterator<ObjectCursor<VType>> {
private final ObjectCursor<VType> cursor;
private final int max = mask + 1;
private int slot = -1;
public ValuesIterator() {
cursor = new ObjectCursor<VType>();
}
@Override
protected ObjectCursor<VType> fetch() {
if (slot < max) {
for (slot++; slot < max; slot++) {
if (!(( keys[slot]) == 0)) {
cursor.index = slot;
cursor.value = (VType) values[slot];
return cursor;
}
}
}
if (slot == max && hasEmptyKey) {
cursor.index = slot;
cursor.value = (VType) values[max];
slot++;
return cursor;
}
return done();
}
}
@Override
public CharObjectHashMap<VType> clone() {
try {
CharObjectHashMap<VType> cloned = (CharObjectHashMap<VType>) super.clone();
cloned.keys = keys.clone();
cloned.values = values.clone();
cloned.hasEmptyKey = cloned.hasEmptyKey;
cloned.orderMixer = orderMixer.clone();
return cloned;
} catch (CloneNotSupportedException e) {
throw new RuntimeException(e);
}
}
@Override
public String toString() {
final StringBuilder buffer = new StringBuilder();
buffer.append("[");
boolean first = true;
for (CharObjectCursor<VType> cursor : this) {
if (!first) {
buffer.append(", ");
}
buffer.append(cursor.key);
buffer.append("=>");
buffer.append(cursor.value);
first = false;
}
buffer.append("]");
return buffer.toString();
}
@Override
public String visualizeKeyDistribution(int characters) {
return CharBufferVisualizer.visualizeKeyDistribution(keys, mask, characters);
}
public static <VType> CharObjectHashMap<VType> from(char[] keys, VType[] values) {
if (keys.length != values.length) {
throw new IllegalArgumentException("Arrays of keys and values must have an identical length.");
}
CharObjectHashMap<VType> map = new CharObjectHashMap<>(keys.length);
for (int i = 0; i < keys.length; i++) {
map.put(keys[i], values[i]);
}
return map;
}
protected
int hashKey(char key) {
assert !((key) == 0);
return BitMixer.mix(key, this.keyMixer);
}
protected double verifyLoadFactor(double loadFactor) {
checkLoadFactor(loadFactor, MIN_LOAD_FACTOR, MAX_LOAD_FACTOR);
return loadFactor;
}
protected void rehash(char[] fromKeys, VType[] fromValues) {
assert fromKeys.length == fromValues.length &&
HashContainers.checkPowerOfTwo(fromKeys.length - 1);
final char[] keys = this.keys;
final VType[] values = (VType[]) this.values;
final int mask = this.mask;
char existing;
int from = fromKeys.length - 1;
keys[keys.length - 1] = fromKeys[from];
values[values.length - 1] = fromValues[from];
while (--from >= 0) {
if (!((existing = fromKeys[from]) == 0)) {
int slot = hashKey(existing) & mask;
while (!((keys[slot]) == 0)) {
slot = (slot + 1) & mask;
}
keys[slot] = existing;
values[slot] = fromValues[from];
}
}
}
protected void allocateBuffers(int arraySize) {
assert Integer.bitCount(arraySize) == 1;
final int newKeyMixer = this.orderMixer.newKeyMixer(arraySize);
char[] prevKeys = this.keys;
VType[] prevValues = (VType[]) this.values;
try {
int emptyElementSlot = 1;
this.keys = (new char [arraySize + emptyElementSlot]);
this.values = ((VType[]) new Object [arraySize + emptyElementSlot]);
} catch (OutOfMemoryError e) {
this.keys = prevKeys;
this.values = prevValues;
throw new BufferAllocationException(
"Not enough memory to allocate buffers for rehashing: %,d -> %,d",
e,
this.mask + 1,
arraySize);
}
this.resizeAt = expandAtCount(arraySize, loadFactor);
this.keyMixer = newKeyMixer;
this.mask = arraySize - 1;
}
protected void allocateThenInsertThenRehash(int slot, char pendingKey, VType pendingValue) {
assert assigned == resizeAt
&& (( keys[slot]) == 0)
&& !((pendingKey) == 0);
final char[] prevKeys = this.keys;
final VType[] prevValues = (VType[]) this.values;
allocateBuffers(nextBufferSize(mask + 1, size(), loadFactor));
assert this.keys.length > prevKeys.length;
prevKeys[slot] = pendingKey;
prevValues[slot] = pendingValue;
rehash(prevKeys, prevValues);
}
protected void shiftConflictingKeys(int gapSlot) {
final char[] keys = this.keys;
final VType[] values = (VType[]) this.values;
final int mask = this.mask;
int distance = 0;
while (true) {
final int slot = (gapSlot + (++distance)) & mask;
final char existing = keys[slot];
if (((existing) == 0)) {
break;
}
final int idealSlot = hashKey(existing);
final int shift = (slot - idealSlot) & mask;
if (shift >= distance) {
keys[gapSlot] = existing;
values[gapSlot] = values[slot];
gapSlot = slot;
distance = 0;
}
}
keys[gapSlot] = ((char) 0);
values[gapSlot] = null;
assigned--;
}
}