0001: package JSci.maths;
0002:
0003: import JSci.GlobalSettings;
0004:
0005: /**
0006: * Arrays are faster than object, so this class is here to take full
0007: * advantage of arrays without encapsulation.
0008: * All methods are safe, that is, they create copies of arrays whenever
0009: * necessary
0010: * This makes for slower methods, but the programmer can always
0011: * define his own methods optimized for performance.
0012: * @author Daniel Lemire
0013: * @author Mark Hale
0014: */
0015: public final class ArrayMath extends AbstractMath {
0016: private ArrayMath() {
0017: }
0018:
0019: public static boolean isSquare(double[][] a) {
0020: for (int i = 0; i < a.length; i++) {
0021: if (a[i].length != a.length)
0022: return false;
0023: }
0024: return true;
0025: }
0026:
0027: public static boolean isSquare(int[][] a) {
0028: for (int i = 0; i < a.length; i++) {
0029: if (a[i].length != a.length)
0030: return false;
0031: }
0032: return true;
0033: }
0034:
0035: public static boolean isSquare(Object[][] a) {
0036: for (int i = 0; i < a.length; i++) {
0037: if (a[i].length != a.length)
0038: return false;
0039: }
0040: return true;
0041: }
0042:
0043: /**
0044: * Applys a map to every component of an array.
0045: */
0046: public static double[] apply(Mapping m, double[] v) {
0047: double[] ans = new double[v.length];
0048: for (int k = 0; k < v.length; k++) {
0049: ans[k] = m.map(v[k]);
0050: }
0051: return (ans);
0052: }
0053:
0054: /**
0055: * Applys a map to every component of an array.
0056: */
0057: public static double[][] apply(Mapping m, double[][] v) {
0058: double[][] ans = new double[v.length][];
0059: for (int k = 0; k < v.length; k++) {
0060: ans[k] = apply(m, v[k]);
0061: }
0062: return (ans);
0063: }
0064:
0065: /**
0066: * Applys a map to every component of an array.
0067: */
0068: public static Complex[] apply(ComplexMapping m, Complex[] v) {
0069: Complex[] ans = new Complex[v.length];
0070: for (int k = 0; k < v.length; k++) {
0071: ans[k] = m.map(v[k]);
0072: }
0073: return (ans);
0074: }
0075:
0076: /**
0077: * Applys a map to every component of an array.
0078: */
0079: public static Complex[][] apply(ComplexMapping m, Complex[][] v) {
0080: Complex[][] ans = new Complex[v.length][];
0081: for (int k = 0; k < v.length; k++) {
0082: ans[k] = apply(m, v[k]);
0083: }
0084: return (ans);
0085: }
0086:
0087: /**
0088: * Renormalizes the array so that its L2 norm is 1
0089: * (up to computational errors).
0090: */
0091: public static double[] normalize(double[] v) {
0092: return (scalarMultiply(1.0 / norm(v), v));
0093: }
0094:
0095: /**
0096: * Sets an array to the specified length scraping or
0097: * padding the beginning if necessary.
0098: */
0099: public static double[] setLengthFromEnd(double[] data, int length) {
0100: double[] ans = new double[length];
0101: int debut;
0102: if (length - data.length < 0)
0103: debut = data.length - length;
0104: else
0105: debut = 0;
0106: System.arraycopy(data, debut, ans, -data.length + length
0107: + debut, data.length - debut);
0108: return (ans);
0109: }
0110:
0111: /**
0112: * Sets an array to the specified length scraping or
0113: * padding the end if necessary.
0114: */
0115: public static double[] setLengthFromBeginning(double[] data,
0116: int length) {
0117: double[] ans = new double[length];
0118: int debut;
0119: if (length - data.length < 0)
0120: debut = data.length - length;
0121: else
0122: debut = 0;
0123: System.arraycopy(data, 0, ans, 0, data.length - debut);
0124: return (ans);
0125: }
0126:
0127: /**
0128: * Returns a copy of the array.
0129: */
0130: public static double[] copy(final double[] v) {
0131: double[] ans = new double[v.length];
0132: System.arraycopy(v, 0, ans, 0, v.length);
0133: return (ans);
0134: }
0135:
0136: /**
0137: * Returns a copy of the array.
0138: */
0139: public static double[][] copy(double[][] v) {
0140: double[][] ans = new double[v.length][];
0141: for (int k = 0; k < v.length; k++)
0142: ans[k] = copy(v[k]);
0143: return (ans);
0144: }
0145:
0146: /**
0147: * Computes the variance.
0148: */
0149: public static double variance(double[] v) {
0150: final double m = mean(v);
0151: double ans = 0.0;
0152: for (int i = 0; i < v.length; i++)
0153: ans += (v[i] - m) * (v[i] - m);
0154: return ans / (v.length - 1);
0155: }
0156:
0157: /**
0158: * Computes the covariance.
0159: */
0160: public static double covariance(double[] v1, double[] v2) {
0161: if (v1.length != v2.length)
0162: throw new IllegalArgumentException(
0163: "Arrays must have the same length : " + v1.length
0164: + ", " + v2.length);
0165: final double m1 = mean(v1);
0166: final double m2 = mean(v2);
0167: double ans = 0.0;
0168: for (int i = 0; i < v1.length; i++)
0169: ans += (v1[i] - m1) * (v2[i] - m2);
0170: return ans / (v1.length - 1);
0171: }
0172:
0173: /**
0174: * Computes the (linear) correlation between two arrays.
0175: * Squaring this result and multiply by 100 gives you
0176: * the percentage of correlation.
0177: */
0178: public static double correlation(double[] v1, double[] v2) {
0179: double denom = Math.sqrt(variance(v1) * variance(v2));
0180: if (denom != 0)
0181: return (covariance(v1, v2) / denom);
0182: else {
0183: if ((variance(v1) == 0) && (variance(v2) == 0))
0184: return (1.0);
0185: else
0186: return (0.0); // impossible to correlate a null signal with another
0187: }
0188: }
0189:
0190: /**
0191: * Computes the mean.
0192: */
0193: public static double mean(double[] v) {
0194: if (v.length == 0)
0195: throw new IllegalArgumentException(
0196: "Nothing to compute! The array must have at least one element.");
0197: return (mass(v) / (double) v.length);
0198: }
0199:
0200: /**
0201: * Computes the standard deviation of an array.
0202: */
0203: public static double standardDeviation(double[] v) {
0204: return (Math.sqrt(variance(v)));
0205: }
0206:
0207: /**
0208: * Returns a sorted array from the minimum to the maximum value.
0209: */
0210: public static double[] sortMinToMax(double[] v) {
0211: double[] ans = copy(v);
0212: quickSortMinToMax(ans, 0, ans.length - 1);
0213: return (ans);
0214: }
0215:
0216: /**
0217: * Returns a sorted array from the maximum to the minimum value.
0218: */
0219: public static double[] sortMaxToMin(double[] v) {
0220: double[] ans = copy(v);
0221: quickSortMaxToMin(ans, 0, ans.length - 1);
0222: return (ans);
0223: }
0224:
0225: /**
0226: * Gives the percentile of an array.
0227: * @param v an unsorted array
0228: * @param p percentile, must be between 0 and 1
0229: * @exception IllegalArgumentException if parameter.
0230: * p is not between 0 and 1.
0231: */
0232: public static double percentile(double[] v, double p) {
0233: return percentile(v, p, false);
0234: }
0235:
0236: public static double percentile(double[] v, double p,
0237: boolean isSorted) {
0238: if ((p < 0) || (p > 1)) {
0239: throw new IllegalArgumentException(
0240: "Percentile must be between 0 and 1 : " + p);
0241: }
0242: final double[] ans = (isSorted ? v : sortMinToMax(v));
0243: final int pos = (int) Math.floor(p * (ans.length - 1));
0244: final double dif = p * (ans.length - 1)
0245: - Math.floor(p * (ans.length - 1));
0246: if (pos == (ans.length - 1))
0247: return (ans[ans.length - 1]);
0248: else
0249: return (ans[pos] * (1.0 - dif) + ans[pos + 1] * dif);
0250: }
0251:
0252: /**
0253: * Computes the median of an array.
0254: * If the array contains an even number of elements,
0255: * then the mean of the lower and upper medians is returned.
0256: */
0257: public static double median(double[] v) {
0258: if (v.length == 3) {
0259: return median3(copy(v));
0260: } else if (v.length == 5) {
0261: return median5(copy(v));
0262: } else if (v.length == 7) {
0263: return median7(copy(v));
0264: } else if (v.length % 2 == 1) { // odd
0265: return quickSelect(copy(v), false);
0266: } else { // even
0267: double[] tmp = copy(v);
0268: double lowerMedian = quickSelect(tmp, false);
0269: double upperMedian = quickSelect(tmp, true);
0270: return (lowerMedian + upperMedian) / 2.0;
0271: }
0272: }
0273:
0274: /*
0275: * http://ndevilla.free.fr/median/median/index.html
0276: * optmed.c
0277: * @author N. Devillard
0278: */
0279: private static void sortInPlace(final double[] v, final int i,
0280: final int j) {
0281: if (v[i] > v[j]) {
0282: final double tmp = v[i];
0283: v[i] = v[j];
0284: v[j] = tmp;
0285: }
0286: }
0287:
0288: private static double median3(double[] v) {
0289: sortInPlace(v, 0, 1);
0290: sortInPlace(v, 1, 2);
0291: sortInPlace(v, 0, 1);
0292: return v[1];
0293: }
0294:
0295: private static double median5(double[] v) {
0296: sortInPlace(v, 0, 1);
0297: sortInPlace(v, 3, 4);
0298: sortInPlace(v, 0, 3);
0299: sortInPlace(v, 1, 4);
0300: sortInPlace(v, 1, 2);
0301: sortInPlace(v, 2, 3);
0302: sortInPlace(v, 1, 2);
0303: return v[2];
0304: }
0305:
0306: private static double median7(double[] v) {
0307: sortInPlace(v, 0, 5);
0308: sortInPlace(v, 0, 3);
0309: sortInPlace(v, 1, 6);
0310: sortInPlace(v, 2, 4);
0311: sortInPlace(v, 0, 1);
0312: sortInPlace(v, 3, 5);
0313: sortInPlace(v, 2, 6);
0314: sortInPlace(v, 2, 3);
0315: sortInPlace(v, 3, 6);
0316: sortInPlace(v, 4, 5);
0317: sortInPlace(v, 1, 4);
0318: sortInPlace(v, 1, 3);
0319: sortInPlace(v, 3, 4);
0320: return v[3];
0321: }
0322:
0323: /*
0324: * http://ndevilla.free.fr/median/median/index.html
0325: * quickselect.c
0326: * @author N. Devillard
0327: */
0328: private static double quickSelect(double[] v, boolean upperMedian) {
0329: int low = 0, high = v.length - 1;
0330: final int median = upperMedian ? high / 2 + 1 : high / 2;
0331: int middle, ll, hh;
0332:
0333: for (;;) {
0334: if (high <= low) { /* One element only */
0335: return v[median];
0336: }
0337:
0338: if (high == low + 1) { /* Two elements only */
0339: if (v[low] > v[high])
0340: swap(v, low, high);
0341: return v[median];
0342: }
0343:
0344: /* Find median of low, middle and high items; swap into position low */
0345: middle = (low + high) / 2;
0346: if (v[middle] > v[high])
0347: swap(v, middle, high);
0348: if (v[low] > v[high])
0349: swap(v, low, high);
0350: if (v[middle] > v[low])
0351: swap(v, middle, low);
0352:
0353: /* Swap low item (now in position middle) into position (low+1) */
0354: swap(v, middle, low + 1);
0355:
0356: /* Nibble from each end towards middle, swapping items when stuck */
0357: ll = low + 1;
0358: hh = high;
0359: for (;;) {
0360: do
0361: ll++;
0362: while (v[low] > v[ll]);
0363: do
0364: hh--;
0365: while (v[hh] > v[low]);
0366:
0367: if (hh < ll)
0368: break;
0369:
0370: swap(v, ll, hh);
0371: }
0372:
0373: /* Swap middle item (in position low) back into correct position */
0374: swap(v, low, hh);
0375:
0376: /* Re-set active partition */
0377: if (hh <= median)
0378: low = ll;
0379: if (hh >= median)
0380: high = hh - 1;
0381: }
0382: }
0383:
0384: /**
0385: * Checks if two arrays are equal within a tolerance.
0386: */
0387: public static boolean equals(double[] a, double[] b) {
0388: if (a.length != b.length)
0389: return (false);
0390: for (int i = 0; i < a.length; i++) {
0391: if (Math.abs(a[i] - b[i]) > GlobalSettings.ZERO_TOL)
0392: return (false);
0393: }
0394: return (true);
0395: }
0396:
0397: /**
0398: * Takes the absolute value of each component of an array.
0399: */
0400: public static double[] abs(double[] v) {
0401: double[] ans = new double[v.length];
0402: for (int i = 0; i < v.length; i++) {
0403: ans[i] = Math.abs(v[i]);
0404: }
0405: return (ans);
0406: }
0407:
0408: /**
0409: * Takes the absolute value of each component of an array.
0410: */
0411: public static double[][] abs(double[][] v) {
0412: double[][] ans = new double[v.length][];
0413: for (int i = 0; i < v.length; i++) {
0414: ans[i] = abs(v[i]);
0415: }
0416: return (ans);
0417: }
0418:
0419: /**
0420: * Returns the maximum of an array.
0421: */
0422: public static double max(double[] v) {
0423: double max = v[0];
0424: for (int i = 1; i < v.length; i++) {
0425: if (max < v[i]) {
0426: max = v[i];
0427: }
0428: }
0429: return (max);
0430: }
0431:
0432: /**
0433: * Returns the maximum of an array.
0434: */
0435: public static double max(double[][] v) {
0436: double max = max(v[0]);
0437: for (int i = 1; i < v.length; i++) {
0438: if (max < max(v[i])) {
0439: max = max(v[i]);
0440: }
0441: }
0442: return (max);
0443: }
0444:
0445: /**
0446: * Returns the minimum of an array.
0447: */
0448: public static double min(double[] v) {
0449: double min = v[0];
0450: for (int i = 1; i < v.length; i++) {
0451: if (min > v[i]) {
0452: min = v[i];
0453: }
0454: }
0455: return (min);
0456: }
0457:
0458: /**
0459: * Returns the minimum of an array.
0460: */
0461: public static double min(double[][] v) {
0462: double min = min(v[0]);
0463: for (int i = 1; i < v.length; i++) {
0464: if (min > min(v[i])) {
0465: min = min(v[i]);
0466: }
0467: }
0468: return (min);
0469: }
0470:
0471: /**
0472: * Returns the componentwise modulus of
0473: * an array of Complex numbers.
0474: */
0475: public static double[] mod(Complex[] v) {
0476: double[] ans = new double[v.length];
0477: for (int k = 0; k < v.length; k++) {
0478: ans[k] = v[k].mod();
0479: }
0480: return (ans);
0481: }
0482:
0483: /**
0484: * Returns the componentwise modulus of
0485: * an array of Complex numbers.
0486: */
0487: public static double[][] mod(Complex[][] v) {
0488: double[][] ans = new double[v.length][];
0489: for (int k = 0; k < v.length; k++) {
0490: ans[k] = mod(v[k]);
0491: }
0492: return (ans);
0493: }
0494:
0495: public static double sumModSqrs(Complex[] v) {
0496: double ans = 0.0;
0497: for (int k = 0; k < v.length; k++) {
0498: ans += v[k].modSqr();
0499: }
0500: return (ans);
0501: }
0502:
0503: public static double sumModSqrs(Complex[][] v) {
0504: double ans = 0.0;
0505: for (int k = 0; k < v.length; k++) {
0506: ans += sumModSqrs(v[k]);
0507: }
0508: return (ans);
0509: }
0510:
0511: /**
0512: * Computes the L2 norm of an array (Euclidean norm or "length").
0513: */
0514: public static double norm(double[] data) {
0515: return (Math.sqrt(sumSquares(data)));
0516: }
0517:
0518: /**
0519: * Sums the squares of all components;
0520: * also called the energy of the array.
0521: */
0522: public static double sumSquares(double[] data) {
0523: double ans = 0.0;
0524: for (int k = 0; k < data.length; k++) {
0525: ans += data[k] * data[k];
0526: }
0527: return (ans);
0528: }
0529:
0530: /**
0531: * Sums the squares of all components;
0532: * also called the energy of the array.
0533: */
0534: public static double sumSquares(double[][] data) {
0535: double ans = 0.0;
0536: for (int k = 0; k < data.length; k++) {
0537: for (int l = 0; l < data[k].length; l++) {
0538: ans += data[k][l] * data[k][l];
0539: }
0540: }
0541: return (ans);
0542: }
0543:
0544: /**
0545: * Computes the scalar product of two array as if they were vectors.
0546: * @exception IllegalArgumentException if the don't have the same length
0547: */
0548: public static double scalarProduct(double[] w0, double[] w1) {
0549: if (w0.length != w1.length) {
0550: throw new IllegalArgumentException(
0551: "Arrays must have the same length : " + w0.length
0552: + ", " + w1.length);
0553: }
0554: if (w0.length == 0)
0555: throw new IllegalArgumentException(
0556: "Nothing to compute! Arrays must have at least one element.");
0557: double sortie = 0.0;
0558: for (int k = 0; k < w0.length; k++) {
0559: sortie += w0[k] * w1[k];
0560: }
0561: return (sortie);
0562: }
0563:
0564: /**
0565: * Computes the scalar product of two array as if they were matrices.
0566: * @exception IllegalArgumentException if the don't have the same length
0567: */
0568: public static double scalarProduct(double[][] w0, double[][] w1) {
0569: if (w0.length != w1.length) {
0570: throw new IllegalArgumentException(
0571: "Arrays must have the same length : " + w0.length
0572: + ", " + w1.length);
0573: }
0574: if (w0.length == 0)
0575: throw new IllegalArgumentException(
0576: "Nothing to compute! Arrays must have at least one element.");
0577: double sortie = 0.0;
0578: for (int k = 0; k < w0.length; k++) {
0579: sortie = sortie + scalarProduct(w0[k], w1[k]);
0580: }
0581: return (sortie);
0582: }
0583:
0584: /**
0585: * Extracts a sub-array (will invert the resulting array if k0 > k1).
0586: * @param k0 location of the first component
0587: * @param k1 location of the last component
0588: */
0589: public static double[] extract(int k0, int k1, double[] invect) {
0590: if ((k0 < 0) || (k1 < 0) || (k0 > invect.length - 1)
0591: || (k1 > invect.length - 1)) {
0592: throw new IllegalArgumentException(
0593: "The parameters are incorrect : " + k0 + ", " + k1
0594: + ", " + invect.length);
0595: }
0596: if (k1 > k0) {
0597: double[] ans = new double[k1 - k0 + 1];
0598: System.arraycopy(invect, k0, ans, 0, k1 - k0 + 1);
0599: return (ans);
0600: }
0601: double[] ans = new double[-k1 + k0 + 1];
0602: for (int k = k1; k <= k0; k++) {
0603: ans[k0 - k] = invect[k];
0604: }
0605: return (ans);
0606: }
0607:
0608: /**
0609: * Inverts an array from left to right.
0610: */
0611: public static double[] invert(double[] v) {
0612: double[] w = new double[v.length];
0613: for (int k = 0; k < v.length; k++) {
0614: w[v.length - 1 - k] = v[k];
0615: }
0616: return (w);
0617: }
0618:
0619: /**
0620: * Fills in with zero to get to the desired length;
0621: * original array with be at the specified position.
0622: * @param n0 length of the new array.
0623: * @param pos position of the old array.
0624: */
0625: public static double[] padding(int n0, int pos, double[] v) {
0626: if ((v.length + pos > n0) || (pos < 0)) {
0627: throw new IllegalArgumentException(
0628: "Array is to long for this : " + n0 + ", " + pos
0629: + ", " + v.length);
0630: }
0631: double[] w = new double[n0];
0632: System.arraycopy(v, 0, w, pos, v.length);
0633: return (w);
0634: }
0635:
0636: /**
0637: * Adds to an array w, a times v where a is a scalar.
0638: * Since v can be smaller then w, we must specified the position at which v will be added.
0639: * @param a scalar.
0640: * @param p position.
0641: */
0642: public static double[] add(double[] w, double a, double[] v, int p) {
0643: if (v.length > w.length) {
0644: throw new IllegalArgumentException(
0645: "Second array must be shorter or equal to the first one : "
0646: + w.length + ", " + v.length);
0647: }
0648: double[] ans = copy(w);
0649: for (int k = p; k < p + v.length; k++) {
0650: ans[k] += a * v[k - p];
0651: }
0652: return (ans);
0653: }
0654:
0655: /**
0656: * Adds a scalar to every element in the array.
0657: */
0658: public static double[] add(double[] w, double a) {
0659: double[] ans = copy(w);
0660: for (int k = 0; k < ans.length; k++) {
0661: ans[k] += a;
0662: }
0663: return (ans);
0664: }
0665:
0666: /**
0667: * Takes the transpose of an array (like the matrix operation).
0668: * @exception IllegalArgumentException if the array is not a matrix
0669: */
0670: public static double[][] transpose(double[][] M) {
0671: double[][] Mt = new double[M[0].length][M.length];
0672: for (int i = 0; i < M.length; i++) {
0673: if (M[i].length != M[0].length) {
0674: throw new IllegalArgumentException(
0675: "The array is not a matrix.");
0676: }
0677: for (int j = 0; j < M[0].length; j++) {
0678: Mt[j][i] = M[i][j];
0679: }
0680: }
0681: return (Mt);
0682: }
0683:
0684: /**
0685: * Generates an array going for a to b
0686: * with steps of size step. If it can't
0687: * get to the value b in a finite number
0688: * of steps, it gets as close as possible
0689: * (a can be larger or smaller than b)
0690: * @param step size of steps, must be positive.
0691: * @param a first value of array.
0692: * @param b last value of array.
0693: * @exception IllegalArgumentException if step is negative of if a=b.
0694: */
0695: public static double[] range(double a, double b, double step) {
0696: if (step <= 0.0) {
0697: throw new IllegalArgumentException(
0698: "The argument step should be positive: " + step
0699: + " < 0");
0700: }
0701: if (a == b) {
0702: double[] ans = new double[1];
0703: ans[0] = a;
0704: return (ans);
0705: }
0706: int sizeOfArray = (new Double(Math.abs(a - b) / step))
0707: .intValue() + 1;
0708: double[] ans = new double[sizeOfArray];
0709: ans[0] = a;
0710: if (a > b) {
0711: step = -step;
0712: }
0713: for (int k = 1; k < sizeOfArray; k++) {
0714: ans[k] = ans[k - 1] + step;
0715: }
0716: return (ans);
0717: }
0718:
0719: /**
0720: * Generates an array going for a to b
0721: * inclusively with steps of size 1. a can be
0722: * smaller or larger than b.
0723: */
0724: public static double[] range(double a, double b) {
0725: return (range(a, b, 1.0));
0726: }
0727:
0728: /**
0729: * Generates an array going for 0 to b
0730: * with steps of size 1. 0 can be
0731: * smaller or larger than b.
0732: */
0733: public static double[] range(double b) {
0734: return (range(0, b));
0735: }
0736:
0737: /**
0738: * Adds the two arrays together (componentwise).
0739: * @exception IllegalArgumentException if the
0740: * two arrays don't have the same length.
0741: */
0742: public static double[] add(double[] a, double[] b) {
0743: if (a.length != b.length) {
0744: throw new IllegalArgumentException(
0745: "To add two arrays, they must have the same length : "
0746: + a.length + ", " + b.length);
0747: }
0748: double[] ans = copy(a);
0749: for (int i = 0; i < a.length; i++) {
0750: ans[i] += b[i];
0751: }
0752: return (ans);
0753: }
0754:
0755: /**
0756: * Subtracts the two arrays together (componentwise)
0757: * @exception IllegalArgumentException if the
0758: * two arrays don't have the same length.
0759: */
0760: public static double[] subtract(double[] a, double[] b) {
0761: if (a.length != b.length) {
0762: throw new IllegalArgumentException(
0763: "To add two arrays, they must have the same length : "
0764: + a.length + ", " + b.length);
0765: }
0766: double[] ans = copy(a);
0767: for (int i = 0; i < a.length; i++) {
0768: ans[i] -= b[i];
0769: }
0770: return (ans);
0771: }
0772:
0773: /**
0774: * Multiplies every component of an array by a scalar.
0775: */
0776: public static double[] scalarMultiply(double a, double[] v) {
0777: double[] ans = new double[v.length];
0778: for (int k = 0; k < v.length; k++) {
0779: ans[k] = a * v[k];
0780: }
0781: return (ans);
0782: }
0783:
0784: /**
0785: * Returns a comma delimited string representing the value of the array.
0786: */
0787: public static String toString(double[] array) {
0788:
0789: StringBuffer buf = new StringBuffer(array.length);
0790: int i;
0791: for (i = 0; i < array.length - 1; i++) {
0792: buf.append(array[i]);
0793: buf.append(',');
0794: }
0795: buf.append(array[i]);
0796: return buf.toString();
0797: }
0798:
0799: /**
0800: * Returns a comma delimited string representing the value of the array.
0801: */
0802: public static String toString(double[][] array) {
0803: StringBuffer buf = new StringBuffer();
0804: for (int k = 0; k < array.length; k++) {
0805: buf.append(toString(array[k]));
0806: buf.append(System.getProperty("line.separator"));
0807: }
0808: return buf.toString();
0809: }
0810:
0811: /**
0812: * Returns the sum of the elements of the array.
0813: */
0814: public static double mass(double[] v) {
0815: double somme = 0.0;
0816: for (int k = 0; k < v.length; k++) {
0817: somme += v[k];
0818: }
0819: return (somme);
0820: }
0821:
0822: /**
0823: * Fast scalar multiplication for sparse arrays.
0824: */
0825: public static double[] scalarMultiplyFast(double a, double[] v) {
0826: if (a == 0.0)
0827: return (new double[v.length]);
0828: double[] ans = new double[v.length];
0829: for (int k = 0; k < v.length; k++) {
0830: if ((a != 0.0) && (v[k] != 0)) {
0831: ans[k] = v[k] * a;
0832: } else
0833: ans[k] = 0.0;
0834: }
0835: return (ans);
0836: }
0837:
0838: /**
0839: * Prints an array to screen.
0840: */
0841: public static void print(double[] v) {
0842: for (int k = 0; k < v.length; k++) {
0843: System.out.println("array [" + k + "] = " + v[k]);
0844: }
0845: }
0846:
0847: /**
0848: * Prints an array to screen.
0849: */
0850: public static void print(double[][] v) {
0851: for (int k = 0; k < v.length; k++) {
0852: for (int l = 0; l < v[k].length; l++) {
0853: System.out.println("array [" + k + "][" + l + "] = "
0854: + v[k][l]);
0855: }
0856: }
0857: }
0858:
0859: /**
0860: * Sets an array to the specified length scraping or
0861: * padding the beginning if necessary.
0862: */
0863: public static int[] setLengthFromEnd(int[] data, int length) {
0864: int[] ans = new int[length];
0865: int debut;
0866: if (length - data.length < 0)
0867: debut = data.length - length;
0868: else
0869: debut = 0;
0870: System.arraycopy(data, debut, ans, -data.length + length
0871: + debut, data.length - debut);
0872: return (ans);
0873: }
0874:
0875: /**
0876: * Sets an array to the specified length scraping or
0877: * padding the end if necessary.
0878: */
0879: public static int[] setLengthFromBeginning(int[] data, int length) {
0880: int[] ans = new int[length];
0881: int debut;
0882: if (length - data.length < 0)
0883: debut = data.length - length;
0884: else
0885: debut = 0;
0886: System.arraycopy(data, 0, ans, 0, data.length - debut);
0887: return (ans);
0888: }
0889:
0890: /**
0891: * Returns a copy of the array.
0892: */
0893: public static int[] copy(int[] v) {
0894: int[] ans = new int[v.length];
0895: System.arraycopy(v, 0, ans, 0, v.length);
0896: return (ans);
0897: }
0898:
0899: /**
0900: * Returns a copy of the array.
0901: */
0902: public static int[][] copy(int[][] v) {
0903: int[][] ans = new int[v.length][];
0904: for (int k = 0; k < v.length; k++)
0905: ans[k] = copy(v[k]);
0906: return (ans);
0907: }
0908:
0909: /**
0910: * Computes the variance.
0911: */
0912: public static double variance(int[] v) {
0913: final double m = mean(v);
0914: double ans = 0.0;
0915: for (int i = 0; i < v.length; i++)
0916: ans += (v[i] - m) * (v[i] - m);
0917: return ans / (v.length - 1);
0918: }
0919:
0920: /**
0921: * Computes the covariance.
0922: */
0923: public static double covariance(int[] v1, int[] v2) {
0924: if (v1.length != v2.length)
0925: throw new IllegalArgumentException(
0926: "Arrays must have the same length : " + v1.length
0927: + ", " + v2.length);
0928: final double m1 = mean(v1);
0929: final double m2 = mean(v2);
0930: double ans = 0.0;
0931: for (int i = 0; i < v1.length; i++)
0932: ans += (v1[i] - m1) * (v2[i] - m2);
0933: return ans / (v1.length - 1);
0934: }
0935:
0936: /**
0937: * Computes the (linear) correlation between two arrays.
0938: * Squaring this result and multiply by 100 gives you
0939: * the percentage of correlation.
0940: */
0941: public static double correlation(int[] v1, int[] v2) {
0942: double denom = Math.sqrt(variance(v1) * variance(v2));
0943: if (denom != 0)
0944: return (covariance(v1, v2) / denom);
0945: else {
0946: if ((variance(v1) == 0) && (variance(v2) == 0))
0947: return (1.0);
0948: else
0949: return (0.0); // impossible to correlate a null signal with another
0950: }
0951: }
0952:
0953: /**
0954: * Computes the mean.
0955: */
0956: public static double mean(int[] v) {
0957: if (v.length == 0)
0958: throw new IllegalArgumentException(
0959: "Nothing to compute! The array must have at least one element.");
0960: return (mass(v) / (double) v.length);
0961: }
0962:
0963: /**
0964: * Returns the standard deviation of an array.
0965: */
0966: public static double standardDeviation(int[] v) {
0967: return (Math.sqrt(variance(v)));
0968: }
0969:
0970: /**
0971: * Returns a sorted array from the minimum to the maximum value.
0972: */
0973: public static int[] sortMinToMax(int[] v) {
0974: int[] ans = copy(v);
0975: quickSortMinToMax(ans, 0, ans.length - 1);
0976: return (ans);
0977: }
0978:
0979: /**
0980: * Returns a sorted array from the maximum to the minimum value.
0981: */
0982: public static int[] sortMaxToMin(int[] v) {
0983: int[] ans = copy(v);
0984: quickSortMaxToMin(ans, 0, ans.length - 1);
0985: return (ans);
0986: }
0987:
0988: /**
0989: * Returns a comma delimited string representing the value of the array.
0990: */
0991: public static String toString(int[] array) {
0992: StringBuffer buf = new StringBuffer(array.length);
0993: int i;
0994: for (i = 0; i < array.length - 1; i++) {
0995: buf.append(array[i]);
0996: buf.append(',');
0997: }
0998: buf.append(array[i]);
0999: return buf.toString();
1000: }
1001:
1002: /**
1003: * Returns a comma delimited string representing the value of the array.
1004: */
1005: public static String toString(int[][] array) {
1006: StringBuffer buf = new StringBuffer();
1007: for (int k = 0; k < array.length; k++) {
1008: buf.append(toString(array[k]));
1009: buf.append(System.getProperty("line.separator"));
1010: }
1011: return buf.toString();
1012: }
1013:
1014: /**
1015: * Gives the percentile of an array.
1016: * @param v an unsorted array
1017: * @param p percentile, must be between 0 and 1
1018: * @exception IllegalArgumentException if parameter
1019: * p is not between 0 and 1.
1020: */
1021: public static double percentile(int[] v, double p) {
1022: return percentile(v, p, false);
1023: }
1024:
1025: /**
1026: * @param isSorted true if the array is already sorted into ascending numerical order.
1027: */
1028: public static double percentile(int[] v, double p, boolean isSorted) {
1029: if ((p < 0) || (p > 1)) {
1030: throw new IllegalArgumentException(
1031: "Percentile must be between 0 and 1 : " + p);
1032: }
1033: final int[] ans = (isSorted ? v : sortMinToMax(v));
1034: final int pos = (int) Math.floor(p * (ans.length - 1));
1035: final double dif = p * (ans.length - 1)
1036: - Math.floor(p * (ans.length - 1));
1037: if (pos == (ans.length - 1))
1038: return (ans[ans.length - 1]);
1039: else
1040: return (ans[pos] * (1.0 - dif) + ans[pos + 1] * dif);
1041: }
1042:
1043: /**
1044: * Computes the median of an array.
1045: * If the array contains an even number of elements,
1046: * the lower median is returned.
1047: */
1048: public static int median(int[] v) {
1049: if (v.length == 3) {
1050: return median3(copy(v));
1051: } else if (v.length == 5) {
1052: return median5(copy(v));
1053: } else if (v.length == 7) {
1054: return median7(copy(v));
1055: } else {
1056: return quickSelect(copy(v));
1057: }
1058: }
1059:
1060: /*
1061: * http://ndevilla.free.fr/median/median/index.html
1062: * optmed.c
1063: * @author N. Devillard
1064: */
1065: private static void sortInPlace(final int[] v, final int i,
1066: final int j) {
1067: if (v[i] > v[j]) {
1068: final int tmp = v[i];
1069: v[i] = v[j];
1070: v[j] = tmp;
1071: }
1072: }
1073:
1074: private static int median3(int[] v) {
1075: sortInPlace(v, 0, 1);
1076: sortInPlace(v, 1, 2);
1077: sortInPlace(v, 0, 1);
1078: return v[1];
1079: }
1080:
1081: private static int median5(int[] v) {
1082: sortInPlace(v, 0, 1);
1083: sortInPlace(v, 3, 4);
1084: sortInPlace(v, 0, 3);
1085: sortInPlace(v, 1, 4);
1086: sortInPlace(v, 1, 2);
1087: sortInPlace(v, 2, 3);
1088: sortInPlace(v, 1, 2);
1089: return v[2];
1090: }
1091:
1092: private static int median7(int[] v) {
1093: sortInPlace(v, 0, 5);
1094: sortInPlace(v, 0, 3);
1095: sortInPlace(v, 1, 6);
1096: sortInPlace(v, 2, 4);
1097: sortInPlace(v, 0, 1);
1098: sortInPlace(v, 3, 5);
1099: sortInPlace(v, 2, 6);
1100: sortInPlace(v, 2, 3);
1101: sortInPlace(v, 3, 6);
1102: sortInPlace(v, 4, 5);
1103: sortInPlace(v, 1, 4);
1104: sortInPlace(v, 1, 3);
1105: sortInPlace(v, 3, 4);
1106: return v[3];
1107: }
1108:
1109: /*
1110: * http://ndevilla.free.fr/median/median/index.html
1111: * quickselect.c
1112: * @author N. Devillard
1113: */
1114: private static int quickSelect(int[] v) {
1115: int low = 0, high = v.length - 1;
1116: final int median = high / 2;
1117: int middle, ll, hh;
1118:
1119: for (;;) {
1120: if (high <= low) { /* One element only */
1121: return v[median];
1122: }
1123:
1124: if (high == low + 1) { /* Two elements only */
1125: if (v[low] > v[high])
1126: swap(v, low, high);
1127: return v[median];
1128: }
1129:
1130: /* Find median of low, middle and high items; swap into position low */
1131: middle = (low + high) / 2;
1132: if (v[middle] > v[high])
1133: swap(v, middle, high);
1134: if (v[low] > v[high])
1135: swap(v, low, high);
1136: if (v[middle] > v[low])
1137: swap(v, middle, low);
1138:
1139: /* Swap low item (now in position middle) into position (low+1) */
1140: swap(v, middle, low + 1);
1141:
1142: /* Nibble from each end towards middle, swapping items when stuck */
1143: ll = low + 1;
1144: hh = high;
1145: for (;;) {
1146: do
1147: ll++;
1148: while (v[low] > v[ll]);
1149: do
1150: hh--;
1151: while (v[hh] > v[low]);
1152:
1153: if (hh < ll)
1154: break;
1155:
1156: swap(v, ll, hh);
1157: }
1158:
1159: /* Swap middle item (in position low) back into correct position */
1160: swap(v, low, hh);
1161:
1162: /* Re-set active partition */
1163: if (hh <= median)
1164: low = ll;
1165: if (hh >= median)
1166: high = hh - 1;
1167: }
1168: }
1169:
1170: /**
1171: * Use java.util.Arrays instead.
1172: * Check if two arrays are equal.
1173: * @deprecated Use java.util.Arrays instead.
1174: */
1175: public static boolean equals(int[] a, int[] b) {
1176: if (a.length != b.length) {
1177: return (false);
1178: }
1179: for (int i = 0; i < a.length; i++) {
1180: if (a[i] != b[i]) {
1181: return (false);
1182: }
1183: }
1184: return (true);
1185: }
1186:
1187: /**
1188: * Takes the absolute value of each component of an array.
1189: */
1190: public static int[] abs(int[] v) {
1191: int[] ans = new int[v.length];
1192: for (int i = 0; i < v.length; i++) {
1193: ans[i] = Math.abs(v[i]);
1194: }
1195: return (ans);
1196: }
1197:
1198: /**
1199: * Takes the absolute value of each component of an array.
1200: */
1201: public static int[][] abs(int[][] v) {
1202: int[][] ans = new int[v.length][];
1203: for (int i = 0; i < v.length; i++) {
1204: ans[i] = abs(v[i]);
1205: }
1206: return (ans);
1207: }
1208:
1209: /**
1210: * Returns the maximum of an array.
1211: */
1212: public static int max(int[] v) {
1213: int max = v[0];
1214: for (int i = 1; i < v.length; i++) {
1215: if (max < v[i]) {
1216: max = v[i];
1217: }
1218: }
1219: return (max);
1220: }
1221:
1222: /**
1223: * Returns the maximum of an array.
1224: */
1225: public static int max(int[][] v) {
1226: int max = max(v[0]);
1227: for (int i = 1; i < v.length; i++) {
1228: if (max < max(v[i])) {
1229: max = max(v[i]);
1230: }
1231: }
1232: return (max);
1233: }
1234:
1235: /**
1236: * Returns the minimum of an array.
1237: */
1238: public static int min(int[] v) {
1239: int min = v[0];
1240: for (int i = 1; i < v.length; i++) {
1241: if (min > v[i]) {
1242: min = v[i];
1243: }
1244: }
1245: return (min);
1246: }
1247:
1248: /**
1249: * Returns the minimum of an array.
1250: */
1251: public static int min(int[][] v) {
1252: int min = min(v[0]);
1253: for (int i = 1; i < v.length; i++) {
1254: if (min > min(v[i])) {
1255: min = min(v[i]);
1256: }
1257: }
1258: return (min);
1259: }
1260:
1261: /**
1262: * Computes the L2 norm of an array (Euclidean norm or "length").
1263: */
1264: public static double norm(int[] data) {
1265: return (Math.sqrt(sumSquares(data)));
1266: }
1267:
1268: /**
1269: * Sums the squares of all components;
1270: * also called the energy of the array.
1271: */
1272: public static int sumSquares(int[] data) {
1273: int ans = 0;
1274: for (int k = 0; k < data.length; k++) {
1275: ans += data[k] * data[k];
1276: }
1277: return (ans);
1278: }
1279:
1280: /**
1281: * Sums the squares of all components;
1282: * also called the energy of the array.
1283: */
1284: public static int sumSquares(int[][] data) {
1285: int ans = 0;
1286: for (int k = 0; k < data.length; k++) {
1287: for (int l = 0; l < data[k].length; l++) {
1288: ans += data[k][l] * data[k][l];
1289: }
1290: }
1291: return (ans);
1292: }
1293:
1294: /**
1295: * Computes the scalar product of two array
1296: * as if they were vectors.
1297: * @exception IllegalArgumentException if the
1298: * don't have the same length.
1299: */
1300: public static int scalarProduct(int[] w0, int[] w1) {
1301: if (w0.length != w1.length) {
1302: throw new IllegalArgumentException(
1303: "Arrays must have the same length : " + w0.length
1304: + ", " + w1.length);
1305: }
1306: if (w0.length == 0)
1307: throw new IllegalArgumentException(
1308: "Nothing to compute! Arrays must have at least one element.");
1309: int sortie = 0;
1310: for (int k = 0; k < w0.length; k++) {
1311: sortie = sortie + w0[k] * w1[k];
1312: }
1313: return (sortie);
1314: }
1315:
1316: /**
1317: * Computes the scalar product of two array
1318: * as if they were matrices.
1319: * @exception IllegalArgumentException if the
1320: * don't have the same length.
1321: */
1322: public static double scalarProduct(int[][] w0, int[][] w1) {
1323: if (w0.length != w1.length) {
1324: throw new IllegalArgumentException(
1325: "Arrays must have the same length : " + w0.length
1326: + ", " + w1.length);
1327: }
1328: if (w0.length == 0)
1329: throw new IllegalArgumentException(
1330: "Nothing to compute! Arrays must have at least one element.");
1331: double sortie = 0.0;
1332: for (int k = 0; k < w0.length; k++) {
1333: sortie = sortie + scalarProduct(w0[k], w1[k]);
1334: }
1335: return (sortie);
1336: }
1337:
1338: /**
1339: * Extracts a sub-array (will invert the
1340: * resulting array if k0 > k1).
1341: * @param k0 location of the first component.
1342: * @param k1 location of the last component.
1343: */
1344: public static int[] extract(int k0, int k1, int[] invect) {
1345: if ((k0 < 0) || (k1 < 0) || (k0 > invect.length - 1)
1346: || (k1 > invect.length - 1)) {
1347: throw new IllegalArgumentException(
1348: "The parameters are incorrect : " + k0 + ", " + k1
1349: + ", " + invect.length);
1350: }
1351: if (k1 > k0) {
1352: int[] ans = new int[k1 - k0 + 1];
1353: System.arraycopy(invect, k0, ans, 0, k1 - k0 + 1);
1354: return (ans);
1355: }
1356: int[] ans = new int[-k1 + k0 + 1];
1357: for (int k = k1; k <= k0; k++) {
1358: ans[k0 - k] = invect[k];
1359: }
1360: return (ans);
1361: }
1362:
1363: /**
1364: * Inverts an array from left to right.
1365: */
1366: public static int[] invert(int[] v) {
1367: int[] w = new int[v.length];
1368: for (int k = 0; k < v.length; k++) {
1369: w[v.length - 1 - k] = v[k];
1370: }
1371: return (w);
1372: }
1373:
1374: /**
1375: * Fills in with zeroes to get to the specified length;
1376: * original array with be at the specified position
1377: * @param n0 length of the new array.
1378: * @param pos position of the old array.
1379: */
1380: public static int[] padding(int n0, int pos, int[] v) {
1381: if ((v.length + pos > n0) || (pos < 0)) {
1382: throw new IllegalArgumentException(
1383: "The array is too long for this : " + n0 + ", "
1384: + pos + ", " + v.length);
1385: }
1386: int[] w = new int[n0];
1387: System.arraycopy(v, 0, w, pos, v.length);
1388: return (w);
1389: }
1390:
1391: /**
1392: * Adds to an array w, a times v where a is a scalar.
1393: * Since v can be smaller then w, we must specified the position at which v will be added.
1394: * @param a scalar.
1395: * @param p position.
1396: * @param w longer array.
1397: * @param v shorter array.
1398: * @exception IllegalArgumentException if the second array
1399: * is not shorter than the first one.
1400: */
1401: public static int[] add(int[] w, double a, int[] v, int p) {
1402: if (v.length > w.length) {
1403: throw new IllegalArgumentException(
1404: "Second array must be shorter or equal to the first one : "
1405: + w.length + ", " + v.length);
1406: }
1407: int[] ans = copy(w);
1408: for (int k = p; k < p + v.length; k++) {
1409: ans[k] += a * v[k - p];
1410: }
1411: return (ans);
1412: }
1413:
1414: /**
1415: * Adds a scalar to every element in the array.
1416: */
1417: public static int[] add(int[] w, int a) {
1418: int[] ans = copy(w);
1419: for (int k = 0; k < ans.length; k++) {
1420: ans[k] += a;
1421: }
1422: return (ans);
1423: }
1424:
1425: /**
1426: * Generates an array going for a to b
1427: * with steps of size 1. a can be
1428: * smaller or larger than b.
1429: */
1430: public static int[] range(int a, int b) {
1431: return (range(a, b, 1));
1432: }
1433:
1434: /**
1435: * Generates an array going for 0 to b
1436: * with steps of size 1. 0 can be
1437: * smaller or larger than b.
1438: */
1439: public static int[] range(int b) {
1440: return (range(0, b));
1441: }
1442:
1443: /**
1444: * Generates an array going for a to b
1445: * with steps of size step. If it can't
1446: * get to the value b in a finite number
1447: * of steps, it gets as close as possible
1448: * (a can be larger or smaller than b)
1449: * @param step size of steps, must be positive
1450: * @param a first value of array
1451: * @param b last value of array
1452: * @exception IllegalArgumentException if step is
1453: * negative or if a=b.
1454: */
1455: public static int[] range(int a, int b, int step) {
1456: if (step <= 0) {
1457: throw new IllegalArgumentException(
1458: "The argument step should be positive: " + step
1459: + " < 0");
1460: }
1461: if (a == b) {
1462: int[] ans = new int[1];
1463: ans[0] = a;
1464: return (ans);
1465: }
1466: int sizeOfArray = (new Double(Math.abs(a - b) / step))
1467: .intValue();
1468: int[] ans = new int[sizeOfArray];
1469: ans[0] = a;
1470: if (a > b) {
1471: step = -step;
1472: }
1473: for (int k = 1; k < sizeOfArray; k++) {
1474: ans[k] = ans[k - 1] + step;
1475: }
1476: return (ans);
1477: }
1478:
1479: /**
1480: * Takes the transpose of an array (like the matrix
1481: * operation).
1482: * @exception IllegalArgumentException if the array
1483: * is not a matrix
1484: */
1485: public static int[][] transpose(int[][] M) {
1486: int[][] Mt = new int[M[0].length][M.length];
1487: for (int i = 0; i < M.length; i++) {
1488: if (M[i].length != M[0].length) {
1489: throw new IllegalArgumentException(
1490: "The array is not a matrix.");
1491: }
1492: for (int j = 0; j < M[0].length; j++) {
1493: Mt[j][i] = M[i][j];
1494: }
1495: }
1496: return (Mt);
1497: }
1498:
1499: /**
1500: * Adds the two arrays together (componentwise).
1501: * @exception IllegalArgumentException if the
1502: * two arrays don't have the same length.
1503: */
1504: public static int[] add(int[] a, int[] b) {
1505: if (a.length != b.length) {
1506: throw new IllegalArgumentException(
1507: "To add two arrays, they must have the same length : "
1508: + a.length + ", " + b.length);
1509: }
1510: int[] ans = copy(a);
1511: for (int i = 0; i < a.length; i++) {
1512: ans[i] += b[i];
1513: }
1514: return (ans);
1515: }
1516:
1517: /**
1518: * Subtracts the two arrays together (componentwise).
1519: * @exception IllegalArgumentException if the
1520: * two arrays don't have the same length.
1521: */
1522: public static int[] subtract(int[] a, int[] b) {
1523: if (a.length != b.length) {
1524: throw new IllegalArgumentException(
1525: "To add two arrays, they must have the same length : "
1526: + a.length + ", " + b.length);
1527: }
1528: int[] ans = copy(a);
1529: for (int i = 0; i < a.length; i++) {
1530: ans[i] -= b[i];
1531: }
1532: return (ans);
1533: }
1534:
1535: /**
1536: * Returns the sum of the elements of the array.
1537: */
1538: public static int mass(int[] v) {
1539: int somme = 0;
1540: for (int k = 0; k < v.length; k++) {
1541: somme += v[k];
1542: }
1543: return (somme);
1544: }
1545:
1546: /**
1547: * Multiplies every component of an array by a scalar.
1548: */
1549: public static double[] scalarMultiply(double a, int[] v) {
1550: double[] ans = new double[v.length];
1551: for (int k = 0; k < v.length; k++) {
1552: ans[k] = v[k] * a;
1553: }
1554: return (ans);
1555: }
1556:
1557: /**
1558: * Fast scalar multiplication for sparse arrays.
1559: */
1560: public static double[] scalarMultiplyFast(double a, int[] v) {
1561: if (a == 0.0)
1562: return (new double[v.length]);
1563: double[] ans = new double[v.length];
1564: for (int k = 0; k < v.length; k++) {
1565: if ((a != 0) && (v[k] != 0)) {
1566: ans[k] = v[k] * a;
1567: } else
1568: ans[k] = 0.0;
1569: }
1570: return (ans);
1571: }
1572:
1573: /**
1574: * Prints an array to screen.
1575: */
1576: public static void print(int[] v) {
1577: for (int k = 0; k < v.length; k++) {
1578: System.out.println("array [" + k + "] = " + v[k]);
1579: }
1580: }
1581:
1582: /**
1583: * Prints an array to screen.
1584: */
1585: public static void print(int[][] v) {
1586: for (int k = 0; k < v.length; k++) {
1587: for (int l = 0; l < v[k].length; l++) {
1588: System.out.println("array [" + k + "][" + l + "] = "
1589: + v[k][l]);
1590: }
1591: }
1592: }
1593:
1594: /**
1595: * This is a generic version of C.A.R Hoare's Quick Sort
1596: * algorithm. This will handle arrays that are already
1597: * sorted, and arrays with duplicate keys.<BR>
1598: *
1599: * If you think of a one dimensional array as going from
1600: * the lowest index on the left to the highest index on the right
1601: * then the parameters to this function are lowest index or
1602: * left and highest index or right. The first time you call
1603: * this function it will be with the parameters 0, a.length - 1.
1604: * (taken out of a code by James Gosling and Kevin A. Smith provided
1605: * with Sun's JDK 1.1.7)
1606: *
1607: * @param a an integer array
1608: * @param lo0 left boundary of array partition (inclusive).
1609: * @param hi0 right boundary of array partition (inclusive).
1610: * @deprecated
1611: */
1612: private static void quickSortMinToMax(int a[], int lo0, int hi0) {
1613: int lo = lo0;
1614: int hi = hi0;
1615: int mid;
1616:
1617: if (hi0 > lo0) {
1618:
1619: /* Arbitrarily establishing partition element as the midpoint of
1620: * the array.
1621: */
1622: mid = a[(int) Math.round((lo0 + hi0) / 2.0)];
1623:
1624: // loop through the array until indices cross
1625: while (lo <= hi) {
1626: /* find the first element that is greater than or equal to
1627: * the partition element starting from the left Index.
1628: */
1629: while ((lo < hi0) && (a[lo] < mid))
1630: ++lo;
1631:
1632: /* find an element that is smaller than or equal to
1633: * the partition element starting from the right Index.
1634: */
1635: while ((hi > lo0) && (a[hi] > mid))
1636: --hi;
1637:
1638: // if the indexes have not crossed, swap
1639: if (lo <= hi) {
1640: swap(a, lo, hi);
1641: ++lo;
1642: --hi;
1643: }
1644: }
1645:
1646: /* If the right index has not reached the left side of array
1647: * must now sort the left partition.
1648: */
1649: if (lo0 < hi)
1650: quickSortMinToMax(a, lo0, hi);
1651:
1652: /* If the left index has not reached the right side of array
1653: * must now sort the right partition.
1654: */
1655: if (lo < hi0)
1656: quickSortMinToMax(a, lo, hi0);
1657:
1658: }
1659: }
1660:
1661: /** This is a generic version of C.A.R Hoare's Quick Sort
1662: * algorithm. This will handle arrays that are already
1663: * sorted, and arrays with duplicate keys.<BR>
1664: *
1665: * If you think of a one dimensional array as going from
1666: * the lowest index on the left to the highest index on the right
1667: * then the parameters to this function are lowest index or
1668: * left and highest index or right. The first time you call
1669: * this function it will be with the parameters 0, a.length - 1.
1670: * (taken out of a code by James Gosling and Kevin A. Smith provided
1671: * with Sun's JDK 1.1.7)
1672: *
1673: * @param a an integer array
1674: * @param lo0 left boundary of array partition (inclusive).
1675: * @param hi0 right boundary of array partition (inclusive).
1676: */
1677: private static void quickSortMaxToMin(int a[], int lo0, int hi0) {
1678: int lo = lo0;
1679: int hi = hi0;
1680: int mid;
1681:
1682: if (hi0 > lo0) {
1683:
1684: /* Arbitrarily establishing partition element as the midpoint of
1685: * the array.
1686: */
1687: mid = a[(int) Math.round((lo0 + hi0) / 2.0)];
1688:
1689: // loop through the array until indices cross
1690: while (lo <= hi) {
1691: /* find the first element that is greater than or equal to
1692: * the partition element starting from the left Index.
1693: */
1694: while ((lo < hi0) && (a[lo] > mid))
1695: ++lo;
1696:
1697: /* find an element that is smaller than or equal to
1698: * the partition element starting from the right Index.
1699: */
1700: while ((hi > lo0) && (a[hi] < mid))
1701: --hi;
1702:
1703: // if the indexes have not crossed, swap
1704: if (lo <= hi) {
1705: swap(a, lo, hi);
1706: ++lo;
1707: --hi;
1708: }
1709: }
1710:
1711: /* If the right index has not reached the left side of array
1712: * must now sort the left partition.
1713: */
1714: if (lo0 < hi)
1715: quickSortMaxToMin(a, lo0, hi);
1716:
1717: /* If the left index has not reached the right side of array
1718: * must now sort the right partition.
1719: */
1720: if (lo < hi0)
1721: quickSortMaxToMin(a, lo, hi0);
1722:
1723: }
1724: }
1725:
1726: /**
1727: * This is a generic version of C.A.R Hoare's Quick Sort
1728: * algorithm. This will handle arrays that are already
1729: * sorted, and arrays with duplicate keys.<BR>
1730: *
1731: * If you think of a one dimensional array as going from
1732: * the lowest index on the left to the highest index on the right
1733: * then the parameters to this function are lowest index or
1734: * left and highest index or right. The first time you call
1735: * this function it will be with the parameters 0, a.length - 1.
1736: * (taken out of a code by James Gosling and Kevin A. Smith provided
1737: * with Sun's JDK 1.1.7)
1738: *
1739: * @param a a double array
1740: * @param lo0 left boundary of array partition (inclusive).
1741: * @param hi0 right boundary of array partition (inclusive).
1742: * @deprecated
1743: */
1744: private static void quickSortMinToMax(double a[], int lo0, int hi0) {
1745: int lo = lo0;
1746: int hi = hi0;
1747: double mid;
1748:
1749: if (hi0 > lo0) {
1750:
1751: /* Arbitrarily establishing partition element as the midpoint of
1752: * the array.
1753: */
1754: mid = a[(int) Math.round((lo0 + hi0) / 2.0)];
1755:
1756: // loop through the array until indices cross
1757: while (lo <= hi) {
1758: /* find the first element that is greater than or equal to
1759: * the partition element starting from the left Index.
1760: */
1761: while ((lo < hi0) && (a[lo] < mid))
1762: ++lo;
1763:
1764: /* find an element that is smaller than or equal to
1765: * the partition element starting from the right Index.
1766: */
1767: while ((hi > lo0) && (a[hi] > mid))
1768: --hi;
1769:
1770: // if the indexes have not crossed, swap
1771: if (lo <= hi) {
1772: swap(a, lo, hi);
1773: ++lo;
1774: --hi;
1775: }
1776: }
1777:
1778: /* If the right index has not reached the left side of array
1779: * must now sort the left partition.
1780: */
1781: if (lo0 < hi)
1782: quickSortMinToMax(a, lo0, hi);
1783:
1784: /* If the left index has not reached the right side of array
1785: * must now sort the right partition.
1786: */
1787: if (lo < hi0)
1788: quickSortMinToMax(a, lo, hi0);
1789:
1790: }
1791: }
1792:
1793: /**
1794: * This is a generic version of C.A.R Hoare's Quick Sort
1795: * algorithm. This will handle arrays that are already
1796: * sorted, and arrays with duplicate keys.<BR>
1797: *
1798: * If you think of a one dimensional array as going from
1799: * the lowest index on the left to the highest index on the right
1800: * then the parameters to this function are lowest index or
1801: * left and highest index or right. The first time you call
1802: * this function it will be with the parameters 0, a.length - 1.
1803: * (taken out of a code by James Gosling and Kevin A. Smith provided
1804: * with Sun's JDK 1.1.7)
1805: *
1806: * @param a a double array
1807: * @param lo0 left boundary of array partition (inclusive).
1808: * @param hi0 right boundary of array partition (inclusive).
1809: */
1810: private static void quickSortMaxToMin(double a[], int lo0, int hi0) {
1811: int lo = lo0;
1812: int hi = hi0;
1813: double mid;
1814:
1815: if (hi0 > lo0) {
1816:
1817: /* Arbitrarily establishing partition element as the midpoint of
1818: * the array.
1819: */
1820: mid = a[(int) Math.round((lo0 + hi0) / 2.0)];
1821:
1822: // loop through the array until indices cross
1823: while (lo <= hi) {
1824: /* find the first element that is greater than or equal to
1825: * the partition element starting from the left Index.
1826: */
1827: while ((lo < hi0) && (a[lo] > mid))
1828: ++lo;
1829:
1830: /* find an element that is smaller than or equal to
1831: * the partition element starting from the right Index.
1832: */
1833: while ((hi > lo0) && (a[hi] < mid))
1834: --hi;
1835:
1836: // if the indexes have not crossed, swap
1837: if (lo <= hi) {
1838: swap(a, lo, hi);
1839: ++lo;
1840: --hi;
1841: }
1842: }
1843:
1844: /* If the right index has not reached the left side of array
1845: * must now sort the left partition.
1846: */
1847: if (lo0 < hi)
1848: quickSortMaxToMin(a, lo0, hi);
1849:
1850: /* If the left index has not reached the right side of array
1851: * must now sort the right partition.
1852: */
1853: if (lo < hi0)
1854: quickSortMaxToMin(a, lo, hi0);
1855:
1856: }
1857: }
1858:
1859: /**
1860: * Used by the quick sort and quick select algorithms.
1861: */
1862: private static void swap(final int a[], final int i, final int j) {
1863: final int T;
1864: T = a[i];
1865: a[i] = a[j];
1866: a[j] = T;
1867: }
1868:
1869: /**
1870: * Used by the quick sort and quick select algorithms.
1871: */
1872: private static void swap(final double a[], final int i, final int j) {
1873: final double T;
1874: T = a[i];
1875: a[i] = a[j];
1876: a[j] = T;
1877:
1878: }
1879: }
|