View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math3.util;
18  
19  import java.io.Serializable;
20  import java.util.Arrays;
21  
22  import org.apache.commons.math3.exception.MathIllegalArgumentException;
23  import org.apache.commons.math3.exception.MathIllegalStateException;
24  import org.apache.commons.math3.exception.MathInternalError;
25  import org.apache.commons.math3.exception.NullArgumentException;
26  import org.apache.commons.math3.exception.NotStrictlyPositiveException;
27  import org.apache.commons.math3.exception.NumberIsTooSmallException;
28  import org.apache.commons.math3.exception.util.LocalizedFormats;
29  
30  /**
31   * <p>
32   * A variable length {@link DoubleArray} implementation that automatically
33   * handles expanding and contracting its internal storage array as elements
34   * are added and removed.
35   * </p>
36   * <h3>Important note: Usage should not assume that this class is thread-safe
37   * even though some of the methods are {@code synchronized}.
38   * This qualifier will be dropped in the next major release (4.0).</h3>
39   * <p>
40   * The internal storage array starts with capacity determined by the
41   * {@code initialCapacity} property, which can be set by the constructor.
42   * The default initial capacity is 16.  Adding elements using
43   * {@link #addElement(double)} appends elements to the end of the array.
44   * When there are no open entries at the end of the internal storage array,
45   * the array is expanded.  The size of the expanded array depends on the
46   * {@code expansionMode} and {@code expansionFactor} properties.
47   * The {@code expansionMode} determines whether the size of the array is
48   * multiplied by the {@code expansionFactor}
49   * ({@link ExpansionMode#MULTIPLICATIVE}) or if the expansion is additive
50   * ({@link ExpansionMode#ADDITIVE} -- {@code expansionFactor} storage
51   * locations added).
52   * The default {@code expansionMode} is {@code MULTIPLICATIVE} and the default
53   * {@code expansionFactor} is 2.
54   * </p>
55   * <p>
56   * The {@link #addElementRolling(double)} method adds a new element to the end
57   * of the internal storage array and adjusts the "usable window" of the
58   * internal array forward by one position (effectively making what was the
59   * second element the first, and so on).  Repeated activations of this method
60   * (or activation of {@link #discardFrontElements(int)}) will effectively orphan
61   * the storage locations at the beginning of the internal storage array.  To
62   * reclaim this storage, each time one of these methods is activated, the size
63   * of the internal storage array is compared to the number of addressable
64   * elements (the {@code numElements} property) and if the difference
65   * is too large, the internal array is contracted to size
66   * {@code numElements + 1}.  The determination of when the internal
67   * storage array is "too large" depends on the {@code expansionMode} and
68   * {@code contractionFactor} properties.  If  the {@code expansionMode}
69   * is {@code MULTIPLICATIVE}, contraction is triggered when the
70   * ratio between storage array length and {@code numElements} exceeds
71   * {@code contractionFactor.}  If the {@code expansionMode}
72   * is {@code ADDITIVE}, the number of excess storage locations
73   * is compared to {@code contractionFactor}.
74   * </p>
75   * <p>
76   * To avoid cycles of expansions and contractions, the
77   * {@code expansionFactor} must not exceed the {@code contractionFactor}.
78   * Constructors and mutators for both of these properties enforce this
79   * requirement, throwing a {@code MathIllegalArgumentException} if it is
80   * violated.
81   * </p>
82   */
83  public class ResizableDoubleArray implements DoubleArray, Serializable {
84      /** Additive expansion mode.
85       * @deprecated As of 3.1. Please use {@link ExpansionMode#ADDITIVE} instead.
86       */
87      @Deprecated
88      public static final int ADDITIVE_MODE = 1;
89      /** Multiplicative expansion mode.
90       * @deprecated As of 3.1. Please use {@link ExpansionMode#MULTIPLICATIVE} instead.
91       */
92      @Deprecated
93      public static final int MULTIPLICATIVE_MODE = 0;
94      /** Serializable version identifier. */
95      private static final long serialVersionUID = -3485529955529426875L;
96  
97      /** Default value for initial capacity. */
98      private static final int DEFAULT_INITIAL_CAPACITY = 16;
99      /** 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 }