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 */
083public class ResizableDoubleArray implements DoubleArray, Serializable {
084    /** Additive expansion mode.
085     * @deprecated As of 3.1. Please use {@link ExpansionMode#ADDITIVE} instead.
086     */
087    @Deprecated
088    public static final int ADDITIVE_MODE = 1;
089    /** Multiplicative expansion mode.
090     * @deprecated As of 3.1. Please use {@link ExpansionMode#MULTIPLICATIVE} instead.
091     */
092    @Deprecated
093    public static final int MULTIPLICATIVE_MODE = 0;
094    /** Serializable version identifier. */
095    private static final long serialVersionUID = -3485529955529426875L;
096
097    /** Default value for initial capacity. */
098    private static final int DEFAULT_INITIAL_CAPACITY = 16;
099    /** Default value for array size modifier. */
100    private static final double DEFAULT_EXPANSION_FACTOR = 2.0;
101    /**
102     * Default value for the difference between {@link #contractionCriterion}
103     * and {@link #expansionFactor}.
104     */
105    private static final double DEFAULT_CONTRACTION_DELTA = 0.5;
106
107    /**
108     * The contraction criteria determines when the internal array will be
109     * contracted to fit the number of elements contained in the element
110     *  array + 1.
111     */
112    private double contractionCriterion = 2.5;
113
114    /**
115     * The expansion factor of the array.  When the array needs to be expanded,
116     * the new array size will be
117     * {@code internalArray.length * expansionFactor}
118     * if {@code expansionMode} is set to MULTIPLICATIVE_MODE, or
119     * {@code internalArray.length + expansionFactor} if
120     * {@code expansionMode} is set to ADDITIVE_MODE.
121     */
122    private double expansionFactor = 2.0;
123
124    /**
125     * Determines whether array expansion by {@code expansionFactor}
126     * is additive or multiplicative.
127     */
128    private ExpansionMode expansionMode = ExpansionMode.MULTIPLICATIVE;
129
130    /**
131     * The internal storage array.
132     */
133    private double[] internalArray;
134
135    /**
136     * The number of addressable elements in the array.  Note that this
137     * has nothing to do with the length of the internal storage array.
138     */
139    private int numElements = 0;
140
141    /**
142     * The position of the first addressable element in the internal storage
143     * array.  The addressable elements in the array are
144     * {@code internalArray[startIndex],...,internalArray[startIndex + numElements - 1]}.
145     */
146    private int startIndex = 0;
147
148    /**
149     * Specification of expansion algorithm.
150     * @since 3.1
151     */
152    public static enum ExpansionMode {
153        /** Multiplicative expansion mode. */
154        MULTIPLICATIVE,
155        /** Additive expansion mode. */
156        ADDITIVE
157    }
158
159    /**
160     * Creates an instance with default properties.
161     * <ul>
162     *  <li>{@code initialCapacity = 16}</li>
163     *  <li>{@code expansionMode = MULTIPLICATIVE}</li>
164     *  <li>{@code expansionFactor = 2.0}</li>
165     *  <li>{@code contractionCriterion = 2.5}</li>
166     * </ul>
167     */
168    public ResizableDoubleArray() {
169        this(DEFAULT_INITIAL_CAPACITY);
170    }
171
172    /**
173     * Creates an instance with the specified initial capacity.
174     * Other properties take default values:
175     * <ul>
176     *  <li>{@code expansionMode = MULTIPLICATIVE}</li>
177     *  <li>{@code expansionFactor = 2.0}</li>
178     *  <li>{@code contractionCriterion = 2.5}</li>
179     * </ul>
180     * @param initialCapacity Initial size of the internal storage array.
181     * @throws MathIllegalArgumentException if {@code initialCapacity <= 0}.
182     */
183    public ResizableDoubleArray(int initialCapacity)
184        throws MathIllegalArgumentException {
185        this(initialCapacity, DEFAULT_EXPANSION_FACTOR);
186    }
187
188    /**
189     * Creates an instance from an existing {@code double[]} with the
190     * initial capacity and numElements corresponding to the size of
191     * the supplied {@code double[]} array.
192     * If the supplied array is null, a new empty array with the default
193     * initial capacity will be created.
194     * The input array is copied, not referenced.
195     * Other properties take default values:
196     * <ul>
197     *  <li>{@code initialCapacity = 16}</li>
198     *  <li>{@code expansionMode = MULTIPLICATIVE}</li>
199     *  <li>{@code expansionFactor = 2.0}</li>
200     *  <li>{@code contractionCriterion = 2.5}</li>
201     * </ul>
202     *
203     * @param initialArray initial array
204     * @since 2.2
205     */
206    public ResizableDoubleArray(double[] initialArray) {
207        this(DEFAULT_INITIAL_CAPACITY,
208             DEFAULT_EXPANSION_FACTOR,
209             DEFAULT_CONTRACTION_DELTA + DEFAULT_EXPANSION_FACTOR,
210             ExpansionMode.MULTIPLICATIVE,
211             initialArray);
212    }
213
214    /**
215     * Creates an instance with the specified initial capacity
216     * and expansion factor.
217     * The remaining properties take default values:
218     * <ul>
219     *  <li>{@code expansionMode = MULTIPLICATIVE}</li>
220     *  <li>{@code contractionCriterion = 0.5 + expansionFactor}</li>
221     * </ul>
222     * <br/>
223     * Throws IllegalArgumentException if the following conditions are
224     * not met:
225     * <ul>
226     *  <li>{@code initialCapacity > 0}</li>
227     *  <li>{@code expansionFactor > 1}</li>
228     * </ul>
229     *
230     * @param initialCapacity Initial size of the internal storage array.
231     * @param expansionFactor The array will be expanded based on this
232     * parameter.
233     * @throws MathIllegalArgumentException if parameters are not valid.
234     * @deprecated As of 3.1. Please use
235     * {@link #ResizableDoubleArray(int,double)} instead.
236     */
237    @Deprecated
238    public ResizableDoubleArray(int initialCapacity,
239                                float expansionFactor)
240        throws MathIllegalArgumentException {
241        this(initialCapacity,
242             (double) expansionFactor);
243    }
244
245    /**
246     * Creates an instance with the specified initial capacity
247     * and expansion factor.
248     * The remaining properties take default values:
249     * <ul>
250     *  <li>{@code expansionMode = MULTIPLICATIVE}</li>
251     *  <li>{@code contractionCriterion = 0.5 + expansionFactor}</li>
252     * </ul>
253     * <br/>
254     * Throws IllegalArgumentException if the following conditions are
255     * not met:
256     * <ul>
257     *  <li>{@code initialCapacity > 0}</li>
258     *  <li>{@code expansionFactor > 1}</li>
259     * </ul>
260     *
261     * @param initialCapacity Initial size of the internal storage array.
262     * @param expansionFactor The array will be expanded based on this
263     * parameter.
264     * @throws MathIllegalArgumentException if parameters are not valid.
265     * @since 3.1
266     */
267    public ResizableDoubleArray(int initialCapacity,
268                                double expansionFactor)
269        throws MathIllegalArgumentException {
270        this(initialCapacity,
271             expansionFactor,
272             DEFAULT_CONTRACTION_DELTA + expansionFactor);
273    }
274
275    /**
276     * Creates an instance with the specified initialCapacity,
277     * expansionFactor, and contractionCriterion.
278     * The expansion mode will default to {@code MULTIPLICATIVE}.
279     * <br/>
280     * Throws IllegalArgumentException if the following conditions are
281     * not met:
282     * <ul>
283     *  <li>{@code initialCapacity > 0}</li>
284     *  <li>{@code expansionFactor > 1}</li>
285     *  <li>{@code contractionCriterion >= expansionFactor}</li>
286     * </ul>
287     *
288     * @param initialCapacity Initial size of the internal storage array..
289     * @param expansionFactor The array will be expanded based on this
290     * parameter.
291     * @param contractionCriteria Contraction criteria.
292     * @throws MathIllegalArgumentException if parameters are not valid.
293     * @deprecated As of 3.1. Please use
294     * {@link #ResizableDoubleArray(int,double,double)} instead.
295     */
296    @Deprecated
297    public ResizableDoubleArray(int initialCapacity,
298                                float expansionFactor,
299                                float contractionCriteria)
300        throws MathIllegalArgumentException {
301        this(initialCapacity,
302             (double) expansionFactor,
303             (double) contractionCriteria);
304    }
305
306    /**
307     * Creates an instance with the specified initial capacity,
308     * expansion factor, and contraction criteria.
309     * The expansion mode will default to {@code MULTIPLICATIVE}.
310     * <br/>
311     * Throws IllegalArgumentException if the following conditions are
312     * not met:
313     * <ul>
314     *  <li>{@code initialCapacity > 0}</li>
315     *  <li>{@code expansionFactor > 1}</li>
316     *  <li>{@code contractionCriterion >= expansionFactor}</li>
317     * </ul>
318     *
319     * @param initialCapacity Initial size of the internal storage array..
320     * @param expansionFactor The array will be expanded based on this
321     * parameter.
322     * @param contractionCriterion Contraction criterion.
323     * @throws MathIllegalArgumentException if the parameters are not valid.
324     * @since 3.1
325     */
326    public ResizableDoubleArray(int initialCapacity,
327                                double expansionFactor,
328                                double contractionCriterion)
329        throws MathIllegalArgumentException {
330        this(initialCapacity,
331             expansionFactor,
332             contractionCriterion,
333             ExpansionMode.MULTIPLICATIVE,
334             null);
335    }
336
337    /**
338     * <p>
339     * Create a ResizableArray with the specified properties.</p>
340     * <p>
341     * Throws IllegalArgumentException if the following conditions are
342     * not met:
343     * <ul>
344     * <li><code>initialCapacity > 0</code></li>
345     * <li><code>expansionFactor > 1</code></li>
346     * <li><code>contractionFactor >= expansionFactor</code></li>
347     * <li><code>expansionMode in {MULTIPLICATIVE_MODE, ADDITIVE_MODE}</code>
348     * </li>
349     * </ul></p>
350     *
351     * @param initialCapacity the initial size of the internal storage array
352     * @param expansionFactor the array will be expanded based on this
353     *                        parameter
354     * @param contractionCriteria the contraction Criteria
355     * @param expansionMode  the expansion mode
356     * @throws MathIllegalArgumentException if parameters are not valid
357     * @deprecated As of 3.1. Please use
358     * {@link #ResizableDoubleArray(int,double,double,ExpansionMode,double[])}
359     * instead.
360     */
361    @Deprecated
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 && data.length > 1) {
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    @Deprecated
535    protected void checkContractExpand(float contraction, float expansion)
536        throws MathIllegalArgumentException {
537        checkContractExpand((double) contraction,
538                            (double) expansion);
539    }
540
541    /**
542     * Checks the expansion factor and the contraction criterion and raises
543     * an exception if the contraction criterion is smaller than the
544     * expansion criterion.
545     *
546     * @param contraction Criterion to be checked.
547     * @param expansion Factor to be checked.
548     * @throws NumberIsTooSmallException if {@code contraction < expansion}.
549     * @throws NumberIsTooSmallException if {@code contraction <= 1}.
550     * @throws NumberIsTooSmallException if {@code expansion <= 1 }.
551     * @since 3.1
552     */
553    protected void checkContractExpand(double contraction,
554                                       double expansion)
555        throws NumberIsTooSmallException {
556        if (contraction < expansion) {
557            final NumberIsTooSmallException e = new NumberIsTooSmallException(contraction, 1, true);
558            e.getContext().addMessage(LocalizedFormats.CONTRACTION_CRITERIA_SMALLER_THAN_EXPANSION_FACTOR,
559                                      contraction, expansion);
560            throw e;
561        }
562
563        if (contraction <= 1) {
564            final NumberIsTooSmallException e = new NumberIsTooSmallException(contraction, 1, false);
565            e.getContext().addMessage(LocalizedFormats.CONTRACTION_CRITERIA_SMALLER_THAN_ONE,
566                                      contraction);
567            throw e;
568        }
569
570        if (expansion <= 1) {
571            final NumberIsTooSmallException e = new NumberIsTooSmallException(contraction, 1, false);
572            e.getContext().addMessage(LocalizedFormats.EXPANSION_FACTOR_SMALLER_THAN_ONE,
573                                      expansion);
574            throw e;
575        }
576    }
577
578    /**
579     * Clear the array contents, resetting the number of elements to zero.
580     */
581    public synchronized void clear() {
582        numElements = 0;
583        startIndex = 0;
584    }
585
586    /**
587     * Contracts the storage array to the (size of the element set) + 1 - to
588     * avoid a zero length array. This function also resets the startIndex to
589     * zero.
590     */
591    public synchronized void contract() {
592        final double[] tempArray = new double[numElements + 1];
593
594        // Copy and swap - copy only the element array from the src array.
595        System.arraycopy(internalArray, startIndex, tempArray, 0, numElements);
596        internalArray = tempArray;
597
598        // Reset the start index to zero
599        startIndex = 0;
600    }
601
602    /**
603     * Discards the <code>i</code> initial elements of the array.  For example,
604     * if the array contains the elements 1,2,3,4, invoking
605     * <code>discardFrontElements(2)</code> will cause the first two elements
606     * to be discarded, leaving 3,4 in the array.  Throws illegalArgumentException
607     * if i exceeds numElements.
608     *
609     * @param i  the number of elements to discard from the front of the array
610     * @throws MathIllegalArgumentException if i is greater than numElements.
611     * @since 2.0
612     */
613    public synchronized void discardFrontElements(int i)
614        throws MathIllegalArgumentException {
615        discardExtremeElements(i,true);
616    }
617
618    /**
619     * Discards the <code>i</code> last elements of the array.  For example,
620     * if the array contains the elements 1,2,3,4, invoking
621     * <code>discardMostRecentElements(2)</code> will cause the last two elements
622     * to be discarded, leaving 1,2 in the array.  Throws illegalArgumentException
623     * if i exceeds numElements.
624     *
625     * @param i  the number of elements to discard from the end of the array
626     * @throws MathIllegalArgumentException if i is greater than numElements.
627     * @since 2.0
628     */
629    public synchronized void discardMostRecentElements(int i)
630        throws MathIllegalArgumentException {
631        discardExtremeElements(i,false);
632    }
633
634    /**
635     * Discards the <code>i</code> first or last elements of the array,
636     * depending on the value of <code>front</code>.
637     * For example, if the array contains the elements 1,2,3,4, invoking
638     * <code>discardExtremeElements(2,false)</code> will cause the last two elements
639     * to be discarded, leaving 1,2 in the array.
640     * For example, if the array contains the elements 1,2,3,4, invoking
641     * <code>discardExtremeElements(2,true)</code> will cause the first two elements
642     * to be discarded, leaving 3,4 in the array.
643     * Throws illegalArgumentException
644     * if i exceeds numElements.
645     *
646     * @param i  the number of elements to discard from the front/end of the array
647     * @param front true if elements are to be discarded from the front
648     * of the array, false if elements are to be discarded from the end
649     * of the array
650     * @throws MathIllegalArgumentException if i is greater than numElements.
651     * @since 2.0
652     */
653    private synchronized void discardExtremeElements(int i,
654                                                     boolean front)
655        throws MathIllegalArgumentException {
656        if (i > numElements) {
657            throw new MathIllegalArgumentException(
658                    LocalizedFormats.TOO_MANY_ELEMENTS_TO_DISCARD_FROM_ARRAY,
659                    i, numElements);
660       } else if (i < 0) {
661           throw new MathIllegalArgumentException(
662                   LocalizedFormats.CANNOT_DISCARD_NEGATIVE_NUMBER_OF_ELEMENTS,
663                   i);
664        } else {
665            // "Subtract" this number of discarded from numElements
666            numElements -= i;
667            if (front) {
668                startIndex += i;
669            }
670        }
671        if (shouldContract()) {
672            contract();
673        }
674    }
675
676    /**
677     * Expands the internal storage array using the expansion factor.
678     * <p>
679     * if <code>expansionMode</code> is set to MULTIPLICATIVE_MODE,
680     * the new array size will be <code>internalArray.length * expansionFactor.</code>
681     * If <code>expansionMode</code> is set to ADDITIVE_MODE,  the length
682     * after expansion will be <code>internalArray.length + expansionFactor</code>
683     * </p>
684     */
685    protected synchronized void expand() {
686        // notice the use of FastMath.ceil(), this guarantees that we will always
687        // have an array of at least currentSize + 1.   Assume that the
688        // current initial capacity is 1 and the expansion factor
689        // is 1.000000000000000001.  The newly calculated size will be
690        // rounded up to 2 after the multiplication is performed.
691        int newSize = 0;
692        if (expansionMode == ExpansionMode.MULTIPLICATIVE) {
693            newSize = (int) FastMath.ceil(internalArray.length * expansionFactor);
694        } else {
695            newSize = (int) (internalArray.length + FastMath.round(expansionFactor));
696        }
697        final double[] tempArray = new double[newSize];
698
699        // Copy and swap
700        System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
701        internalArray = tempArray;
702    }
703
704    /**
705     * Expands the internal storage array to the specified size.
706     *
707     * @param size Size of the new internal storage array.
708     */
709    private synchronized void expandTo(int size) {
710        final double[] tempArray = new double[size];
711        // Copy and swap
712        System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
713        internalArray = tempArray;
714    }
715
716    /**
717     * The contraction criteria defines when the internal array will contract
718     * to store only the number of elements in the element array.
719     * If  the <code>expansionMode</code> is <code>MULTIPLICATIVE_MODE</code>,
720     * contraction is triggered when the ratio between storage array length
721     * and <code>numElements</code> exceeds <code>contractionFactor</code>.
722     * If the <code>expansionMode</code> is <code>ADDITIVE_MODE</code>, the
723     * number of excess storage locations is compared to
724     * <code>contractionFactor.</code>
725     *
726     * @return the contraction criteria used to reclaim memory.
727     * @deprecated As of 3.1. Please use {@link #getContractionCriterion()}
728     * instead.
729     */
730    @Deprecated
731    public float getContractionCriteria() {
732        return (float) getContractionCriterion();
733    }
734
735    /**
736     * The contraction criterion defines when the internal array will contract
737     * to store only the number of elements in the element array.
738     * If  the <code>expansionMode</code> is <code>MULTIPLICATIVE_MODE</code>,
739     * contraction is triggered when the ratio between storage array length
740     * and <code>numElements</code> exceeds <code>contractionFactor</code>.
741     * If the <code>expansionMode</code> is <code>ADDITIVE_MODE</code>, the
742     * number of excess storage locations is compared to
743     * <code>contractionFactor.</code>
744     *
745     * @return the contraction criterion used to reclaim memory.
746     * @since 3.1
747     */
748    public double getContractionCriterion() {
749        return contractionCriterion;
750    }
751
752    /**
753     * Returns the element at the specified index
754     *
755     * @param index index to fetch a value from
756     * @return value stored at the specified index
757     * @throws ArrayIndexOutOfBoundsException if <code>index</code> is less than
758     * zero or is greater than <code>getNumElements() - 1</code>.
759     */
760    public synchronized double getElement(int index) {
761        if (index >= numElements) {
762            throw new ArrayIndexOutOfBoundsException(index);
763        } else if (index >= 0) {
764            return internalArray[startIndex + index];
765        } else {
766            throw new ArrayIndexOutOfBoundsException(index);
767        }
768    }
769
770     /**
771     * Returns a double array containing the elements of this
772     * <code>ResizableArray</code>.  This method returns a copy, not a
773     * reference to the underlying array, so that changes made to the returned
774     *  array have no effect on this <code>ResizableArray.</code>
775     * @return the double array.
776     */
777    public synchronized double[] getElements() {
778        final double[] elementArray = new double[numElements];
779        System.arraycopy(internalArray, startIndex, elementArray, 0, numElements);
780        return elementArray;
781    }
782
783    /**
784     * The expansion factor controls the size of a new array when an array
785     * needs to be expanded.  The <code>expansionMode</code>
786     * determines whether the size of the array is multiplied by the
787     * <code>expansionFactor</code> (MULTIPLICATIVE_MODE) or if
788     * the expansion is additive (ADDITIVE_MODE -- <code>expansionFactor</code>
789     * storage locations added).  The default <code>expansionMode</code> is
790     * MULTIPLICATIVE_MODE and the default <code>expansionFactor</code>
791     * is 2.0.
792     *
793     * @return the expansion factor of this expandable double array
794     * @deprecated As of 3.1. Return type will be changed to "double" in 4.0.
795     */
796    @Deprecated
797    public float getExpansionFactor() {
798        return (float) expansionFactor;
799    }
800
801    /**
802     * The expansion mode determines whether the internal storage
803     * array grows additively or multiplicatively when it is expanded.
804     *
805     * @return the expansion mode.
806     * @deprecated As of 3.1. Return value to be changed to
807     * {@link ExpansionMode} in 4.0.
808     */
809    @Deprecated
810    public int getExpansionMode() {
811        switch (expansionMode) {
812        case MULTIPLICATIVE:
813            return MULTIPLICATIVE_MODE;
814        case ADDITIVE:
815            return ADDITIVE_MODE;
816        default:
817            throw new MathInternalError(); // Should never happen.
818        }
819    }
820
821    /**
822     * Notice the package scope on this method.   This method is simply here
823     * for the JUnit test, it allows us check if the expansion is working
824     * properly after a number of expansions.  This is not meant to be a part
825     * of the public interface of this class.
826     *
827     * @return the length of the internal storage array.
828     * @deprecated As of 3.1. Please use {@link #getCapacity()} instead.
829     */
830    @Deprecated
831    synchronized int getInternalLength() {
832        return internalArray.length;
833    }
834
835    /**
836     * Gets the currently allocated size of the internal data structure used
837     * for storing elements.
838     * This is not to be confused with {@link #getNumElements() the number of
839     * elements actually stored}.
840     *
841     * @return the length of the internal array.
842     * @since 3.1
843     */
844    public int getCapacity() {
845        return internalArray.length;
846    }
847
848    /**
849     * Returns the number of elements currently in the array.  Please note
850     * that this is different from the length of the internal storage array.
851     *
852     * @return the number of elements.
853     */
854    public synchronized int getNumElements() {
855        return numElements;
856    }
857
858    /**
859     * Returns the internal storage array.  Note that this method returns
860     * a reference to the internal storage array, not a copy, and to correctly
861     * address elements of the array, the <code>startIndex</code> is
862     * required (available via the {@link #start} method).  This method should
863     * only be used in cases where copying the internal array is not practical.
864     * The {@link #getElements} method should be used in all other cases.
865     *
866     *
867     * @return the internal storage array used by this object
868     * @since 2.0
869     * @deprecated As of 3.1.
870     */
871    @Deprecated
872    public synchronized double[] getInternalValues() {
873        return internalArray;
874    }
875
876    /**
877     * Provides <em>direct</em> access to the internal storage array.
878     * Please note that this method returns a reference to this object's
879     * storage array, not a copy.
880     * <br/>
881     * To correctly address elements of the array, the "start index" is
882     * required (available via the {@link #getStartIndex() getStartIndex}
883     * method.
884     * <br/>
885     * This method should only be used to avoid copying the internal array.
886     * The returned value <em>must</em> be used for reading only; other
887     * uses could lead to this object becoming inconsistent.
888     * <br/>
889     * The {@link #getElements} method has no such limitation since it
890     * returns a copy of this array's addressable elements.
891     *
892     * @return the internal storage array used by this object.
893     * @since 3.1
894     */
895    protected double[] getArrayRef() {
896        return internalArray;
897    }
898
899    /**
900     * Returns the "start index" of the internal array.
901     * This index is the position of the first addressable element in the
902     * internal storage array.
903     * The addressable elements in the array are at indices contained in
904     * the interval [{@link #getStartIndex()},
905     *               {@link #getStartIndex()} + {@link #getNumElements()} - 1].
906     *
907     * @return the start index.
908     * @since 3.1
909     */
910    protected int getStartIndex() {
911        return startIndex;
912    }
913
914    /**
915     * Sets the contraction criteria.
916     *
917     * @param contractionCriteria contraction criteria
918     * @throws MathIllegalArgumentException if the contractionCriteria is less than
919     *         the expansionCriteria.
920     * @deprecated As of 3.1 (to be removed in 4.0 as field will become "final").
921     */
922    @Deprecated
923    public void setContractionCriteria(float contractionCriteria)
924        throws MathIllegalArgumentException {
925        checkContractExpand(contractionCriteria, getExpansionFactor());
926        synchronized(this) {
927            this.contractionCriterion = contractionCriteria;
928        }
929    }
930
931    /**
932     * Performs an operation on the addressable elements of the array.
933     *
934     * @param f Function to be applied on this array.
935     * @return the result.
936     * @since 3.1
937     */
938    public double compute(MathArrays.Function f) {
939        final double[] array;
940        final int start;
941        final int num;
942        synchronized(this) {
943            array = internalArray;
944            start = startIndex;
945            num   = numElements;
946        }
947        return f.evaluate(array, start, num);
948    }
949
950    /**
951     * Sets the element at the specified index.  If the specified index is greater than
952     * <code>getNumElements() - 1</code>, the <code>numElements</code> property
953     * is increased to <code>index +1</code> and additional storage is allocated
954     * (if necessary) for the new element and all  (uninitialized) elements
955     * between the new element and the previous end of the array).
956     *
957     * @param index index to store a value in
958     * @param value value to store at the specified index
959     * @throws ArrayIndexOutOfBoundsException if {@code index < 0}.
960     */
961    public synchronized void setElement(int index, double value) {
962        if (index < 0) {
963            throw new ArrayIndexOutOfBoundsException(index);
964        }
965        if (index + 1 > numElements) {
966            numElements = index + 1;
967        }
968        if ((startIndex + index) >= internalArray.length) {
969            expandTo(startIndex + (index + 1));
970        }
971        internalArray[startIndex + index] = value;
972    }
973
974    /**
975     * Sets the expansionFactor.  Throws IllegalArgumentException if the
976     * the following conditions are not met:
977     * <ul>
978     * <li><code>expansionFactor > 1</code></li>
979     * <li><code>contractionFactor >= expansionFactor</code></li>
980     * </ul>
981     * @param expansionFactor the new expansion factor value.
982     * @throws MathIllegalArgumentException if expansionFactor is <= 1 or greater
983     * than contractionFactor
984     * @deprecated As of 3.1 (to be removed in 4.0 as field will become "final").
985     */
986    @Deprecated
987    public void setExpansionFactor(float expansionFactor) throws MathIllegalArgumentException {
988        checkContractExpand(getContractionCriterion(), expansionFactor);
989        // The check above verifies that the expansion factor is > 1.0;
990        synchronized(this) {
991            this.expansionFactor = expansionFactor;
992        }
993    }
994
995    /**
996     * Sets the <code>expansionMode</code>. The specified value must be one of
997     * ADDITIVE_MODE, MULTIPLICATIVE_MODE.
998     *
999     * @param expansionMode The expansionMode to set.
1000     * @throws MathIllegalArgumentException if the specified mode value is not valid.
1001     * @deprecated As of 3.1. Please use {@link #setExpansionMode(ExpansionMode)} instead.
1002     */
1003    @Deprecated
1004    public void setExpansionMode(int expansionMode)
1005        throws MathIllegalArgumentException {
1006        if (expansionMode != MULTIPLICATIVE_MODE &&
1007            expansionMode != ADDITIVE_MODE) {
1008            throw new MathIllegalArgumentException(LocalizedFormats.UNSUPPORTED_EXPANSION_MODE, expansionMode,
1009                                                   MULTIPLICATIVE_MODE, "MULTIPLICATIVE_MODE",
1010                                                   ADDITIVE_MODE, "ADDITIVE_MODE");
1011        }
1012        synchronized(this) {
1013            if (expansionMode == MULTIPLICATIVE_MODE) {
1014                setExpansionMode(ExpansionMode.MULTIPLICATIVE);
1015            } else if (expansionMode == ADDITIVE_MODE) {
1016                setExpansionMode(ExpansionMode.ADDITIVE);
1017            }
1018        }
1019    }
1020
1021    /**
1022     * Sets the {@link ExpansionMode expansion mode}.
1023     *
1024     * @param expansionMode Expansion mode to use for resizing the array.
1025     * @deprecated As of 3.1 (to be removed in 4.0 as field will become "final").
1026     */
1027    @Deprecated
1028    public void setExpansionMode(ExpansionMode expansionMode) {
1029        this.expansionMode = expansionMode;
1030    }
1031
1032    /**
1033     * Sets the initial capacity.  Should only be invoked by constructors.
1034     *
1035     * @param initialCapacity of the array
1036     * @throws MathIllegalArgumentException if <code>initialCapacity</code> is not
1037     * positive.
1038     * @deprecated As of 3.1, this is a no-op.
1039     */
1040    @Deprecated
1041    protected void setInitialCapacity(int initialCapacity)
1042        throws MathIllegalArgumentException {
1043        // Body removed in 3.1.
1044    }
1045
1046    /**
1047     * This function allows you to control the number of elements contained
1048     * in this array, and can be used to "throw out" the last n values in an
1049     * array. This function will also expand the internal array as needed.
1050     *
1051     * @param i a new number of elements
1052     * @throws MathIllegalArgumentException if <code>i</code> is negative.
1053     */
1054    public synchronized void setNumElements(int i)
1055        throws MathIllegalArgumentException {
1056        // If index is negative thrown an error.
1057        if (i < 0) {
1058            throw new MathIllegalArgumentException(
1059                    LocalizedFormats.INDEX_NOT_POSITIVE,
1060                    i);
1061        }
1062
1063        // Test the new num elements, check to see if the array needs to be
1064        // expanded to accommodate this new number of elements.
1065        final int newSize = startIndex + i;
1066        if (newSize > internalArray.length) {
1067            expandTo(newSize);
1068        }
1069
1070        // Set the new number of elements to new value.
1071        numElements = i;
1072    }
1073
1074    /**
1075     * Returns true if the internal storage array has too many unused
1076     * storage positions.
1077     *
1078     * @return true if array satisfies the contraction criteria
1079     */
1080    private synchronized boolean shouldContract() {
1081        if (expansionMode == ExpansionMode.MULTIPLICATIVE) {
1082            return (internalArray.length / ((float) numElements)) > contractionCriterion;
1083        } else {
1084            return (internalArray.length - numElements) > contractionCriterion;
1085        }
1086    }
1087
1088    /**
1089     * Returns the starting index of the internal array.  The starting index is
1090     * the position of the first addressable element in the internal storage
1091     * array.  The addressable elements in the array are <code>
1092     * internalArray[startIndex],...,internalArray[startIndex + numElements -1]
1093     * </code>
1094     *
1095     * @return the starting index.
1096     * @deprecated As of 3.1.
1097     */
1098    @Deprecated
1099    public synchronized int start() {
1100        return startIndex;
1101    }
1102
1103    /**
1104     * <p>Copies source to dest, copying the underlying data, so dest is
1105     * a new, independent copy of source.  Does not contract before
1106     * the copy.</p>
1107     *
1108     * <p>Obtains synchronization locks on both source and dest
1109     * (in that order) before performing the copy.</p>
1110     *
1111     * <p>Neither source nor dest may be null; otherwise a {@link NullArgumentException}
1112     * is thrown</p>
1113     *
1114     * @param source ResizableDoubleArray to copy
1115     * @param dest ResizableArray to replace with a copy of the source array
1116     * @exception NullArgumentException if either source or dest is null
1117     * @since 2.0
1118     *
1119     */
1120    public static void copy(ResizableDoubleArray source,
1121                            ResizableDoubleArray dest)
1122        throws NullArgumentException {
1123        MathUtils.checkNotNull(source);
1124        MathUtils.checkNotNull(dest);
1125        synchronized(source) {
1126           synchronized(dest) {
1127               dest.contractionCriterion = source.contractionCriterion;
1128               dest.expansionFactor = source.expansionFactor;
1129               dest.expansionMode = source.expansionMode;
1130               dest.internalArray = new double[source.internalArray.length];
1131               System.arraycopy(source.internalArray, 0, dest.internalArray,
1132                       0, dest.internalArray.length);
1133               dest.numElements = source.numElements;
1134               dest.startIndex = source.startIndex;
1135           }
1136       }
1137    }
1138
1139    /**
1140     * Returns a copy of the ResizableDoubleArray.  Does not contract before
1141     * the copy, so the returned object is an exact copy of this.
1142     *
1143     * @return a new ResizableDoubleArray with the same data and configuration
1144     * properties as this
1145     * @since 2.0
1146     */
1147    public synchronized ResizableDoubleArray copy() {
1148        final ResizableDoubleArray result = new ResizableDoubleArray();
1149        copy(this, result);
1150        return result;
1151    }
1152
1153    /**
1154     * Returns true iff object is a ResizableDoubleArray with the same properties
1155     * as this and an identical internal storage array.
1156     *
1157     * @param object object to be compared for equality with this
1158     * @return true iff object is a ResizableDoubleArray with the same data and
1159     * properties as this
1160     * @since 2.0
1161     */
1162    @Override
1163    public boolean equals(Object object) {
1164        if (object == this ) {
1165            return true;
1166        }
1167        if (object instanceof ResizableDoubleArray == false) {
1168            return false;
1169        }
1170        synchronized(this) {
1171            synchronized(object) {
1172                boolean result = true;
1173                final ResizableDoubleArray other = (ResizableDoubleArray) object;
1174                result = result && (other.contractionCriterion == contractionCriterion);
1175                result = result && (other.expansionFactor == expansionFactor);
1176                result = result && (other.expansionMode == expansionMode);
1177                result = result && (other.numElements == numElements);
1178                result = result && (other.startIndex == startIndex);
1179                if (!result) {
1180                    return false;
1181                } else {
1182                    return Arrays.equals(internalArray, other.internalArray);
1183                }
1184            }
1185        }
1186    }
1187
1188    /**
1189     * Returns a hash code consistent with equals.
1190     *
1191     * @return the hash code representing this {@code ResizableDoubleArray}.
1192     * @since 2.0
1193     */
1194    @Override
1195    public synchronized int hashCode() {
1196        final int[] hashData = new int[6];
1197        hashData[0] = Double.valueOf(expansionFactor).hashCode();
1198        hashData[1] = Double.valueOf(contractionCriterion).hashCode();
1199        hashData[2] = expansionMode.hashCode();
1200        hashData[3] = Arrays.hashCode(internalArray);
1201        hashData[4] = numElements;
1202        hashData[5] = startIndex;
1203        return Arrays.hashCode(hashData);
1204    }
1205
1206}