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 018package org.apache.commons.math4.legacy.core; 019 020import java.lang.reflect.Array; 021import java.util.Arrays; 022import java.util.Iterator; 023import java.util.TreeSet; 024 025import org.apache.commons.numbers.core.Precision; 026import org.apache.commons.math4.legacy.exception.DimensionMismatchException; 027import org.apache.commons.math4.legacy.exception.MathArithmeticException; 028import org.apache.commons.math4.legacy.exception.MathIllegalArgumentException; 029import org.apache.commons.math4.legacy.exception.MathInternalError; 030import org.apache.commons.math4.legacy.exception.NoDataException; 031import org.apache.commons.math4.legacy.exception.NonMonotonicSequenceException; 032import org.apache.commons.math4.legacy.exception.NotANumberException; 033import org.apache.commons.math4.legacy.exception.NotPositiveException; 034import org.apache.commons.math4.legacy.exception.NotStrictlyPositiveException; 035import org.apache.commons.math4.legacy.exception.NullArgumentException; 036import org.apache.commons.math4.legacy.exception.NumberIsTooLargeException; 037import org.apache.commons.math4.legacy.exception.util.LocalizedFormats; 038import org.apache.commons.math4.core.jdkmath.JdkMath; 039 040/** 041 * Arrays utilities. 042 * 043 * @since 3.0 044 */ 045public final class MathArrays { 046 047 /** 048 * Private constructor. 049 */ 050 private MathArrays() {} 051 052 /** 053 * Real-valued function that operate on an array or a part of it. 054 * @since 3.1 055 */ 056 public interface Function { 057 /** 058 * Operates on an entire array. 059 * 060 * @param array Array to operate on. 061 * @return the result of the operation. 062 */ 063 double evaluate(double[] array); 064 /** 065 * @param array Array to operate on. 066 * @param startIndex Index of the first element to take into account. 067 * @param numElements Number of elements to take into account. 068 * @return the result of the operation. 069 */ 070 double evaluate(double[] array, 071 int startIndex, 072 int numElements); 073 } 074 075 /** 076 * Create a copy of an array scaled by a value. 077 * 078 * @param arr Array to scale. 079 * @param val Scalar. 080 * @return scaled copy of array with each entry multiplied by val. 081 * @since 3.2 082 */ 083 public static double[] scale(double val, final double[] arr) { 084 double[] newArr = new double[arr.length]; 085 for (int i = 0; i < arr.length; i++) { 086 newArr[i] = arr[i] * val; 087 } 088 return newArr; 089 } 090 091 /** 092 * <p>Multiply each element of an array by a value.</p> 093 * 094 * <p>The array is modified in place (no copy is created).</p> 095 * 096 * @param arr Array to scale 097 * @param val Scalar 098 * @since 3.2 099 */ 100 public static void scaleInPlace(double val, final double[] arr) { 101 for (int i = 0; i < arr.length; i++) { 102 arr[i] *= val; 103 } 104 } 105 106 /** 107 * Creates an array whose contents will be the element-by-element 108 * addition of the arguments. 109 * 110 * @param a First term of the addition. 111 * @param b Second term of the addition. 112 * @return a new array {@code r} where {@code r[i] = a[i] + b[i]}. 113 * @throws DimensionMismatchException if the array lengths differ. 114 * @since 3.1 115 */ 116 public static double[] ebeAdd(double[] a, double[] b) { 117 checkEqualLength(a, b); 118 119 final double[] result = a.clone(); 120 for (int i = 0; i < a.length; i++) { 121 result[i] += b[i]; 122 } 123 return result; 124 } 125 /** 126 * Creates an array whose contents will be the element-by-element 127 * subtraction of the second argument from the first. 128 * 129 * @param a First term. 130 * @param b Element to be subtracted. 131 * @return a new array {@code r} where {@code r[i] = a[i] - b[i]}. 132 * @throws DimensionMismatchException if the array lengths differ. 133 * @since 3.1 134 */ 135 public static double[] ebeSubtract(double[] a, double[] b) { 136 checkEqualLength(a, b); 137 138 final double[] result = a.clone(); 139 for (int i = 0; i < a.length; i++) { 140 result[i] -= b[i]; 141 } 142 return result; 143 } 144 /** 145 * Creates an array whose contents will be the element-by-element 146 * multiplication of the arguments. 147 * 148 * @param a First factor of the multiplication. 149 * @param b Second factor of the multiplication. 150 * @return a new array {@code r} where {@code r[i] = a[i] * b[i]}. 151 * @throws DimensionMismatchException if the array lengths differ. 152 * @since 3.1 153 */ 154 public static double[] ebeMultiply(double[] a, double[] b) { 155 checkEqualLength(a, b); 156 157 final double[] result = a.clone(); 158 for (int i = 0; i < a.length; i++) { 159 result[i] *= b[i]; 160 } 161 return result; 162 } 163 /** 164 * Creates an array whose contents will be the element-by-element 165 * division of the first argument by the second. 166 * 167 * @param a Numerator of the division. 168 * @param b Denominator of the division. 169 * @return a new array {@code r} where {@code r[i] = a[i] / b[i]}. 170 * @throws DimensionMismatchException if the array lengths differ. 171 * @since 3.1 172 */ 173 public static double[] ebeDivide(double[] a, double[] b) { 174 checkEqualLength(a, b); 175 176 final double[] result = a.clone(); 177 for (int i = 0; i < a.length; i++) { 178 result[i] /= b[i]; 179 } 180 return result; 181 } 182 183 /** 184 * Calculates the L<sub>1</sub> (sum of abs) distance between two points. 185 * 186 * @param p1 the first point 187 * @param p2 the second point 188 * @return the L<sub>1</sub> distance between the two points 189 * @throws DimensionMismatchException if the array lengths differ. 190 */ 191 public static double distance1(double[] p1, double[] p2) { 192 checkEqualLength(p1, p2); 193 double sum = 0; 194 for (int i = 0; i < p1.length; i++) { 195 sum += JdkMath.abs(p1[i] - p2[i]); 196 } 197 return sum; 198 } 199 200 /** 201 * Calculates the L<sub>1</sub> (sum of abs) distance between two points. 202 * 203 * @param p1 the first point 204 * @param p2 the second point 205 * @return the L<sub>1</sub> distance between the two points 206 * @throws DimensionMismatchException if the array lengths differ. 207 */ 208 public static int distance1(int[] p1, int[] p2) { 209 checkEqualLength(p1, p2); 210 int sum = 0; 211 for (int i = 0; i < p1.length; i++) { 212 sum += JdkMath.abs(p1[i] - p2[i]); 213 } 214 return sum; 215 } 216 217 /** 218 * Calculates the L<sub>2</sub> (Euclidean) distance between two points. 219 * 220 * @param p1 the first point 221 * @param p2 the second point 222 * @return the L<sub>2</sub> distance between the two points 223 * @throws DimensionMismatchException if the array lengths differ. 224 */ 225 public static double distance(double[] p1, double[] p2) { 226 checkEqualLength(p1, p2); 227 double sum = 0; 228 for (int i = 0; i < p1.length; i++) { 229 final double dp = p1[i] - p2[i]; 230 sum += dp * dp; 231 } 232 return JdkMath.sqrt(sum); 233 } 234 235 /** 236 * Calculates the L<sub>2</sub> (Euclidean) distance between two points. 237 * 238 * @param p1 the first point 239 * @param p2 the second point 240 * @return the L<sub>2</sub> distance between the two points 241 * @throws DimensionMismatchException if the array lengths differ. 242 */ 243 public static double distance(int[] p1, int[] p2) { 244 checkEqualLength(p1, p2); 245 double sum = 0; 246 for (int i = 0; i < p1.length; i++) { 247 final double dp = (double) p1[i] - p2[i]; 248 sum += dp * dp; 249 } 250 return JdkMath.sqrt(sum); 251 } 252 253 /** 254 * Calculates the L<sub>∞</sub> (max of abs) distance between two points. 255 * 256 * @param p1 the first point 257 * @param p2 the second point 258 * @return the L<sub>∞</sub> distance between the two points 259 * @throws DimensionMismatchException if the array lengths differ. 260 */ 261 public static double distanceInf(double[] p1, double[] p2) { 262 checkEqualLength(p1, p2); 263 double max = 0; 264 for (int i = 0; i < p1.length; i++) { 265 max = JdkMath.max(max, JdkMath.abs(p1[i] - p2[i])); 266 } 267 return max; 268 } 269 270 /** 271 * Calculates the L<sub>∞</sub> (max of abs) distance between two points. 272 * 273 * @param p1 the first point 274 * @param p2 the second point 275 * @return the L<sub>∞</sub> distance between the two points 276 * @throws DimensionMismatchException if the array lengths differ. 277 */ 278 public static int distanceInf(int[] p1, int[] p2) { 279 checkEqualLength(p1, p2); 280 int max = 0; 281 for (int i = 0; i < p1.length; i++) { 282 max = JdkMath.max(max, JdkMath.abs(p1[i] - p2[i])); 283 } 284 return max; 285 } 286 287 /** 288 * Specification of ordering direction. 289 */ 290 public enum OrderDirection { 291 /** Constant for increasing direction. */ 292 INCREASING, 293 /** Constant for decreasing direction. */ 294 DECREASING 295 } 296 297 /** 298 * Check that an array is monotonically increasing or decreasing. 299 * 300 * @param <T> the type of the elements in the specified array 301 * @param val Values. 302 * @param dir Ordering direction. 303 * @param strict Whether the order should be strict. 304 * @return {@code true} if sorted, {@code false} otherwise. 305 */ 306 public static <T extends Comparable<? super T>> boolean isMonotonic(T[] val, 307 OrderDirection dir, 308 boolean strict) { 309 T previous = val[0]; 310 final int max = val.length; 311 for (int i = 1; i < max; i++) { 312 final int comp; 313 switch (dir) { 314 case INCREASING: 315 comp = previous.compareTo(val[i]); 316 if (strict) { 317 if (comp >= 0) { 318 return false; 319 } 320 } else { 321 if (comp > 0) { 322 return false; 323 } 324 } 325 break; 326 case DECREASING: 327 comp = val[i].compareTo(previous); 328 if (strict) { 329 if (comp >= 0) { 330 return false; 331 } 332 } else { 333 if (comp > 0) { 334 return false; 335 } 336 } 337 break; 338 default: 339 // Should never happen. 340 throw new MathInternalError(); 341 } 342 343 previous = val[i]; 344 } 345 return true; 346 } 347 348 /** 349 * Check that an array is monotonically increasing or decreasing. 350 * 351 * @param val Values. 352 * @param dir Ordering direction. 353 * @param strict Whether the order should be strict. 354 * @return {@code true} if sorted, {@code false} otherwise. 355 */ 356 public static boolean isMonotonic(double[] val, OrderDirection dir, boolean strict) { 357 return checkOrder(val, dir, strict, false); 358 } 359 360 /** 361 * Check that both arrays have the same length. 362 * 363 * @param a Array. 364 * @param b Array. 365 * @param abort Whether to throw an exception if the check fails. 366 * @return {@code true} if the arrays have the same length. 367 * @throws DimensionMismatchException if the lengths differ and 368 * {@code abort} is {@code true}. 369 * @since 3.6 370 */ 371 public static boolean checkEqualLength(double[] a, 372 double[] b, 373 boolean abort) { 374 if (a.length == b.length) { 375 return true; 376 } else { 377 if (abort) { 378 throw new DimensionMismatchException(a.length, b.length); 379 } 380 return false; 381 } 382 } 383 384 /** 385 * Check that both arrays have the same length. 386 * 387 * @param a Array. 388 * @param b Array. 389 * @throws DimensionMismatchException if the lengths differ. 390 * @since 3.6 391 */ 392 public static void checkEqualLength(double[] a, 393 double[] b) { 394 checkEqualLength(a, b, true); 395 } 396 397 398 /** 399 * Check that both arrays have the same length. 400 * 401 * @param a Array. 402 * @param b Array. 403 * @param abort Whether to throw an exception if the check fails. 404 * @return {@code true} if the arrays have the same length. 405 * @throws DimensionMismatchException if the lengths differ and 406 * {@code abort} is {@code true}. 407 * @since 3.6 408 */ 409 public static boolean checkEqualLength(int[] a, 410 int[] b, 411 boolean abort) { 412 if (a.length == b.length) { 413 return true; 414 } else { 415 if (abort) { 416 throw new DimensionMismatchException(a.length, b.length); 417 } 418 return false; 419 } 420 } 421 422 /** 423 * Check that both arrays have the same length. 424 * 425 * @param a Array. 426 * @param b Array. 427 * @throws DimensionMismatchException if the lengths differ. 428 * @since 3.6 429 */ 430 public static void checkEqualLength(int[] a, 431 int[] b) { 432 checkEqualLength(a, b, true); 433 } 434 435 /** 436 * Check that the given array is sorted. 437 * 438 * @param val Values. 439 * @param dir Ordering direction. 440 * @param strict Whether the order should be strict. 441 * @param abort Whether to throw an exception if the check fails. 442 * @return {@code true} if the array is sorted. 443 * @throws NonMonotonicSequenceException if the array is not sorted 444 * and {@code abort} is {@code true}. 445 */ 446 public static boolean checkOrder(double[] val, OrderDirection dir, 447 boolean strict, boolean abort) { 448 double previous = val[0]; 449 final int max = val.length; 450 451 int index; 452 ITEM: 453 for (index = 1; index < max; index++) { 454 switch (dir) { 455 case INCREASING: 456 if (strict) { 457 if (val[index] <= previous) { 458 break ITEM; 459 } 460 } else { 461 if (val[index] < previous) { 462 break ITEM; 463 } 464 } 465 break; 466 case DECREASING: 467 if (strict) { 468 if (val[index] >= previous) { 469 break ITEM; 470 } 471 } else { 472 if (val[index] > previous) { 473 break ITEM; 474 } 475 } 476 break; 477 default: 478 // Should never happen. 479 throw new MathInternalError(); 480 } 481 482 previous = val[index]; 483 } 484 485 if (index == max) { 486 // Loop completed. 487 return true; 488 } 489 490 // Loop early exit means wrong ordering. 491 if (abort) { 492 throw new NonMonotonicSequenceException(val[index], 493 previous, 494 index, 495 dir == OrderDirection.INCREASING, 496 strict); 497 } else { 498 return false; 499 } 500 } 501 502 /** 503 * Check that the given array is sorted. 504 * 505 * @param val Values. 506 * @param dir Ordering direction. 507 * @param strict Whether the order should be strict. 508 * @throws NonMonotonicSequenceException if the array is not sorted. 509 * @since 2.2 510 */ 511 public static void checkOrder(double[] val, OrderDirection dir, boolean strict) { 512 checkOrder(val, dir, strict, true); 513 } 514 515 /** 516 * Check that the given array is sorted in strictly increasing order. 517 * 518 * @param val Values. 519 * @throws NonMonotonicSequenceException if the array is not sorted. 520 * @since 2.2 521 */ 522 public static void checkOrder(double[] val) { 523 checkOrder(val, OrderDirection.INCREASING, true); 524 } 525 526 /** 527 * Throws DimensionMismatchException if the input array is not rectangular. 528 * 529 * @param in array to be tested 530 * @throws NullArgumentException if input array is null 531 * @throws DimensionMismatchException if input array is not rectangular 532 * @since 3.1 533 */ 534 public static void checkRectangular(final long[][] in) { 535 NullArgumentException.check(in); 536 for (int i = 1; i < in.length; i++) { 537 if (in[i].length != in[0].length) { 538 throw new DimensionMismatchException( 539 LocalizedFormats.DIFFERENT_ROWS_LENGTHS, 540 in[i].length, in[0].length); 541 } 542 } 543 } 544 545 /** 546 * Check that all entries of the input array are strictly positive. 547 * 548 * @param in Array to be tested 549 * @throws NotStrictlyPositiveException if any entries of the array are not 550 * strictly positive. 551 * @since 3.1 552 */ 553 public static void checkPositive(final double[] in) { 554 for (int i = 0; i < in.length; i++) { 555 if (in[i] <= 0) { 556 throw new NotStrictlyPositiveException(in[i]); 557 } 558 } 559 } 560 561 /** 562 * Check that no entry of the input array is {@code NaN}. 563 * 564 * @param in Array to be tested. 565 * @throws NotANumberException if an entry is {@code NaN}. 566 * @since 3.4 567 */ 568 public static void checkNotNaN(final double[] in) { 569 for (int i = 0; i < in.length; i++) { 570 if (Double.isNaN(in[i])) { 571 throw new NotANumberException(); 572 } 573 } 574 } 575 576 /** 577 * Check that all entries of the input array are >= 0. 578 * 579 * @param in Array to be tested 580 * @throws NotPositiveException if any array entries are less than 0. 581 * @since 3.1 582 */ 583 public static void checkNonNegative(final long[] in) { 584 for (int i = 0; i < in.length; i++) { 585 if (in[i] < 0) { 586 throw new NotPositiveException(in[i]); 587 } 588 } 589 } 590 591 /** 592 * Check all entries of the input array are >= 0. 593 * 594 * @param in Array to be tested 595 * @throws NotPositiveException if any array entries are less than 0. 596 * @since 3.1 597 */ 598 public static void checkNonNegative(final long[][] in) { 599 for (int i = 0; i < in.length; i++) { 600 for (int j = 0; j < in[i].length; j++) { 601 if (in[i][j] < 0) { 602 throw new NotPositiveException(in[i][j]); 603 } 604 } 605 } 606 } 607 608 /** 609 * Returns true iff both arguments are null or have same dimensions and all 610 * their elements are equal as defined by 611 * {@link Precision#equals(float,float)}. 612 * 613 * @param x first array 614 * @param y second array 615 * @return true if the values are both null or have same dimension 616 * and equal elements. 617 */ 618 public static boolean equals(float[] x, float[] y) { 619 if (x == null || y == null) { 620 return (x == null) == (y == null); 621 } 622 if (x.length != y.length) { 623 return false; 624 } 625 for (int i = 0; i < x.length; ++i) { 626 if (!Precision.equals(x[i], y[i])) { 627 return false; 628 } 629 } 630 return true; 631 } 632 633 /** 634 * Returns true iff both arguments are null or have same dimensions and all 635 * their elements are equal as defined by 636 * {@link Precision#equalsIncludingNaN(double,double) this method}. 637 * 638 * @param x first array 639 * @param y second array 640 * @return true if the values are both null or have same dimension and 641 * equal elements 642 * @since 2.2 643 */ 644 public static boolean equalsIncludingNaN(float[] x, float[] y) { 645 if (x == null || y == null) { 646 return (x == null) == (y == null); 647 } 648 if (x.length != y.length) { 649 return false; 650 } 651 for (int i = 0; i < x.length; ++i) { 652 if (!Precision.equalsIncludingNaN(x[i], y[i])) { 653 return false; 654 } 655 } 656 return true; 657 } 658 659 /** 660 * Returns {@code true} iff both arguments are {@code null} or have same 661 * dimensions and all their elements are equal as defined by 662 * {@link Precision#equals(double,double)}. 663 * 664 * @param x First array. 665 * @param y Second array. 666 * @return {@code true} if the values are both {@code null} or have same 667 * dimension and equal elements. 668 */ 669 public static boolean equals(double[] x, double[] y) { 670 if (x == null || y == null) { 671 return (x == null) == (y == null); 672 } 673 if (x.length != y.length) { 674 return false; 675 } 676 for (int i = 0; i < x.length; ++i) { 677 if (!Precision.equals(x[i], y[i])) { 678 return false; 679 } 680 } 681 return true; 682 } 683 684 /** 685 * Returns {@code true} iff both arguments are {@code null} or have same 686 * dimensions and all their elements are equal as defined by 687 * {@link Precision#equalsIncludingNaN(double,double) this method}. 688 * 689 * @param x First array. 690 * @param y Second array. 691 * @return {@code true} if the values are both {@code null} or have same 692 * dimension and equal elements. 693 * @since 2.2 694 */ 695 public static boolean equalsIncludingNaN(double[] x, double[] y) { 696 if (x == null || y == null) { 697 return (x == null) == (y == null); 698 } 699 if (x.length != y.length) { 700 return false; 701 } 702 for (int i = 0; i < x.length; ++i) { 703 if (!Precision.equalsIncludingNaN(x[i], y[i])) { 704 return false; 705 } 706 } 707 return true; 708 } 709 710 /** 711 * Normalizes an array to make it sum to a specified value. 712 * Returns the result of the transformation 713 * <pre> 714 * x |-> x * normalizedSum / sum 715 * </pre> 716 * applied to each non-NaN element x of the input array, where sum is the 717 * sum of the non-NaN entries in the input array. 718 * <p> 719 * Throws IllegalArgumentException if {@code normalizedSum} is infinite 720 * or NaN and ArithmeticException if the input array contains any infinite elements 721 * or sums to 0. 722 * <p> 723 * Ignores (i.e., copies unchanged to the output array) NaNs in the input array. 724 * 725 * @param values Input array to be normalized 726 * @param normalizedSum Target sum for the normalized array 727 * @return the normalized array. 728 * @throws MathArithmeticException if the input array contains infinite 729 * elements or sums to zero. 730 * @throws MathIllegalArgumentException if the target sum is infinite or {@code NaN}. 731 * @since 2.1 732 */ 733 public static double[] normalizeArray(double[] values, double normalizedSum) { 734 if (Double.isInfinite(normalizedSum)) { 735 throw new MathIllegalArgumentException(LocalizedFormats.NORMALIZE_INFINITE); 736 } 737 if (Double.isNaN(normalizedSum)) { 738 throw new MathIllegalArgumentException(LocalizedFormats.NORMALIZE_NAN); 739 } 740 double sum = 0d; 741 final int len = values.length; 742 double[] out = new double[len]; 743 for (int i = 0; i < len; i++) { 744 if (Double.isInfinite(values[i])) { 745 throw new MathIllegalArgumentException(LocalizedFormats.INFINITE_ARRAY_ELEMENT, values[i], i); 746 } 747 if (!Double.isNaN(values[i])) { 748 sum += values[i]; 749 } 750 } 751 if (sum == 0) { 752 throw new MathArithmeticException(LocalizedFormats.ARRAY_SUMS_TO_ZERO); 753 } 754 final double scale = normalizedSum / sum; 755 for (int i = 0; i < len; i++) { 756 if (Double.isNaN(values[i])) { 757 out[i] = Double.NaN; 758 } else { 759 out[i] = values[i] * scale; 760 } 761 } 762 return out; 763 } 764 765 /** Build an array of elements. 766 * <p> 767 * Arrays are filled with field.getZero() 768 * 769 * @param <T> the type of the field elements 770 * @param field field to which array elements belong 771 * @param length of the array 772 * @return a new array 773 * @since 3.2 774 */ 775 public static <T> T[] buildArray(final Field<T> field, final int length) { 776 @SuppressWarnings("unchecked") // OK because field must be correct class 777 T[] array = (T[]) Array.newInstance(field.getRuntimeClass(), length); 778 Arrays.fill(array, field.getZero()); 779 return array; 780 } 781 782 /** Build a double dimension array of elements. 783 * <p> 784 * Arrays are filled with field.getZero() 785 * 786 * @param <T> the type of the field elements 787 * @param field field to which array elements belong 788 * @param rows number of rows in the array 789 * @param columns number of columns (may be negative to build partial 790 * arrays in the same way <code>new Field[rows][]</code> works) 791 * @return a new array 792 * @since 3.2 793 */ 794 @SuppressWarnings("unchecked") 795 public static <T> T[][] buildArray(final Field<T> field, final int rows, final int columns) { 796 final T[][] array; 797 if (columns < 0) { 798 T[] dummyRow = buildArray(field, 0); 799 array = (T[][]) Array.newInstance(dummyRow.getClass(), rows); 800 } else { 801 array = (T[][]) Array.newInstance(field.getRuntimeClass(), 802 rows, columns); 803 for (int i = 0; i < rows; ++i) { 804 Arrays.fill(array[i], field.getZero()); 805 } 806 } 807 return array; 808 } 809 810 /** 811 * Calculates the <a href="http://en.wikipedia.org/wiki/Convolution"> 812 * convolution</a> between two sequences. 813 * <p> 814 * The solution is obtained via straightforward computation of the 815 * convolution sum (and not via FFT). Whenever the computation needs 816 * an element that would be located at an index outside the input arrays, 817 * the value is assumed to be zero. 818 * 819 * @param x First sequence. 820 * Typically, this sequence will represent an input signal to a system. 821 * @param h Second sequence. 822 * Typically, this sequence will represent the impulse response of the system. 823 * @return the convolution of {@code x} and {@code h}. 824 * This array's length will be {@code x.length + h.length - 1}. 825 * @throws NullArgumentException if either {@code x} or {@code h} is {@code null}. 826 * @throws NoDataException if either {@code x} or {@code h} is empty. 827 * 828 * @since 3.3 829 */ 830 public static double[] convolve(double[] x, double[] h) { 831 NullArgumentException.check(x); 832 NullArgumentException.check(h); 833 834 final int xLen = x.length; 835 final int hLen = h.length; 836 837 if (xLen == 0 || hLen == 0) { 838 throw new NoDataException(); 839 } 840 841 // initialize the output array 842 final int totalLength = xLen + hLen - 1; 843 final double[] y = new double[totalLength]; 844 845 // straightforward implementation of the convolution sum 846 for (int n = 0; n < totalLength; n++) { 847 double yn = 0; 848 int k = JdkMath.max(0, n + 1 - xLen); 849 int j = n - k; 850 while (k < hLen && j >= 0) { 851 yn += x[j--] * h[k++]; 852 } 853 y[n] = yn; 854 } 855 856 return y; 857 } 858 859 /** 860 * Returns an array representing the natural number {@code n}. 861 * 862 * @param n Natural number. 863 * @return an array whose entries are the numbers 0, 1, ..., {@code n}-1. 864 * If {@code n == 0}, the returned array is empty. 865 */ 866 public static int[] natural(int n) { 867 return sequence(n, 0, 1); 868 } 869 /** 870 * Returns an array of {@code size} integers starting at {@code start}, 871 * skipping {@code stride} numbers. 872 * 873 * @param size Natural number. 874 * @param start Natural number. 875 * @param stride Natural number. 876 * @return an array whose entries are the numbers 877 * {@code start, start + stride, ..., start + (size - 1) * stride}. 878 * If {@code size == 0}, the returned array is empty. 879 * 880 * @since 3.4 881 */ 882 public static int[] sequence(int size, 883 int start, 884 int stride) { 885 final int[] a = new int[size]; 886 for (int i = 0; i < size; i++) { 887 a[i] = start + i * stride; 888 } 889 return a; 890 } 891 /** 892 * This method is used 893 * to verify that the input parameters designate a subarray of positive length. 894 * <ul> 895 * <li>returns <code>true</code> iff the parameters designate a subarray of 896 * positive length</li> 897 * <li>throws <code>MathIllegalArgumentException</code> if the array is null or 898 * or the indices are invalid</li> 899 * <li>returns <code>false</code> if the array is non-null, but 900 * <code>length</code> is 0.</li> 901 * </ul> 902 * 903 * @param values the input array 904 * @param begin index of the first array element to include 905 * @param length the number of elements to include 906 * @return true if the parameters are valid and designate a subarray of positive length 907 * @throws MathIllegalArgumentException if the indices are invalid or the array is null 908 * @since 3.3 909 */ 910 public static boolean verifyValues(final double[] values, final int begin, final int length) { 911 return verifyValues(values, begin, length, false); 912 } 913 914 /** 915 * This method is used 916 * to verify that the input parameters designate a subarray of positive length. 917 * <ul> 918 * <li>returns <code>true</code> iff the parameters designate a subarray of 919 * non-negative length</li> 920 * <li>throws <code>IllegalArgumentException</code> if the array is null or 921 * or the indices are invalid</li> 922 * <li>returns <code>false</code> if the array is non-null, but 923 * <code>length</code> is 0 unless <code>allowEmpty</code> is <code>true</code></li> 924 * </ul> 925 * 926 * @param values the input array 927 * @param begin index of the first array element to include 928 * @param length the number of elements to include 929 * @param allowEmpty if <code>true</code> then zero length arrays are allowed 930 * @return true if the parameters are valid 931 * @throws MathIllegalArgumentException if the indices are invalid or the array is null 932 * @since 3.3 933 */ 934 public static boolean verifyValues(final double[] values, final int begin, 935 final int length, final boolean allowEmpty) { 936 937 if (values == null) { 938 throw new NullArgumentException(LocalizedFormats.INPUT_ARRAY); 939 } 940 941 if (begin < 0) { 942 throw new NotPositiveException(LocalizedFormats.START_POSITION, Integer.valueOf(begin)); 943 } 944 945 if (length < 0) { 946 throw new NotPositiveException(LocalizedFormats.LENGTH, Integer.valueOf(length)); 947 } 948 949 if (begin + length > values.length) { 950 throw new NumberIsTooLargeException(LocalizedFormats.SUBARRAY_ENDS_AFTER_ARRAY_END, 951 Integer.valueOf(begin + length), Integer.valueOf(values.length), true); 952 } 953 954 return !(length == 0 && !allowEmpty); 955 } 956 957 /** 958 * This method is used 959 * to verify that the begin and length parameters designate a subarray of positive length 960 * and the weights are all non-negative, non-NaN, finite, and not all zero. 961 * <ul> 962 * <li>returns <code>true</code> iff the parameters designate a subarray of 963 * positive length and the weights array contains legitimate values.</li> 964 * <li>throws <code>IllegalArgumentException</code> if any of the following are true: 965 * <ul><li>the values array is null</li> 966 * <li>the weights array is null</li> 967 * <li>the weights array does not have the same length as the values array</li> 968 * <li>the weights array contains one or more infinite values</li> 969 * <li>the weights array contains one or more NaN values</li> 970 * <li>the weights array contains negative values</li> 971 * <li>the weights array does not contain at least one non-zero value (applies when length is non zero)</li> 972 * <li>the start and length arguments do not determine a valid array</li></ul> 973 * </li> 974 * <li>returns <code>false</code> if the array is non-null, but 975 * <code>length</code> is 0.</li> 976 * </ul> 977 * 978 * @param values the input array 979 * @param weights the weights array 980 * @param begin index of the first array element to include 981 * @param length the number of elements to include 982 * @return true if the parameters are valid and designate a subarray of positive length 983 * @throws MathIllegalArgumentException if the indices are invalid or the array is null 984 * @since 3.3 985 */ 986 public static boolean verifyValues( 987 final double[] values, 988 final double[] weights, 989 final int begin, 990 final int length) { 991 return verifyValues(values, weights, begin, length, false); 992 } 993 994 /** 995 * This method is used 996 * to verify that the begin and length parameters designate a subarray of positive length 997 * and the weights are all non-negative, non-NaN, finite, and not all zero. 998 * <ul> 999 * <li>returns <code>true</code> iff the parameters designate a subarray of 1000 * non-negative length and the weights array contains legitimate values.</li> 1001 * <li>throws <code>MathIllegalArgumentException</code> if any of the following are true: 1002 * <ul><li>the values array is null</li> 1003 * <li>the weights array is null</li> 1004 * <li>the weights array does not have the same length as the values array</li> 1005 * <li>the weights array contains one or more infinite values</li> 1006 * <li>the weights array contains one or more NaN values</li> 1007 * <li>the weights array contains negative values</li> 1008 * <li>the weights array does not contain at least one non-zero value (applies when length is non zero)</li> 1009 * <li>the start and length arguments do not determine a valid array</li></ul> 1010 * </li> 1011 * <li>returns <code>false</code> if the array is non-null, but 1012 * <code>length</code> is 0 unless <code>allowEmpty</code> is <code>true</code>.</li> 1013 * </ul> 1014 * 1015 * @param values the input array. 1016 * @param weights the weights array. 1017 * @param begin index of the first array element to include. 1018 * @param length the number of elements to include. 1019 * @param allowEmpty if {@code true} than allow zero length arrays to pass. 1020 * @return {@code true} if the parameters are valid. 1021 * @throws NullArgumentException if either of the arrays are null 1022 * @throws MathIllegalArgumentException if the array indices are not valid, 1023 * the weights array contains NaN, infinite or negative elements, or there 1024 * are no positive weights. 1025 * @since 3.3 1026 */ 1027 public static boolean verifyValues(final double[] values, final double[] weights, 1028 final int begin, final int length, final boolean allowEmpty) { 1029 1030 if (weights == null || values == null) { 1031 throw new NullArgumentException(LocalizedFormats.INPUT_ARRAY); 1032 } 1033 1034 checkEqualLength(weights, values); 1035 1036 if (length != 0) { 1037 boolean containsPositiveWeight = false; 1038 for (int i = begin; i < begin + length; i++) { 1039 final double weight = weights[i]; 1040 if (Double.isNaN(weight)) { 1041 throw new MathIllegalArgumentException(LocalizedFormats.NAN_ELEMENT_AT_INDEX, Integer.valueOf(i)); 1042 } 1043 if (Double.isInfinite(weight)) { 1044 throw new MathIllegalArgumentException(LocalizedFormats.INFINITE_ARRAY_ELEMENT, 1045 Double.valueOf(weight), Integer.valueOf(i)); 1046 } 1047 if (weight < 0) { 1048 throw new MathIllegalArgumentException(LocalizedFormats.NEGATIVE_ELEMENT_AT_INDEX, 1049 Integer.valueOf(i), Double.valueOf(weight)); 1050 } 1051 if (!containsPositiveWeight && weight > 0.0) { 1052 containsPositiveWeight = true; 1053 } 1054 } 1055 1056 if (!containsPositiveWeight) { 1057 throw new MathIllegalArgumentException(LocalizedFormats.WEIGHT_AT_LEAST_ONE_NON_ZERO); 1058 } 1059 } 1060 1061 return verifyValues(values, begin, length, allowEmpty); 1062 } 1063 1064 /** 1065 * Concatenates a sequence of arrays. The return array consists of the 1066 * entries of the input arrays concatenated in the order they appear in 1067 * the argument list. Null arrays cause NullPointerExceptions; zero 1068 * length arrays are allowed (contributing nothing to the output array). 1069 * 1070 * @param x list of double[] arrays to concatenate 1071 * @return a new array consisting of the entries of the argument arrays 1072 * @throws NullPointerException if any of the arrays are null 1073 * @since 3.6 1074 */ 1075 public static double[] concatenate(double[]... x) { 1076 int combinedLength = 0; 1077 for (double[] a : x) { 1078 combinedLength += a.length; 1079 } 1080 int offset = 0; 1081 int curLength = 0; 1082 final double[] combined = new double[combinedLength]; 1083 for (int i = 0; i < x.length; i++) { 1084 curLength = x[i].length; 1085 System.arraycopy(x[i], 0, combined, offset, curLength); 1086 offset += curLength; 1087 } 1088 return combined; 1089 } 1090 1091 /** 1092 * Returns an array consisting of the unique values in {@code data}. 1093 * The return array is sorted in descending order. Empty arrays 1094 * are allowed, but null arrays result in NullPointerException. 1095 * Infinities are allowed. NaN values are allowed with maximum 1096 * sort order - i.e., if there are NaN values in {@code data}, 1097 * {@code Double.NaN} will be the first element of the output array, 1098 * even if the array also contains {@code Double.POSITIVE_INFINITY}. 1099 * 1100 * @param data array to scan 1101 * @return descending list of values included in the input array 1102 * @throws NullPointerException if data is null 1103 * @since 3.6 1104 */ 1105 public static double[] unique(double[] data) { 1106 TreeSet<Double> values = new TreeSet<>(); 1107 for (int i = 0; i < data.length; i++) { 1108 values.add(data[i]); 1109 } 1110 final int count = values.size(); 1111 final double[] out = new double[count]; 1112 Iterator<Double> iterator = values.descendingIterator(); 1113 int i = 0; 1114 while (iterator.hasNext()) { 1115 out[i++] = iterator.next(); 1116 } 1117 return out; 1118 } 1119}