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