001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.math4.util;
018
019import java.io.Serializable;
020import java.util.Arrays;
021
022import org.apache.commons.math4.exception.MathIllegalArgumentException;
023import org.apache.commons.math4.exception.MathIllegalStateException;
024import org.apache.commons.math4.exception.NotStrictlyPositiveException;
025import org.apache.commons.math4.exception.NullArgumentException;
026import org.apache.commons.math4.exception.NumberIsTooSmallException;
027import org.apache.commons.math4.exception.util.LocalizedFormats;
028
029/**
030 * A variable length {@link DoubleArray} implementation that automatically
031 * handles expanding and contracting its internal storage array as elements
032 * are added and removed.
033 * <p>
034 * The internal storage array starts with capacity determined by the
035 * {@code initialCapacity} property, which can be set by the constructor.
036 * The default initial capacity is 16.  Adding elements using
037 * {@link #addElement(double)} appends elements to the end of the array.
038 * When there are no open entries at the end of the internal storage array,
039 * the array is expanded.  The size of the expanded array depends on the
040 * {@code expansionMode} and {@code expansionFactor} properties.
041 * The {@code expansionMode} determines whether the size of the array is
042 * multiplied by the {@code expansionFactor}
043 * ({@link ExpansionMode#MULTIPLICATIVE}) or if the expansion is additive
044 * ({@link ExpansionMode#ADDITIVE} -- {@code expansionFactor} storage
045 * locations added).
046 * The default {@code expansionMode} is {@code MULTIPLICATIVE} and the default
047 * {@code expansionFactor} is 2.
048 * <p>
049 * The {@link #addElementRolling(double)} method adds a new element to the end
050 * of the internal storage array and adjusts the "usable window" of the
051 * internal array forward by one position (effectively making what was the
052 * second element the first, and so on).  Repeated activations of this method
053 * (or activation of {@link #discardFrontElements(int)}) will effectively orphan
054 * the storage locations at the beginning of the internal storage array.  To
055 * reclaim this storage, each time one of these methods is activated, the size
056 * of the internal storage array is compared to the number of addressable
057 * elements (the {@code numElements} property) and if the difference
058 * is too large, the internal array is contracted to size
059 * {@code numElements + 1}.  The determination of when the internal
060 * storage array is "too large" depends on the {@code expansionMode} and
061 * {@code contractionFactor} properties.  If  the {@code expansionMode}
062 * is {@code MULTIPLICATIVE}, contraction is triggered when the
063 * ratio between storage array length and {@code numElements} exceeds
064 * {@code contractionFactor.}  If the {@code expansionMode}
065 * is {@code ADDITIVE}, the number of excess storage locations
066 * is compared to {@code contractionFactor}.
067 * <p>
068 * To avoid cycles of expansions and contractions, the
069 * {@code expansionFactor} must not exceed the {@code contractionFactor}.
070 * Constructors and mutators for both of these properties enforce this
071 * requirement, throwing a {@code MathIllegalArgumentException} if it is
072 * violated.
073 * <p>
074 * <b>Note:</b> this class is <b>NOT</b> thread-safe.
075 */
076public class ResizableDoubleArray implements DoubleArray, Serializable {
077    /** Serializable version identifier. */
078    private static final long serialVersionUID = -3485529955529426875L;
079
080    /** Default value for initial capacity. */
081    private static final int DEFAULT_INITIAL_CAPACITY = 16;
082    /** Default value for array size modifier. */
083    private static final double DEFAULT_EXPANSION_FACTOR = 2.0;
084    /** Default value for expansion mode. */
085    private static final ExpansionMode DEFAULT_EXPANSION_MODE = ExpansionMode.MULTIPLICATIVE;
086    /**
087     * Default value for the difference between {@link #contractionCriterion}
088     * and {@link #expansionFactor}.
089     */
090    private static final double DEFAULT_CONTRACTION_DELTA = 0.5;
091
092    /**
093     * The contraction criteria determines when the internal array will be
094     * contracted to fit the number of elements contained in the element
095     *  array + 1.
096     */
097    private final double contractionCriterion;
098
099    /**
100     * The expansion factor of the array.  When the array needs to be expanded,
101     * the new array size will be {@code internalArray.length * expansionFactor}
102     * if {@code expansionMode} is set to MULTIPLICATIVE, or
103     * {@code internalArray.length + expansionFactor} if
104     * {@code expansionMode} is set to ADDITIVE.
105     */
106    private final double expansionFactor;
107
108    /**
109     * Determines whether array expansion by {@code expansionFactor}
110     * is additive or multiplicative.
111     */
112    private final ExpansionMode expansionMode;
113
114    /**
115     * The internal storage array.
116     */
117    private double[] internalArray;
118
119    /**
120     * The number of addressable elements in the array.  Note that this
121     * has nothing to do with the length of the internal storage array.
122     */
123    private int numElements;
124
125    /**
126     * The position of the first addressable element in the internal storage
127     * array.  The addressable elements in the array are
128     * {@code internalArray[startIndex],...,internalArray[startIndex + numElements - 1]}.
129     */
130    private int startIndex;
131
132    /**
133     * Specification of expansion algorithm.
134     * @since 3.1
135     */
136    public enum ExpansionMode {
137        /** Multiplicative expansion mode. */
138        MULTIPLICATIVE,
139        /** Additive expansion mode. */
140        ADDITIVE
141    }
142
143    /**
144     * Creates an instance with default properties.
145     * <ul>
146     *  <li>{@code initialCapacity = 16}</li>
147     *  <li>{@code expansionMode = MULTIPLICATIVE}</li>
148     *  <li>{@code expansionFactor = 2.0}</li>
149     *  <li>{@code contractionCriterion = 2.5}</li>
150     * </ul>
151     */
152    public ResizableDoubleArray() {
153        this(DEFAULT_INITIAL_CAPACITY);
154    }
155
156    /**
157     * Creates an instance with the specified initial capacity.
158     * <p>
159     * Other properties take default values:
160     * <ul>
161     *  <li>{@code expansionMode = MULTIPLICATIVE}</li>
162     *  <li>{@code expansionFactor = 2.0}</li>
163     *  <li>{@code contractionCriterion = 2.5}</li>
164     * </ul>
165     * @param initialCapacity Initial size of the internal storage array.
166     * @throws MathIllegalArgumentException if {@code initialCapacity <= 0}.
167     */
168    public ResizableDoubleArray(int initialCapacity) throws MathIllegalArgumentException {
169        this(initialCapacity, DEFAULT_EXPANSION_FACTOR);
170    }
171
172    /**
173     * Creates an instance from an existing {@code double[]} with the
174     * initial capacity and numElements corresponding to the size of
175     * the supplied {@code double[]} array.
176     * <p>
177     * If the supplied array is null, a new empty array with the default
178     * initial capacity will be created.
179     * The input array is copied, not referenced.
180     * Other properties take default values:
181     * <ul>
182     *  <li>{@code expansionMode = MULTIPLICATIVE}</li>
183     *  <li>{@code expansionFactor = 2.0}</li>
184     *  <li>{@code contractionCriterion = 2.5}</li>
185     * </ul>
186     *
187     * @param initialArray initial array
188     * @since 2.2
189     */
190    public ResizableDoubleArray(double[] initialArray) {
191        this(initialArray == null || initialArray.length == 0 ?
192              DEFAULT_INITIAL_CAPACITY :
193              initialArray.length,
194             DEFAULT_EXPANSION_FACTOR,
195             DEFAULT_CONTRACTION_DELTA + DEFAULT_EXPANSION_FACTOR,
196             DEFAULT_EXPANSION_MODE,
197             initialArray);
198    }
199
200    /**
201     * Creates an instance with the specified initial capacity
202     * and expansion factor.
203     * <p>
204     * The remaining properties take default values:
205     * <ul>
206     *  <li>{@code expansionMode = MULTIPLICATIVE}</li>
207     *  <li>{@code contractionCriterion = 0.5 + expansionFactor}</li>
208     * </ul>
209     * <p>
210     * Throws MathIllegalArgumentException if the following conditions
211     * are not met:
212     * <ul>
213     *  <li>{@code initialCapacity > 0}</li>
214     *  <li>{@code expansionFactor > 1}</li>
215     * </ul>
216     *
217     * @param initialCapacity Initial size of the internal storage array.
218     * @param expansionFactor The array will be expanded based on this parameter.
219     * @throws MathIllegalArgumentException if parameters are not valid.
220     * @since 3.1
221     */
222    public ResizableDoubleArray(int initialCapacity, double expansionFactor) throws MathIllegalArgumentException {
223        this(initialCapacity, expansionFactor, DEFAULT_CONTRACTION_DELTA + expansionFactor);
224    }
225
226    /**
227     * Creates an instance with the specified initial capacity,
228     * expansion factor, and contraction criteria.
229     * <p>
230     * The expansion mode will default to {@code MULTIPLICATIVE}.
231     * <p>
232     * Throws MathIllegalArgumentException if the following conditions
233     * are not met:
234     * <ul>
235     *  <li>{@code initialCapacity > 0}</li>
236     *  <li>{@code expansionFactor > 1}</li>
237     *  <li>{@code contractionCriterion >= expansionFactor}</li>
238     * </ul>
239     *
240     * @param initialCapacity Initial size of the internal storage array.
241     * @param expansionFactor The array will be expanded based on this parameter.
242     * @param contractionCriterion Contraction criterion.
243     * @throws MathIllegalArgumentException if the parameters are not valid.
244     * @since 3.1
245     */
246    public ResizableDoubleArray(int initialCapacity, double expansionFactor, double contractionCriterion)
247        throws MathIllegalArgumentException {
248        this(initialCapacity, expansionFactor, contractionCriterion, DEFAULT_EXPANSION_MODE);
249    }
250
251    /**
252     * Creates an instance with the specified properties.
253     * <br>
254     * Throws MathIllegalArgumentException if the following conditions
255     * are not met:
256     * <ul>
257     *  <li>{@code initialCapacity > 0}</li>
258     *  <li>{@code expansionFactor > 1}</li>
259     *  <li>{@code contractionCriterion >= expansionFactor}</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 parameter.
264     * @param contractionCriterion Contraction criteria.
265     * @param expansionMode Expansion mode.
266     * @param data Initial contents of the array.
267     * @throws MathIllegalArgumentException if the parameters are not valid.
268     * @throws NullArgumentException if expansionMode is null
269     */
270    public ResizableDoubleArray(int initialCapacity,
271                                double expansionFactor,
272                                double contractionCriterion,
273                                ExpansionMode expansionMode,
274                                double ... data)
275        throws MathIllegalArgumentException {
276        if (initialCapacity <= 0) {
277            throw new NotStrictlyPositiveException(LocalizedFormats.INITIAL_CAPACITY_NOT_POSITIVE,
278                                                   initialCapacity);
279        }
280        checkContractExpand(contractionCriterion, expansionFactor);
281        MathUtils.checkNotNull(expansionMode);
282
283        this.expansionFactor = expansionFactor;
284        this.contractionCriterion = contractionCriterion;
285        this.expansionMode = expansionMode;
286        internalArray = new double[initialCapacity];
287        numElements = 0;
288        startIndex = 0;
289
290        if (data != null && data.length > 0) {
291            addElements(data);
292        }
293    }
294
295    /**
296     * Copy constructor.
297     * <p>
298     * Creates a new ResizableDoubleArray that is a deep, fresh copy of the original.
299     * Original may not be null; otherwise a {@link NullArgumentException} is thrown.
300     *
301     * @param original array to copy
302     * @exception NullArgumentException if original is null
303     * @since 2.0
304     */
305    public ResizableDoubleArray(final ResizableDoubleArray original)
306        throws NullArgumentException {
307        MathUtils.checkNotNull(original);
308        this.contractionCriterion = original.contractionCriterion;
309        this.expansionFactor = original.expansionFactor;
310        this.expansionMode = original.expansionMode;
311        this.internalArray = new double[original.internalArray.length];
312        System.arraycopy(original.internalArray, 0, this.internalArray, 0, this.internalArray.length);
313        this.numElements = original.numElements;
314        this.startIndex = original.startIndex;
315    }
316
317    /**
318     * Adds an element to the end of this expandable array.
319     *
320     * @param value Value to be added to end of array.
321     */
322    @Override
323    public void addElement(final double value) {
324        if (internalArray.length <= startIndex + numElements) {
325            expand();
326        }
327        internalArray[startIndex + numElements++] = value;
328    }
329
330    /**
331     * Adds several element to the end of this expandable array.
332     *
333     * @param values Values to be added to end of array.
334     * @since 2.2
335     */
336    @Override
337    public void addElements(final double[] values) {
338        final double[] tempArray = new double[numElements + values.length + 1];
339        System.arraycopy(internalArray, startIndex, tempArray, 0, numElements);
340        System.arraycopy(values, 0, tempArray, numElements, values.length);
341        internalArray = tempArray;
342        startIndex = 0;
343        numElements += values.length;
344    }
345
346    /**
347     * Adds an element to the end of the array and removes the first
348     * element in the array.  Returns the discarded first element.
349     * <p>
350     * The effect is similar to a push operation in a FIFO queue.
351     * <p>
352     * Example: If the array contains the elements 1, 2, 3, 4 (in that order)
353     * and addElementRolling(5) is invoked, the result is an array containing
354     * the entries 2, 3, 4, 5 and the value returned is 1.
355     *
356     * @param value Value to be added to the array.
357     * @return the value which has been discarded or "pushed" out of the array
358     * by this rolling insert.
359     */
360    @Override
361    public double addElementRolling(double value) {
362        double discarded = internalArray[startIndex];
363
364        if ((startIndex + (numElements + 1)) > internalArray.length) {
365            expand();
366        }
367        // Increment the start index
368        startIndex += 1;
369
370        // Add the new value
371        internalArray[startIndex + (numElements - 1)] = value;
372
373        // Check the contraction criterion.
374        if (shouldContract()) {
375            contract();
376        }
377        return discarded;
378    }
379
380    /**
381     * Substitutes {@code value} for the most recently added value.
382     * <p>
383     * Returns the value that has been replaced. If the array is empty (i.e.
384     * if {@link #numElements} is zero), an MathIllegalStateException is thrown.
385     *
386     * @param value New value to substitute for the most recently added value
387     * @return the value that has been replaced in the array.
388     * @throws MathIllegalStateException if the array is empty
389     * @since 2.0
390     */
391    public double substituteMostRecentElement(double value) throws MathIllegalStateException {
392        if (numElements < 1) {
393            throw new MathIllegalStateException(LocalizedFormats.CANNOT_SUBSTITUTE_ELEMENT_FROM_EMPTY_ARRAY);
394        }
395
396        final int substIndex = startIndex + (numElements - 1);
397        final double discarded = internalArray[substIndex];
398
399        internalArray[substIndex] = value;
400
401        return discarded;
402    }
403
404    /**
405     * Checks the expansion factor and the contraction criterion and raises
406     * an exception if the contraction criterion is smaller than the
407     * expansion criterion.
408     *
409     * @param contraction Criterion to be checked.
410     * @param expansion Factor to be checked.
411     * @throws NumberIsTooSmallException if {@code contraction < expansion}.
412     * @throws NumberIsTooSmallException if {@code contraction <= 1}.
413     * @throws NumberIsTooSmallException if {@code expansion <= 1 }.
414     * @since 3.1
415     */
416    protected void checkContractExpand(double contraction, double expansion) throws NumberIsTooSmallException {
417        if (contraction < expansion) {
418            final NumberIsTooSmallException e = new NumberIsTooSmallException(contraction, 1, true);
419            e.getContext().addMessage(LocalizedFormats.CONTRACTION_CRITERIA_SMALLER_THAN_EXPANSION_FACTOR,
420                                      contraction, expansion);
421            throw e;
422        }
423
424        if (contraction <= 1) {
425            final NumberIsTooSmallException e = new NumberIsTooSmallException(contraction, 1, false);
426            e.getContext().addMessage(LocalizedFormats.CONTRACTION_CRITERIA_SMALLER_THAN_ONE,
427                                      contraction);
428            throw e;
429        }
430
431        if (expansion <= 1) {
432            final NumberIsTooSmallException e = new NumberIsTooSmallException(contraction, 1, false);
433            e.getContext().addMessage(LocalizedFormats.EXPANSION_FACTOR_SMALLER_THAN_ONE,
434                                      expansion);
435            throw e;
436        }
437    }
438
439    /**
440     * Clear the array contents, resetting the number of elements to zero.
441     */
442    @Override
443    public void clear() {
444        numElements = 0;
445        startIndex = 0;
446    }
447
448    /**
449     * Contracts the storage array to the (size of the element set) + 1 - to avoid
450     * a zero length array. This function also resets the startIndex to zero.
451     */
452    public void contract() {
453        final double[] tempArray = new double[numElements + 1];
454
455        // Copy and swap - copy only the element array from the src array.
456        System.arraycopy(internalArray, startIndex, tempArray, 0, numElements);
457        internalArray = tempArray;
458
459        // Reset the start index to zero
460        startIndex = 0;
461    }
462
463    /**
464     * Discards the {@code i} initial elements of the array.
465     * <p>
466     * For example, if the array contains the elements 1,2,3,4, invoking
467     * {@code discardFrontElements(2)} will cause the first two elements
468     * to be discarded, leaving 3,4 in the array.
469     *
470     * @param i  the number of elements to discard from the front of the array
471     * @throws MathIllegalArgumentException if i is greater than numElements.
472     * @since 2.0
473     */
474    public void discardFrontElements(int i) throws MathIllegalArgumentException {
475        discardExtremeElements(i,true);
476    }
477
478    /**
479     * Discards the {@code i} last elements of the array.
480     * <p>
481     * For example, if the array contains the elements 1,2,3,4, invoking
482     * {@code discardMostRecentElements(2)} will cause the last two elements
483     * to be discarded, leaving 1,2 in the array.
484     *
485     * @param i  the number of elements to discard from the end of the array
486     * @throws MathIllegalArgumentException if i is greater than numElements.
487     * @since 2.0
488     */
489    public void discardMostRecentElements(int i) throws MathIllegalArgumentException {
490        discardExtremeElements(i,false);
491    }
492
493    /**
494     * Discards the {@code i} first or last elements of the array,
495     * depending on the value of {@code front}.
496     * <p>
497     * For example, if the array contains the elements 1,2,3,4, invoking
498     * {@code discardExtremeElements(2,false)} will cause the last two elements
499     * to be discarded, leaving 1,2 in the array.
500     * For example, if the array contains the elements 1,2,3,4, invoking
501     * {@code discardExtremeElements(2,true)} will cause the first two elements
502     * to be discarded, leaving 3,4 in the array.
503     *
504     * @param i  the number of elements to discard from the front/end of the array
505     * @param front true if elements are to be discarded from the front
506     * of the array, false if elements are to be discarded from the end
507     * of the array
508     * @throws MathIllegalArgumentException if i is greater than numElements.
509     * @since 2.0
510     */
511    private void discardExtremeElements(int i, boolean front) throws MathIllegalArgumentException {
512        if (i > numElements) {
513            throw new MathIllegalArgumentException(
514                    LocalizedFormats.TOO_MANY_ELEMENTS_TO_DISCARD_FROM_ARRAY,
515                    i, numElements);
516       } else if (i < 0) {
517           throw new MathIllegalArgumentException(
518                   LocalizedFormats.CANNOT_DISCARD_NEGATIVE_NUMBER_OF_ELEMENTS,
519                   i);
520        } else {
521            // "Subtract" this number of discarded from numElements
522            numElements -= i;
523            if (front) {
524                startIndex += i;
525            }
526        }
527        if (shouldContract()) {
528            contract();
529        }
530    }
531
532    /**
533     * Expands the internal storage array using the expansion factor.
534     * <p>
535     * If {@code expansionMode} is set to MULTIPLICATIVE,
536     * the new array size will be {@code internalArray.length * expansionFactor}.
537     * If {@code expansionMode} is set to ADDITIVE, the length
538     * after expansion will be {@code internalArray.length + expansionFactor}.
539     */
540    protected void expand() {
541        // notice the use of FastMath.ceil(), this guarantees that we will always
542        // have an array of at least currentSize + 1.   Assume that the
543        // current initial capacity is 1 and the expansion factor
544        // is 1.000000000000000001.  The newly calculated size will be
545        // rounded up to 2 after the multiplication is performed.
546        int newSize = 0;
547        if (expansionMode == ExpansionMode.MULTIPLICATIVE) {
548            newSize = (int) FastMath.ceil(internalArray.length * expansionFactor);
549        } else {
550            newSize = (int) (internalArray.length + FastMath.round(expansionFactor));
551        }
552        final double[] tempArray = new double[newSize];
553
554        // Copy and swap
555        System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
556        internalArray = tempArray;
557    }
558
559    /**
560     * Expands the internal storage array to the specified size.
561     *
562     * @param size Size of the new internal storage array.
563     */
564    private void expandTo(int size) {
565        final double[] tempArray = new double[size];
566        // Copy and swap
567        System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
568        internalArray = tempArray;
569    }
570
571    /**
572     * The contraction criterion defines when the internal array will contract
573     * to store only the number of elements in the element array.
574     * <p>
575     * If the {@code expansionMode} is {@code MULTIPLICATIVE},
576     * contraction is triggered when the ratio between storage array length
577     * and {@code numElements} exceeds {@code contractionFactor}.
578     * If the {@code expansionMode} is {@code ADDITIVE}, the
579     * number of excess storage locations is compared to {@code contractionFactor}.
580     *
581     * @return the contraction criterion used to reclaim memory.
582     * @since 3.1
583     */
584    public double getContractionCriterion() {
585        return contractionCriterion;
586    }
587
588    /**
589     * Returns the element at the specified index.
590     *
591     * @param index index to fetch a value from
592     * @return value stored at the specified index
593     * @throws ArrayIndexOutOfBoundsException if {@code index} is less than
594     * zero or is greater than {@code getNumElements() - 1}.
595     */
596    @Override
597    public double getElement(int index) {
598        if (index >= numElements) {
599            throw new ArrayIndexOutOfBoundsException(index);
600        } else if (index >= 0) {
601            return internalArray[startIndex + index];
602        } else {
603            throw new ArrayIndexOutOfBoundsException(index);
604        }
605    }
606
607     /**
608     * Returns a double array containing the elements of this ResizableArray.
609     * <p>
610     * This method returns a copy, not a reference to the underlying array,
611     * so that changes made to the returned array have no effect on this ResizableArray.
612     *
613     * @return the double array.
614     */
615    @Override
616    public double[] getElements() {
617        final double[] elementArray = new double[numElements];
618        System.arraycopy(internalArray, startIndex, elementArray, 0, numElements);
619        return elementArray;
620    }
621
622    /**
623     * The expansion factor controls the size of a new array when an array
624     * needs to be expanded.
625     * <p>
626     * The {@code expansionMode} determines whether the size of the array
627     * is multiplied by the {@code expansionFactor} (MULTIPLICATIVE) or if
628     * the expansion is additive (ADDITIVE -- {@code expansionFactor}
629     * storage locations added).  The default {@code expansionMode} is
630     * MULTIPLICATIVE and the default {@code expansionFactor} is 2.0.
631     *
632     * @return the expansion factor of this expandable double array
633     */
634    public double getExpansionFactor() {
635        return expansionFactor;
636    }
637
638    /**
639     * The expansion mode determines whether the internal storage
640     * array grows additively or multiplicatively when it is expanded.
641     *
642     * @return the expansion mode.
643     */
644    public ExpansionMode getExpansionMode() {
645        return expansionMode;
646    }
647
648    /**
649     * Gets the currently allocated size of the internal data structure used
650     * for storing elements.
651     * This is not to be confused with {@link #getNumElements() the number of
652     * elements actually stored}.
653     *
654     * @return the length of the internal array.
655     * @since 3.1
656     */
657    public int getCapacity() {
658        return internalArray.length;
659    }
660
661    /**
662     * Returns the number of elements currently in the array.  Please note
663     * that this is different from the length of the internal storage array.
664     *
665     * @return the number of elements.
666     */
667    @Override
668    public int getNumElements() {
669        return numElements;
670    }
671
672    /**
673     * Provides <em>direct</em> access to the internal storage array.
674     * Please note that this method returns a reference to this object's
675     * storage array, not a copy.
676     * <p>
677     * To correctly address elements of the array, the "start index" is
678     * required (available via the {@link #getStartIndex() getStartIndex}
679     * method.
680     * <p>
681     * This method should only be used to avoid copying the internal array.
682     * The returned value <em>must</em> be used for reading only; other
683     * uses could lead to this object becoming inconsistent.
684     * <p>
685     * The {@link #getElements} method has no such limitation since it
686     * returns a copy of this array's addressable elements.
687     *
688     * @return the internal storage array used by this object.
689     * @since 3.1
690     */
691    protected double[] getArrayRef() {
692        return internalArray;
693    }
694
695    /**
696     * Returns the "start index" of the internal array.
697     * This index is the position of the first addressable element in the
698     * internal storage array.
699     * <p>
700     * The addressable elements in the array are at indices contained in
701     * the interval [{@link #getStartIndex()},
702     *               {@link #getStartIndex()} + {@link #getNumElements()} - 1].
703     *
704     * @return the start index.
705     * @since 3.1
706     */
707    protected int getStartIndex() {
708        return startIndex;
709    }
710
711    /**
712     * Performs an operation on the addressable elements of the array.
713     *
714     * @param f Function to be applied on this array.
715     * @return the result.
716     * @since 3.1
717     */
718    public double compute(MathArrays.Function f) {
719        return f.evaluate(internalArray, startIndex, numElements);
720    }
721
722    /**
723     * Sets the element at the specified index.
724     * <p>
725     * If the specified index is greater than {@code getNumElements() - 1},
726     * the {@code numElements} property is increased to {@code index +1}
727     * and additional storage is allocated (if necessary) for the new element and
728     * all (uninitialized) elements between the new element and the previous end
729     * of the array).
730     *
731     * @param index index to store a value in
732     * @param value value to store at the specified index
733     * @throws ArrayIndexOutOfBoundsException if {@code index < 0}.
734     */
735    @Override
736    public void setElement(int index, double value) {
737        if (index < 0) {
738            throw new ArrayIndexOutOfBoundsException(index);
739        }
740        if (index + 1 > numElements) {
741            numElements = index + 1;
742        }
743        if ((startIndex + index) >= internalArray.length) {
744            expandTo(startIndex + (index + 1));
745        }
746        internalArray[startIndex + index] = value;
747    }
748
749    /**
750     * This function allows you to control the number of elements contained
751     * in this array, and can be used to "throw out" the last n values in an
752     * array. This function will also expand the internal array as needed.
753     *
754     * @param i a new number of elements
755     * @throws MathIllegalArgumentException if {@code i} is negative.
756     */
757    public void setNumElements(int i) throws MathIllegalArgumentException {
758        // If index is negative thrown an error.
759        if (i < 0) {
760            throw new MathIllegalArgumentException(LocalizedFormats.INDEX_NOT_POSITIVE, i);
761        }
762
763        // Test the new num elements, check to see if the array needs to be
764        // expanded to accommodate this new number of elements.
765        final int newSize = startIndex + i;
766        if (newSize > internalArray.length) {
767            expandTo(newSize);
768        }
769
770        // Set the new number of elements to new value.
771        numElements = i;
772    }
773
774    /**
775     * Returns true if the internal storage array has too many unused
776     * storage positions.
777     *
778     * @return true if array satisfies the contraction criteria
779     */
780    private boolean shouldContract() {
781        if (expansionMode == ExpansionMode.MULTIPLICATIVE) {
782            return (internalArray.length / ((float) numElements)) > contractionCriterion;
783        } else {
784            return (internalArray.length - numElements) > contractionCriterion;
785        }
786    }
787
788    /**
789     * Returns a copy of the ResizableDoubleArray.  Does not contract before
790     * the copy, so the returned object is an exact copy of this.
791     *
792     * @return a new ResizableDoubleArray with the same data and configuration
793     * properties as this
794     * @since 2.0
795     */
796    public ResizableDoubleArray copy() {
797        return new ResizableDoubleArray(this);
798    }
799
800    /**
801     * Returns true iff object is a ResizableDoubleArray with the same properties
802     * as this and an identical internal storage array.
803     *
804     * @param object object to be compared for equality with this
805     * @return true iff object is a ResizableDoubleArray with the same data and
806     * properties as this
807     * @since 2.0
808     */
809    @Override
810    public boolean equals(Object object) {
811        if (object == this ) {
812            return true;
813        }
814        if (object instanceof ResizableDoubleArray == false) {
815            return false;
816        }
817        boolean result = true;
818        final ResizableDoubleArray other = (ResizableDoubleArray) object;
819        result = result && (other.contractionCriterion == contractionCriterion);
820        result = result && (other.expansionFactor == expansionFactor);
821        result = result && (other.expansionMode == expansionMode);
822        result = result && (other.numElements == numElements);
823        result = result && (other.startIndex == startIndex);
824        if (!result) {
825            return false;
826        } else {
827            return Arrays.equals(internalArray, other.internalArray);
828        }
829    }
830
831    /**
832     * Returns a hash code consistent with equals.
833     *
834     * @return the hash code representing this {@code ResizableDoubleArray}.
835     * @since 2.0
836     */
837    @Override
838    public int hashCode() {
839        final int[] hashData = new int[6];
840        hashData[0] = Double.valueOf(expansionFactor).hashCode();
841        hashData[1] = Double.valueOf(contractionCriterion).hashCode();
842        hashData[2] = expansionMode.hashCode();
843        hashData[3] = Arrays.hashCode(internalArray);
844        hashData[4] = numElements;
845        hashData[5] = startIndex;
846        return Arrays.hashCode(hashData);
847    }
848
849}