src/jalview/util/QuickSort.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.9)
   3  * Copyright (C) 2015 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.copyOfRange(f1, nextZeroValue, f1.length);
 510     char[] nonZeroChars = Arrays.copyOfRange(s1, nextZeroValue, s1.length);
 511     externalSort(nonZeroInts, nonZeroChars);
 512     // sort(nonZeroFloats, 0, nonZeroFloats.length - 1, nonZeroChars);
 513
 514     /*
 515      * Assemble sorted non-zero results
 516      */
 517     System.arraycopy(nonZeroInts, 0, arr, nextZeroValue, nonZeroInts.length);
 518     System.arraycopy(nonZeroChars, 0, s, nextZeroValue, nonZeroChars.length);
 519   }
 520
 521   /**
 522    * Sort by making an array of indices, and sorting it using a comparator that
 523    * refers to the float values.
 524    *
 525    * @see http
 526    *      ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
 527    *      after-sorting
 528    * @param arr
 529    * @param s
 530    */
 531   protected static void externalSort(int[] arr, char[] s)
 532   {
 533     final int length = arr.length;
 534     Integer[] indices = makeIndexArray(length);
 535     Arrays.sort(indices, new IntComparator(arr));
 536
 537     /*
 538      * Copy the array values as per the sorted indices
 539      */
 540     int[] sortedInts = new int[length];
 541     char[] sortedChars = new char[s.length];
 542     for (int i = 0; i < length; i++)
 543     {
 544       sortedInts[i] = arr[indices[i]];
 545       sortedChars[i] = s[indices[i]];
 546     }
 547
 548     /*
 549      * And copy the sorted values back into the arrays
 550      */
 551     System.arraycopy(sortedInts, 0, arr, 0, length);
 552     System.arraycopy(sortedChars, 0, s, 0, s.length);
 553   }
 554 }