Class ResizableDoubleArray

  • All Implemented Interfaces:
    java.io.Serializable, DoubleArray

    public class ResizableDoubleArray
    extends java.lang.Object
    implements DoubleArray, java.io.Serializable

    A variable length 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 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 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 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.

    Version:
    $Revision: 1073474 $ $Date: 2011-02-22 20:52:17 +0100 (mar. 22 févr. 2011) $
    See Also:
    Serialized Form
    • Field Summary

      Fields 
      Modifier and Type Field Description
      static int ADDITIVE_MODE
      additive expansion mode
      protected float contractionCriteria
      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 expansionFactor
      The expansion factor of the array.
      protected int expansionMode
      Determines whether array expansion by expansionFactor is additive or multiplicative.
      protected int initialCapacity
      The initial capacity of the array.
      protected double[] internalArray
      The internal storage array.
      static int MULTIPLICATIVE_MODE
      multiplicative expansion mode
      protected int numElements
      The number of addressable elements in the array.
      protected int startIndex
      The position of the first addressable element in the internal storage array.
    • Constructor Summary

      Constructors 
      Constructor Description
      ResizableDoubleArray()
      Create a ResizableArray with default properties.
      ResizableDoubleArray​(double[] initialArray)
      Create a ResizableArray from an existing double[] with the initial capacity and numElements corresponding to the size of the supplied double[] array.
      ResizableDoubleArray​(int initialCapacity)
      Create a ResizableArray with the specified initial capacity.
      ResizableDoubleArray​(int initialCapacity, float expansionFactor)
      Create a ResizableArray with the specified initial capacity and expansion factor.
      ResizableDoubleArray​(int initialCapacity, float expansionFactor, float contractionCriteria)
      Create a ResizableArray with the specified initialCapacity, expansionFactor, and contractionCriteria.
      ResizableDoubleArray​(int initialCapacity, float expansionFactor, float contractionCriteria, int expansionMode)
      Create a ResizableArray with the specified properties.
      ResizableDoubleArray​(ResizableDoubleArray original)
      Copy constructor.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods Deprecated Methods 
      Modifier and Type Method Description
      void addElement​(double value)
      Adds an element to the end of this expandable array.
      double addElementRolling​(double value)
      Adds an element to the end of the array and removes the first element in the array.
      void addElements​(double[] values)
      Adds several element to the end of this expandable array.
      protected void checkContractExpand​(float contraction, float expansion)
      Checks the expansion factor and the contraction criteria and throws an IllegalArgumentException if the contractionCriteria is less than the expansionCriteria
      void clear()
      Clear the array, reset the size to the initialCapacity and the number of elements to zero.
      void contract()
      Contracts the storage array to the (size of the element set) + 1 - to avoid a zero length array.
      ResizableDoubleArray copy()
      Returns a copy of the ResizableDoubleArray.
      static void copy​(ResizableDoubleArray source, ResizableDoubleArray dest)
      Copies source to dest, copying the underlying data, so dest is a new, independent copy of source.
      void discardFrontElements​(int i)
      Discards the i initial elements of the array.
      void discardMostRecentElements​(int i)
      Discards the i last elements of the array.
      boolean equals​(java.lang.Object object)
      Returns true iff object is a ResizableDoubleArray with the same properties as this and an identical internal storage array.
      protected void expand()
      Expands the internal storage array using the expansion factor.
      float getContractionCriteria()
      The contraction criteria defines when the internal array will contract to store only the number of elements in the element array.
      double getElement​(int index)
      Returns the element at the specified index
      double[] getElements()
      Returns a double array containing the elements of this ResizableArray.
      float getExpansionFactor()
      The expansion factor controls the size of a new array when an array needs to be expanded.
      int getExpansionMode()
      The expansionMode determines whether the internal storage array grows additively (ADDITIVE_MODE) or multiplicatively (MULTIPLICATIVE_MODE) when it is expanded.
      double[] getInternalValues()
      Returns the internal storage array.
      int getNumElements()
      Returns the number of elements currently in the array.
      double[] getValues()
      Deprecated.
      replaced by getInternalValues() as of 2.0
      int hashCode()
      Returns a hash code consistent with equals.
      void setContractionCriteria​(float contractionCriteria)
      Sets the contraction criteria for this ExpandContractDoubleArray.
      void setElement​(int index, double value)
      Sets the element at the specified index.
      void setExpansionFactor​(float expansionFactor)
      Sets the expansionFactor.
      void setExpansionMode​(int expansionMode)
      Sets the expansionMode.
      protected void setInitialCapacity​(int initialCapacity)
      Sets the initial capacity.
      void setNumElements​(int i)
      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.
      int start()
      Returns the starting index of the internal array.
      double substituteMostRecentElement​(double value)
      Substitutes value for the most recently added value.
      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • ADDITIVE_MODE

        public static final int ADDITIVE_MODE
        additive expansion mode
        See Also:
        Constant Field Values
      • MULTIPLICATIVE_MODE

        public static final int MULTIPLICATIVE_MODE
        multiplicative expansion mode
        See Also:
        Constant Field Values
      • contractionCriteria

        protected float contractionCriteria
        The contraction criteria determines when the internal array will be contracted to fit the number of elements contained in the element array + 1.
      • expansionFactor

        protected float expansionFactor
        The expansion factor of the array. When the array needs to be expanded, the new array size will be internalArray.length * expansionFactor if expansionMode is set to MULTIPLICATIVE_MODE, or internalArray.length + expansionFactor if expansionMode is set to ADDITIVE_MODE.
      • expansionMode

        protected int expansionMode
        Determines whether array expansion by expansionFactor is additive or multiplicative.
      • initialCapacity

        protected int initialCapacity
        The initial capacity of the array. Initial capacity is not exposed as a property as it is only meaningful when passed to a constructor.
      • internalArray

        protected double[] internalArray
        The internal storage array.
      • numElements

        protected int numElements
        The number of addressable elements in the array. Note that this has nothing to do with the length of the internal storage array.
      • startIndex

        protected int startIndex
        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]
    • Constructor Detail

      • ResizableDoubleArray

        public ResizableDoubleArray()
        Create a ResizableArray with default properties.
        • initialCapacity = 16
        • expansionMode = MULTIPLICATIVE_MODE
        • expansionFactor = 2.5
        • contractionFactor = 2.0
      • ResizableDoubleArray

        public ResizableDoubleArray​(int initialCapacity)
        Create a ResizableArray with the specified initial capacity. Other properties take default values:
        • expansionMode = MULTIPLICATIVE_MODE
        • expansionFactor = 2.5
        • contractionFactor = 2.0
        Parameters:
        initialCapacity - The initial size of the internal storage array
        Throws:
        java.lang.IllegalArgumentException - if initialCapacity is not > 0
      • ResizableDoubleArray

        public ResizableDoubleArray​(double[] initialArray)
        Create a ResizableArray from an existing double[] with the initial capacity and numElements corresponding to the size of the supplied double[] array. If the supplied array is null, a new empty array with the default initial capacity will be created. The input array is copied, not referenced. Other properties take default values:
        • initialCapacity = 16
        • expansionMode = MULTIPLICATIVE_MODE
        • expansionFactor = 2.5
        • contractionFactor = 2.0
        Parameters:
        initialArray - initial array
        Since:
        2.2
      • ResizableDoubleArray

        public ResizableDoubleArray​(int initialCapacity,
                                    float expansionFactor)

        Create a ResizableArray with the specified initial capacity and expansion factor. The remaining properties take default values:

        • expansionMode = MULTIPLICATIVE_MODE
        • contractionFactor = 0.5 + expansionFactor

        Throws IllegalArgumentException if the following conditions are not met:

        • initialCapacity > 0
        • expansionFactor > 1

        Parameters:
        initialCapacity - The initial size of the internal storage array
        expansionFactor - the array will be expanded based on this parameter
        Throws:
        java.lang.IllegalArgumentException - if parameters are not valid
      • ResizableDoubleArray

        public ResizableDoubleArray​(int initialCapacity,
                                    float expansionFactor,
                                    float contractionCriteria)

        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 > 0
        • expansionFactor > 1
        • contractionFactor >= expansionFactor

        Parameters:
        initialCapacity - The initial size of the internal storage array
        expansionFactor - the array will be expanded based on this parameter
        contractionCriteria - The contraction Criteria.
        Throws:
        java.lang.IllegalArgumentException - if parameters are not valid
      • ResizableDoubleArray

        public ResizableDoubleArray​(int initialCapacity,
                                    float expansionFactor,
                                    float contractionCriteria,
                                    int expansionMode)

        Create a ResizableArray with the specified properties.

        Throws IllegalArgumentException if the following conditions are not met:

        • initialCapacity > 0
        • expansionFactor > 1
        • contractionFactor >= expansionFactor
        • expansionMode in {MULTIPLICATIVE_MODE, ADDITIVE_MODE}

        Parameters:
        initialCapacity - the initial size of the internal storage array
        expansionFactor - the array will be expanded based on this parameter
        contractionCriteria - the contraction Criteria
        expansionMode - the expansion mode
        Throws:
        java.lang.IllegalArgumentException - if parameters are not valid
      • ResizableDoubleArray

        public ResizableDoubleArray​(ResizableDoubleArray original)
        Copy constructor. Creates a new ResizableDoubleArray that is a deep, fresh copy of the original. Needs to acquire synchronization lock on original. Original may not be null; otherwise a NullPointerException is thrown.
        Parameters:
        original - array to copy
        Since:
        2.0
    • Method Detail

      • addElement

        public void addElement​(double value)
        Adds an element to the end of this expandable array.
        Specified by:
        addElement in interface DoubleArray
        Parameters:
        value - to be added to end of array
      • addElements

        public void addElements​(double[] values)
        Adds several element to the end of this expandable array.
        Parameters:
        values - to be added to end of array
        Since:
        2.2
      • addElementRolling

        public double addElementRolling​(double value)

        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.

        Specified by:
        addElementRolling in interface DoubleArray
        Parameters:
        value - the value to be added to the array
        Returns:
        the value which has been discarded or "pushed" out of the array by this rolling insert
      • substituteMostRecentElement

        public double substituteMostRecentElement​(double value)
        Substitutes value for the most recently added value. Returns the value that has been replaced. If the array is empty (i.e. if numElements is zero), a MathRuntimeException is thrown.
        Parameters:
        value - new value to substitute for the most recently added value
        Returns:
        value that has been replaced in the array
        Since:
        2.0
      • checkContractExpand

        protected void checkContractExpand​(float contraction,
                                           float expansion)
        Checks the expansion factor and the contraction criteria and throws an IllegalArgumentException if the contractionCriteria is less than the expansionCriteria
        Parameters:
        expansion - factor to be checked
        contraction - criteria to be checked
        Throws:
        java.lang.IllegalArgumentException - if the contractionCriteria is less than the expansionCriteria.
      • clear

        public void clear()
        Clear the array, reset the size to the initialCapacity and the number of elements to zero.
        Specified by:
        clear in interface DoubleArray
      • contract

        public void contract()
        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.
      • discardFrontElements

        public void discardFrontElements​(int i)
        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.
        Parameters:
        i - the number of elements to discard from the front of the array
        Throws:
        java.lang.IllegalArgumentException - if i is greater than numElements.
        Since:
        2.0
      • discardMostRecentElements

        public void discardMostRecentElements​(int i)
        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.
        Parameters:
        i - the number of elements to discard from the end of the array
        Throws:
        java.lang.IllegalArgumentException - if i is greater than numElements.
        Since:
        2.0
      • expand

        protected void expand()
        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

      • getContractionCriteria

        public float getContractionCriteria()
        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.
        Returns:
        the contraction criteria used to reclaim memory.
      • getElement

        public double getElement​(int index)
        Returns the element at the specified index
        Specified by:
        getElement in interface DoubleArray
        Parameters:
        index - index to fetch a value from
        Returns:
        value stored at the specified index
        Throws:
        java.lang.ArrayIndexOutOfBoundsException - if index is less than zero or is greater than getNumElements() - 1.
      • getElements

        public double[] getElements()
        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.
        Specified by:
        getElements in interface DoubleArray
        Returns:
        the double array.
      • getExpansionFactor

        public float getExpansionFactor()
        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.
        Returns:
        the expansion factor of this expandable double array
      • getExpansionMode

        public int getExpansionMode()
        The expansionMode determines whether the internal storage array grows additively (ADDITIVE_MODE) or multiplicatively (MULTIPLICATIVE_MODE) when it is expanded.
        Returns:
        Returns the expansionMode.
      • getNumElements

        public int getNumElements()
        Returns the number of elements currently in the array. Please note that this is different from the length of the internal storage array.
        Specified by:
        getNumElements in interface DoubleArray
        Returns:
        number of elements
      • getValues

        @Deprecated
        public double[] getValues()
        Deprecated.
        replaced by getInternalValues() as of 2.0
        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 start() method). This method should only be used in cases where copying the internal array is not practical. The getElements() method should be used in all other cases.
        Returns:
        the internal storage array used by this object
      • getInternalValues

        public double[] getInternalValues()
        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 start() method). This method should only be used in cases where copying the internal array is not practical. The getElements() method should be used in all other cases.
        Returns:
        the internal storage array used by this object
        Since:
        2.0
      • setContractionCriteria

        public void setContractionCriteria​(float contractionCriteria)
        Sets the contraction criteria for this ExpandContractDoubleArray.
        Parameters:
        contractionCriteria - contraction criteria
      • setElement

        public void setElement​(int index,
                               double value)
        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).
        Specified by:
        setElement in interface DoubleArray
        Parameters:
        index - index to store a value in
        value - value to store at the specified index
        Throws:
        java.lang.ArrayIndexOutOfBoundsException - if index is less than zero.
      • setExpansionFactor

        public void setExpansionFactor​(float expansionFactor)
        Sets the expansionFactor. Throws IllegalArgumentException if the the following conditions are not met:
        • expansionFactor > 1
        • contractionFactor >= expansionFactor
        Parameters:
        expansionFactor - the new expansion factor value.
        Throws:
        java.lang.IllegalArgumentException - if expansionFactor is <= 1 or greater than contractionFactor
      • setExpansionMode

        public void setExpansionMode​(int expansionMode)
        Sets the expansionMode. The specified value must be one of ADDITIVE_MODE, MULTIPLICATIVE_MODE.
        Parameters:
        expansionMode - The expansionMode to set.
        Throws:
        java.lang.IllegalArgumentException - if the specified mode value is not valid
      • setInitialCapacity

        protected void setInitialCapacity​(int initialCapacity)
        Sets the initial capacity. Should only be invoked by constructors.
        Parameters:
        initialCapacity - of the array
        Throws:
        java.lang.IllegalArgumentException - if initialCapacity is not positive.
      • setNumElements

        public void setNumElements​(int i)
        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.
        Parameters:
        i - a new number of elements
        Throws:
        java.lang.IllegalArgumentException - if i is negative.
      • start

        public int start()
        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]
        Returns:
        starting index
      • copy

        public static void copy​(ResizableDoubleArray source,
                                ResizableDoubleArray dest)

        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 NullPointerException is thrown

        Parameters:
        source - ResizableDoubleArray to copy
        dest - ResizableArray to replace with a copy of the source array
        Since:
        2.0
      • copy

        public ResizableDoubleArray copy()
        Returns a copy of the ResizableDoubleArray. Does not contract before the copy, so the returned object is an exact copy of this.
        Returns:
        a new ResizableDoubleArray with the same data and configuration properties as this
        Since:
        2.0
      • equals

        public boolean equals​(java.lang.Object object)
        Returns true iff object is a ResizableDoubleArray with the same properties as this and an identical internal storage array.
        Overrides:
        equals in class java.lang.Object
        Parameters:
        object - object to be compared for equality with this
        Returns:
        true iff object is a ResizableDoubleArray with the same data and properties as this
        Since:
        2.0
      • hashCode

        public int hashCode()
        Returns a hash code consistent with equals.
        Overrides:
        hashCode in class java.lang.Object
        Returns:
        hash code representing this ResizableDoubleArray
        Since:
        2.0