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