1 /* 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 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 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. 16 */ 17 package org.apache.commons.math.util; 18 19 import java.io.Serializable; 20 21 /** 22 * <p> 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. 26 * </p> 27 * <p> 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> 40 * is 2.0. 41 * </p> 42 * <p> 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> 61 * </p> 62 * <p> 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 67 * is violated. 68 * </p> 69 * @version $Revision: 618057 $ $Date: 2008-02-03 11:58:54 -0700 (Sun, 03 Feb 2008) $ 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 * </p> 398 */ 399 protected synchronized void expand() { 400 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. 406 int newSize = 0; 407 if (expansionMode == MULTIPLICATIVE_MODE) { 408 newSize = (int) Math.ceil(internalArray.length * expansionFactor); 409 } else { 410 newSize = internalArray.length + Math.round(expansionFactor); 411 } 412 double[] tempArray = new double[newSize]; 413 414 // Copy and swap 415 System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length); 416 internalArray = tempArray; 417 } 418 419 /** 420 * Expands the internal storage array to the specified size. 421 * 422 * @param size Size of the new internal storage array 423 */ 424 private synchronized void expandTo(int size) { 425 double[] tempArray = new double[size]; 426 // Copy and swap 427 System.arraycopy(internalArray, 0, tempArray, 0, internalArray.length); 428 internalArray = tempArray; 429 } 430 431 /** 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> 440 * 441 * @return the contraction criteria used to reclaim memory. 442 */ 443 public float getContractionCriteria() { 444 return contractionCriteria; 445 } 446 447 /** 448 * Returns the element at the specified index 449 * 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>. 454 */ 455 public synchronized double getElement(int index) { 456 if (index >= numElements) { 457 String msg = 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]; 463 } else { 464 String msg = 465 "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 /** 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). 565 * 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 569 * zero. 570 */ 571 public synchronized void setElement(int index, double value) { 572 if (index < 0) { 573 String msg = "Cannot set an element at a negative index"; 574 throw new ArrayIndexOutOfBoundsException(msg); 575 } 576 if (index + 1 > numElements) { 577 numElements = index + 1; 578 } 579 if ((startIndex + index) >= internalArray.length) { 580 expandTo(startIndex + (index + 1)); 581 } 582 internalArray[startIndex + index] = value; 583 } 584 585 /** 586 * Sets the expansionFactor. Throws IllegalArgumentException if the 587 * the following conditions are not met: 588 * <ul> 589 * <li><code>expansionFactor > 1</code></li> 590 * <li><code>contractionFactor >= expansionFactor</code></li> 591 * </ul> 592 * @param expansionFactor the new expansion factor value. 593 * @throws IllegalArgumentException if expansionFactor is <= 1 or greater 594 * than contractionFactor 595 */ 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; 600 } 601 602 /** 603 * Sets the <code>expansionMode</code>. The specified value must be one of 604 * ADDITIVE_MODE, MULTIPLICATIVE_MODE. 605 * 606 * @param expansionMode The expansionMode to set. 607 * @throws IllegalArgumentException if the specified mode value is not valid 608 */ 609 public void setExpansionMode(int expansionMode) { 610 if (expansionMode != MULTIPLICATIVE_MODE && 611 expansionMode != ADDITIVE_MODE) { 612 throw new IllegalArgumentException("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 synchronized(this) { 627 this.initialCapacity = initialCapacity; 628 } 629 } else { 630 String msg = 631 "The initial capacity supplied: " + initialCapacity + 632 "must be a positive integer"; 633 throw new IllegalArgumentException(msg); 634 } 635 } 636 637 /** 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. 641 * 642 * @param i a new number of elements 643 * @throws IllegalArgumentException if <code>i</code> is negative. 644 */ 645 public synchronized void setNumElements(int i) { 646 647 // If index is negative thrown an error 648 if (i < 0) { 649 String msg = 650 "Number of elements must be zero or a positive " + "integer"; 651 throw new IllegalArgumentException(msg); 652 } 653 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); 658 } 659 660 // Set the new number of elements to new value 661 numElements = i; 662 } 663 664 /** 665 * Returns true if the internal storage array has too many unused 666 * storage positions. 667 * 668 * @return true if array satisfies the contraction criteria 669 */ 670 private synchronized boolean shouldContract() { 671 if (expansionMode == MULTIPLICATIVE_MODE) { 672 return (internalArray.length / ((float) numElements)) > contractionCriteria; 673 } else { 674 return (internalArray.length - numElements) > contractionCriteria; 675 } 676 } 677 678 /** 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] 683 * </code> 684 * 685 * @return starting index 686 */ 687 public synchronized int start() { 688 return startIndex; 689 } 690 691 }