Clover icon

jalviewX

  1. Project Clover database Wed Oct 31 2018 15:13:58 GMT
  2. Package jalview.util

File QuickSort.java

 

Coverage histogram

../../img/srcFileCovDistChart9.png
12% of files have more coverage

Code metrics

76
233
30
5
769
472
68
0.29
7.77
6
2.27

Classes

Class Line # Actions
QuickSort 33 219 56 33
0.8932038589.3%
QuickSort.FloatComparator 39 3 3 0
1.0100%
QuickSort.DoubleComparator 64 5 3 0
1.0100%
QuickSort.IntComparator 94 3 3 0
1.0100%
QuickSort.ExternalComparator 121 3 3 0
1.0100%
 

Contributing tests

This file is covered by 126 tests. .

Source view

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  3 toggle FloatComparator(float[] v, boolean asc)
46    {
47  3 values = v;
48  3 ascending = asc;
49    }
50   
 
51  212 toggle @Override
52    public int compare(Integer o1, Integer o2)
53    {
54  212 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  5 toggle DoubleComparator(double[] v, boolean asc)
71    {
72  5 values = v;
73  5 ascending = asc;
74    }
75   
 
76  26 toggle @Override
77    public int compare(Integer o1, Integer o2)
78    {
79  26 if (ascending)
80    {
81  21 return Double.compare(values[o1.intValue()], values[o2.intValue()]);
82    }
83    else
84    {
85  5 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  96477 toggle IntComparator(int[] v, boolean asc)
101    {
102  96477 values = v;
103  96477 ascending = asc;
104    }
105   
 
106  112501 toggle @Override
107    public int compare(Integer o1, Integer o2)
108    {
109  112499 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  2 toggle ExternalComparator(Comparable[] v, boolean asc)
128    {
129  2 values = v;
130  2 ascending = asc;
131    }
132   
 
133  16 toggle @Override
134    public int compare(Integer o1, Integer o2)
135    {
136  16 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  83 toggle public static void sort(int[] arr, Object[] s)
150    {
151  83 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  1 toggle public static void sort(float[] arr, Object[] s)
162    {
163  1 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  1 toggle public static void sort(double[] arr, Object[] s)
174    {
175  1 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  1577 toggle public static void sort(String[] arr, Object[] s)
186    {
187  1577 stringSort(arr, 0, arr.length - 1, s);
188    }
189   
 
190  23981 toggle static void stringSort(String[] arr, int p, int r, Object[] s)
191    {
192  23981 int q;
193   
194  23981 if (p < r)
195    {
196  11202 q = stringPartition(arr, p, r, s);
197  11202 stringSort(arr, p, q, s);
198  11202 stringSort(arr, q + 1, r, s);
199    }
200    }
201   
 
202  9 toggle static void sort(float[] arr, int p, int r, Object[] s)
203    {
204  9 int q;
205   
206  9 if (p < r)
207    {
208  4 q = partition(arr, p, r, s);
209  4 sort(arr, p, q, s);
210  4 sort(arr, q + 1, r, s);
211    }
212    }
213   
 
214  9 toggle static void sort(double[] arr, int p, int r, Object[] s)
215    {
216  9 int q;
217   
218  9 if (p < r)
219    {
220  4 q = partition(arr, p, r, s);
221  4 sort(arr, p, q, s);
222  4 sort(arr, q + 1, r, s);
223    }
224    }
225   
 
226  493 toggle static void sort(int[] arr, int p, int r, Object[] s)
227    {
228  493 int q;
229   
230  493 if (p < r)
231    {
232  205 q = partition(arr, p, r, s);
233  205 sort(arr, p, q, s);
234  205 sort(arr, q + 1, r, s);
235    }
236    }
237   
 
238  4 toggle static int partition(float[] arr, int p, int r, Object[] s)
239    {
240  4 float x = arr[p];
241  4 int i = p - 1;
242  4 int j = r + 1;
243   
244  4 while (true)
245    {
246  7 do
247    {
248  10 j = j - 1;
249  10 } while (arr[j] > x);
250   
251  7 do
252    {
253  8 i = i + 1;
254  8 } while (arr[i] < x);
255   
256  7 if (i < j)
257    {
258  3 float tmp = arr[i];
259  3 arr[i] = arr[j];
260  3 arr[j] = tmp;
261   
262  3 Object tmp2 = s[i];
263  3 s[i] = s[j];
264  3 s[j] = tmp2;
265    }
266    else
267    {
268  4 return j;
269    }
270    }
271    }
272   
 
273  0 toggle static int partition(float[] arr, int p, int r, char[] s)
274    {
275  0 float x = arr[p];
276  0 int i = p - 1;
277  0 int j = r + 1;
278   
279  0 while (true)
280    {
281  0 do
282    {
283  0 j = j - 1;
284  0 } while (arr[j] > x);
285   
286  0 do
287    {
288  0 i = i + 1;
289  0 } while (arr[i] < x);
290   
291  0 if (i < j)
292    {
293  0 float tmp = arr[i];
294  0 arr[i] = arr[j];
295  0 arr[j] = tmp;
296   
297  0 char tmp2 = s[i];
298  0 s[i] = s[j];
299  0 s[j] = tmp2;
300    }
301    else
302    {
303  0 return j;
304    }
305    }
306    }
307   
 
308  205 toggle static int partition(int[] arr, int p, int r, Object[] s)
309    {
310  205 int x = arr[p];
311  205 int i = p - 1;
312  205 int j = r + 1;
313   
314  205 while (true)
315    {
316  326 do
317    {
318  784 j = j - 1;
319  784 } while (arr[j] > x);
320   
321  326 do
322    {
323  379 i = i + 1;
324  379 } while (arr[i] < x);
325   
326  326 if (i < j)
327    {
328  121 int tmp = arr[i];
329  121 arr[i] = arr[j];
330  121 arr[j] = tmp;
331   
332  121 Object tmp2 = s[i];
333  121 s[i] = s[j];
334  121 s[j] = tmp2;
335    }
336    else
337    {
338  205 return j;
339    }
340    }
341    }
342   
 
343  4 toggle static int partition(double[] arr, int p, int r, Object[] s)
344    {
345  4 double x = arr[p];
346  4 int i = p - 1;
347  4 int j = r + 1;
348   
349  4 while (true)
350    {
351  7 do
352    {
353  10 j = j - 1;
354  10 } while (arr[j] > x);
355   
356  7 do
357    {
358  8 i = i + 1;
359  8 } while (arr[i] < x);
360   
361  7 if (i < j)
362    {
363  3 double tmp = arr[i];
364  3 arr[i] = arr[j];
365  3 arr[j] = tmp;
366   
367  3 Object tmp2 = s[i];
368  3 s[i] = s[j];
369  3 s[j] = tmp2;
370    }
371    else
372    {
373  4 return j;
374    }
375    }
376    }
377   
 
378  11202 toggle static int stringPartition(String[] arr, int p, int r, Object[] s)
379    {
380  11202 String x = arr[p];
381  11202 int i = p - 1;
382  11202 int j = r + 1;
383   
384  11202 while (true)
385    {
386  19098 do
387    {
388  40858 j = j - 1;
389  40858 } while (arr[j].compareTo(x) < 0);
390   
391  19098 do
392    {
393  32034 i = i + 1;
394  32034 } while (arr[i].compareTo(x) > 0);
395   
396  19098 if (i < j)
397    {
398  7896 String tmp = arr[i];
399  7896 arr[i] = arr[j];
400  7896 arr[j] = tmp;
401   
402  7896 Object tmp2 = s[i];
403  7896 s[i] = s[j];
404  7896 s[j] = tmp2;
405    }
406    else
407    {
408  11202 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  1 toggle 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  1 float[] f1 = new float[arr.length];
429  1 char[] s1 = new char[s.length];
430  1 int negativeCount = 0;
431  1 int zerosCount = 0;
432  1 int nextNonZeroValue = arr.length - 1;
433  65 for (int i = 0; i < arr.length; i++)
434    {
435  64 float val = arr[i];
436  64 if (val != 0f)
437    {
438  3 f1[nextNonZeroValue] = val;
439  3 s1[nextNonZeroValue] = s[i];
440  3 nextNonZeroValue--;
441  3 if (val < 0f)
442    {
443  1 negativeCount++;
444    }
445    }
446    else
447    {
448  61 f1[zerosCount] = val;
449  61 s1[zerosCount] = s[i];
450  61 zerosCount++;
451    }
452    }
453  1 int positiveCount = arr.length - zerosCount - negativeCount;
454   
455  1 if (zerosCount == arr.length)
456    {
457  0 return; // all zero
458    }
459   
460    /*
461    * sort the non-zero values
462    */
463  1 float[] nonZeroFloats = Arrays.copyOfRange(f1, zerosCount, f1.length);
464  1 char[] nonZeroChars = Arrays.copyOfRange(s1, zerosCount, s1.length);
465  1 charSortByFloat(nonZeroFloats, nonZeroChars, true);
466   
467    /*
468    * Backfill zero values to original arrays, after the space reserved for
469    * negatives
470    */
471  1 System.arraycopy(f1, 0, arr, negativeCount, zerosCount);
472  1 System.arraycopy(s1, 0, s, negativeCount, zerosCount);
473   
474    /*
475    * Copy sorted negative values to the front of arr, s
476    */
477  1 System.arraycopy(nonZeroFloats, 0, arr, 0, negativeCount);
478  1 System.arraycopy(nonZeroChars, 0, s, 0, negativeCount);
479   
480    /*
481    * Copy sorted positive values after the negatives and zeros
482    */
483  1 System.arraycopy(nonZeroFloats, negativeCount, arr,
484    negativeCount + zerosCount, positiveCount);
485  1 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  3 toggle public static void charSortByFloat(float[] arr, char[] s,
501    boolean ascending)
502    {
503  3 final int length = arr.length;
504  3 Integer[] indices = makeIndexArray(length);
505  3 Arrays.sort(indices, new FloatComparator(arr, ascending));
506   
507    /*
508    * Copy the array values as per the sorted indices
509    */
510  3 float[] sortedFloats = new float[length];
511  3 char[] sortedChars = new char[s.length];
512  134 for (int i = 0; i < length; i++)
513    {
514  131 sortedFloats[i] = arr[indices[i]];
515  131 sortedChars[i] = s[indices[i]];
516    }
517   
518    /*
519    * And copy the sorted values back into the arrays
520    */
521  3 System.arraycopy(sortedFloats, 0, arr, 0, length);
522  3 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  96492 toggle protected static Integer[] makeIndexArray(final int length)
532    {
533  96492 Integer[] indices = new Integer[length];
534  265111 for (int i = 0; i < length; i++)
535    {
536  168619 indices[i] = i;
537    }
538  96492 return indices;
539    }
540   
 
541  0 toggle static void sort(float[] arr, int p, int r, char[] s)
542    {
543  0 int q;
544  0 if (p < r)
545    {
546  0 q = partition(arr, p, r, s);
547  0 sort(arr, p, q, s);
548  0 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  97400 toggle 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  97400 int[] f1 = new int[arr.length];
567  97401 char[] s1 = new char[s.length];
568  97404 int negativeCount = 0;
569  97404 int zerosCount = 0;
570  97404 int nextNonZeroValue = arr.length - 1;
571  267447 for (int i = 0; i < arr.length; i++)
572    {
573  170043 int val = arr[i];
574  170043 if (val != 0f)
575    {
576  168320 f1[nextNonZeroValue] = val;
577  168319 s1[nextNonZeroValue] = s[i];
578  168318 nextNonZeroValue--;
579  168321 if (val < 0)
580    {
581  1 negativeCount++;
582    }
583    }
584    else
585    {
586  1724 f1[zerosCount] = val;
587  1724 s1[zerosCount] = s[i];
588  1724 zerosCount++;
589    }
590    }
591  97405 int positiveCount = arr.length - zerosCount - negativeCount;
592   
593  97404 if (zerosCount == arr.length)
594    {
595  927 return; // all zero
596    }
597   
598    /*
599    * sort the non-zero values
600    */
601  96476 int[] nonZeroInts = Arrays.copyOfRange(f1, zerosCount, f1.length);
602  96477 char[] nonZeroChars = Arrays.copyOfRange(s1, zerosCount, s1.length);
603  96479 charSortByInt(nonZeroInts, nonZeroChars, true);
604   
605    /*
606    * Backfill zero values to original arrays, after the space reserved for
607    * negatives
608    */
609  96475 System.arraycopy(f1, 0, arr, negativeCount, zerosCount);
610  96475 System.arraycopy(s1, 0, s, negativeCount, zerosCount);
611   
612    /*
613    * Copy sorted negative values to the front of arr, s
614    */
615  96475 System.arraycopy(nonZeroInts, 0, arr, 0, negativeCount);
616  96475 System.arraycopy(nonZeroChars, 0, s, 0, negativeCount);
617   
618    /*
619    * Copy sorted positive values after the negatives and zeros
620    */
621  96474 System.arraycopy(nonZeroInts, negativeCount, arr,
622    negativeCount + zerosCount, positiveCount);
623  96472 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  96480 toggle public static void charSortByInt(int[] arr, char[] s, boolean ascending)
639    {
640  96480 final int length = arr.length;
641  96480 Integer[] indices = makeIndexArray(length);
642  96477 Arrays.sort(indices, new IntComparator(arr, ascending));
643   
644    /*
645    * Copy the array values as per the sorted indices
646    */
647  96476 int[] sortedInts = new int[length];
648  96477 char[] sortedChars = new char[s.length];
649  264927 for (int i = 0; i < length; i++)
650    {
651  168451 sortedInts[i] = arr[indices[i]];
652  168447 sortedChars[i] = s[indices[i]];
653    }
654   
655    /*
656    * And copy the sorted values back into the arrays
657    */
658  96479 System.arraycopy(sortedInts, 0, arr, 0, length);
659  96477 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  2 toggle public static void sortByInt(int[] arr, Object[] s, boolean ascending)
674    {
675  2 final int length = arr.length;
676  2 Integer[] indices = makeIndexArray(length);
677  2 Arrays.sort(indices, new IntComparator(arr, ascending));
678   
679    /*
680    * Copy the array values as per the sorted indices
681    */
682  2 int[] sortedInts = new int[length];
683  2 Object[] sortedObjects = new Object[s.length];
684  12 for (int i = 0; i < length; i++)
685    {
686  10 sortedInts[i] = arr[indices[i]];
687  10 sortedObjects[i] = s[indices[i]];
688    }
689   
690    /*
691    * And copy the sorted values back into the arrays
692    */
693  2 System.arraycopy(sortedInts, 0, arr, 0, length);
694  2 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  2 toggle public static void sortByString(String[] arr, Object[] s,
710    boolean ascending)
711    {
712  2 final int length = arr.length;
713  2 Integer[] indices = makeIndexArray(length);
714  2 Arrays.sort(indices, new ExternalComparator(arr, ascending));
715   
716    /*
717    * Copy the array values as per the sorted indices
718    */
719  2 String[] sortedStrings = new String[length];
720  2 Object[] sortedObjects = new Object[s.length];
721  12 for (int i = 0; i < length; i++)
722    {
723  10 sortedStrings[i] = arr[indices[i]];
724  10 sortedObjects[i] = s[indices[i]];
725    }
726   
727    /*
728    * And copy the sorted values back into the arrays
729    */
730  2 System.arraycopy(sortedStrings, 0, arr, 0, length);
731  2 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  5 toggle public static void sortByDouble(double[] arr, Object[] s,
746    boolean ascending)
747    {
748  5 final int length = arr.length;
749  5 Integer[] indices = makeIndexArray(length);
750  5 Arrays.sort(indices, new DoubleComparator(arr, ascending));
751   
752    /*
753    * Copy the array values as per the sorted indices
754    */
755  5 double[] sortedDoubles = new double[length];
756  5 Object[] sortedObjects = new Object[s.length];
757  25 for (int i = 0; i < length; i++)
758    {
759  20 sortedDoubles[i] = arr[indices[i]];
760  20 sortedObjects[i] = s[indices[i]];
761    }
762   
763    /*
764    * And copy the sorted values back into the arrays
765    */
766  5 System.arraycopy(sortedDoubles, 0, arr, 0, length);
767  5 System.arraycopy(sortedObjects, 0, s, 0, s.length);
768    }
769    }
  • Report generated by OpenClover v 4.2.1 on Wed Oct 31 2018 15:15:54 GMT using coverage data from Wed Oct 31 2018 15:15:47 GMT.
  • Clover free edition.