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    }