resizabledoublearray.java

Apache的common math数学软件包

/*
 * 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 org.apache.commons.math.util;

import java.io.Serializable;

/**
 * <p>
 * A variable length {@link DoubleArray} implementation that automatically 
 * handles expanding and contracting its internal storage array as elements 
 * are added and removed.
 * </p>
 * <p>
 *  The internal storage array starts with capacity determined by the
 * <code>initialCapacity</code> 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</code> and <code>expansionFactor</code> properties.  
 * The <code>expansionMode</code> determines whether the size of the array is 
 * multiplied by the <code>expansionFactor</code> (MULTIPLICATIVE_MODE) or if 
 * the expansion is additive (ADDITIVE_MODE -- <code>expansionFactor</code>
 * storage locations added).  The default <code>expansionMode</code> is 
 * MULTIPLICATIVE_MODE and the default <code>expansionFactor</code>
 * is 2.0.
 * </p>
 * <p>
 * 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</code> property) and if the difference
 * is too large, the internal array is contracted to size 
 * <code>numElements + 1.</code>  The determination of when the internal
 * storage array is "too large" depends on the <code>expansionMode</code> and
 * <code>contractionFactor</code> properties.  If  the <code>expansionMode</code>
 * is <code>MULTIPLICATIVE_MODE</code>, contraction is triggered when the
 * ratio between storage array length and <code>numElements</code> exceeds
 * <code>contractionFactor.</code>  If the <code>expansionMode</code>
 * is <code>ADDITIVE_MODE,</code> the number of excess storage locations
 * is compared to <code>contractionFactor.</code>  
 * </p>
 * <p>
 * To avoid cycles of expansions and contractions, the 
 * <code>expansionFactor</code> must not exceed the 
 * <code>contractionFactor.</code> Constructors and mutators for both of these
 * properties enforce this requirement, throwing IllegalArgumentException if it
 * is violated.
 * </p>
 * @version $Revision: 618057 $ $Date: 2008-02-03 11:58:54 -0700 (Sun, 03 Feb 2008) $
 */
public class ResizableDoubleArray implements DoubleArray, Serializable {
    
    /** Serializable version identifier */
    private static final long serialVersionUID = -3485529955529426875L; 
    
    /** additive expansion mode */
    public static final int ADDITIVE_MODE = 1;
    
    /** multiplicative expansion mode */
    public static final int MULTIPLICATIVE_MODE = 0;
   
    /** 
     * The contraction criteria determines when the internal array will be 
     * contracted to fit the number of elements contained in the element
     *  array + 1.
     */
    protected float contractionCriteria = 2.5f;

    /** 
     * The expansion factor of the array.  When the array needs to be expanded, 
     * the new array size will be 
     * <code>internalArray.length * expansionFactor</code>
     * if <code>expansionMode</code> is set to MULTIPLICATIVE_MODE, or
     * <code>internalArray.length + expansionFactor</code> if 
     * <code>expansionMode</code> is set to ADDITIVE_MODE.
     */
    protected float expansionFactor = 2.0f;
    
    /**
     * Determines whether array expansion by <code>expansionFactor</code>
     * 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 <code>
     * internalArray[startIndex],...,internalArray[startIndex + numElements -1]
     * </code>
     */
    protected int startIndex = 0;

    /**
     * Create a ResizableArray with default properties.
     * <ul>
     * <li><code>initialCapacity = 16</code></li>
     * <li><code>expansionMode = MULTIPLICATIVE_MODE</code></li>
     * <li><code>expansionFactor = 2.5</code></li>
     * <li><code>contractionFactor = 2.0</code></li>
     * </ul>
     */
    public ResizableDoubleArray() {
        internalArray = new double[initialCapacity];
    }

    /**
     * Create a ResizableArray with the specified initial capacity.  Other
     * properties take default values:
      * <ul>
     * <li><code>expansionMode = MULTIPLICATIVE_MODE</code></li>
     * <li><code>expansionFactor = 2.5</code></li>
     * <li><code>contractionFactor = 2.0</code></li>
     * </ul>
     * @param initialCapacity The initial size of the internal storage array
     * @throws IllegalArgumentException if initialCapacity is not > 0
     */
    public ResizableDoubleArray(int initialCapacity) {
        setInitialCapacity(initialCapacity);
        internalArray = new double[this.initialCapacity];
    }

    /**
     * <p>
     * Create a ResizableArray with the specified initial capacity 
     * and expansion factor.  The remaining properties take default
     * values:
     * <ul>
     * <li><code>expansionMode = MULTIPLICATIVE_MODE</code></li>
     * <li><code>contractionFactor = 0.5 + expansionFactor</code></li>
     * </ul></p>
     * <p>
     * Throws IllegalArgumentException if the following conditions are
     * not met:
     * <ul>
     * <li><code>initialCapacity > 0</code></li>
     * <li><code>expansionFactor > 1</code></li>
     * </ul></p>
     * 
     * @param initialCapacity The initial size of the internal storage array
     * @param expansionFactor the array will be expanded based on this 
     *                        parameter
     * @throws IllegalArgumentException if parameters are not valid
     */
    public ResizableDoubleArray(int initialCapacity, float expansionFactor) {
        this.expansionFactor = expansionFactor;
        setInitialCapacity(initialCapacity);
        internalArray = new double[initialCapacity];
        setContractionCriteria(expansionFactor +0.5f);
    }

    /**
     * <p>
     * Create a ResizableArray with the specified initialCapacity, 
     * expansionFactor, and contractionCriteria. The <code>expansionMode</code>
     * will default to <code>MULTIPLICATIVE_MODE.</code></p>
     * <p>
     * Throws IllegalArgumentException if the following conditions are
     * not met:
     * <ul>
     * <li><code>initialCapacity > 0</code></li>
     * <li><code>expansionFactor > 1</code></li>
     * <li><code>contractionFactor >= expansionFactor</code></li>
     * </ul></p>
     * @param initialCapacity The initial size of the internal storage array
     * @param expansionFactor the array will be expanded based on this 
     *                        parameter
     * @param contractionCriteria The contraction Criteria.
     * @throws IllegalArgumentException if parameters are not valid
     */
    public ResizableDoubleArray(int initialCapacity, float expansionFactor,
        float contractionCriteria) {
        this.expansionFactor = expansionFactor;
        setContractionCriteria(contractionCriteria);
        setInitialCapacity(initialCapacity);
        internalArray = new double[initialCapacity];
    }
    
    /**
     * <p>
     * Create a ResizableArray with the specified properties.</p>
    * <p>
     * Throws IllegalArgumentException if the following conditions are
     * not met:
     * <ul>
     * <li><code>initialCapacity > 0</code></li>
     * <li><code>expansionFactor > 1</code></li>
     * <li><code>contractionFactor >= expansionFactor</code></li>
     * <li><code>expansionMode in {MULTIPLICATIVE_MODE, ADDITIVE_MODE}</code>
     * </li>
     * </ul></p>
     * 
     * @param initialCapacity the initial size of the internal storage array
     * @param expansionFactor the array will be expanded based on this 
     *                        parameter
     * @param contractionCriteria the contraction Criteria
     * @param expansionMode  the expansion mode
     * @throws IllegalArgumentException if parameters are not valid
     */
    public ResizableDoubleArray(int initialCapacity, float expansionFactor,
            float contractionCriteria, int expansionMode) {
        this.expansionFactor = expansionFactor;
        setContractionCriteria(contractionCriteria);
        setInitialCapacity(initialCapacity);
        setExpansionMode(expansionMode);
        internalArray = new double[initialCapacity];
    }

    /**
     * Adds an element to the end of this expandable array.
     * 
     * @param value to be added to end of array
     */
    public synchronized void addElement(double value) {
        numElements++;
        if ((startIndex + numElements) > internalArray.length) {
            expand();
        }
        internalArray[startIndex + (numElements - 1)] = value;
        if (shouldContract()) {
            contract();
        }
    }

    /**
     * <p>
     * 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.
     * </p>
     * <p>
     * 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.
     * </p>
     * 
     * @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];
    }
    
    /**