JAL-1863 allow RNA secondary structure rows exported by Jalview to be imported again
[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   static class FloatComparator implements Comparator<Integer>
36   {
37
38     private final float[] values;
39
40     FloatComparator(float[] v)
41     {
42       values = v;
43     }
44
45     @Override
46     public int compare(Integer o1, Integer o2)
47     {
48       return Float.compare(values[o1], values[o2]);
49     }
50     
51   }
52
53   static class IntComparator implements Comparator<Integer>
54   {
55
56     private final int[] values;
57
58     IntComparator(int[] v)
59     {
60       values = v;
61     }
62
63     @Override
64     public int compare(Integer o1, Integer o2)
65     {
66       return Integer.compare(values[o1], values[o2]);
67     }
68
69   }
70
71   /**
72    * Sorts both arrays with respect to ascending order of the items in the first
73    * array.
74    * 
75    * @param arr
76    * @param s
77    */
78   public static void sort(int[] arr, Object[] s)
79   {
80     sort(arr, 0, arr.length - 1, s);
81   }
82
83   /**
84    * Sorts both arrays with respect to ascending order of the items in the first
85    * array.
86    * 
87    * @param arr
88    * @param s
89    */
90   public static void sort(float[] arr, Object[] s)
91   {
92     sort(arr, 0, arr.length - 1, s);
93   }
94
95   /**
96    * Sorts both arrays with respect to ascending order of the items in the first
97    * array.
98    * 
99    * @param arr
100    * @param s
101    */
102   public static void sort(double[] arr, Object[] s)
103   {
104     sort(arr, 0, arr.length - 1, s);
105   }
106
107   /**
108    * Sorts both arrays with respect to descending order of the items in the
109    * first array.
110    * 
111    * @param arr
112    * @param s
113    */
114   public static void sort(String[] arr, Object[] s)
115   {
116     stringSort(arr, 0, arr.length - 1, s);
117   }
118
119   static void stringSort(String[] arr, int p, int r, Object[] s)
120   {
121     int q;
122
123     if (p < r)
124     {
125       q = stringPartition(arr, p, r, s);
126       stringSort(arr, p, q, s);
127       stringSort(arr, q + 1, r, s);
128     }
129   }
130
131   static void sort(float[] arr, int p, int r, Object[] s)
132   {
133     int q;
134
135     if (p < r)
136     {
137       q = partition(arr, p, r, s);
138       sort(arr, p, q, s);
139       sort(arr, q + 1, r, s);
140     }
141   }
142
143   static void sort(double[] arr, int p, int r, Object[] s)
144   {
145     int q;
146
147     if (p < r)
148     {
149       q = partition(arr, p, r, s);
150       sort(arr, p, q, s);
151       sort(arr, q + 1, r, s);
152     }
153   }
154
155   static void sort(int[] arr, int p, int r, Object[] s)
156   {
157     int q;
158
159     if (p < r)
160     {
161       q = partition(arr, p, r, s);
162       sort(arr, p, q, s);
163       sort(arr, q + 1, r, s);
164     }
165   }
166
167   static int partition(float[] arr, int p, int r, Object[] s)
168   {
169     float x = arr[p];
170     int i = p - 1;
171     int j = r + 1;
172
173     while (true)
174     {
175       do
176       {
177         j = j - 1;
178       } while (arr[j] > x);
179
180       do
181       {
182         i = i + 1;
183       } while (arr[i] < x);
184
185       if (i < j)
186       {
187         float tmp = arr[i];
188         arr[i] = arr[j];
189         arr[j] = tmp;
190
191         Object tmp2 = s[i];
192         s[i] = s[j];
193         s[j] = tmp2;
194       }
195       else
196       {
197         return j;
198       }
199     }
200   }
201
202   static int partition(float[] arr, int p, int r, char[] s)
203   {
204     float x = arr[p];
205     int i = p - 1;
206     int j = r + 1;
207
208     while (true)
209     {
210       do
211       {
212         j = j - 1;
213       } while (arr[j] > x);
214
215       do
216       {
217         i = i + 1;
218       } while (arr[i] < x);
219
220       if (i < j)
221       {
222         float tmp = arr[i];
223         arr[i] = arr[j];
224         arr[j] = tmp;
225
226         char tmp2 = s[i];
227         s[i] = s[j];
228         s[j] = tmp2;
229       }
230       else
231       {
232         return j;
233       }
234     }
235   }
236
237   static int partition(int[] arr, int p, int r, Object[] s)
238   {
239     int x = arr[p];
240     int i = p - 1;
241     int j = r + 1;
242
243     while (true)
244     {
245       do
246       {
247         j = j - 1;
248       } while (arr[j] > x);
249
250       do
251       {
252         i = i + 1;
253       } while (arr[i] < x);
254
255       if (i < j)
256       {
257         int tmp = arr[i];
258         arr[i] = arr[j];
259         arr[j] = tmp;
260
261         Object tmp2 = s[i];
262         s[i] = s[j];
263         s[j] = tmp2;
264       }
265       else
266       {
267         return j;
268       }
269     }
270   }
271
272   static int partition(double[] arr, int p, int r, Object[] s)
273   {
274     double x = arr[p];
275     int i = p - 1;
276     int j = r + 1;
277
278     while (true)
279     {
280       do
281       {
282         j = j - 1;
283       } while (arr[j] > x);
284
285       do
286       {
287         i = i + 1;
288       } while (arr[i] < x);
289
290       if (i < j)
291       {
292         double tmp = arr[i];
293         arr[i] = arr[j];
294         arr[j] = tmp;
295
296         Object tmp2 = s[i];
297         s[i] = s[j];
298         s[j] = tmp2;
299       }
300       else
301       {
302         return j;
303       }
304     }
305   }
306
307   static int stringPartition(String[] arr, int p, int r, Object[] s)
308   {
309     String x = arr[p];
310     int i = p - 1;
311     int j = r + 1;
312
313     while (true)
314     {
315       do
316       {
317         j = j - 1;
318       } while (arr[j].compareTo(x) < 0);
319
320       do
321       {
322         i = i + 1;
323       } while (arr[i].compareTo(x) > 0);
324
325       if (i < j)
326       {
327         String tmp = arr[i];
328         arr[i] = arr[j];
329         arr[j] = tmp;
330
331         Object tmp2 = s[i];
332         s[i] = s[j];
333         s[j] = tmp2;
334       }
335       else
336       {
337         return j;
338       }
339     }
340   }
341
342   /**
343    * Sorts both arrays to give ascending order in the first array, by first
344    * partitioning into zero and non-zero values before sorting the latter.
345    * 
346    * @param arr
347    * @param s
348    */
349   public static void sort(float[] arr, char[] s)
350   {
351     /*
352      * Sort all zero values to the front
353      */
354     float[] f1 = new float[arr.length];
355     char[] s1 = new char[s.length];
356     int nextZeroValue = 0;
357     int nextNonZeroValue = arr.length - 1;
358     for (int i = 0; i < arr.length; i++)
359     {
360       float val = arr[i];
361       if (val > 0f)
362       {
363         f1[nextNonZeroValue] = val;
364         s1[nextNonZeroValue] = s[i];
365         nextNonZeroValue--;
366       }
367       else
368       {
369         f1[nextZeroValue] = val;
370         s1[nextZeroValue] = s[i];
371         nextZeroValue++;
372       }
373     }
374
375     /*
376      * Copy zero values back to original arrays
377      */
378     System.arraycopy(f1, 0, arr, 0, nextZeroValue);
379     System.arraycopy(s1, 0, s, 0, nextZeroValue);
380
381     if (nextZeroValue == arr.length)
382     {
383       return; // all zero
384     }
385     /*
386      * Sort the non-zero values
387      */
388     float[] nonZeroFloats = Arrays
389             .copyOfRange(f1, nextZeroValue, f1.length);
390     char[] nonZeroChars = Arrays.copyOfRange(s1, nextZeroValue, s1.length);
391     externalSort(nonZeroFloats, nonZeroChars);
392     // sort(nonZeroFloats, 0, nonZeroFloats.length - 1, nonZeroChars);
393
394     /*
395      * Assemble sorted non-zero results
396      */
397     System.arraycopy(nonZeroFloats, 0, arr, nextZeroValue,
398             nonZeroFloats.length);
399     System.arraycopy(nonZeroChars, 0, s, nextZeroValue, nonZeroChars.length);
400   }
401
402   /**
403    * Sort by making an array of indices, and sorting it using a comparator that
404    * refers to the float values.
405    * 
406    * @see http
407    *      ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
408    *      after-sorting
409    * @param arr
410    * @param s
411    */
412   protected static void externalSort(float[] arr, char[] s)
413   {
414     final int length = arr.length;
415     Integer[] indices = makeIndexArray(length);
416     Arrays.sort(indices, new FloatComparator(arr));
417
418     /*
419      * Copy the array values as per the sorted indices
420      */
421     float[] sortedFloats = new float[length];
422     char[] sortedChars = new char[s.length];
423     for (int i = 0; i < length; i++)
424     {
425       sortedFloats[i] = arr[indices[i]];
426       sortedChars[i] = s[indices[i]];
427     }
428
429     /*
430      * And copy the sorted values back into the arrays
431      */
432     System.arraycopy(sortedFloats, 0, arr, 0, length);
433     System.arraycopy(sortedChars, 0, s, 0, s.length);
434   }
435
436   /**
437    * Make an array whose values are 0...length.
438    * 
439    * @param length
440    * @return
441    */
442   protected static Integer[] makeIndexArray(final int length)
443   {
444     Integer[] indices = new Integer[length];
445     for (int i = 0; i < length; i++)
446     {
447       indices[i] = i;
448     }
449     return indices;
450   }
451
452   static void sort(float[] arr, int p, int r, char[] s)
453   {
454     int q;
455     if (p < r)
456     {
457       q = partition(arr, p, r, s);
458       sort(arr, p, q, s);
459       sort(arr, q + 1, r, s);
460     }
461   }
462
463   /**
464    * Sorts both arrays to give ascending order in the first array, by first
465    * partitioning into zero and non-zero values before sorting the latter.
466    * 
467    * @param arr
468    * @param s
469    */
470   public static void sort(int[] arr, char[] s)
471   {
472     /*
473      * Sort all zero values to the front
474      */
475     int[] f1 = new int[arr.length];
476     char[] s1 = new char[s.length];
477     int nextZeroValue = 0;
478     int nextNonZeroValue = arr.length - 1;
479     for (int i = 0; i < arr.length; i++)
480     {
481       int val = arr[i];
482       if (val > 0f)
483       {
484         f1[nextNonZeroValue] = val;
485         s1[nextNonZeroValue] = s[i];
486         nextNonZeroValue--;
487       }
488       else
489       {
490         f1[nextZeroValue] = val;
491         s1[nextZeroValue] = s[i];
492         nextZeroValue++;
493       }
494     }
495   
496     /*
497      * Copy zero values back to original arrays
498      */
499     System.arraycopy(f1, 0, arr, 0, nextZeroValue);
500     System.arraycopy(s1, 0, s, 0, nextZeroValue);
501   
502     if (nextZeroValue == arr.length)
503     {
504       return; // all zero
505     }
506     /*
507      * Sort the non-zero values
508      */
509     int[] nonZeroInts = Arrays
510             .copyOfRange(f1, nextZeroValue, f1.length);
511     char[] nonZeroChars = Arrays.copyOfRange(s1, nextZeroValue, s1.length);
512     externalSort(nonZeroInts, nonZeroChars);
513     // sort(nonZeroFloats, 0, nonZeroFloats.length - 1, nonZeroChars);
514   
515     /*
516      * Assemble sorted non-zero results
517      */
518     System.arraycopy(nonZeroInts, 0, arr, nextZeroValue, nonZeroInts.length);
519     System.arraycopy(nonZeroChars, 0, s, nextZeroValue, nonZeroChars.length);
520   }
521
522   /**
523    * Sort by making an array of indices, and sorting it using a comparator that
524    * refers to the float values.
525    * 
526    * @see http
527    *      ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
528    *      after-sorting
529    * @param arr
530    * @param s
531    */
532   protected static void externalSort(int[] arr, char[] s)
533   {
534     final int length = arr.length;
535     Integer[] indices = makeIndexArray(length);
536     Arrays.sort(indices, new IntComparator(arr));
537
538     /*
539      * Copy the array values as per the sorted indices
540      */
541     int[] sortedInts = new int[length];
542     char[] sortedChars = new char[s.length];
543     for (int i = 0; i < length; i++)
544     {
545       sortedInts[i] = arr[indices[i]];
546       sortedChars[i] = s[indices[i]];
547     }
548
549     /*
550      * And copy the sorted values back into the arrays
551      */
552     System.arraycopy(sortedInts, 0, arr, 0, length);
553     System.arraycopy(sortedChars, 0, s, 0, s.length);
554   }
555 }