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