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.intValue()], 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 sortInt(int[] arr, Object[] s)
  79   {
  80     sortInt(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 sortFloatObject(float[] arr, Object[] s)
  91   {
  92     sortFloat(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 sortDouble(double[] arr, Object[] s)
 103   {
 104     sortDouble(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   private 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   private static void sortFloat(float[] arr, int p, int r, Object[] s)
 132   {
 133     int q;
 134
 135     if (p < r)
 136     {
 137       q = partitionFloat(arr, p, r, s);
 138       sortFloat(arr, p, q, s);
 139       sortFloat(arr, q + 1, r, s);
 140     }
 141   }
 142
 143   /**
 144    * We don't need both of these
 145    *
 146    * @j2sIgnore
 147    *
 148    * @param arr
 149    * @param p
 150    * @param r
 151    * @param s
 152    */
 153           private static void sortDouble(double[] arr, int p, int r, Object[] s)
 154   {
 155     int q;
 156
 157     if (p < r)
 158     {
 159       q = partitionDouble(arr, p, r, s);
 160       sortDouble(arr, p, q, s);
 161       sortDouble(arr, q + 1, r, s);
 162     }
 163   }
 164
 165   private static void sortInt(int[] arr, int p, int r, Object[] s)
 166   {
 167     int q;
 168
 169     if (p < r)
 170     {
 171       q = partitionInt(arr, p, r, s);
 172       sortInt(arr, p, q, s);
 173       sortInt(arr, q + 1, r, s);
 174     }
 175   }
 176
 177   private static int partitionFloat(float[] arr, int p, int r, Object[] s)
 178   {
 179     float x = arr[p];
 180     int i = p - 1;
 181     int j = r + 1;
 182
 183     while (true)
 184     {
 185       do
 186       {
 187         j = j - 1;
 188       } while (arr[j] > x);
 189
 190       do
 191       {
 192         i = i + 1;
 193       } while (arr[i] < x);
 194
 195       if (i < j)
 196       {
 197         float tmp = arr[i];
 198         arr[i] = arr[j];
 199         arr[j] = tmp;
 200
 201         Object tmp2 = s[i];
 202         s[i] = s[j];
 203         s[j] = tmp2;
 204       }
 205       else
 206       {
 207         return j;
 208       }
 209     }
 210   }
 211
 212   private static int partitionFloatChar(float[] arr, int p, int r, char[] s)
 213   {
 214     float x = arr[p];
 215     int i = p - 1;
 216     int j = r + 1;
 217
 218     while (true)
 219     {
 220       do
 221       {
 222         j = j - 1;
 223       } while (arr[j] > x);
 224
 225       do
 226       {
 227         i = i + 1;
 228       } while (arr[i] < x);
 229
 230       if (i < j)
 231       {
 232         float tmp = arr[i];
 233         arr[i] = arr[j];
 234         arr[j] = tmp;
 235
 236         char tmp2 = s[i];
 237         s[i] = s[j];
 238         s[j] = tmp2;
 239       }
 240       else
 241       {
 242         return j;
 243       }
 244     }
 245   }
 246
 247   private static int partitionInt(int[] arr, int p, int r, Object[] s)
 248   {
 249     int x = arr[p];
 250     int i = p - 1;
 251     int j = r + 1;
 252
 253     while (true)
 254     {
 255       do
 256       {
 257         j = j - 1;
 258       } while (arr[j] > x);
 259
 260       do
 261       {
 262         i = i + 1;
 263       } while (arr[i] < x);
 264
 265       if (i < j)
 266       {
 267         int tmp = arr[i];
 268         arr[i] = arr[j];
 269         arr[j] = tmp;
 270
 271         Object tmp2 = s[i];
 272         s[i] = s[j];
 273         s[j] = tmp2;
 274       }
 275       else
 276       {
 277         return j;
 278       }
 279     }
 280   }
 281
 282   private static int partitionDouble(double[] arr, int p, int r, Object[] s)
 283   {
 284     double x = arr[p];
 285     int i = p - 1;
 286     int j = r + 1;
 287
 288     while (true)
 289     {
 290       do
 291       {
 292         j = j - 1;
 293       } while (arr[j] > x);
 294
 295       do
 296       {
 297         i = i + 1;
 298       } while (arr[i] < x);
 299
 300       if (i < j)
 301       {
 302         double tmp = arr[i];
 303         arr[i] = arr[j];
 304         arr[j] = tmp;
 305
 306         Object tmp2 = s[i];
 307         s[i] = s[j];
 308         s[j] = tmp2;
 309       }
 310       else
 311       {
 312         return j;
 313       }
 314     }
 315   }
 316
 317   private static int stringPartition(String[] arr, int p, int r, Object[] s)
 318   {
 319     String x = arr[p];
 320     int i = p - 1;
 321     int j = r + 1;
 322
 323     while (true)
 324     {
 325       do
 326       {
 327         j = j - 1;
 328       } while (arr[j].compareTo(x) < 0);
 329
 330       do
 331       {
 332         i = i + 1;
 333       } while (arr[i].compareTo(x) > 0);
 334
 335       if (i < j)
 336       {
 337         String tmp = arr[i];
 338         arr[i] = arr[j];
 339         arr[j] = tmp;
 340
 341         Object tmp2 = s[i];
 342         s[i] = s[j];
 343         s[j] = tmp2;
 344       }
 345       else
 346       {
 347         return j;
 348       }
 349     }
 350   }
 351
 352   /**
 353    * Sorts both arrays to give ascending order in the first array, by first
 354    * partitioning into zero and non-zero values before sorting the latter.
 355    *
 356    * @param arr
 357    * @param s
 358    */
 359   public static void sortFloatChar(float[] arr, char[] s)
 360   {
 361     /*
 362      * Sort all zero values to the front
 363      */
 364     float[] f1 = new float[arr.length];
 365     char[] s1 = new char[s.length];
 366     int nextZeroValue = 0;
 367     int nextNonZeroValue = arr.length - 1;
 368     for (int i = 0; i < arr.length; i++)
 369     {
 370       float val = arr[i];
 371       if (val > 0f)
 372       {
 373         f1[nextNonZeroValue] = val;
 374         s1[nextNonZeroValue] = s[i];
 375         nextNonZeroValue--;
 376       }
 377       else
 378       {
 379         f1[nextZeroValue] = val;
 380         s1[nextZeroValue] = s[i];
 381         nextZeroValue++;
 382       }
 383     }
 384
 385     /*
 386      * Copy zero values back to original arrays
 387      */
 388     System.arraycopy(f1, 0, arr, 0, nextZeroValue);
 389     System.arraycopy(s1, 0, s, 0, nextZeroValue);
 390
 391     if (nextZeroValue == arr.length)
 392     {
 393       return; // all zero
 394     }
 395     /*
 396      * Sort the non-zero values
 397      */
 398     float[] nonZeroFloats = Arrays
 399             .copyOfRange(f1, nextZeroValue, f1.length);
 400     char[] nonZeroChars = Arrays.copyOfRange(s1, nextZeroValue, s1.length);
 401     externalSortFloat(nonZeroFloats, nonZeroChars);
 402     // sort(nonZeroFloats, 0, nonZeroFloats.length - 1, nonZeroChars);
 403
 404     /*
 405      * Assemble sorted non-zero results
 406      */
 407     System.arraycopy(nonZeroFloats, 0, arr, nextZeroValue,
 408             nonZeroFloats.length);
 409     System.arraycopy(nonZeroChars, 0, s, nextZeroValue, nonZeroChars.length);
 410   }
 411
 412   /**
 413    * Sort by making an array of indices, and sorting it using a comparator that
 414    * refers to the float values.
 415    *
 416    * @see http
 417    *      ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
 418    *      after-sorting
 419    * @param arr
 420    * @param s
 421    */
 422   private static void externalSortFloat(float[] arr, char[] s)
 423   {
 424     final int length = arr.length;
 425     Integer[] indices = makeIndexArray(length);
 426     Arrays.sort(indices, new FloatComparator(arr));
 427
 428     /*
 429      * Copy the array values as per the sorted indices
 430      */
 431     float[] sortedFloats = new float[length];
 432     char[] sortedChars = new char[s.length];
 433     for (int i = 0; i < length; i++)
 434     {
 435       sortedFloats[i] = arr[indices[i]];
 436       sortedChars[i] = s[indices[i]];
 437     }
 438
 439     /*
 440      * And copy the sorted values back into the arrays
 441      */
 442     System.arraycopy(sortedFloats, 0, arr, 0, length);
 443     System.arraycopy(sortedChars, 0, s, 0, s.length);
 444   }
 445
 446   /**
 447    * Make an array whose values are 0...length.
 448    *
 449    * @param length
 450    * @return
 451    */
 452   private  static Integer[] makeIndexArray(final int length)
 453   {
 454     Integer[] indices = new Integer[length];
 455     for (int i = 0; i < length; i++)
 456     {
 457       indices[i] = i;
 458     }
 459     return indices;
 460   }
 461
 462 //  private static void sortFloat(float[] arr, int p, int r, char[] s)
 463 //  {
 464 //    int q;
 465 //    if (p < r)
 466 //    {
 467 //      q = partitionFloatChar(arr, p, r, s);
 468 //      sortFloat(arr, p, q, s);
 469 //      sortFloat(arr, q + 1, r, s);
 470 //    }
 471 //  }
 472 //
 473   /**
 474    * Sorts both arrays to give ascending order in the first array, by first
 475    * partitioning into zero and non-zero values before sorting the latter.
 476    *
 477    * @param arr
 478    * @param s
 479    */
 480   public static void sortIntChar(int[] arr, char[] s)
 481   {
 482     /*
 483      * Sort all zero values to the front
 484      */
 485     int[] f1 = new int[arr.length];
 486     char[] s1 = new char[s.length];
 487     int nextZeroValue = 0;
 488     int nextNonZeroValue = arr.length - 1;
 489     for (int i = 0; i < arr.length; i++)
 490     {
 491       int val = arr[i];
 492       if (val > 0f)
 493       {
 494         f1[nextNonZeroValue] = val;
 495         s1[nextNonZeroValue] = s[i];
 496         nextNonZeroValue--;
 497       }
 498       else
 499       {
 500         f1[nextZeroValue] = val;
 501         s1[nextZeroValue] = s[i];
 502         nextZeroValue++;
 503       }
 504     }
 505
 506     /*
 507      * Copy zero values back to original arrays
 508      */
 509     System.arraycopy(f1, 0, arr, 0, nextZeroValue);
 510     System.arraycopy(s1, 0, s, 0, nextZeroValue);
 511
 512     if (nextZeroValue == arr.length)
 513     {
 514       return; // all zero
 515     }
 516     /*
 517      * Sort the non-zero values
 518      */
 519     int[] nonZeroInts = Arrays
 520             .copyOfRange(f1, nextZeroValue, f1.length);
 521     char[] nonZeroChars = Arrays.copyOfRange(s1, nextZeroValue, s1.length);
 522     externalSortInt(nonZeroInts, nonZeroChars);
 523     // sort(nonZeroFloats, 0, nonZeroFloats.length - 1, nonZeroChars);
 524
 525     /*
 526      * Assemble sorted non-zero results
 527      */
 528     System.arraycopy(nonZeroInts, 0, arr, nextZeroValue, nonZeroInts.length);
 529     System.arraycopy(nonZeroChars, 0, s, nextZeroValue, nonZeroChars.length);
 530   }
 531
 532   /**
 533    * Sort by making an array of indices, and sorting it using a comparator that
 534    * refers to the float values.
 535    *
 536    * @see http
 537    *      ://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-
 538    *      after-sorting
 539    * @param arr
 540    * @param s
 541    */
 542   private static void externalSortInt(int[] arr, char[] s)
 543   {
 544     final int length = arr.length;
 545     Integer[] indices = makeIndexArray(length);
 546     Arrays.sort(indices, new IntComparator(arr));
 547
 548     /*
 549      * Copy the array values as per the sorted indices
 550      */
 551     int[] sortedInts = new int[length];
 552     char[] sortedChars = new char[s.length];
 553     for (int i = 0; i < length; i++)
 554     {
 555       sortedInts[i] = arr[indices[i]];
 556       sortedChars[i] = s[indices[i]];
 557     }
 558
 559     /*
 560      * And copy the sorted values back into the arrays
 561      */
 562     System.arraycopy(sortedInts, 0, arr, 0, length);
 563     System.arraycopy(sortedChars, 0, s, 0, s.length);
 564   }
 565 }