Merge branch 'develop' into task/JAL-3796_notarization
[jalview.git] / src / jalview / util / QuickSort.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
4  * 
5  * This file is part of Jalview.
6  * 
7  * Jalview is free software: you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License 
9  * as published by the Free Software Foundation, either version 3
10  * of the License, or (at your option) any later version.
11  *  
12  * Jalview is distributed in the hope that it will be useful, but 
13  * WITHOUT ANY WARRANTY; without even the implied warranty 
14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
15  * PURPOSE.  See the GNU General Public License for more details.
16  * 
17  * You should have received a copy of the GNU General Public License
18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
19  * The Jalview Authors are detailed in the 'AUTHORS' file.
20  */
21 package jalview.util;
22
23 import java.util.Arrays;
24 import java.util.Comparator;
25
26 /**
27  * A class to perform efficient sorting of arrays of objects based on arrays of
28  * scores or other attributes. For example, residues by percentage frequency.
29  * 
30  * @author gmcarstairs
31  *
32  */
33 public class QuickSort
34 {
35   /**
36    * A comparator that compares two integers by comparing their respective
37    * indexed values in an array of floats
38    */
39   static class FloatComparator implements Comparator<Integer>
40   {
41     private final float[] values;
42
43     private boolean ascending;
44
45     FloatComparator(float[] v, boolean asc)
46     {
47       values = v;
48       ascending = asc;
49     }
50
51     @Override
52     public int compare(Integer o1, Integer o2)
53     {
54       return ascending
55               ? Float.compare(values[o1.intValue()], values[o2.intValue()])
56               : Float.compare(values[o2.intValue()], values[o1.intValue()]);
57     }
58   }
59
60   /**
61    * A comparator that compares two integers by comparing their respective
62    * indexed values in an array of doubles
63    */
64   static class DoubleComparator implements Comparator<Integer>
65   {
66     private final double[] values;
67
68     private boolean ascending;
69
70     DoubleComparator(double[] v, boolean asc)
71     {
72       values = v;
73       ascending = asc;
74     }
75
76     @Override
77     public int compare(Integer o1, Integer o2)
78     {
79       if (ascending)
80       {
81         return Double.compare(values[o1.intValue()], values[o2.intValue()]);
82       }
83       else
84       {
85         return Double.compare(values[o2.intValue()], values[o1.intValue()]);
86       }
87     }
88   }
89
90   /**
91    * A comparator that compares two integers by comparing their respective
92    * indexed values in an array of ints
93    */
94   static class IntComparator implements Comparator<Integer>
95   {
96     private final int[] values;
97
98     private boolean ascending;
99
100     IntComparator(int[] v, boolean asc)
101     {
102       values = v;
103       ascending = asc;
104     }
105
106     @Override
107     public int compare(Integer o1, Integer o2)
108     {
109       return ascending
110               ? Integer.compare(values[o1.intValue()],
111                       values[o2.intValue()])
112               : Integer.compare(values[o2.intValue()],
113                       values[o1.intValue()]);
114     }
115   }
116
117   /**
118    * A comparator that compares two integers by comparing their respective
119    * indexed values in an array of comparable objects.
120    */
121   static class ExternalComparator implements Comparator<Integer>
122   {
123     private final Comparable[] values;
124
125     private boolean ascending;
126
127     ExternalComparator(Comparable[] v, boolean asc)
128     {
129       values = v;
130       ascending = asc;
131     }
132
133     @Override
134     public int compare(Integer o1, Integer o2)
135     {
136       return ascending
137               ? values[o1.intValue()].compareTo(values[o2.intValue()])
138               : values[o2.intValue()].compareTo(values[o1.intValue()]);
139     }
140   }
141
142   /**
143    * Sorts both arrays with respect to ascending order of the items in the first
144    * array.
145    * 
146    * @param arr
147    * @param s
148    */
149   public static void sort(int[] arr, Object[] s)
150   {
151     sort(arr, 0, arr.length - 1, s);
152   }
153
154   /**
155    * Sorts both arrays with respect to ascending order of the items in the first
156    * array.
157    * 
158    * @param arr
159    * @param s
160    */
161   public static void sort(float[] arr, Object[] s)
162   {
163     sort(arr, 0, arr.length - 1, s);
164   }
165
166   /**
167    * Sorts both arrays with respect to ascending order of the items in the first
168    * array.
169    * 
170    * @param arr
171    * @param s
172    */
173   public static void sort(double[] arr, Object[] s)
174   {
175     sort(arr, 0, arr.length - 1, s);
176   }
177
178   /**
179    * Sorts both arrays with respect to descending order of the items in the
180    * first array. The sorting is case-sensitive.
181    * 
182    * @param arr
183    * @param s
184    */
185   public static void sort(String[] arr, Object[] s)
186   {
187     stringSort(arr, 0, arr.length - 1, s);
188   }
189
190   static void stringSort(String[] arr, int p, int r, Object[] s)
191   {
192     int q;
193
194     if (p < r)
195     {
196       q = stringPartition(arr, p, r, s);
197       stringSort(arr, p, q, s);
198       stringSort(arr, q + 1, r, s);
199     }
200   }
201
202   static void sort(float[] arr, int p, int r, Object[] s)
203   {
204     int q;
205
206     if (p < r)
207     {
208       q = partition(arr, p, r, s);
209       sort(arr, p, q, s);
210       sort(arr, q + 1, r, s);
211     }
212   }
213
214   static void sort(double[] arr, int p, int r, Object[] s)
215   {
216     int q;
217
218     if (p < r)
219     {
220       q = partition(arr, p, r, s);
221       sort(arr, p, q, s);
222       sort(arr, q + 1, r, s);
223     }
224   }
225
226   static void sort(int[] arr, int p, int r, Object[] s)
227   {
228     int q;
229
230     if (p < r)
231     {
232       q = partition(arr, p, r, s);
233       sort(arr, p, q, s);
234       sort(arr, q + 1, r, s);
235     }
236   }
237
238   static int partition(float[] arr, int p, int r, Object[] s)
239   {
240     float x = arr[p];
241     int i = p - 1;
242     int j = r + 1;
243
244     while (true)
245     {
246       do
247       {
248         j = j - 1;
249       } while (arr[j] > x);
250
251       do
252       {
253         i = i + 1;
254       } while (arr[i] < x);
255
256       if (i < j)
257       {
258         float tmp = arr[i];
259         arr[i] = arr[j];
260         arr[j] = tmp;
261
262         Object tmp2 = s[i];
263         s[i] = s[j];
264         s[j] = tmp2;
265       }
266       else
267       {
268         return j;
269       }
270     }
271   }
272
273   static int partition(float[] arr, int p, int r, char[] s)
274   {
275     float x = arr[p];
276     int i = p - 1;
277     int j = r + 1;
278
279     while (true)
280     {
281       do
282       {
283         j = j - 1;
284       } while (arr[j] > x);
285
286       do
287       {
288         i = i + 1;
289       } while (arr[i] < x);
290
291       if (i < j)
292       {
293         float tmp = arr[i];
294         arr[i] = arr[j];
295         arr[j] = tmp;
296
297         char tmp2 = s[i];
298         s[i] = s[j];
299         s[j] = tmp2;
300       }
301       else
302       {
303         return j;
304       }
305     }
306   }
307
308   static int partition(int[] arr, int p, int r, Object[] s)
309   {
310     int x = arr[p];
311     int i = p - 1;
312     int j = r + 1;
313
314     while (true)
315     {
316       do
317       {
318         j = j - 1;
319       } while (arr[j] > x);
320
321       do
322       {
323         i = i + 1;
324       } while (arr[i] < x);
325
326       if (i < j)
327       {
328         int tmp = arr[i];
329         arr[i] = arr[j];
330         arr[j] = tmp;
331
332         Object tmp2 = s[i];
333         s[i] = s[j];
334         s[j] = tmp2;
335       }
336       else
337       {
338         return j;
339       }
340     }
341   }
342
343   static int partition(double[] arr, int p, int r, Object[] s)
344   {
345     double x = arr[p];
346     int i = p - 1;
347     int j = r + 1;
348
349     while (true)
350     {
351       do
352       {
353         j = j - 1;
354       } while (arr[j] > x);
355
356       do
357       {
358         i = i + 1;
359       } while (arr[i] < x);
360
361       if (i < j)
362       {
363         double tmp = arr[i];
364         arr[i] = arr[j];
365         arr[j] = tmp;
366
367         Object tmp2 = s[i];
368         s[i] = s[j];
369         s[j] = tmp2;
370       }
371       else
372       {
373         return j;
374       }
375     }
376   }
377
378   static int stringPartition(String[] arr, int p, int r, Object[] s)
379   {
380     String x = arr[p];
381     int i = p - 1;
382     int j = r + 1;
383
384     while (true)
385     {
386       do
387       {
388         j = j - 1;
389       } while (arr[j].compareTo(x) < 0);
390
391       do
392       {
393         i = i + 1;
394       } while (arr[i].compareTo(x) > 0);
395
396       if (i < j)
397       {
398         String tmp = arr[i];
399         arr[i] = arr[j];
400         arr[j] = tmp;
401
402         Object tmp2 = s[i];
403         s[i] = s[j];
404         s[j] = tmp2;
405       }
406       else
407       {
408         return j;
409       }
410     }
411   }
412
413   /**
414    * Sorts both arrays to give ascending order by the first array, by first
415    * partitioning into zero and non-zero values before sorting the latter. This
416    * is faster than a direct call to charSortByFloat in the case where most of
417    * the array to be sorted is zero.
418    * 
419    * @param arr
420    * @param s
421    */
422   public static void sort(float[] arr, char[] s)
423   {
424     /*
425      * Move all zero values to the front, non-zero to the back, while counting
426      * negative values
427      */
428     float[] f1 = new float[arr.length];
429     char[] s1 = new char[s.length];
430     int negativeCount = 0;
431     int zerosCount = 0;
432     int nextNonZeroValue = arr.length - 1;
433     for (int i = 0; i < arr.length; i++)
434     {
435       float val = arr[i];
436       if (val != 0f)
437       {
438         f1[nextNonZeroValue] = val;
439         s1[nextNonZeroValue] = s[i];
440         nextNonZeroValue--;
441         if (val < 0f)
442         {
443           negativeCount++;
444         }
445       }
446       else
447       {
448         f1[zerosCount] = val;
449         s1[zerosCount] = s[i];
450         zerosCount++;
451       }
452     }
453     int positiveCount = arr.length - zerosCount - negativeCount;
454
455     if (zerosCount == arr.length)
456     {
457       return; // all zero
458     }
459
460     /*
461      * sort the non-zero values
462      */
463     float[] nonZeroFloats = Arrays.copyOfRange(f1, zerosCount, f1.length);
464     char[] nonZeroChars = Arrays.copyOfRange(s1, zerosCount, s1.length);
465     charSortByFloat(nonZeroFloats, nonZeroChars, true);
466
467     /*
468      * Backfill zero values to original arrays, after the space reserved for
469      * negatives
470      */
471     System.arraycopy(f1, 0, arr, negativeCount, zerosCount);
472     System.arraycopy(s1, 0, s, negativeCount, zerosCount);
473
474     /*
475      * Copy sorted negative values to the front of arr, s
476      */
477     System.arraycopy(nonZeroFloats, 0, arr, 0, negativeCount);
478     System.arraycopy(nonZeroChars, 0, s, 0, negativeCount);
479
480     /*
481      * Copy sorted positive values after the negatives and zeros
482      */
483     System.arraycopy(nonZeroFloats, negativeCount, arr,
484             negativeCount + zerosCount, positiveCount);
485     System.arraycopy(nonZeroChars, negativeCount, s,
486             negativeCount + zerosCount, positiveCount);
487   }
488
489   /**
490    * Sorts arrays of float and char by the float values, by making an array of
491    * indices, and sorting it using a comparator that refers to the float values.
492    * 
493    * @see http
494    *      ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
495    *      after-sorting
496    * @param arr
497    * @param s
498    * @param ascending
499    */
500   public static void charSortByFloat(float[] arr, char[] s,
501           boolean ascending)
502   {
503     final int length = arr.length;
504     Integer[] indices = makeIndexArray(length);
505     Arrays.sort(indices, new FloatComparator(arr, ascending));
506
507     /*
508      * Copy the array values as per the sorted indices
509      */
510     float[] sortedFloats = new float[length];
511     char[] sortedChars = new char[s.length];
512     for (int i = 0; i < length; i++)
513     {
514       sortedFloats[i] = arr[indices[i]];
515       sortedChars[i] = s[indices[i]];
516     }
517
518     /*
519      * And copy the sorted values back into the arrays
520      */
521     System.arraycopy(sortedFloats, 0, arr, 0, length);
522     System.arraycopy(sortedChars, 0, s, 0, s.length);
523   }
524
525   /**
526    * Make an array whose values are 0...length.
527    * 
528    * @param length
529    * @return
530    */
531   protected static Integer[] makeIndexArray(final int length)
532   {
533     Integer[] indices = new Integer[length];
534     for (int i = 0; i < length; i++)
535     {
536       indices[i] = i;
537     }
538     return indices;
539   }
540
541   static void sort(float[] arr, int p, int r, char[] s)
542   {
543     int q;
544     if (p < r)
545     {
546       q = partition(arr, p, r, s);
547       sort(arr, p, q, s);
548       sort(arr, q + 1, r, s);
549     }
550   }
551
552   /**
553    * Sorts both arrays to give ascending order in the first array, by first
554    * partitioning into zero and non-zero values before sorting the latter. This
555    * is faster than a direct call to charSortByInt in the case where most of the
556    * array to be sorted is zero.
557    * 
558    * @param arr
559    * @param s
560    */
561   public static void sort(int[] arr, char[] s)
562   { /*
563      * Move all zero values to the front, non-zero to the back, while counting
564      * negative values
565      */
566     int[] f1 = new int[arr.length];
567     char[] s1 = new char[s.length];
568     int negativeCount = 0;
569     int zerosCount = 0;
570     int nextNonZeroValue = arr.length - 1;
571     for (int i = 0; i < arr.length; i++)
572     {
573       int val = arr[i];
574       if (val != 0f)
575       {
576         f1[nextNonZeroValue] = val;
577         s1[nextNonZeroValue] = s[i];
578         nextNonZeroValue--;
579         if (val < 0)
580         {
581           negativeCount++;
582         }
583       }
584       else
585       {
586         f1[zerosCount] = val;
587         s1[zerosCount] = s[i];
588         zerosCount++;
589       }
590     }
591     int positiveCount = arr.length - zerosCount - negativeCount;
592
593     if (zerosCount == arr.length)
594     {
595       return; // all zero
596     }
597
598     /*
599      * sort the non-zero values
600      */
601     int[] nonZeroInts = Arrays.copyOfRange(f1, zerosCount, f1.length);
602     char[] nonZeroChars = Arrays.copyOfRange(s1, zerosCount, s1.length);
603     charSortByInt(nonZeroInts, nonZeroChars, true);
604
605     /*
606      * Backfill zero values to original arrays, after the space reserved for
607      * negatives
608      */
609     System.arraycopy(f1, 0, arr, negativeCount, zerosCount);
610     System.arraycopy(s1, 0, s, negativeCount, zerosCount);
611
612     /*
613      * Copy sorted negative values to the front of arr, s
614      */
615     System.arraycopy(nonZeroInts, 0, arr, 0, negativeCount);
616     System.arraycopy(nonZeroChars, 0, s, 0, negativeCount);
617
618     /*
619      * Copy sorted positive values after the negatives and zeros
620      */
621     System.arraycopy(nonZeroInts, negativeCount, arr,
622             negativeCount + zerosCount, positiveCount);
623     System.arraycopy(nonZeroChars, negativeCount, s,
624             negativeCount + zerosCount, positiveCount);
625   }
626
627   /**
628    * Sorts arrays of int and char, by making an array of indices, and sorting it
629    * using a comparator that refers to the int values.
630    * 
631    * @see http
632    *      ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
633    *      after-sorting
634    * @param arr
635    * @param s
636    * @param ascending
637    */
638   public static void charSortByInt(int[] arr, char[] s, boolean ascending)
639   {
640     final int length = arr.length;
641     Integer[] indices = makeIndexArray(length);
642     Arrays.sort(indices, new IntComparator(arr, ascending));
643
644     /*
645      * Copy the array values as per the sorted indices
646      */
647     int[] sortedInts = new int[length];
648     char[] sortedChars = new char[s.length];
649     for (int i = 0; i < length; i++)
650     {
651       sortedInts[i] = arr[indices[i]];
652       sortedChars[i] = s[indices[i]];
653     }
654
655     /*
656      * And copy the sorted values back into the arrays
657      */
658     System.arraycopy(sortedInts, 0, arr, 0, length);
659     System.arraycopy(sortedChars, 0, s, 0, s.length);
660   }
661
662   /**
663    * Sorts arrays of int and Object, by making an array of indices, and sorting
664    * it using a comparator that refers to the int values.
665    * 
666    * @see http
667    *      ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
668    *      after-sorting
669    * @param arr
670    * @param s
671    * @param ascending
672    */
673   public static void sortByInt(int[] arr, Object[] s, boolean ascending)
674   {
675     final int length = arr.length;
676     Integer[] indices = makeIndexArray(length);
677     Arrays.sort(indices, new IntComparator(arr, ascending));
678
679     /*
680      * Copy the array values as per the sorted indices
681      */
682     int[] sortedInts = new int[length];
683     Object[] sortedObjects = new Object[s.length];
684     for (int i = 0; i < length; i++)
685     {
686       sortedInts[i] = arr[indices[i]];
687       sortedObjects[i] = s[indices[i]];
688     }
689
690     /*
691      * And copy the sorted values back into the arrays
692      */
693     System.arraycopy(sortedInts, 0, arr, 0, length);
694     System.arraycopy(sortedObjects, 0, s, 0, s.length);
695   }
696
697   /**
698    * Sorts arrays of String and Object, by making an array of indices, and
699    * sorting it using a comparator that refers to the String values. Both arrays
700    * are sorted by case-sensitive order of the string array values.
701    * 
702    * @see http
703    *      ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
704    *      after-sorting
705    * @param arr
706    * @param s
707    * @param ascending
708    */
709   public static void sortByString(String[] arr, Object[] s,
710           boolean ascending)
711   {
712     final int length = arr.length;
713     Integer[] indices = makeIndexArray(length);
714     Arrays.sort(indices, new ExternalComparator(arr, ascending));
715
716     /*
717      * Copy the array values as per the sorted indices
718      */
719     String[] sortedStrings = new String[length];
720     Object[] sortedObjects = new Object[s.length];
721     for (int i = 0; i < length; i++)
722     {
723       sortedStrings[i] = arr[indices[i]];
724       sortedObjects[i] = s[indices[i]];
725     }
726
727     /*
728      * And copy the sorted values back into the arrays
729      */
730     System.arraycopy(sortedStrings, 0, arr, 0, length);
731     System.arraycopy(sortedObjects, 0, s, 0, s.length);
732   }
733
734   /**
735    * Sorts arrays of double and Object, by making an array of indices, and
736    * sorting it using a comparator that refers to the double values.
737    * 
738    * @see http
739    *      ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
740    *      after-sorting
741    * @param arr
742    * @param s
743    * @param ascending
744    */
745   public static void sortByDouble(double[] arr, Object[] s,
746           boolean ascending)
747   {
748     final int length = arr.length;
749     Integer[] indices = makeIndexArray(length);
750     Arrays.sort(indices, new DoubleComparator(arr, ascending));
751
752     /*
753      * Copy the array values as per the sorted indices
754      */
755     double[] sortedDoubles = new double[length];
756     Object[] sortedObjects = new Object[s.length];
757     for (int i = 0; i < length; i++)
758     {
759       sortedDoubles[i] = arr[indices[i]];
760       sortedObjects[i] = s[indices[i]];
761     }
762
763     /*
764      * And copy the sorted values back into the arrays
765      */
766     System.arraycopy(sortedDoubles, 0, arr, 0, length);
767     System.arraycopy(sortedObjects, 0, s, 0, s.length);
768   }
769 }