001: /*
002: * Copyright 2003-2004 The Apache Software Foundation.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.math.util;
017:
018: import java.io.Serializable;
019:
020: /**
021: * <p>
022: * A variable length {@link DoubleArray} implementation that automatically
023: * handles expanding and contracting its internal storage array as elements
024: * are added and removed.
025: * </p>
026: * <p>
027: * The internal storage array starts with capacity determined by the
028: * <code>initialCapacity</code> property, which can be set by the constructor.
029: * The default initial capacity is 16. Adding elements using
030: * {@link #addElement(double)} appends elements to the end of the array. When
031: * there are no open entries at the end of the internal storage array, the
032: * array is expanded. The size of the expanded array depends on the
033: * <code>expansionMode</code> and <code>expansionFactor</code> properties.
034: * The <code>expansionMode</code> determines whether the size of the array is
035: * multiplied by the <code>expansionFactor</code> (MULTIPLICATIVE_MODE) or if
036: * the expansion is additive (ADDITIVE_MODE -- <code>expansionFactor</code>
037: * storage locations added). The default <code>expansionMode</code> is
038: * MULTIPLICATIVE_MODE and the default <code>expansionFactor</code>
039: * is 2.0.
040: * </p>
041: * <p>
042: * The {@link #addElementRolling(double)} method adds a new element to the end
043: * of the internal storage array and adjusts the "usable window" of the
044: * internal array forward by one position (effectively making what was the
045: * second element the first, and so on). Repeated activations of this method
046: * (or activation of {@link #discardFrontElements(int)}) will effectively orphan
047: * the storage locations at the beginning of the internal storage array. To
048: * reclaim this storage, each time one of these methods is activated, the size
049: * of the internal storage array is compared to the number of addressable
050: * elements (the <code>numElements</code> property) and if the difference
051: * is too large, the internal array is contracted to size
052: * <code>numElements + 1.</code> The determination of when the internal
053: * storage array is "too large" depends on the <code>expansionMode</code> and
054: * <code>contractionFactor</code> properties. If the <code>expansionMode</code>
055: * is <code>MULTIPLICATIVE_MODE</code>, contraction is triggered when the
056: * ratio between storage array length and <code>numElements</code> exceeds
057: * <code>contractionFactor.</code> If the <code>expansionMode</code>
058: * is <code>ADDITIVE_MODE,</code> the number of excess storage locations
059: * is compared to <code>contractionFactor.</code>
060: * </p>
061: * <p>
062: * To avoid cycles of expansions and contractions, the
063: * <code>expansionFactor</code> must not exceed the
064: * <code>contractionFactor.</code> Constructors and mutators for both of these
065: * properties enforce this requirement, throwing IllegalArgumentException if it
066: * is violated.
067: * </p>
068: * <p>
069: * @version $Revision: 348519 $ $Date: 2005-11-23 12:12:18 -0700 (Wed, 23 Nov 2005) $
070: */
071: public class ResizableDoubleArray implements DoubleArray, Serializable {
072:
073: /** Serializable version identifier */
074: private static final long serialVersionUID = -3485529955529426875L;
075:
076: /** additive expansion mode */
077: public static final int ADDITIVE_MODE = 1;
078:
079: /** multiplicative expansion mode */
080: public static final int MULTIPLICATIVE_MODE = 0;
081:
082: /**
083: * The contraction criteria determines when the internal array will be
084: * contracted to fit the number of elements contained in the element
085: * array + 1.
086: */
087: protected float contractionCriteria = 2.5f;
088:
089: /**
090: * The expansion factor of the array. When the array needs to be expanded,
091: * the new array size will be
092: * <code>internalArray.length * expansionFactor</code>
093: * if <code>expansionMode</code> is set to MULTIPLICATIVE_MODE, or
094: * <code>internalArray.length + expansionFactor</code> if
095: * <code>expansionMode</code> is set to ADDITIVE_MODE.
096: */
097: protected float expansionFactor = 2.0f;
098:
099: /**
100: * Determines whether array expansion by <code>expansionFactor</code>
101: * is additive or multiplicative.
102: */
103: protected int expansionMode = MULTIPLICATIVE_MODE;
104:
105: /**
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.
108: */
109: protected int initialCapacity = 16;
110:
111: /**
112: * The internal storage array.
113: */
114: protected double[] internalArray;
115:
116: /**
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.
119: */
120: protected int numElements = 0;
121:
122: /**
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]
126: * </code>
127: */
128: protected int startIndex = 0;
129:
130: /**
131: * Create a ResizableArray with default properties.
132: * <ul>
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>
137: * </ul>
138: */
139: public ResizableDoubleArray() {
140: internalArray = new double[initialCapacity];
141: }
142:
143: /**
144: * Create a ResizableArray with the specified initial capacity. Other
145: * properties take default values:
146: * <ul>
147: * <li><code>expansionMode = MULTIPLICATIVE_MODE</code></li>
148: * <li><code>expansionFactor = 2.5</code></li>
149: * <li><code>contractionFactor = 2.0</code></li>
150: * </ul>
151: * @param initialCapacity The initial size of the internal storage array
152: * @throws IllegalArgumentException if initialCapacity is not > 0
153: */
154: public ResizableDoubleArray(int initialCapacity) {
155: setInitialCapacity(initialCapacity);
156: internalArray = new double[this .initialCapacity];
157: }
158:
159: /**
160: * <p>
161: * Create a ResizableArray with the specified initial capacity
162: * and expansion factor. The remaining properties take default
163: * values:
164: * <ul>
165: * <li><code>expansionMode = MULTIPLICATIVE_MODE</code></li>
166: * <li><code>contractionFactor = 0.5 + expansionFactor</code></li>
167: * </ul></p>
168: * <p>
169: * Throws IllegalArgumentException if the following conditions are
170: * not met:
171: * <ul>
172: * <li><code>initialCapacity > 0</code></li>
173: * <li><code>expansionFactor > 1</code></li>
174: * </ul></p>
175: *
176: * @param initialCapacity The initial size of the internal storage array
177: * @param expansionFactor the array will be expanded based on this
178: * parameter
179: * @throws IllegalArgumentException if parameters are not valid
180: */
181: public ResizableDoubleArray(int initialCapacity,
182: float expansionFactor) {
183: this .expansionFactor = expansionFactor;
184: setInitialCapacity(initialCapacity);
185: internalArray = new double[initialCapacity];
186: setContractionCriteria(expansionFactor + 0.5f);
187: }
188:
189: /**
190: * <p>
191: * Create a ResizableArray with the specified initialCapacity,
192: * expansionFactor, and contractionCriteria. The <code>expansionMode</code>
193: * will default to <code>MULTIPLICATIVE_MODE.</code></p>
194: * <p>
195: * Throws IllegalArgumentException if the following conditions are
196: * not met:
197: * <ul>
198: * <li><code>initialCapacity > 0</code></li>
199: * <li><code>expansionFactor > 1</code></li>
200: * <li><code>contractionFactor >= expansionFactor</code></li>
201: * </ul></p>
202: * @param initialCapacity The initial size of the internal storage array
203: * @param expansionFactor the array will be expanded based on this
204: * parameter
205: * @param contractionCriteria The contraction Criteria.
206: * @throws IllegalArgumentException if parameters are not valid
207: */
208: public ResizableDoubleArray(int initialCapacity,
209: float expansionFactor, float contractionCriteria) {
210: this .expansionFactor = expansionFactor;
211: setContractionCriteria(contractionCriteria);
212: setInitialCapacity(initialCapacity);
213: internalArray = new double[initialCapacity];
214: }
215:
216: /**
217: * <p>
218: * Create a ResizableArray with the specified properties.</p>
219: * <p>
220: * Throws IllegalArgumentException if the following conditions are
221: * not met:
222: * <ul>
223: * <li><code>initialCapacity > 0</code></li>
224: * <li><code>expansionFactor > 1</code></li>
225: * <li><code>contractionFactor >= expansionFactor</code></li>
226: * <li><code>expansionMode in {MULTIPLICATIVE_MODE, ADDITIVE_MODE}</code>
227: * </li>
228: * </ul></p>
229: *
230: * @param initialCapacity the initial size of the internal storage array
231: * @param expansionFactor the array will be expanded based on this
232: * parameter
233: * @param contractionCriteria the contraction Criteria
234: * @param expansionMode the expansion mode
235: * @throws IllegalArgumentException if parameters are not valid
236: */
237: public ResizableDoubleArray(int initialCapacity,
238: float expansionFactor, float contractionCriteria,
239: int expansionMode) {
240: this .expansionFactor = expansionFactor;
241: setContractionCriteria(contractionCriteria);
242: setInitialCapacity(initialCapacity);
243: setExpansionMode(expansionMode);
244: internalArray = new double[initialCapacity];
245: }
246:
247: /**
248: * Adds an element to the end of this expandable array.
249: *
250: * @param value to be added to end of array
251: */
252: public synchronized void addElement(double value) {
253: numElements++;
254: if ((startIndex + numElements) > internalArray.length) {
255: expand();
256: }
257: internalArray[startIndex + (numElements - 1)] = value;
258: if (shouldContract()) {
259: contract();
260: }
261: }
262:
263: /**
264: * <p>
265: * Adds an element to the end of the array and removes the first
266: * element in the array. Returns the discarded first element.
267: * The effect is similar to a push operation in a FIFO queue.
268: * </p>
269: * <p>
270: * Example: If the array contains the elements 1, 2, 3, 4 (in that order)
271: * and addElementRolling(5) is invoked, the result is an array containing
272: * the entries 2, 3, 4, 5 and the value returned is 1.
273: * </p>
274: *
275: * @param value the value to be added to the array
276: * @return the value which has been discarded or "pushed" out of the array
277: * by this rolling insert
278: */
279: public synchronized double addElementRolling(double value) {
280: double discarded = internalArray[startIndex];
281:
282: if ((startIndex + (numElements + 1)) > internalArray.length) {
283: expand();
284: }
285: // Increment the start index
286: startIndex += 1;
287:
288: // Add the new value
289: internalArray[startIndex + (numElements - 1)] = value;
290:
291: // Check the contraction criteria
292: if (shouldContract()) {
293: contract();
294: }
295: return discarded;
296: }
297:
298: /**
299: * Checks the expansion factor and the contraction criteria and throws an
300: * IllegalArgumentException if the contractionCriteria is less than the
301: * expansionCriteria
302: *
303: * @param expansionFactor factor to be checked
304: * @param contractionCritera critera to be checked
305: * @throws IllegalArgumentException if the contractionCriteria is less than
306: * the expansionCriteria.
307: */
308: protected void checkContractExpand(float contractionCritera,
309: float expansionFactor) {
310:
311: if (contractionCritera < expansionFactor) {
312: String msg = "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);
318: }
319:
320: if (contractionCriteria <= 1.0) {
321: String msg = "The contraction criteria must be a number larger "
322: + "than one. If the contractionCriteria is less than or "
323: + "equal to one an endless loop of contraction and "
324: + "expansion would ensue as an internalArray.length "
325: + "== numElements would satisfy the contraction criteria";
326: throw new IllegalArgumentException(msg);
327: }
328:
329: if (expansionFactor <= 1.0) {
330: String msg = "The expansion factor must be a number greater than 1.0";
331: throw new IllegalArgumentException(msg);
332: }
333: }
334:
335: /**
336: * Clear the array, reset the size to the initialCapacity and the number
337: * of elements to zero.
338: */
339: public synchronized void clear() {
340: numElements = 0;
341: internalArray = new double[initialCapacity];
342: }
343:
344: /**
345: * Contracts the storage array to the (size of the element set) + 1 - to
346: * avoid a zero length array. This function also resets the startIndex to
347: * zero.
348: */
349: public synchronized void contract() {
350: double[] tempArray = new double[numElements + 1];
351:
352: // Copy and swap - copy only the element array from the src array.
353: System.arraycopy(internalArray, startIndex, tempArray, 0,
354: numElements);
355: internalArray = tempArray;
356:
357: // Reset the start index to zero
358: startIndex = 0;
359: }
360:
361: /**
362: * Discards the <code>i<code> initial elements of the array. For example,
363: * if the array contains the elements 1,2,3,4, invoking
364: * <code>discardFrontElements(2)</code> will cause the first two elements
365: * to be discarded, leaving 3,4 in the array. Throws illegalArgumentException
366: * if i exceeds numElements.
367: *
368: * @param i the number of elements to discard from the front of the array
369: * @throws IllegalArgumentException if i is greater than numElements.
370: */
371: public synchronized void discardFrontElements(int i) {
372: if (i > numElements) {
373: String msg = "Cannot discard more elements than are"
374: + "contained in this array.";
375: throw new IllegalArgumentException(msg);
376: } else if (i < 0) {
377: String msg = "Cannot discard a negative number of elements.";
378: throw new IllegalArgumentException(msg);
379: } else {
380: // "Subtract" this number of discarded from numElements
381: numElements -= i;
382: startIndex += i;
383: }
384: if (shouldContract()) {
385: contract();
386: }
387: }
388:
389: /**
390: * Expands the internal storage array using the expansion factor.
391: * <p>
392: * if <code>expansionMode</code> is set to MULTIPLICATIVE_MODE,
393: * the new array size will be <code>internalArray.length * expansionFactor.</code>
394: * If <code>expansionMode</code> is set to ADDITIVE_MODE, the length
395: * after expansion will be <code>internalArray.length + expansionFactor</code>
396: */
397: protected synchronized void expand() {
398:
399: // notice the use of Math.ceil(), this gaurantees that we will always
400: // have an array of at least currentSize + 1. Assume that the
401: // current initial capacity is 1 and the expansion factor
402: // is 1.000000000000000001. The newly calculated size will be
403: // rounded up to 2 after the multiplication is performed.
404: int newSize = 0;
405: if (expansionMode == MULTIPLICATIVE_MODE) {
406: newSize = (int) Math.ceil(internalArray.length
407: * expansionFactor);
408: } else {
409: newSize = internalArray.length
410: + Math.round(expansionFactor);
411: }
412: double[] tempArray = new double[newSize];
413:
414: // Copy and swap
415: System.arraycopy(internalArray, 0, tempArray, 0,
416: internalArray.length);
417: internalArray = tempArray;
418: }
419:
420: /**
421: * Expands the internal storage array to the specified size.
422: *
423: * @param size Size of the new internal storage array
424: */
425: private synchronized void expandTo(int size) {
426: double[] tempArray = new double[size];
427: // Copy and swap
428: System.arraycopy(internalArray, 0, tempArray, 0,
429: internalArray.length);
430: internalArray = tempArray;
431: }
432:
433: /**
434: * The contraction criteria defines when the internal array will contract
435: * to store only the number of elements in the element array.
436: * If the <code>expansionMode</code> is <code>MULTIPLICATIVE_MODE</code>,
437: * contraction is triggered when the ratio between storage array length
438: * and <code>numElements</code> exceeds <code>contractionFactor</code>.
439: * If the <code>expansionMode</code> is <code>ADDITIVE_MODE</code>, the
440: * number of excess storage locations is compared to
441: * <code>contractionFactor.</code>
442: *
443: * @return the contraction criteria used to reclaim memory.
444: */
445: public float getContractionCriteria() {
446: return contractionCriteria;
447: }
448:
449: /**
450: * Returns the element at the specified index
451: *
452: * @param index index to fetch a value from
453: * @return value stored at the specified index
454: * @throws ArrayIndexOutOfBoundsException if <code>index</code> is less than
455: * zero or is greater than <code>getNumElements() - 1</code>.
456: */
457: public synchronized double getElement(int index) {
458: if (index >= numElements) {
459: String msg = "The index specified: " + index
460: + " is larger than the current number of elements";
461: throw new ArrayIndexOutOfBoundsException(msg);
462: } else if (index >= 0) {
463: return internalArray[startIndex + index];
464: } else {
465: String msg = "Elements cannot be retrieved from a negative array index";
466: throw new ArrayIndexOutOfBoundsException(msg);
467: }
468: }
469:
470: /**
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.
476: */
477: public synchronized double[] getElements() {
478: double[] elementArray = new double[numElements];
479: System.arraycopy(internalArray, startIndex, elementArray, 0,
480: numElements);
481: return elementArray;
482: }
483:
484: /**
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>
492: * is 2.0.
493: *
494: * @return the expansion factor of this expandable double array
495: */
496: public float getExpansionFactor() {
497: return expansionFactor;
498: }
499:
500: /**
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.
504: *
505: * @return Returns the expansionMode.
506: */
507: public int getExpansionMode() {
508: return expansionMode;
509: }
510:
511: /**
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.
516: *
517: * @return the length of the internal storage array.
518: */
519: synchronized int getInternalLength() {
520: return (internalArray.length);
521: }
522:
523: /**
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.
526: *
527: * @return number of elements
528: */
529: public synchronized int getNumElements() {
530: return (numElements);
531: }
532:
533: /**
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.
540: *
541: *
542: * @return the internal storage array used by this object
543: */
544: public synchronized double[] getValues() {
545: return (internalArray);
546: }
547:
548: /**
549: * Sets the contraction criteria for this ExpandContractDoubleArray.
550: *
551: * @param contractionCriteria contraction criteria
552: */
553: public void setContractionCriteria(float contractionCriteria) {
554: checkContractExpand(contractionCriteria, getExpansionFactor());
555: this .contractionCriteria = contractionCriteria;
556: }
557:
558: /**
559: * Sets the element at the specified index. If the specified index is greater than
560: * <code>getNumElements() - 1</code>, the <code>numElements</code> property
561: * is increased to <code>index +1</code> and additional storage is allocated
562: * (if necessary) for the new element and all (uninitialized) elements
563: * between the new element and the previous end of the array).
564: *
565: * @param index index to store a value in
566: * @param value value to store at the specified index
567: * @throws ArrayIndexOutOfBoundsException if <code>index</code> is less than
568: * zero.
569: */
570: public synchronized void setElement(int index, double value) {
571: if (index < 0) {
572: String msg = "Cannot set an element at a negative index";
573: throw new ArrayIndexOutOfBoundsException(msg);
574: }
575: if (index + 1 > numElements) {
576: numElements = index + 1;
577: }
578: if ((startIndex + index) >= internalArray.length) {
579: expandTo(startIndex + (index + 1));
580: }
581: internalArray[startIndex + index] = value;
582: }
583:
584: /**
585: * Sets the expansionFactor. Throws IllegalArgumentException if the
586: * the following conditions are not met:
587: * <ul>
588: * <li><code>expansionFactor > 1</code></li>
589: * <li><code>contractionFactor >= expansionFactor</code></li>
590: * </ul>
591: * @param expansionFactor the new expansion factor value.
592: * @throws IllegalArgumentException if expansionFactor is <= 1 or greater
593: * than contractionFactor
594: */
595: public void setExpansionFactor(float expansionFactor) {
596: checkContractExpand(getContractionCriteria(), expansionFactor);
597: // The check above verifies that the expansion factor is > 1.0;
598: this .expansionFactor = expansionFactor;
599: }
600:
601: /**
602: * Sets the <code>expansionMode</code>. The specified value must be one of
603: * ADDITIVE_MODE, MULTIPLICATIVE_MODE.
604: *
605: * @param expansionMode The expansionMode to set.
606: * @throws IllegalArgumentException if the specified mode value is not valid
607: */
608: public void setExpansionMode(int expansionMode) {
609: if (expansionMode != MULTIPLICATIVE_MODE
610: && expansionMode != ADDITIVE_MODE) {
611: throw new IllegalArgumentException(
612: "Illegal expansionMode setting.");
613: }
614: this .expansionMode = expansionMode;
615: }
616:
617: /**
618: * Sets the initial capacity. Should only be invoked by constructors.
619: *
620: * @param initialCapacity of the array
621: * @throws IllegalArgumentException if <code>initialCapacity</code> is not
622: * positive.
623: */
624: protected void setInitialCapacity(int initialCapacity) {
625: if (initialCapacity > 0) {
626: this .initialCapacity = initialCapacity;
627: } else {
628: String msg = "The initial capacity supplied: "
629: + initialCapacity + "must be a positive integer";
630: throw new IllegalArgumentException(msg);
631: }
632: }
633:
634: /**
635: * This function allows you to control the number of elements contained
636: * in this array, and can be used to "throw out" the last n values in an
637: * array. This function will also expand the internal array as needed.
638: *
639: * @param i a new number of elements
640: * @throws IllegalArgumentException if <code>i</code> is negative.
641: */
642: public synchronized void setNumElements(int i) {
643:
644: // If index is negative thrown an error
645: if (i < 0) {
646: String msg = "Number of elements must be zero or a positive "
647: + "integer";
648: throw new IllegalArgumentException(msg);
649: }
650:
651: // Test the new num elements, check to see if the array needs to be
652: // expanded to accomodate this new number of elements
653: if ((startIndex + i) > internalArray.length) {
654: expandTo(startIndex + i);
655: }
656:
657: // Set the new number of elements to new value
658: numElements = i;
659: }
660:
661: /**
662: * Returns true if the internal storage array has too many unused
663: * storage positions.
664: *
665: * @return true if array satisfies the contraction criteria
666: */
667: private synchronized boolean shouldContract() {
668: if (expansionMode == MULTIPLICATIVE_MODE) {
669: return (internalArray.length / numElements) > contractionCriteria;
670: } else {
671: return (internalArray.length - numElements) > contractionCriteria;
672: }
673: }
674:
675: /**
676: * Returns the starting index of the internal array. The starting index is
677: * the position of the first addressable element in the internal storage
678: * array. The addressable elements in the array are <code>
679: * internalArray[startIndex],...,internalArray[startIndex + numElements -1]
680: * </code>
681: *
682: * @return starting index
683: */
684: public synchronized int start() {
685: return startIndex;
686: }
687:
688: }
|