    001    /*
    002     * Licensed to the Apache Software Foundation (ASF) under one or more
    003     * contributor license agreements.  See the NOTICE file distributed with
    004     * this work for additional information regarding copyright ownership.
    005     * The ASF licenses this file to You under the Apache License, Version 2.0
    006     * (the "License"); you may not use this file except in compliance with
    007     * the License.  You may obtain a copy of the License at
    008     *
    009     *      http://www.apache.org/licenses/LICENSE-2.0
    010     *
    011     * Unless required by applicable law or agreed to in writing, software
    012     * distributed under the License is distributed on an "AS IS" BASIS,
    013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014     * See the License for the specific language governing permissions and
    015     * limitations under the License.
    016     */
    017    package org.apache.commons.math3.util;
    018
    019    import java.io.Serializable;
    020    import java.util.Arrays;
    021
    022    import org.apache.commons.math3.exception.MathIllegalArgumentException;
    023    import org.apache.commons.math3.exception.MathIllegalStateException;
    024    import org.apache.commons.math3.exception.MathInternalError;
    025    import org.apache.commons.math3.exception.NullArgumentException;
    026    import org.apache.commons.math3.exception.NotStrictlyPositiveException;
    027    import org.apache.commons.math3.exception.NumberIsTooSmallException;
    028    import org.apache.commons.math3.exception.util.LocalizedFormats;
    029
    030    /**
    031     * <p>
    032     * A variable length {@link DoubleArray} implementation that automatically
    033     * handles expanding and contracting its internal storage array as elements
    034     * are added and removed.
    035     * </p>
    036     * <h3>Important note: Usage should not assume that this class is thread-safe
    037     * even though some of the methods are {@code synchronized}.
    038     * This qualifier will be dropped in the next major release (4.0).</h3>
    039     * <p>
    040     * The internal storage array starts with capacity determined by the
    041     * {@code initialCapacity} property, which can be set by the constructor.
    042     * The default initial capacity is 16.  Adding elements using
    043     * {@link #addElement(double)} appends elements to the end of the array.
    044     * When there are no open entries at the end of the internal storage array,
    045     * the array is expanded.  The size of the expanded array depends on the
    046     * {@code expansionMode} and {@code expansionFactor} properties.
    047     * The {@code expansionMode} determines whether the size of the array is
    048     * multiplied by the {@code expansionFactor}
    049     * ({@link ExpansionMode#MULTIPLICATIVE}) or if the expansion is additive
    050     * ({@link ExpansionMode#ADDITIVE} -- {@code expansionFactor} storage
    051     * locations added).
    052     * The default {@code expansionMode} is {@code MULTIPLICATIVE} and the default
    053     * {@code expansionFactor} is 2.
    054     * </p>
    055     * <p>
    056     * The {@link #addElementRolling(double)} method adds a new element to the end
    057     * of the internal storage array and adjusts the "usable window" of the
    058     * internal array forward by one position (effectively making what was the
    059     * second element the first, and so on).  Repeated activations of this method
    060     * (or activation of {@link #discardFrontElements(int)}) will effectively orphan
    061     * the storage locations at the beginning of the internal storage array.  To
    062     * reclaim this storage, each time one of these methods is activated, the size
    063     * of the internal storage array is compared to the number of addressable
    064     * elements (the {@code numElements} property) and if the difference
    065     * is too large, the internal array is contracted to size
    066     * {@code numElements + 1}.  The determination of when the internal
    067     * storage array is "too large" depends on the {@code expansionMode} and
    068     * {@code contractionFactor} properties.  If  the {@code expansionMode}
    069     * is {@code MULTIPLICATIVE}, contraction is triggered when the
    070     * ratio between storage array length and {@code numElements} exceeds
    071     * {@code contractionFactor.}  If the {@code expansionMode}
    072     * is {@code ADDITIVE}, the number of excess storage locations
    073     * is compared to {@code contractionFactor}.
    074     * </p>
    075     * <p>
    076     * To avoid cycles of expansions and contractions, the
    077     * {@code expansionFactor} must not exceed the {@code contractionFactor}.
    078     * Constructors and mutators for both of these properties enforce this
    079     * requirement, throwing a {@code MathIllegalArgumentException} if it is
    080     * violated.
    081     * </p>
    082     * @version $Id: ResizableDoubleArray.java 1422433 2012-12-16 00:45:18Z erans $
    083     */
    084    public class ResizableDoubleArray implements DoubleArray, Serializable {
    085        /** Additive expansion mode.
    086         * @deprecated As of 3.1. Please use {@link ExpansionMode#ADDITIVE} instead.
    087         */
    088        @Deprecated
    089        public static final int ADDITIVE_MODE = 1;
    090        /** Multiplicative expansion mode.
    091         * @deprecated As of 3.1. Please use {@link ExpansionMode#MULTIPLICATIVE} instead.
    092         */
    093        @Deprecated
    094        public static final int MULTIPLICATIVE_MODE = 0;
    095        /** Serializable version identifier. */
    096        private static final long serialVersionUID = -3485529955529426875L;
    097
    098        /** Default value for initial capacity. */
    099        private static final int DEFAULT_INITIAL_CAPACITY = 16;
    100        /** Default value for array size modifier. */
    101        private static final double DEFAULT_EXPANSION_FACTOR = 2.0;
    102        /**
    103         * Default value for the difference between {@link #contractionCriterion}
    104         * and {@link #expansionFactor}.
    105         */
    106        private static final double DEFAULT_CONTRACTION_DELTA = 0.5;
    107
    108        /**
    109         * The contraction criteria determines when the internal array will be
    110         * contracted to fit the number of elements contained in the element
    111         *  array + 1.
    112         */
    113        private double contractionCriterion = 2.5;
    114
    115        /**
    116         * The expansion factor of the array.  When the array needs to be expanded,
    117         * the new array size will be
    118         * {@code internalArray.length * expansionFactor}
    119         * if {@code expansionMode} is set to MULTIPLICATIVE_MODE, or
    120         * {@code internalArray.length + expansionFactor} if
    121         * {@code expansionMode} is set to ADDITIVE_MODE.
    122         */
    123        private double expansionFactor = 2.0;
    124
    125        /**
    126         * Determines whether array expansion by {@code expansionFactor}
    127         * is additive or multiplicative.
    128         */
    129        private ExpansionMode expansionMode = ExpansionMode.MULTIPLICATIVE;
    130
    131        /**
    132         * The internal storage array.
    133         */
    134        private double[] internalArray;
    135
    136        /**
    137         * The number of addressable elements in the array.  Note that this
    138         * has nothing to do with the length of the internal storage array.
    139         */
    140        private int numElements = 0;
    141
    142        /**
    143         * The position of the first addressable element in the internal storage
    144         * array.  The addressable elements in the array are
    145         * {@code internalArray[startIndex],...,internalArray[startIndex + numElements - 1]}.
    146         */
    147        private int startIndex = 0;
    148
    149        /**
    150         * Specification of expansion algorithm.
    151         * @since 3.1
    152         */
    153        public static enum ExpansionMode {
    154            /** Multiplicative expansion mode. */
    155            MULTIPLICATIVE,
    156            /** Additive expansion mode. */
    157            ADDITIVE
    158        }
    159
    160        /**
    161         * Creates an instance with default properties.
    162         * <ul>
    163         *  <li>{@code initialCapacity = 16}</li>
    164         *  <li>{@code expansionMode = MULTIPLICATIVE}</li>
    165         *  <li>{@code expansionFactor = 2.0}</li>
    166         *  <li>{@code contractionCriterion = 2.5}</li>
    167         * </ul>
    168         */
    169        public ResizableDoubleArray() {
    170            this(DEFAULT_INITIAL_CAPACITY);
    171        }
    172
    173        /**
    174         * Creates an instance with the specified initial capacity.
    175         * Other properties take default values:
    176         * <ul>
    177         *  <li>{@code expansionMode = MULTIPLICATIVE}</li>
    178         *  <li>{@code expansionFactor = 2.0}</li>
    179         *  <li>{@code contractionCriterion = 2.5}</li>
    180         * </ul>
    181         * @param initialCapacity Initial size of the internal storage array.
    182         * @throws MathIllegalArgumentException if {@code initialCapacity <= 0}.
    183         */
    184        public ResizableDoubleArray(int initialCapacity)
    185            throws MathIllegalArgumentException {
    186            this(initialCapacity, DEFAULT_EXPANSION_FACTOR);
    187        }
    188
    189        /**
    190         * Creates an instance from an existing {@code double[]} with the
    191         * initial capacity and numElements corresponding to the size of
    192         * the supplied {@code double[]} array.
    193         * If the supplied array is null, a new empty array with the default
    194         * initial capacity will be created.
    195         * The input array is copied, not referenced.
    196         * Other properties take default values:
    197         * <ul>
    198         *  <li>{@code initialCapacity = 16}</li>
    199         *  <li>{@code expansionMode = MULTIPLICATIVE}</li>
    200         *  <li>{@code expansionFactor = 2.0}</li>
    201         *  <li>{@code contractionCriterion = 2.5}</li>
    202         * </ul>
    203         *
    204         * @param initialArray initial array
    205         * @since 2.2
    206         */
    207        public ResizableDoubleArray(double[] initialArray) {
    208            this(DEFAULT_INITIAL_CAPACITY,
    209                 DEFAULT_EXPANSION_FACTOR,
    210                 DEFAULT_CONTRACTION_DELTA + DEFAULT_EXPANSION_FACTOR,
    211                 ExpansionMode.MULTIPLICATIVE,
    212                 initialArray);
    213        }
    214
    215        /**
    216         * Creates an instance with the specified initial capacity
    217         * and expansion factor.
    218         * The remaining properties take default values:
    219         * <ul>
    220         *  <li>{@code expansionMode = MULTIPLICATIVE}</li>
    221         *  <li>{@code contractionCriterion = 0.5 + expansionFactor}</li>
    222         * </ul>
    223         * <br/>
    224         * Throws IllegalArgumentException if the following conditions are
    225         * not met:
    226         * <ul>
    227         *  <li>{@code initialCapacity > 0}</li>
    228         *  <li>{@code expansionFactor > 1}</li>
    229         * </ul>
    230         *
    231         * @param initialCapacity Initial size of the internal storage array.
    232         * @param expansionFactor The array will be expanded based on this
    233         * parameter.
    234         * @throws MathIllegalArgumentException if parameters are not valid.
    235         * @deprecated As of 3.1. Please use
    236         * {@link #ResizableDoubleArray(int,double)} instead.
    237         */
    238        @Deprecated
    239        public ResizableDoubleArray(int initialCapacity,
    240                                    float expansionFactor)
    241            throws MathIllegalArgumentException {
    242            this(initialCapacity,
    243                 (double) expansionFactor);
    244        }
    245
    246        /**
    247         * Creates an instance with the specified initial capacity
    248         * and expansion factor.
    249         * The remaining properties take default values:
    250         * <ul>
    251         *  <li>{@code expansionMode = MULTIPLICATIVE}</li>
    252         *  <li>{@code contractionCriterion = 0.5 + expansionFactor}</li>
    253         * </ul>
    254         * <br/>
    255         * Throws IllegalArgumentException if the following conditions are
    256         * not met:
    257         * <ul>
    258         *  <li>{@code initialCapacity > 0}</li>
    259         *  <li>{@code expansionFactor > 1}</li>
    260         * </ul>
    261         *
    262         * @param initialCapacity Initial size of the internal storage array.
    263         * @param expansionFactor The array will be expanded based on this
    264         * parameter.
    265         * @throws MathIllegalArgumentException if parameters are not valid.
    266         * @since 3.1
    267         */
    268        public ResizableDoubleArray(int initialCapacity,
    269                                    double expansionFactor)
    270            throws MathIllegalArgumentException {
    271            this(initialCapacity,
    272                 expansionFactor,
    273                 DEFAULT_CONTRACTION_DELTA + expansionFactor);
    274        }
    275
    276        /**
    277         * Creates an instance with the specified initialCapacity,
    278         * expansionFactor, and contractionCriterion.
    279         * The expansion mode will default to {@code MULTIPLICATIVE}.
    280         * <br/>
    281         * Throws IllegalArgumentException if the following conditions are
    282         * not met:
    283         * <ul>
    284         *  <li>{@code initialCapacity > 0}</li>
    285         *  <li>{@code expansionFactor > 1}</li>
    286         *  <li>{@code contractionCriterion >= expansionFactor}</li>
    287         * </ul>
    288         *
    289         * @param initialCapacity Initial size of the internal storage array..
    290         * @param expansionFactor The array will be expanded based on this
    291         * parameter.
    292         * @param contractionCriteria Contraction criteria.
    293         * @throws MathIllegalArgumentException if parameters are not valid.
    294         * @deprecated As of 3.1. Please use
    295         * {@link #ResizableDoubleArray(int,double,double)} instead.
    296         */
    297        @Deprecated
    298        public ResizableDoubleArray(int initialCapacity,
    299                                    float expansionFactor,
    300                                    float contractionCriteria)
    301            throws MathIllegalArgumentException {
    302            this(initialCapacity,
    303                 (double) expansionFactor,
    304                 (double) contractionCriteria);
    305        }
    306
    307        /**
    308         * Creates an instance with the specified initial capacity,
    309         * expansion factor, and contraction criteria.
    310         * The expansion mode will default to {@code MULTIPLICATIVE}.
    311         * <br/>
    312         * Throws IllegalArgumentException if the following conditions are
    313         * not met:
    314         * <ul>
    315         *  <li>{@code initialCapacity > 0}</li>
    316         *  <li>{@code expansionFactor > 1}</li>
    317         *  <li>{@code contractionCriterion >= expansionFactor}</li>
    318         * </ul>
    319         *
    320         * @param initialCapacity Initial size of the internal storage array..
    321         * @param expansionFactor The array will be expanded based on this
    322         * parameter.
    323         * @param contractionCriterion Contraction criterion.
    324         * @throws MathIllegalArgumentException if the parameters are not valid.
    325         * @since 3.1
    326         */
    327        public ResizableDoubleArray(int initialCapacity,
    328                                    double expansionFactor,
    329                                    double contractionCriterion)
    330            throws MathIllegalArgumentException {
    331            this(initialCapacity,
    332                 expansionFactor,
    333                 contractionCriterion,
    334                 ExpansionMode.MULTIPLICATIVE,
    335                 null);
    336        }
    337
    338        /**
    339         * <p>
    340         * Create a ResizableArray with the specified properties.</p>
    341         * <p>
    342         * Throws IllegalArgumentException if the following conditions are
    343         * not met:
    344         * <ul>
    345         * <li><code>initialCapacity > 0</code></li>
    346         * <li><code>expansionFactor > 1</code></li>
    347         * <li><code>contractionFactor >= expansionFactor</code></li>
    348         * <li><code>expansionMode in {MULTIPLICATIVE_MODE, ADDITIVE_MODE}</code>
    349         * </li>
    350         * </ul></p>
    351         *
    352         * @param initialCapacity the initial size of the internal storage array
    353         * @param expansionFactor the array will be expanded based on this
    354         *                        parameter
    355         * @param contractionCriteria the contraction Criteria
    356         * @param expansionMode  the expansion mode
    357         * @throws MathIllegalArgumentException if parameters are not valid
    358         * @deprecated As of 3.1. Please use
    359         * {@link #ResizableDoubleArray(int,double,double,ExpansionMode,double[])}
    360         * instead.
    361         */
    362        public ResizableDoubleArray(int initialCapacity, float expansionFactor,
    363                float contractionCriteria, int expansionMode) throws MathIllegalArgumentException {
    364            this(initialCapacity,
    365                 expansionFactor,
    366                 contractionCriteria,
    367                 expansionMode == ADDITIVE_MODE ?
    368                 ExpansionMode.ADDITIVE :
    369                 ExpansionMode.MULTIPLICATIVE,
    370                 null);
    371            // XXX Just ot retain the expected failure in a unit test.
    372            // With the new "enum", that test will become obsolete.
    373            setExpansionMode(expansionMode);
    374        }
    375
    376        /**
    377         * Creates an instance with the specified properties.
    378         * <br/>
    379         * Throws MathIllegalArgumentException if the following conditions are
    380         * not met:
    381         * <ul>
    382         *  <li>{@code initialCapacity > 0}</li>
    383         *  <li>{@code expansionFactor > 1}</li>
    384         *  <li>{@code contractionCriterion >= expansionFactor}</li>
    385         * </ul>
    386         *
    387         * @param initialCapacity Initial size of the internal storage array.
    388         * @param expansionFactor The array will be expanded based on this
    389         * parameter.
    390         * @param contractionCriterion Contraction criteria.
    391         * @param expansionMode Expansion mode.
    392         * @param data Initial contents of the array.
    393         * @throws MathIllegalArgumentException if the parameters are not valid.
    394         */
    395        public ResizableDoubleArray(int initialCapacity,
    396                                    double expansionFactor,
    397                                    double contractionCriterion,
    398                                    ExpansionMode expansionMode,
    399                                    double ... data)
    400            throws MathIllegalArgumentException {
    401            if (initialCapacity <= 0) {
    402                throw new NotStrictlyPositiveException(LocalizedFormats.INITIAL_CAPACITY_NOT_POSITIVE,
    403                                                       initialCapacity);
    404            }
    405            checkContractExpand(contractionCriterion, expansionFactor);
    406
    407            this.expansionFactor = expansionFactor;
    408            this.contractionCriterion = contractionCriterion;
    409            this.expansionMode = expansionMode;
    410            internalArray = new double[initialCapacity];
    411            numElements = 0;
    412            startIndex = 0;
    413
    414            if (data != null) {
    415                addElements(data);
    416            }
    417        }
    418
    419        /**
    420         * Copy constructor.  Creates a new ResizableDoubleArray that is a deep,
    421         * fresh copy of the original. Needs to acquire synchronization lock
    422         * on original.  Original may not be null; otherwise a {@link NullArgumentException}
    423         * is thrown.
    424         *
    425         * @param original array to copy
    426         * @exception NullArgumentException if original is null
    427         * @since 2.0
    428         */
    429        public ResizableDoubleArray(ResizableDoubleArray original)
    430            throws NullArgumentException {
    431            MathUtils.checkNotNull(original);
    432            copy(original, this);
    433        }
    434
    435        /**
    436         * Adds an element to the end of this expandable array.
    437         *
    438         * @param value Value to be added to end of array.
    439         */
    440        public synchronized void addElement(double value) {
    441            if (internalArray.length <= startIndex + numElements) {
    442                expand();
    443            }
    444            internalArray[startIndex + numElements++] = value;
    445        }
    446
    447        /**
    448         * Adds several element to the end of this expandable array.
    449         *
    450         * @param values Values to be added to end of array.
    451         * @since 2.2
    452         */
    453        public synchronized void addElements(double[] values) {
    454            final double[] tempArray = new double[numElements + values.length + 1];
    455            System.arraycopy(internalArray, startIndex, tempArray, 0, numElements);
    456            System.arraycopy(values, 0, tempArray, numElements, values.length);
    457            internalArray = tempArray;
    458            startIndex = 0;
    459            numElements += values.length;
    460        }
    461
    462        /**
    463         * <p>
    464         * Adds an element to the end of the array and removes the first
    465         * element in the array.  Returns the discarded first element.
    466         * The effect is similar to a push operation in a FIFO queue.
    467         * </p>
    468         * <p>
    469         * Example: If the array contains the elements 1, 2, 3, 4 (in that order)
    470         * and addElementRolling(5) is invoked, the result is an array containing
    471         * the entries 2, 3, 4, 5 and the value returned is 1.
    472         * </p>
    473         *
    474         * @param value Value to be added to the array.
    475         * @return the value which has been discarded or "pushed" out of the array
    476         * by this rolling insert.
    477         */
    478        public synchronized double addElementRolling(double value) {
    479            double discarded = internalArray[startIndex];
    480
    481            if ((startIndex + (numElements + 1)) > internalArray.length) {
    482                expand();
    483            }
    484            // Increment the start index
    485            startIndex += 1;
    486
    487            // Add the new value
    488            internalArray[startIndex + (numElements - 1)] = value;
    489
    490            // Check the contraction criterion.
    491            if (shouldContract()) {
    492                contract();
    493            }
    494            return discarded;
    495        }
    496
    497        /**
    498         * Substitutes <code>value</code> for the most recently added value.
    499         * Returns the value that has been replaced. If the array is empty (i.e.
    500         * if {@link #numElements} is zero), an IllegalStateException is thrown.
    501         *
    502         * @param value New value to substitute for the most recently added value
    503         * @return the value that has been replaced in the array.
    504         * @throws MathIllegalStateException if the array is empty
    505         * @since 2.0
    506         */
    507        public synchronized double substituteMostRecentElement(double value)
    508            throws MathIllegalStateException {
    509            if (numElements < 1) {
    510                throw new MathIllegalStateException(
    511                        LocalizedFormats.CANNOT_SUBSTITUTE_ELEMENT_FROM_EMPTY_ARRAY);
    512            }
    513
    514            final int substIndex = startIndex + (numElements - 1);
    515            final double discarded = internalArray[substIndex];
    516
    517            internalArray[substIndex] = value;
    518
    519            return discarded;
    520        }
    521
    522        /**
    523         * Checks the expansion factor and the contraction criterion and throws an
    524         * IllegalArgumentException if the contractionCriteria is less than the
    525         * expansionCriteria
    526         *
    527         * @param expansion factor to be checked
    528         * @param contraction criteria to be checked
    529         * @throws MathIllegalArgumentException if the contractionCriteria is less than
    530         * the expansionCriteria.
    531         * @deprecated As of 3.1. Please use
    532         * {@link #checkContractExpand(double,double)} instead.
    533         */
    534        protected void checkContractExpand(float contraction, float expansion)
    535            throws MathIllegalArgumentException {
    536            checkContractExpand((double) contraction,
    537                                (double) expansion);
    538        }
    539
    540        /**
    541         * Checks the expansion factor and the contraction criterion and raises
    542         * an exception if the contraction criterion is smaller than the
    543         * expansion criterion.
    544         *
    545         * @param contraction Criterion to be checked.
    546         * @param expansion Factor to be checked.
    547         * @throws NumberIsTooSmallException if {@code contraction < expansion}.
    548         * @throws NumberIsTooSmallException if {@code contraction <= 1}.
    549         * @throws NumberIsTooSmallException if {@code expansion <= 1 }.
    550         * @since 3.1
    551         */
    552        protected void checkContractExpand(double contraction,
    553                                           double expansion)
    554            throws NumberIsTooSmallException {
    555            if (contraction < expansion) {
    556                final NumberIsTooSmallException e = new NumberIsTooSmallException(contraction, 1, true);
    557                e.getContext().addMessage(LocalizedFormats.CONTRACTION_CRITERIA_SMALLER_THAN_EXPANSION_FACTOR,
    558                                          contraction, expansion);
    559                throw e;
    560            }
    561
    562            if (contraction <= 1) {
    563                final NumberIsTooSmallException e = new NumberIsTooSmallException(contraction, 1, false);
    564                e.getContext().addMessage(LocalizedFormats.CONTRACTION_CRITERIA_SMALLER_THAN_ONE,
    565                                          contraction);
    566                throw e;
    567            }
    568
    569            if (expansion <= 1) {
    570                final NumberIsTooSmallException e = new NumberIsTooSmallException(contraction, 1, false);
    571                e.getContext().addMessage(LocalizedFormats.EXPANSION_FACTOR_SMALLER_THAN_ONE,
    572                                          expansion);
    573                throw e;
    574            }
    575        }
    576
    577        /**
    578         * Clear the array contents, resetting the number of elements to zero.
    579         */
    580        public synchronized void clear() {
    581            numElements = 0;
    582            startIndex = 0;
    583        }
    584
    585        /**
    586         * Contracts the storage array to the (size of the element set) + 1 - to
    587         * avoid a zero length array. This function also resets the startIndex to
    588         * zero.
    589         */
    590        public synchronized void contract() {
    591            final double[] tempArray = new double[numElements + 1];
    592
    593            // Copy and swap - copy only the element array from the src array.
    594            System.arraycopy(internalArray, startIndex, tempArray, 0, numElements);
    595            internalArray = tempArray;
    596
    597            // Reset the start index to zero
    598            startIndex = 0;
    599        }
    600
    601        /**
    602         * Discards the <code>i</code> initial elements of the array.  For example,
    603         * if the array contains the elements 1,2,3,4, invoking
    604         * <code>discardFrontElements(2)</code> will cause the first two elements
    605         * to be discarded, leaving 3,4 in the array.  Throws illegalArgumentException
    606         * if i exceeds numElements.
    607         *
    608         * @param i  the number of elements to discard from the front of the array
    609         * @throws MathIllegalArgumentException if i is greater than numElements.
    610         * @since 2.0
    611         */
    612        public synchronized void discardFrontElements(int i)
    613            throws MathIllegalArgumentException {
    614            discardExtremeElements(i,true);
    615        }
    616
    617        /**
    618         * Discards the <code>i</code> last elements of the array.  For example,
    619         * if the array contains the elements 1,2,3,4, invoking
    620         * <code>discardMostRecentElements(2)</code> will cause the last two elements
    621         * to be discarded, leaving 1,2 in the array.  Throws illegalArgumentException
    622         * if i exceeds numElements.
    623         *
    624         * @param i  the number of elements to discard from the end of the array
    625         * @throws MathIllegalArgumentException if i is greater than numElements.
    626         * @since 2.0
    627         */
    628        public synchronized void discardMostRecentElements(int i)
    629            throws MathIllegalArgumentException {
    630            discardExtremeElements(i,false);
    631        }
    632
    633        /**
    634         * Discards the <code>i</code> first or last elements of the array,
    635         * depending on the value of <code>front</code>.
    636         * For example, if the array contains the elements 1,2,3,4, invoking
    637         * <code>discardExtremeElements(2,false)</code> will cause the last two elements
    638         * to be discarded, leaving 1,2 in the array.
    639         * For example, if the array contains the elements 1,2,3,4, invoking
    640         * <code>discardExtremeElements(2,true)</code> will cause the first two elements
    641         * to be discarded, leaving 3,4 in the array.
    642         * Throws illegalArgumentException
    643         * if i exceeds numElements.
    644         *
    645         * @param i  the number of elements to discard from the front/end of the array
    646         * @param front true if elements are to be discarded from the front
    647         * of the array, false if elements are to be discarded from the end
    648         * of the array
    649         * @throws MathIllegalArgumentException if i is greater than numElements.
    650         * @since 2.0
    651         */
    652        private synchronized void discardExtremeElements(int i,
    653                                                         boolean front)
    654            throws MathIllegalArgumentException {
    655            if (i > numElements) {
    656                throw new MathIllegalArgumentException(
    657                        LocalizedFormats.TOO_MANY_ELEMENTS_TO_DISCARD_FROM_ARRAY,
    658                        i, numElements);
    659           } else if (i < 0) {
    660               throw new MathIllegalArgumentException(
    661                       LocalizedFormats.CANNOT_DISCARD_NEGATIVE_NUMBER_OF_ELEMENTS,
    662                       i);
    663            } else {
    664                // "Subtract" this number of discarded from numElements
    665                numElements -= i;
    666                if (front) {
    667                    startIndex += i;
    668                }
    669            }
    670            if (shouldContract()) {
    671                contract();
    672            }
    673        }
    674
    675        /**
    676         * Expands the internal storage array using the expansion factor.
    677         * <p>
    678         * if <code>expansionMode</code> is set to MULTIPLICATIVE_MODE,
    679         * the new array size will be <code>internalArray.length * expansionFactor.</code>
    680         * If <code>expansionMode</code> is set to ADDITIVE_MODE,  the length
    681         * after expansion will be <code>internalArray.length + expansionFactor</code>
    682         * </p>
    683         */
    684        protected synchronized void expand() {
    685            // notice the use of FastMath.ceil(), this guarantees that we will always
    686            // have an array of at least currentSize + 1.   Assume that the
    687            // current initial capacity is 1 and the expansion factor
    688            // is 1.000000000000000001.  The newly calculated size will be
    689            // rounded up to 2 after the multiplication is performed.
    690            int newSize = 0;
    691            if (expansionMode == ExpansionMode.MULTIPLICATIVE) {
    692                newSize = (int) FastMath.ceil(internalArray.length * expansionFactor);
    693            } else {
    694                newSize = (int) (internalArray.length + FastMath.round(expansionFactor));
    695            }
    696            final double[] tempArray = new double[newSize];
    697
    698            // Copy and swap
    699            System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
    700            internalArray = tempArray;
    701        }
    702
    703        /**
    704         * Expands the internal storage array to the specified size.
    705         *
    706         * @param size Size of the new internal storage array.
    707         */
    708        private synchronized void expandTo(int size) {
    709            final double[] tempArray = new double[size];
    710            // Copy and swap
    711            System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
    712            internalArray = tempArray;
    713        }
    714
    715        /**
    716         * The contraction criteria defines when the internal array will contract
    717         * to store only the number of elements in the element array.
    718         * If  the <code>expansionMode</code> is <code>MULTIPLICATIVE_MODE</code>,
    719         * contraction is triggered when the ratio between storage array length
    720         * and <code>numElements</code> exceeds <code>contractionFactor</code>.
    721         * If the <code>expansionMode</code> is <code>ADDITIVE_MODE</code>, the
    722         * number of excess storage locations is compared to
    723         * <code>contractionFactor.</code>
    724         *
    725         * @return the contraction criteria used to reclaim memory.
    726         * @deprecated As of 3.1. Please use {@link #getContractionCriterion()}
    727         * instead.
    728         */
    729        @Deprecated
    730        public float getContractionCriteria() {
    731            return (float) getContractionCriterion();
    732        }
    733
    734        /**
    735         * The contraction criterion defines when the internal array will contract
    736         * to store only the number of elements in the element array.
    737         * If  the <code>expansionMode</code> is <code>MULTIPLICATIVE_MODE</code>,
    738         * contraction is triggered when the ratio between storage array length
    739         * and <code>numElements</code> exceeds <code>contractionFactor</code>.
    740         * If the <code>expansionMode</code> is <code>ADDITIVE_MODE</code>, the
    741         * number of excess storage locations is compared to
    742         * <code>contractionFactor.</code>
    743         *
    744         * @return the contraction criterion used to reclaim memory.
    745         * @since 3.1
    746         */
    747        public double getContractionCriterion() {
    748            return contractionCriterion;
    749        }
    750
    751        /**
    752         * Returns the element at the specified index
    753         *
    754         * @param index index to fetch a value from
    755         * @return value stored at the specified index
    756         * @throws ArrayIndexOutOfBoundsException if <code>index</code> is less than
    757         * zero or is greater than <code>getNumElements() - 1</code>.
    758         */
    759        public synchronized double getElement(int index) {
    760            if (index >= numElements) {
    761                throw new ArrayIndexOutOfBoundsException(index);
    762            } else if (index >= 0) {
    763                return internalArray[startIndex + index];
    764            } else {
    765                throw new ArrayIndexOutOfBoundsException(index);
    766            }
    767        }
    768
    769         /**
    770         * Returns a double array containing the elements of this
    771         * <code>ResizableArray</code>.  This method returns a copy, not a
    772         * reference to the underlying array, so that changes made to the returned
    773         *  array have no effect on this <code>ResizableArray.</code>
    774         * @return the double array.
    775         */
    776        public synchronized double[] getElements() {
    777            final double[] elementArray = new double[numElements];
    778            System.arraycopy(internalArray, startIndex, elementArray, 0, numElements);
    779            return elementArray;
    780        }
    781
    782        /**
    783         * The expansion factor controls the size of a new array when an array
    784         * needs to be expanded.  The <code>expansionMode</code>
    785         * determines whether the size of the array is multiplied by the
    786         * <code>expansionFactor</code> (MULTIPLICATIVE_MODE) or if
    787         * the expansion is additive (ADDITIVE_MODE -- <code>expansionFactor</code>
    788         * storage locations added).  The default <code>expansionMode</code> is
    789         * MULTIPLICATIVE_MODE and the default <code>expansionFactor</code>
    790         * is 2.0.
    791         *
    792         * @return the expansion factor of this expandable double array
    793         * @deprecated As of 3.1. Return type will be changed to "double" in 4.0.
    794         */
    795        @Deprecated
    796        public float getExpansionFactor() {
    797            return (float) expansionFactor;
    798        }
    799
    800        /**
    801         * The expansion mode determines whether the internal storage
    802         * array grows additively or multiplicatively when it is expanded.
    803         *
    804         * @return the expansion mode.
    805         * @deprecated As of 3.1. Return value to be changed to
    806         * {@link ExpansionMode} in 4.0.
    807         */
    808        public int getExpansionMode() {
    809            switch (expansionMode) {
    810            case MULTIPLICATIVE:
    811                return MULTIPLICATIVE_MODE;
    812            case ADDITIVE:
    813                return ADDITIVE_MODE;
    814            default:
    815                throw new MathInternalError(); // Should never happen.
    816            }
    817        }
    818
    819        /**
    820         * Notice the package scope on this method.   This method is simply here
    821         * for the JUnit test, it allows us check if the expansion is working
    822         * properly after a number of expansions.  This is not meant to be a part
    823         * of the public interface of this class.
    824         *
    825         * @return the length of the internal storage array.
    826         * @deprecated As of 3.1. Please use {@link #getCapacity()} instead.
    827         */
    828        @Deprecated
    829        synchronized int getInternalLength() {
    830            return internalArray.length;
    831        }
    832
    833        /**
    834         * Gets the currently allocated size of the internal data structure used
    835         * for storing elements.
    836         * This is not to be confused with {@link #getNumElements() the number of
    837         * elements actually stored}.
    838         *
    839         * @return the length of the internal array.
    840         * @since 3.1
    841         */
    842        public int getCapacity() {
    843            return internalArray.length;
    844        }
    845
    846        /**
    847         * Returns the number of elements currently in the array.  Please note
    848         * that this is different from the length of the internal storage array.
    849         *
    850         * @return the number of elements.
    851         */
    852        public synchronized int getNumElements() {
    853            return numElements;
    854        }
    855
    856        /**
    857         * Returns the internal storage array.  Note that this method returns
    858         * a reference to the internal storage array, not a copy, and to correctly
    859         * address elements of the array, the <code>startIndex</code> is
    860         * required (available via the {@link #start} method).  This method should
    861         * only be used in cases where copying the internal array is not practical.
    862         * The {@link #getElements} method should be used in all other cases.
    863         *
    864         *
    865         * @return the internal storage array used by this object
    866         * @since 2.0
    867         * @deprecated As of 3.1.
    868         */
    869        @Deprecated
    870        public synchronized double[] getInternalValues() {
    871            return internalArray;
    872        }
    873
    874        /**
    875         * Provides <em>direct</em> access to the internal storage array.
    876         * Please note that this method returns a reference to this object's
    877         * storage array, not a copy.
    878         * <br/>
    879         * To correctly address elements of the array, the "start index" is
    880         * required (available via the {@link #getStartIndex() getStartIndex}
    881         * method.
    882         * <br/>
    883         * This method should only be used to avoid copying the internal array.
    884         * The returned value <em>must</em> be used for reading only; other
    885         * uses could lead to this object becoming inconsistent.
    886         * <br/>
    887         * The {@link #getElements} method has no such limitation since it
    888         * returns a copy of this array's addressable elements.
    889         *
    890         * @return the internal storage array used by this object.
    891         * @since 3.1
    892         */
    893        protected double[] getArrayRef() {
    894            return internalArray;
    895        }
    896
    897        /**
    898         * Returns the "start index" of the internal array.
    899         * This index is the position of the first addressable element in the
    900         * internal storage array.
    901         * The addressable elements in the array are at indices contained in
    902         * the interval [{@link #getStartIndex()},
    903         *               {@link #getStartIndex()} + {@link #getNumElements()} - 1].
    904         *
    905         * @return the start index.
    906         * @since 3.1
    907         */
    908        protected int getStartIndex() {
    909            return startIndex;
    910        }
    911
    912        /**
    913         * Sets the contraction criteria.
    914         *
    915         * @param contractionCriteria contraction criteria
    916         * @throws MathIllegalArgumentException if the contractionCriteria is less than
    917         *         the expansionCriteria.
    918         * @deprecated As of 3.1 (to be removed in 4.0 as field will become "final").
    919         */
    920        @Deprecated
    921        public void setContractionCriteria(float contractionCriteria)
    922            throws MathIllegalArgumentException {
    923            checkContractExpand(contractionCriteria, getExpansionFactor());
    924            synchronized(this) {
    925                this.contractionCriterion = contractionCriteria;
    926            }
    927        }
    928
    929        /**
    930         * Performs an operation on the addressable elements of the array.
    931         *
    932         * @param f Function to be applied on this array.
    933         * @return the result.
    934         * @since 3.1
    935         */
    936        public double compute(MathArrays.Function f) {
    937            return f.evaluate(internalArray, startIndex, numElements);
    938        }
    939
    940        /**
    941         * Sets the element at the specified index.  If the specified index is greater than
    942         * <code>getNumElements() - 1</code>, the <code>numElements</code> property
    943         * is increased to <code>index +1</code> and additional storage is allocated
    944         * (if necessary) for the new element and all  (uninitialized) elements
    945         * between the new element and the previous end of the array).
    946         *
    947         * @param index index to store a value in
    948         * @param value value to store at the specified index
    949         * @throws ArrayIndexOutOfBoundsException if {@code index < 0}.
    950         */
    951        public synchronized void setElement(int index, double value) {
    952            if (index < 0) {
    953                throw new ArrayIndexOutOfBoundsException(index);
    954            }
    955            if (index + 1 > numElements) {
    956                numElements = index + 1;
    957            }
    958            if ((startIndex + index) >= internalArray.length) {
    959                expandTo(startIndex + (index + 1));
    960            }
    961            internalArray[startIndex + index] = value;
    962        }
    963
    964        /**
    965         * Sets the expansionFactor.  Throws IllegalArgumentException if the
    966         * the following conditions are not met:
    967         * <ul>
    968         * <li><code>expansionFactor > 1</code></li>
    969         * <li><code>contractionFactor >= expansionFactor</code></li>
    970         * </ul>
    971         * @param expansionFactor the new expansion factor value.
    972         * @throws MathIllegalArgumentException if expansionFactor is <= 1 or greater
    973         * than contractionFactor
    974         * @deprecated As of 3.1 (to be removed in 4.0 as field will become "final").
    975         */
    976        @Deprecated
    977        public void setExpansionFactor(float expansionFactor) throws MathIllegalArgumentException {
    978            checkContractExpand(getContractionCriterion(), expansionFactor);
    979            // The check above verifies that the expansion factor is > 1.0;
    980            synchronized(this) {
    981                this.expansionFactor = expansionFactor;
    982            }
    983        }
    984
    985        /**
    986         * Sets the <code>expansionMode</code>. The specified value must be one of
    987         * ADDITIVE_MODE, MULTIPLICATIVE_MODE.
    988         *
    989         * @param expansionMode The expansionMode to set.
    990         * @throws MathIllegalArgumentException if the specified mode value is not valid.
    991         * @deprecated As of 3.1. Please use {@link #setExpansionMode(ExpansionMode)} instead.
    992         */
    993        @Deprecated
    994        public void setExpansionMode(int expansionMode)
    995            throws MathIllegalArgumentException {
    996            if (expansionMode != MULTIPLICATIVE_MODE &&
    997                expansionMode != ADDITIVE_MODE) {
    998                throw new MathIllegalArgumentException(LocalizedFormats.UNSUPPORTED_EXPANSION_MODE, expansionMode,
    999                                                       MULTIPLICATIVE_MODE, "MULTIPLICATIVE_MODE",
    1000                                                       ADDITIVE_MODE, "ADDITIVE_MODE");
    1001            }
    1002            synchronized(this) {
    1003                if (expansionMode == MULTIPLICATIVE_MODE) {
    1004                    setExpansionMode(ExpansionMode.MULTIPLICATIVE);
    1005                } else if (expansionMode == ADDITIVE_MODE) {
    1006                    setExpansionMode(ExpansionMode.ADDITIVE);
    1007                }
    1008            }
    1009        }
    1010
    1011        /**
    1012         * Sets the {@link ExpansionMode expansion mode}.
    1013         *
    1014         * @param expansionMode Expansion mode to use for resizing the array.
    1015         * @deprecated As of 3.1 (to be removed in 4.0 as field will become "final").
    1016         */
    1017        @Deprecated
    1018        public void setExpansionMode(ExpansionMode expansionMode) {
    1019            this.expansionMode = expansionMode;
    1020        }
    1021
    1022        /**
    1023         * Sets the initial capacity.  Should only be invoked by constructors.
    1024         *
    1025         * @param initialCapacity of the array
    1026         * @throws MathIllegalArgumentException if <code>initialCapacity</code> is not
    1027         * positive.
    1028         * @deprecated As of 3.1, this is a no-op.
    1029         */
    1030        @Deprecated
    1031        protected void setInitialCapacity(int initialCapacity)
    1032            throws MathIllegalArgumentException {
    1033            // Body removed in 3.1.
    1034        }
    1035
    1036        /**
    1037         * This function allows you to control the number of elements contained
    1038         * in this array, and can be used to "throw out" the last n values in an
    1039         * array. This function will also expand the internal array as needed.
    1040         *
    1041         * @param i a new number of elements
    1042         * @throws MathIllegalArgumentException if <code>i</code> is negative.
    1043         */
    1044        public synchronized void setNumElements(int i)
    1045            throws MathIllegalArgumentException {
    1046            // If index is negative thrown an error.
    1047            if (i < 0) {
    1048                throw new MathIllegalArgumentException(
    1049                        LocalizedFormats.INDEX_NOT_POSITIVE,
    1050                        i);
    1051            }
    1052
    1053            // Test the new num elements, check to see if the array needs to be
    1054            // expanded to accommodate this new number of elements.
    1055            final int newSize = startIndex + i;
    1056            if (newSize > internalArray.length) {
    1057                expandTo(newSize);
    1058            }
    1059
    1060            // Set the new number of elements to new value.
    1061            numElements = i;
    1062        }
    1063
    1064        /**
    1065         * Returns true if the internal storage array has too many unused
    1066         * storage positions.
    1067         *
    1068         * @return true if array satisfies the contraction criteria
    1069         */
    1070        private synchronized boolean shouldContract() {
    1071            if (expansionMode == ExpansionMode.MULTIPLICATIVE) {
    1072                return (internalArray.length / ((float) numElements)) > contractionCriterion;
    1073            } else {
    1074                return (internalArray.length - numElements) > contractionCriterion;
    1075            }
    1076        }
    1077
    1078        /**
    1079         * Returns the starting index of the internal array.  The starting index is
    1080         * the position of the first addressable element in the internal storage
    1081         * array.  The addressable elements in the array are <code>
    1082         * internalArray[startIndex],...,internalArray[startIndex + numElements -1]
    1083         * </code>
    1084         *
    1085         * @return the starting index.
    1086         * @deprecated As of 3.1.
    1087         */
    1088        @Deprecated
    1089        public synchronized int start() {
    1090            return startIndex;
    1091        }
    1092
    1093        /**
    1094         * <p>Copies source to dest, copying the underlying data, so dest is
    1095         * a new, independent copy of source.  Does not contract before
    1096         * the copy.</p>
    1097         *
    1098         * <p>Obtains synchronization locks on both source and dest
    1099         * (in that order) before performing the copy.</p>
    1100         *
    1101         * <p>Neither source nor dest may be null; otherwise a {@link NullArgumentException}
    1102         * is thrown</p>
    1103         *
    1104         * @param source ResizableDoubleArray to copy
    1105         * @param dest ResizableArray to replace with a copy of the source array
    1106         * @exception NullArgumentException if either source or dest is null
    1107         * @since 2.0
    1108         *
    1109         */
    1110        public static void copy(ResizableDoubleArray source,
    1111                                ResizableDoubleArray dest)
    1112            throws NullArgumentException {
    1113            MathUtils.checkNotNull(source);
    1114            MathUtils.checkNotNull(dest);
    1115            synchronized(source) {
    1116               synchronized(dest) {
    1117                   dest.contractionCriterion = source.contractionCriterion;
    1118                   dest.expansionFactor = source.expansionFactor;
    1119                   dest.expansionMode = source.expansionMode;
    1120                   dest.internalArray = new double[source.internalArray.length];
    1121                   System.arraycopy(source.internalArray, 0, dest.internalArray,
    1122                           0, dest.internalArray.length);
    1123                   dest.numElements = source.numElements;
    1124                   dest.startIndex = source.startIndex;
    1125               }
    1126           }
    1127        }
    1128
    1129        /**
    1130         * Returns a copy of the ResizableDoubleArray.  Does not contract before
    1131         * the copy, so the returned object is an exact copy of this.
    1132         *
    1133         * @return a new ResizableDoubleArray with the same data and configuration
    1134         * properties as this
    1135         * @since 2.0
    1136         */
    1137        public synchronized ResizableDoubleArray copy() {
    1138            final ResizableDoubleArray result = new ResizableDoubleArray();
    1139            copy(this, result);
    1140            return result;
    1141        }
    1142
    1143        /**
    1144         * Returns true iff object is a ResizableDoubleArray with the same properties
    1145         * as this and an identical internal storage array.
    1146         *
    1147         * @param object object to be compared for equality with this
    1148         * @return true iff object is a ResizableDoubleArray with the same data and
    1149         * properties as this
    1150         * @since 2.0
    1151         */
    1152        @Override
    1153        public boolean equals(Object object) {
    1154            if (object == this ) {
    1155                return true;
    1156            }
    1157            if (object instanceof ResizableDoubleArray == false) {
    1158                return false;
    1159            }
    1160            synchronized(this) {
    1161                synchronized(object) {
    1162                    boolean result = true;
    1163                    final ResizableDoubleArray other = (ResizableDoubleArray) object;
    1164                    result = result && (other.contractionCriterion == contractionCriterion);
    1165                    result = result && (other.expansionFactor == expansionFactor);
    1166                    result = result && (other.expansionMode == expansionMode);
    1167                    result = result && (other.numElements == numElements);
    1168                    result = result && (other.startIndex == startIndex);
    1169                    if (!result) {
    1170                        return false;
    1171                    } else {
    1172                        return Arrays.equals(internalArray, other.internalArray);
    1173                    }
    1174                }
    1175            }
    1176        }
    1177
    1178        /**
    1179         * Returns a hash code consistent with equals.
    1180         *
    1181         * @return the hash code representing this {@code ResizableDoubleArray}.
    1182         * @since 2.0
    1183         */
    1184        @Override
    1185        public synchronized int hashCode() {
    1186            final int[] hashData = new int[6];
    1187            hashData[0] = Double.valueOf(expansionFactor).hashCode();
    1188            hashData[1] = Double.valueOf(contractionCriterion).hashCode();
    1189            hashData[2] = expansionMode.hashCode();
    1190            hashData[3] = Arrays.hashCode(internalArray);
    1191            hashData[4] = numElements;
    1192            hashData[5] = startIndex;
    1193            return Arrays.hashCode(hashData);
    1194        }
    1195
    1196    }