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 }