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