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
9
* http://www.apache.org/licenses/LICENSE-2.0
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.
17
package org.apache.commons.math.util;
19
import java.io.Serializable;
23
* A variable length {@link DoubleArray} implementation that automatically
24
* handles expanding and contracting its internal storage array as elements
25
* are added and removed.
28
* The internal storage array starts with capacity determined by the
29
* <code>initialCapacity</code> property, which can be set by the constructor.
30
* The default initial capacity is 16. Adding elements using
31
* {@link #addElement(double)} appends elements to the end of the array. When
32
* there are no open entries at the end of the internal storage array, the
33
* array is expanded. The size of the expanded array depends on the
34
* <code>expansionMode</code> and <code>expansionFactor</code> properties.
35
* The <code>expansionMode</code> determines whether the size of the array is
36
* multiplied by the <code>expansionFactor</code> (MULTIPLICATIVE_MODE) or if
37
* the expansion is additive (ADDITIVE_MODE -- <code>expansionFactor</code>
38
* storage locations added). The default <code>expansionMode</code> is
39
* MULTIPLICATIVE_MODE and the default <code>expansionFactor</code>
43
* The {@link #addElementRolling(double)} method adds a new element to the end
44
* of the internal storage array and adjusts the "usable window" of the
45
* internal array forward by one position (effectively making what was the
46
* second element the first, and so on). Repeated activations of this method
47
* (or activation of {@link #discardFrontElements(int)}) will effectively orphan
48
* the storage locations at the beginning of the internal storage array. To
49
* reclaim this storage, each time one of these methods is activated, the size
50
* of the internal storage array is compared to the number of addressable
51
* elements (the <code>numElements</code> property) and if the difference
52
* is too large, the internal array is contracted to size
53
* <code>numElements + 1.</code> The determination of when the internal
54
* storage array is "too large" depends on the <code>expansionMode</code> and
55
* <code>contractionFactor</code> properties. If the <code>expansionMode</code>
56
* is <code>MULTIPLICATIVE_MODE</code>, contraction is triggered when the
57
* ratio between storage array length and <code>numElements</code> exceeds
58
* <code>contractionFactor.</code> If the <code>expansionMode</code>
59
* is <code>ADDITIVE_MODE,</code> the number of excess storage locations
60
* is compared to <code>contractionFactor.</code>
63
* To avoid cycles of expansions and contractions, the
64
* <code>expansionFactor</code> must not exceed the
65
* <code>contractionFactor.</code> Constructors and mutators for both of these
66
* properties enforce this requirement, throwing IllegalArgumentException if it
69
* @version $Revision: 618057 $ $Date: 2008-02-03 11:58:54 -0700 (Sun, 03 Feb 2008) $
71
public class ResizableDoubleArray implements DoubleArray, Serializable {
73
/** Serializable version identifier */
74
private static final long serialVersionUID = -3485529955529426875L;
76
/** additive expansion mode */
77
public static final int ADDITIVE_MODE = 1;
79
/** multiplicative expansion mode */
80
public static final int MULTIPLICATIVE_MODE = 0;
83
* The contraction criteria determines when the internal array will be
84
* contracted to fit the number of elements contained in the element
87
protected float contractionCriteria = 2.5f;
90
* The expansion factor of the array. When the array needs to be expanded,
91
* the new array size will be
92
* <code>internalArray.length * expansionFactor</code>
93
* if <code>expansionMode</code> is set to MULTIPLICATIVE_MODE, or
94
* <code>internalArray.length + expansionFactor</code> if
95
* <code>expansionMode</code> is set to ADDITIVE_MODE.
97
protected float expansionFactor = 2.0f;
100
* Determines whether array expansion by <code>expansionFactor</code>
101
* is additive or multiplicative.
103
protected int expansionMode = MULTIPLICATIVE_MODE;
106
* The initial capacity of the array. Initial capacity is not exposed as a
107
* property as it is only meaningful when passed to a constructor.
109
protected int initialCapacity = 16;
112
* The internal storage array.
114
protected double[] internalArray;
117
* The number of addressable elements in the array. Note that this
118
* has nothing to do with the length of the internal storage array.
120
protected int numElements = 0;
123
* The position of the first addressable element in the internal storage
124
* array. The addressable elements in the array are <code>
125
* internalArray[startIndex],...,internalArray[startIndex + numElements -1]
128
protected int startIndex = 0;
131
* Create a ResizableArray with default properties.
133
* <li><code>initialCapacity = 16</code></li>
134
* <li><code>expansionMode = MULTIPLICATIVE_MODE</code></li>
135
* <li><code>expansionFactor = 2.5</code></li>
136
* <li><code>contractionFactor = 2.0</code></li>
139
public ResizableDoubleArray() {
140
internalArray = new double[initialCapacity];
144
* Create a ResizableArray with the specified initial capacity. Other
145
* properties take default values:
147
* <li><code>expansionMode = MULTIPLICATIVE_MODE</code></li>
148
* <li><code>expansionFactor = 2.5</code></li>
149
* <li><code>contractionFactor = 2.0</code></li>
151
* @param initialCapacity The initial size of the internal storage array
152
* @throws IllegalArgumentException if initialCapacity is not > 0
154
public ResizableDoubleArray(int initialCapacity) {
155
setInitialCapacity(initialCapacity);
156
internalArray = new double[this.initialCapacity];
161
* Create a ResizableArray with the specified initial capacity
162
* and expansion factor. The remaining properties take default
165
* <li><code>expansionMode = MULTIPLICATIVE_MODE</code></li>
166
* <li><code>contractionFactor = 0.5 + expansionFactor</code></li>
169
* Throws IllegalArgumentException if the following conditions are
172
* <li><code>initialCapacity > 0</code></li>
173
* <li><code>expansionFactor > 1</code></li>
176
* @param initialCapacity The initial size of the internal storage array
177
* @param expansionFactor the array will be expanded based on this
179
* @throws IllegalArgumentException if parameters are not valid
181
public ResizableDoubleArray(int initialCapacity, float expansionFactor) {
182
this.expansionFactor = expansionFactor;
183
setInitialCapacity(initialCapacity);
184
internalArray = new double[initialCapacity];
185
setContractionCriteria(expansionFactor +0.5f);
190
* Create a ResizableArray with the specified initialCapacity,
191
* expansionFactor, and contractionCriteria. The <code>expansionMode</code>
192
* will default to <code>MULTIPLICATIVE_MODE.</code></p>
194
* Throws IllegalArgumentException if the following conditions are
197
* <li><code>initialCapacity > 0</code></li>
198
* <li><code>expansionFactor > 1</code></li>
199
* <li><code>contractionFactor >= expansionFactor</code></li>
201
* @param initialCapacity The initial size of the internal storage array
202
* @param expansionFactor the array will be expanded based on this
204
* @param contractionCriteria The contraction Criteria.
205
* @throws IllegalArgumentException if parameters are not valid
207
public ResizableDoubleArray(int initialCapacity, float expansionFactor,
208
float contractionCriteria) {
209
this.expansionFactor = expansionFactor;
210
setContractionCriteria(contractionCriteria);
211
setInitialCapacity(initialCapacity);
212
internalArray = new double[initialCapacity];
217
* Create a ResizableArray with the specified properties.</p>
219
* Throws IllegalArgumentException if the following conditions are
222
* <li><code>initialCapacity > 0</code></li>
223
* <li><code>expansionFactor > 1</code></li>
224
* <li><code>contractionFactor >= expansionFactor</code></li>
225
* <li><code>expansionMode in {MULTIPLICATIVE_MODE, ADDITIVE_MODE}</code>
229
* @param initialCapacity the initial size of the internal storage array
230
* @param expansionFactor the array will be expanded based on this
232
* @param contractionCriteria the contraction Criteria
233
* @param expansionMode the expansion mode
234
* @throws IllegalArgumentException if parameters are not valid
236
public ResizableDoubleArray(int initialCapacity, float expansionFactor,
237
float contractionCriteria, int expansionMode) {
238
this.expansionFactor = expansionFactor;
239
setContractionCriteria(contractionCriteria);
240
setInitialCapacity(initialCapacity);
241
setExpansionMode(expansionMode);
242
internalArray = new double[initialCapacity];
246
* Adds an element to the end of this expandable array.
248
* @param value to be added to end of array
250
public synchronized void addElement(double value) {
252
if ((startIndex + numElements) > internalArray.length) {
255
internalArray[startIndex + (numElements - 1)] = value;
256
if (shouldContract()) {
263
* Adds an element to the end of the array and removes the first
264
* element in the array. Returns the discarded first element.
265
* The effect is similar to a push operation in a FIFO queue.
268
* Example: If the array contains the elements 1, 2, 3, 4 (in that order)
269
* and addElementRolling(5) is invoked, the result is an array containing
270
* the entries 2, 3, 4, 5 and the value returned is 1.
273
* @param value the value to be added to the array
274
* @return the value which has been discarded or "pushed" out of the array
275
* by this rolling insert
277
public synchronized double addElementRolling(double value) {
278
double discarded = internalArray[startIndex];
280
if ((startIndex + (numElements + 1)) > internalArray.length) {
283
// Increment the start index
287
internalArray[startIndex + (numElements - 1)] = value;
289
// Check the contraction criteria
290
if (shouldContract()) {
297
* Checks the expansion factor and the contraction criteria and throws an
298
* IllegalArgumentException if the contractionCriteria is less than the
301
* @param expansionFactor factor to be checked
302
* @param contractionCritera critera to be checked
303
* @throws IllegalArgumentException if the contractionCriteria is less than
304
* the expansionCriteria.
306
protected void checkContractExpand(
307
float contractionCritera,
308
float expansionFactor) {
310
if (contractionCritera < expansionFactor) {
312
"Contraction criteria can never be smaller than " +
313
"the expansion factor. This would lead to a never " +
314
"ending loop of expansion and contraction as a newly " +
315
"expanded internal storage array would immediately " +
316
"satisfy the criteria for contraction";
317
throw new IllegalArgumentException(msg);
320
if (contractionCriteria <= 1.0) {
322
"The contraction criteria must be a number larger " +
323
"than one. If the contractionCriteria is less than or " +
324
"equal to one an endless loop of contraction and " +
325
"expansion would ensue as an internalArray.length " +
326
"== numElements would satisfy the contraction criteria";
327
throw new IllegalArgumentException(msg);
330
if (expansionFactor <= 1.0) {
332
"The expansion factor must be a number greater than 1.0";
333
throw new IllegalArgumentException(msg);
338
* Clear the array, reset the size to the initialCapacity and the number
339
* of elements to zero.
341
public synchronized void clear() {
343
internalArray = new double[initialCapacity];
347
* Contracts the storage array to the (size of the element set) + 1 - to
348
* avoid a zero length array. This function also resets the startIndex to
351
public synchronized void contract() {
352
double[] tempArray = new double[numElements + 1];
354
// Copy and swap - copy only the element array from the src array.
355
System.arraycopy(internalArray, startIndex, tempArray, 0, numElements);
356
internalArray = tempArray;
358
// Reset the start index to zero
363
* Discards the <code>i<code> initial elements of the array. For example,
364
* if the array contains the elements 1,2,3,4, invoking
365
* <code>discardFrontElements(2)</code> will cause the first two elements
366
* to be discarded, leaving 3,4 in the array. Throws illegalArgumentException
367
* if i exceeds numElements.
369
* @param i the number of elements to discard from the front of the array
370
* @throws IllegalArgumentException if i is greater than numElements.
372
public synchronized void discardFrontElements(int i) {
373
if (i > numElements) {
374
String msg = "Cannot discard more elements than are" +
375
"contained in this array.";
376
throw new IllegalArgumentException(msg);
378
String msg = "Cannot discard a negative number of elements.";
379
throw new IllegalArgumentException(msg);
381
// "Subtract" this number of discarded from numElements
385
if (shouldContract()) {
391
* Expands the internal storage array using the expansion factor.
393
* if <code>expansionMode</code> is set to MULTIPLICATIVE_MODE,
394
* the new array size will be <code>internalArray.length * expansionFactor.</code>
395
* If <code>expansionMode</code> is set to ADDITIVE_MODE, the length
396
* after expansion will be <code>internalArray.length + expansionFactor</code>
399
protected synchronized void expand() {
401
// notice the use of Math.ceil(), this gaurantees that we will always
402
// have an array of at least currentSize + 1. Assume that the
403
// current initial capacity is 1 and the expansion factor
404
// is 1.000000000000000001. The newly calculated size will be
405
// rounded up to 2 after the multiplication is performed.
407
if (expansionMode == MULTIPLICATIVE_MODE) {
408
newSize = (int) Math.ceil(internalArray.length * expansionFactor);
410
newSize = internalArray.length + Math.round(expansionFactor);
412
double[] tempArray = new double[newSize];
415
System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
416
internalArray = tempArray;
420
* Expands the internal storage array to the specified size.
422
* @param size Size of the new internal storage array
424
private synchronized void expandTo(int size) {
425
double[] tempArray = new double[size];
427
System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length);
428
internalArray = tempArray;
432
* The contraction criteria defines when the internal array will contract
433
* to store only the number of elements in the element array.
434
* If the <code>expansionMode</code> is <code>MULTIPLICATIVE_MODE</code>,
435
* contraction is triggered when the ratio between storage array length
436
* and <code>numElements</code> exceeds <code>contractionFactor</code>.
437
* If the <code>expansionMode</code> is <code>ADDITIVE_MODE</code>, the
438
* number of excess storage locations is compared to
439
* <code>contractionFactor.</code>
441
* @return the contraction criteria used to reclaim memory.
443
public float getContractionCriteria() {
444
return contractionCriteria;
448
* Returns the element at the specified index
450
* @param index index to fetch a value from
451
* @return value stored at the specified index
452
* @throws ArrayIndexOutOfBoundsException if <code>index</code> is less than
453
* zero or is greater than <code>getNumElements() - 1</code>.
455
public synchronized double getElement(int index) {
456
if (index >= numElements) {
458
"The index specified: " + index +
459
" is larger than the current number of elements";
460
throw new ArrayIndexOutOfBoundsException(msg);
461
} else if (index >= 0) {
462
return internalArray[startIndex + index];
465
"Elements cannot be retrieved from a negative array index";
466
throw new ArrayIndexOutOfBoundsException(msg);
471
* Returns a double array containing the elements of this
472
* <code>ResizableArray</code>. This method returns a copy, not a
473
* reference to the underlying array, so that changes made to the returned
474
* array have no effect on this <code>ResizableArray.</code>
475
* @return the double array.
477
public synchronized double[] getElements() {
478
double[] elementArray = new double[numElements];
479
System.arraycopy( internalArray, startIndex, elementArray, 0,
485
* The expansion factor controls the size of a new aray when an array
486
* needs to be expanded. The <code>expansionMode</code>
487
* determines whether the size of the array is multiplied by the
488
* <code>expansionFactor</code> (MULTIPLICATIVE_MODE) or if
489
* the expansion is additive (ADDITIVE_MODE -- <code>expansionFactor</code>
490
* storage locations added). The default <code>expansionMode</code> is
491
* MULTIPLICATIVE_MODE and the default <code>expansionFactor</code>
494
* @return the expansion factor of this expandable double array
496
public float getExpansionFactor() {
497
return expansionFactor;
501
* The <code>expansionMode</code> determines whether the internal storage
502
* array grows additively (ADDITIVE_MODE) or multiplicatively
503
* (MULTIPLICATIVE_MODE) when it is expanded.
505
* @return Returns the expansionMode.
507
public int getExpansionMode() {
508
return expansionMode;
512
* Notice the package scope on this method. This method is simply here
513
* for the JUnit test, it allows us check if the expansion is working
514
* properly after a number of expansions. This is not meant to be a part
515
* of the public interface of this class.
517
* @return the length of the internal storage array.
519
synchronized int getInternalLength() {
520
return (internalArray.length);
524
* Returns the number of elements currently in the array. Please note
525
* that this is different from the length of the internal storage array.
527
* @return number of elements
529
public synchronized int getNumElements() {
530
return (numElements);
534
* Returns the internal storage array. Note that this method returns
535
* a reference to the internal storage array, not a copy, and to correctly
536
* address elements of the array, the <code>startIndex</code> is
537
* required (available via the {@link #start} method). This method should
538
* only be used in cases where copying the internal array is not practical.
539
* The {@link #getElements} method should be used in all other cases.
542
* @return the internal storage array used by this object
544
public synchronized double[] getValues() {
545
return (internalArray);
549
* Sets the contraction criteria for this ExpandContractDoubleArray.
551
* @param contractionCriteria contraction criteria
553
public void setContractionCriteria(float contractionCriteria) {
554
checkContractExpand(contractionCriteria, getExpansionFactor());
555
this.contractionCriteria = contractionCriteria;
560
* Sets the element at the specified index. If the specified index is greater than
561
* <code>getNumElements() - 1</code>, the <code>numElements</code> property
562
* is increased to <code>index +1</code> and additional storage is allocated
563
* (if necessary) for the new element and all (uninitialized) elements
564
* between the new element and the previous end of the array).
566
* @param index index to store a value in
567
* @param value value to store at the specified index
568
* @throws ArrayIndexOutOfBoundsException if <code>index</code> is less than
571
public synchronized void setElement(int index, double value) {
573
String msg = "Cannot set an element at a negative index";
574
throw new ArrayIndexOutOfBoundsException(msg);
576
if (index + 1 > numElements) {
577
numElements = index + 1;
579
if ((startIndex + index) >= internalArray.length) {
580
expandTo(startIndex + (index + 1));
582
internalArray[startIndex + index] = value;
586
* Sets the expansionFactor. Throws IllegalArgumentException if the
587
* the following conditions are not met:
589
* <li><code>expansionFactor > 1</code></li>
590
* <li><code>contractionFactor >= expansionFactor</code></li>
592
* @param expansionFactor the new expansion factor value.
593
* @throws IllegalArgumentException if expansionFactor is <= 1 or greater
594
* than contractionFactor
596
public void setExpansionFactor(float expansionFactor) {
597
checkContractExpand(getContractionCriteria(), expansionFactor);
598
// The check above verifies that the expansion factor is > 1.0;
599
this.expansionFactor = expansionFactor;
603
* Sets the <code>expansionMode</code>. The specified value must be one of
604
* ADDITIVE_MODE, MULTIPLICATIVE_MODE.
606
* @param expansionMode The expansionMode to set.
607
* @throws IllegalArgumentException if the specified mode value is not valid
609
public void setExpansionMode(int expansionMode) {
610
if (expansionMode != MULTIPLICATIVE_MODE &&
611
expansionMode != ADDITIVE_MODE) {
612
throw new IllegalArgumentException("Illegal expansionMode setting.");
614
this.expansionMode = expansionMode;
618
* Sets the initial capacity. Should only be invoked by constructors.
620
* @param initialCapacity of the array
621
* @throws IllegalArgumentException if <code>initialCapacity</code> is not
624
protected void setInitialCapacity(int initialCapacity) {
625
if (initialCapacity > 0) {
627
this.initialCapacity = initialCapacity;
631
"The initial capacity supplied: " + initialCapacity +
632
"must be a positive integer";
633
throw new IllegalArgumentException(msg);
638
* This function allows you to control the number of elements contained
639
* in this array, and can be used to "throw out" the last n values in an
640
* array. This function will also expand the internal array as needed.
642
* @param i a new number of elements
643
* @throws IllegalArgumentException if <code>i</code> is negative.
645
public synchronized void setNumElements(int i) {
647
// If index is negative thrown an error
650
"Number of elements must be zero or a positive " + "integer";
651
throw new IllegalArgumentException(msg);
654
// Test the new num elements, check to see if the array needs to be
655
// expanded to accomodate this new number of elements
656
if ((startIndex + i) > internalArray.length) {
657
expandTo(startIndex + i);
660
// Set the new number of elements to new value
665
* Returns true if the internal storage array has too many unused
668
* @return true if array satisfies the contraction criteria
670
private synchronized boolean shouldContract() {
671
if (expansionMode == MULTIPLICATIVE_MODE) {
672
return (internalArray.length / ((float) numElements)) > contractionCriteria;
674
return (internalArray.length - numElements) > contractionCriteria;
679
* Returns the starting index of the internal array. The starting index is
680
* the position of the first addressable element in the internal storage
681
* array. The addressable elements in the array are <code>
682
* internalArray[startIndex],...,internalArray[startIndex + numElements -1]
685
* @return starting index
687
public synchronized int start() {
added
removed
src/java/org/apache/commons/math/util/ResizableDoubleArray.java
