1 /* 2 * Copyright 2003-2004 The Apache Software Foundation. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 package org.apache.commons.math.util; 17 18 import java.io.Serializable; 19 20 /** 21 * <p> 22 * A variable length {@link DoubleArray} implementation that automatically 23 * handles expanding and contracting its internal storage array as elements 24 * are added and removed. 25 * </p> 26 * <p> 27 * The internal storage array starts with capacity determined by the 28 * <code>initialCapacity</code> property, which can be set by the constructor. 29 * The default initial capacity is 16. Adding elements using 30 * {@link #addElement(double)} appends elements to the end of the array. When 31 * there are no open entries at the end of the internal storage array, the 32 * array is expanded. The size of the expanded array depends on the 33 * <code>expansionMode</code> and <code>expansionFactor</code> properties. 34 * The <code>expansionMode</code> determines whether the size of the array is 35 * multiplied by the <code>expansionFactor</code> (MULTIPLICATIVE_MODE) or if 36 * the expansion is additive (ADDITIVE_MODE -- <code>expansionFactor</code> 37 * storage locations added). The default <code>expansionMode</code> is 38 * MULTIPLICATIVE_MODE and the default <code>expansionFactor</code> 39 * is 2.0. 40 * </p> 41 * <p> 42 * The {@link #addElementRolling(double)} method adds a new element to the end 43 * of the internal storage array and adjusts the "usable window" of the 44 * internal array forward by one position (effectively making what was the 45 * second element the first, and so on). Repeated activations of this method 46 * (or activation of {@link #discardFrontElements(int)}) will effectively orphan 47 * the storage locations at the beginning of the internal storage array. To 48 * reclaim this storage, each time one of these methods is activated, the size 49 * of the internal storage array is compared to the number of addressable 50 * elements (the <code>numElements</code> property) and if the difference 51 * is too large, the internal array is contracted to size 52 * <code>numElements + 1.</code> The determination of when the internal 53 * storage array is "too large" depends on the <code>expansionMode</code> and 54 * <code>contractionFactor</code> properties. If the <code>expansionMode</code> 55 * is <code>MULTIPLICATIVE_MODE</code>, contraction is triggered when the 56 * ratio between storage array length and <code>numElements</code> exceeds 57 * <code>contractionFactor.</code> If the <code>expansionMode</code> 58 * is <code>ADDITIVE_MODE,</code> the number of excess storage locations 59 * is compared to <code>contractionFactor.</code> 60 * </p> 61 * <p> 62 * To avoid cycles of expansions and contractions, the 63 * <code>expansionFactor</code> must not exceed the 64 * <code>contractionFactor.</code> Constructors and mutators for both of these 65 * properties enforce this requirement, throwing IllegalArgumentException if it 66 * is violated. 67 * </p> 68 * <p> 69 * @version $Revision: 348519 $ $Date: 2005-11-23 12:12:18 -0700 (Wed, 23 Nov 2005) $ 70 */ 71 public class ResizableDoubleArray implements DoubleArray, Serializable { 72 73 /** Serializable version identifier */ 74 private static final long serialVersionUID = -3485529955529426875L; 75 76 /** additive expansion mode */ 77 public static final int ADDITIVE_MODE = 1; 78 79 /** multiplicative expansion mode */ 80 public static final int MULTIPLICATIVE_MODE = 0; 81 82 /** 83 * The contraction criteria determines when the internal array will be 84 * contracted to fit the number of elements contained in the element 85 * array + 1. 86 */ 87 protected float contractionCriteria = 2.5f; 88 89 /** 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. 96 */ 97 protected float expansionFactor = 2.0f; 98 99 /** 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, float expansionFactor) { 182 this.expansionFactor = expansionFactor; 183 setInitialCapacity(initialCapacity); 184 internalArray = new double[initialCapacity]; 185 setContractionCriteria(expansionFactor +0.5f); 186 } 187 188 /** 189 * <p> 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> 193 * <p> 194 * Throws IllegalArgumentException if the following conditions are 195 * not met: 196 * <ul> 197 * <li><code>initialCapacity > 0</code></li> 198 * <li><code>expansionFactor > 1</code></li> 199 * <li><code>contractionFactor >= expansionFactor</code></li> 200 * </ul></p> 201 * @param initialCapacity The initial size of the internal storage array 202 * @param expansionFactor the array will be expanded based on this 203 * parameter 204 * @param contractionCriteria The contraction Criteria. 205 * @throws IllegalArgumentException if parameters are not valid 206 */ 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]; 213 } 214 215 /** 216 * <p> 217 * Create a ResizableArray with the specified properties.</p> 218 * <p> 219 * Throws IllegalArgumentException if the following conditions are 220 * not met: 221 * <ul> 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> 226 * </li> 227 * </ul></p> 228 * 229 * @param initialCapacity the initial size of the internal storage array 230 * @param expansionFactor the array will be expanded based on this 231 * parameter 232 * @param contractionCriteria the contraction Criteria 233 * @param expansionMode the expansion mode 234 * @throws IllegalArgumentException if parameters are not valid 235 */ 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]; 243 } 244 245 /** 246 * Adds an element to the end of this expandable array. 247 * 248 * @param value to be added to end of array 249 */ 250 public synchronized void addElement(double value) { 251 numElements++; 252 if ((startIndex + numElements) > internalArray.length) { 253 expand(); 254 } 255 internalArray[startIndex + (numElements - 1)] = value; 256 if (shouldContract()) { 257 contract(); 258 } 259 } 260 261 /** 262 * <p> 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. 266 * </p> 267 * <p> 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. 271 * </p> 272 * 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 276 */ 277 public synchronized double addElementRolling(double value) { 278 double discarded = internalArray[startIndex]; 279 280 if ((startIndex + (numElements + 1)) > internalArray.length) { 281 expand(); 282 } 283 // Increment the start index 284 startIndex += 1; 285 286 // Add the new value 287 internalArray[startIndex + (numElements - 1)] = value; 288 289 // Check the contraction criteria 290 if (shouldContract()) { 291 contract(); 292 } 293 return discarded; 294 } 295 296 /** 297 * Checks the expansion factor and the contraction criteria and throws an 298 * IllegalArgumentException if the contractionCriteria is less than the 299 * expansionCriteria 300 * 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. 305 */ 306 protected void checkContractExpand( 307 float contractionCritera, 308 float expansionFactor) { 309 310 if (contractionCritera < expansionFactor) { 311 String msg = 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); 318 } 319 320 if (contractionCriteria <= 1.0) { 321 String msg = 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); 328 } 329 330 if (expansionFactor <= 1.0) { 331 String msg = 332 "The expansion factor must be a number greater than 1.0"; 333 throw new IllegalArgumentException(msg); 334 } 335 } 336 337 /** 338 * Clear the array, reset the size to the initialCapacity and the number 339 * of elements to zero. 340 */ 341 public synchronized void clear() { 342 numElements = 0; 343 internalArray = new double[initialCapacity]; 344 } 345 346 /** 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 349 * zero. 350 */ 351 public synchronized void contract() { 352 double[] tempArray = new double[numElements + 1]; 353 354 // Copy and swap - copy only the element array from the src array. 355 System.arraycopy(internalArray, startIndex, tempArray, 0, numElements); 356 internalArray = tempArray; 357 358 // Reset the start index to zero 359 startIndex = 0; 360 } 361 362 /** 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. 368 * 369 * @param i the number of elements to discard from the front of the array 370 * @throws IllegalArgumentException if i is greater than numElements. 371 */ 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); 377 } else if (i < 0) { 378 String msg = "Cannot discard a negative number of elements."; 379 throw new IllegalArgumentException(msg); 380 } else { 381 // "Subtract" this number of discarded from numElements 382 numElements -= i; 383 startIndex += i; 384 } 385 if (shouldContract()) { 386 contract(); 387 } 388 } 389 390 /** 391 * Expands the internal storage array using the expansion factor. 392 * <p> 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> 397 */ 398 protected synchronized void expand() { 399 400 // notice the use of Math.ceil(), this gaurantees that we will always 401 // have an array of at least currentSize + 1. Assume that the 402 // current initial capacity is 1 and the expansion factor 403 // is 1.000000000000000001. The newly calculated size will be 404 // rounded up to 2 after the multiplication is performed. 405 int newSize = 0; 406 if (expansionMode == MULTIPLICATIVE_MODE) { 407 newSize = (int) Math.ceil(internalArray.length * expansionFactor); 408 } else { 409 newSize = internalArray.length + Math.round(expansionFactor); 410 } 411 double[] tempArray = new double[newSize]; 412 413 // Copy and swap 414 System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length); 415 internalArray = tempArray; 416 } 417 418 /** 419 * Expands the internal storage array to the specified size. 420 * 421 * @param size Size of the new internal storage array 422 */ 423 private synchronized void expandTo(int size) { 424 double[] tempArray = new double[size]; 425 // Copy and swap 426 System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length); 427 internalArray = tempArray; 428 } 429 430 /** 431 * The contraction criteria defines when the internal array will contract 432 * to store only the number of elements in the element array. 433 * If the <code>expansionMode</code> is <code>MULTIPLICATIVE_MODE</code>, 434 * contraction is triggered when the ratio between storage array length 435 * and <code>numElements</code> exceeds <code>contractionFactor</code>. 436 * If the <code>expansionMode</code> is <code>ADDITIVE_MODE</code>, the 437 * number of excess storage locations is compared to 438 * <code>contractionFactor.</code> 439 * 440 * @return the contraction criteria used to reclaim memory. 441 */ 442 public float getContractionCriteria() { 443 return contractionCriteria; 444 } 445 446 /** 447 * Returns the element at the specified index 448 * 449 * @param index index to fetch a value from 450 * @return value stored at the specified index 451 * @throws ArrayIndexOutOfBoundsException if <code>index</code> is less than 452 * zero or is greater than <code>getNumElements() - 1</code>. 453 */ 454 public synchronized double getElement(int index) { 455 if (index >= numElements) { 456 String msg = 457 "The index specified: " + index + 458 " is larger than the current number of elements"; 459 throw new ArrayIndexOutOfBoundsException(msg); 460 } else if (index >= 0) { 461 return internalArray[startIndex + index]; 462 } else { 463 String msg = 464 "Elements cannot be retrieved from a negative array index"; 465 throw new ArrayIndexOutOfBoundsException(msg); 466 } 467 } 468 469 /** 470 * Returns a double array containing the elements of this 471 * <code>ResizableArray</code>. This method returns a copy, not a 472 * reference to the underlying array, so that changes made to the returned 473 * array have no effect on this <code>ResizableArray.</code> 474 * @return the double array. 475 */ 476 public synchronized double[] getElements() { 477 double[] elementArray = new double[numElements]; 478 System.arraycopy( internalArray, startIndex, elementArray, 0, 479 numElements); 480 return elementArray; 481 } 482 483 /** 484 * The expansion factor controls the size of a new aray when an array 485 * needs to be expanded. The <code>expansionMode</code> 486 * determines whether the size of the array is multiplied by the 487 * <code>expansionFactor</code> (MULTIPLICATIVE_MODE) or if 488 * the expansion is additive (ADDITIVE_MODE -- <code>expansionFactor</code> 489 * storage locations added). The default <code>expansionMode</code> is 490 * MULTIPLICATIVE_MODE and the default <code>expansionFactor</code> 491 * is 2.0. 492 * 493 * @return the expansion factor of this expandable double array 494 */ 495 public float getExpansionFactor() { 496 return expansionFactor; 497 } 498 499 /** 500 * The <code>expansionMode</code> determines whether the internal storage 501 * array grows additively (ADDITIVE_MODE) or multiplicatively 502 * (MULTIPLICATIVE_MODE) when it is expanded. 503 * 504 * @return Returns the expansionMode. 505 */ 506 public int getExpansionMode() { 507 return expansionMode; 508 } 509 510 /** 511 * Notice the package scope on this method. This method is simply here 512 * for the JUnit test, it allows us check if the expansion is working 513 * properly after a number of expansions. This is not meant to be a part 514 * of the public interface of this class. 515 * 516 * @return the length of the internal storage array. 517 */ 518 synchronized int getInternalLength() { 519 return (internalArray.length); 520 } 521 522 /** 523 * Returns the number of elements currently in the array. Please note 524 * that this is different from the length of the internal storage array. 525 * 526 * @return number of elements 527 */ 528 public synchronized int getNumElements() { 529 return (numElements); 530 } 531 532 /** 533 * Returns the internal storage array. Note that this method returns 534 * a reference to the internal storage array, not a copy, and to correctly 535 * address elements of the array, the <code>startIndex</code> is 536 * required (available via the {@link #start} method). This method should 537 * only be used in cases where copying the internal array is not practical. 538 * The {@link #getElements} method should be used in all other cases. 539 * 540 * 541 * @return the internal storage array used by this object 542 */ 543 public synchronized double[] getValues() { 544 return (internalArray); 545 } 546 547 /** 548 * Sets the contraction criteria for this ExpandContractDoubleArray. 549 * 550 * @param contractionCriteria contraction criteria 551 */ 552 public void setContractionCriteria(float contractionCriteria) { 553 checkContractExpand(contractionCriteria, getExpansionFactor()); 554 this.contractionCriteria = contractionCriteria; 555 } 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("Illegal expansionMode setting."); 612 } 613 this.expansionMode = expansionMode; 614 } 615 616 /** 617 * Sets the initial capacity. Should only be invoked by constructors. 618 * 619 * @param initialCapacity of the array 620 * @throws IllegalArgumentException if <code>initialCapacity</code> is not 621 * positive. 622 */ 623 protected void setInitialCapacity(int initialCapacity) { 624 if (initialCapacity > 0) { 625 this.initialCapacity = initialCapacity; 626 } else { 627 String msg = 628 "The initial capacity supplied: " + initialCapacity + 629 "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 = 647 "Number of elements must be zero or a positive " + "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 }