You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by to...@apache.org on 2003/05/15 07:19:57 UTC
cvs commit: jakarta-commons-sandbox/math/src/test/org/apache/commons/math ExpandableDoubleArrayTest.java
tobrien 2003/05/14 22:19:57
Added: math/src/java/org/apache/commons/math
ExpandableDoubleArray.java
math/src/test/org/apache/commons/math
ExpandableDoubleArrayTest.java
Log:
Added an expandable double array, this class simply contains a double[] and takes care of automatic expansion of an internal array when necessary. Class added with accompanying unit test
Revision Changes Path
1.1 jakarta-commons-sandbox/math/src/java/org/apache/commons/math/ExpandableDoubleArray.java
Index: ExpandableDoubleArray.java
===================================================================
/* ====================================================================
* The Apache Software License, Version 1.1
*
* Copyright (c) 2003 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution, if
* any, must include the following acknowlegement:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowlegement may appear in the software itself,
* if and wherever such third-party acknowlegements normally appear.
*
* 4. The names "The Jakarta Project", "Commons", and "Apache Software
* Foundation" must not be used to endorse or promote products derived
* from this software without prior written permission. For written
* permission, please contact apache@apache.org.
*
* 5. Products derived from this software may not be called "Apache"
* nor may "Apache" appear in their names without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
package org.apache.commons.math;
import java.util.NoSuchElementException;
/**
* An array of double primitives which can expand as needed.
*
* @author <a href="mailto:tobrien@apache.org">Tim O'Brien</a>
*/
public class ExpandableDoubleArray {
// This is the internal storage array.
private double[] internalArray;
// Number of elements in the array
private int numElements = 0;
// The initial capacity of the array.
// Initial capacity is not exposed as a property as it is only meaningful
// when passed to a constructor.
private int initialCapacity = 16;
// The expand factor of the array. When the array need to be expanded, the new array size
// will be internalArray.length * expandFactor
private float expansionFactor = 2.0f;
/**
* Create an expandable double array with the
* default initial capactiy of 16 and an expansion factor of 2.00
*/
public ExpandableDoubleArray() {
internalArray = new double[initialCapacity];
}
/**
* Create an expandable double array with the
* specified initial capacity and the defult expansion factor of 2.00
*
* @param initialCapacity The initial size of the internal storage array
*/
public ExpandableDoubleArray(int initialCapacity) {
setInitialCapacity(initialCapacity);
internalArray = new double[this.initialCapacity];
}
/**
* Create an expandable double array with the
* specificed initial capacity and expand factor.
*
* @param initialCapacity The initial size of the internal storage array
* @param expansionFactor the array will be expanded based on this parameter
*/
public ExpandableDoubleArray(int initialCapacity, float expansionFactor) {
setInitialCapacity( initialCapacity );
setExpansionFactor(expansionFactor);
this.initialCapacity = initialCapacity;
internalArray = new double[initialCapacity];
}
/**
* The expansion factor controls the size of a new aray when an array needs to be expanded.
* When a value is inserted into a full array, the new array size is calculated as the
* current array size times this expansion factor. The default expansion factor is 2.0
*
* @return the expansion factor of this expandable double array
*/
public float getExpansionFactor() {
return expansionFactor;
}
/**
* Sets the expansion factor for this expandable double array. The expansion factor will
* affect the next expansion of this array.
*
* @param expansionFactor the expansion factor of this array
*/
public void setExpansionFactor(float expansionFactor) {
// The expansion factor *must* be larger than 1.0, otherwise we'll have an inconsistency
// upon expansion we'll start shrinking which will lead to ArrayOutOfBound exceptions.
if (expansionFactor > 1.0) {
this.expansionFactor = expansionFactor;
} else {
throw new IllegalArgumentException(
"The expansion factor must be a number greater than" + "1.0");
}
}
/**
* Sets the initial capacity
*
* @param initialCapacity
*/
public void setInitialCapacity(int initialCapacity) {
if (initialCapacity > 0) {
this.initialCapacity = initialCapacity;
} else {
throw new IllegalArgumentException(
"The initial capacity supplied: "
+ initialCapacity
+ "must be a positive integer");
}
}
/**
* Returns the internal storage array
*
* @return the internal storage array used by this object
*/
public double[] getValues() {
return (internalArray);
}
/**
* 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 int getNumElements() {
return (numElements);
}
/**
* Returns the element at the specified index
*
* @param index index to fetch a value from
* @return value stored at the specified index
*/
public double getElement(int index) throws NoSuchElementException {
double value = Double.NaN;
if (index >= numElements) {
throw new NoSuchElementException(
"The index specified: "
+ index
+ " is larger than the "
+ "current number of elements");
} else if (index >= 0) {
value = internalArray[index];
} else {
throw new IllegalArgumentException(
"Elements cannot be retrieved from negative array " + "index");
}
return value;
}
/**
* Sets the element at the specified index. This method will expand the internal storage array to
* accomodate the insertion of a value at an index beyond the current capacity.
* @param index index to store a value in
* @param value value to store at the specified index
*/
public synchronized void setElement(int index, double value) {
if( index < 0 ) {
throw new IllegalArgumentException( "Cannot set an element at a negative index");
}
if (index >= internalArray.length) {
expandTo(index + 1);
numElements = index + 1;
}
internalArray[index] = value;
}
/**
* 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;
}
/**
* Expands the internal storage array using the expansion factor
*/
private 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 = (int) Math.ceil(internalArray.length * expansionFactor);
double[] tempArray =
new double[newSize];
// Copy and swap
System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
internalArray = tempArray;
}
/**
* Adds an element to the end of this expandable array
*
* @return value to be added to end of array
*/
public synchronized void addElement(double value) {
numElements++;
if (numElements > internalArray.length) {
expand();
}
internalArray[numElements - 1] = value;
}
/**
* 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.
*/
int getInternalLength() {
return (internalArray.length);
}
/**
* 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];
}
}
1.1 jakarta-commons-sandbox/math/src/test/org/apache/commons/math/ExpandableDoubleArrayTest.java
Index: ExpandableDoubleArrayTest.java
===================================================================
/* ====================================================================
* The Apache Software License, Version 1.1
*
* Copyright (c) 2003 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution, if
* any, must include the following acknowlegement:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowlegement may appear in the software itself,
* if and wherever such third-party acknowlegements normally appear.
*
* 4. The names "The Jakarta Project", "Commons", and "Apache Software
* Foundation" must not be used to endorse or promote products derived
* from this software without prior written permission. For written
* permission, please contact apache@apache.org.
*
* 5. Products derived from this software may not be called "Apache"
* nor may "Apache" appear in their names without prior written
* permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
package org.apache.commons.math;
import java.util.NoSuchElementException;
import junit.framework.TestCase;
/**
* This class contains test cases for the ExpandableDoubleArray.
*
* @author <a href="mailto:tobrien@apache.org">Tim O'Brien</a>
*/
public class ExpandableDoubleArrayTest extends TestCase {
public ExpandableDoubleArrayTest(String name) {
super( name );
}
/** TEST NORMAL OPERATIONS **/
public void testAdd1000() {
ExpandableDoubleArray exDoubleArr = new ExpandableDoubleArray();
for( int i = 0; i < 1000; i++) {
exDoubleArr.addElement( i );
}
assertTrue("Number of elements should be equal to 1000 after adding 1000 values",
exDoubleArr.getNumElements() == 1000);
assertTrue("Internal Storage length should be 1024 if we started out with initial capacity of " +
"16 and an expansion factor of 2.0",
exDoubleArr.getInternalLength() == 1024);
assertTrue("The element at the 56th index should be 56",
exDoubleArr.getElement(56) == 56 );
}
public void testWithInitialCapacity() {
ExpandableDoubleArray exDoubleArr = new ExpandableDoubleArray(2);
assertTrue("Initial internal length should be 2", exDoubleArr.getInternalLength() == 2);
assertTrue("Initial number of elements should be 0", exDoubleArr.getNumElements() == 0);
int iterations = (int) Math.pow(2.0, 15.0);
for( int i = 0; i < iterations; i++) {
exDoubleArr.addElement( i );
}
assertTrue("Number of elements should be equal to 2^15", exDoubleArr.getNumElements() == (int) Math.pow(2.0, 15.0));
assertTrue("Internal length should be 2^15", exDoubleArr.getInternalLength() == (int) Math.pow(2.0, 15.0));
exDoubleArr.addElement( 2.0 );
assertTrue("Number of elements should be equals to 2^15 + 1",
exDoubleArr.getNumElements() == ( (int) Math.pow(2.0, 15.0) + 1 ) );
assertTrue("Internal length should be 2^16", exDoubleArr.getInternalLength() == (int) Math.pow(2.0, 16.0));
}
public void testWithInitialCapacitAndExpansionFactor() {
ExpandableDoubleArray exDoubleArr = new ExpandableDoubleArray(3, 3.0f);
assertTrue("Initial internal length should be 3", exDoubleArr.getInternalLength() == 3);
assertTrue("Initial number of elements should be 0", exDoubleArr.getNumElements() == 0);
int iterations = (int) Math.pow(3.0, 7.0);
for( int i = 0; i < iterations; i++) {
exDoubleArr.addElement( i );
}
assertTrue("Number of elements should be equal to 3^7", exDoubleArr.getNumElements() == (int) Math.pow(3.0, 7.0));
assertTrue("Internal length should be 3^7", exDoubleArr.getInternalLength() == (int) Math.pow(3.0, 7.0));
exDoubleArr.addElement( 2.0 );
assertTrue("Number of elements should be equals to 3^7 + 1",
exDoubleArr.getNumElements() == ( (int) Math.pow(3.0, 7.0) + 1 ) );
assertTrue("Internal length should be 3^8", exDoubleArr.getInternalLength() == (int) Math.pow(3.0, 8.0));
assertTrue("Expansion factor should equal 3.0", exDoubleArr.getExpansionFactor() == 3.0f);
}
public void testGetValues() {
ExpandableDoubleArray eDA = new ExpandableDoubleArray();
double[] controlArray = {2.0, 4.0, 6.0};
eDA.addElement(2.0);
eDA.addElement(4.0);
eDA.addElement(6.0);
double[] testArray = eDA.getValues();
for( int i = 0; i < eDA.getNumElements(); i++) {
assertTrue( "The testArray values should equal the controlArray values, index i: " + i +
" does not match", testArray[i] == controlArray[i]);
}
}
public void testSetElementArbitraryExpansion() {
ExpandableDoubleArray eDA = new ExpandableDoubleArray();
double[] controlArray = {2.0, 4.0, 6.0};
eDA.addElement(2.0);
eDA.addElement(4.0);
eDA.addElement(6.0);
eDA.setElement(1, 3.0);
// Expand the array arbitrarily to 1000 items
eDA.setElement(1000, 3.4);
assertTrue( "The length of the internal array should now be 1001, it isn't", eDA.getInternalLength() == 1001);
assertTrue( "The number of elements should now be 1001, it isn't", eDA.getNumElements() == 1001);
assertTrue( "Uninitialized Elements are default value of 0.0, index 766 wasn't",
eDA.getElement( 760 ) == 0.0);
assertTrue( "The 1000th index should be 3.4, it isn't", eDA.getElement(1000) == 3.4);
assertTrue( "The 0th index should be 2.0, it isn't", eDA.getElement(0) == 2.0);
}
/** TEST ERROR CONDITIONS **/
public void testIllegalInitialCapacity() {
try {
ExpandableDoubleArray eDA = new ExpandableDoubleArray(-3, 2.0f);
fail( "That constructor should have thrown an IllegalArgumentException because " +
"the initialCapacity was negative, if it didn't then" +
" the range checking of initialCapacity is not working properly" );
} catch( IllegalArgumentException iae ) {
}
try {
ExpandableDoubleArray eDA = new ExpandableDoubleArray(0, 2.0f);
fail( "That constructor should have thrown an IllegalArgumentException because " +
"the initialCapacity was ZERO if it didn't then" +
" the range checking of initialCapacity is not working properly" );
} catch( IllegalArgumentException iae ) {
}
}
public void testIllegalExpansionFactor() {
try {
ExpandableDoubleArray eDA = new ExpandableDoubleArray(3, 0.66f);
fail( "That constructor should have thrown an IllegalArgumentException because " +
"the expansionFactor for 0.66 which would shrink the array instead of expand the array");
} catch( IllegalArgumentException iae ) {
}
try {
ExpandableDoubleArray eDA = new ExpandableDoubleArray(3, 0.0f);
fail( "That constructor should have thrown an IllegalArgumentException because " +
"the expansionFactor for 0.0");
} catch( IllegalArgumentException iae) {
}
try {
ExpandableDoubleArray eDA = new ExpandableDoubleArray(3, -4.35f);
fail( "That constructor should have thrown an IllegalArgumentException because " +
"the expansionFactor for -4.35");
} catch( IllegalArgumentException iae) {
}
}
public void testGetOutOfBounds() {
ExpandableDoubleArray eDA = new ExpandableDoubleArray();
eDA.addElement(2.0);
eDA.addElement(3.0);
try {
eDA.getElement(0);
eDA.getElement(1);
} catch( NoSuchElementException nsee ) {
fail( "There are values for index 0 and 1, this should not have thrown an exception");
}
try {
eDA.getElement(2);
fail( "There are 2 elements in the array, you asked for index 2 implying that there are 3. " +
"exception should have been thrown");
} catch( NoSuchElementException nsee ) {
}
try {
eDA.getElement(-234);
fail( "You tried to retrieve a negative index, this should have thrown an exception. " );
} catch( IllegalArgumentException iae) {
}
}
public void testSetOutOfBounds() {
ExpandableDoubleArray eDA = new ExpandableDoubleArray();
try {
eDA.setElement( -3, 3.4 );
fail( "You tried to set an element with a negative index, thisshould have thrown an error");
} catch( IllegalArgumentException iae ) {
}
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org