commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From tobr...@apache.org
Subject cvs commit: jakarta-commons-sandbox/math/src/test/org/apache/commons/math ExpandableDoubleArrayTest.java ListUnivariateImplTest.java
Date Thu, 15 May 2003 15:38:48 GMT
tobrien     2003/05/15 08:38:48

  Modified:    math     project.xml
               math/src/java/org/apache/commons/math
                        ExpandableDoubleArray.java StoreUnivariateImpl.java
               math/src/test/org/apache/commons/math
                        ExpandableDoubleArrayTest.java
                        ListUnivariateImplTest.java
  Added:       math/src/java/org/apache/commons/math
                        ContractableDoubleArray.java
  Log:
  Made a nubmer of change to the ExpandableDoubleArray.
  
  * This class now supports
  the ability to move the starting index of the internal element array.  This
  allows one to move the beginning of the element array, and form a sort of
  "window", this will come into play when we want to provide moving
  averages, or "rolling".
  
  * Added an addElementRolling(double v) - this will increment the startIndex
  and add the element to the end of the internal element array
  
  * brought the Clover test cases up to 100% for this class
  
  Added a class ContractableDoubleArray:
  
  * This is an extension of ExpandableDoubleArray - it addes a configuration
  parameter contractionCriteria.  Essential if the contractionCriteria is
  2.0f we commit to never having the internal storage array provide more
  than 2.0 times the storage capacity needed.  Once the internal
  storage array exceed this measurement, the internal storage array is
  pruned to the size of the internal element array.
  
  Also, my IDE scolded me for some ununsed imports in ListUnivariateImpl, they
  have been removed.
  
  Revision  Changes    Path
  1.2       +1 -0      jakarta-commons-sandbox/math/project.xml
  
  Index: project.xml
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/math/project.xml,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- project.xml	12 May 2003 19:28:54 -0000	1.1
  +++ project.xml	15 May 2003 15:38:47 -0000	1.2
  @@ -91,4 +91,5 @@
      <report>maven-statcvs-plugin</report>
      <report>maven-tasklist-plugin</report>
     </reports>
  +
   </project>
  
  
  
  1.3       +94 -12    jakarta-commons-sandbox/math/src/java/org/apache/commons/math/ExpandableDoubleArray.java
  
  Index: ExpandableDoubleArray.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/math/src/java/org/apache/commons/math/ExpandableDoubleArray.java,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- ExpandableDoubleArray.java	15 May 2003 06:33:19 -0000	1.2
  +++ ExpandableDoubleArray.java	15 May 2003 15:38:48 -0000	1.3
  @@ -64,19 +64,22 @@
   public class ExpandableDoubleArray implements Serializable {
   
   	// This is the internal storage array.
  -	private double[] internalArray;
  +	protected double[] internalArray;
   
   	// Number of elements in the array
  -	private int numElements = 0;
  +	protected int numElements = 0;
  +	
  +	// Keeps track of a starting index
  +	protected int startIndex = 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;
  +	protected 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;
  +	protected float expansionFactor = 2.0f;
   
   	/**
   	 * Create an expandable double array with the
  @@ -175,6 +178,32 @@
   	}
   
   	/**
  +	 * 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
  +	 * feature is mainly targetted at the subclasses of this array class.  Note
  +	 * that this function will also expand the internal array as needed.
  +	 * 
  +	 * @param a new number of elements
  +	 */
  +	public synchronized void setNumElements(int i) {
  +		
  +		// If index is negative thrown an error
  +		if( i <  0 ) {
  +			throw new IllegalArgumentException( "Number of elements must be zero or a positive integer");
  +		} 
  +		
  +		// 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 the element at the specified index
   	 * 
   	 * @param index index to fetch a value from
  @@ -189,10 +218,10 @@
   					+ " is larger than the "
   					+ "current number of elements");
   		} else if (index >= 0) {
  -			value = internalArray[index];
  +			value = internalArray[startIndex + index];
   		} else {
   			throw new IllegalArgumentException(
  -				"Elements cannot be retrieved from negative array " + "index");
  +				"Elements cannot be retrieved from a negative array index");
   		}
   		return value;
   	}
  @@ -209,11 +238,11 @@
   			throw new IllegalArgumentException( "Cannot set an element at a negative index");
   		}
   		
  -		if (index >= internalArray.length) {
  -			expandTo(index + 1);
  +		if ( (startIndex + index) >= internalArray.length) {
  +			expandTo( startIndex + (index + 1));
   			numElements = index + 1;
   		}
  -		internalArray[index] = value;
  +		internalArray[startIndex + index] = value;
   	}
   
   	/**
  @@ -231,7 +260,7 @@
   	/**
   	 * Expands the internal storage array using the expansion factor
   	 */
  -	private synchronized void expand() {
  +	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
  @@ -253,12 +282,28 @@
   	 */
   	public synchronized void addElement(double value) {
   		numElements++;
  -		if (numElements > internalArray.length) {
  +		if ( (startIndex + numElements) > internalArray.length) {
  +			expand();
  +		}
  +		internalArray[startIndex + (numElements - 1)] = value;
  +	}
  +	
  +	/**
  +	 * Adds an element and moves the window of elements up one.  This
  +	 * has the effect of a FIFO
  +	 */
  +	public synchronized void addElementRolling(double value) {
  +		if ( (startIndex + (numElements+1) ) > internalArray.length) {
   			expand();
   		}
  -		internalArray[numElements - 1] = value;
  +		// Increment the start index
  +		startIndex += 1;
  +		
  +		// Add the new value
  +		internalArray[startIndex + (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
  @@ -276,6 +321,43 @@
   	public synchronized void clear() {
   		numElements = 0;
   		internalArray = new double[initialCapacity];
  +	}
  +
  +	/**
  +	 * Returns the starting index from the internal array.  This value should remain at
  +	 * zero in this implementation of ExpandableDoubleArray.
  +	 * 
  +	 * @return the starting Index in the internal storage array, in this class it is always
zero.
  +	 */
  +	public int getStartIndex() {
  +		return startIndex;
  +	}
  +
  +	/**
  +	 * Sets the starting index of the element array in the internal array, and subtracts the
difference
  +	 * between the original startIndex and the new startIndex from the number of elements.
  This
  +	 * method should be used with care.
  +	 * 
  +	 * @param Index relative to the internal array from which to start the element array
  +	 */
  +	public synchronized void setStartIndex(int i) {
  +		
  +		if( i > (startIndex + numElements) ) {
  +			throw new IllegalArgumentException( "Cannot start the element array outside of the "
+
				"current element array.");
  +		} else if( i < 0 ) {
  +			throw new IllegalArgumentException( "The starting index cannot be set to a negative
index");
  +		} else {
  +			
  +		 	// Calculat the difference between the original start index and the current start index
  +			int difference = i - startIndex;
  +			
  +			// "Subtract" this difference from numElements - this works both ways.  If the
  +			// new start index is lower than the current start index then numElements is
  +			// incremenet by that differen
  +			numElements -= difference;
  +			
  +			startIndex = i;
  +		}
   	}
   
   }
  
  
  
  1.3       +0 -1      jakarta-commons-sandbox/math/src/java/org/apache/commons/math/StoreUnivariateImpl.java
  
  Index: StoreUnivariateImpl.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/math/src/java/org/apache/commons/math/StoreUnivariateImpl.java,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- StoreUnivariateImpl.java	15 May 2003 06:33:19 -0000	1.2
  +++ StoreUnivariateImpl.java	15 May 2003 15:38:48 -0000	1.3
  @@ -64,7 +64,6 @@
   		eDA = new ExpandableDoubleArray();
   	}
   
  -
   	/* (non-Javadoc)
   	 * @see org.apache.commons.math.StoreUnivariate#getValues()
   	 */
  
  
  
  1.1                  jakarta-commons-sandbox/math/src/java/org/apache/commons/math/ContractableDoubleArray.java
  
  Index: ContractableDoubleArray.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.io.Serializable;
  
  /**
   * An array of double primitives which can expand as needed.
   * 
   * @author <a href="mailto:tobrien@apache.org">Tim O'Brien</a>
   */
  public class ContractableDoubleArray extends ExpandableDoubleArray implements Serializable
{
  
  	// The contraction criteria is related to the expansion factor.  Since this array is allowed
to contract
  	// 
  	protected float contractionCriteria = 2.5f;
  
  	/**
  	 * Create an expandable double array with the
  	 * default initial capactiy of 16, an expansion factor of 2.00, and a contractionCriteria
of 2.5
  	 */
  	public ContractableDoubleArray() {
  		super();
  	}	
  
  	/**
  	 * Create an expandable double array with the
  	 * specified initial capacity, the defult expansion factor of 2.00, and a contractionCriteria
of 2.5
  	 * 
  	 * @param initialCapacity The initial size of the internal storage array
  	 */
  	public ContractableDoubleArray(int initialCapacity) {
  		super( initialCapacity );
  	}
  
  	/**
  	 * Create an expandable double array with the
  	 * specificed initial capacity and expand factor, with a contractionCriteria of 2.5
  	 * 
  	 * @param initialCapacity The initial size of the internal storage array
  	 * @param expansionFactor the array will be expanded based on this parameter
  	 */
  	public ContractableDoubleArray(int initialCapacity, float expansionFactor) {
  		this.expansionFactor = expansionFactor;
  		this.initialCapacity = initialCapacity;
  		internalArray = new double[initialCapacity];
  		checkContractExpand(getContractionCriteria(), expansionFactor);
  	}
  
  	/**
  	 * Create an expandable double array with the
  	 * specificed initial capacity, expand factor, and contractionCriteria
  	 * 
  	 * @param initialCapacity The initial size of the internal storage array
  	 * @param expansionFactor the array will be expanded based on this parameter
  	 */
  	public ContractableDoubleArray(int initialCapacity, float expansionFactor, float contractionCriteria)
{
  		this.contractionCriteria = contractionCriteria;
  		this.expansionFactor = expansionFactor;
  		this.initialCapacity = initialCapacity;
  		internalArray = new double[initialCapacity];
  		checkContractExpand(contractionCriteria, expansionFactor);
  	}
  
  	/**
  	 * 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;
  	}
  
  	/**
  	 * 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) {
  		super.addElement( value );
  		if( shouldContract() ) {
  			contract();
  		}
  	}
  
  	/**
  	 * Adds an element to the end of this expandable array
  	 * 
  	 * @return value to be added to end of array
  	 */
  	public synchronized void addElementRolling(double value) {
  		super.addElementRolling(value);
  		// Check the contraction criteria
  		if( shouldContract() ) {
  			contract();
  		}
  	}
  	
  	/**
  	 * Should contract returns true if the ratio of (internal storage length) to (number of
elements)
  	 * is larger than the contractionCriteria value.  In other words, using the default value
  	 * of 2.5, if the internal storage array provides more than 2.5x the space needed to store
  	 * numElements, then this function returns true
  	 * 
  	 * @return true if array satisfies the contraction criteria
  	 */
  	private synchronized boolean shouldContract() {
  		boolean shouldContract = false;
  		if( ( internalArray.length / numElements ) > contractionCriteria ) {
  			shouldContract = true;
  		}
  		return shouldContract;
  	}
  
  	/* (non-Javadoc)
  	 * @see org.apache.commons.math.ExpandableDoubleArray#setElement(int, double)
  	 */
  	public synchronized void setElement(int index, double value) {
  		super.setElement(index, value);
  		if( shouldContract() ) {
  			contract();
  		}
  	}
  
  	/* (non-Javadoc)
  	 * @see org.apache.commons.math.ExpandableDoubleArray#setExpansionFactor(float)
  	 */
  	public void setExpansionFactor(float expansionFactor) {
  		checkContractExpand(getContractionCriteria(), expansionFactor);
  		super.setExpansionFactor(expansionFactor);
  	}
  
  	/* (non-Javadoc)
  	 * @see org.apache.commons.math.ExpandableDoubleArray#setStartIndex(int)
  	 */
  	public synchronized void setStartIndex(int i) {
  		super.setStartIndex(i);
  		if( shouldContract() ) {
  			contract();
  		}
  	}
  
  	/**
  	 * The contraction criteria defines when the internal array will contract to store only
the
  	 * number of elements in the element array.  This contractionCriteria gaurantees that
  	 * the internal storage array will never exceed this factor more than the space needed
  	 * to store numElements.
  	 * 
  	 * @return the contraction criteria used to reclaim memory when array is empty
  	 */
  	public float getContractionCriteria() {
  		return contractionCriteria;
  	}
  
  	/**
  	 * Sets the contraction criteria for this ExpandContractDoubleArray. 
  	 * 
  	 * @param new contraction criteria
  	 */
  	public void setContractionCriteria(float contractionCriteria) {
  		checkContractExpand( contractionCriteria, getExpansionFactor() );
  		
  		if( contractionCriteria <= 1.0 ) {
  			throw new IllegalArgumentException( "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");
  		}
  		this.contractionCriteria = contractionCriteria;
  	}
  	
  	/**
  	 * Checks the expansion factor and the contraction criteria and throws an IllegalArgumentException
  	 * if the contractionCriteria is less than the expansionCriteria
  	 * 
  	 * @param expansionFactor 
  	 * @param contractionCriteria
  	 */
  	public void checkContractExpand( float contractionCritera, float expansionFactor ) {
  		
  		if( contractionCritera < expansionFactor ) {
  			throw new IllegalArgumentException( "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");
  		}
  		
  	}
  	
  }
  
  
  
  1.2       +67 -0     jakarta-commons-sandbox/math/src/test/org/apache/commons/math/ExpandableDoubleArrayTest.java
  
  Index: ExpandableDoubleArrayTest.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/math/src/test/org/apache/commons/math/ExpandableDoubleArrayTest.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- ExpandableDoubleArrayTest.java	15 May 2003 05:19:57 -0000	1.1
  +++ ExpandableDoubleArrayTest.java	15 May 2003 15:38:48 -0000	1.2
  @@ -179,6 +179,73 @@
   		assertTrue( "The 0th index should be 2.0, it isn't", eDA.getElement(0) == 2.0);		
   		
   	}
  +	
  +	public void testSetNumberOfElements() {
  +		
  +		ExpandableDoubleArray eDA = new ExpandableDoubleArray();
  +		eDA.addElement( 1.0 );
  +		eDA.addElement( 1.0 );
  +		eDA.addElement( 1.0 );
  +		eDA.addElement( 1.0 );
  +		eDA.addElement( 1.0 );
  +		eDA.addElement( 1.0 );
  +		assertTrue( "Number of elements should equal 6", eDA.getNumElements() == 6);
  +		
  +		eDA.setNumElements( 3 );
  +		assertTrue( "Number of elements should equal 3", eDA.getNumElements() == 3);
  +		
  +		try {
  +			eDA.setNumElements( -3 );
  +			fail( "Setting number of elements to negative should've thrown an exception");
  +		} catch( IllegalArgumentException iae ) {
  +		}
  +
  +		eDA.setNumElements(1024);
  +		assertTrue( "Number of elements should now be 1024", eDA.getNumElements() == 1024);
  +		assertTrue( "Element 453 should be a default double", eDA.getElement( 453 ) == 0.0);
  +				
  +	}
  +	
  +	public void testAddElementRolling() {
  +		
  +		ExpandableDoubleArray eDA = new ExpandableDoubleArray();
  +		
  +		eDA.addElement( 1.0 );
  +		eDA.addElement( 1.0 );
  +		eDA.addElement( 1.0 );
  +		eDA.addElement( 1.0 );
  +		eDA.addElement( 1.0 );
  +		eDA.addElement( 1.0 );
  +		eDA.addElementRolling( 2.0 );
  +		
  +		assertTrue( "There should be 6 elements in the eda", eDA.getNumElements() == 6);
  +		assertTrue( "The last element should be 2.0", eDA.getElement( eDA.getNumElements() -1
) == 2.0);
  +		
  +		for( int i = 0; i  < 1024; i++ ) {
  +			eDA.addElementRolling( i );
  +		}
  +		
  +		assertTrue( "We just inserted 1024 rolling elements, num elements should still be 6",
eDA.getNumElements() == 6);
  +		assertTrue( "Even though there are only 6 element, internal storage should be 2048",
eDA.getInternalLength() == 2048);
  +		assertEquals( "The start index should be 1025", 1025, eDA.getStartIndex());
  +		
  +		eDA.setStartIndex( 0 );
  +		
  +		assertEquals( "There shoud now be 1031 elements in this array", 1031, eDA.getNumElements(),
0.001);
  +		assertEquals( "The first element should be 1.0",1.0,  eDA.getElement(0), 0.001);
  +		
  +		try {
  +			eDA.setStartIndex( 100000 );
  +			fail( "TRying to set the start index outside of the current array should have caused
an error");
  +		} catch( IllegalArgumentException iae ) {
  +		}
  +
  +		try {
  +			eDA.setStartIndex( -1 );
  +			fail( "TRying to set the start index to a negative number should have caused an error");
  +		} catch( IllegalArgumentException iae ) {
  +		}
  +	}
   
   	/** TEST ERROR CONDITIONS **/
   
  
  
  
  1.2       +1 -2      jakarta-commons-sandbox/math/src/test/org/apache/commons/math/ListUnivariateImplTest.java
  
  Index: ListUnivariateImplTest.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/math/src/test/org/apache/commons/math/ListUnivariateImplTest.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- ListUnivariateImplTest.java	15 May 2003 06:33:19 -0000	1.1
  +++ ListUnivariateImplTest.java	15 May 2003 15:38:48 -0000	1.2
  @@ -54,7 +54,6 @@
   package org.apache.commons.math;
   
   import java.util.ArrayList;
  -import java.util.Collection;
   import java.util.List;
   
   import junit.framework.Test;
  
  
  

---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message