/*
 * Copyright (c) 2018 Goldman Sachs and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * and Eclipse Distribution License v. 1.0 which accompany this distribution.
 * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v10.html
 * and the Eclipse Distribution License is available at
 * http://www.eclipse.org/org/documents/edl-v10.php.
 */

package org.eclipse.collections.impl.map.mutable.primitive;

import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

import org.eclipse.collections.api.ShortIterable;
import org.eclipse.collections.api.LazyShortIterable;
import org.eclipse.collections.api.ByteIterable;
import org.eclipse.collections.api.RichIterable;
import org.eclipse.collections.api.block.function.primitive.ShortToByteFunction;
import org.eclipse.collections.api.block.function.primitive.ByteFunction;
import org.eclipse.collections.api.block.function.primitive.ByteFunction0;
import org.eclipse.collections.api.block.function.primitive.ByteToByteFunction;
import org.eclipse.collections.api.block.function.primitive.ShortByteToByteFunction;
import org.eclipse.collections.api.block.function.primitive.ObjectByteToObjectFunction;
import org.eclipse.collections.api.block.predicate.primitive.ShortBytePredicate;
import org.eclipse.collections.api.block.procedure.Procedure;
import org.eclipse.collections.api.block.procedure.Procedure2;
import org.eclipse.collections.api.block.procedure.primitive.ShortProcedure;
import org.eclipse.collections.api.block.procedure.primitive.ShortByteProcedure;
import org.eclipse.collections.api.block.procedure.primitive.ObjectIntProcedure;
import org.eclipse.collections.impl.SpreadFunctions;
import org.eclipse.collections.api.collection.primitive.MutableByteCollection;
import org.eclipse.collections.api.iterator.ShortIterator;
import org.eclipse.collections.api.iterator.MutableShortIterator;
import org.eclipse.collections.api.iterator.MutableByteIterator;
import org.eclipse.collections.api.map.primitive.ShortByteMap;
import org.eclipse.collections.api.map.primitive.ImmutableShortByteMap;
import org.eclipse.collections.api.map.primitive.MutableShortByteMap;
import org.eclipse.collections.api.map.primitive.MutableByteShortMap;
import org.eclipse.collections.api.set.primitive.ShortSet;
import org.eclipse.collections.api.set.primitive.ByteSet;
import org.eclipse.collections.api.set.primitive.MutableShortSet;
import org.eclipse.collections.api.tuple.primitive.ShortBytePair;
import org.eclipse.collections.impl.bag.mutable.primitive.ByteHashBag;
import org.eclipse.collections.impl.factory.primitive.ShortByteMaps;
import org.eclipse.collections.impl.factory.primitive.ByteShortMaps;
import org.eclipse.collections.impl.iterator.UnmodifiableShortIterator;
import org.eclipse.collections.impl.lazy.AbstractLazyIterable;
import org.eclipse.collections.impl.lazy.primitive.AbstractLazyShortIterable;
import org.eclipse.collections.impl.set.mutable.primitive.ShortHashSet;
import org.eclipse.collections.impl.tuple.primitive.PrimitiveTuples;

This file was automatically generated from template file primitivePrimitiveHashMap.stg.
Since:3.0.
/** * This file was automatically generated from template file primitivePrimitiveHashMap.stg. * * @since 3.0. */
public class ShortByteHashMap extends AbstractMutableByteValuesMap implements MutableShortByteMap, Externalizable, MutableShortKeysMap { private static final byte EMPTY_VALUE = (byte) 0; private static final long serialVersionUID = 1L; private static final short EMPTY_KEY = (short) 0; private static final short REMOVED_KEY = (short) 1; private static final int CACHE_LINE_SIZE = 64; private static final int KEY_SIZE = 2; private static final int INITIAL_LINEAR_PROBE = CACHE_LINE_SIZE / KEY_SIZE / 2; /* half a cache line */ private static final int DEFAULT_INITIAL_CAPACITY = 8; private short[] keys; private byte[] values; private int occupiedWithData; private int occupiedWithSentinels; private SentinelValues sentinelValues; private boolean copyKeysOnWrite; public ShortByteHashMap() { this.allocateTable(DEFAULT_INITIAL_CAPACITY << 1); } public ShortByteHashMap(int initialCapacity) { if (initialCapacity < 0) { throw new IllegalArgumentException("initial capacity cannot be less than 0"); } int capacity = this.smallestPowerOfTwoGreaterThan(initialCapacity << 1); this.allocateTable(capacity); } public ShortByteHashMap(ShortByteMap map) { if (map instanceof ShortByteHashMap && ((ShortByteHashMap) map).occupiedWithSentinels == 0) { ShortByteHashMap hashMap = (ShortByteHashMap) map; this.occupiedWithData = hashMap.occupiedWithData; if (hashMap.sentinelValues != null) { this.sentinelValues = hashMap.sentinelValues.copy(); } this.keys = Arrays.copyOf(hashMap.keys, hashMap.keys.length); this.values = Arrays.copyOf(hashMap.values, hashMap.values.length); } else { int capacity = this.smallestPowerOfTwoGreaterThan(Math.max(map.size(), DEFAULT_INITIAL_CAPACITY) << 1); this.allocateTable(capacity); this.putAll(map); } } public static ShortByteHashMap newWithKeysValues(short key1, byte value1) { return new ShortByteHashMap(1).withKeyValue(key1, value1); } public static ShortByteHashMap newWithKeysValues(short key1, byte value1, short key2, byte value2) { return new ShortByteHashMap(2).withKeysValues(key1, value1, key2, value2); } public static ShortByteHashMap newWithKeysValues(short key1, byte value1, short key2, byte value2, short key3, byte value3) { return new ShortByteHashMap(3).withKeysValues(key1, value1, key2, value2, key3, value3); } public static ShortByteHashMap newWithKeysValues(short key1, byte value1, short key2, byte value2, short key3, byte value3, short key4, byte value4) { return new ShortByteHashMap(4).withKeysValues(key1, value1, key2, value2, key3, value3, key4, value4); } private int smallestPowerOfTwoGreaterThan(int n) { return n > 1 ? Integer.highestOneBit(n - 1) << 1 : 1; } @Override protected int getOccupiedWithData() { return this.occupiedWithData; } @Override protected SentinelValues getSentinelValues() { return this.sentinelValues; } @Override protected void setSentinelValuesNull() { this.sentinelValues = null; } @Override protected byte getEmptyValue() { return EMPTY_VALUE; } @Override protected int getTableSize() { return this.values.length; } @Override protected byte getValueAtIndex(int index) { return this.values[index]; } @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (!(obj instanceof ShortByteMap)) { return false; } ShortByteMap other = (ShortByteMap) obj; if (this.size() != other.size()) { return false; } if (this.sentinelValues == null) { if (other.containsKey(EMPTY_KEY) || other.containsKey(REMOVED_KEY)) { return false; } } else { if (this.sentinelValues.containsZeroKey && (!other.containsKey(EMPTY_KEY) || this.sentinelValues.zeroValue != other.getOrThrow(EMPTY_KEY))) { return false; } if (this.sentinelValues.containsOneKey && (!other.containsKey(REMOVED_KEY) || this.sentinelValues.oneValue != other.getOrThrow(REMOVED_KEY))) { return false; } } for (int i = 0; i < this.keys.length; i++) { short key = this.keys[i]; if (isNonSentinel(key) && (!other.containsKey(key) || this.values[i] != other.getOrThrow(key))) { return false; } } return true; } @Override public int hashCode() { int result = 0; if (this.sentinelValues != null) { if (this.sentinelValues.containsZeroKey) { result += (int) EMPTY_KEY ^ (int) this.sentinelValues.zeroValue; } if (this.sentinelValues.containsOneKey) { result += (int) REMOVED_KEY ^ (int) this.sentinelValues.oneValue; } } for (int i = 0; i < this.keys.length; i++) { if (isNonSentinel(this.keys[i])) { result += (int) this.keys[i] ^ (int) this.values[i]; } } return result; } @Override public String toString() { StringBuilder appendable = new StringBuilder(); appendable.append("{"); boolean first = true; if (this.sentinelValues != null) { if (this.sentinelValues.containsZeroKey) { appendable.append(EMPTY_KEY).append("=").append(this.sentinelValues.zeroValue); first = false; } if (this.sentinelValues.containsOneKey) { if (!first) { appendable.append(", "); } appendable.append(REMOVED_KEY).append("=").append(this.sentinelValues.oneValue); first = false; } } for (int i = 0; i < this.keys.length; i++) { short key = this.keys[i]; if (isNonSentinel(key)) { if (!first) { appendable.append(", "); } appendable.append(key).append("=").append(this.values[i]); first = false; } } appendable.append("}"); return appendable.toString(); } @Override public MutableByteIterator byteIterator() { return new InternalByteIterator(); } @Override public <V> V injectInto(V injectedValue, ObjectByteToObjectFunction<? super V, ? extends V> function) { V result = injectedValue; if (this.sentinelValues != null) { if (this.sentinelValues.containsZeroKey) { result = function.valueOf(result, this.sentinelValues.zeroValue); } if (this.sentinelValues.containsOneKey) { result = function.valueOf(result, this.sentinelValues.oneValue); } } for (int i = 0; i < this.keys.length; i++) { if (isNonSentinel(this.keys[i])) { result = function.valueOf(result, this.values[i]); } } return result; } @Override public void clear() { this.sentinelValues = null; this.occupiedWithData = 0; this.occupiedWithSentinels = 0; if (this.copyKeysOnWrite) { this.copyKeys(); } Arrays.fill(this.keys, EMPTY_KEY); Arrays.fill(this.values, EMPTY_VALUE); } @Override public void put(short key, byte value) { if (isEmptyKey(key)) { this.putForEmptySentinel(value); return; } if (isRemovedKey(key)) { this.putForRemovedSentinel(value); return; } int index = this.probe(key); short keyAtIndex = this.keys[index]; if (keyAtIndex == key) { this.values[index] = value; } else { this.addKeyValueAtIndex(key, value, index); } } private void putForRemovedSentinel(byte value) { if (this.sentinelValues == null) { this.sentinelValues = new SentinelValues(); } this.addRemovedKeyValue(value); } private void putForEmptySentinel(byte value) { if (this.sentinelValues == null) { this.sentinelValues = new SentinelValues(); } this.addEmptyKeyValue(value); } @Override public void putAll(ShortByteMap map) { map.forEachKeyValue(this::put); } @Override public void updateValues(ShortByteToByteFunction function) { if (this.sentinelValues != null) { if (this.sentinelValues.containsZeroKey) { this.sentinelValues.zeroValue = function.valueOf(EMPTY_KEY, this.sentinelValues.zeroValue); } if (this.sentinelValues.containsOneKey) { this.sentinelValues.oneValue = function.valueOf(REMOVED_KEY, this.sentinelValues.oneValue); } } for (int i = 0; i < this.keys.length; i++) { if (isNonSentinel(this.keys[i])) { this.values[i] = function.valueOf(this.keys[i], this.values[i]); } } } @Override public void removeKey(short key) { if (isEmptyKey(key)) { if (this.sentinelValues == null || !this.sentinelValues.containsZeroKey) { return; } this.removeEmptyKey(); return; } if (isRemovedKey(key)) { if (this.sentinelValues == null || !this.sentinelValues.containsOneKey) { return; } this.removeRemovedKey(); return; } int index = this.probe(key); if (this.keys[index] == key) { this.removeKeyAtIndex(index); } } @Override public void remove(short key) { this.removeKey(key); } @Override public byte removeKeyIfAbsent(short key, byte value) { if (isEmptyKey(key)) { if (this.sentinelValues == null || !this.sentinelValues.containsZeroKey) { return value; } byte oldValue = this.sentinelValues.zeroValue; this.removeEmptyKey(); return oldValue; } if (isRemovedKey(key)) { if (this.sentinelValues == null || !this.sentinelValues.containsOneKey) { return value; } byte oldValue = this.sentinelValues.oneValue; this.removeRemovedKey(); return oldValue; } int index = this.probe(key); if (this.keys[index] == key) { byte oldValue = this.values[index]; this.removeKeyAtIndex(index); return oldValue; } return value; } @Override public byte getIfAbsentPut(short key, byte value) { if (isEmptyKey(key)) { if (this.sentinelValues == null) { this.sentinelValues = new SentinelValues(); this.addEmptyKeyValue(value); return value; } if (this.sentinelValues.containsZeroKey) { return this.sentinelValues.zeroValue; } this.addEmptyKeyValue(value); return value; } if (isRemovedKey(key)) { if (this.sentinelValues == null) { this.sentinelValues = new SentinelValues(); this.addRemovedKeyValue(value); return value; } if (this.sentinelValues.containsOneKey) { return this.sentinelValues.oneValue; } this.addRemovedKeyValue(value); return value; } int index = this.probe(key); if (this.keys[index] == key) { return this.values[index]; } this.addKeyValueAtIndex(key, value, index); return value; } @Override public byte getIfAbsentPut(short key, ByteFunction0 function) { if (isEmptyKey(key)) { if (this.sentinelValues == null) { byte value = function.value(); this.sentinelValues = new SentinelValues(); this.addEmptyKeyValue(value); return value; } if (this.sentinelValues.containsZeroKey) { return this.sentinelValues.zeroValue; } byte value = function.value(); this.addEmptyKeyValue(value); return value; } if (isRemovedKey(key)) { if (this.sentinelValues == null) { byte value = function.value(); this.sentinelValues = new SentinelValues(); this.addRemovedKeyValue(value); return value; } if (this.sentinelValues.containsOneKey) { return this.sentinelValues.oneValue; } byte value = function.value(); this.addRemovedKeyValue(value); return value; } int index = this.probe(key); if (this.keys[index] == key) { return this.values[index]; } byte value = function.value(); this.addKeyValueAtIndex(key, value, index); return value; } @Override public <P> byte getIfAbsentPutWith(short key, ByteFunction<? super P> function, P parameter) { if (isEmptyKey(key)) { if (this.sentinelValues == null) { byte value = function.byteValueOf(parameter); this.sentinelValues = new SentinelValues(); this.addEmptyKeyValue(value); return value; } if (this.sentinelValues.containsZeroKey) { return this.sentinelValues.zeroValue; } byte value = function.byteValueOf(parameter); this.addEmptyKeyValue(value); return value; } if (isRemovedKey(key)) { if (this.sentinelValues == null) { byte value = function.byteValueOf(parameter); this.sentinelValues = new SentinelValues(); this.addRemovedKeyValue(value); return value; } if (this.sentinelValues.containsOneKey) { return this.sentinelValues.oneValue; } byte value = function.byteValueOf(parameter); this.addRemovedKeyValue(value); return value; } int index = this.probe(key); if (this.keys[index] == key) { return this.values[index]; } byte value = function.byteValueOf(parameter); this.addKeyValueAtIndex(key, value, index); return value; } @Override public byte getIfAbsentPutWithKey(short key, ShortToByteFunction function) { if (isEmptyKey(key)) { if (this.sentinelValues == null) { byte value = function.valueOf(key); this.sentinelValues = new SentinelValues(); this.addEmptyKeyValue(value); return value; } if (this.sentinelValues.containsZeroKey) { return this.sentinelValues.zeroValue; } byte value = function.valueOf(key); this.addEmptyKeyValue(value); return value; } if (isRemovedKey(key)) { if (this.sentinelValues == null) { byte value = function.valueOf(key); this.sentinelValues = new SentinelValues(); this.addRemovedKeyValue(value); return value; } if (this.sentinelValues.containsOneKey) { return this.sentinelValues.oneValue; } byte value = function.valueOf(key); this.addRemovedKeyValue(value); return value; } int index = this.probe(key); if (this.keys[index] == key) { return this.values[index]; } byte value = function.valueOf(key); this.addKeyValueAtIndex(key, value, index); return value; } @Override public byte addToValue(short key, byte toBeAdded) { if (isEmptyKey(key)) { if (this.sentinelValues == null) { this.sentinelValues = new SentinelValues(); this.addEmptyKeyValue(toBeAdded); } else if (this.sentinelValues.containsZeroKey) { this.sentinelValues.zeroValue += toBeAdded; } else { this.addEmptyKeyValue(toBeAdded); } return this.sentinelValues.zeroValue; } if (isRemovedKey(key)) { if (this.sentinelValues == null) { this.sentinelValues = new SentinelValues(); this.addRemovedKeyValue(toBeAdded); } else if (this.sentinelValues.containsOneKey) { this.sentinelValues.oneValue += toBeAdded; } else { this.addRemovedKeyValue(toBeAdded); } return this.sentinelValues.oneValue; } int index = this.probe(key); if (this.keys[index] == key) { this.values[index] += toBeAdded; return this.values[index]; } this.addKeyValueAtIndex(key, toBeAdded, index); return toBeAdded; } private void addKeyValueAtIndex(short key, byte value, int index) { if (this.keys[index] == REMOVED_KEY) { this.occupiedWithSentinels--; } if (this.copyKeysOnWrite) { this.copyKeys(); } this.keys[index] = key; this.values[index] = value; this.occupiedWithData++; if (this.occupiedWithData + this.occupiedWithSentinels > this.maxOccupiedWithData()) { this.rehashAndGrow(); } } private void removeKeyAtIndex(int index) { if (this.copyKeysOnWrite) { this.copyKeys(); } this.keys[index] = REMOVED_KEY; this.values[index] = EMPTY_VALUE; this.occupiedWithData--; this.occupiedWithSentinels++; } private void copyKeys() { short[] copy = new short[this.keys.length]; System.arraycopy(this.keys, 0, copy, 0, this.keys.length); this.keys = copy; this.copyKeysOnWrite = false; } @Override public byte updateValue(short key, byte initialValueIfAbsent, ByteToByteFunction function) { if (isEmptyKey(key)) { if (this.sentinelValues == null) { this.sentinelValues = new SentinelValues(); this.addEmptyKeyValue(function.valueOf(initialValueIfAbsent)); } else if (this.sentinelValues.containsZeroKey) { this.sentinelValues.zeroValue = function.valueOf(this.sentinelValues.zeroValue); } else { this.addEmptyKeyValue(function.valueOf(initialValueIfAbsent)); } return this.sentinelValues.zeroValue; } if (isRemovedKey(key)) { if (this.sentinelValues == null) { this.sentinelValues = new SentinelValues(); this.addRemovedKeyValue(function.valueOf(initialValueIfAbsent)); } else if (this.sentinelValues.containsOneKey) { this.sentinelValues.oneValue = function.valueOf(this.sentinelValues.oneValue); } else { this.addRemovedKeyValue(function.valueOf(initialValueIfAbsent)); } return this.sentinelValues.oneValue; } int index = this.probe(key); if (this.keys[index] == key) { this.values[index] = function.valueOf(this.values[index]); return this.values[index]; } byte value = function.valueOf(initialValueIfAbsent); this.addKeyValueAtIndex(key, value, index); return value; } @Override public ShortByteHashMap withKeyValue(short key1, byte value1) { this.put(key1, value1); return this; } public ShortByteHashMap withKeysValues(short key1, byte value1, short key2, byte value2) { this.put(key1, value1); this.put(key2, value2); return this; } public ShortByteHashMap withKeysValues(short key1, byte value1, short key2, byte value2, short key3, byte value3) { this.put(key1, value1); this.put(key2, value2); this.put(key3, value3); return this; } public ShortByteHashMap withKeysValues(short key1, byte value1, short key2, byte value2, short key3, byte value3, short key4, byte value4) { this.put(key1, value1); this.put(key2, value2); this.put(key3, value3); this.put(key4, value4); return this; } @Override public ShortByteHashMap withoutKey(short key) { this.removeKey(key); return this; } @Override public ShortByteHashMap withoutAllKeys(ShortIterable keys) { keys.forEach(this::removeKey); return this; } @Override public MutableShortByteMap asUnmodifiable() { return new UnmodifiableShortByteMap(this); } @Override public MutableShortByteMap asSynchronized() { return new SynchronizedShortByteMap(this); } @Override public ImmutableShortByteMap toImmutable() { return ShortByteMaps.immutable.ofAll(this); } @Override public byte get(short key) { return this.getIfAbsent(key, EMPTY_VALUE); } @Override public byte getIfAbsent(short key, byte ifAbsent) { if (isEmptyKey(key) || isRemovedKey(key)) { return this.getForSentinel(key, ifAbsent); } if (this.occupiedWithSentinels == 0) { return this.fastGetIfAbsent(key, ifAbsent); } return this.slowGetIfAbsent(key, ifAbsent); } private byte getForSentinel(short key, byte ifAbsent) { if (isEmptyKey(key)) { if (this.sentinelValues == null || !this.sentinelValues.containsZeroKey) { return ifAbsent; } return this.sentinelValues.zeroValue; } if (this.sentinelValues == null || !this.sentinelValues.containsOneKey) { return ifAbsent; } return this.sentinelValues.oneValue; } private byte slowGetIfAbsent(short key, byte ifAbsent) { int index = this.probe(key); if (this.keys[index] == key) { return this.values[index]; } return ifAbsent; } private byte fastGetIfAbsent(short key, byte ifAbsent) { int index = this.mask((int) key); for (int i = 0; i < INITIAL_LINEAR_PROBE; i++) { short keyAtIndex = this.keys[index]; if (keyAtIndex == key) { return this.values[index]; } if (keyAtIndex == EMPTY_KEY) { return ifAbsent; } index = (index + 1) & (this.keys.length - 1); } return this.slowGetIfAbsentTwo(key, ifAbsent); } private byte slowGetIfAbsentTwo(short key, byte ifAbsent) { int index = this.probeTwo(key, -1); if (this.keys[index] == key) { return this.values[index]; } return ifAbsent; } @Override public byte getOrThrow(short key) { if (isEmptyKey(key)) { if (this.sentinelValues == null || !this.sentinelValues.containsZeroKey) { throw new IllegalStateException("Key " + key + " not present."); } return this.sentinelValues.zeroValue; } if (isRemovedKey(key)) { if (this.sentinelValues == null || !this.sentinelValues.containsOneKey) { throw new IllegalStateException("Key " + key + " not present."); } return this.sentinelValues.oneValue; } int index = this.probe(key); if (isNonSentinel(this.keys[index])) { return this.values[index]; } throw new IllegalStateException("Key " + key + " not present."); } @Override public boolean containsKey(short key) { if (isEmptyKey(key)) { return this.sentinelValues != null && this.sentinelValues.containsZeroKey; } if (isRemovedKey(key)) { return this.sentinelValues != null && this.sentinelValues.containsOneKey; } return this.keys[this.probe(key)] == key; } @Override public void forEachKey(ShortProcedure procedure) { if (this.sentinelValues != null) { if (this.sentinelValues.containsZeroKey) { procedure.value(EMPTY_KEY); } if (this.sentinelValues.containsOneKey) { procedure.value(REMOVED_KEY); } } for (int i = 0; i < this.keys.length; i++) { if (isNonSentinel(this.keys[i])) { procedure.value(this.keys[i]); } } } @Override public void forEachKeyValue(ShortByteProcedure procedure) { if (this.sentinelValues != null) { if (this.sentinelValues.containsZeroKey) { procedure.value(EMPTY_KEY, this.sentinelValues.zeroValue); } if (this.sentinelValues.containsOneKey) { procedure.value(REMOVED_KEY, this.sentinelValues.oneValue); } } for (int i = 0; i < this.keys.length; i++) { if (isNonSentinel(this.keys[i])) { procedure.value(this.keys[i], this.values[i]); } } } @Override public LazyShortIterable keysView() { return new KeysView(); } @Override public RichIterable<ShortBytePair> keyValuesView() { return new KeyValuesView(); } @Override public MutableByteShortMap flipUniqueValues() { MutableByteShortMap result = ByteShortMaps.mutable.empty(); this.forEachKeyValue((key, value) -> { if (result.containsKey(value)) { throw new IllegalStateException("Duplicate value: " + value + " found at key: " + result.get(value) + " and key: " + key); } result.put(value, key); }); return result; } @Override public ShortByteHashMap select(ShortBytePredicate predicate) { ShortByteHashMap result = new ShortByteHashMap(); if (this.sentinelValues != null) { if (this.sentinelValues.containsZeroKey && predicate.accept(EMPTY_KEY, this.sentinelValues.zeroValue)) { result.put(EMPTY_KEY, this.sentinelValues.zeroValue); } if (this.sentinelValues.containsOneKey && predicate.accept(REMOVED_KEY, this.sentinelValues.oneValue)) { result.put(REMOVED_KEY, this.sentinelValues.oneValue); } } for (int i = 0; i < this.keys.length; i++) { if (isNonSentinel(this.keys[i]) && predicate.accept(this.keys[i], this.values[i])) { result.put(this.keys[i], this.values[i]); } } return result; } @Override public ShortByteHashMap reject(ShortBytePredicate predicate) { ShortByteHashMap result = new ShortByteHashMap(); if (this.sentinelValues != null) { if (this.sentinelValues.containsZeroKey && !predicate.accept(EMPTY_KEY, this.sentinelValues.zeroValue)) { result.put(EMPTY_KEY, this.sentinelValues.zeroValue); } if (this.sentinelValues.containsOneKey && !predicate.accept(REMOVED_KEY, this.sentinelValues.oneValue)) { result.put(REMOVED_KEY, this.sentinelValues.oneValue); } } for (int i = 0; i < this.keys.length; i++) { if (isNonSentinel(this.keys[i]) && !predicate.accept(this.keys[i], this.values[i])) { result.put(this.keys[i], this.values[i]); } } return result; } @Override public void writeExternal(ObjectOutput out) throws IOException { out.writeInt(this.size()); if (this.sentinelValues != null) { if (this.sentinelValues.containsZeroKey) { out.writeShort(EMPTY_KEY); out.writeByte(this.sentinelValues.zeroValue); } if (this.sentinelValues.containsOneKey) { out.writeShort(REMOVED_KEY); out.writeByte(this.sentinelValues.oneValue); } } for (int i = 0; i < this.keys.length; i++) { if (isNonSentinel(this.keys[i])) { out.writeShort(this.keys[i]); out.writeByte(this.values[i]); } } } @Override public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException { int size = in.readInt(); for (int i = 0; i < size; i++) { this.put(in.readShort(), in.readByte()); } }
Rehashes every element in the set into a new backing table of the smallest possible size and eliminating removed sentinels.
/** * Rehashes every element in the set into a new backing table of the smallest possible size and eliminating removed sentinels. */
public void compact() { this.rehash(this.smallestPowerOfTwoGreaterThan(this.size())); } private void rehashAndGrow() { int max = this.maxOccupiedWithData(); int newCapacity = Math.max(max, smallestPowerOfTwoGreaterThan((this.occupiedWithData + 1) << 1)); if (this.occupiedWithSentinels > 0 && (max >> 1) + (max >> 2) < this.occupiedWithData) { newCapacity <<= 1; } this.rehash(newCapacity); } private void rehash(int newCapacity) { int oldLength = this.keys.length; short[] old = this.keys; byte[] oldValues = this.values; this.allocateTable(newCapacity); this.occupiedWithData = 0; this.occupiedWithSentinels = 0; for (int i = 0; i < oldLength; i++) { if (isNonSentinel(old[i])) { this.put(old[i], oldValues[i]); } } } // exposed for testing int probe(short element) { int index = this.mask((int) element); short keyAtIndex = this.keys[index]; if (keyAtIndex == element || keyAtIndex == EMPTY_KEY) { return index; } int removedIndex = keyAtIndex == REMOVED_KEY ? index : -1; for (int i = 1; i < INITIAL_LINEAR_PROBE; i++) { int nextIndex = (index + i) & (this.keys.length - 1); keyAtIndex = this.keys[nextIndex]; if (keyAtIndex == element) { return nextIndex; } if (keyAtIndex == EMPTY_KEY) { return removedIndex == -1 ? nextIndex : removedIndex; } if (keyAtIndex == REMOVED_KEY && removedIndex == -1) { removedIndex = nextIndex; } } return this.probeTwo(element, removedIndex); } int probeTwo(short element, int removedIndex) { int index = this.spreadTwoAndMask(element); for (int i = 0; i < INITIAL_LINEAR_PROBE; i++) { int nextIndex = (index + i) & (this.keys.length - 1); short keyAtIndex = this.keys[nextIndex]; if (keyAtIndex == element) { return nextIndex; } if (keyAtIndex == EMPTY_KEY) { return removedIndex == -1 ? nextIndex : removedIndex; } if (keyAtIndex == REMOVED_KEY && removedIndex == -1) { removedIndex = nextIndex; } } return this.probeThree(element, removedIndex); } int probeThree(short element, int removedIndex) { int nextIndex = (int) SpreadFunctions.shortSpreadOne(element); int spreadTwo = Integer.reverse(SpreadFunctions.shortSpreadTwo(element)) | 1; while (true) { nextIndex = this.mask(nextIndex + spreadTwo); short keyAtIndex = this.keys[nextIndex]; if (keyAtIndex == element) { return nextIndex; } if (keyAtIndex == EMPTY_KEY) { return removedIndex == -1 ? nextIndex : removedIndex; } if (keyAtIndex == REMOVED_KEY && removedIndex == -1) { removedIndex = nextIndex; } } } // exposed for testing int spreadAndMask(short element) { int code = SpreadFunctions.shortSpreadOne(element); return this.mask(code); } int spreadTwoAndMask(short element) { int code = SpreadFunctions.shortSpreadTwo(element); return this.mask(code); } private int mask(int spread) { return spread & (this.keys.length - 1); } private void allocateTable(int sizeToAllocate) { this.keys = new short[sizeToAllocate]; this.values = new byte[sizeToAllocate]; } private static boolean isEmptyKey(short key) { return key == EMPTY_KEY; } private static boolean isRemovedKey(short key) { return key == REMOVED_KEY; } private static boolean isNonSentinel(short key) { return !isEmptyKey(key) && !isRemovedKey(key); } @Override protected boolean isNonSentinelAtIndex(int index) { return !isEmptyKey(this.keys[index]) && !isRemovedKey(this.keys[index]); } private int maxOccupiedWithData() { return this.keys.length >> 1; } private class InternalByteIterator implements MutableByteIterator { private int count; private int position; private short lastKey; private boolean handledZero; private boolean handledOne; private boolean canRemove; @Override public boolean hasNext() { return this.count < ShortByteHashMap.this.size(); } @Override public byte next() { if (!this.hasNext()) { throw new NoSuchElementException("next() called, but the iterator is exhausted"); } this.count++; this.canRemove = true; if (!this.handledZero) { this.handledZero = true; if (ShortByteHashMap.this.containsKey(EMPTY_KEY)) { this.lastKey = EMPTY_KEY; return ShortByteHashMap.this.get(EMPTY_KEY); } } if (!this.handledOne) { this.handledOne = true; if (ShortByteHashMap.this.containsKey(REMOVED_KEY)) { this.lastKey = REMOVED_KEY; return ShortByteHashMap.this.get(REMOVED_KEY); } } short[] keys = ShortByteHashMap.this.keys; while (!isNonSentinel(keys[this.position])) { this.position++; } this.lastKey = keys[this.position]; byte result = ShortByteHashMap.this.values[this.position]; this.position++; return result; } @Override public void remove() { if (!this.canRemove) { throw new IllegalStateException(); } ShortByteHashMap.this.removeKey(this.lastKey); this.count--; this.canRemove = false; } } private class KeysView extends AbstractLazyShortIterable { @Override public ShortIterator shortIterator() { return new UnmodifiableShortIterator(new KeySetIterator()); }
Since:7.0.
/** * @since 7.0. */
@Override public void each(ShortProcedure procedure) { ShortByteHashMap.this.forEachKey(procedure); } } private class KeySetIterator implements MutableShortIterator { private int count; private int position; private short lastKey; private boolean handledZero; private boolean handledOne; private boolean canRemove; @Override public boolean hasNext() { return this.count < ShortByteHashMap.this.size(); } @Override public short next() { if (!this.hasNext()) { throw new NoSuchElementException("next() called, but the iterator is exhausted"); } this.count++; this.canRemove = true; if (!this.handledZero) { this.handledZero = true; if (ShortByteHashMap.this.containsKey(EMPTY_KEY)) { this.lastKey = EMPTY_KEY; return this.lastKey; } } if (!this.handledOne) { this.handledOne = true; if (ShortByteHashMap.this.containsKey(REMOVED_KEY)) { this.lastKey = REMOVED_KEY; return this.lastKey; } } short[] keys = ShortByteHashMap.this.keys; while (!isNonSentinel(keys[this.position])) { this.position++; } this.lastKey = keys[this.position]; this.position++; return this.lastKey; } @Override public void remove() { if (!this.canRemove) { throw new IllegalStateException(); } ShortByteHashMap.this.removeKey(this.lastKey); this.count--; this.canRemove = false; } } @Override public MutableShortSet keySet() { return new KeySet(); } private class KeySet extends AbstractMutableShortKeySet { @Override protected MutableShortKeysMap getOuter() { return ShortByteHashMap.this; } @Override protected SentinelValues getSentinelValues() { return ShortByteHashMap.this.sentinelValues; } @Override protected short getKeyAtIndex(int index) { return ShortByteHashMap.this.keys[index]; } @Override protected int getTableSize() { return ShortByteHashMap.this.keys.length; } @Override public MutableShortIterator shortIterator() { return new KeySetIterator(); } @Override public boolean retainAll(ShortIterable source) { int oldSize = ShortByteHashMap.this.size(); ShortSet sourceSet = source instanceof ShortSet ? (ShortSet) source : source.toSet(); ShortByteHashMap retained = ShortByteHashMap.this.select((short key, byte value) -> sourceSet.contains(key)); if (retained.size() != oldSize) { ShortByteHashMap.this.keys = retained.keys; ShortByteHashMap.this.values = retained.values; ShortByteHashMap.this.sentinelValues = retained.sentinelValues; ShortByteHashMap.this.occupiedWithData = retained.occupiedWithData; ShortByteHashMap.this.occupiedWithSentinels = retained.occupiedWithSentinels; return true; } return false; } @Override public boolean retainAll(short... source) { return this.retainAll(ShortHashSet.newSetWith(source)); } @Override public ShortSet freeze() { ShortByteHashMap.this.copyKeysOnWrite = true; boolean containsZeroKey = false; boolean containsOneKey = false; if (ShortByteHashMap.this.sentinelValues != null) { containsZeroKey = ShortByteHashMap.this.sentinelValues.containsZeroKey; containsOneKey = ShortByteHashMap.this.sentinelValues.containsOneKey; } return new ImmutableShortMapKeySet(ShortByteHashMap.this.keys, ShortByteHashMap.this.occupiedWithData, containsZeroKey, containsOneKey); }
Since:9.2.
/** * @since 9.2. */
@Override public MutableShortSet newEmpty() { return new ShortHashSet(); } } @Override public MutableByteCollection values() { return new ValuesCollection(); } private class ValuesCollection extends AbstractByteValuesCollection { @Override public MutableByteIterator byteIterator() { return ShortByteHashMap.this.byteIterator(); } @Override public boolean remove(byte item) { int oldSize = ShortByteHashMap.this.size(); if (ShortByteHashMap.this.sentinelValues != null) { if (ShortByteHashMap.this.sentinelValues.containsZeroKey && item == ShortByteHashMap.this.sentinelValues.zeroValue) { ShortByteHashMap.this.removeKey(EMPTY_KEY); } if (ShortByteHashMap.this.sentinelValues.containsOneKey && item == ShortByteHashMap.this.sentinelValues.oneValue) { ShortByteHashMap.this.removeKey(REMOVED_KEY); } } for (int i = 0; i < ShortByteHashMap.this.keys.length; i++) { if (isNonSentinel(ShortByteHashMap.this.keys[i]) && item == ShortByteHashMap.this.values[i]) { ShortByteHashMap.this.removeKey(ShortByteHashMap.this.keys[i]); } } return oldSize != ShortByteHashMap.this.size(); } @Override public boolean retainAll(ByteIterable source) { int oldSize = ShortByteHashMap.this.size(); ByteSet sourceSet = source instanceof ByteSet ? (ByteSet) source : source.toSet(); ShortByteHashMap retained = ShortByteHashMap.this.select((short key, byte value) -> sourceSet.contains(value)); if (retained.size() != oldSize) { ShortByteHashMap.this.keys = retained.keys; ShortByteHashMap.this.values = retained.values; ShortByteHashMap.this.sentinelValues = retained.sentinelValues; ShortByteHashMap.this.occupiedWithData = retained.occupiedWithData; ShortByteHashMap.this.occupiedWithSentinels = retained.occupiedWithSentinels; return true; } return false; }
Since:9.2.
/** * @since 9.2. */
@Override public MutableByteCollection newEmpty() { return new ByteHashBag(); } } private class KeyValuesView extends AbstractLazyIterable<ShortBytePair> { @Override public void each(Procedure<? super ShortBytePair> procedure) { if (ShortByteHashMap.this.sentinelValues != null) { if (ShortByteHashMap.this.sentinelValues.containsZeroKey) { procedure.value(PrimitiveTuples.pair(EMPTY_KEY, ShortByteHashMap.this.sentinelValues.zeroValue)); } if (ShortByteHashMap.this.sentinelValues.containsOneKey) { procedure.value(PrimitiveTuples.pair(REMOVED_KEY, ShortByteHashMap.this.sentinelValues.oneValue)); } } for (int i = 0; i < ShortByteHashMap.this.keys.length; i++) { if (isNonSentinel(ShortByteHashMap.this.keys[i])) { procedure.value(PrimitiveTuples.pair(ShortByteHashMap.this.keys[i], ShortByteHashMap.this.values[i])); } } } @Override public void forEachWithIndex(ObjectIntProcedure<? super ShortBytePair> objectIntProcedure) { int index = 0; if (ShortByteHashMap.this.sentinelValues != null) { if (ShortByteHashMap.this.sentinelValues.containsZeroKey) { objectIntProcedure.value(PrimitiveTuples.pair(EMPTY_KEY, ShortByteHashMap.this.sentinelValues.zeroValue), index); index++; } if (ShortByteHashMap.this.sentinelValues.containsOneKey) { objectIntProcedure.value(PrimitiveTuples.pair(REMOVED_KEY, ShortByteHashMap.this.sentinelValues.oneValue), index); index++; } } for (int i = 0; i < ShortByteHashMap.this.keys.length; i++) { if (isNonSentinel(ShortByteHashMap.this.keys[i])) { objectIntProcedure.value(PrimitiveTuples.pair(ShortByteHashMap.this.keys[i], ShortByteHashMap.this.values[i]), index); index++; } } } @Override public <P> void forEachWith(Procedure2<? super ShortBytePair, ? super P> procedure, P parameter) { if (ShortByteHashMap.this.sentinelValues != null) { if (ShortByteHashMap.this.sentinelValues.containsZeroKey) { procedure.value(PrimitiveTuples.pair(EMPTY_KEY, ShortByteHashMap.this.sentinelValues.zeroValue), parameter); } if (ShortByteHashMap.this.sentinelValues.containsOneKey) { procedure.value(PrimitiveTuples.pair(REMOVED_KEY, ShortByteHashMap.this.sentinelValues.oneValue), parameter); } } for (int i = 0; i < ShortByteHashMap.this.keys.length; i++) { if (isNonSentinel(ShortByteHashMap.this.keys[i])) { procedure.value(PrimitiveTuples.pair(ShortByteHashMap.this.keys[i], ShortByteHashMap.this.values[i]), parameter); } } } @Override public Iterator<ShortBytePair> iterator() { return new InternalKeyValuesIterator(); } public class InternalKeyValuesIterator implements Iterator<ShortBytePair> { private int count; private int position; private boolean handledZero; private boolean handledOne; @Override public ShortBytePair next() { if (!this.hasNext()) { throw new NoSuchElementException("next() called, but the iterator is exhausted"); } this.count++; if (!this.handledZero) { this.handledZero = true; if (ShortByteHashMap.this.containsKey(EMPTY_KEY)) { return PrimitiveTuples.pair(EMPTY_KEY, ShortByteHashMap.this.sentinelValues.zeroValue); } } if (!this.handledOne) { this.handledOne = true; if (ShortByteHashMap.this.containsKey(REMOVED_KEY)) { return PrimitiveTuples.pair(REMOVED_KEY, ShortByteHashMap.this.sentinelValues.oneValue); } } short[] keys = ShortByteHashMap.this.keys; while (!isNonSentinel(keys[this.position])) { this.position++; } ShortBytePair result = PrimitiveTuples.pair(keys[this.position], ShortByteHashMap.this.values[this.position]); this.position++; return result; } @Override public void remove() { throw new UnsupportedOperationException("Cannot call remove() on " + this.getClass().getSimpleName()); } @Override public boolean hasNext() { return this.count != ShortByteHashMap.this.size(); } } } }