* A variable length {@link DoubleArray} implementation that automatically * handles expanding and contracting its internal storage array as elements * are added and removed. *
*
* The internal storage array starts with capacity determined by the
* 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
* expansionMode and expansionFactor properties.
* 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.
*
* 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 numElements property) and if the difference
* is too large, the internal array is contracted to size
* numElements + 1. The determination of when the internal
* storage array is "too large" depends on the expansionMode and
* contractionFactor properties. 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.
*
* To avoid cycles of expansions and contractions, the
* expansionFactor must not exceed the
* contractionFactor. Constructors and mutators for both of these
* properties enforce this requirement, throwing IllegalArgumentException if it
* is violated.
*
internalArray.length * expansionFactor
* if expansionMode is set to MULTIPLICATIVE_MODE, or
* internalArray.length + expansionFactor if
* expansionMode is set to ADDITIVE_MODE.
*/
protected float expansionFactor = 2.0f;
/**
* Determines whether array expansion by expansionFactor
* is additive or multiplicative.
*/
protected int expansionMode = MULTIPLICATIVE_MODE;
/**
* The initial capacity of the array. Initial capacity is not exposed as a
* property as it is only meaningful when passed to a constructor.
*/
protected int initialCapacity = 16;
/**
* The internal storage array.
*/
protected 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.
*/
protected int numElements = 0;
/**
* 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]
*
*/
protected int startIndex = 0;
/**
* Create a ResizableArray with default properties.
* initialCapacity = 16expansionMode = MULTIPLICATIVE_MODEexpansionFactor = 2.5contractionFactor = 2.0expansionMode = MULTIPLICATIVE_MODEexpansionFactor = 2.5contractionFactor = 2.0* Create a ResizableArray with the specified initial capacity * and expansion factor. The remaining properties take default * values: *
expansionMode = MULTIPLICATIVE_MODEcontractionFactor = 0.5 + expansionFactor* Throws IllegalArgumentException if the following conditions are * not met: *
initialCapacity > 0expansionFactor > 1
* Create a ResizableArray with the specified initialCapacity,
* expansionFactor, and contractionCriteria. The expansionMode
* will default to MULTIPLICATIVE_MODE.
* Throws IllegalArgumentException if the following conditions are * not met: *
initialCapacity > 0expansionFactor > 1contractionFactor >= expansionFactor* Create a ResizableArray with the specified properties.
** Throws IllegalArgumentException if the following conditions are * not met: *
initialCapacity > 0expansionFactor > 1contractionFactor >= expansionFactorexpansionMode in {MULTIPLICATIVE_MODE, ADDITIVE_MODE}
* * Adds an element to the end of the array and removes the first * element in the array. Returns the discarded first element. * The effect is similar to a push operation in a FIFO queue. *
** 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 the 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 criteria if (shouldContract()) { contract(); } return discarded; } /** * Checks the expansion factor and the contraction criteria and throws an * IllegalArgumentException if the contractionCriteria is less than the * expansionCriteria * * @param expansionFactor factor to be checked * @param contractionCritera critera to be checked * @throws IllegalArgumentException if the contractionCriteria is less than * the expansionCriteria. */ protected void checkContractExpand( float contractionCritera, float expansionFactor) { if (contractionCritera < expansionFactor) { String msg = "Contraction criteria can never be smaller than " + "the expansion factor. This would lead to a never " + "ending loop of expansion and contraction as a newly " + "expanded internal storage array would immediately " + "satisfy the criteria for contraction"; throw new IllegalArgumentException(msg); } if (contractionCriteria <= 1.0) { String msg = "The contraction criteria must be a number larger " + "than one. If the contractionCriteria is less than or " + "equal to one an endless loop of contraction and " + "expansion would ensue as an internalArray.length " + "== numElements would satisfy the contraction criteria"; throw new IllegalArgumentException(msg); } if (expansionFactor <= 1.0) { String msg = "The expansion factor must be a number greater than 1.0"; throw new IllegalArgumentException(msg); } } /** * Clear the array, reset the size to the initialCapacity and the number * of elements to zero. */ public synchronized void clear() { numElements = 0; internalArray = new double[initialCapacity]; } /** * 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() { 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 thei 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 IllegalArgumentException if i is greater than numElements.
*/
public synchronized void discardFrontElements(int i) {
if (i > numElements) {
String msg = "Cannot discard more elements than are" +
"contained in this array.";
throw new IllegalArgumentException(msg);
} else if (i < 0) {
String msg = "Cannot discard a negative number of elements.";
throw new IllegalArgumentException(msg);
} else {
// "Subtract" this number of discarded from numElements
numElements -= i;
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 Math.ceil(), this gaurantees 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 == MULTIPLICATIVE_MODE) {
newSize = (int) Math.ceil(internalArray.length * expansionFactor);
} else {
newSize = internalArray.length + Math.round(expansionFactor);
}
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) {
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.
*/
public float getContractionCriteria() {
return contractionCriteria;
}
/**
* 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) {
String msg =
"The index specified: " + index +
" is larger than the current number of elements";
throw new ArrayIndexOutOfBoundsException(msg);
} else if (index >= 0) {
return internalArray[startIndex + index];
} else {
String msg =
"Elements cannot be retrieved from a negative array index";
throw new ArrayIndexOutOfBoundsException(msg);
}
}
/**
* 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() {
double[] elementArray = new double[numElements];
System.arraycopy( internalArray, startIndex, elementArray, 0,
numElements);
return elementArray;
}
/**
* The expansion factor controls the size of a new aray 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
*/
public float getExpansionFactor() {
return expansionFactor;
}
/**
* The expansionMode determines whether the internal storage
* array grows additively (ADDITIVE_MODE) or multiplicatively
* (MULTIPLICATIVE_MODE) when it is expanded.
*
* @return Returns the expansionMode.
*/
public int getExpansionMode() {
return expansionMode;
}
/**
* 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.
*/
synchronized int getInternalLength() {
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 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
*/
public synchronized double[] getValues() {
return (internalArray);
}
/**
* Sets the contraction criteria for this ExpandContractDoubleArray.
*
* @param contractionCriteria contraction criteria
*/
public void setContractionCriteria(float contractionCriteria) {
checkContractExpand(contractionCriteria, getExpansionFactor());
this.contractionCriteria = contractionCriteria;
}
/**
* 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 index is less than
* zero.
*/
public synchronized void setElement(int index, double value) {
if (index < 0) {
String msg = "Cannot set an element at a negative index";
throw new ArrayIndexOutOfBoundsException(msg);
}
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 > 1contractionFactor >= expansionFactor
* @param expansionFactor the new expansion factor value.
* @throws IllegalArgumentException if expansionFactor is <= 1 or greater
* than contractionFactor
*/
public void setExpansionFactor(float expansionFactor) {
checkContractExpand(getContractionCriteria(), expansionFactor);
// The check above verifies that the expansion factor is > 1.0;
this.expansionFactor = expansionFactor;
}
/**
* Sets the expansionMode. The specified value must be one of
* ADDITIVE_MODE, MULTIPLICATIVE_MODE.
*
* @param expansionMode The expansionMode to set.
* @throws IllegalArgumentException if the specified mode value is not valid
*/
public void setExpansionMode(int expansionMode) {
if (expansionMode != MULTIPLICATIVE_MODE &&
expansionMode != ADDITIVE_MODE) {
throw new IllegalArgumentException("Illegal expansionMode setting.");
}
this.expansionMode = expansionMode;
}
/**
* Sets the initial capacity. Should only be invoked by constructors.
*
* @param initialCapacity of the array
* @throws IllegalArgumentException if initialCapacity is not
* positive.
*/
protected void setInitialCapacity(int initialCapacity) {
if (initialCapacity > 0) {
synchronized(this) {
this.initialCapacity = initialCapacity;
}
} else {
String msg =
"The initial capacity supplied: " + initialCapacity +
"must be a positive integer";
throw new IllegalArgumentException(msg);
}
}
/**
* 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 IllegalArgumentException if i is negative.
*/
public synchronized void setNumElements(int i) {
// If index is negative thrown an error
if (i < 0) {
String msg =
"Number of elements must be zero or a positive " + "integer";
throw new IllegalArgumentException(msg);
}
// Test the new num elements, check to see if the array needs to be
// expanded to accomodate this new number of elements
if ((startIndex + i) > internalArray.length) {
expandTo(startIndex + i);
}
// 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 == MULTIPLICATIVE_MODE) {
return (internalArray.length / ((float) numElements)) > contractionCriteria;
} else {
return (internalArray.length - numElements) > contractionCriteria;
}
}
/**
* 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 starting index
*/
public synchronized int start() {
return startIndex;
}
}