The internal storage array starts with capacity determined by the {@code initialCapacity} * property, which can be set by the constructor. The default initial capacity is 16. Adding * elements using {@link #addElement(double)} appends elements to the end of the array. When there * are no open entries at the end of the internal storage array, the array is expanded. The size of * the expanded array depends on the {@code expansionMode} and {@code expansionFactor} properties. * The {@code expansionMode} determines whether the size of the array is multiplied by the {@code * expansionFactor} ({@link ExpansionMode#MULTIPLICATIVE}) or if the expansion is additive ({@link * ExpansionMode#ADDITIVE} -- {@code expansionFactor} storage locations added). The default {@code * expansionMode} is {@code MULTIPLICATIVE} and the default {@code expansionFactor} is 2. * *
The {@link #addElementRolling(double)} method adds a new element to the end of the internal * storage array and adjusts the "usable window" of the internal array forward by one position * (effectively making what was the second element the first, and so on). Repeated activations of * this method (or activation of {@link #discardFrontElements(int)}) will effectively orphan the * storage locations at the beginning of the internal storage array. To reclaim this storage, each * time one of these methods is activated, the size of the internal storage array is compared to the * number of addressable elements (the {@code numElements} property) and if the difference is too * large, the internal array is contracted to size {@code numElements + 1}. The determination of * when the internal storage array is "too large" depends on the {@code expansionMode} and {@code * contractionFactor} properties. If the {@code expansionMode} is {@code MULTIPLICATIVE}, * contraction is triggered when the ratio between storage array length and {@code numElements} * exceeds {@code contractionFactor.} If the {@code expansionMode} is {@code ADDITIVE}, the number * of excess storage locations is compared to {@code contractionFactor}. * *
To avoid cycles of expansions and contractions, the {@code expansionFactor} must not exceed * the {@code contractionFactor}. Constructors and mutators for both of these properties enforce * this requirement, throwing a {@code MathIllegalArgumentException} if it is violated. */ public class ResizableDoubleArray implements DoubleArray, Serializable { /** * Additive expansion mode. * * @deprecated As of 3.1. Please use {@link ExpansionMode#ADDITIVE} instead. */ @Deprecated public static final int ADDITIVE_MODE = 1; /** * Multiplicative expansion mode. * * @deprecated As of 3.1. Please use {@link ExpansionMode#MULTIPLICATIVE} instead. */ @Deprecated public static final int MULTIPLICATIVE_MODE = 0; /** Serializable version identifier. */ private static final long serialVersionUID = -3485529955529426875L; /** Default value for initial capacity. */ private static final int DEFAULT_INITIAL_CAPACITY = 16; /** Default value for array size modifier. */ private static final double DEFAULT_EXPANSION_FACTOR = 2.0; /** * Default value for the difference between {@link #contractionCriterion} and {@link * #expansionFactor}. */ private static final double DEFAULT_CONTRACTION_DELTA = 0.5; /** * The contraction criteria determines when the internal array will be contracted to fit the * number of elements contained in the element array + 1. */ private double contractionCriterion = 2.5; /** * The expansion factor of the array. When the array needs to be expanded, the new array size * will be {@code internalArray.length * expansionFactor} if {@code expansionMode} is set to * MULTIPLICATIVE_MODE, or {@code internalArray.length + expansionFactor} if {@code * expansionMode} is set to ADDITIVE_MODE. */ private double expansionFactor = 2.0; /** * Determines whether array expansion by {@code expansionFactor} is additive or multiplicative. */ private ExpansionMode expansionMode = ExpansionMode.MULTIPLICATIVE; /** The internal storage array. */ private double[] internalArray; /** * The number of addressable elements in the array. Note that this has nothing to do with the * length of the internal storage array. */ private int numElements = 0; /** * The position of the first addressable element in the internal storage array. The addressable * elements in the array are {@code internalArray[startIndex],...,internalArray[startIndex + * numElements - 1]}. */ private int startIndex = 0; /** * Specification of expansion algorithm. * * @since 3.1 */ public enum ExpansionMode { /** Multiplicative expansion mode. */ MULTIPLICATIVE, /** Additive expansion mode. */ ADDITIVE } /** * Creates an instance with default properties. * *
Throws IllegalArgumentException if the following conditions are not met: * *
initialCapacity > 0
* expansionFactor > 1
* contractionFactor >= expansionFactor
* expansionMode in {MULTIPLICATIVE_MODE, ADDITIVE_MODE}
* Example: If the array contains the elements 1, 2, 3, 4 (in that order) and
* addElementRolling(5) is invoked, the result is an array containing the entries 2, 3, 4, 5 and
* the value returned is 1.
*
* @param value Value to be added to the array.
* @return the value which has been discarded or "pushed" out of the array by this rolling
* insert.
*/
public synchronized double addElementRolling(double value) {
double discarded = internalArray[startIndex];
if ((startIndex + (numElements + 1)) > internalArray.length) {
expand();
}
// Increment the start index
startIndex += 1;
// Add the new value
internalArray[startIndex + (numElements - 1)] = value;
// Check the contraction criterion.
if (shouldContract()) {
contract();
}
return discarded;
}
/**
* Substitutes value for the most recently added value. Returns the value that has
* been replaced. If the array is empty (i.e. if {@link #numElements} is zero), an
* IllegalStateException is thrown.
*
* @param value New value to substitute for the most recently added value
* @return the value that has been replaced in the array.
* @throws MathIllegalStateException if the array is empty
* @since 2.0
*/
public synchronized double substituteMostRecentElement(double value)
throws MathIllegalStateException {
if (numElements < 1) {
throw new MathIllegalStateException(
LocalizedFormats.CANNOT_SUBSTITUTE_ELEMENT_FROM_EMPTY_ARRAY);
}
final int substIndex = startIndex + (numElements - 1);
final double discarded = internalArray[substIndex];
internalArray[substIndex] = value;
return discarded;
}
/**
* Checks the expansion factor and the contraction criterion and throws an
* IllegalArgumentException if the contractionCriteria is less than the expansionCriteria
*
* @param expansion factor to be checked
* @param contraction criteria to be checked
* @throws MathIllegalArgumentException if the contractionCriteria is less than the
* expansionCriteria.
* @deprecated As of 3.1. Please use {@link #checkContractExpand(double,double)} instead.
*/
@Deprecated
protected void checkContractExpand(float contraction, float expansion)
throws MathIllegalArgumentException {
checkContractExpand((double) contraction, (double) expansion);
}
/**
* Checks the expansion factor and the contraction criterion and raises an exception if the
* contraction criterion is smaller than the expansion criterion.
*
* @param contraction Criterion to be checked.
* @param expansion Factor to be checked.
* @throws NumberIsTooSmallException if {@code contraction < expansion}.
* @throws NumberIsTooSmallException if {@code contraction <= 1}.
* @throws NumberIsTooSmallException if {@code expansion <= 1 }.
* @since 3.1
*/
protected void checkContractExpand(double contraction, double expansion)
throws NumberIsTooSmallException {
if (contraction < expansion) {
final NumberIsTooSmallException e = new NumberIsTooSmallException(contraction, 1, true);
e.getContext()
.addMessage(
LocalizedFormats.CONTRACTION_CRITERIA_SMALLER_THAN_EXPANSION_FACTOR,
contraction,
expansion);
throw e;
}
if (contraction <= 1) {
final NumberIsTooSmallException e =
new NumberIsTooSmallException(contraction, 1, false);
e.getContext()
.addMessage(
LocalizedFormats.CONTRACTION_CRITERIA_SMALLER_THAN_ONE, contraction);
throw e;
}
if (expansion <= 1) {
final NumberIsTooSmallException e =
new NumberIsTooSmallException(contraction, 1, false);
e.getContext()
.addMessage(LocalizedFormats.EXPANSION_FACTOR_SMALLER_THAN_ONE, expansion);
throw e;
}
}
/** Clear the array contents, resetting the number of elements to zero. */
public synchronized void clear() {
numElements = 0;
startIndex = 0;
}
/**
* Contracts the storage array to the (size of the element set) + 1 - to avoid a zero length
* array. This function also resets the startIndex to zero.
*/
public synchronized void contract() {
final double[] tempArray = new double[numElements + 1];
// Copy and swap - copy only the element array from the src array.
System.arraycopy(internalArray, startIndex, tempArray, 0, numElements);
internalArray = tempArray;
// Reset the start index to zero
startIndex = 0;
}
/**
* Discards the i initial elements of the array. For example, if the array contains
* the elements 1,2,3,4, invoking discardFrontElements(2) will cause the first two
* elements to be discarded, leaving 3,4 in the array. Throws illegalArgumentException if i
* exceeds numElements.
*
* @param i the number of elements to discard from the front of the array
* @throws MathIllegalArgumentException if i is greater than numElements.
* @since 2.0
*/
public synchronized void discardFrontElements(int i) throws MathIllegalArgumentException {
discardExtremeElements(i, true);
}
/**
* Discards the i last elements of the array. For example, if the array contains
* the elements 1,2,3,4, invoking discardMostRecentElements(2) will cause the last
* two elements to be discarded, leaving 1,2 in the array. Throws illegalArgumentException if i
* exceeds numElements.
*
* @param i the number of elements to discard from the end of the array
* @throws MathIllegalArgumentException if i is greater than numElements.
* @since 2.0
*/
public synchronized void discardMostRecentElements(int i) throws MathIllegalArgumentException {
discardExtremeElements(i, false);
}
/**
* Discards the i first or last elements of the array, depending on the value of
* front. For example, if the array contains the elements 1,2,3,4, invoking
* discardExtremeElements(2,false) will cause the last two elements to be discarded,
* leaving 1,2 in the array. For example, if the array contains the elements 1,2,3,4, invoking
* discardExtremeElements(2,true) will cause the first two elements to be
* discarded, leaving 3,4 in the array. Throws illegalArgumentException if i exceeds
* numElements.
*
* @param i the number of elements to discard from the front/end of the array
* @param front true if elements are to be discarded from the front of the array, false if
* elements are to be discarded from the end of the array
* @throws MathIllegalArgumentException if i is greater than numElements.
* @since 2.0
*/
private synchronized void discardExtremeElements(int i, boolean front)
throws MathIllegalArgumentException {
if (i > numElements) {
throw new MathIllegalArgumentException(
LocalizedFormats.TOO_MANY_ELEMENTS_TO_DISCARD_FROM_ARRAY, i, numElements);
} else if (i < 0) {
throw new MathIllegalArgumentException(
LocalizedFormats.CANNOT_DISCARD_NEGATIVE_NUMBER_OF_ELEMENTS, i);
} else {
// "Subtract" this number of discarded from numElements
numElements -= i;
if (front) {
startIndex += i;
}
}
if (shouldContract()) {
contract();
}
}
/**
* Expands the internal storage array using the expansion factor.
*
*
if expansionMode is set to MULTIPLICATIVE_MODE, the new array size will be
* internalArray.length * expansionFactor. If expansionMode is set to
* ADDITIVE_MODE, the length after expansion will be
* internalArray.length + expansionFactor
*/
protected synchronized void expand() {
// notice the use of FastMath.ceil(), this guarantees that we will always
// have an array of at least currentSize + 1. Assume that the
// current initial capacity is 1 and the expansion factor
// is 1.000000000000000001. The newly calculated size will be
// rounded up to 2 after the multiplication is performed.
int newSize = 0;
if (expansionMode == ExpansionMode.MULTIPLICATIVE) {
newSize = (int) FastMath.ceil(internalArray.length * expansionFactor);
} else {
newSize = (int) (internalArray.length + FastMath.round(expansionFactor));
}
final double[] tempArray = new double[newSize];
// Copy and swap
System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
internalArray = tempArray;
}
/**
* Expands the internal storage array to the specified size.
*
* @param size Size of the new internal storage array.
*/
private synchronized void expandTo(int size) {
final double[] tempArray = new double[size];
// Copy and swap
System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
internalArray = tempArray;
}
/**
* The contraction criteria defines when the internal array will contract to store only the
* number of elements in the element array. If the expansionMode is
* MULTIPLICATIVE_MODE, contraction is triggered when the ratio between storage array
* length and numElements exceeds contractionFactor. If the
* expansionMode is ADDITIVE_MODE, the number of excess storage locations is
* compared to contractionFactor.
*
* @return the contraction criteria used to reclaim memory.
* @deprecated As of 3.1. Please use {@link #getContractionCriterion()} instead.
*/
@Deprecated
public float getContractionCriteria() {
return (float) getContractionCriterion();
}
/**
* The contraction criterion defines when the internal array will contract to store only the
* number of elements in the element array. If the expansionMode is
* MULTIPLICATIVE_MODE, contraction is triggered when the ratio between storage array
* length and numElements exceeds contractionFactor. If the
* expansionMode is ADDITIVE_MODE, the number of excess storage locations is
* compared to contractionFactor.
*
* @return the contraction criterion used to reclaim memory.
* @since 3.1
*/
public double getContractionCriterion() {
return contractionCriterion;
}
/**
* Returns the element at the specified index
*
* @param index index to fetch a value from
* @return value stored at the specified index
* @throws ArrayIndexOutOfBoundsException if index is less than zero or is greater
* than getNumElements() - 1.
*/
public synchronized double getElement(int index) {
if (index >= numElements) {
throw new ArrayIndexOutOfBoundsException(index);
} else if (index >= 0) {
return internalArray[startIndex + index];
} else {
throw new ArrayIndexOutOfBoundsException(index);
}
}
/**
* Returns a double array containing the elements of this ResizableArray. This
* method returns a copy, not a reference to the underlying array, so that changes made to the
* returned array have no effect on this ResizableArray.
*
* @return the double array.
*/
public synchronized double[] getElements() {
final double[] elementArray = new double[numElements];
System.arraycopy(internalArray, startIndex, elementArray, 0, numElements);
return elementArray;
}
/**
* The expansion factor controls the size of a new array when an array needs to be expanded. The
* expansionMode determines whether the size of the array is multiplied by the
* expansionFactor (MULTIPLICATIVE_MODE) or if the expansion is additive
* (ADDITIVE_MODE -- expansionFactor storage locations added). The default
* expansionMode is MULTIPLICATIVE_MODE and the default expansionFactor is
* 2.0.
*
* @return the expansion factor of this expandable double array
* @deprecated As of 3.1. Return type will be changed to "double" in 4.0.
*/
@Deprecated
public float getExpansionFactor() {
return (float) expansionFactor;
}
/**
* The expansion mode determines whether the internal storage array grows additively or
* multiplicatively when it is expanded.
*
* @return the expansion mode.
* @deprecated As of 3.1. Return value to be changed to {@link ExpansionMode} in 4.0.
*/
@Deprecated
public int getExpansionMode() {
synchronized (this) {
switch (expansionMode) {
case MULTIPLICATIVE:
return MULTIPLICATIVE_MODE;
case ADDITIVE:
return ADDITIVE_MODE;
default:
throw new MathInternalError(); // Should never happen.
}
}
}
/**
* Notice the package scope on this method. This method is simply here for the JUnit test, it
* allows us check if the expansion is working properly after a number of expansions. This is
* not meant to be a part of the public interface of this class.
*
* @return the length of the internal storage array.
* @deprecated As of 3.1. Please use {@link #getCapacity()} instead.
*/
@Deprecated
synchronized int getInternalLength() {
return internalArray.length;
}
/**
* Gets the currently allocated size of the internal data structure used for storing elements.
* This is not to be confused with {@link #getNumElements() the number of elements actually
* stored}.
*
* @return the length of the internal array.
* @since 3.1
*/
public int getCapacity() {
return internalArray.length;
}
/**
* Returns the number of elements currently in the array. Please note that this is different
* from the length of the internal storage array.
*
* @return the number of elements.
*/
public synchronized int getNumElements() {
return numElements;
}
/**
* Returns the internal storage array. Note that this method returns a reference to the internal
* storage array, not a copy, and to correctly address elements of the array, the
* startIndex is required (available via the {@link #start} method). This method should
* only be used in cases where copying the internal array is not practical. The {@link
* #getElements} method should be used in all other cases.
*
* @return the internal storage array used by this object
* @since 2.0
* @deprecated As of 3.1.
*/
@Deprecated
public synchronized double[] getInternalValues() {
return internalArray;
}
/**
* Provides direct access to the internal storage array. Please note that this method
* returns a reference to this object's storage array, not a copy.
* To correctly address elements of the array, the "start index" is required (available via the
* {@link #getStartIndex() getStartIndex} method.
* This method should only be used to avoid copying the internal array. The returned value
* must be used for reading only; other uses could lead to this object becoming
* inconsistent.
* The {@link #getElements} method has no such limitation since it returns a copy of this
* array's addressable elements.
*
* @return the internal storage array used by this object.
* @since 3.1
*/
protected double[] getArrayRef() {
return internalArray;
}
/**
* Returns the "start index" of the internal array. This index is the position of the first
* addressable element in the internal storage array. The addressable elements in the array are
* at indices contained in the interval [{@link #getStartIndex()}, {@link #getStartIndex()} +
* {@link #getNumElements()} - 1].
*
* @return the start index.
* @since 3.1
*/
protected int getStartIndex() {
return startIndex;
}
/**
* Sets the contraction criteria.
*
* @param contractionCriteria contraction criteria
* @throws MathIllegalArgumentException if the contractionCriteria is less than the
* expansionCriteria.
* @deprecated As of 3.1 (to be removed in 4.0 as field will become "final").
*/
@Deprecated
public void setContractionCriteria(float contractionCriteria)
throws MathIllegalArgumentException {
checkContractExpand(contractionCriteria, getExpansionFactor());
synchronized (this) {
this.contractionCriterion = contractionCriteria;
}
}
/**
* Performs an operation on the addressable elements of the array.
*
* @param f Function to be applied on this array.
* @return the result.
* @since 3.1
*/
public double compute(MathArrays.Function f) {
final double[] array;
final int start;
final int num;
synchronized (this) {
array = internalArray;
start = startIndex;
num = numElements;
}
return f.evaluate(array, start, num);
}
/**
* Sets the element at the specified index. If the specified index is greater than
* getNumElements() - 1, the numElements property is increased to
* index +1 and additional storage is allocated (if necessary) for the new element and
* all (uninitialized) elements between the new element and the previous end of the array).
*
* @param index index to store a value in
* @param value value to store at the specified index
* @throws ArrayIndexOutOfBoundsException if {@code index < 0}.
*/
public synchronized void setElement(int index, double value) {
if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
if (index + 1 > numElements) {
numElements = index + 1;
}
if ((startIndex + index) >= internalArray.length) {
expandTo(startIndex + (index + 1));
}
internalArray[startIndex + index] = value;
}
/**
* Sets the expansionFactor. Throws IllegalArgumentException if the the following conditions are
* not met:
*
*
expansionFactor > 1
* contractionFactor >= expansionFactor
* expansionMode. The specified value must be one of ADDITIVE_MODE,
* MULTIPLICATIVE_MODE.
*
* @param expansionMode The expansionMode to set.
* @throws MathIllegalArgumentException if the specified mode value is not valid.
* @deprecated As of 3.1. Please use {@link #setExpansionMode(ExpansionMode)} instead.
*/
@Deprecated
public void setExpansionMode(int expansionMode) throws MathIllegalArgumentException {
if (expansionMode != MULTIPLICATIVE_MODE && expansionMode != ADDITIVE_MODE) {
throw new MathIllegalArgumentException(
LocalizedFormats.UNSUPPORTED_EXPANSION_MODE,
expansionMode,
MULTIPLICATIVE_MODE,
"MULTIPLICATIVE_MODE",
ADDITIVE_MODE,
"ADDITIVE_MODE");
}
synchronized (this) {
if (expansionMode == MULTIPLICATIVE_MODE) {
setExpansionMode(ExpansionMode.MULTIPLICATIVE);
} else if (expansionMode == ADDITIVE_MODE) {
setExpansionMode(ExpansionMode.ADDITIVE);
}
}
}
/**
* Sets the {@link ExpansionMode expansion mode}.
*
* @param expansionMode Expansion mode to use for resizing the array.
* @deprecated As of 3.1 (to be removed in 4.0 as field will become "final").
*/
@Deprecated
public void setExpansionMode(ExpansionMode expansionMode) {
synchronized (this) {
this.expansionMode = expansionMode;
}
}
/**
* Sets the initial capacity. Should only be invoked by constructors.
*
* @param initialCapacity of the array
* @throws MathIllegalArgumentException if initialCapacity is not positive.
* @deprecated As of 3.1, this is a no-op.
*/
@Deprecated
protected void setInitialCapacity(int initialCapacity) throws MathIllegalArgumentException {
// Body removed in 3.1.
}
/**
* This function allows you to control the number of elements contained in this array, and can
* be used to "throw out" the last n values in an array. This function will also expand the
* internal array as needed.
*
* @param i a new number of elements
* @throws MathIllegalArgumentException if i is negative.
*/
public synchronized void setNumElements(int i) throws MathIllegalArgumentException {
// If index is negative thrown an error.
if (i < 0) {
throw new MathIllegalArgumentException(LocalizedFormats.INDEX_NOT_POSITIVE, i);
}
// Test the new num elements, check to see if the array needs to be
// expanded to accommodate this new number of elements.
final int newSize = startIndex + i;
if (newSize > internalArray.length) {
expandTo(newSize);
}
// Set the new number of elements to new value.
numElements = i;
}
/**
* Returns true if the internal storage array has too many unused storage positions.
*
* @return true if array satisfies the contraction criteria
*/
private synchronized boolean shouldContract() {
if (expansionMode == ExpansionMode.MULTIPLICATIVE) {
return (internalArray.length / ((float) numElements)) > contractionCriterion;
} else {
return (internalArray.length - numElements) > contractionCriterion;
}
}
/**
* Returns the starting index of the internal array. The starting index is the position of the
* first addressable element in the internal storage array. The addressable elements in the
* array are
* internalArray[startIndex],...,internalArray[startIndex + numElements -1]
*
*
* @return the starting index.
* @deprecated As of 3.1.
*/
@Deprecated
public synchronized int start() {
return startIndex;
}
/**
* Copies source to dest, copying the underlying data, so dest is a new, independent copy of
* source. Does not contract before the copy.
*
* Obtains synchronization locks on both source and dest (in that order) before performing * the copy. * *
Neither source nor dest may be null; otherwise a {@link NullArgumentException} is thrown * * @param source ResizableDoubleArray to copy * @param dest ResizableArray to replace with a copy of the source array * @exception NullArgumentException if either source or dest is null * @since 2.0 */ public static void copy(ResizableDoubleArray source, ResizableDoubleArray dest) throws NullArgumentException { MathUtils.checkNotNull(source); MathUtils.checkNotNull(dest); synchronized (source) { synchronized (dest) { dest.contractionCriterion = source.contractionCriterion; dest.expansionFactor = source.expansionFactor; dest.expansionMode = source.expansionMode; dest.internalArray = new double[source.internalArray.length]; System.arraycopy( source.internalArray, 0, dest.internalArray, 0, dest.internalArray.length); dest.numElements = source.numElements; dest.startIndex = source.startIndex; } } } /** * Returns a copy of the ResizableDoubleArray. Does not contract before the copy, so the * returned object is an exact copy of this. * * @return a new ResizableDoubleArray with the same data and configuration properties as this * @since 2.0 */ public synchronized ResizableDoubleArray copy() { final ResizableDoubleArray result = new ResizableDoubleArray(); copy(this, result); return result; } /** * Returns true iff object is a ResizableDoubleArray with the same properties as this and an * identical internal storage array. * * @param object object to be compared for equality with this * @return true iff object is a ResizableDoubleArray with the same data and properties as this * @since 2.0 */ @Override public boolean equals(Object object) { if (object == this) { return true; } if (object instanceof ResizableDoubleArray == false) { return false; } synchronized (this) { synchronized (object) { boolean result = true; final ResizableDoubleArray other = (ResizableDoubleArray) object; result = result && (other.contractionCriterion == contractionCriterion); result = result && (other.expansionFactor == expansionFactor); result = result && (other.expansionMode == expansionMode); result = result && (other.numElements == numElements); result = result && (other.startIndex == startIndex); if (!result) { return false; } else { return Arrays.equals(internalArray, other.internalArray); } } } } /** * Returns a hash code consistent with equals. * * @return the hash code representing this {@code ResizableDoubleArray}. * @since 2.0 */ @Override public synchronized int hashCode() { final int[] hashData = new int[6]; hashData[0] = Double.valueOf(expansionFactor).hashCode(); hashData[1] = Double.valueOf(contractionCriterion).hashCode(); hashData[2] = expansionMode.hashCode(); hashData[3] = Arrays.hashCode(internalArray); hashData[4] = numElements; hashData[5] = startIndex; return Arrays.hashCode(hashData); } }