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 */
017package org.apache.commons.math3.util;
018
019import java.io.Serializable;
020import java.util.Arrays;
021
022import org.apache.commons.math3.exception.MathIllegalArgumentException;
023import org.apache.commons.math3.exception.MathIllegalStateException;
024import org.apache.commons.math3.exception.MathInternalError;
025import org.apache.commons.math3.exception.NullArgumentException;
026import org.apache.commons.math3.exception.NotStrictlyPositiveException;
027import org.apache.commons.math3.exception.NumberIsTooSmallException;
028import 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 1499808 2013-07-04 17:00:42Z sebb $
083 */
084public 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    @Deprecated
363    public ResizableDoubleArray(int initialCapacity, float expansionFactor,
364            float contractionCriteria, int expansionMode) throws MathIllegalArgumentException {
365        this(initialCapacity,
366             expansionFactor,
367             contractionCriteria,
368             expansionMode == ADDITIVE_MODE ?
369             ExpansionMode.ADDITIVE :
370             ExpansionMode.MULTIPLICATIVE,
371             null);
372        // XXX Just ot retain the expected failure in a unit test.
373        // With the new "enum", that test will become obsolete.
374        setExpansionMode(expansionMode);
375    }
376
377    /**
378     * Creates an instance with the specified properties.
379     * <br/>
380     * Throws MathIllegalArgumentException if the following conditions are
381     * not met:
382     * <ul>
383     *  <li>{@code initialCapacity > 0}</li>
384     *  <li>{@code expansionFactor > 1}</li>
385     *  <li>{@code contractionCriterion >= expansionFactor}</li>
386     * </ul>
387     *
388     * @param initialCapacity Initial size of the internal storage array.
389     * @param expansionFactor The array will be expanded based on this
390     * parameter.
391     * @param contractionCriterion Contraction criteria.
392     * @param expansionMode Expansion mode.
393     * @param data Initial contents of the array.
394     * @throws MathIllegalArgumentException if the parameters are not valid.
395     */
396    public ResizableDoubleArray(int initialCapacity,
397                                double expansionFactor,
398                                double contractionCriterion,
399                                ExpansionMode expansionMode,
400                                double ... data)
401        throws MathIllegalArgumentException {
402        if (initialCapacity <= 0) {
403            throw new NotStrictlyPositiveException(LocalizedFormats.INITIAL_CAPACITY_NOT_POSITIVE,
404                                                   initialCapacity);
405        }
406        checkContractExpand(contractionCriterion, expansionFactor);
407
408        this.expansionFactor = expansionFactor;
409        this.contractionCriterion = contractionCriterion;
410        this.expansionMode = expansionMode;
411        internalArray = new double[initialCapacity];
412        numElements = 0;
413        startIndex = 0;
414
415        if (data != null) {
416            addElements(data);
417        }
418    }
419
420    /**
421     * Copy constructor.  Creates a new ResizableDoubleArray that is a deep,
422     * fresh copy of the original. Needs to acquire synchronization lock
423     * on original.  Original may not be null; otherwise a {@link NullArgumentException}
424     * is thrown.
425     *
426     * @param original array to copy
427     * @exception NullArgumentException if original is null
428     * @since 2.0
429     */
430    public ResizableDoubleArray(ResizableDoubleArray original)
431        throws NullArgumentException {
432        MathUtils.checkNotNull(original);
433        copy(original, this);
434    }
435
436    /**
437     * Adds an element to the end of this expandable array.
438     *
439     * @param value Value to be added to end of array.
440     */
441    public synchronized void addElement(double value) {
442        if (internalArray.length <= startIndex + numElements) {
443            expand();
444        }
445        internalArray[startIndex + numElements++] = value;
446    }
447
448    /**
449     * Adds several element to the end of this expandable array.
450     *
451     * @param values Values to be added to end of array.
452     * @since 2.2
453     */
454    public synchronized void addElements(double[] values) {
455        final double[] tempArray = new double[numElements + values.length + 1];
456        System.arraycopy(internalArray, startIndex, tempArray, 0, numElements);
457        System.arraycopy(values, 0, tempArray, numElements, values.length);
458        internalArray = tempArray;
459        startIndex = 0;
460        numElements += values.length;
461    }
462
463    /**
464     * <p>
465     * Adds an element to the end of the array and removes the first
466     * element in the array.  Returns the discarded first element.
467     * The effect is similar to a push operation in a FIFO queue.
468     * </p>
469     * <p>
470     * Example: If the array contains the elements 1, 2, 3, 4 (in that order)
471     * and addElementRolling(5) is invoked, the result is an array containing
472     * the entries 2, 3, 4, 5 and the value returned is 1.
473     * </p>
474     *
475     * @param value Value to be added to the array.
476     * @return the value which has been discarded or "pushed" out of the array
477     * by this rolling insert.
478     */
479    public synchronized double addElementRolling(double value) {
480        double discarded = internalArray[startIndex];
481
482        if ((startIndex + (numElements + 1)) > internalArray.length) {
483            expand();
484        }
485        // Increment the start index
486        startIndex += 1;
487
488        // Add the new value
489        internalArray[startIndex + (numElements - 1)] = value;
490
491        // Check the contraction criterion.
492        if (shouldContract()) {
493            contract();
494        }
495        return discarded;
496    }
497
498    /**
499     * Substitutes <code>value</code> for the most recently added value.
500     * Returns the value that has been replaced. If the array is empty (i.e.
501     * if {@link #numElements} is zero), an IllegalStateException is thrown.
502     *
503     * @param value New value to substitute for the most recently added value
504     * @return the value that has been replaced in the array.
505     * @throws MathIllegalStateException if the array is empty
506     * @since 2.0
507     */
508    public synchronized double substituteMostRecentElement(double value)
509        throws MathIllegalStateException {
510        if (numElements < 1) {
511            throw new MathIllegalStateException(
512                    LocalizedFormats.CANNOT_SUBSTITUTE_ELEMENT_FROM_EMPTY_ARRAY);
513        }
514
515        final int substIndex = startIndex + (numElements - 1);
516        final double discarded = internalArray[substIndex];
517
518        internalArray[substIndex] = value;
519
520        return discarded;
521    }
522
523    /**
524     * Checks the expansion factor and the contraction criterion and throws an
525     * IllegalArgumentException if the contractionCriteria is less than the
526     * expansionCriteria
527     *
528     * @param expansion factor to be checked
529     * @param contraction criteria to be checked
530     * @throws MathIllegalArgumentException if the contractionCriteria is less than
531     * the expansionCriteria.
532     * @deprecated As of 3.1. Please use
533     * {@link #checkContractExpand(double,double)} instead.
534     */
535    @Deprecated
536    protected void checkContractExpand(float contraction, float expansion)
537        throws MathIllegalArgumentException {
538        checkContractExpand((double) contraction,
539                            (double) expansion);
540    }
541
542    /**
543     * Checks the expansion factor and the contraction criterion and raises
544     * an exception if the contraction criterion is smaller than the
545     * expansion criterion.
546     *
547     * @param contraction Criterion to be checked.
548     * @param expansion Factor to be checked.
549     * @throws NumberIsTooSmallException if {@code contraction < expansion}.
550     * @throws NumberIsTooSmallException if {@code contraction <= 1}.
551     * @throws NumberIsTooSmallException if {@code expansion <= 1 }.
552     * @since 3.1
553     */
554    protected void checkContractExpand(double contraction,
555                                       double expansion)
556        throws NumberIsTooSmallException {
557        if (contraction < expansion) {
558            final NumberIsTooSmallException e = new NumberIsTooSmallException(contraction, 1, true);
559            e.getContext().addMessage(LocalizedFormats.CONTRACTION_CRITERIA_SMALLER_THAN_EXPANSION_FACTOR,
560                                      contraction, expansion);
561            throw e;
562        }
563
564        if (contraction <= 1) {
565            final NumberIsTooSmallException e = new NumberIsTooSmallException(contraction, 1, false);
566            e.getContext().addMessage(LocalizedFormats.CONTRACTION_CRITERIA_SMALLER_THAN_ONE,
567                                      contraction);
568            throw e;
569        }
570
571        if (expansion <= 1) {
572            final NumberIsTooSmallException e = new NumberIsTooSmallException(contraction, 1, false);
573            e.getContext().addMessage(LocalizedFormats.EXPANSION_FACTOR_SMALLER_THAN_ONE,
574                                      expansion);
575            throw e;
576        }
577    }
578
579    /**
580     * Clear the array contents, resetting the number of elements to zero.
581     */
582    public synchronized void clear() {
583        numElements = 0;
584        startIndex = 0;
585    }
586
587    /**
588     * Contracts the storage array to the (size of the element set) + 1 - to
589     * avoid a zero length array. This function also resets the startIndex to
590     * zero.
591     */
592    public synchronized void contract() {
593        final double[] tempArray = new double[numElements + 1];
594
595        // Copy and swap - copy only the element array from the src array.
596        System.arraycopy(internalArray, startIndex, tempArray, 0, numElements);
597        internalArray = tempArray;
598
599        // Reset the start index to zero
600        startIndex = 0;
601    }
602
603    /**
604     * Discards the <code>i</code> initial elements of the array.  For example,
605     * if the array contains the elements 1,2,3,4, invoking
606     * <code>discardFrontElements(2)</code> will cause the first two elements
607     * to be discarded, leaving 3,4 in the array.  Throws illegalArgumentException
608     * if i exceeds numElements.
609     *
610     * @param i  the number of elements to discard from the front of the array
611     * @throws MathIllegalArgumentException if i is greater than numElements.
612     * @since 2.0
613     */
614    public synchronized void discardFrontElements(int i)
615        throws MathIllegalArgumentException {
616        discardExtremeElements(i,true);
617    }
618
619    /**
620     * Discards the <code>i</code> last elements of the array.  For example,
621     * if the array contains the elements 1,2,3,4, invoking
622     * <code>discardMostRecentElements(2)</code> will cause the last two elements
623     * to be discarded, leaving 1,2 in the array.  Throws illegalArgumentException
624     * if i exceeds numElements.
625     *
626     * @param i  the number of elements to discard from the end of the array
627     * @throws MathIllegalArgumentException if i is greater than numElements.
628     * @since 2.0
629     */
630    public synchronized void discardMostRecentElements(int i)
631        throws MathIllegalArgumentException {
632        discardExtremeElements(i,false);
633    }
634
635    /**
636     * Discards the <code>i</code> first or last elements of the array,
637     * depending on the value of <code>front</code>.
638     * For example, if the array contains the elements 1,2,3,4, invoking
639     * <code>discardExtremeElements(2,false)</code> will cause the last two elements
640     * to be discarded, leaving 1,2 in the array.
641     * For example, if the array contains the elements 1,2,3,4, invoking
642     * <code>discardExtremeElements(2,true)</code> will cause the first two elements
643     * to be discarded, leaving 3,4 in the array.
644     * Throws illegalArgumentException
645     * if i exceeds numElements.
646     *
647     * @param i  the number of elements to discard from the front/end of the array
648     * @param front true if elements are to be discarded from the front
649     * of the array, false if elements are to be discarded from the end
650     * of the array
651     * @throws MathIllegalArgumentException if i is greater than numElements.
652     * @since 2.0
653     */
654    private synchronized void discardExtremeElements(int i,
655                                                     boolean front)
656        throws MathIllegalArgumentException {
657        if (i > numElements) {
658            throw new MathIllegalArgumentException(
659                    LocalizedFormats.TOO_MANY_ELEMENTS_TO_DISCARD_FROM_ARRAY,
660                    i, numElements);
661       } else if (i < 0) {
662           throw new MathIllegalArgumentException(
663                   LocalizedFormats.CANNOT_DISCARD_NEGATIVE_NUMBER_OF_ELEMENTS,
664                   i);
665        } else {
666            // "Subtract" this number of discarded from numElements
667            numElements -= i;
668            if (front) {
669                startIndex += i;
670            }
671        }
672        if (shouldContract()) {
673            contract();
674        }
675    }
676
677    /**
678     * Expands the internal storage array using the expansion factor.
679     * <p>
680     * if <code>expansionMode</code> is set to MULTIPLICATIVE_MODE,
681     * the new array size will be <code>internalArray.length * expansionFactor.</code>
682     * If <code>expansionMode</code> is set to ADDITIVE_MODE,  the length
683     * after expansion will be <code>internalArray.length + expansionFactor</code>
684     * </p>
685     */
686    protected synchronized void expand() {
687        // notice the use of FastMath.ceil(), this guarantees that we will always
688        // have an array of at least currentSize + 1.   Assume that the
689        // current initial capacity is 1 and the expansion factor
690        // is 1.000000000000000001.  The newly calculated size will be
691        // rounded up to 2 after the multiplication is performed.
692        int newSize = 0;
693        if (expansionMode == ExpansionMode.MULTIPLICATIVE) {
694            newSize = (int) FastMath.ceil(internalArray.length * expansionFactor);
695        } else {
696            newSize = (int) (internalArray.length + FastMath.round(expansionFactor));
697        }
698        final double[] tempArray = new double[newSize];
699
700        // Copy and swap
701        System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
702        internalArray = tempArray;
703    }
704
705    /**
706     * Expands the internal storage array to the specified size.
707     *
708     * @param size Size of the new internal storage array.
709     */
710    private synchronized void expandTo(int size) {
711        final double[] tempArray = new double[size];
712        // Copy and swap
713        System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
714        internalArray = tempArray;
715    }
716
717    /**
718     * The contraction criteria defines when the internal array will contract
719     * to store only the number of elements in the element array.
720     * If  the <code>expansionMode</code> is <code>MULTIPLICATIVE_MODE</code>,
721     * contraction is triggered when the ratio between storage array length
722     * and <code>numElements</code> exceeds <code>contractionFactor</code>.
723     * If the <code>expansionMode</code> is <code>ADDITIVE_MODE</code>, the
724     * number of excess storage locations is compared to
725     * <code>contractionFactor.</code>
726     *
727     * @return the contraction criteria used to reclaim memory.
728     * @deprecated As of 3.1. Please use {@link #getContractionCriterion()}
729     * instead.
730     */
731    @Deprecated
732    public float getContractionCriteria() {
733        return (float) getContractionCriterion();
734    }
735
736    /**
737     * The contraction criterion defines when the internal array will contract
738     * to store only the number of elements in the element array.
739     * If  the <code>expansionMode</code> is <code>MULTIPLICATIVE_MODE</code>,
740     * contraction is triggered when the ratio between storage array length
741     * and <code>numElements</code> exceeds <code>contractionFactor</code>.
742     * If the <code>expansionMode</code> is <code>ADDITIVE_MODE</code>, the
743     * number of excess storage locations is compared to
744     * <code>contractionFactor.</code>
745     *
746     * @return the contraction criterion used to reclaim memory.
747     * @since 3.1
748     */
749    public double getContractionCriterion() {
750        return contractionCriterion;
751    }
752
753    /**
754     * Returns the element at the specified index
755     *
756     * @param index index to fetch a value from
757     * @return value stored at the specified index
758     * @throws ArrayIndexOutOfBoundsException if <code>index</code> is less than
759     * zero or is greater than <code>getNumElements() - 1</code>.
760     */
761    public synchronized double getElement(int index) {
762        if (index >= numElements) {
763            throw new ArrayIndexOutOfBoundsException(index);
764        } else if (index >= 0) {
765            return internalArray[startIndex + index];
766        } else {
767            throw new ArrayIndexOutOfBoundsException(index);
768        }
769    }
770
771     /**
772     * Returns a double array containing the elements of this
773     * <code>ResizableArray</code>.  This method returns a copy, not a
774     * reference to the underlying array, so that changes made to the returned
775     *  array have no effect on this <code>ResizableArray.</code>
776     * @return the double array.
777     */
778    public synchronized double[] getElements() {
779        final double[] elementArray = new double[numElements];
780        System.arraycopy(internalArray, startIndex, elementArray, 0, numElements);
781        return elementArray;
782    }
783
784    /**
785     * The expansion factor controls the size of a new array when an array
786     * needs to be expanded.  The <code>expansionMode</code>
787     * determines whether the size of the array is multiplied by the
788     * <code>expansionFactor</code> (MULTIPLICATIVE_MODE) or if
789     * the expansion is additive (ADDITIVE_MODE -- <code>expansionFactor</code>
790     * storage locations added).  The default <code>expansionMode</code> is
791     * MULTIPLICATIVE_MODE and the default <code>expansionFactor</code>
792     * is 2.0.
793     *
794     * @return the expansion factor of this expandable double array
795     * @deprecated As of 3.1. Return type will be changed to "double" in 4.0.
796     */
797    @Deprecated
798    public float getExpansionFactor() {
799        return (float) expansionFactor;
800    }
801
802    /**
803     * The expansion mode determines whether the internal storage
804     * array grows additively or multiplicatively when it is expanded.
805     *
806     * @return the expansion mode.
807     * @deprecated As of 3.1. Return value to be changed to
808     * {@link ExpansionMode} in 4.0.
809     */
810    @Deprecated
811    public int getExpansionMode() {
812        switch (expansionMode) {
813        case MULTIPLICATIVE:
814            return MULTIPLICATIVE_MODE;
815        case ADDITIVE:
816            return ADDITIVE_MODE;
817        default:
818            throw new MathInternalError(); // Should never happen.
819        }
820    }
821
822    /**
823     * Notice the package scope on this method.   This method is simply here
824     * for the JUnit test, it allows us check if the expansion is working
825     * properly after a number of expansions.  This is not meant to be a part
826     * of the public interface of this class.
827     *
828     * @return the length of the internal storage array.
829     * @deprecated As of 3.1. Please use {@link #getCapacity()} instead.
830     */
831    @Deprecated
832    synchronized int getInternalLength() {
833        return internalArray.length;
834    }
835
836    /**
837     * Gets the currently allocated size of the internal data structure used
838     * for storing elements.
839     * This is not to be confused with {@link #getNumElements() the number of
840     * elements actually stored}.
841     *
842     * @return the length of the internal array.
843     * @since 3.1
844     */
845    public int getCapacity() {
846        return internalArray.length;
847    }
848
849    /**
850     * Returns the number of elements currently in the array.  Please note
851     * that this is different from the length of the internal storage array.
852     *
853     * @return the number of elements.
854     */
855    public synchronized int getNumElements() {
856        return numElements;
857    }
858
859    /**
860     * Returns the internal storage array.  Note that this method returns
861     * a reference to the internal storage array, not a copy, and to correctly
862     * address elements of the array, the <code>startIndex</code> is
863     * required (available via the {@link #start} method).  This method should
864     * only be used in cases where copying the internal array is not practical.
865     * The {@link #getElements} method should be used in all other cases.
866     *
867     *
868     * @return the internal storage array used by this object
869     * @since 2.0
870     * @deprecated As of 3.1.
871     */
872    @Deprecated
873    public synchronized double[] getInternalValues() {
874        return internalArray;
875    }
876
877    /**
878     * Provides <em>direct</em> access to the internal storage array.
879     * Please note that this method returns a reference to this object's
880     * storage array, not a copy.
881     * <br/>
882     * To correctly address elements of the array, the "start index" is
883     * required (available via the {@link #getStartIndex() getStartIndex}
884     * method.
885     * <br/>
886     * This method should only be used to avoid copying the internal array.
887     * The returned value <em>must</em> be used for reading only; other
888     * uses could lead to this object becoming inconsistent.
889     * <br/>
890     * The {@link #getElements} method has no such limitation since it
891     * returns a copy of this array's addressable elements.
892     *
893     * @return the internal storage array used by this object.
894     * @since 3.1
895     */
896    protected double[] getArrayRef() {
897        return internalArray;
898    }
899
900    /**
901     * Returns the "start index" of the internal array.
902     * This index is the position of the first addressable element in the
903     * internal storage array.
904     * The addressable elements in the array are at indices contained in
905     * the interval [{@link #getStartIndex()},
906     *               {@link #getStartIndex()} + {@link #getNumElements()} - 1].
907     *
908     * @return the start index.
909     * @since 3.1
910     */
911    protected int getStartIndex() {
912        return startIndex;
913    }
914
915    /**
916     * Sets the contraction criteria.
917     *
918     * @param contractionCriteria contraction criteria
919     * @throws MathIllegalArgumentException if the contractionCriteria is less than
920     *         the expansionCriteria.
921     * @deprecated As of 3.1 (to be removed in 4.0 as field will become "final").
922     */
923    @Deprecated
924    public void setContractionCriteria(float contractionCriteria)
925        throws MathIllegalArgumentException {
926        checkContractExpand(contractionCriteria, getExpansionFactor());
927        synchronized(this) {
928            this.contractionCriterion = contractionCriteria;
929        }
930    }
931
932    /**
933     * Performs an operation on the addressable elements of the array.
934     *
935     * @param f Function to be applied on this array.
936     * @return the result.
937     * @since 3.1
938     */
939    public double compute(MathArrays.Function f) {
940        final double[] array;
941        final int start;
942        final int num;
943        synchronized(this) {
944            array = internalArray;
945            start = startIndex;
946            num   = numElements;
947        }
948        return f.evaluate(array, start, num);
949    }
950
951    /**
952     * Sets the element at the specified index.  If the specified index is greater than
953     * <code>getNumElements() - 1</code>, the <code>numElements</code> property
954     * is increased to <code>index +1</code> and additional storage is allocated
955     * (if necessary) for the new element and all  (uninitialized) elements
956     * between the new element and the previous end of the array).
957     *
958     * @param index index to store a value in
959     * @param value value to store at the specified index
960     * @throws ArrayIndexOutOfBoundsException if {@code index < 0}.
961     */
962    public synchronized void setElement(int index, double value) {
963        if (index < 0) {
964            throw new ArrayIndexOutOfBoundsException(index);
965        }
966        if (index + 1 > numElements) {
967            numElements = index + 1;
968        }
969        if ((startIndex + index) >= internalArray.length) {
970            expandTo(startIndex + (index + 1));
971        }
972        internalArray[startIndex + index] = value;
973    }
974
975    /**
976     * Sets the expansionFactor.  Throws IllegalArgumentException if the
977     * the following conditions are not met:
978     * <ul>
979     * <li><code>expansionFactor > 1</code></li>
980     * <li><code>contractionFactor >= expansionFactor</code></li>
981     * </ul>
982     * @param expansionFactor the new expansion factor value.
983     * @throws MathIllegalArgumentException if expansionFactor is <= 1 or greater
984     * than contractionFactor
985     * @deprecated As of 3.1 (to be removed in 4.0 as field will become "final").
986     */
987    @Deprecated
988    public void setExpansionFactor(float expansionFactor) throws MathIllegalArgumentException {
989        checkContractExpand(getContractionCriterion(), expansionFactor);
990        // The check above verifies that the expansion factor is > 1.0;
991        synchronized(this) {
992            this.expansionFactor = expansionFactor;
993        }
994    }
995
996    /**
997     * Sets the <code>expansionMode</code>. The specified value must be one of
998     * ADDITIVE_MODE, MULTIPLICATIVE_MODE.
999     *
1000     * @param expansionMode The expansionMode to set.
1001     * @throws MathIllegalArgumentException if the specified mode value is not valid.
1002     * @deprecated As of 3.1. Please use {@link #setExpansionMode(ExpansionMode)} instead.
1003     */
1004    @Deprecated
1005    public void setExpansionMode(int expansionMode)
1006        throws MathIllegalArgumentException {
1007        if (expansionMode != MULTIPLICATIVE_MODE &&
1008            expansionMode != ADDITIVE_MODE) {
1009            throw new MathIllegalArgumentException(LocalizedFormats.UNSUPPORTED_EXPANSION_MODE, expansionMode,
1010                                                   MULTIPLICATIVE_MODE, "MULTIPLICATIVE_MODE",
1011                                                   ADDITIVE_MODE, "ADDITIVE_MODE");
1012        }
1013        synchronized(this) {
1014            if (expansionMode == MULTIPLICATIVE_MODE) {
1015                setExpansionMode(ExpansionMode.MULTIPLICATIVE);
1016            } else if (expansionMode == ADDITIVE_MODE) {
1017                setExpansionMode(ExpansionMode.ADDITIVE);
1018            }
1019        }
1020    }
1021
1022    /**
1023     * Sets the {@link ExpansionMode expansion mode}.
1024     *
1025     * @param expansionMode Expansion mode to use for resizing the array.
1026     * @deprecated As of 3.1 (to be removed in 4.0 as field will become "final").
1027     */
1028    @Deprecated
1029    public void setExpansionMode(ExpansionMode expansionMode) {
1030        this.expansionMode = expansionMode;
1031    }
1032
1033    /**
1034     * Sets the initial capacity.  Should only be invoked by constructors.
1035     *
1036     * @param initialCapacity of the array
1037     * @throws MathIllegalArgumentException if <code>initialCapacity</code> is not
1038     * positive.
1039     * @deprecated As of 3.1, this is a no-op.
1040     */
1041    @Deprecated
1042    protected void setInitialCapacity(int initialCapacity)
1043        throws MathIllegalArgumentException {
1044        // Body removed in 3.1.
1045    }
1046
1047    /**
1048     * This function allows you to control the number of elements contained
1049     * in this array, and can be used to "throw out" the last n values in an
1050     * array. This function will also expand the internal array as needed.
1051     *
1052     * @param i a new number of elements
1053     * @throws MathIllegalArgumentException if <code>i</code> is negative.
1054     */
1055    public synchronized void setNumElements(int i)
1056        throws MathIllegalArgumentException {
1057        // If index is negative thrown an error.
1058        if (i < 0) {
1059            throw new MathIllegalArgumentException(
1060                    LocalizedFormats.INDEX_NOT_POSITIVE,
1061                    i);
1062        }
1063
1064        // Test the new num elements, check to see if the array needs to be
1065        // expanded to accommodate this new number of elements.
1066        final int newSize = startIndex + i;
1067        if (newSize > internalArray.length) {
1068            expandTo(newSize);
1069        }
1070
1071        // Set the new number of elements to new value.
1072        numElements = i;
1073    }
1074
1075    /**
1076     * Returns true if the internal storage array has too many unused
1077     * storage positions.
1078     *
1079     * @return true if array satisfies the contraction criteria
1080     */
1081    private synchronized boolean shouldContract() {
1082        if (expansionMode == ExpansionMode.MULTIPLICATIVE) {
1083            return (internalArray.length / ((float) numElements)) > contractionCriterion;
1084        } else {
1085            return (internalArray.length - numElements) > contractionCriterion;
1086        }
1087    }
1088
1089    /**
1090     * Returns the starting index of the internal array.  The starting index is
1091     * the position of the first addressable element in the internal storage
1092     * array.  The addressable elements in the array are <code>
1093     * internalArray[startIndex],...,internalArray[startIndex + numElements -1]
1094     * </code>
1095     *
1096     * @return the starting index.
1097     * @deprecated As of 3.1.
1098     */
1099    @Deprecated
1100    public synchronized int start() {
1101        return startIndex;
1102    }
1103
1104    /**
1105     * <p>Copies source to dest, copying the underlying data, so dest is
1106     * a new, independent copy of source.  Does not contract before
1107     * the copy.</p>
1108     *
1109     * <p>Obtains synchronization locks on both source and dest
1110     * (in that order) before performing the copy.</p>
1111     *
1112     * <p>Neither source nor dest may be null; otherwise a {@link NullArgumentException}
1113     * is thrown</p>
1114     *
1115     * @param source ResizableDoubleArray to copy
1116     * @param dest ResizableArray to replace with a copy of the source array
1117     * @exception NullArgumentException if either source or dest is null
1118     * @since 2.0
1119     *
1120     */
1121    public static void copy(ResizableDoubleArray source,
1122                            ResizableDoubleArray dest)
1123        throws NullArgumentException {
1124        MathUtils.checkNotNull(source);
1125        MathUtils.checkNotNull(dest);
1126        synchronized(source) {
1127           synchronized(dest) {
1128               dest.contractionCriterion = source.contractionCriterion;
1129               dest.expansionFactor = source.expansionFactor;
1130               dest.expansionMode = source.expansionMode;
1131               dest.internalArray = new double[source.internalArray.length];
1132               System.arraycopy(source.internalArray, 0, dest.internalArray,
1133                       0, dest.internalArray.length);
1134               dest.numElements = source.numElements;
1135               dest.startIndex = source.startIndex;
1136           }
1137       }
1138    }
1139
1140    /**
1141     * Returns a copy of the ResizableDoubleArray.  Does not contract before
1142     * the copy, so the returned object is an exact copy of this.
1143     *
1144     * @return a new ResizableDoubleArray with the same data and configuration
1145     * properties as this
1146     * @since 2.0
1147     */
1148    public synchronized ResizableDoubleArray copy() {
1149        final ResizableDoubleArray result = new ResizableDoubleArray();
1150        copy(this, result);
1151        return result;
1152    }
1153
1154    /**
1155     * Returns true iff object is a ResizableDoubleArray with the same properties
1156     * as this and an identical internal storage array.
1157     *
1158     * @param object object to be compared for equality with this
1159     * @return true iff object is a ResizableDoubleArray with the same data and
1160     * properties as this
1161     * @since 2.0
1162     */
1163    @Override
1164    public boolean equals(Object object) {
1165        if (object == this ) {
1166            return true;
1167        }
1168        if (object instanceof ResizableDoubleArray == false) {
1169            return false;
1170        }
1171        synchronized(this) {
1172            synchronized(object) {
1173                boolean result = true;
1174                final ResizableDoubleArray other = (ResizableDoubleArray) object;
1175                result = result && (other.contractionCriterion == contractionCriterion);
1176                result = result && (other.expansionFactor == expansionFactor);
1177                result = result && (other.expansionMode == expansionMode);
1178                result = result && (other.numElements == numElements);
1179                result = result && (other.startIndex == startIndex);
1180                if (!result) {
1181                    return false;
1182                } else {
1183                    return Arrays.equals(internalArray, other.internalArray);
1184                }
1185            }
1186        }
1187    }
1188
1189    /**
1190     * Returns a hash code consistent with equals.
1191     *
1192     * @return the hash code representing this {@code ResizableDoubleArray}.
1193     * @since 2.0
1194     */
1195    @Override
1196    public synchronized int hashCode() {
1197        final int[] hashData = new int[6];
1198        hashData[0] = Double.valueOf(expansionFactor).hashCode();
1199        hashData[1] = Double.valueOf(contractionCriterion).hashCode();
1200        hashData[2] = expansionMode.hashCode();
1201        hashData[3] = Arrays.hashCode(internalArray);
1202        hashData[4] = numElements;
1203        hashData[5] = startIndex;
1204        return Arrays.hashCode(hashData);
1205    }
1206
1207}