ArrayMath


1   package JSci.maths;
2   
3   import JSci.GlobalSettings;
4   
5   /**
6   * Arrays are faster than object, so this class is here to take full
7   * advantage of arrays without encapsulation.
8   * All methods are safe, that is, they create copies of arrays whenever
9   * necessary
10  * This makes for slower methods, but the programmer can always
11  * define his own methods optimized for performance.
12  * @author Daniel Lemire
13  * @author Mark Hale
14  */
15  public final class ArrayMath extends AbstractMath {
16          private ArrayMath() {}
17  
18          public static boolean isSquare(double[][] a) {
19                  for(int i=0; i<a.length; i++) {
20                          if(a[i].length != a.length)
21                                  return false;
22                  }
23                  return true;
24          }
25          public static boolean isSquare(int[][] a) {
26                  for(int i=0; i<a.length; i++) {
27                          if(a[i].length != a.length)
28                                  return false;
29                  }
30                  return true;
31          }
32          public static boolean isSquare(Object  [][] a) {
33                  for(int i=0; i<a.length; i++) {
34                          if(a[i].length != a.length)
35                                  return false;
36                  }
37                  return true;
38          }
39  
40          /**
41          * Applys a map to every component of an array.
42          */
43    public static double[] apply(Mapping m, double[] v) {
44      double[] ans=new double[v.length];
45      for(int k=0;k<v.length;k++) {
46        ans[k]=m.map(v[k]);
47      }
48      return(ans);
49    }
50  
51          /**
52          * Applys a map to every component of an array.
53          */
54    public static double[][] apply(Mapping m, double[][] v) {
55      double[][] ans=new double[v.length][];
56      for(int k=0;k<v.length;k++) {
57        ans[k]=apply(m,v[k]);
58      }
59      return(ans);
60    }
61  
62          /**
63          * Applys a map to every component of an array.
64          */
65    public static Complex[] apply(ComplexMapping m, Complex[] v) {
66      Complex[] ans=new Complex[v.length];
67      for(int k=0;k<v.length;k++) {
68        ans[k]=m.map(v[k]);
69      }
70      return(ans);
71    }
72  
73          /**
74          * Applys a map to every component of an array.
75          */
76    public static Complex[][] apply(ComplexMapping m, Complex[][] v) {
77      Complex[][] ans=new Complex[v.length][];
78      for(int k=0;k<v.length;k++) {
79        ans[k]=apply(m,v[k]);
80      }
81      return(ans);
82    }
83          /**
84          * Renormalizes the array so that its L2 norm is 1
85          * (up to computational errors).
86          */
87    public static double[] normalize(double[] v) {
88      return(scalarMultiply(1.0/norm(v),v));
89    }
90  
91          /**
92          * Sets an array to the specified length scraping or
93          * padding the beginning if necessary.
94          */
95          public static double[] setLengthFromEnd(double[] data, int length) {
96                  double[] ans = new double[length];
97                  int debut;
98                  if(length-data.length<0)
99        debut = data.length-length;
100                 else
101       debut = 0;
102     System.arraycopy(data,debut,ans,-data.length+length+debut,data.length-debut);
103                 return(ans);
104         }
105 
106         /**
107         * Sets an array to the specified length scraping or
108         * padding the end if necessary.
109         */
110         public static double[] setLengthFromBeginning(double[] data, int length) {
111                 double[] ans = new double[length];
112                 int debut;
113                 if(length-data.length<0)
114       debut=data.length-length;
115                 else
116       debut = 0;
117     System.arraycopy(data,0,ans,0,data.length-debut);
118                 return(ans);
119         }
120 
121 
122         /**
123         * Returns a copy of the array.
124         */
125         public static double[] copy(final double[] v) {
126                 double[] ans = new double[v.length];
127     System.arraycopy(v,0,ans,0,v.length);
128                 return(ans);
129         }
130         /**
131         * Returns a copy of the array.
132         */
133         public static double[][] copy(double[][] v) {
134                 double[][] ans = new double[v.length][];
135     for (int k=0;k<v.length;k++)
136       ans[k]=copy(v[k]);
137                 return(ans);
138         }
139 
140 
141         /**
142         * Computes the variance.
143         */
144         public static double variance(double[] v) {
145                 final double m = mean(v);
146                 double ans=0.0;
147                 for(int i=0;i<v.length;i++)
148                         ans+=(v[i]-m)*(v[i]-m);
149                 return ans/(v.length-1);
150         }
151 
152         /**
153         * Computes the covariance.
154         */
155         public static double covariance(double[] v1 , double[] v2) {
156                 if(v1.length!=v2.length)
157                         throw new IllegalArgumentException  ("Arrays must have the same length : "+v1.length+", "+v2.length);
158                 final double m1 = mean(v1);
159                 final double m2 = mean(v2);
160                 double ans=0.0;
161                 for(int i=0;i<v1.length;i++)
162                         ans+=(v1[i]-m1)*(v2[i]-m2);
163                 return ans/(v1.length-1);
164         }
165 
166         /**
167         * Computes the (linear) correlation between two arrays.
168         * Squaring this result and multiply by 100 gives you
169         * the percentage of correlation.
170         */
171   public static double correlation(double[] v1, double[] v2) {
172     double denom=Math.sqrt(variance(v1)*variance(v2));
173     if(denom!=0)
174       return(covariance(v1,v2)/denom);
175     else {
176       if((variance(v1)==0) &&(variance(v2)==0))
177         return(1.0);
178       else return(0.0);  // impossible to correlate a null signal with another
179     }
180   }
181 
182         /**
183         * Computes the mean.
184         */
185         public static double mean(double[] v) {
186     if(v.length==0)
187       throw new IllegalArgumentException  ("Nothing to compute! The array must have at least one element.");
188                 return(mass(v)/(double)v.length);
189         }
190 
191         /**
192         * Computes the standard deviation of an array.
193         */
194         public static double standardDeviation(double[] v) {
195                 return(Math.sqrt(variance(v)));
196         }
197 
198 
199         /**
200         * Returns a sorted array from the minimum to the maximum value.
201         */
202         public static double[] sortMinToMax(double[] v) {
203     double[] ans=copy(v);
204     quickSortMinToMax(ans, 0, ans.length - 1);
205     return(ans);
206         }
207 
208         /**
209         * Returns a sorted array from the maximum to the minimum value.
210         */
211         public static double[] sortMaxToMin(double[] v) {
212     double[] ans=copy(v);
213     quickSortMaxToMin(ans, 0, ans.length - 1);
214     return(ans);
215         }
216 
217         /**
218         * Gives the percentile of an array.
219     * @param v an unsorted array
220         * @param p percentile, must be between 0 and 1
221         * @exception IllegalArgumentException if parameter.
222         * p is not between 0 and 1.
223         */
224         public static double percentile(double[] v, double p) {
225         return percentile(v, p, false);
226         }
227         public static double percentile(double[] v, double p, boolean isSorted) {
228                 if((p<0) || (p>1)) {
229                         throw new IllegalArgumentException  ("Percentile must be between 0 and 1 : "+p);
230                 }
231                 final double[] ans = (isSorted ? v : sortMinToMax(v));
232                 final int pos = (int) Math.floor(p*(ans.length-1));
233                 final double dif = p*(ans.length-1) - Math.floor(p*(ans.length-1));
234                 if(pos == (ans.length-1))
235                         return(ans[ans.length-1]);
236                 else
237                         return(ans[pos]*(1.0-dif) + ans[pos+1]*dif);
238         }
239 
240         /**
241         * Computes the median of an array.
242         * If the array contains an even number of elements,
243         * then the mean of the lower and upper medians is returned.
244         */
245         public static double median(double[] v) {
246                 if(v.length == 3) {
247                         return median3(copy(v));
248                 } else if(v.length == 5) {
249                         return median5(copy(v));
250                 } else if(v.length == 7) {
251                         return median7(copy(v));
252                 } else if(v.length % 2 == 1) { // odd
253                         return quickSelect(copy(v), false);
254                 } else { // even
255                         double[] tmp = copy(v);
256                         double lowerMedian = quickSelect(tmp, false);
257                         double upperMedian = quickSelect(tmp, true);
258                         return (lowerMedian+upperMedian)/2.0;
259                 }
260         }
261         /*
262         * http://ndevilla.free.fr/median/median/index.html
263         * optmed.c
264         * @author N. Devillard
265         */
266         private static void sortInPlace(final double[] v, final int i, final int j) {
267                 if(v[i] > v[j]) {
268                         final double tmp = v[i];
269                         v[i] = v[j];
270                         v[j] = tmp;
271                 }
272         }
273         private static double median3(double[] v) {
274                 sortInPlace(v,0,1);
275                 sortInPlace(v,1,2);
276                 sortInPlace(v,0,1);
277                 return v[1];
278         }
279         private static double median5(double[] v) {
280                 sortInPlace(v,0,1);
281                 sortInPlace(v,3,4);
282                 sortInPlace(v,0,3);
283                 sortInPlace(v,1,4);
284                 sortInPlace(v,1,2);
285                 sortInPlace(v,2,3);
286                 sortInPlace(v,1,2);
287                 return v[2];
288         }
289         private static double median7(double[] v) {
290                 sortInPlace(v,0,5);
291                 sortInPlace(v,0,3);
292                 sortInPlace(v,1,6);
293                 sortInPlace(v,2,4);
294                 sortInPlace(v,0,1);
295                 sortInPlace(v,3,5);
296                 sortInPlace(v,2,6);
297                 sortInPlace(v,2,3);
298                 sortInPlace(v,3,6);
299                 sortInPlace(v,4,5);
300                 sortInPlace(v,1,4);
301                 sortInPlace(v,1,3);
302                 sortInPlace(v,3,4);
303                 return v[3];
304         }
305         /*
306         * http://ndevilla.free.fr/median/median/index.html
307         * quickselect.c
308         * @author N. Devillard
309         */
310         private static double quickSelect(double[] v, boolean upperMedian) {
311                 int low=0, high=v.length-1;
312                 final int median = upperMedian ? high/2+1 : high/2;
313                 int middle, ll, hh;
314 
315                 for (;;) {
316                         if (high <= low) { /* One element only */
317                                 return v[median];
318                         }
319 
320                         if (high == low + 1) {  /* Two elements only */
321                                 if (v[low] > v[high])
322                                         swap(v, low, high);
323                                 return v[median];
324                         }
325 
326                 /* Find median of low, middle and high items; swap into position low */
327                         middle = (low + high) / 2;
328                         if (v[middle] > v[high]) swap(v, middle, high);
329                         if (v[low] > v[high]) swap(v, low, high);
330                         if (v[middle] > v[low]) swap(v, middle, low);
331 
332                 /* Swap low item (now in position middle) into position (low+1) */
333                         swap(v, middle, low+1);
334 
335                 /* Nibble from each end towards middle, swapping items when stuck */
336                         ll = low + 1;
337                         hh = high;
338                         for (;;) {
339                                 do ll++; while (v[low] > v[ll]);
340                                 do hh--; while (v[hh]  > v[low]);
341 
342                                 if (hh < ll)
343                                         break;
344 
345                                 swap(v, ll, hh);
346                         }
347 
348                 /* Swap middle item (in position low) back into correct position */
349                         swap(v, low, hh);
350 
351                 /* Re-set active partition */
352                         if (hh <= median)
353                                 low = ll;
354                         if (hh >= median)
355                                 high = hh - 1;
356                 }
357         }
358 
359         /**
360         * Checks if two arrays are equal within a tolerance.
361         */
362         public static boolean equals(double[] a, double[] b) {
363                 if(a.length!=b.length)
364                         return(false);
365                 for(int i=0;i<a.length;i++) {
366                         if(Math.abs(a[i]-b[i])>GlobalSettings.ZERO_TOL)
367                                 return(false);
368                 }
369                 return(true);
370         }
371 
372         /**
373         * Takes the absolute value of each component of an array.
374         */
375         public static double[] abs(double[] v) {
376                 double[] ans=new double[v.length];
377                 for(int i=0;i<v.length;i++) {
378                         ans[i]=Math.abs(v[i]);
379                 }
380                 return(ans);
381         }
382 
383         /**
384         * Takes the absolute value of each component of an array.
385         */
386         public static double[][] abs(double[][] v) {
387                 double[][] ans=new double[v.length][];
388                 for(int i=0;i<v.length;i++) {
389                         ans[i]=abs(v[i]);
390                 }
391                 return(ans);
392         }
393 
394         /**
395         * Returns the maximum of an array.
396         */
397         public static double max(double[] v) {
398                 double max=v[0];
399                 for(int i=1;i<v.length;i++) {
400                         if(max<v[i]) {
401                                 max=v[i];
402                         }
403                 }
404                 return(max);
405         }
406 
407         /**
408         * Returns the maximum of an array.
409         */
410         public static double max(double[][] v) {
411                 double max=max(v[0]);
412                 for(int i=1;i<v.length;i++) {
413                         if(max<max(v[i])) {
414                                 max=max(v[i]);
415                         }
416                 }
417                 return(max);
418         }
419 
420         /**
421         * Returns the minimum of an array.
422         */
423         public static double min(double[] v) {
424                 double min=v[0];
425                 for(int i=1;i<v.length;i++) {
426                         if(min>v[i]) {
427                                 min=v[i];
428                         }
429                 }
430                 return(min);
431         }
432 
433         /**
434         * Returns the minimum of an array.
435         */
436         public static double min(double[][] v) {
437                 double min=min(v[0]);
438                 for(int i=1;i<v.length;i++) {
439                         if(min>min(v[i])) {
440                                 min=min(v[i]);
441                         }
442                 }
443                 return(min);
444         }
445 
446         /**
447         * Returns the componentwise modulus of
448         * an array of Complex numbers.
449         */
450   public static double[] mod(Complex[] v) {
451     double[] ans=new double[v.length];
452     for(int k=0;k<v.length;k++) {
453       ans[k]=v[k].mod();
454     }
455     return(ans);
456   }
457 
458         /**
459         * Returns the componentwise modulus of
460         * an array of Complex numbers.
461         */
462   public static double[][] mod(Complex[][] v) {
463     double[][] ans=new double[v.length][];
464     for(int k=0;k<v.length;k++) {
465       ans[k]=mod(v[k]);
466     }
467     return(ans);
468   }
469 
470   public static double sumModSqrs(Complex[] v) {
471     double ans = 0.0;
472     for(int k=0; k<v.length; k++) {
473       ans += v[k].modSqr();
474     }
475     return(ans);
476   }
477   public static double sumModSqrs(Complex[][] v) {
478     double ans = 0.0;
479     for(int k=0; k<v.length; k++) {
480       ans += sumModSqrs(v[k]);
481     }
482     return(ans);
483   }
484 
485         /**
486         * Computes the L2 norm of an array (Euclidean norm or "length").
487         */
488         public static double norm(double[] data) {
489                 return(Math.sqrt(sumSquares(data)));
490         }
491 
492         /**
493         * Sums the squares of all components;
494         * also called the energy of the array.
495         */
496         public static double sumSquares(double[] data) {
497                 double ans=0.0;
498                 for(int k=0;k<data.length;k++) {
499                         ans+=data[k]*data[k];
500                 }
501                 return(ans);
502         }
503 
504         /**
505         * Sums the squares of all components;
506         * also called the energy of the array.
507         */
508         public static double sumSquares(double[][] data) {
509                 double ans=0.0;
510                 for(int k=0;k<data.length;k++) {
511       for(int l=0;l<data[k].length;l++) {
512                           ans+=data[k][l]*data[k][l];
513       }
514                 }
515                 return(ans);
516         }
517 
518         /**
519         * Computes the scalar product of two array as if they were vectors.
520         * @exception IllegalArgumentException if the don't have the same length
521         */
522         public static double scalarProduct(double[] w0,double[] w1) {
523                 if (w0.length!=w1.length) {
524                         throw new IllegalArgumentException  ("Arrays must have the same length : "+w0.length+", "+w1.length);
525                 }
526     if(w0.length==0)
527       throw new IllegalArgumentException  ("Nothing to compute! Arrays must have at least one element.");
528                 double sortie=0.0;
529                 for(int k=0;k<w0.length;k++){
530                         sortie+=w0[k]*w1[k];
531                 }
532                 return(sortie);
533         }
534 
535         /**
536         * Computes the scalar product of two array as if they were matrices.
537         * @exception IllegalArgumentException if the don't have the same length
538         */
539         public static double scalarProduct(double[][] w0,double[][] w1) {
540                 if (w0.length!=w1.length) {
541                         throw new IllegalArgumentException  ("Arrays must have the same length : "+w0.length+", "+w1.length);
542                 }
543     if(w0.length==0)
544       throw new IllegalArgumentException  ("Nothing to compute! Arrays must have at least one element.");
545                 double sortie=0.0;
546                 for(int k=0;k<w0.length;k++){
547                         sortie=sortie+scalarProduct(w0[k],w1[k]);
548                 }
549                 return(sortie);
550         }
551 
552 
553         /**
554         * Extracts a sub-array (will invert the resulting array if k0 > k1).
555         * @param k0 location of the first component
556         * @param k1 location of the last component
557         */
558         public static double[] extract(int k0, int k1, double[] invect) {
559                 if ((k0<0)||(k1<0)||(k0>invect.length-1)||(k1>invect.length-1)) {
560                         throw new IllegalArgumentException  ("The parameters are incorrect : "+k0+", "+k1+", "+invect.length);
561                 }
562                 if(k1>k0) {
563                         double[] ans=new double[k1-k0+1];
564       System.arraycopy(invect,k0,ans,0,k1-k0+1);
565       return(ans);
566                 }
567     double[] ans=new double[-k1+k0+1];
568     for(int k=k1;k<=k0;k++) {
569       ans[k0-k]=invect[k];
570     }
571     return(ans);
572         }
573 
574         /**
575         * Inverts an array from left to right.
576         */
577         public static double [] invert (double[] v) {
578                 double[] w=new double[v.length];
579                 for(int k=0;k<v.length;k++) {
580                         w[v.length-1-k]=v[k];
581                 }
582                 return(w);
583         }
584 
585         /**
586         * Fills in with zero to get to the desired length;
587         * original array with be at the specified position.
588         * @param n0 length of the new array.
589         * @param pos position of the old array.
590         */
591         public static double[] padding(int n0, int pos, double[] v) {
592                 if ((v.length+pos>n0)||(pos<0)) {
593                         throw new IllegalArgumentException  ("Array is to long for this : "+n0+", "+pos+", "+v.length);
594                 }
595                 double[] w=new double[n0];
596     System.arraycopy(v,0,w,pos,v.length);
597                 return(w);
598         }
599 
600 
601 
602         /**
603         * Adds to an array w, a times v where a is a scalar.
604         * Since v can be smaller then w, we must specified the position at which v will be added.
605         * @param a scalar.
606         * @param p position.
607         */
608         public static double[] add(double[]w, double a, double[] v,int p) {
609     if(v.length>w.length) {
610       throw new IllegalArgumentException  ("Second array must be shorter or equal to the first one : "+w.length+", "+v.length);
611     }
612                 double[] ans=copy(w);
613                 for(int k=p;k<p+v.length;k++) {
614                         ans[k]+=a*v[k-p];
615                 }
616                 return(ans);
617         }
618 
619         /**
620         * Adds a scalar to every element in the array.
621         */
622   public static double[] add(double[] w, double a) {
623     double[] ans=copy(w);
624     for(int k=0;k<ans.length;k++) {
625       ans[k]+=a;
626     }
627     return(ans);
628   }
629 
630         /**
631         * Takes the transpose of an array (like the matrix operation).
632         * @exception IllegalArgumentException if the array is not a matrix
633         */
634         public static double[][] transpose (double[][] M) {
635                 double[][] Mt=new double[M[0].length][M.length];
636                 for(int i=0;i<M.length;i++) {
637       if(M[i].length!=M[0].length) {
638         throw new IllegalArgumentException  ("The array is not a matrix.");
639       }
640                         for(int j=0;j<M[0].length;j++) {
641                                 Mt[j][i]=M[i][j];
642                         }
643                 }
644                 return(Mt);
645         }
646 
647   /**
648   * Generates an array going for a to b
649   * with steps of size step. If it can't
650   * get to the value b in a finite number
651   * of steps, it gets as close as possible
652   * (a can be larger or smaller than b)
653   * @param step size of steps, must be positive.
654   * @param a first value of array.
655   * @param b last value of array.
656   * @exception IllegalArgumentException if step is negative of if a=b.
657   */
658   public static double[] range(double a, double b, double step) {
659     if( step<=0.0) {
660       throw new IllegalArgumentException  ("The argument step should be positive: "+step+" < 0");
661     }
662     if( a==b) {
663       double[] ans=new double[1];
664       ans[0]=a;
665       return(ans);
666     }
667     int sizeOfArray=(new Double  (Math.abs(a-b)/step)).intValue()+1;
668     double[] ans=new double[sizeOfArray];
669     ans[0]=a;
670     if(a>b) {
671       step=-step;
672     }
673     for(int k=1;k<sizeOfArray;k++) {
674       ans[k]=ans[k-1]+step;
675     }
676     return(ans);
677   }
678 
679   /**
680   * Generates an array going for a to b
681   * inclusively with steps of size 1. a can be
682   * smaller or larger than b.
683   */
684   public static double[] range(double a, double b) {
685     return(range(a,b,1.0));
686   }
687   /**
688   * Generates an array going for 0 to b
689   * with steps of size 1. 0 can be
690   * smaller or larger than b.
691   */
692   public static double[] range(double b) {
693     return(range(0,b));
694   }
695 
696   /**
697   * Adds the two arrays together (componentwise).
698   * @exception IllegalArgumentException if the
699   * two arrays don't have the same length.
700   */
701         public static double[] add (double[] a, double[] b) {
702                 if (a.length!=b.length) {
703                         throw new IllegalArgumentException  ("To add two arrays, they must have the same length : "+a.length+", "+b.length);
704                 }
705                 double[] ans=copy(a);
706                 for(int i=0;i<a.length;i++) {
707                         ans[i]+=b[i];
708                 }
709                 return(ans);
710         }
711   /**
712   * Subtracts the two arrays together (componentwise)
713   * @exception IllegalArgumentException if the
714   * two arrays don't have the same length.
715   */
716         public static double[] subtract (double[] a, double[] b) {
717                 if (a.length!=b.length) {
718                         throw new IllegalArgumentException  ("To add two arrays, they must have the same length : "+a.length+", "+b.length);
719                 }
720                 double[] ans=copy(a);
721                 for(int i=0;i<a.length;i++) {
722                         ans[i]-=b[i];
723                 }
724                 return(ans);
725         }
726 
727 
728         /**
729         * Multiplies every component of an array by a scalar.
730         */
731         public static double[] scalarMultiply(double a, double[] v) {
732                 double[] ans=new double[v.length];
733                 for(int k=0;k<v.length;k++) {
734                         ans[k]=a*v[k];
735                 }
736                 return(ans);
737         }
738 
739 
740   /**
741   * Returns a comma delimited string representing the value of the array.
742   */
743   public static String   toString(double[] array) {
744 
745           StringBuffer   buf=new StringBuffer  (array.length);
746           int i;
747           for(i=0;i<array.length-1;i++) {
748                   buf.append(array[i]);
749                   buf.append(',');
750           }
751           buf.append(array[i]);
752           return buf.toString();
753   }
754 
755   /**
756   * Returns a comma delimited string representing the value of the array.
757   */
758   public static String   toString(double[][] array) {
759           StringBuffer   buf=new StringBuffer  ();
760           for(int k=0;k<array.length;k++) {
761             buf.append(toString(array[k]));
762             buf.append(System.getProperty("line.separator"));
763           }
764           return buf.toString();
765   }
766 
767         /**
768         * Returns the sum of the elements of the array.
769         */
770         public static double mass(double[] v) {
771                 double somme=0.0;
772                 for(int k=0;k<v.length;k++) {
773                         somme+=v[k];
774                 }
775                 return(somme);
776         }
777 
778         /**
779         * Fast scalar multiplication for sparse arrays.
780         */
781         public static double[] scalarMultiplyFast(double a, double[] v) {
782                 if(a==0.0) return(new double[v.length]);
783                 double[] ans=new double[v.length];
784                 for(int k=0;k<v.length;k++) {
785                         if((a!=0.0) && (v[k]!=0)) {
786                                 ans[k]=v[k]*a;
787                         } else ans[k]=0.0;
788                 }
789                 return(ans);
790         }
791 
792         /**
793         * Prints an array to screen.
794         */
795         public static void print(double[] v) {
796                 for(int k=0;k<v.length;k++) {
797                         System.out.println("array ["+k+"] = "+v[k]);
798                 }
799         }
800 
801         /**
802         * Prints an array to screen.
803         */
804         public static void print(double[][] v) {
805                 for(int k=0;k<v.length;k++) {
806       for(int l=0;l<v[k].length;l++) {
807                           System.out.println("array ["+k+"]["+l+"] = "+v[k][l]);
808       }
809                 }
810         }
811         /**
812         * Sets an array to the specified length scraping or
813         * padding the beginning if necessary.
814         */
815         public static int[] setLengthFromEnd(int[] data, int length) {
816                 int[] ans=new int[length];
817                 int debut;
818                 if(length-data.length<0)
819       debut=data.length-length;
820                 else
821       debut=0;
822     System.arraycopy(data,debut,ans,-data.length+length+debut,data.length-debut);
823                 return(ans);
824         }
825 
826         /**
827         * Sets an array to the specified length scraping or
828         * padding the end if necessary.
829         */
830         public static int[] setLengthFromBeginning (int[] data, int length) {
831                 int[] ans=new int[length];
832                 int debut;
833                 if(length-data.length<0)
834       debut=data.length-length;
835                 else
836       debut=0;
837     System.arraycopy(data,0,ans,0,data.length-debut);
838                 return(ans);
839         }
840 
841 
842         /**
843         * Returns a copy of the array.
844         */
845         public static int[] copy(int[] v) {
846                 int[] ans=new int[v.length];
847     System.arraycopy(v,0,ans,0,v.length);
848                 return(ans);
849         }
850 
851         /**
852         * Returns a copy of the array.
853         */
854         public static int[][] copy(int[][] v) {
855                 int[][] ans=new int[v.length][];
856     for (int k=0;k<v.length;k++)
857       ans[k]=copy(v[k]);
858                 return(ans);
859         }
860 
861         /**
862         * Computes the variance.
863         */
864         public static double variance(int[] v) {
865                 final double m = mean(v);
866                 double ans=0.0;
867                 for(int i=0;i<v.length;i++)
868                         ans+=(v[i]-m)*(v[i]-m);
869                 return ans/(v.length-1);
870         }
871 
872 
873   /**
874   * Computes the covariance.
875   */
876         public static double covariance(int[] v1 , int[] v2) {
877                 if(v1.length!=v2.length)
878                         throw new IllegalArgumentException  ("Arrays must have the same length : "+v1.length+", "+v2.length);
879                 final double m1 = mean(v1);
880                 final double m2 = mean(v2);
881                 double ans=0.0;
882                 for(int i=0;i<v1.length;i++)
883                         ans+=(v1[i]-m1)*(v2[i]-m2);
884                 return ans/(v1.length-1);
885         }
886 
887         /**
888         * Computes the (linear) correlation between two arrays.
889         * Squaring this result and multiply by 100 gives you
890         * the percentage of correlation.
891         */
892   public static double correlation (int[] v1, int[] v2) {
893     double denom=Math.sqrt(variance(v1)*variance(v2));
894     if(denom!=0)
895       return(covariance(v1,v2)/denom);
896     else {
897       if((variance(v1)==0) &&(variance(v2)==0))
898         return(1.0);
899       else return(0.0);  // impossible to correlate a null signal with another
900     }
901   }
902 
903         /**
904         * Computes the mean.
905         */
906         public static double mean(int[] v) {
907     if(v.length==0)
908       throw new IllegalArgumentException  ("Nothing to compute! The array must have at least one element.");
909                 return(mass(v)/(double)v.length);
910         }
911 
912         /**
913         * Returns the standard deviation of an array.
914         */
915         public static double standardDeviation(int[] v) {
916                 return(Math.sqrt(variance(v)));
917         }
918 
919 
920         /**
921         * Returns a sorted array from the minimum to the maximum value.
922         */
923         public static int[] sortMinToMax(int[] v) {
924     int[] ans=copy(v);
925     quickSortMinToMax(ans, 0, ans.length - 1);
926     return(ans);
927         }
928 
929         /**
930         * Returns a sorted array from the maximum to the minimum value.
931         */
932         public static int[] sortMaxToMin(int[] v) {
933     int[] ans=copy(v);
934     quickSortMaxToMin(ans, 0, ans.length - 1);
935     return(ans);
936         }
937 
938   /**
939   * Returns a comma delimited string representing the value of the array.
940   */
941   public static String   toString(int[] array) {
942           StringBuffer   buf=new StringBuffer  (array.length);
943           int i;
944           for(i=0;i<array.length-1;i++) {
945                   buf.append(array[i]);
946                   buf.append(',');
947           }
948           buf.append(array[i]);
949           return buf.toString();
950   }
951 
952   /**
953   * Returns a comma delimited string representing the value of the array.
954   */
955   public static String   toString(int[][] array) {
956           StringBuffer   buf=new StringBuffer  ();
957           for(int k=0;k<array.length;k++) {
958             buf.append(toString(array[k]));
959             buf.append(System.getProperty("line.separator"));
960           }
961           return buf.toString();
962   }
963 
964         /**
965         * Gives the percentile of an array.
966     * @param v an unsorted array
967         * @param p percentile, must be between 0 and 1
968         * @exception IllegalArgumentException if parameter
969         * p is not between 0 and 1.
970         */
971         public static double percentile(int[] v, double p) {
972         return percentile(v, p, false);
973     }
974     /**
975     * @param isSorted true if the array is already sorted into ascending numerical order.
976     */
977         public static double percentile(int[] v, double p, boolean isSorted) {
978                 if((p<0) || (p>1)) {
979                         throw new IllegalArgumentException  ("Percentile must be between 0 and 1 : "+p);
980                 }
981                 final int[] ans = (isSorted ? v : sortMinToMax(v));
982                 final int pos = (int) Math.floor(p*(ans.length-1));
983                 final double dif = p*(ans.length-1)-Math.floor(p*(ans.length-1));
984                 if(pos == (ans.length-1))
985                         return(ans[ans.length-1]);
986                 else
987                         return(ans[pos]*(1.0-dif)+ans[pos+1]*dif);
988         }
989 
990         /**
991         * Computes the median of an array.
992         * If the array contains an even number of elements,
993         * the lower median is returned.
994         */
995         public static int median(int[] v) {
996                 if(v.length == 3) {
997                         return median3(copy(v));
998                 } else if(v.length == 5) {
999                         return median5(copy(v));
1000                } else if(v.length == 7) {
1001                        return median7(copy(v));
1002                } else {
1003                        return quickSelect(copy(v));
1004                }
1005        }
1006        /*
1007        * http://ndevilla.free.fr/median/median/index.html
1008        * optmed.c
1009        * @author N. Devillard
1010        */
1011        private static void sortInPlace(final int[] v, final int i, final int j) {
1012                if(v[i] > v[j]) {
1013                        final int tmp = v[i];
1014                        v[i] = v[j];
1015                        v[j] = tmp;
1016                }
1017        }
1018        private static int median3(int[] v) {
1019                sortInPlace(v,0,1);
1020                sortInPlace(v,1,2);
1021                sortInPlace(v,0,1);
1022                return v[1];
1023        }
1024        private static int median5(int[] v) {
1025                sortInPlace(v,0,1);
1026                sortInPlace(v,3,4);
1027                sortInPlace(v,0,3);
1028                sortInPlace(v,1,4);
1029                sortInPlace(v,1,2);
1030                sortInPlace(v,2,3);
1031                sortInPlace(v,1,2);
1032                return v[2];
1033        }
1034        private static int median7(int[] v) {
1035                sortInPlace(v,0,5);
1036                sortInPlace(v,0,3);
1037                sortInPlace(v,1,6);
1038                sortInPlace(v,2,4);
1039                sortInPlace(v,0,1);
1040                sortInPlace(v,3,5);
1041                sortInPlace(v,2,6);
1042                sortInPlace(v,2,3);
1043                sortInPlace(v,3,6);
1044                sortInPlace(v,4,5);
1045                sortInPlace(v,1,4);
1046                sortInPlace(v,1,3);
1047                sortInPlace(v,3,4);
1048                return v[3];
1049        }
1050        /*
1051        * http://ndevilla.free.fr/median/median/index.html
1052        * quickselect.c
1053        * @author N. Devillard
1054        */
1055        private static int quickSelect(int[] v) {
1056                int low=0, high=v.length-1;
1057                final int median=high/2;
1058                int middle, ll, hh;
1059
1060                for (;;) {
1061                        if (high <= low) { /* One element only */
1062                                return v[median];
1063                        }
1064
1065                        if (high == low + 1) {  /* Two elements only */
1066                                if (v[low] > v[high])
1067                                        swap(v, low, high);
1068                                return v[median];
1069                        }
1070
1071                /* Find median of low, middle and high items; swap into position low */
1072                        middle = (low + high) / 2;
1073                        if (v[middle] > v[high]) swap(v, middle, high);
1074                        if (v[low] > v[high]) swap(v, low, high);
1075                        if (v[middle] > v[low]) swap(v, middle, low);
1076
1077                /* Swap low item (now in position middle) into position (low+1) */
1078                        swap(v, middle, low+1);
1079
1080                /* Nibble from each end towards middle, swapping items when stuck */
1081                        ll = low + 1;
1082                        hh = high;
1083                        for (;;) {
1084                                do ll++; while (v[low] > v[ll]);
1085                                do hh--; while (v[hh]  > v[low]);
1086
1087                                if (hh < ll)
1088                                        break;
1089
1090                                swap(v, ll, hh);
1091                        }
1092
1093                /* Swap middle item (in position low) back into correct position */
1094                        swap(v, low, hh);
1095
1096                /* Re-set active partition */
1097                        if (hh <= median)
1098                                low = ll;
1099                        if (hh >= median)
1100                                high = hh - 1;
1101                }
1102        }
1103
1104        /**
1105        * Use java.util.Arrays instead.
1106        * Check if two arrays are equal.
1107        * @deprecated Use java.util.Arrays instead.
1108        */
1109        public static boolean equals(int[] a, int[] b) {
1110                if(a.length!=b.length) {
1111                        return(false);
1112                }
1113                for(int i=0;i<a.length;i++) {
1114                        if(a[i]!=b[i]) {
1115                                return(false);
1116                        }
1117                }
1118                return(true);
1119        }
1120
1121        /**
1122        * Takes the absolute value of each component of an array.
1123        */
1124        public static int[] abs(int[] v) {
1125                int[] ans=new int[v.length];
1126                for(int i=0;i<v.length;i++) {
1127                        ans[i]=Math.abs(v[i]);
1128                }
1129                return(ans);
1130        }
1131
1132        /**
1133        * Takes the absolute value of each component of an array.
1134        */
1135        public static int[][] abs(int[][] v) {
1136                int[][] ans=new int[v.length][];
1137                for(int i=0;i<v.length;i++) {
1138                        ans[i]=abs(v[i]);
1139                }
1140                return(ans);
1141        }
1142
1143        /**
1144        * Returns the maximum of an array.
1145        */
1146        public static int max(int[] v) {
1147                int max=v[0];
1148                for(int i=1;i<v.length;i++) {
1149                        if(max<v[i]) {
1150                                max=v[i];
1151                        }
1152                }
1153                return(max);
1154        }
1155
1156        /**
1157        * Returns the maximum of an array.
1158        */
1159        public static int max(int[][] v) {
1160                int max=max(v[0]);
1161                for(int i=1;i<v.length;i++) {
1162                        if(max<max(v[i])) {
1163                                max=max(v[i]);
1164                        }
1165                }
1166                return(max);
1167        }
1168
1169        /**
1170        * Returns the minimum of an array.
1171        */
1172        public static int min(int[] v) {
1173                int min=v[0];
1174                for(int i=1;i<v.length;i++) {
1175                        if(min>v[i]) {
1176                                min=v[i];
1177                        }
1178                }
1179                return(min);
1180        }
1181
1182        /**
1183        * Returns the minimum of an array.
1184        */
1185        public static int min(int[][] v) {
1186                int min=min(v[0]);
1187                for(int i=1;i<v.length;i++) {
1188                        if(min>min(v[i])) {
1189                                min=min(v[i]);
1190                        }
1191                }
1192                return(min);
1193        }
1194
1195        /**
1196        * Computes the L2 norm of an array (Euclidean norm or "length").
1197        */
1198        public static double norm (int[] data) {
1199                return(Math.sqrt(sumSquares(data)));
1200        }
1201
1202        /**
1203        * Sums the squares of all components;
1204        * also called the energy of the array.
1205        */
1206        public static int sumSquares (int[] data) {
1207                int ans=0;
1208                for(int k=0;k<data.length;k++) {
1209                        ans+=data[k]*data[k];
1210                }
1211                return(ans);
1212        }
1213
1214        /**
1215        * Sums the squares of all components;
1216        * also called the energy of the array.
1217        */
1218        public static int sumSquares (int[][] data) {
1219                int ans=0;
1220                for(int k=0;k<data.length;k++) {
1221      for(int l=0;l<data[k].length;l++) {
1222                          ans+=data[k][l]*data[k][l];
1223      }
1224                }
1225                return(ans);
1226        }
1227
1228        /**
1229        * Computes the scalar product of two array
1230        * as if they were vectors.
1231        * @exception IllegalArgumentException if the
1232        * don't have the same length.
1233        */
1234        public static int scalarProduct (int[] w0,int[] w1) {
1235                if (w0.length!=w1.length) {
1236                        throw new IllegalArgumentException  ("Arrays must have the same length : "+w0.length+", "+w1.length);
1237                }
1238    if(w0.length==0)
1239      throw new IllegalArgumentException  ("Nothing to compute! Arrays must have at least one element.");
1240                int sortie=0;
1241                for(int k=0;k<w0.length;k++){
1242                        sortie=sortie+w0[k]*w1[k];
1243                }
1244                return(sortie);
1245        }
1246
1247        /**
1248        * Computes the scalar product of two array
1249        * as if they were matrices.
1250        * @exception IllegalArgumentException if the
1251        * don't have the same length.
1252        */
1253        public static double scalarProduct (int[][] w0,int[][] w1) {
1254                if (w0.length!=w1.length) {
1255                        throw new IllegalArgumentException  ("Arrays must have the same length : "+w0.length+", "+w1.length);
1256                }
1257    if(w0.length==0)
1258      throw new IllegalArgumentException  ("Nothing to compute! Arrays must have at least one element.");
1259                double sortie=0.0;
1260                for(int k=0;k<w0.length;k++){
1261                        sortie=sortie+scalarProduct(w0[k],w1[k]);
1262                }
1263                return(sortie);
1264        }
1265
1266
1267        /**
1268        * Extracts a sub-array (will invert the
1269        * resulting array if k0 > k1).
1270        * @param k0 location of the first component.
1271        * @param k1 location of the last component.
1272        */
1273        public static  int[] extract(int k0, int k1, int[] invect) {
1274                if ((k0<0)||(k1<0)||(k0>invect.length-1)||(k1>invect.length-1)) {
1275                        throw new IllegalArgumentException  ("The parameters are incorrect : "+k0+", "+k1+", "+invect.length);
1276                }
1277                if(k1>k0) {
1278                        int[] ans=new int[k1-k0+1];
1279      System.arraycopy(invect,k0,ans,0,k1-k0+1);
1280                        return(ans);
1281                }
1282                        int[] ans=new int[-k1+k0+1];
1283                        for(int k=k1;k<=k0;k++) {
1284                                ans[k0-k]=invect[k];
1285                        }
1286                        return(ans);
1287        }
1288
1289        /**
1290        * Inverts an array from left to right.
1291        */
1292        public static int [] invert (int[] v) {
1293                int[] w=new int[v.length];
1294                for(int k=0;k<v.length;k++) {
1295                        w[v.length-1-k]=v[k];
1296                }
1297                return(w);
1298        }
1299
1300        /**
1301        * Fills in with zeroes to get to the specified length;
1302        * original array with be at the specified position
1303        * @param n0 length of the new array.
1304        * @param pos position of the old array.
1305        */
1306        public static int[] padding(int n0, int pos, int[] v) {
1307                if ((v.length+pos>n0)||(pos<0)) {
1308                        throw new IllegalArgumentException  ("The array is too long for this : "+n0+", "+pos+", "+v.length);
1309                }
1310                int[] w=new int[n0];
1311    System.arraycopy(v,0,w,pos,v.length);
1312                return(w);
1313        }
1314
1315
1316        /**
1317        * Adds to an array w, a times v where a is a scalar.
1318        * Since v can be smaller then w, we must specified the position at which v will be added.
1319        * @param a scalar.
1320        * @param p position.
1321        * @param w longer array.
1322        * @param v shorter array.
1323        * @exception IllegalArgumentException if the second array
1324        * is not shorter than the first one.
1325        */
1326        public static int[] add(int[]w, double a, int[] v,int p) {
1327    if(v.length>w.length) {
1328      throw new IllegalArgumentException  ("Second array must be shorter or equal to the first one : "+w.length+", "+v.length);
1329    }
1330                int[] ans=copy(w);
1331                for(int k=p;k<p+v.length;k++) {
1332                        ans[k]+=a*v[k-p];
1333                }
1334                return(ans);
1335        }
1336
1337  /**
1338  * Adds a scalar to every element in the array.
1339  */
1340  public static int[] add(int[] w, int a) {
1341    int[] ans=copy(w);
1342    for(int k=0;k<ans.length;k++) {
1343      ans[k]+=a;
1344    }
1345    return(ans);
1346  }
1347
1348  /**
1349  * Generates an array going for a to b
1350  * with steps of size 1. a can be
1351  * smaller or larger than b.
1352  */
1353  public static int[] range(int a, int b) {
1354    return(range(a,b,1));
1355  }
1356  /**
1357  * Generates an array going for 0 to b
1358  * with steps of size 1. 0 can be
1359  * smaller or larger than b.
1360  */
1361  public static int[] range(int b) {
1362    return(range(0,b));
1363  }
1364
1365  /**
1366  * Generates an array going for a to b
1367  * with steps of size step. If it can't
1368  * get to the value b in a finite number
1369  * of steps, it gets as close as possible
1370  * (a can be larger or smaller than b)
1371  * @param step size of steps, must be positive
1372  * @param a first value of array
1373  * @param b last value of array
1374  * @exception IllegalArgumentException if step is
1375  * negative or if a=b.
1376  */
1377  public static int[] range(int a, int b, int step) {
1378    if( step<=0) {
1379      throw new IllegalArgumentException  ("The argument step should be positive: "+step+" < 0");
1380    }
1381    if( a==b) {
1382      int[] ans=new int[1];
1383      ans[0]=a;
1384      return(ans);
1385    }
1386    int sizeOfArray=(new Double  (Math.abs(a-b)/step)).intValue();
1387    int[] ans=new int[sizeOfArray];
1388    ans[0]=a;
1389    if(a>b) {
1390      step=-step;
1391    }
1392    for(int k=1;k<sizeOfArray;k++) {
1393      ans[k]=ans[k-1]+step;
1394    }
1395    return(ans);
1396  }
1397
1398  /**
1399  * Takes the transpose of an array (like the matrix
1400  * operation).
1401  * @exception IllegalArgumentException if the array
1402  * is not a matrix
1403  */
1404        public static int[][] transpose (int[][] M) {
1405                int[][] Mt=new int[M[0].length][M.length];
1406                for(int i=0;i<M.length;i++) {
1407      if(M[i].length!=M[0].length) {
1408        throw new IllegalArgumentException  ("The array is not a matrix.");
1409      }
1410                        for(int j=0;j<M[0].length;j++) {
1411                                Mt[j][i]=M[i][j];
1412                        }
1413                }
1414                return(Mt);
1415        }
1416
1417        /**
1418        * Adds the two arrays together (componentwise).
1419        * @exception IllegalArgumentException if the
1420        * two arrays don't have the same length.
1421        */
1422        public static int[] add (int[] a, int[] b) {
1423                if (a.length!=b.length) {
1424                        throw new IllegalArgumentException  ("To add two arrays, they must have the same length : "+a.length+", "+b.length);
1425                }
1426                int[] ans=copy(a);
1427                for(int i=0;i<a.length;i++) {
1428                        ans[i]+=b[i];
1429                }
1430                return(ans);
1431        }
1432        /**
1433        * Subtracts the two arrays together (componentwise).
1434        * @exception IllegalArgumentException if the
1435        * two arrays don't have the same length.
1436        */
1437        public static int[] subtract (int[] a, int[] b) {
1438                if (a.length!=b.length) {
1439                        throw new IllegalArgumentException  ("To add two arrays, they must have the same length : "+a.length+", "+b.length);
1440                }
1441                int[] ans=copy(a);
1442                for(int i=0;i<a.length;i++) {
1443                        ans[i]-=b[i];
1444                }
1445                return(ans);
1446        }
1447
1448        /**
1449        * Returns the sum of the elements of the array.
1450        */
1451        public static int mass(int[] v) {
1452                int somme=0;
1453                for(int k=0;k<v.length;k++) {
1454                        somme+=v[k];
1455                }
1456                return(somme);
1457        }
1458
1459        /**
1460        * Multiplies every component of an array by a scalar.
1461        */
1462        public static double[] scalarMultiply(double a, int[] v) {
1463                double[] ans=new double[v.length];
1464                for(int k=0;k<v.length;k++) {
1465                        ans[k]=v[k]*a;
1466                }
1467                return(ans);
1468        }
1469
1470        /**
1471        * Fast scalar multiplication for sparse arrays.
1472        */
1473        public static double[] scalarMultiplyFast(double a, int[] v) {
1474                if(a==0.0) return (new double[v.length]);
1475                double[] ans=new double[v.length];
1476                for(int k=0;k<v.length;k++) {
1477                        if((a!=0) && (v[k]!=0)) {
1478                                ans[k]=v[k]*a;
1479                        } else ans[k]=0.0;
1480                }
1481                return(ans);
1482        }
1483
1484        /**
1485        * Prints an array to screen.
1486        */
1487        public static void print(int[] v) {
1488                for(int k=0;k<v.length;k++) {
1489                        System.out.println("array ["+k+"] = "+v[k]);
1490                }
1491        }
1492        /**
1493        * Prints an array to screen.
1494        */
1495        public static void print(int[][] v) {
1496                for(int k=0;k<v.length;k++) {
1497      for(int l=0;l<v[k].length;l++) {
1498                          System.out.println("array ["+k+"]["+l+"] = "+v[k][l]);
1499      }
1500                }
1501        }
1502
1503   /**
1504* This is a generic version of C.A.R Hoare's Quick Sort
1505    * algorithm.  This will handle arrays that are already
1506    * sorted, and arrays with duplicate keys.<BR>
1507    *
1508    * If you think of a one dimensional array as going from
1509    * the lowest index on the left to the highest index on the right
1510    * then the parameters to this function are lowest index or
1511    * left and highest index or right.  The first time you call
1512    * this function it will be with the parameters 0, a.length - 1.
1513    * (taken out of a code by James Gosling and Kevin A. Smith provided
1514    * with Sun's JDK 1.1.7)
1515    *
1516    * @param a       an integer array
1517    * @param lo0     left boundary of array partition (inclusive).
1518    * @param hi0     right boundary of array partition (inclusive).
1519        * @deprecated
1520    */
1521   private static void quickSortMinToMax(int a[], int lo0, int hi0)
1522   {
1523      int lo = lo0;
1524      int hi = hi0;
1525      int mid;
1526
1527      if ( hi0 > lo0)
1528      {
1529
1530         /* Arbitrarily establishing partition element as the midpoint of
1531          * the array.
1532          */
1533         mid = a[ (int) Math.round(( lo0 + hi0 ) / 2.0) ];
1534
1535         // loop through the array until indices cross
1536         while( lo <= hi )
1537         {
1538            /* find the first element that is greater than or equal to
1539             * the partition element starting from the left Index.
1540             */
1541             while( ( lo < hi0 )  && ( a[lo] < mid ))
1542                 ++lo;
1543
1544            /* find an element that is smaller than or equal to
1545             * the partition element starting from the right Index.
1546             */
1547             while( ( hi > lo0 )  && ( a[hi] > mid ))
1548                 --hi;
1549
1550            // if the indexes have not crossed, swap
1551            if( lo <= hi )
1552            {
1553               swap(a, lo, hi);
1554               ++lo;
1555               --hi;
1556            }
1557         }
1558
1559         /* If the right index has not reached the left side of array
1560          * must now sort the left partition.
1561          */
1562         if( lo0 < hi )
1563            quickSortMinToMax( a, lo0, hi );
1564
1565         /* If the left index has not reached the right side of array
1566          * must now sort the right partition.
1567          */
1568         if( lo < hi0 )
1569            quickSortMinToMax( a, lo, hi0 );
1570
1571      }
1572   }
1573
1574   /** This is a generic version of C.A.R Hoare's Quick Sort
1575    * algorithm.  This will handle arrays that are already
1576    * sorted, and arrays with duplicate keys.<BR>
1577    *
1578    * If you think of a one dimensional array as going from
1579    * the lowest index on the left to the highest index on the right
1580    * then the parameters to this function are lowest index or
1581    * left and highest index or right.  The first time you call
1582    * this function it will be with the parameters 0, a.length - 1.
1583    * (taken out of a code by James Gosling and Kevin A. Smith provided
1584    * with Sun's JDK 1.1.7)
1585    *
1586    * @param a       an integer array
1587    * @param lo0     left boundary of array partition (inclusive).
1588    * @param hi0     right boundary of array partition (inclusive).
1589    */
1590   private static void quickSortMaxToMin(int a[], int lo0, int hi0)
1591   {
1592      int lo = lo0;
1593      int hi = hi0;
1594      int mid;
1595
1596      if ( hi0 > lo0)
1597      {
1598
1599         /* Arbitrarily establishing partition element as the midpoint of
1600          * the array.
1601          */
1602         mid = a[(int) Math.round( ( lo0 + hi0 ) / 2.0) ];
1603
1604         // loop through the array until indices cross
1605         while( lo <= hi )
1606         {
1607            /* find the first element that is greater than or equal to
1608             * the partition element starting from the left Index.
1609             */
1610             while( ( lo < hi0 )  && ( a[lo] > mid ))
1611                 ++lo;
1612
1613            /* find an element that is smaller than or equal to
1614             * the partition element starting from the right Index.
1615             */
1616             while( ( hi > lo0 )  && ( a[hi] < mid ))
1617                 --hi;
1618
1619            // if the indexes have not crossed, swap
1620            if( lo <= hi )
1621            {
1622               swap(a, lo, hi);
1623               ++lo;
1624               --hi;
1625            }
1626         }
1627
1628         /* If the right index has not reached the left side of array
1629          * must now sort the left partition.
1630          */
1631         if( lo0 < hi )
1632            quickSortMaxToMin( a, lo0, hi );
1633
1634         /* If the left index has not reached the right side of array
1635          * must now sort the right partition.
1636          */
1637         if( lo < hi0 )
1638            quickSortMaxToMin( a, lo, hi0 );
1639
1640      }
1641   }
1642
1643   /**
1644* This is a generic version of C.A.R Hoare's Quick Sort
1645    * algorithm.  This will handle arrays that are already
1646    * sorted, and arrays with duplicate keys.<BR>
1647    *
1648    * If you think of a one dimensional array as going from
1649    * the lowest index on the left to the highest index on the right
1650    * then the parameters to this function are lowest index or
1651    * left and highest index or right.  The first time you call
1652    * this function it will be with the parameters 0, a.length - 1.
1653    * (taken out of a code by James Gosling and Kevin A. Smith provided
1654    * with Sun's JDK 1.1.7)
1655    *
1656    * @param a       a double array
1657    * @param lo0     left boundary of array partition (inclusive).
1658    * @param hi0     right boundary of array partition (inclusive).
1659        * @deprecated
1660    */
1661   private static void quickSortMinToMax(double a[], int lo0, int hi0)
1662   {
1663      int lo = lo0;
1664      int hi = hi0;
1665      double mid;
1666
1667      if ( hi0 > lo0)
1668      {
1669
1670         /* Arbitrarily establishing partition element as the midpoint of
1671          * the array.
1672          */
1673         mid = a[(int) Math.round( ( lo0 + hi0 ) / 2.0) ];
1674
1675         // loop through the array until indices cross
1676         while( lo <= hi )
1677         {
1678            /* find the first element that is greater than or equal to
1679             * the partition element starting from the left Index.
1680             */
1681             while( ( lo < hi0 )  && ( a[lo] < mid ))
1682                 ++lo;
1683
1684            /* find an element that is smaller than or equal to
1685             * the partition element starting from the right Index.
1686             */
1687             while( ( hi > lo0 )  && ( a[hi] > mid ))
1688                 --hi;
1689
1690            // if the indexes have not crossed, swap
1691            if( lo <= hi )
1692            {
1693               swap(a, lo, hi);
1694               ++lo;
1695               --hi;
1696            }
1697         }
1698
1699         /* If the right index has not reached the left side of array
1700          * must now sort the left partition.
1701          */
1702         if( lo0 < hi )
1703            quickSortMinToMax( a, lo0, hi );
1704
1705         /* If the left index has not reached the right side of array
1706          * must now sort the right partition.
1707          */
1708         if( lo < hi0 )
1709            quickSortMinToMax( a, lo, hi0 );
1710
1711      }
1712   }
1713
1714   /**
1715* This is a generic version of C.A.R Hoare's Quick Sort
1716    * algorithm.  This will handle arrays that are already
1717    * sorted, and arrays with duplicate keys.<BR>
1718    *
1719    * If you think of a one dimensional array as going from
1720    * the lowest index on the left to the highest index on the right
1721    * then the parameters to this function are lowest index or
1722    * left and highest index or right.  The first time you call
1723    * this function it will be with the parameters 0, a.length - 1.
1724    * (taken out of a code by James Gosling and Kevin A. Smith provided
1725    * with Sun's JDK 1.1.7)
1726    *
1727    * @param a       a double array
1728    * @param lo0     left boundary of array partition (inclusive).
1729    * @param hi0     right boundary of array partition (inclusive).
1730    */
1731   private static void quickSortMaxToMin(double a[], int lo0, int hi0)
1732   {
1733      int lo = lo0;
1734      int hi = hi0;
1735      double mid;
1736
1737      if ( hi0 > lo0)
1738      {
1739
1740         /* Arbitrarily establishing partition element as the midpoint of
1741          * the array.
1742          */
1743         mid = a[ (int) Math.round(( lo0 + hi0 ) / 2.0) ];
1744
1745         // loop through the array until indices cross
1746         while( lo <= hi )
1747         {
1748            /* find the first element that is greater than or equal to
1749             * the partition element starting from the left Index.
1750             */
1751             while( ( lo < hi0 )  && ( a[lo] > mid ))
1752                 ++lo;
1753
1754            /* find an element that is smaller than or equal to
1755             * the partition element starting from the right Index.
1756             */
1757             while( ( hi > lo0 )  && ( a[hi] < mid ))
1758                 --hi;
1759
1760            // if the indexes have not crossed, swap
1761            if( lo <= hi )
1762            {
1763               swap(a, lo, hi);
1764               ++lo;
1765               --hi;
1766            }
1767         }
1768
1769         /* If the right index has not reached the left side of array
1770          * must now sort the left partition.
1771          */
1772         if( lo0 < hi )
1773            quickSortMaxToMin( a, lo0, hi );
1774
1775         /* If the left index has not reached the right side of array
1776          * must now sort the right partition.
1777          */
1778         if( lo < hi0 )
1779            quickSortMaxToMin( a, lo, hi0 );
1780
1781      }
1782   }
1783   /**
1784   * Used by the quick sort and quick select algorithms.
1785   */
1786   private static void swap(final int a[], final int i, final int j)
1787   {
1788      final int T;
1789      T = a[i];
1790      a[i] = a[j];
1791      a[j] = T;
1792   }
1793   /**
1794   * Used by the quick sort and quick select algorithms.
1795   */
1796   private static void swap(final double a[], final int i, final int j)
1797   {
1798      final double T;
1799      T = a[i];
1800      a[i] = a[j];
1801      a[j] = T;
1802
1803   }
1804}
1805
1806
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags