http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/OpenHashTable.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/OpenHashTable.java b/core/src/main/java/hivemall/utils/collections/OpenHashTable.java deleted file mode 100644 index 1a3dff7..0000000 --- a/core/src/main/java/hivemall/utils/collections/OpenHashTable.java +++ /dev/null @@ -1,412 +0,0 @@ -/* - * 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 hivemall.utils.collections; - -import hivemall.utils.lang.Copyable; -import hivemall.utils.math.Primes; - -import java.io.Externalizable; -import java.io.IOException; -import java.io.ObjectInput; -import java.io.ObjectOutput; -import java.util.Arrays; -import java.util.HashMap; - -import javax.annotation.Nonnull; - -/** - * An open-addressing hash table with double-hashing that requires less memory to {@link HashMap}. - */ -public final class OpenHashTable<K, V> implements Externalizable { - - public static final float DEFAULT_LOAD_FACTOR = 0.7f; - public static final float DEFAULT_GROW_FACTOR = 2.0f; - - protected static final byte FREE = 0; - protected static final byte FULL = 1; - protected static final byte REMOVED = 2; - - protected/* final */float _loadFactor; - protected/* final */float _growFactor; - - protected int _used = 0; - protected int _threshold; - - protected K[] _keys; - protected V[] _values; - protected byte[] _states; - - public OpenHashTable() {} // for Externalizable - - public OpenHashTable(int size) { - this(size, DEFAULT_LOAD_FACTOR, DEFAULT_GROW_FACTOR); - } - - @SuppressWarnings("unchecked") - public OpenHashTable(int size, float loadFactor, float growFactor) { - if (size < 1) { - throw new IllegalArgumentException(); - } - this._loadFactor = loadFactor; - this._growFactor = growFactor; - int actualSize = Primes.findLeastPrimeNumber(size); - this._keys = (K[]) new Object[actualSize]; - this._values = (V[]) new Object[actualSize]; - this._states = new byte[actualSize]; - this._threshold = Math.round(actualSize * _loadFactor); - } - - public OpenHashTable(@Nonnull K[] keys, @Nonnull V[] values, @Nonnull byte[] states, int used) { - this._used = used; - this._threshold = keys.length; - this._keys = keys; - this._values = values; - this._states = states; - } - - public Object[] getKeys() { - return _keys; - } - - public Object[] getValues() { - return _values; - } - - public byte[] getStates() { - return _states; - } - - public boolean containsKey(final K key) { - return findKey(key) >= 0; - } - - public V get(final K key) { - final int i = findKey(key); - if (i < 0) { - return null; - } - return _values[i]; - } - - public V put(final K key, final V value) { - int hash = keyHash(key); - int keyLength = _keys.length; - int keyIdx = hash % keyLength; - - boolean expanded = preAddEntry(keyIdx); - if (expanded) { - keyLength = _keys.length; - keyIdx = hash % keyLength; - } - - K[] keys = _keys; - V[] values = _values; - byte[] states = _states; - - if (states[keyIdx] == FULL) { - if (equals(keys[keyIdx], key)) { - V old = values[keyIdx]; - values[keyIdx] = value; - return old; - } - // try second hash - int decr = 1 + (hash % (keyLength - 2)); - for (;;) { - keyIdx -= decr; - if (keyIdx < 0) { - keyIdx += keyLength; - } - if (isFree(keyIdx, key)) { - break; - } - if (states[keyIdx] == FULL && equals(keys[keyIdx], key)) { - V old = values[keyIdx]; - values[keyIdx] = value; - return old; - } - } - } - keys[keyIdx] = key; - values[keyIdx] = value; - states[keyIdx] = FULL; - ++_used; - return null; - } - - private static boolean equals(final Object k1, final Object k2) { - return k1 == k2 || k1.equals(k2); - } - - /** Return weather the required slot is free for new entry */ - protected boolean isFree(int index, K key) { - byte stat = _states[index]; - if (stat == FREE) { - return true; - } - if (stat == REMOVED && equals(_keys[index], key)) { - return true; - } - return false; - } - - /** @return expanded or not */ - protected boolean preAddEntry(int index) { - if ((_used + 1) >= _threshold) {// filled enough - int newCapacity = Math.round(_keys.length * _growFactor); - ensureCapacity(newCapacity); - return true; - } - return false; - } - - protected int findKey(final K key) { - K[] keys = _keys; - byte[] states = _states; - int keyLength = keys.length; - - int hash = keyHash(key); - int keyIdx = hash % keyLength; - if (states[keyIdx] != FREE) { - if (states[keyIdx] == FULL && equals(keys[keyIdx], key)) { - return keyIdx; - } - // try second hash - int decr = 1 + (hash % (keyLength - 2)); - for (;;) { - keyIdx -= decr; - if (keyIdx < 0) { - keyIdx += keyLength; - } - if (isFree(keyIdx, key)) { - return -1; - } - if (states[keyIdx] == FULL && equals(keys[keyIdx], key)) { - return keyIdx; - } - } - } - return -1; - } - - public V remove(final K key) { - K[] keys = _keys; - V[] values = _values; - byte[] states = _states; - int keyLength = keys.length; - - int hash = keyHash(key); - int keyIdx = hash % keyLength; - if (states[keyIdx] != FREE) { - if (states[keyIdx] == FULL && equals(keys[keyIdx], key)) { - V old = values[keyIdx]; - states[keyIdx] = REMOVED; - --_used; - return old; - } - // second hash - int decr = 1 + (hash % (keyLength - 2)); - for (;;) { - keyIdx -= decr; - if (keyIdx < 0) { - keyIdx += keyLength; - } - if (states[keyIdx] == FREE) { - return null; - } - if (states[keyIdx] == FULL && equals(keys[keyIdx], key)) { - V old = values[keyIdx]; - states[keyIdx] = REMOVED; - --_used; - return old; - } - } - } - return null; - } - - public int size() { - return _used; - } - - public void clear() { - Arrays.fill(_states, FREE); - this._used = 0; - } - - public IMapIterator<K, V> entries() { - return new MapIterator(); - } - - @Override - public String toString() { - int len = size() * 10 + 2; - final StringBuilder buf = new StringBuilder(len); - buf.append('{'); - final IMapIterator<K, V> i = entries(); - while (i.next() != -1) { - String key = i.getKey().toString(); - buf.append(key); - buf.append('='); - buf.append(i.getValue()); - if (i.hasNext()) { - buf.append(','); - } - } - buf.append('}'); - return buf.toString(); - } - - protected void ensureCapacity(int newCapacity) { - int prime = Primes.findLeastPrimeNumber(newCapacity); - rehash(prime); - this._threshold = Math.round(prime * _loadFactor); - } - - @SuppressWarnings("unchecked") - private void rehash(int newCapacity) { - int oldCapacity = _keys.length; - if (newCapacity <= oldCapacity) { - throw new IllegalArgumentException("new: " + newCapacity + ", old: " + oldCapacity); - } - final K[] newkeys = (K[]) new Object[newCapacity]; - final V[] newValues = (V[]) new Object[newCapacity]; - final byte[] newStates = new byte[newCapacity]; - int used = 0; - for (int i = 0; i < oldCapacity; i++) { - if (_states[i] == FULL) { - used++; - K k = _keys[i]; - V v = _values[i]; - int hash = keyHash(k); - int keyIdx = hash % newCapacity; - if (newStates[keyIdx] == FULL) {// second hashing - int decr = 1 + (hash % (newCapacity - 2)); - while (newStates[keyIdx] != FREE) { - keyIdx -= decr; - if (keyIdx < 0) { - keyIdx += newCapacity; - } - } - } - newStates[keyIdx] = FULL; - newkeys[keyIdx] = k; - newValues[keyIdx] = v; - } - } - this._keys = newkeys; - this._values = newValues; - this._states = newStates; - this._used = used; - } - - private static int keyHash(final Object key) { - int hash = key.hashCode(); - return hash & 0x7fffffff; - } - - private final class MapIterator implements IMapIterator<K, V> { - - int nextEntry; - int lastEntry = -1; - - MapIterator() { - this.nextEntry = nextEntry(0); - } - - /** find the index of next full entry */ - int nextEntry(int index) { - while (index < _keys.length && _states[index] != FULL) { - index++; - } - return index; - } - - public boolean hasNext() { - return nextEntry < _keys.length; - } - - public int next() { - if (!hasNext()) { - return -1; - } - int curEntry = nextEntry; - this.lastEntry = nextEntry; - this.nextEntry = nextEntry(nextEntry + 1); - return curEntry; - } - - public K getKey() { - if (lastEntry == -1) { - throw new IllegalStateException(); - } - return _keys[lastEntry]; - } - - public V getValue() { - if (lastEntry == -1) { - throw new IllegalStateException(); - } - return _values[lastEntry]; - } - - @Override - public <T extends Copyable<V>> void getValue(T probe) { - probe.copyFrom(getValue()); - } - } - - @Override - public void writeExternal(ObjectOutput out) throws IOException { - out.writeFloat(_loadFactor); - out.writeFloat(_growFactor); - out.writeInt(_used); - - final int size = _keys.length; - out.writeInt(size); - - for (int i = 0; i < size; i++) { - out.writeObject(_keys[i]); - out.writeObject(_values[i]); - out.writeByte(_states[i]); - } - } - - @SuppressWarnings("unchecked") - @Override - public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException { - this._loadFactor = in.readFloat(); - this._growFactor = in.readFloat(); - this._used = in.readInt(); - - final int size = in.readInt(); - final Object[] keys = new Object[size]; - final Object[] values = new Object[size]; - final byte[] states = new byte[size]; - for (int i = 0; i < size; i++) { - keys[i] = in.readObject(); - values[i] = in.readObject(); - states[i] = in.readByte(); - } - this._threshold = size; - this._keys = (K[]) keys; - this._values = (V[]) values; - this._states = states; - } - -}
http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/SparseDoubleArray.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/SparseDoubleArray.java b/core/src/main/java/hivemall/utils/collections/SparseDoubleArray.java deleted file mode 100644 index c4dbbb5..0000000 --- a/core/src/main/java/hivemall/utils/collections/SparseDoubleArray.java +++ /dev/null @@ -1,213 +0,0 @@ -/* - * 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 hivemall.utils.collections; - -import hivemall.utils.lang.ArrayUtils; -import hivemall.utils.lang.Preconditions; - -import java.util.Arrays; - -import javax.annotation.Nonnull; - -public final class SparseDoubleArray implements DoubleArray { - private static final long serialVersionUID = -2814248784231540118L; - - @Nonnull - private int[] mKeys; - @Nonnull - private double[] mValues; - private int mSize; - - public SparseDoubleArray() { - this(10); - } - - public SparseDoubleArray(int initialCapacity) { - mKeys = new int[initialCapacity]; - mValues = new double[initialCapacity]; - mSize = 0; - } - - private SparseDoubleArray(@Nonnull int[] mKeys, @Nonnull double[] mValues, int mSize) { - this.mKeys = mKeys; - this.mValues = mValues; - this.mSize = mSize; - } - - @Nonnull - public SparseDoubleArray deepCopy() { - int[] newKeys = new int[mSize]; - double[] newValues = new double[mSize]; - System.arraycopy(mKeys, 0, newKeys, 0, mSize); - System.arraycopy(mValues, 0, newValues, 0, mSize); - return new SparseDoubleArray(newKeys, newValues, mSize); - } - - @Override - public double get(int key) { - return get(key, 0); - } - - @Override - public double get(int key, double valueIfKeyNotFound) { - int i = Arrays.binarySearch(mKeys, 0, mSize, key); - if (i < 0) { - return valueIfKeyNotFound; - } else { - return mValues[i]; - } - } - - public void delete(int key) { - int i = Arrays.binarySearch(mKeys, 0, mSize, key); - if (i >= 0) { - removeAt(i); - } - } - - public void removeAt(int index) { - System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); - System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); - mSize--; - } - - @Override - public void put(int key, double value) { - int i = Arrays.binarySearch(mKeys, 0, mSize, key); - if (i >= 0) { - mValues[i] = value; - } else { - i = ~i; - mKeys = ArrayUtils.insert(mKeys, mSize, i, key); - mValues = ArrayUtils.insert(mValues, mSize, i, value); - mSize++; - } - } - - public void increment(int key, double value) { - int i = Arrays.binarySearch(mKeys, 0, mSize, key); - if (i >= 0) { - mValues[i] += value; - } else { - i = ~i; - mKeys = ArrayUtils.insert(mKeys, mSize, i, key); - mValues = ArrayUtils.insert(mValues, mSize, i, value); - mSize++; - } - } - - @Override - public int size() { - return mSize; - } - - @Override - public int keyAt(int index) { - return mKeys[index]; - } - - public double valueAt(int index) { - return mValues[index]; - } - - public void setValueAt(int index, double value) { - mValues[index] = value; - } - - public int indexOfKey(int key) { - return Arrays.binarySearch(mKeys, 0, mSize, key); - } - - public int indexOfValue(double value) { - for (int i = 0; i < mSize; i++) { - if (mValues[i] == value) { - return i; - } - } - return -1; - } - - public void clear() { - clear(true); - } - - public void clear(boolean zeroFill) { - mSize = 0; - if (zeroFill) { - Arrays.fill(mKeys, 0); - Arrays.fill(mValues, 0.d); - } - } - - public void append(int key, double value) { - if (mSize != 0 && key <= mKeys[mSize - 1]) { - put(key, value); - return; - } - mKeys = ArrayUtils.append(mKeys, mSize, key); - mValues = ArrayUtils.append(mValues, mSize, value); - mSize++; - } - - @Override - public double[] toArray() { - return toArray(true); - } - - @Override - public double[] toArray(boolean copy) { - if (mSize == 0) { - return new double[0]; - } - - int last = mKeys[mSize - 1]; - final double[] array = new double[last + 1]; - for (int i = 0; i < mSize; i++) { - int k = mKeys[i]; - double v = mValues[i]; - Preconditions.checkArgument(k >= 0, "Negative key is not allowed for toArray(): " + k); - array[k] = v; - } - return array; - } - - @Override - public String toString() { - if (size() <= 0) { - return "{}"; - } - - StringBuilder buffer = new StringBuilder(mSize * 28); - buffer.append('{'); - for (int i = 0; i < mSize; i++) { - if (i > 0) { - buffer.append(", "); - } - int key = keyAt(i); - buffer.append(key); - buffer.append('='); - double value = valueAt(i); - buffer.append(value); - } - buffer.append('}'); - return buffer.toString(); - } - - -} http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/SparseIntArray.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/SparseIntArray.java b/core/src/main/java/hivemall/utils/collections/SparseIntArray.java deleted file mode 100644 index 7a4ba69..0000000 --- a/core/src/main/java/hivemall/utils/collections/SparseIntArray.java +++ /dev/null @@ -1,210 +0,0 @@ -/* - * 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 hivemall.utils.collections; - -import hivemall.utils.lang.ArrayUtils; -import hivemall.utils.lang.Preconditions; - -import java.util.Arrays; - -import javax.annotation.Nonnull; - -public final class SparseIntArray implements IntArray { - private static final long serialVersionUID = -2814248784231540118L; - - private int[] mKeys; - private int[] mValues; - private int mSize; - - public SparseIntArray() { - this(10); - } - - public SparseIntArray(int initialCapacity) { - mKeys = new int[initialCapacity]; - mValues = new int[initialCapacity]; - mSize = 0; - } - - private SparseIntArray(int[] mKeys, int[] mValues, int mSize) { - this.mKeys = mKeys; - this.mValues = mValues; - this.mSize = mSize; - } - - public IntArray deepCopy() { - int[] newKeys = new int[mSize]; - int[] newValues = new int[mSize]; - System.arraycopy(mKeys, 0, newKeys, 0, mSize); - System.arraycopy(mValues, 0, newValues, 0, mSize); - return new SparseIntArray(newKeys, newValues, mSize); - } - - @Override - public int get(int key) { - return get(key, 0); - } - - @Override - public int get(int key, int valueIfKeyNotFound) { - int i = Arrays.binarySearch(mKeys, 0, mSize, key); - if (i < 0) { - return valueIfKeyNotFound; - } else { - return mValues[i]; - } - } - - public void delete(int key) { - int i = Arrays.binarySearch(mKeys, 0, mSize, key); - if (i >= 0) { - removeAt(i); - } - } - - public void removeAt(int index) { - System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); - System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); - mSize--; - } - - @Override - public void put(int key, int value) { - int i = Arrays.binarySearch(mKeys, 0, mSize, key); - if (i >= 0) { - mValues[i] = value; - } else { - i = ~i; - mKeys = ArrayUtils.insert(mKeys, mSize, i, key); - mValues = ArrayUtils.insert(mValues, mSize, i, value); - mSize++; - } - } - - public void increment(int key, int value) { - int i = Arrays.binarySearch(mKeys, 0, mSize, key); - if (i >= 0) { - mValues[i] += value; - } else { - i = ~i; - mKeys = ArrayUtils.insert(mKeys, mSize, i, key); - mValues = ArrayUtils.insert(mValues, mSize, i, value); - mSize++; - } - } - - @Override - public int size() { - return mSize; - } - - @Override - public int keyAt(int index) { - return mKeys[index]; - } - - public int valueAt(int index) { - return mValues[index]; - } - - public void setValueAt(int index, int value) { - mValues[index] = value; - } - - public int indexOfKey(int key) { - return Arrays.binarySearch(mKeys, 0, mSize, key); - } - - public int indexOfValue(int value) { - for (int i = 0; i < mSize; i++) { - if (mValues[i] == value) { - return i; - } - } - return -1; - } - - public void clear() { - clear(true); - } - - public void clear(boolean zeroFill) { - mSize = 0; - if (zeroFill) { - Arrays.fill(mKeys, 0); - Arrays.fill(mValues, 0); - } - } - - public void append(int key, int value) { - if (mSize != 0 && key <= mKeys[mSize - 1]) { - put(key, value); - return; - } - mKeys = ArrayUtils.append(mKeys, mSize, key); - mValues = ArrayUtils.append(mValues, mSize, value); - mSize++; - } - - @Nonnull - public int[] toArray() { - return toArray(true); - } - - @Override - public int[] toArray(boolean copy) { - if (mSize == 0) { - return new int[0]; - } - - int last = mKeys[mSize - 1]; - final int[] array = new int[last + 1]; - for (int i = 0; i < mSize; i++) { - int k = mKeys[i]; - int v = mValues[i]; - Preconditions.checkArgument(k >= 0, "Negative key is not allowed for toArray(): " + k); - array[k] = v; - } - return array; - } - - @Override - public String toString() { - if (size() <= 0) { - return "{}"; - } - - StringBuilder buffer = new StringBuilder(mSize * 28); - buffer.append('{'); - for (int i = 0; i < mSize; i++) { - if (i > 0) { - buffer.append(", "); - } - int key = keyAt(i); - buffer.append(key); - buffer.append('='); - int value = valueAt(i); - buffer.append(value); - } - buffer.append('}'); - return buffer.toString(); - } - - -} http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/arrays/DenseDoubleArray.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/arrays/DenseDoubleArray.java b/core/src/main/java/hivemall/utils/collections/arrays/DenseDoubleArray.java new file mode 100644 index 0000000..f79f039 --- /dev/null +++ b/core/src/main/java/hivemall/utils/collections/arrays/DenseDoubleArray.java @@ -0,0 +1,92 @@ +/* + * 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 hivemall.utils.collections.arrays; + +import java.util.Arrays; + +import javax.annotation.Nonnull; + +/** + * A fixed double array that has keys greater than or equals to 0. + */ +public final class DenseDoubleArray implements DoubleArray { + private static final long serialVersionUID = 4282904528662802088L; + + @Nonnull + private final double[] array; + private final int size; + + public DenseDoubleArray(@Nonnull int size) { + this.array = new double[size]; + this.size = size; + } + + public DenseDoubleArray(@Nonnull double[] array) { + this.array = array; + this.size = array.length; + } + + @Override + public double get(int index) { + return array[index]; + } + + @Override + public double get(int index, double valueIfKeyNotFound) { + if (index >= size) { + return valueIfKeyNotFound; + } + return array[index]; + } + + @Override + public void put(int index, double value) { + array[index] = value; + } + + @Override + public int size() { + return array.length; + } + + @Override + public int keyAt(int index) { + return index; + } + + @Override + public double[] toArray() { + return toArray(true); + } + + @Override + public double[] toArray(boolean copy) { + if (copy) { + return Arrays.copyOf(array, size); + } else { + return array; + } + } + + @Override + public void clear() { + Arrays.fill(array, 0.d); + } + +} http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/arrays/DenseIntArray.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/arrays/DenseIntArray.java b/core/src/main/java/hivemall/utils/collections/arrays/DenseIntArray.java new file mode 100644 index 0000000..0869ff2 --- /dev/null +++ b/core/src/main/java/hivemall/utils/collections/arrays/DenseIntArray.java @@ -0,0 +1,92 @@ +/* + * 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 hivemall.utils.collections.arrays; + +import java.util.Arrays; + +import javax.annotation.Nonnull; + +/** + * A fixed INT array that has keys greater than or equals to 0. + */ +public final class DenseIntArray implements IntArray { + private static final long serialVersionUID = -1450212841013810240L; + + @Nonnull + private final int[] array; + private final int size; + + public DenseIntArray(@Nonnull int size) { + this.array = new int[size]; + this.size = size; + } + + public DenseIntArray(@Nonnull int[] array) { + this.array = array; + this.size = array.length; + } + + @Override + public int get(int index) { + return array[index]; + } + + @Override + public int get(int index, int valueIfKeyNotFound) { + if (index >= size) { + return valueIfKeyNotFound; + } + return array[index]; + } + + @Override + public void put(int index, int value) { + array[index] = value; + } + + @Override + public void increment(int index, int value) { + array[index] += value; + } + + @Override + public int size() { + return array.length; + } + + @Override + public int keyAt(int index) { + return index; + } + + @Override + public int[] toArray() { + return toArray(true); + } + + @Override + public int[] toArray(boolean copy) { + if (copy) { + return Arrays.copyOf(array, size); + } else { + return array; + } + } + +} http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/arrays/DoubleArray.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/arrays/DoubleArray.java b/core/src/main/java/hivemall/utils/collections/arrays/DoubleArray.java new file mode 100644 index 0000000..c8f3e17 --- /dev/null +++ b/core/src/main/java/hivemall/utils/collections/arrays/DoubleArray.java @@ -0,0 +1,45 @@ +/* + * 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 hivemall.utils.collections.arrays; + +import java.io.Serializable; + +import javax.annotation.Nonnull; + +public interface DoubleArray extends Serializable { + + public double get(int key); + + public double get(int key, double valueIfKeyNotFound); + + public void put(int key, double value); + + public int size(); + + public int keyAt(int index); + + @Nonnull + public double[] toArray(); + + @Nonnull + public double[] toArray(boolean copy); + + public void clear(); + +} http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/arrays/DoubleArray3D.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/arrays/DoubleArray3D.java b/core/src/main/java/hivemall/utils/collections/arrays/DoubleArray3D.java new file mode 100644 index 0000000..35feff9 --- /dev/null +++ b/core/src/main/java/hivemall/utils/collections/arrays/DoubleArray3D.java @@ -0,0 +1,147 @@ +/* + * 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 hivemall.utils.collections.arrays; + +import hivemall.utils.lang.Primitives; + +import java.nio.ByteBuffer; +import java.nio.DoubleBuffer; + +import javax.annotation.Nonnull; + +public final class DoubleArray3D { + private static final int DEFAULT_SIZE = 100 * 100 * 10; // feature * field * factor + + private final boolean direct; + + @Nonnull + private DoubleBuffer buffer; + private int capacity; + + private int size; + // number of array in each dimension + private int n1, n2, n3; + // pointer to each dimension + private int p1, p2; + + private boolean sanityCheck; + + public DoubleArray3D() { + this(DEFAULT_SIZE, true); + } + + public DoubleArray3D(int initSize, boolean direct) { + this.direct = direct; + this.buffer = allocate(direct, initSize); + this.capacity = initSize; + this.size = -1; + this.sanityCheck = true; + } + + public DoubleArray3D(int dim1, int dim2, int dim3) { + this.direct = true; + this.capacity = -1; + configure(dim1, dim2, dim3); + this.sanityCheck = true; + } + + public void setSanityCheck(boolean enable) { + this.sanityCheck = enable; + } + + public void configure(final int dim1, final int dim2, final int dim3) { + int requiredSize = cardinarity(dim1, dim2, dim3); + if (requiredSize > capacity) { + this.buffer = allocate(direct, requiredSize); + this.capacity = requiredSize; + } + this.size = requiredSize; + this.n1 = dim1; + this.n2 = dim2; + this.n3 = dim3; + this.p1 = n2 * n3; + this.p2 = n3; + } + + public void clear() { + buffer.clear(); + this.size = -1; + } + + public int getSize() { + return size; + } + + int getCapacity() { + return capacity; + } + + public double get(final int i, final int j, final int k) { + int idx = idx(i, j, k); + return buffer.get(idx); + } + + public void set(final int i, final int j, final int k, final double val) { + int idx = idx(i, j, k); + buffer.put(idx, val); + } + + private int idx(final int i, final int j, final int k) { + if (sanityCheck == false) { + return i * p1 + j * p2 + k; + } + + if (size == -1) { + throw new IllegalStateException("Double3DArray#configure() is not called"); + } + if (i >= n1 || i < 0) { + throw new ArrayIndexOutOfBoundsException("Index '" + i + + "' out of bounds for 1st dimension of size " + n1); + } + if (j >= n2 || j < 0) { + throw new ArrayIndexOutOfBoundsException("Index '" + j + + "' out of bounds for 2nd dimension of size " + n2); + } + if (k >= n3 || k < 0) { + throw new ArrayIndexOutOfBoundsException("Index '" + k + + "' out of bounds for 3rd dimension of size " + n3); + } + final int idx = i * p1 + j * p2 + k; + if (idx >= size) { + throw new IndexOutOfBoundsException("Computed internal index '" + idx + + "' exceeds buffer size '" + size + "' where i=" + i + ", j=" + j + ", k=" + k); + } + return idx; + } + + private static int cardinarity(final int dim1, final int dim2, final int dim3) { + if (dim1 <= 0 || dim2 <= 0 || dim3 <= 0) { + throw new IllegalArgumentException("Detected negative dimension size. dim1=" + dim1 + + ", dim2=" + dim2 + ", dim3=" + dim3); + } + return dim1 * dim2 * dim3; + } + + @Nonnull + private static DoubleBuffer allocate(final boolean direct, final int size) { + int bytes = size * Primitives.DOUBLE_BYTES; + ByteBuffer buf = direct ? ByteBuffer.allocateDirect(bytes) : ByteBuffer.allocate(bytes); + return buf.asDoubleBuffer(); + } +} http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/arrays/FloatArray.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/arrays/FloatArray.java b/core/src/main/java/hivemall/utils/collections/arrays/FloatArray.java new file mode 100644 index 0000000..b72bdef --- /dev/null +++ b/core/src/main/java/hivemall/utils/collections/arrays/FloatArray.java @@ -0,0 +1,45 @@ +/* + * 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 hivemall.utils.collections.arrays; + +import java.io.Serializable; + +import javax.annotation.Nonnull; + +public interface FloatArray extends Serializable { + + public float get(int key); + + public float get(int key, float valueIfKeyNotFound); + + public void put(int key, float value); + + public int size(); + + public int keyAt(int index); + + @Nonnull + public float[] toArray(); + + @Nonnull + public float[] toArray(boolean copy); + + public void clear(); + +} http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/arrays/IntArray.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/arrays/IntArray.java b/core/src/main/java/hivemall/utils/collections/arrays/IntArray.java new file mode 100644 index 0000000..8edb0d4 --- /dev/null +++ b/core/src/main/java/hivemall/utils/collections/arrays/IntArray.java @@ -0,0 +1,45 @@ +/* + * 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 hivemall.utils.collections.arrays; + +import java.io.Serializable; + +import javax.annotation.Nonnull; + +public interface IntArray extends Serializable { + + public int get(int key); + + public int get(int key, int valueIfKeyNotFound); + + public void put(int key, int value); + + public void increment(int key, int value); + + public int size(); + + public int keyAt(int index); + + @Nonnull + public int[] toArray(); + + @Nonnull + public int[] toArray(boolean copy); + +} http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/arrays/SparseDoubleArray.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/arrays/SparseDoubleArray.java b/core/src/main/java/hivemall/utils/collections/arrays/SparseDoubleArray.java new file mode 100644 index 0000000..ac41951 --- /dev/null +++ b/core/src/main/java/hivemall/utils/collections/arrays/SparseDoubleArray.java @@ -0,0 +1,223 @@ +/* + * 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 hivemall.utils.collections.arrays; + +import hivemall.math.vector.VectorProcedure; +import hivemall.utils.lang.ArrayUtils; +import hivemall.utils.lang.Preconditions; + +import java.util.Arrays; + +import javax.annotation.Nonnull; + +public final class SparseDoubleArray implements DoubleArray { + private static final long serialVersionUID = -2814248784231540118L; + + @Nonnull + private int[] mKeys; + @Nonnull + private double[] mValues; + private int mSize; + + public SparseDoubleArray() { + this(10); + } + + public SparseDoubleArray(int initialCapacity) { + mKeys = new int[initialCapacity]; + mValues = new double[initialCapacity]; + mSize = 0; + } + + private SparseDoubleArray(@Nonnull int[] mKeys, @Nonnull double[] mValues, int mSize) { + this.mKeys = mKeys; + this.mValues = mValues; + this.mSize = mSize; + } + + @Nonnull + public SparseDoubleArray deepCopy() { + int[] newKeys = new int[mSize]; + double[] newValues = new double[mSize]; + System.arraycopy(mKeys, 0, newKeys, 0, mSize); + System.arraycopy(mValues, 0, newValues, 0, mSize); + return new SparseDoubleArray(newKeys, newValues, mSize); + } + + @Override + public double get(int key) { + return get(key, 0); + } + + @Override + public double get(int key, double valueIfKeyNotFound) { + int i = Arrays.binarySearch(mKeys, 0, mSize, key); + if (i < 0) { + return valueIfKeyNotFound; + } else { + return mValues[i]; + } + } + + public void delete(int key) { + int i = Arrays.binarySearch(mKeys, 0, mSize, key); + if (i >= 0) { + removeAt(i); + } + } + + public void removeAt(int index) { + System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); + System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); + mSize--; + } + + @Override + public void put(int key, double value) { + int i = Arrays.binarySearch(mKeys, 0, mSize, key); + if (i >= 0) { + mValues[i] = value; + } else { + i = ~i; + mKeys = ArrayUtils.insert(mKeys, mSize, i, key); + mValues = ArrayUtils.insert(mValues, mSize, i, value); + mSize++; + } + } + + public void increment(int key, double value) { + int i = Arrays.binarySearch(mKeys, 0, mSize, key); + if (i >= 0) { + mValues[i] += value; + } else { + i = ~i; + mKeys = ArrayUtils.insert(mKeys, mSize, i, key); + mValues = ArrayUtils.insert(mValues, mSize, i, value); + mSize++; + } + } + + @Override + public int size() { + return mSize; + } + + @Override + public int keyAt(int index) { + return mKeys[index]; + } + + public double valueAt(int index) { + return mValues[index]; + } + + public void setValueAt(int index, double value) { + mValues[index] = value; + } + + public int indexOfKey(int key) { + return Arrays.binarySearch(mKeys, 0, mSize, key); + } + + public int indexOfValue(double value) { + for (int i = 0; i < mSize; i++) { + if (mValues[i] == value) { + return i; + } + } + return -1; + } + + @Override + public void clear() { + clear(true); + } + + public void clear(boolean zeroFill) { + mSize = 0; + if (zeroFill) { + Arrays.fill(mKeys, 0); + Arrays.fill(mValues, 0.d); + } + } + + public void append(int key, double value) { + if (mSize != 0 && key <= mKeys[mSize - 1]) { + put(key, value); + return; + } + mKeys = ArrayUtils.append(mKeys, mSize, key); + mValues = ArrayUtils.append(mValues, mSize, value); + mSize++; + } + + @Override + public double[] toArray() { + return toArray(true); + } + + @Override + public double[] toArray(boolean copy) { + if (mSize == 0) { + return new double[0]; + } + + int last = mKeys[mSize - 1]; + final double[] array = new double[last + 1]; + for (int i = 0; i < mSize; i++) { + int k = mKeys[i]; + double v = mValues[i]; + Preconditions.checkArgument(k >= 0, "Negative key is not allowed for toArray(): " + k); + array[k] = v; + } + return array; + } + + public void each(@Nonnull final VectorProcedure procedure) { + for (int i = 0; i < mSize; i++) { + int k = mKeys[i]; + double v = mValues[i]; + procedure.apply(k, v); + } + } + + @Override + public String toString() { + if (size() <= 0) { + return "{}"; + } + + StringBuilder buffer = new StringBuilder(mSize * 28); + buffer.append('{'); + for (int i = 0; i < mSize; i++) { + if (i > 0) { + buffer.append(", "); + } + int key = keyAt(i); + buffer.append(key); + buffer.append('='); + double value = valueAt(i); + buffer.append(value); + } + buffer.append('}'); + return buffer.toString(); + } + + +} http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/arrays/SparseFloatArray.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/arrays/SparseFloatArray.java b/core/src/main/java/hivemall/utils/collections/arrays/SparseFloatArray.java new file mode 100644 index 0000000..928de77 --- /dev/null +++ b/core/src/main/java/hivemall/utils/collections/arrays/SparseFloatArray.java @@ -0,0 +1,210 @@ +/* + * 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 hivemall.utils.collections.arrays; + +import hivemall.utils.lang.ArrayUtils; +import hivemall.utils.lang.Preconditions; + +import java.util.Arrays; + +import javax.annotation.Nonnull; + +public final class SparseFloatArray implements FloatArray { + private static final long serialVersionUID = -2814248784231540118L; + + private int[] mKeys; + private float[] mValues; + private int mSize; + + public SparseFloatArray() { + this(10); + } + + public SparseFloatArray(int initialCapacity) { + mKeys = new int[initialCapacity]; + mValues = new float[initialCapacity]; + mSize = 0; + } + + private SparseFloatArray(@Nonnull int[] mKeys, @Nonnull float[] mValues, int mSize) { + this.mKeys = mKeys; + this.mValues = mValues; + this.mSize = mSize; + } + + public SparseFloatArray deepCopy() { + int[] newKeys = new int[mSize]; + float[] newValues = new float[mSize]; + System.arraycopy(mKeys, 0, newKeys, 0, mSize); + System.arraycopy(mValues, 0, newValues, 0, mSize); + return new SparseFloatArray(newKeys, newValues, mSize); + } + + @Override + public float get(int key) { + return get(key, 0.f); + } + + @Override + public float get(int key, float valueIfKeyNotFound) { + int i = Arrays.binarySearch(mKeys, 0, mSize, key); + if (i < 0) { + return valueIfKeyNotFound; + } else { + return mValues[i]; + } + } + + public void delete(int key) { + int i = Arrays.binarySearch(mKeys, 0, mSize, key); + if (i >= 0) { + removeAt(i); + } + } + + public void removeAt(int index) { + System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); + System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); + mSize--; + } + + @Override + public void put(int key, float value) { + int i = Arrays.binarySearch(mKeys, 0, mSize, key); + if (i >= 0) { + mValues[i] = value; + } else { + i = ~i; + mKeys = ArrayUtils.insert(mKeys, mSize, i, key); + mValues = ArrayUtils.insert(mValues, mSize, i, value); + mSize++; + } + } + + public void increment(int key, float value) { + int i = Arrays.binarySearch(mKeys, 0, mSize, key); + if (i >= 0) { + mValues[i] += value; + } else { + i = ~i; + mKeys = ArrayUtils.insert(mKeys, mSize, i, key); + mValues = ArrayUtils.insert(mValues, mSize, i, value); + mSize++; + } + } + + @Override + public int size() { + return mSize; + } + + @Override + public int keyAt(int index) { + return mKeys[index]; + } + + public float valueAt(int index) { + return mValues[index]; + } + + public void setValueAt(int index, float value) { + mValues[index] = value; + } + + public int indexOfKey(int key) { + return Arrays.binarySearch(mKeys, 0, mSize, key); + } + + public int indexOfValue(float value) { + for (int i = 0; i < mSize; i++) { + if (mValues[i] == value) { + return i; + } + } + return -1; + } + + public void clear() { + clear(true); + } + + public void clear(boolean zeroFill) { + mSize = 0; + if (zeroFill) { + Arrays.fill(mKeys, 0); + Arrays.fill(mValues, 0.f); + } + } + + public void append(int key, float value) { + if (mSize != 0 && key <= mKeys[mSize - 1]) { + put(key, value); + return; + } + mKeys = ArrayUtils.append(mKeys, mSize, key); + mValues = ArrayUtils.append(mValues, mSize, value); + mSize++; + } + + @Nonnull + public float[] toArray() { + return toArray(true); + } + + @Override + public float[] toArray(boolean copy) { + if (mSize == 0) { + return new float[0]; + } + + int last = mKeys[mSize - 1]; + final float[] array = new float[last + 1]; + for (int i = 0; i < mSize; i++) { + int k = mKeys[i]; + float v = mValues[i]; + Preconditions.checkArgument(k >= 0, "Negative key is not allowed for toArray(): " + k); + array[k] = v; + } + return array; + } + + @Override + public String toString() { + if (size() <= 0) { + return "{}"; + } + + StringBuilder buffer = new StringBuilder(mSize * 28); + buffer.append('{'); + for (int i = 0; i < mSize; i++) { + if (i > 0) { + buffer.append(", "); + } + int key = keyAt(i); + buffer.append(key); + buffer.append('='); + float value = valueAt(i); + buffer.append(value); + } + buffer.append('}'); + return buffer.toString(); + } + + +} http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/arrays/SparseIntArray.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/arrays/SparseIntArray.java b/core/src/main/java/hivemall/utils/collections/arrays/SparseIntArray.java new file mode 100644 index 0000000..8de5476 --- /dev/null +++ b/core/src/main/java/hivemall/utils/collections/arrays/SparseIntArray.java @@ -0,0 +1,211 @@ +/* + * 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 hivemall.utils.collections.arrays; + +import hivemall.utils.lang.ArrayUtils; +import hivemall.utils.lang.Preconditions; + +import java.util.Arrays; + +import javax.annotation.Nonnull; + +public final class SparseIntArray implements IntArray { + private static final long serialVersionUID = -2814248784231540118L; + + private int[] mKeys; + private int[] mValues; + private int mSize; + + public SparseIntArray() { + this(10); + } + + public SparseIntArray(int initialCapacity) { + mKeys = new int[initialCapacity]; + mValues = new int[initialCapacity]; + mSize = 0; + } + + private SparseIntArray(int[] mKeys, int[] mValues, int mSize) { + this.mKeys = mKeys; + this.mValues = mValues; + this.mSize = mSize; + } + + public IntArray deepCopy() { + int[] newKeys = new int[mSize]; + int[] newValues = new int[mSize]; + System.arraycopy(mKeys, 0, newKeys, 0, mSize); + System.arraycopy(mValues, 0, newValues, 0, mSize); + return new SparseIntArray(newKeys, newValues, mSize); + } + + @Override + public int get(int key) { + return get(key, 0); + } + + @Override + public int get(int key, int valueIfKeyNotFound) { + int i = Arrays.binarySearch(mKeys, 0, mSize, key); + if (i < 0) { + return valueIfKeyNotFound; + } else { + return mValues[i]; + } + } + + public void delete(int key) { + int i = Arrays.binarySearch(mKeys, 0, mSize, key); + if (i >= 0) { + removeAt(i); + } + } + + public void removeAt(int index) { + System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); + System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); + mSize--; + } + + @Override + public void put(int key, int value) { + int i = Arrays.binarySearch(mKeys, 0, mSize, key); + if (i >= 0) { + mValues[i] = value; + } else { + i = ~i; + mKeys = ArrayUtils.insert(mKeys, mSize, i, key); + mValues = ArrayUtils.insert(mValues, mSize, i, value); + mSize++; + } + } + + @Override + public void increment(int key, int value) { + int i = Arrays.binarySearch(mKeys, 0, mSize, key); + if (i >= 0) { + mValues[i] += value; + } else { + i = ~i; + mKeys = ArrayUtils.insert(mKeys, mSize, i, key); + mValues = ArrayUtils.insert(mValues, mSize, i, value); + mSize++; + } + } + + @Override + public int size() { + return mSize; + } + + @Override + public int keyAt(int index) { + return mKeys[index]; + } + + public int valueAt(int index) { + return mValues[index]; + } + + public void setValueAt(int index, int value) { + mValues[index] = value; + } + + public int indexOfKey(int key) { + return Arrays.binarySearch(mKeys, 0, mSize, key); + } + + public int indexOfValue(int value) { + for (int i = 0; i < mSize; i++) { + if (mValues[i] == value) { + return i; + } + } + return -1; + } + + public void clear() { + clear(true); + } + + public void clear(boolean zeroFill) { + mSize = 0; + if (zeroFill) { + Arrays.fill(mKeys, 0); + Arrays.fill(mValues, 0); + } + } + + public void append(int key, int value) { + if (mSize != 0 && key <= mKeys[mSize - 1]) { + put(key, value); + return; + } + mKeys = ArrayUtils.append(mKeys, mSize, key); + mValues = ArrayUtils.append(mValues, mSize, value); + mSize++; + } + + @Nonnull + public int[] toArray() { + return toArray(true); + } + + @Override + public int[] toArray(boolean copy) { + if (mSize == 0) { + return new int[0]; + } + + int last = mKeys[mSize - 1]; + final int[] array = new int[last + 1]; + for (int i = 0; i < mSize; i++) { + int k = mKeys[i]; + int v = mValues[i]; + Preconditions.checkArgument(k >= 0, "Negative key is not allowed for toArray(): " + k); + array[k] = v; + } + return array; + } + + @Override + public String toString() { + if (size() <= 0) { + return "{}"; + } + + StringBuilder buffer = new StringBuilder(mSize * 28); + buffer.append('{'); + for (int i = 0; i < mSize; i++) { + if (i > 0) { + buffer.append(", "); + } + int key = keyAt(i); + buffer.append(key); + buffer.append('='); + int value = valueAt(i); + buffer.append(value); + } + buffer.append('}'); + return buffer.toString(); + } + + +} http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/lists/DoubleArrayList.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/lists/DoubleArrayList.java b/core/src/main/java/hivemall/utils/collections/lists/DoubleArrayList.java new file mode 100644 index 0000000..feb614f --- /dev/null +++ b/core/src/main/java/hivemall/utils/collections/lists/DoubleArrayList.java @@ -0,0 +1,164 @@ +/* + * 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 hivemall.utils.collections.lists; + +import java.io.Serializable; + +import javax.annotation.Nonnull; + +public final class DoubleArrayList implements Serializable { + private static final long serialVersionUID = -8155789759545975413L; + public static final int DEFAULT_CAPACITY = 12; + + /** array entity */ + private double[] data; + private int used; + + public DoubleArrayList() { + this(DEFAULT_CAPACITY); + } + + public DoubleArrayList(int size) { + this.data = new double[size]; + this.used = 0; + } + + public DoubleArrayList(double[] initValues) { + this.data = initValues; + this.used = initValues.length; + } + + @Nonnull + public DoubleArrayList add(double value) { + if (used >= data.length) { + expand(used + 1); + } + data[used++] = value; + return this; + } + + @Nonnull + public DoubleArrayList add(@Nonnull double[] values) { + final int needs = used + values.length; + if (needs >= data.length) { + expand(needs); + } + System.arraycopy(values, 0, data, used, values.length); + this.used = needs; + return this; + } + + /** + * dynamic expansion. + */ + private void expand(int max) { + while (data.length < max) { + final int len = data.length; + double[] newArray = new double[len * 2]; + System.arraycopy(data, 0, newArray, 0, len); + this.data = newArray; + } + } + + public double remove() { + return data[--used]; + } + + public double remove(int index) { + if (index >= used) { + throw new IndexOutOfBoundsException(); + } + + final double ret; + if (index == used) { + ret = data[index]; + --used; + } else { // index < used + ret = data[index]; + System.arraycopy(data, index + 1, data, index, used - index - 1); + --used; + } + return ret; + } + + public void set(int index, double value) { + if (index > used) { + throw new IllegalArgumentException("Index MUST be less than \"size()\"."); + } else if (index == used) { + ++used; + } + data[index] = value; + } + + public double get(int index) { + if (index >= used) + throw new IndexOutOfBoundsException(); + return data[index]; + } + + public double fastGet(int index) { + return data[index]; + } + + public int size() { + return used; + } + + public boolean isEmpty() { + return used == 0; + } + + public void clear() { + used = 0; + } + + @Nonnull + public double[] toArray() { + return toArray(false); + } + + @Nonnull + public double[] toArray(boolean close) { + final double[] newArray = new double[used]; + System.arraycopy(data, 0, newArray, 0, used); + if (close) { + this.data = null; + } + return newArray; + } + + public double[] array() { + return data; + } + + @Override + public String toString() { + final StringBuilder buf = new StringBuilder(); + buf.append('['); + for (int i = 0; i < used; i++) { + if (i != 0) { + buf.append(", "); + } + buf.append(data[i]); + } + buf.append(']'); + return buf.toString(); + } + +} http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/lists/FloatArrayList.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/lists/FloatArrayList.java b/core/src/main/java/hivemall/utils/collections/lists/FloatArrayList.java new file mode 100644 index 0000000..54b214d --- /dev/null +++ b/core/src/main/java/hivemall/utils/collections/lists/FloatArrayList.java @@ -0,0 +1,162 @@ +/* + * 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 hivemall.utils.collections.lists; + +import java.io.Serializable; + +import javax.annotation.Nonnull; + +public final class FloatArrayList implements Serializable { + private static final long serialVersionUID = 8764828070342317585L; + + public static final int DEFAULT_CAPACITY = 12; + + /** array entity */ + private float[] data; + private int used; + + public FloatArrayList() { + this(DEFAULT_CAPACITY); + } + + public FloatArrayList(int size) { + this.data = new float[size]; + this.used = 0; + } + + public FloatArrayList(float[] initValues) { + this.data = initValues; + this.used = initValues.length; + } + + @Nonnull + public FloatArrayList add(float value) { + if (used >= data.length) { + expand(used + 1); + } + data[used++] = value; + return this; + } + + @Nonnull + public FloatArrayList add(@Nonnull float[] values) { + final int needs = used + values.length; + if (needs >= data.length) { + expand(needs); + } + System.arraycopy(values, 0, data, used, values.length); + this.used = needs; + return this; + } + + /** + * dynamic expansion. + */ + private void expand(int max) { + while (data.length < max) { + final int len = data.length; + float[] newArray = new float[len * 2]; + System.arraycopy(data, 0, newArray, 0, len); + this.data = newArray; + } + } + + public float remove() { + return data[--used]; + } + + public float remove(int index) { + if (index >= used) { + throw new IndexOutOfBoundsException(); + } + + final float ret; + if (index == used) { + ret = data[index]; + --used; + } else { // index < used + ret = data[index]; + System.arraycopy(data, index + 1, data, index, used - index - 1); + --used; + } + return ret; + } + + public void set(int index, float value) { + if (index > used) { + throw new IllegalArgumentException("Index MUST be less than \"size()\"."); + } else if (index == used) { + ++used; + } + data[index] = value; + } + + public float get(int index) { + if (index >= used) + throw new IndexOutOfBoundsException(); + return data[index]; + } + + public float fastGet(int index) { + return data[index]; + } + + public int size() { + return used; + } + + public boolean isEmpty() { + return used == 0; + } + + public void clear() { + this.used = 0; + } + + public float[] toArray() { + return toArray(false); + } + + public float[] toArray(boolean close) { + final float[] newArray = new float[used]; + System.arraycopy(data, 0, newArray, 0, used); + if (close) { + this.data = null; + } + return newArray; + } + + public float[] array() { + return data; + } + + @Override + public String toString() { + final StringBuilder buf = new StringBuilder(); + buf.append('['); + for (int i = 0; i < used; i++) { + if (i != 0) { + buf.append(", "); + } + buf.append(data[i]); + } + buf.append(']'); + return buf.toString(); + } +} http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/lists/IntArrayList.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/lists/IntArrayList.java b/core/src/main/java/hivemall/utils/collections/lists/IntArrayList.java new file mode 100644 index 0000000..ea17c5f --- /dev/null +++ b/core/src/main/java/hivemall/utils/collections/lists/IntArrayList.java @@ -0,0 +1,179 @@ +/* + * 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 hivemall.utils.collections.lists; + +import hivemall.utils.lang.ArrayUtils; + +import java.io.Serializable; + +import javax.annotation.Nonnull; + +public final class IntArrayList implements Serializable { + private static final long serialVersionUID = -2147675120406747488L; + public static final int DEFAULT_CAPACITY = 12; + + /** array entity */ + private int[] data; + private int used; + + public IntArrayList() { + this(DEFAULT_CAPACITY); + } + + public IntArrayList(int size) { + this.data = new int[size]; + this.used = 0; + } + + public IntArrayList(int[] initValues) { + this.data = initValues; + this.used = initValues.length; + } + + @Nonnull + public IntArrayList add(final int value) { + if (used >= data.length) { + expand(used + 1); + } + data[used++] = value; + return this; + } + + @Nonnull + public IntArrayList add(@Nonnull final int[] values) { + final int needs = used + values.length; + if (needs >= data.length) { + expand(needs); + } + System.arraycopy(values, 0, data, used, values.length); + this.used = needs; + return this; + } + + /** + * dynamic expansion. + */ + private void expand(final int max) { + while (data.length < max) { + final int len = data.length; + int[] newArray = new int[len * 2]; + System.arraycopy(data, 0, newArray, 0, len); + this.data = newArray; + } + } + + public int remove() { + return data[--used]; + } + + public int remove(final int index) { + if (index >= used) { + throw new IndexOutOfBoundsException(); + } + + final int ret; + if (index == used) { + ret = data[index]; + --used; + } else { // index < used + ret = data[index]; + System.arraycopy(data, index + 1, data, index, used - index - 1); + --used; + } + return ret; + } + + public void set(final int index, final int value) { + if (index > used) { + throw new IllegalArgumentException("Index " + index + " MUST be less than size() " + + used); + } else if (index == used) { + ++used; + } + data[index] = value; + } + + public int get(final int index) { + if (index >= used) { + throw new IndexOutOfBoundsException("Index " + index + " out of bounds " + used); + } + return data[index]; + } + + public int fastGet(final int index) { + return data[index]; + } + + /** + * @return -1 if not found. + */ + public int indexOf(final int key) { + return ArrayUtils.indexOf(data, key, 0, used); + } + + public boolean contains(final int key) { + return ArrayUtils.indexOf(data, key, 0, used) != -1; + } + + public int size() { + return used; + } + + public boolean isEmpty() { + return used == 0; + } + + public void clear() { + used = 0; + } + + @Nonnull + public int[] toArray() { + return toArray(false); + } + + @Nonnull + public int[] toArray(boolean close) { + final int[] newArray = new int[used]; + System.arraycopy(data, 0, newArray, 0, used); + if (close) { + this.data = null; + } + return newArray; + } + + public int[] array() { + return data; + } + + @Override + public String toString() { + final StringBuilder buf = new StringBuilder(); + buf.append('['); + for (int i = 0; i < used; i++) { + if (i != 0) { + buf.append(", "); + } + buf.append(data[i]); + } + buf.append(']'); + return buf.toString(); + } + +} http://git-wip-us.apache.org/repos/asf/incubator-hivemall/blob/8dc3a024/core/src/main/java/hivemall/utils/collections/lists/LongArrayList.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/hivemall/utils/collections/lists/LongArrayList.java b/core/src/main/java/hivemall/utils/collections/lists/LongArrayList.java new file mode 100644 index 0000000..0786872 --- /dev/null +++ b/core/src/main/java/hivemall/utils/collections/lists/LongArrayList.java @@ -0,0 +1,166 @@ +/* + * 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 hivemall.utils.collections.lists; + +import java.io.Serializable; + +import javax.annotation.Nonnull; + +public final class LongArrayList implements Serializable { + private static final long serialVersionUID = 6928415231676568533L; + + public static final int DEFAULT_CAPACITY = 12; + + /** array entity */ + private long[] data; + private int used; + + public LongArrayList() { + this(DEFAULT_CAPACITY); + } + + public LongArrayList(int size) { + this.data = new long[size]; + this.used = 0; + } + + public LongArrayList(@Nonnull long[] initValues) { + this.data = initValues; + this.used = initValues.length; + } + + @Nonnull + public LongArrayList add(final long value) { + if (used >= data.length) { + expand(used + 1); + } + data[used++] = value; + return this; + } + + @Nonnull + public LongArrayList add(@Nonnull final long[] values) { + final int needs = used + values.length; + if (needs >= data.length) { + expand(needs); + } + System.arraycopy(values, 0, data, used, values.length); + this.used = needs; + return this; + } + + /** + * dynamic expansion. + */ + private void expand(final int max) { + while (data.length < max) { + final int len = data.length; + long[] newArray = new long[len * 2]; + System.arraycopy(data, 0, newArray, 0, len); + this.data = newArray; + } + } + + public long remove() { + return data[--used]; + } + + public long remove(final int index) { + if (index >= used) { + throw new IndexOutOfBoundsException(); + } + + final long ret; + if (index == used) { + ret = data[index]; + --used; + } else { // index < used + ret = data[index]; + System.arraycopy(data, index + 1, data, index, used - index - 1); + --used; + } + return ret; + } + + public void set(final int index, final long value) { + if (index > used) { + throw new IllegalArgumentException("Index MUST be less than \"size()\"."); + } else if (index == used) { + ++used; + } + data[index] = value; + } + + public long get(final int index) { + if (index >= used) { + throw new IndexOutOfBoundsException(); + } + return data[index]; + } + + public long fastGet(final int index) { + return data[index]; + } + + public int size() { + return used; + } + + public boolean isEmpty() { + return used == 0; + } + + public void clear() { + this.used = 0; + } + + @Nonnull + public long[] toArray() { + return toArray(false); + } + + @Nonnull + public long[] toArray(boolean close) { + final long[] newArray = new long[used]; + System.arraycopy(data, 0, newArray, 0, used); + if (close) { + this.data = null; + } + return newArray; + } + + @Nonnull + public long[] array() { + return data; + } + + @Override + public String toString() { + final StringBuilder buf = new StringBuilder(); + buf.append('['); + for (int i = 0; i < used; i++) { + if (i != 0) { + buf.append(", "); + } + buf.append(data[i]); + } + buf.append(']'); + return buf.toString(); + } +}
