Author: schor
Date: Fri Dec 15 15:32:56 2017
New Revision: 1818293
URL: http://svn.apache.org/viewvc?rev=1818293&view=rev
Log:
[UIMA-5674] multiple hash map upgrade using common code, fixing edge cases.
Added:
uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Common_hash_support.java
Modified:
uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2ObjHashMap.java
uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java
uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Obj2IntIdentityHashMap.java
uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/ObjHashSet.java
Added:
uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Common_hash_support.java
URL:
http://svn.apache.org/viewvc/uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Common_hash_support.java?rev=1818293&view=auto
==============================================================================
---
uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Common_hash_support.java
(added)
+++
uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Common_hash_support.java
Fri Dec 15 15:32:56 2017
@@ -0,0 +1,534 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 org.apache.uima.internal.util;
+
+import java.util.Arrays;
+import java.util.function.IntConsumer;
+import java.util.function.IntPredicate;
+import java.util.function.IntSupplier;
+
+/**
+ * A common superclass for hash maps and hash sets
+ *
+ */
+public abstract class Common_hash_support {
+
+ // set to true to collect statistics for tuning
+ // you have to also put a call to showHistogram() at the end of the run
+ protected static final boolean TUNE = false;
+
+ protected static final int MIN_SIZE = 10; // 10 / .66 =15.15
+ protected static final int MIN_CAPACITY = 16;
+ protected static final int MIN_CAPACITY_SHRINK = 64; // don't shrink below
this - thrashing
+
+ protected final float loadFactor;
+
+ protected final int initialCapacity;
+
+ protected int histogram [];
+ protected int maxProbe = 0;
+
+ protected int sizeWhichTriggersExpansion;
+ private int size = 0; // number of elements in the table
+
+ protected int removed = 0; // for rebalancing
+
+ /** set to the first found_removed when searching */
+ protected int found_removed;
+
+ protected boolean secondTimeShrinkable = false;
+
+ /**
+ * @param initialSizeBeforeExpanding the number of elements the table should
hold before expanding
+ */
+ public Common_hash_support(int initialSizeBeforeExpanding) {
+ this(initialSizeBeforeExpanding, 0.66F);
+ }
+
+ public Common_hash_support(int initialSizeBeforeExpanding, float factor) {
+ this.loadFactor = factor;
+ this.initialCapacity = tableSpace(initialSizeBeforeExpanding, factor);
+ if (TUNE) {
+ histogram = new int[200];
+ Arrays.fill(histogram, 0);
+ maxProbe = 0;
+ }
+ }
+
+ public Common_hash_support(Common_hash_support orig) {
+ this(orig.initialCapacity);
+ this.sizeWhichTriggersExpansion = orig.sizeWhichTriggersExpansion;
+ this.size = orig.size;
+ this.removed = orig.removed;
+ this.secondTimeShrinkable = orig.secondTimeShrinkable;
+
+ // copy doesn't do tuning measurements
+ this.histogram = null;
+ }
+
+ public void clear() {
+ // see if size is less than the 1/2 size that triggers expansion
+ if (size + removed < (sizeWhichTriggersExpansion >>> 1)) {
+ // if 2nd time then shrink by 50%
+ // this is done to avoid thrashing around the threshold
+ if (secondTimeShrinkable) {
+ secondTimeShrinkable = false;
+ final int newCapacity = Math.max(initialCapacity, keys_length() >>> 1);
+ if (newCapacity < keys_length()) {
+ newTable(newCapacity); // shrink table by 50%
+ size = 0;
+ removed = 0;
+ resetHistogram();
+ return;
+ } else { // don't shrink below minimum
+ clearExisting();
+ return;
+ }
+ } else {
+ secondTimeShrinkable = true;
+ }
+ } else {
+ secondTimeShrinkable = false; // reset this to require 2 triggers in a
row
+ }
+ clearExisting();
+ }
+
+ private void clearExisting() {
+ clearKeysAndValues();
+ size = 0;
+ removed = 0;
+ resetHistogram();
+ }
+
+ /** It gets a ref to the current value of table, and then searches that
array.
+ * Side effect: found_removed is set to the position of the first
REMOVED_KEY (if any) encountered
+ * during the search.
+ *
+ * @param key_validity_checks check the key is valid or throw
+ * @param key_hash compute the hash code of the key
+ * @param is_eq_sor_not_present true if the key at the int position is ==
to the key, or is 0
+ * @param is_removed_key true if the key at the int position is "removed"
+ * @return the probeAddr in keys array. The value is the not-present-value
if not found
+ */
+ protected int findPosition(
+ int hash,
+ IntPredicate is_eq_or_not_present,
+ IntPredicate is_removed_key) {
+
+ found_removed = -1;
+// final int hash = key_hash.getAsInt();
+
+// final int[] localKeys = keys;
+ final int bitMask = keys_length() - 1;
+
+ int nbrProbes = 1;
+ int probeDelta = 0;
+ int probeAddr = hash & bitMask;
+
+ for (;;) {
+
+ if (is_eq_or_not_present.test(probeAddr)) {
+ if (TUNE) {
+ updateHistogram(nbrProbes);
+ }
+ return probeAddr;
+ }
+
+ if (found_removed == -1 && is_removed_key.test(probeAddr)) {
+ found_removed = probeAddr;
+ }
+
+ if (TUNE) nbrProbes++;
+
+ if (probeDelta < 13) {
+ probeDelta ++; // stop at a prime
+ // which guarantees all slots eventually traversed.
+ }
+ probeAddr = bitMask & (probeAddr + probeDelta);
+ }
+
+//
+// // fast paths
+// if (is_eq_or_not_present.test(probeAddr)) {
+//// final int testKey = localKeys[probeAddr];
+//// if (testKey == 0 || testKey == key) {
+// if (TUNE) {
+// updateHistogram(1);
+// }
+// return probeAddr;
+// }
+// if (is_removed_key.test(probeAddr)) {
+//// testKey == REMOVED_KEY) {
+// found_removed = probeAddr;
+// }
+// return findPosition2(is_eq_or_not_present, is_removed_key, probeAddr);
+ }
+
+// private int findPosition2(IntPredicate is_eq_or_not_present,
+// IntPredicate is_removed_key,
+// int probeAddr) {
+// final int bitMask = keys_length() - 1;
+// int nbrProbes = 2;
+// int probeDelta = 1;
+// probeAddr = bitMask & (probeAddr + (probeDelta++));
+//
+// while (true) {
+// if (is_eq_or_not_present.test(probeAddr)) {
+//// final int testKey = localKeys[probeAddr];
+//// if (testKey == 0 || testKey == key) {
+// break;
+// }
+//
+// if (found_removed == -1 && is_removed_key.test(probeAddr)) {
+// found_removed = probeAddr;
+// }
+// nbrProbes++;
+// if (probeDelta < 13) {
+// probeDelta ++; // stop at a prime
+// // which guarantees all slots eventually traversed.
+// }
+// probeAddr = bitMask & (probeAddr + (probeDelta++));
+// }
+//
+// if (TUNE) {
+// final int pv = histogram[nbrProbes];
+//
+// histogram[nbrProbes] = 1 + pv;
+// if (maxProbe < nbrProbes) {
+// maxProbe = nbrProbes;
+// }
+// }
+// return probeAddr;
+// }
+
+ /**
+ * As REMOVED tokens populate,
+ * the number of 0's (representing free cells and
+ * also the end of bucket chain searches) drops.
+ *
+ * If this drops a lot, then searches take much longer.
+ * If there are no 0's left, searches never terminate!
+ *
+ * Keep the number of 0's at about 1 - load factor
+ *
+ */
+ private void maybeRebalanceRemoves() {
+ final int old_capacity = keys_length();
+ if (old_capacity <= MIN_CAPACITY_SHRINK) {
+ return;
+ }
+ int new_capacity = old_capacity >> 1;
+
+// //debug
+// int sz = size;
+
+ /******************************************************
+ * Logic for clearing out the removed markers in bulk
+ *
+ * 3 cases: resize up (never happens), down, or the same
+ *
+ * Don't clear out if there's room left unless
+ * there's too much room left and should downsize
+ *
+ * Don't over do - avoid thrashing, avoid work for small sizes
+ *
+ * Case for upsizing: none. It's guaranteed there are always enough
+ * 0's for the load factor, by put/add implementation.
+ *
+ * Case for downsizing: if the size < 1/3 of the new capacity or,
+ * number being removed would be > 1/3 of the new capacity
+ ******************************************************/
+
+ if (removed + size >= sizeWhichTriggersExpansion) {
+ Misc.internalError(); // put or add always keeps this false. remove
always reduces or keeps this value the same
+ }
+
+ // REMOVED tags if there are enough of them to make it worthwhile
+ // or if just should shrink because removed + size is smaller than 1/3 the
new capacity
+ int one_third_new_capacity = sizeWhichTriggersExpansion >> 2;
+ int one_half_new_capacity = new_capacity >> 1;
+ if (removed > one_half_new_capacity || (size < one_third_new_capacity)) {
+ if (size >= one_third_new_capacity) {
+ new_capacity = old_capacity;
+ }
+ if (TUNE) {
+ System.out.println("Capacity (maybe) decreasing from " + old_capacity
+ " to " + new_capacity + " removed= " + removed + " size= " + size);
+ }
+ copyOld2New(new_capacity, old_capacity);
+ }
+// //debug
+// if (sz != size)
+// System.out.println("debug");
+ }
+
+ /**
+ * This method calls the subclass's copy_to_new_table method,
+ * passing an inner lambda containing common code for copying old to new.
+ *
+ * That inner lambda, when invoked by the copy_to_new_table method,
+ * is passed another lambda of one argument (the old index)
+ * which is called to copy each element.
+ * @param new_capacity
+ * @param old_capacity
+ */
+ private void copyOld2New(int new_capacity, int old_capacity) {
+ copy_to_new_table(
+ new_capacity,
+ old_capacity,
+
+ // this code assigned to "commonCopy" arg
+ (IntConsumer copyToNew, IntPredicate is_valid_old_key) -> {
+ newTable(new_capacity);
+ removed = 0; // reset before put, otherwise, causes premature expansion
+ for (int i = 0; i < old_capacity; i++) {
+ if (is_valid_old_key.test(i)) {
+ copyToNew.accept(i);
+ }
+ }
+ });
+ }
+
+ /**
+ * advance pos until it points to a non 0 or is 1 past end
+ * If pos is negative, start at 0.
+ * Don't move if pos already has valid key
+ * @param pos
+ * @return updated pos
+ */
+ protected int moveToNextFilled(int pos) {
+ final int max = keys_length();
+ if (pos < 0) {
+ pos = 0;
+ }
+ while (true) {
+ if (pos >= max) {
+ return pos;
+ }
+ if (is_valid_key(pos)) {
+ return pos;
+ }
+ pos ++;
+ }
+ }
+
+ /**
+ * decrement pos until it points to a non 0 or is -1
+ * If pos is beyond end start at end.
+ * Don't move if pos already has valid key
+ * @param pos
+ * @return updated pos
+ */
+ protected int moveToPreviousFilled(int pos) {
+ final int max = keys_length();
+ if (pos > max) {
+ pos = max - 1;
+ }
+
+ while (true) {
+ if (pos < 0) {
+ return pos;
+ }
+ if (is_valid_key(pos)) {
+ return pos;
+ }
+ pos --;
+ }
+ }
+
+ // called by clear, increase table size, decrease table size
+ protected void newTable(int capacity) {
+ capacity = Math.max(MIN_SIZE, Misc.nextHigherPowerOf2(capacity));
+ newKeysAndValues(capacity);
+ sizeWhichTriggersExpansion = (int)(capacity * loadFactor);
+ }
+
+ protected void incrementSize() {
+ size++;
+ if (size + removed >= sizeWhichTriggersExpansion) {
+ maybeIncreaseTableCapacity();
+ }
+ }
+
+ private void maybeIncreaseTableCapacity() {
+ int old_capacity = keys_length();
+ int new_capacity = (removed >= size)
+ ? old_capacity
+ : 2 * old_capacity;
+
+ if (TUNE) {
+ System.out.println("Capacity (maybe) increasing from " + old_capacity +
" to " + new_capacity + ", removes= " + removed + " size=" + size);
+ }
+
+ copyOld2New(new_capacity, old_capacity);
+ }
+
+ /**
+ *
+ * @param keyNotFound -
+ * @return true if keyNotFound
+ */
+ protected void commonPutOrAddNotFound() {
+
+ if (found_removed != -1) {
+ removed --; // used up a removed slot
+ }
+ incrementSize();
+// debugValidate();
+ }
+
+ /**
+ * only called if actually found and removed an entry
+ */
+ protected void commonRemove() {
+ removed ++;
+ size --;
+ maybeRebalanceRemoves();
+// debugValidate();
+ }
+
+ public int size() {
+ return size;
+ }
+
+ @FunctionalInterface
+ public interface CommonCopyOld2New {
+ void apply(IntConsumer copyToNew, IntPredicate is_valid_old_key);
+ }
+ protected abstract boolean is_valid_key(int pos);
+ protected abstract int keys_length();
+ protected abstract void newKeysAndValues(int capacity);
+ protected abstract void clearKeysAndValues();
+ protected abstract void copy_to_new_table(int new_capacity, int
old_capacity, CommonCopyOld2New r);
+
+ protected void resetHistogram() {
+ if (TUNE) {
+ histogram = new int[200];
+ Arrays.fill(histogram, 0);
+ maxProbe = 0;
+ }
+ }
+
+ private void updateHistogram(int nbrProbes) {
+ histogram[nbrProbes] = 1 + histogram[nbrProbes];
+ if (maxProbe < nbrProbes) {
+ maxProbe = nbrProbes;
+ }
+ }
+
+ public void showHistogram() {
+ if (TUNE) {
+ int sumI = 0;
+ for (int i : histogram) {
+ sumI += i;
+ }
+
+ System.out.format(
+ "Histogram of number of probes, loadfactor = %.1f, maxProbe=%,d nbr
of find operations at last table size=%,d%n",
+ loadFactor, maxProbe, sumI);
+ for (int i = 0; i <= maxProbe; i++) {
+ if (i == maxProbe && histogram[i] == 0) {
+ System.out.println("huh?");
+ }
+ System.out.println(i + ": " + histogram[i]);
+ }
+
+ System.out.println("bytes / entry = " + (float) (keys_length()) * 8 /
size());
+ System.out.format("size = %,d, prevExpansionTriggerSize = %,d, next =
%,d%n",
+ size(),
+ (int) ((keys_length() >>> 1) * loadFactor),
+ (int) (keys_length() * loadFactor));
+ }
+ }
+
+ // test case use
+ int getCapacity() {
+ return keys_length();
+ }
+
+ protected abstract class CommonKeyIterator implements IntListIterator {
+
+ protected int curPosition;
+
+ protected final int firstPosition;
+
+ protected CommonKeyIterator() {
+ this.curPosition = moveToNextFilled(0);
+ firstPosition = curPosition;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return curPosition < keys_length() && curPosition >= 0;
+ }
+
+ @Override
+ public boolean hasPrevious() {
+ if (curPosition > keys_length() || curPosition <= 0) {
+ return false;
+ }
+
+ int test = moveToPreviousFilled(curPosition - 1);
+ return test >= 0;
+ }
+
+ @Override
+ /**
+ * @see org.apache.uima.internal.util.IntListIterator#moveToStart()
+ */
+ public void moveToStart() {
+ curPosition = moveToNextFilled(0);
+ }
+
+ @Override
+ /**
+ * @see org.apache.uima.internal.util.IntListIterator#moveToEnd()
+ */
+ public void moveToEnd() {
+ curPosition = moveToPreviousFilled(keys_length() - 1);
+ }
+
+ }
+
+ /**
+ *
+ * @param numberOfElements -
+ * @param factor -
+ * @return capacity of the main table (either 2 byte or 4 byte entries)
+ */
+ public static int tableSpace(int numberOfElements, Float factor) {
+ if (numberOfElements < 0) {
+ throw new IllegalArgumentException("must be > 0");
+ }
+ final int capacity = Math.round(numberOfElements / factor);
+ return Math.max(16, Misc.nextHigherPowerOf2(capacity));
+ }
+
+ protected void debugValidate() {
+ // count non-0, non-removed, compare to size
+ int sum = 0;
+ for (int i = 0; i < keys_length(); i ++) {
+ if (is_valid_key(i)) {
+ sum ++;
+ if (sum > size) {
+ System.out.println("debug");
+ }
+ }
+ }
+ }
+}
Modified:
uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2ObjHashMap.java
URL:
http://svn.apache.org/viewvc/uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2ObjHashMap.java?rev=1818293&r1=1818292&r2=1818293&view=diff
==============================================================================
---
uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2ObjHashMap.java
(original)
+++
uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2ObjHashMap.java
Fri Dec 15 15:32:56 2017
@@ -21,8 +21,11 @@ package org.apache.uima.internal.util;
import java.lang.reflect.Array;
import java.util.Arrays;
+import java.util.HashSet;
import java.util.Iterator;
import java.util.NoSuchElementException;
+import java.util.function.Consumer;
+import java.util.function.IntConsumer;
import org.apache.uima.util.impl.Constants;
@@ -39,132 +42,35 @@ import org.apache.uima.util.impl.Constan
* keys are non-0 ints
* - 0 is reserved for the empty key slot
* - Integer.MIN_VALUE is reserved for removed slot
- * Entry set not (yet) impl
*
* values can be anything, but null is the value returned by get if not found
so
* values probably should not be null
*
- * remove not currently supported
+ * remove supported by replacing the value slot with null, and replacing the
key slot with a "removed" token.
+ * A cleanout of removed items occurs when necessary.
*
*/
-public class Int2ObjHashMap<T> {
-
- private class KeyIterator implements IntListIterator {
+public class Int2ObjHashMap<T> extends Common_hash_support implements
Iterable<IntEntry<T>>{
+
+ private static final int REMOVED_KEY = Integer.MIN_VALUE;
- /**
- * Keep this always pointing to a non-0 entry, or
- * if not valid, outside the range
- */
- private int curPosition;
-
- private final int firstPosition;
-
- private KeyIterator() {
- this.curPosition = 0;
- moveToNextFilled();
- firstPosition = curPosition;
- }
+ private class KeyIterator extends CommonKeyIterator implements
IntListIterator {
- public final boolean hasNext() {
- return curPosition < keys.length;
- }
-
- public final int next() {
-
-// if (!hasNext()) {
-// throw new NoSuchElementException();
-// }
- try {
- final int r = keys[curPosition++];
- moveToNextFilled();
- return r;
- } catch (IndexOutOfBoundsException e) {
- throw new NoSuchElementException();
- }
- }
-
- /**
- * @see org.apache.uima.internal.util.IntListIterator#hasPrevious()
- */
- public boolean hasPrevious() {
- return (curPosition > firstPosition);
- }
-
- /**
- * @see org.apache.uima.internal.util.IntListIterator#previous()
- */
- public int previous() {
- if (!hasPrevious()) {
- throw new NoSuchElementException();
- }
- curPosition --;
- moveToPreviousFilled();
- return keys[curPosition];
- }
-
- /**
- * @see org.apache.uima.internal.util.IntListIterator#moveToEnd()
- */
- public void moveToEnd() {
- curPosition = keys.length - 1;
- moveToPreviousFilled();
- }
-
- /**
- * @see org.apache.uima.internal.util.IntListIterator#moveToStart()
- */
- public void moveToStart() {
- curPosition = 0;
- moveToNextFilled();
+ @Override
+ public final int nextNvc() {
+ final int r = keys[curPosition];
+ curPosition = moveToNextFilled(curPosition + 1);
+ return r;
}
- /**
- * advance pos until it points to a non 0 or is 1 past end
- * @param pos
- * @return updated pos
- */
- private void moveToNextFilled() {
- final int max = keys.length;
- while (true) {
- if (curPosition >= max) {
- return;
- }
- if (keys[curPosition] != 0) {
- return;
- }
- curPosition ++;
- }
+ @Override
+ public int previousNvc() {
+ curPosition = moveToPreviousFilled(curPosition - 1);
+ return keys[curPosition];
}
-
- /**
- * decrement pos until it points to a non 0 or is -1
- * @param pos
- * @return updated pos
- */
- private void moveToPreviousFilled() {
- final int max = keys.length;
- if (curPosition > max) {
- curPosition = max - 1;
- }
-
- while (true) {
- if (curPosition < 0) {
- return;
- }
- if (keys[curPosition] != 0) {
- return;
- }
- curPosition --;
- }
- }
- }
-
-
- // set to true to collect statistics for tuning
- // you have to also put a call to showHistogram() at the end of the run
- private static final boolean TUNE = false;
-
+ }
+
// this load factor gives, for array doubling strategy:
// between 1.5 * 8 bytes (2 words, one for key, one for value) = 12 and
// 3 * 8 24 bytes
per entry
@@ -178,38 +84,36 @@ public class Int2ObjHashMap<T> {
// See corresponding Int2IntPerfTest which is disabled normally
- private final float loadFactor = (float)0.66;
-
- private final int initialCapacity;
-
- private int histogram [];
- private int maxProbe = 0;
-
- private int sizeWhichTriggersExpansion;
- private int size; // number of elements in the table
+// private final float loadFactor = (float)0.66;
+//
+// private final int initialCapacity;
+//
+// private int histogram [];
+// private int maxProbe = 0;
+//
+// private int sizeWhichTriggersExpansion;
+// private int size; // number of elements in the table
private int [] keys;
private T [] values;
- private boolean secondTimeShrinkable = false;
+// private boolean secondTimeShrinkable = false;
+
+ final private Class<T> componentType; // needed to make new instances of
the value array
+
+// /** set to the first found_removed when searching */
+// private int found_removed;
+
+// private int removed = 0; // for rebalancing
- final private Class<T> componentType;
-
public Int2ObjHashMap(Class<T> clazz) {
- this(clazz, 16);
+ this(clazz, MIN_SIZE);
}
- public Int2ObjHashMap(Class<T> clazz, int initialCapacity) {
+ public Int2ObjHashMap(Class<T> clazz, int initialSizeBeforeExpanding) {
+ super(initialSizeBeforeExpanding);
this.componentType = clazz;
- initialCapacity = Misc.nextHigherPowerOf2(initialCapacity);
- this.initialCapacity = initialCapacity;
- newTableKeepSize(initialCapacity);
- size = 0;
- if (TUNE) {
- histogram = new int[200];
- Arrays.fill(histogram, 0);
- maxProbe = 0;
- }
+ newTable(this.initialCapacity);
}
/**
@@ -217,197 +121,316 @@ public class Int2ObjHashMap<T> {
* @param clazz
* @param initialCapacity
*/
- private Int2ObjHashMap(
- Class<T> clazz,
- int initialCapacity,
- int sizeWhichTriggersExpansion,
- int size,
- int[] keys,
- T[] values) {
- this.componentType = clazz;
- this.initialCapacity = Misc.nextHigherPowerOf2(initialCapacity);
- this.sizeWhichTriggersExpansion = sizeWhichTriggersExpansion;
- this.histogram = null;
- this.size = size;
- this.keys = Arrays.copyOf(keys, keys.length);
- this.values = Arrays.copyOf(values, values.length);
+ private Int2ObjHashMap(Int2ObjHashMap orig) {
+ super(orig);
+ this.componentType = orig.componentType;
+ this.keys = Arrays.copyOf(orig.keys, keys.length);
+ this.values = (T[]) Arrays.copyOf(orig.values, values.length);
}
- private void newTableKeepSize(int capacity) {
- // minimum size is 16
- capacity = Math.max(16, Misc.nextHigherPowerOf2(capacity));
- keys = new int[capacity];
- values = (T[]) Array.newInstance(componentType, capacity);
- sizeWhichTriggersExpansion = (int)(capacity * loadFactor);
- }
-
- private void incrementSize() {
- if (size >= sizeWhichTriggersExpansion) {
- increaseTableCapacity();
- }
- size++;
- }
-
- private void increaseTableCapacity() {
- final int [] oldKeys = keys;
- final T [] oldValues = values;
- final int oldCapacity = oldKeys.length;
- int newCapacity = 2 * oldCapacity;
+// private void newTableKeepSize(int capacity) {
+// capacity = Math.max(MIN_SIZE, Misc.nextHigherPowerOf2(capacity));
+// keys = new int[capacity];
+// values = (T[]) Array.newInstance(componentType, capacity);
+// sizeWhichTriggersExpansion = (int)(capacity * loadFactor);
+// }
+
+// protected void incrementSize() {
+// if (size + removed >= sizeWhichTriggersExpansion) {
+// increaseTableCapacity();
+// }
+// size++;
+// }
+
+// private void increaseTableCapacity() {
+// final int [] oldKeys = keys;
+// final T [] oldValues = values;
+// final int oldCapacity = oldKeys.length;
+// int newCapacity = 2 * oldCapacity;
+//
+// if (TUNE) {
+// System.out.println("Capacity increasing from " + oldCapacity + " to "
+ newCapacity);
+// }
+// removed = 0;
+// newTableKeepSize(newCapacity);
+// int vi = 0;
+// for (int key : oldKeys) {
+// if (key != 0 && key != REMOVED_KEY) {
+// putInner(key, oldValues[vi]);
+// }
+// vi++;
+// }
+// }
- if (TUNE) {
- System.out.println("Capacity increasing from " + oldCapacity + " to " +
newCapacity);
- }
- newTableKeepSize(newCapacity);
- int vi = 0;
- for (int key : oldKeys) {
- if (key != 0) {
- putInner(key, oldValues[vi]);
- }
- vi++;
- }
- }
-
- // called by clear
- private void newTable(int capacity) {
- newTableKeepSize(capacity);
- size = 0;
- resetHistogram();
- }
-
- private void resetHistogram() {
- if (TUNE) {
- histogram = new int[200];
- Arrays.fill(histogram, 0);
- maxProbe = 0;
- }
- }
-
- public void clear() {
- // see if size is less than the 1/2 size that triggers expansion
- if (size < (sizeWhichTriggersExpansion >>> 1)) {
- // if 2nd time then shrink by 50%
- // this is done to avoid thrashing around the threshold
- if (secondTimeShrinkable) {
- secondTimeShrinkable = false;
- final int newCapacity = Math.max(initialCapacity, keys.length >>> 1);
- if (newCapacity < keys.length) {
- newTable(newCapacity); // shrink table by 50%
- } else { // don't shrink below minimum
- Arrays.fill(keys, 0);
- Arrays.fill(values, null);
- }
- size = 0;
- resetHistogram();
- return;
- } else {
- secondTimeShrinkable = true;
- }
- } else {
- secondTimeShrinkable = false; // reset this to require 2 triggers in a
row
- }
- size = 0;
- Arrays.fill(keys, 0);
- Arrays.fill(values, null);
- resetHistogram();
- }
+// // called by clear
+// private void newTable(int capacity) {
+// newTableKeepSize(capacity);
+// size = 0;
+// resetHistogram();
+// }
+
+// private void resetHistogram() {
+// if (TUNE) {
+// histogram = new int[200];
+// Arrays.fill(histogram, 0);
+// maxProbe = 0;
+// }
+// }
+
+// public void clear() {
+// // see if size is less than the 1/2 size that triggers expansion
+// if (size < (sizeWhichTriggersExpansion >>> 1)) {
+// // if 2nd time then shrink by 50%
+// // this is done to avoid thrashing around the threshold
+// if (secondTimeShrinkable) {
+// secondTimeShrinkable = false;
+// final int newCapacity = Math.max(initialCapacity, keys.length >>> 1);
+// if (newCapacity < keys.length) {
+// newTable(newCapacity); // shrink table by 50%
+// } else { // don't shrink below minimum
+// Arrays.fill(keys, 0);
+// Arrays.fill(values, null);
+// }
+// size = 0;
+// resetHistogram();
+// return;
+// } else {
+// secondTimeShrinkable = true;
+// }
+// } else {
+// secondTimeShrinkable = false; // reset this to require 2 triggers in a
row
+// }
+// size = 0;
+// Arrays.fill(keys, 0);
+// Arrays.fill(values, null);
+// resetHistogram();
+// }
- /** It gets a ref to the current value of table, and then searches that int
array.
- *
- * @param key -
- * @return the probeAddr in keys array - might have a 0 value, or the key
value if found
- */
- private int find(final int key) {
- if (key == 0) {
+ /**
+ * Searches the keys for a match
+ * @param key -
+ * @return the probeAddr in keys array - The value[probeAddr] is 0 value if
not found
+ */
+
+ private int findPosition(final int key) {
+
+ if (key == 0) {
throw new IllegalArgumentException("0 is an invalid key");
}
-
- final int hash = Misc.hashInt(key);
-
- final int[] localKeys = keys;
- final int bitMask = localKeys.length - 1;
- int probeAddr = hash & bitMask;
-
- // fast paths
- final int testKey = localKeys[probeAddr];
- if (testKey == 0 || testKey == key) {
- if (TUNE) {
- updateHistogram(1);
- }
- return probeAddr;
- }
-
- return find2(localKeys, key, probeAddr);
- }
-
- private int find2(final int[] localKeys, final int key, int probeAddr) {
- final int bitMask = localKeys.length - 1;
- int nbrProbes = 2;
- int probeDelta = 1;
- probeAddr = bitMask & (probeAddr + (probeDelta++));
-
- while (true) {
- final int testKey = localKeys[probeAddr];
- if (testKey == 0 || testKey == key) {
- break;
- }
- nbrProbes++;
- probeAddr = bitMask & (probeAddr + (probeDelta++));
- }
-
- if (TUNE) {
- final int pv = histogram[nbrProbes];
-
- histogram[nbrProbes] = 1 + pv;
- if (maxProbe < nbrProbes) {
- maxProbe = nbrProbes;
- }
- }
- return probeAddr;
- }
-
- private void updateHistogram(int nbrProbes) {
- histogram[nbrProbes] = 1 + histogram[nbrProbes];
- if (maxProbe < nbrProbes) {
- maxProbe = nbrProbes;
+ if (key == REMOVED_KEY) {
+ throw new IllegalArgumentException("Integer.MIN_VALUE is an invalid
key");
}
+
+
+ return findPosition(
+
+ // key hash
+ Misc.hashInt(key),
+
+ //is_eq_or_is_not_present
+ i -> keys[i] == 0 || keys[i] == key,
+
+ // is_removed_key
+ i -> keys[i] == REMOVED_KEY
+
+ );
+
}
+// private int find(final int key) {
+// if (key == 0) {
+// throw new IllegalArgumentException("0 is an invalid key");
+// }
+// if (key == REMOVED_KEY) {
+// throw new IllegalArgumentException("Integer.MIN_VALUE is an invalid
key");
+// }
+// found_removed = 0;
+// final int hash = Misc.hashInt(key);
+//
+// final int[] localKeys = keys;
+// final int bitMask = localKeys.length - 1;
+// int probeAddr = hash & bitMask;
+//
+// // fast paths
+// final int testKey = localKeys[probeAddr];
+// if (testKey == 0 || testKey == key) {
+// if (TUNE) {
+// updateHistogram(1);
+// }
+// return probeAddr;
+// }
+// if (testKey == REMOVED_KEY) {
+// found_removed = probeAddr;
+// }
+// return find2(localKeys, key, probeAddr);
+// }
+
+// private int find2(final int[] localKeys, final int key, int probeAddr) {
+// final int bitMask = localKeys.length - 1;
+// int nbrProbes = 2;
+// int probeDelta = 1;
+// probeAddr = bitMask & (probeAddr + (probeDelta++));
+//
+// while (true) {
+// final int testKey = localKeys[probeAddr];
+// if (testKey == 0 || testKey == key) {
+// break;
+// }
+// if (found_removed == 0 && testKey == REMOVED_KEY) {
+// found_removed = probeAddr;
+// }
+// nbrProbes++;
+// probeAddr = bitMask & (probeAddr + (probeDelta++));
+// }
+//
+// if (TUNE) {
+// final int pv = histogram[nbrProbes];
+//
+// histogram[nbrProbes] = 1 + pv;
+// if (maxProbe < nbrProbes) {
+// maxProbe = nbrProbes;
+// }
+// }
+// return probeAddr;
+// }
+
+// private void updateHistogram(int nbrProbes) {
+// histogram[nbrProbes] = 1 + histogram[nbrProbes];
+// if (maxProbe < nbrProbes) {
+// maxProbe = nbrProbes;
+// }
+// }
public T get(int key) {
- return (key == 0) ? null : values[find(key)];
+ return (key == 0) ? null : values[findPosition(key)];
}
- public boolean containsKey(int key) {
- int probeAddr = find(key);
- return probeAddr != 0 && keys[probeAddr] != 0;
+ public T remove(int key) {
+ int pos = findPosition(key);
+ T v = values[pos];
+ int k = keys[pos];
+ if (k != 0) {
+ values[pos] = null;
+ keys[pos] = REMOVED_KEY;
+ commonRemove();
+ }
+ return v;
+ }
+
+// private void maybeRebalanceRemoves() {
+// final int new_capacity = keys.length >> 1;
+// if (removed > REBALANCE_MIN_REMOVED &&
+// removed > new_capacity) {
+// // cleanup will remove more than 1/2 the items
+//
+// int [] oldKeys = keys;
+// T [] oldValues = values;
+// newTable(new_capacity);
+// removed = 0; // reset before put, otherwise, causes premature expansion
+//
+// for (int i = 0; i < oldKeys.length; i++) {
+// int k = oldKeys[i];
+// if (k != 0 && k != REMOVED_KEY) {
+// put(k, oldValues[i]);
+// }
+// }
+// }
+// }
+
+ protected void copy_to_new_table(
+ /* ignored */int newCapacity,
+ /* ignored */int oldCapacity,
+ CommonCopyOld2New commonCopy) {
+ int [] oldKeys = keys;
+ T [] oldValues = values;
+ commonCopy.apply(
+
+ // copyToNew
+ i ->
+ putInner(oldKeys[i], oldValues[i]),
+
+ // is_valid_old_key
+ i ->
+ oldKeys[i] != 0 && oldKeys[i] != REMOVED_KEY);
}
- public boolean isKeyValid(int position) {
- return (position != 0) && (keys[position] != 0);
+ // debug
+// private void dump(int[] ks) {
+// HashSet<Integer> found = new HashSet<>();
+// int nbr0 = 0;
+// int nbrRmv = 0;
+// for (int k : ks) {
+// if (k == 0) {
+// nbr0++;
+// } else if (k == REMOVED_KEY) {
+// nbrRmv ++;
+// } else {
+// boolean wasAdded = found.add(k);
+// if (! wasAdded) {
+// System.out.println("dups");
+// }
+// }
+// }
+// }
+//
+// private boolean checkKeyExists(int key) {
+// int c = 0;
+// for (int i = 0; i < keys.length; i++) {
+// int k = keys[i];
+// if (k == key) {
+// c++;
+// if (c > 1) {
+// System.out.println("found key " + key + " in position " + i);
+// return true;
+// }
+// }
+// }
+// return false;
+// }
+
+
+ public boolean containsKey(int key) {
+ int probeAddr = findPosition(key);
+ return keys[probeAddr] != 0 ;
}
-
+
public T put(int key, T value) {
- final int i = find(key);
+ int i = findPosition(key);
final boolean keyNotFound = keys[i] == 0;
final T prevValue = values[i];
+
+ if (! keyNotFound) { // key found
+ values[i] = value;
+ return prevValue;
+ }
+
+ if (found_removed != -1) {
+ i = found_removed; // use the removed slot for the new value
+ }
+// //debug
+// if (checkKeyExists(key)) {
+// find(key);
+// System.out.println("stop");
+// }
+// // debug
+// if (key == 322 && (i == 618 || i == 617)) {
+// find(key);
+// System.out.println("stop");
+// }
+
keys[i] = key;
values[i] = value;
- if (keyNotFound) {
- incrementSize();
- }
+
+ commonPutOrAddNotFound();
return prevValue;
}
public void putInner(int key, T value) {
- final int i = find(key);
+ final int i = findPosition(key);
assert (keys[i] == 0);
keys[i] = key;
values[i] = value;
}
-
- public int size() {
- return size;
- }
-
+
public int[] getSortedKeys() {
final int size = size();
if (size == 0) {
@@ -416,7 +439,7 @@ public class Int2ObjHashMap<T> {
final int[] r = new int[size];
int i = 0;
for (int k : keys) {
- if (k != 0) {
+ if (k != 0 && k != REMOVED_KEY) {
r[i++] = k;
}
}
@@ -437,6 +460,9 @@ public class Int2ObjHashMap<T> {
throw new UnsupportedOperationException();// only makes sense for sorted
things
}
+ /**
+ * @return an iterator<T> over the values in random order
+ */
public Iterator<T> values() {
return new Iterator<T>() {
@@ -444,10 +470,8 @@ public class Int2ObjHashMap<T> {
* Keep this always pointing to a non-0 entry, or
* if not valid, outside the range
*/
- private int curPosition = 0;
- { moveToNextFilled(); } // non-static initializer
+ private int curPosition = moveToNextFilled(0);
-
@Override
public boolean hasNext() {
return curPosition < keys.length;
@@ -455,57 +479,83 @@ public class Int2ObjHashMap<T> {
@Override
public T next() {
- try {
- final T r = values[curPosition++];
- moveToNextFilled();
- return r;
- } catch (IndexOutOfBoundsException e) {
+ if (!hasNext()) {
throw new NoSuchElementException();
}
+ T r = values[curPosition];
+ curPosition = moveToNextFilled(curPosition + 1);
+ return r;
}
- private void moveToNextFilled() {
- final int max = keys.length;
- while (true) {
- if (curPosition >= max) {
- return;
- }
- if (keys[curPosition] != 0) {
- return;
- }
- curPosition ++;
- }
- }
+// private void moveToNextFilled() {
+// final int max = keys.length;
+// while (true) {
+// if (curPosition >= max) {
+// return;
+// }
+// int k = keys[curPosition];
+// if (k != 0 && k != REMOVED_KEY) {
+// return;
+// }
+// curPosition ++;
+// }
+// }
};
}
- public void showHistogram() {
- if (TUNE) {
- int sumI = 0;
- for (int i : histogram) {
- sumI += i;
- }
+ public Int2ObjHashMap<T> copy() {
+ return new Int2ObjHashMap<>(this);
+ }
+
+ @Override
+ public Iterator<IntEntry<T>> iterator() {
+
+ return new Iterator<IntEntry<T>>() {
- System.out.format(
- "Histogram of number of probes, loadfactor = %.1f, maxProbe=%,d nbr
of find operations at last table size=%,d%n",
- loadFactor, maxProbe, sumI);
- for (int i = 0; i <= maxProbe; i++) {
- if (i == maxProbe && histogram[i] == 0) {
- System.out.println("huh?");
+ /**
+ * Keep this always pointing to a non-0 entry, or
+ * if not valid, outside the range
+ */
+ private int curPosition = moveToNextFilled(0);
+
+ @Override
+ public boolean hasNext() {
+ return curPosition < keys.length;
+ }
+
+ @Override
+ public IntEntry next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
}
- System.out.println(i + ": " + histogram[i]);
- }
+ final IntEntry<T> r = new IntEntry<>(keys[curPosition],
values[curPosition]);
+ curPosition = moveToNextFilled(curPosition + 1);
+ return r;
+ }
- System.out.println("bytes / entry = " + (float) (keys.length) * 8 /
size());
- System.out.format("size = %,d, prevExpansionTriggerSize = %,d, next =
%,d%n",
- size(),
- (int) ((keys.length >>> 1) * loadFactor),
- (int) (keys.length * loadFactor));
- }
+ };
+
}
- public Int2ObjHashMap<T> copy() {
- return new Int2ObjHashMap<>(componentType, initialCapacity,
sizeWhichTriggersExpansion, size, keys, values);
+ protected int keys_length() {
+ return keys.length;
+ }
+
+ @Override
+ protected boolean is_valid_key(int pos) {
+ return keys[pos] != 0 && keys[pos] != REMOVED_KEY;
+ }
+
+ @Override
+ protected void newKeysAndValues(int size) {
+ keys = new int[size];
+ values = (T[]) Array.newInstance(componentType, size);
+ }
+
+ @Override
+ protected void clearKeysAndValues() {
+ Arrays.fill(keys, 0);
+ Arrays.fill(values, null);
}
}
Modified:
uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java
URL:
http://svn.apache.org/viewvc/uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java?rev=1818293&r1=1818292&r2=1818293&view=diff
==============================================================================
---
uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java
(original)
+++
uima/uv3/uimaj-v3/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java
Fri Dec 15 15:32:56 2017
@@ -21,11 +21,14 @@ package org.apache.uima.internal.util;
import java.util.Arrays;
import java.util.NoSuchElementException;
+import java.util.function.IntPredicate;
import org.apache.uima.util.impl.Constants;
/**
* A set of non-zero ints.
+ * Can be negative.
+ *
* 0 reserved internally to indicate "not in the map";
* you will get an exception if you try to store 0 as a value.
*
@@ -51,40 +54,18 @@ import org.apache.uima.util.impl.Constan
*
* Automatically switches to full int representation if needed
*/
-public class IntHashSet implements PositiveIntSet {
+public class IntHashSet extends Common_hash_support implements PositiveIntSet {
- public static final int SIZE_NEEDING_4_BYTES = 256 * 256 - 2;
- public static final float DEFAULT_LOAD_FACTOR = 0.66F;
+ public static final int SIZE_NEEDING_4_BYTES = 256 * 256 - 2;
private static final int REMOVED4 = Integer.MIN_VALUE;
private static final int REMOVED2 = Short.MIN_VALUE;
- // set to true to collect statistics for tuning
- // you have to also put a call to showHistogram() at the end of the run
- private static final boolean TUNE = false;
-
- static int nextHigherPowerOf2(int i) {
- return (i < 1) ? 1 : Integer.highestOneBit(i) << ( (Integer.bitCount(i) ==
1 ? 0 : 1));
- }
-
// this load factor gives, for array doubling strategy:
// between 1.5 * 4 bytes (1 word for key) = 6 and
// 3 * 4 12 bytes per entry
// This compares with 160 bytes/entry for the IntArrayRBT impl
-
- private final float loadFactor = DEFAULT_LOAD_FACTOR;
-
- private final int initialCapacity;
-
- private int histogram [];
- private int maxProbe = 0;
-
- private int sizeWhichTriggersExpansion;
- private int size; // number of elements in the table
- private int nbrRemoved; // number of removed elements (coded as removed)
-
- private int removedPositionToUse = -1;
-
+
// offset only used with keys2. values stored are key - offset
// intent is to have them fit into short data type.
// If the offset is 100,000, then the keys range from 100000 - 32766 to
100000 + 32767, includes "0"
@@ -97,15 +78,15 @@ public class IntHashSet implements Posit
private int [] keys4;
private short[] keys2;
-
- private boolean secondTimeShrinkable = false;
+
+ private boolean isMake4;
// these are true values (before any offset adjustment)
private int mostPositive = Integer.MIN_VALUE;
private int mostNegative = Integer.MAX_VALUE;
public IntHashSet() {
- this(12, 0);
+ this(10, 0);
}
public IntHashSet(int initialCapacity) {
@@ -114,87 +95,92 @@ public class IntHashSet implements Posit
/**
*
- * @param initialCapacity - you can add this many before expansion
+ * @param initialSizeBeforeExpanding - you can add this many before expansion
* @param offset - for values in the short range, the amount to subtract
* before storing.
* If == MIN_VALUE, then force 4 byte ints
*/
- public IntHashSet(int initialCapacity, int offset) {
- this.initialCapacity = initialCapacity;
- boolean force4 = offset == Integer.MIN_VALUE;
- this.offset = force4 ? 0 : offset;
- newTableKeepSize(tableSpace(initialCapacity), force4);
- size = 0;
- if (TUNE) {
- histogram = new int[200];
- Arrays.fill(histogram, 0);
- maxProbe = 0;
- }
+ public IntHashSet(int initialSizeBeforeExpanding, int offset) {
+ super(initialSizeBeforeExpanding);
+ isMake4 = offset == Integer.MIN_VALUE;
+ this.offset = isMake4 ? 0 : offset;
+ newTable(this.initialCapacity);
+ resetTable();
}
- /**
- * The number of 32 bit words that are reserved when
- * creating a table to hold the specified number of elements
- *
- * The number is a power of 2.
- *
- * The number is at least 16.
- *
- * The number is such that you could add this many elements without
- * triggering the capacity expansion.
- *
- * @param numberOfElements -
- * @return -
- */
- public int tableSpace(int numberOfElements) {
- return tableSpace(numberOfElements, loadFactor);
- }
+// /**
+// * The number of 32 bit words that are reserved when
+// * creating a table to hold the specified number of elements
+// *
+// * The number is a power of 2.
+// *
+// * The number is at least 16.
+// *
+// * The number is such that you could add this many elements without
+// * triggering the capacity expansion.
+// *
+// * @param numberOfElements -
+// * @return -
+// */
+// public int tableSpace(int numberOfElements) {
+// return tableSpace(numberOfElements, loadFactor);
+// }
+//
- /**
- *
- * @param numberOfElements -
- * @param factor -
- * @return capacity of the main table (either 2 byte or 4 byte entries)
- */
- public static int tableSpace(int numberOfElements, Float factor) {
- if (numberOfElements < 0) {
- throw new IllegalArgumentException("must be > 0");
- }
- final int capacity = Math.round(numberOfElements / factor);
- return Math.max(16, nextHigherPowerOf2(capacity));
- }
-
- private void newTableKeepSize(int capacity, boolean make4) {
- if (!make4) {
- capacity = Math.max(4, nextHigherPowerOf2(capacity));
- make4 = (capacity >= SIZE_NEEDING_4_BYTES);
- }
- // don't use short values unless
- // the number of items is < 65536
- if (make4) {
- keys4 = new int[capacity];
- keys2 = null;
- } else {
- keys2 = new short[capacity];
- keys4 = null;
- }
- sizeWhichTriggersExpansion = (int)(capacity * loadFactor);
- nbrRemoved = 0;
- }
-
- private void incrementSize() {
- if ((size + nbrRemoved) >= sizeWhichTriggersExpansion) {
- increaseTableCapacity();
- }
- size++;
+ public static int tableSpace(int numberOfElements) {
+ return Common_hash_support.tableSpace(numberOfElements, 0.66f);
}
+// /**
+// *
+// * @param numberOfElements -
+// * @param factor -
+// * @return capacity of the main table (either 2 byte or 4 byte entries)
+// */
+// public static int tableSpace(int numberOfElements, Float factor) {
+// if (numberOfElements < 0) {
+// throw new IllegalArgumentException("must be > 0");
+// }
+// final int capacity = Math.round(numberOfElements / factor);
+// return Math.max(16, Misc.nextHigherPowerOf2(capacity));
+// }
+//
+// private void newTableKeepSize(int capacity, boolean make4) {
+// if (!make4) {
+// capacity = Math.max(4, nextHigherPowerOf2(capacity));
+// // don't use short values unless
+// // the number of items is < 65536
+// make4 = (capacity >= SIZE_NEEDING_4_BYTES);
+// }
+//
+// if (make4) {
+// keys4 = new int[capacity];
+// keys2 = null;
+// } else {
+// keys2 = new short[capacity];
+// keys4 = null;
+// }
+// sizeWhichTriggersExpansion = (int)(capacity * loadFactor);
+// nbrRemoved = 0;
+// }
+
+ /**
+ * Method called by handleHashSet in PositiveIntSet
+ * to indicate if adding this many items would cause an expansion
+ * @return true if would not expand
+ */
public boolean wontExpand() {
return wontExpand(1);
}
+ /**
+ * Method called by handleHashSet in PositiveIntSet
+ * to indicate if adding this many items would cause an expansion
+ * @param n the number of items added
+ * @return true if would not expand
+ */
public boolean wontExpand(int n) {
- return (size + nbrRemoved + n) < sizeWhichTriggersExpansion;
+ return (size() + removed + n) < sizeWhichTriggersExpansion;
}
public int getSpaceUsedInWords() {
@@ -204,11 +190,7 @@ public class IntHashSet implements Posit
public static int getSpaceOverheadInWords() {
return 11;
}
-
- private int getCapacity() {
- return (null == keys4) ? keys2.length : keys4.length;
- }
-
+
/**
* Only call this if using short values with offset
* @param adjKey
@@ -219,174 +201,176 @@ public class IntHashSet implements Posit
return adjKey + offset + ((adjKey < 0) ? 1 : 0);
}
- private void increaseTableCapacity() {
- final int oldCapacity = getCapacity();
- // keep same capacity if just removing the "removed" markers would
- // shrink the used slots to the same they would have been had there been
no removed, and
- // the capacity was doubled.
- final int newCapacity = (nbrRemoved > size) ? oldCapacity : oldCapacity <<
1;
-
- if (keys2 != null) {
- final short[] oldKeys = keys2;
- newTableKeepSize(newCapacity, false);
- if (newCapacity >= 256 * 256) { // = 65536
- // switch to 4
- if (TUNE) {System.out.println("Switching to 4 byte keys, Capacity
increasing from " + oldCapacity + " to " + newCapacity);}
- for (short adjKey : oldKeys) {
- if (adjKey != 0 && adjKey != REMOVED2) {
- addInner4(getRawFromAdjKey(adjKey));
- }
- }
-
- } else {
- if (TUNE) {System.out.println("Keeping 2 byte keys, Capacity
increasing from " + oldCapacity + " to " + newCapacity);}
- for (short adjKey : oldKeys) {
- if (adjKey != 0 && adjKey != REMOVED2) {
- addInner2(adjKey);
- }
- }
- }
-
- } else {
- final int [] oldKeys = keys4;
- if (TUNE) {System.out.println("Capacity increasing from " + oldCapacity
+ " to " + newCapacity);}
- newTableKeepSize(newCapacity, true);
- for (int key : oldKeys) {
- if (key != 0 && key != REMOVED4) {
- addInner4(key);
- }
- }
- }
- }
+// private void increaseTableCapacity() {
+// final int oldCapacity = getCapacity();
+// // keep same capacity if just removing the "removed" markers would
+// // shrink the used slots to the same they would have been had there been
no removed, and
+// // the capacity was doubled.
+// final int newCapacity = (nbrRemoved > size) ? oldCapacity : oldCapacity
<< 1;
+//
+// if (keys2 != null) {
+// final short[] oldKeys = keys2;
+// newTableKeepSize(newCapacity, false);
+// if (newCapacity >= 256 * 256) { // = 65536
+// // switch to 4
+// if (TUNE) {System.out.println("Switching to 4 byte keys, Capacity
increasing from " + oldCapacity + " to " + newCapacity);}
+// for (short adjKey : oldKeys) {
+// if (adjKey != 0 && adjKey != REMOVED2) {
+// addInner4(getRawFromAdjKey(adjKey));
+// }
+// }
+//
+// } else {
+// if (TUNE) {System.out.println("Keeping 2 byte keys, Capacity
increasing from " + oldCapacity + " to " + newCapacity);}
+// for (short adjKey : oldKeys) {
+// if (adjKey != 0 && adjKey != REMOVED2) {
+// addInner2(adjKey);
+// }
+// }
+// }
+//
+// } else {
+// final int [] oldKeys = keys4;
+// if (TUNE) {System.out.println("Capacity increasing from " +
oldCapacity + " to " + newCapacity);}
+// newTableKeepSize(newCapacity, true);
+// for (int key : oldKeys) {
+// if (key != 0 && key != REMOVED4) {
+// addInner4(key);
+// }
+// }
+// }
+// }
- // called by clear
- private void newTable(int capacity) {
- newTableKeepSize(capacity, false);
- resetTable();
- }
-
- private void resetHistogram() {
- if (TUNE) {
- histogram = new int[200];
- Arrays.fill(histogram, 0);
- maxProbe = 0;
- }
- }
+// // called by clear
+// private void newTable(int capacity) {
+// newTableKeepSize(capacity, false);
+// resetTable();
+// }
+//
+// private void resetHistogram() {
+// if (TUNE) {
+// histogram = new int[200];
+// Arrays.fill(histogram, 0);
+// maxProbe = 0;
+// }
+// }
- private void resetArray() {
- if (keys4 == null) {
- Arrays.fill(keys2, (short)0);
- } else {
- Arrays.fill(keys4, 0);
- }
- resetTable();
- }
+// private void resetArray() {
+// if (keys4 == null) {
+// Arrays.fill(keys2, (short)0);
+// } else {
+// Arrays.fill(keys4, 0);
+// }
+// resetTable();
+// }
private void resetTable() {
mostPositive = Integer.MIN_VALUE;
mostNegative = Integer.MAX_VALUE;
- resetHistogram();
- size = 0;
- nbrRemoved = 0;
+// resetHistogram();
+// size = 0;
+// nbrRemoved = 0;
}
@Override
public void clear() {
- // see if size is less than the 1/2 size that triggers expansion
- if (size < (sizeWhichTriggersExpansion >>> 1)) {
- // if 2nd time then shrink by 50%
- // this is done to avoid thrashing around the threshold
- if (secondTimeShrinkable) {
- secondTimeShrinkable = false;
- final int currentCapacity = getCapacity();
- final int newCapacity = Math.max(initialCapacity, currentCapacity >>>
1);
- if (newCapacity < currentCapacity) {
- newTable(newCapacity); // shrink table by 50%
- } else { // don't shrink below minimum
- resetArray();
- }
- return;
-
- } else {
- secondTimeShrinkable = true;
- }
- } else {
- secondTimeShrinkable = false; // reset this to require 2 triggers in a
row
- }
- resetArray();
+ super.clear();
+ resetTable();
+// // see if size is less than the 1/2 size that triggers expansion
+// if (size < (sizeWhichTriggersExpansion >>> 1)) {
+// // if 2nd time then shrink by 50%
+// // this is done to avoid thrashing around the threshold
+// if (secondTimeShrinkable) {
+// secondTimeShrinkable = false;
+// final int currentCapacity = getCapacity();
+// final int newCapacity = Math.max(initialCapacity, currentCapacity
>>> 1);
+// if (newCapacity < currentCapacity) {
+// newTable(newCapacity); // shrink table by 50%
+// } else { // don't shrink below minimum
+// resetArray();
+// }
+// return;
+//
+// } else {
+// secondTimeShrinkable = true;
+// }
+// } else {
+// secondTimeShrinkable = false; // reset this to require 2 triggers in a
row
+// }
+// resetArray();
}
- /**
- * returns a position in the key/value table
- * if the key is not found, then the position will be to the
- * place where the key would be put upon adding, and the
- * current internal value of keys[position] would be 0.
- *
- * if the key is found, then keys[position] == key
- * @param adjKey - raw key - offset (-1 if this value is 0 or negative, to
skip 0, if shorts)
- * @return the probeAddr in keys array - might have a 0 value, or the key
value if found
- */
- private int findPosition(final int adjKey) {
- return findPosition(adjKey, false);
- }
-
- private int findPosition(final int adjKey, final boolean includeRemoved) {
- if (adjKey == 0) {
- throw new IllegalArgumentException("0 is an invalid key");
- }
-
- final int hash = Misc.hashInt(adjKey);
- int nbrProbes = 1;
- int probeDelta = 1;
- int probeAddr;
- removedPositionToUse = -1;
-
- if (keys4 == null) {
- final short[] localKeys2 = keys2;
- final int bitMask = localKeys2.length - 1;
- probeAddr = hash & bitMask;
-
- while (true) {
- final int testKey = localKeys2[probeAddr];
- if (includeRemoved && (removedPositionToUse == -1) && (testKey ==
REMOVED2)) {
- nbrRemoved --; // because caller will use this as a slot for adding
- removedPositionToUse = probeAddr;
- }
- if (testKey == 0 || testKey == adjKey) {
- break;
- }
- nbrProbes++;
- probeAddr = bitMask & (probeAddr + (probeDelta++));
- }
- } else {
- final int[] localKeys4 = keys4;
- final int bitMask = localKeys4.length - 1;
- probeAddr = hash & bitMask;
- while (true) {
- final int testKey = localKeys4[probeAddr];
- if (includeRemoved && (removedPositionToUse == -1) && (testKey ==
REMOVED4)) {
- nbrRemoved --; // because caller will use this as a slot for adding
- removedPositionToUse = probeAddr;
- }
- if (testKey == 0 || testKey == adjKey) {
- break;
- }
- nbrProbes++;
- probeAddr = bitMask & (probeAddr + (probeDelta++));
- }
- }
-
- if (TUNE) {
- final int pv = histogram[nbrProbes];
-
- histogram[nbrProbes] = 1 + pv;
- if (maxProbe < nbrProbes) {
- maxProbe = nbrProbes;
- }
- }
-
- return probeAddr;
- }
+// /**
+// * returns a position in the key/value table
+// * if the key is not found, then the position will be to the
+// * place where the key would be put upon adding, and the
+// * current internal value of keys[position] would be 0.
+// *
+// * if the key is found, then keys[position] == key
+// * @param adjKey - raw key - offset (-1 if this value is 0 or negative, to
skip 0, if shorts)
+// * @return the probeAddr in keys array - might have a 0 value, or the key
value if found
+// */
+// private int findPosition(final int adjKey) {
+// return findPosition(adjKey, false);
+// }
+//
+// private int findPosition(final int adjKey, final boolean includeRemoved) {
+// if (adjKey == 0) {
+// throw new IllegalArgumentException("0 is an invalid key");
+// }
+//
+// final int hash = Misc.hashInt(adjKey);
+// int nbrProbes = 1;
+// int probeDelta = 1;
+// int probeAddr;
+// removedPositionToUse = -1;
+//
+// if (keys4 == null) {
+// final short[] localKeys2 = keys2;
+// final int bitMask = localKeys2.length - 1;
+// probeAddr = hash & bitMask;
+//
+// while (true) {
+// final int testKey = localKeys2[probeAddr];
+// if (includeRemoved && (removedPositionToUse == -1) && (testKey ==
REMOVED2)) {
+// nbrRemoved --; // because caller will use this as a slot for
adding
+// removedPositionToUse = probeAddr;
+// }
+// if (testKey == 0 || testKey == adjKey) {
+// break;
+// }
+// nbrProbes++;
+// probeAddr = bitMask & (probeAddr + (probeDelta++));
+// }
+// } else {
+// final int[] localKeys4 = keys4;
+// final int bitMask = localKeys4.length - 1;
+// probeAddr = hash & bitMask;
+// while (true) {
+// final int testKey = localKeys4[probeAddr];
+// if (includeRemoved && (removedPositionToUse == -1) && (testKey ==
REMOVED4)) {
+// nbrRemoved --; // because caller will use this as a slot for
adding
+// removedPositionToUse = probeAddr;
+// }
+// if (testKey == 0 || testKey == adjKey) {
+// break;
+// }
+// nbrProbes++;
+// probeAddr = bitMask & (probeAddr + (probeDelta++));
+// }
+// }
+//
+// if (TUNE) {
+// final int pv = histogram[nbrProbes];
+//
+// histogram[nbrProbes] = 1 + pv;
+// if (maxProbe < nbrProbes) {
+// maxProbe = nbrProbes;
+// }
+// }
+//
+// return probeAddr;
+// }
// only called when keys are shorts
private boolean isAdjKeyOutOfRange(int adjKey) {
@@ -398,41 +382,112 @@ public class IntHashSet implements Posit
@Override
public boolean contains(int rawKey) {
- return find(rawKey) != -1;
+ int pos = findPosition(rawKey);
+ if (pos == -1) {
+ return false;
+ }
+ if (keys4 == null) {
+ return keys2[pos] != 0;
+ } else {
+ return keys4[pos] != 0;
+ }
}
+ /**
+ * This method is part of the PositiveSet API, and
+ * is defined to return an int that could be used with
+ * iterators to position them.
+ *
+ * For this case, it is not used, because
+ * the iterators don't support positioning this way
+ * because they are not sorted.
+ */
@Override
public int find(int rawKey) {
- if (rawKey == 0) {
- return -1;
- }
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * @param rawKey the key value to find
+ * @return the position in the table if present, otherwise the position of
the slot where the
+ * key value would be added, unless the new value is at a position
which would require
+ * the key2 form to be switched to the key4 form, in which case,
+ * -1 is returned (means not found, and requires conversion to 4
byte keys)
+ */
+ private int findPosition(int rawKey) {
+
+ if (rawKey == 0) {
+ throw new IllegalArgumentException("0 is an invalid key");
+ }
+
if (keys4 == null) {
+ // special handling for 2 byte keys with offsets
// check for keys never stored in short table
// adjKey of Short.MIN_VALUE which is the removed flag
final int adjKey = getAdjKey(rawKey);
if (isAdjKeyOutOfRange(adjKey)) {
return -1;
}
- final int pos = findPosition(adjKey);
- return (keys2[pos] == adjKey) ? pos : -1;
+
+ if (rawKey == REMOVED2) {
+ throw new IllegalArgumentException(String.valueOf(REMOVED2) + " is an
invalid key");
+ }
+
+ return findPositionAdjKey(adjKey);
+
+ } else {
+
+ if (rawKey == REMOVED4) {
+ throw new IllegalArgumentException(String.valueOf(REMOVED4) + " is an
invalid key");
+ }
+
+ return findPosition4(rawKey);
}
- // using 4 byte keys, no offset
- if (rawKey == Integer.MIN_VALUE) {
- return -1; // not stored in table (reserved value for removed items)
- }
- final int pos = findPosition(rawKey);
- return (keys4[pos] == rawKey) ? pos : -1;
}
+ private int findPosition4(int rawKey) {
+
+ return super.findPosition(
+
+ // key hash
+ Misc.hashInt(rawKey),
+
+ // is_eq_or_is_not_present
+ i -> keys4[i] == 0 || keys4[i] == rawKey,
+
+ // is_removed_key
+ i -> keys4[i] == REMOVED4
+ );
+ }
+
+ private int findPositionAdjKey(int adjKey) {
+ // special handling for 2 byte keys with offsets
+ // check for keys never stored in short table
+ // adjKey of Short.MIN_VALUE which is the removed flag
+
+ return super.findPosition(
+
+ // key hash
+ Misc.hashInt(adjKey),
+
+ // is_eq_or_is_not_present
+ i -> keys2[i] == 0 || keys2[i] == adjKey,
+
+ // is_removed_key
+ i -> keys2[i] == REMOVED2
+ );
+ }
+
+
/**
* return the adjusted key.
* never called for 4 byte form
* for 2 byte key mode, subtract the offset, and adjust by -1 if 0 or less
* Note: returned value can be less than Short.MIN_VALUE
* @param rawKey
- * @return adjusted key
+ * @return adjusted key, a range from negative to positive, but never 0
*/
private int getAdjKey(int rawKey) {
// if (rawKey == 0 || (rawKey == Integer.MIN_VALUE)) {
@@ -448,7 +503,9 @@ public class IntHashSet implements Posit
private void switchTo4byte() {
// convert to 4 byte because values can't be offset and fit in a short
final short[] oldKeys = keys2;
- newTableKeepSize(getCapacity(), true); // make a 4 table. same size
+ isMake4 = true;
+ newTable(getCapacity()); // make a 4 table. same size
+ removed = 0;
for (short adjKey : oldKeys) {
if (adjKey != 0 && adjKey != REMOVED2) {
addInner4(getRawFromAdjKey(adjKey));
@@ -467,7 +524,7 @@ public class IntHashSet implements Posit
throw new IllegalArgumentException("argument must be non-zero");
}
- if (size == 0) {
+ if (size() == 0) {
mostPositive = mostNegative = rawKey;
} else {
if (rawKey > mostPositive) {
@@ -479,6 +536,9 @@ public class IntHashSet implements Posit
}
if (keys4 != null) {
+ if (rawKey == REMOVED4) {
+ throw new IllegalArgumentException(String.valueOf(REMOVED4) + " is an
invalid key");
+ }
return find4AndAddIfMissing(rawKey);
// short keys
@@ -490,26 +550,42 @@ public class IntHashSet implements Posit
// key in range
} else {
- final int i = findPosition(adjKey, true); // reuse removed slots
+ final int i = findPositionAdjKey(adjKey);
if (keys2[i] == adjKey) {
return false;
}
- keys2[ (removedPositionToUse != -1) ? removedPositionToUse : i ] =
(short) adjKey;
- incrementSize();
+ keys2[ (found_removed != -1) ? found_removed : i ] = (short) adjKey;
+ commonPutOrAddNotFound();
return true;
}
}
}
private boolean find4AndAddIfMissing(int rawKey) {
- removedPositionToUse = -1;
- final int i = findPosition(rawKey, true);
+ int i = findPosition4(rawKey);
if (keys4[i] == rawKey) {
- return false;
+ return false; // already in table
}
- keys4[ (removedPositionToUse == -1) ? i : removedPositionToUse] = rawKey;
- incrementSize();
+
+ if (found_removed == -1) {
+ keys4[i] = rawKey;
+ incrementSize();
+ } else {
+ keys4[found_removed] = rawKey;
+ commonPutOrAddNotFound();
+ }
+// keys4[ (found_removed == -1) ? i : found_removed] = rawKey;
+// commonPutOrAddNotFound();
+//
+//
+// removedPositionToUse = -1;
+// final int i = findPosition(rawKey, true);
+// if (keys4[i] == rawKey) {
+// return false;
+// }
+// keys4[ (found_removed == -1) ? i : found_removed] = rawKey;
+// incrementSize();
return true;
}
@@ -542,13 +618,13 @@ public class IntHashSet implements Posit
* @param rawKey
*/
private void addInner4(int rawKey) {
- final int i = findPosition(rawKey);
+ final int i = findPosition4(rawKey);
assert(keys4[i] == 0);
keys4[i] = rawKey;
}
private void addInner2(short adjKey) {
- final int i = findPosition(adjKey);
+ final int i = findPositionAdjKey(adjKey);
assert(keys2[i] == 0);
keys2[i] = adjKey;
}
@@ -568,33 +644,35 @@ public class IntHashSet implements Posit
*/
@Override
public boolean remove(int rawKey) {
- final int pos = find(rawKey);
- if (pos < 0) {
+// debugValidate();
+ final int pos = findPosition(rawKey);
+ if (pos == -1 || ((keys4 == null)
+ ? (keys2[pos] == 0)
+ : (keys4[pos] == 0)) ) {
return false;
}
+// //debug
+// if (size() <= 0)
+// System.out.println("debug");
+// assert size() > 0;
if (keys4 == null) {
keys2[pos] = REMOVED2;
} else {
keys4[pos] = REMOVED4;
}
-
- size--;
- nbrRemoved ++;
+
if (rawKey == mostPositive) {
mostPositive --; // a weak adjustment
}
if (rawKey == mostNegative) {
mostNegative ++; // a weak adjustment
}
+
+ commonRemove();
return true;
}
-
- @Override
- public int size() {
- return size;
- }
-
+
/**
*
* @return a value that is >= the actual most positive value in the table.
@@ -651,16 +729,16 @@ public class IntHashSet implements Posit
* For short keys, the value stored for adjKey == 0 is -1, adjKey == -1 is
-2, etc.
*/
@Override
- public int get(int index) {
+ public int get(int pos) {
final int adjKey;
if (keys4 == null) {
- adjKey = keys2[index];
+ adjKey = keys2[pos];
if (adjKey == 0 || adjKey == REMOVED2) {
return 0; // null, not present
}
return getRawFromAdjKey(adjKey);
} else {
- adjKey = keys4[index];
+ adjKey = keys4[pos];
if (adjKey == 0 || adjKey == REMOVED4) {
return 0; // null, not present
}
@@ -668,65 +746,66 @@ public class IntHashSet implements Posit
}
}
- /**
- * advance pos until it points to a non 0 or is 1 past end
- * @param pos
- * @return updated pos
- */
- private int moveToNextFilled(int pos) {
- if (pos < 0) {
- pos = 0;
- }
-
- final int max = getCapacity();
- if (null == keys4) {
- while (true) {
- if (pos >= max) {
- return pos;
- }
- int v = get(pos);
- if (v != 0 && v != REMOVED2) {
- return pos;
- }
- pos++;
- }
- } else {
- // keys4 case
- while (true) {
- if (pos >= max) {
- return pos;
- }
- int v = get(pos);
- if (v != 0 && v != REMOVED4) {
- return pos;
- }
- pos ++;
- }
- }
- }
+// /**
+// * advance pos until it points to a non 0 or is 1 past end
+// * @param pos
+// * @return updated pos
+// */
+// private int moveToNextFilled(int pos) {
+// if (pos < 0) {
+// pos = 0;
+// }
+//
+// final int max = getCapacity();
+// if (null == keys4) {
+// while (true) {
+// if (pos >= max) {
+// return pos;
+// }
+// int v = get(pos);
+// if (v != 0 && v != REMOVED2) {
+// return pos;
+// }
+// pos++;
+// }
+// } else {
+// // keys4 case
+// while (true) {
+// if (pos >= max) {
+// return pos;
+// }
+// int v = get(pos);
+// if (v != 0 && v != REMOVED4) {
+// return pos;
+// }
+// pos ++;
+// }
+// }
+// }
- /**
- * decrement pos until it points to a non 0 or is -1
- * @param pos
- * @return updated pos
- */
- private int moveToPreviousFilled(int pos) {
- final int max = getCapacity();
- if (pos > max) {
- pos = max - 1;
- }
-
- while (true) {
- if (pos < 0) {
- return pos;
- }
- int v = get(pos);
- if (v != 0 && v != ( (keys4 == null) ? REMOVED2 : REMOVED4)) {
- return pos;
- }
- pos --;
- }
- }
+// /**
+// * see if there's a value a pos
+// * if not, decrement pos until it points to a non 0 or is -1
+// * @param pos to start looking for a value
+// * @return a pos with a value, or -1. if there's a value at the original
pos, then that pos is returned.
+// */
+// private int moveToPreviousFilled(int pos) {
+// final int max = getCapacity();
+// if (pos > max) {
+// pos = max - 1;
+// }
+//
+// while (true) {
+// if (pos < 0) {
+// return pos;
+// }
+// int v = get(pos); // bug - adjust key!
+// if (v != 0 && v != ( (keys4 == null) ? REMOVED2 : REMOVED4)) {
+// return pos;
+// }
+// pos --;
+// }
+// }
private class IntHashSetIterator implements IntListIterator {
@@ -741,29 +820,34 @@ public class IntHashSet implements Posit
return curPosition < getCapacity();
}
- public final int next() {
- if (!hasNext()) {
- throw new NoSuchElementException();
- }
- return get(curPosition++);
+ public final int nextNvc() {
+ curPosition = moveToNextFilled(curPosition);
+ int r = get(curPosition);
+ curPosition = moveToNextFilled(curPosition + 1);
+ return r;
}
-
+
/**
* @see org.apache.uima.internal.util.IntListIterator#hasPrevious()
*/
public boolean hasPrevious() {
- curPosition = moveToPreviousFilled(curPosition);
- return (curPosition >= 0);
+ int prev = moveToPreviousFilled(curPosition - 1);
+ return (prev >= 0);
}
-
- /**
- * @see org.apache.uima.internal.util.IntListIterator#previous()
- */
+
+ @Override
public int previous() {
- if (!hasPrevious()) {
+ curPosition = moveToPreviousFilled(curPosition - 1);
+ if (curPosition < 0) {
throw new NoSuchElementException();
}
- return get(curPosition--);
+ return get(curPosition);
+ }
+
+ @Override
+ public int previousNvc() {
+ curPosition = moveToPreviousFilled(curPosition - 1);
+ return get(curPosition);
}
/**
@@ -859,7 +943,7 @@ public class IntHashSet implements Posit
return String
.format(
"IntHashSet [loadFactor=%s, initialCapacity=%s,
sizeWhichTriggersExpansion=%s, size=%s, offset=%s%n keys4=%s%n keys2=%s%n
secondTimeShrinkable=%s, mostPositive=%s, mostNegative=%s]",
- loadFactor, initialCapacity, sizeWhichTriggersExpansion, size,
offset,
+ loadFactor, initialCapacity, sizeWhichTriggersExpansion, size(),
offset,
Arrays.toString(keys4), Arrays.toString(keys2),
secondTimeShrinkable, mostPositive,
mostNegative);
}
@@ -872,6 +956,82 @@ public class IntHashSet implements Posit
int getOffset() {
return offset;
}
+
+ @Override
+ protected boolean is_valid_key(int pos) {
+ if (keys4 == null) {
+ return keys2[pos] != 0 && keys2[pos] != REMOVED2;
+ }
+ return keys4[pos] != 0 && keys4[pos] != REMOVED4;
+ }
+
+ @Override
+ protected int keys_length() {
+ return (keys4 == null) ? keys2.length : keys4.length;
+ }
+
+ @Override
+ protected void newKeysAndValues(int capacity) {
+ if (isMake4) {
+ keys4 = new int[capacity];
+ keys2 = null;
+ } else {
+ keys2 = new short[capacity];
+ keys4 = null;
+ }
+ }
+
+ @Override
+ protected void clearKeysAndValues() {
+ if (keys4 == null) {
+ Arrays.fill(keys2, (short)0);
+ } else {
+ Arrays.fill(keys4, 0);
+ }
+ resetTable();
+ }
+
+ @Override
+ protected void copy_to_new_table(
+ int new_capacity,
+ int old_capacity,
+ CommonCopyOld2New commonCopy) {
+ // logic covers
+ // 2 sizes of copying old 2 new
+ // logic to switch to 4 byte key size
+
+ if (keys2 != null) {
+ final short[] oldKeys = keys2;
+ IntPredicate oldKeyValid = i -> oldKeys[i] != 0 && oldKeys[i] !=
REMOVED2;
+
+ if (new_capacity >= 256 * 256) { // == 65536
+ // switch to 4
+ if (TUNE) {System.out.println("Switching to 4 byte keys");}
+ isMake4 = true;
+ commonCopy.apply(
+ // copyToNew
+ i -> addInner4(getRawFromAdjKey(oldKeys[i])),
+
+ oldKeyValid); // is_valid_old_key
+ } else {
+ commonCopy.apply(
+
+ // copyToNew
+ i -> addInner2(oldKeys[i]),
+
+ oldKeyValid); // is_valid_old_key
+ }
+ } else {
+ final int[] oldKeys = keys4;
+// if (TUNE) {System.out.println("Capacity increasing from " +
old_capacity + " to " + new_capacity);}
+ commonCopy.apply(
+ // copyToNew
+ i -> addInner4(oldKeys[i]),
+
+ i -> oldKeys[i] != 0 && oldKeys[i] != REMOVED4);
+ }
+
+ }
}
