test/jalview/util/QuickSortTest.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 static org.testng.AssertJUnit.assertEquals;
  24 import static org.testng.AssertJUnit.assertTrue;
  25
  26 import jalview.gui.JvOptionPane;
  27
  28 import java.util.Arrays;
  29 import java.util.Random;
  30
  31 import org.testng.annotations.BeforeClass;
  32 import org.testng.annotations.Test;
  33
  34 public class QuickSortTest
  35 {
  36
  37   @BeforeClass(alwaysRun = true)
  38   public void setUpJvOptionPane()
  39   {
  40     JvOptionPane.setInteractiveMode(false);
  41     JvOptionPane.setMockResponse(JvOptionPane.CANCEL_OPTION);
  42   }
  43
  44   private static final String c1 = "Blue";
  45
  46   private static final String c2 = "Yellow";
  47
  48   private static final String c3 = "Orange";
  49
  50   private static final String c4 = "Green";
  51
  52   private static final String c5 = "Pink";
  53
  54   @Test(groups = { "Functional" })
  55   public void testSort_byIntValues()
  56   {
  57     int[] values = new int[] { 3, 0, 4, 3, -1 };
  58     Object[] things = new Object[] { c1, c2, c3, c4, c5 };
  59
  60     QuickSort.sort(values, things);
  61     assertTrue(Arrays.equals(new int[] { -1, 0, 3, 3, 4 }, values));
  62     // note sort is not stable: c1/c4 are equal but get reordered
  63     Object[] expect = new Object[] { c5, c2, c4, c1, c3 };
  64     assertTrue(Arrays.equals(expect, things));
  65   }
  66
  67   /**
  68    * Test the alternative sort objects by integer method
  69    */
  70   @Test(groups = { "Functional" })
  71   public void testSortByInt()
  72   {
  73     int[] values = new int[] { 3, 0, 4, 3, -1 };
  74     Object[] things = new Object[] { c1, c2, c3, c4, c5 };
  75
  76     /*
  77      * sort ascending
  78      */
  79     QuickSort.sortByInt(values, things, true);
  80     assertTrue(Arrays.equals(new int[] { -1, 0, 3, 3, 4 }, values));
  81     assertTrue(Arrays.equals(new Object[] { c5, c2, c1, c4, c3 }, things));
  82
  83     /*
  84      * resort descending; c1/c4 should not change order
  85      */
  86     QuickSort.sortByInt(values, things, false);
  87     assertTrue(Arrays.equals(new int[] { 4, 3, 3, 0, -1 }, values));
  88     assertTrue(Arrays.equals(new Object[] { c3, c1, c4, c2, c5 }, things));
  89   }
  90
  91   @Test(groups = { "Functional" })
  92   public void testSort_byFloatValues()
  93   {
  94     float[] values = new float[] { 3f, 0f, 4f, 3f, -1f };
  95     Object[] things = new Object[] { c1, c2, c3, c4, c5 };
  96     QuickSort.sort(values, things);
  97     assertTrue(Arrays.equals(new float[] { -1f, 0f, 3f, 3f, 4f }, values));
  98     // note sort is not stable: c1/c4 are equal but get reordered
  99     assertTrue(Arrays.equals(new Object[] { c5, c2, c4, c1, c3 }, things));
 100   }
 101
 102   @Test(groups = { "Functional" })
 103   public void testSort_byDoubleValues()
 104   {
 105     double[] values = new double[] { 3d, 0d, 4d, 3d, -1d };
 106     Object[] things = new Object[] { c1, c2, c3, c4, c5 };
 107     QuickSort.sort(values, things);
 108     assertTrue(Arrays.equals(new double[] { -1d, 0d, 3d, 3d, 4d }, values));
 109     // note sort is not stable: c1/c4 are equal but get reordered
 110     assertTrue(Arrays.equals(new Object[] { c5, c2, c4, c1, c3 }, things));
 111   }
 112
 113   /**
 114    * Sort by String is descending order, case-sensitive
 115    */
 116   @Test(groups = { "Functional" })
 117   public void testSort_byStringValues()
 118   {
 119     Object[] things = new Object[] { c1, c2, c3, c4, c5 };
 120     String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
 121         "ALISON" };
 122     QuickSort.sort(values, things);
 123     assertTrue(Arrays.equals(new String[] { "lucy", "henry", "henry",
 124         "JOHN", "ALISON" }, values));
 125     assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
 126   }
 127
 128   /**
 129    * Test whether sort is stable i.e. equal values retain their mutual ordering.
 130    */
 131   @Test(groups = { "Functional" }, enabled = false)
 132   public void testSort_withDuplicates()
 133   {
 134     int[] values = new int[] { 3, 4, 2, 4, 1 };
 135     Object[] letters = new Object[] { "A", "X", "Y", "B", "Z" };
 136     QuickSort.sort(values, letters);
 137     assertTrue(Arrays.equals(new int[] { 1, 2, 3, 4, 4 }, values));
 138     // this fails - do we care?
 139     assertTrue(Arrays.equals(new Object[] { "Z", "Y", "A", "X", "B" },
 140             letters));
 141   }
 142
 143   /**
 144    * Test of method that sorts chars by a float array
 145    */
 146   @Test(groups = { "Functional" })
 147   public void testSort_charSortByFloat_mostlyZeroValues()
 148   {
 149     char[] residues = new char[64];
 150     for (int i = 0; i < 64; i++)
 151     {
 152       residues[i] = (char) i;
 153     }
 154     float[] counts = new float[64];
 155     counts[43] = 16;
 156     counts[59] = 7;
 157     counts[62] = -2;
 158     QuickSort.sort(counts, residues);
 159     assertEquals(62, residues[0]); // negative sorts to front
 160     assertEquals(59, residues[62]); // 7 sorts to next-to-end
 161     assertEquals(43, residues[63]); // 16 sorts to end
 162   }
 163
 164   /**
 165    * Timing test - to be run manually as needed, not part of the automated
 166    * suite. <br>
 167    * It shows that the optimised sort is 3-4 times faster than the simple
 168    * external sort if the data to be sorted is mostly zero, but slightly slower
 169    * if the data is fully populated with non-zero values. Worst case for an
 170    * array of size 256 is about 100 sorts per millisecond.
 171    */
 172   @Test(groups = { "Timing" }, enabled = false)
 173   public void testSort_timingTest()
 174   {
 175     char[] residues = new char[256];
 176     for (int i = 0; i < residues.length; i++)
 177     {
 178       residues[i] = (char) i;
 179     }
 180     float[] counts = new float[residues.length];
 181
 182     int iterations = 1000000;
 183
 184     /*
 185      * time it using optimised sort (of a mostly zero-filled array)
 186      */
 187     long start = System.currentTimeMillis();
 188     for (int i = 0; i < iterations; i++)
 189     {
 190       Arrays.fill(counts, 0f);
 191       counts[43] = 16;
 192       counts[59] = 7;
 193       counts[62] = -2;
 194       QuickSort.sort(counts, residues);
 195     }
 196     long elapsed = System.currentTimeMillis() - start;
 197     System.out
 198             .println(String
 199                     .format("Time for %d optimised sorts of mostly zeros array length %d was %dms",
 200                             iterations, counts.length, elapsed));
 201
 202     /*
 203      * time it using unoptimised external sort
 204      */
 205     start = System.currentTimeMillis();
 206     for (int i = 0; i < iterations; i++)
 207     {
 208       Arrays.fill(counts, 0f);
 209       counts[43] = 16;
 210       counts[59] = 7;
 211       counts[62] = -2;
 212       QuickSort.charSortByFloat(counts, residues, true);
 213     }
 214     elapsed = System.currentTimeMillis() - start;
 215     System.out
 216             .println(String
 217                     .format("Time for %d external sorts of mostly zeros array length %d was %dms",
 218                             iterations, counts.length, elapsed));
 219
 220     /*
 221      * optimised external sort, well-filled array
 222      */
 223     Random random = new Random();
 224     float[] randoms = new float[counts.length];
 225     for (int i = 0; i < randoms.length; i++)
 226     {
 227       randoms[i] = random.nextFloat();
 228     }
 229
 230     start = System.currentTimeMillis();
 231     for (int i = 0; i < iterations; i++)
 232     {
 233       System.arraycopy(randoms, 0, counts, 0, randoms.length);
 234       QuickSort.sort(counts, residues);
 235     }
 236     elapsed = System.currentTimeMillis() - start;
 237     System.out
 238             .println(String
 239                     .format("Time for %d optimised sorts of non-zeros array length %d was %dms",
 240                             iterations, counts.length, elapsed));
 241
 242     /*
 243      * time unoptimised external sort, filled array
 244      */
 245     start = System.currentTimeMillis();
 246     for (int i = 0; i < iterations; i++)
 247     {
 248       System.arraycopy(randoms, 0, counts, 0, randoms.length);
 249       QuickSort.charSortByFloat(counts, residues, true);
 250     }
 251     elapsed = System.currentTimeMillis() - start;
 252     System.out
 253             .println(String
 254                     .format("Time for %d external sorts of non-zeros array length %d was %dms",
 255                             iterations, counts.length, elapsed));
 256   }
 257
 258   /**
 259    * Test that exercises sort without any attempt at fancy optimisation
 260    */
 261   @Test(groups = { "Functional" })
 262   public void testCharSortByFloat()
 263   {
 264     char[] residues = new char[64];
 265     for (int i = 0; i < 64; i++)
 266     {
 267       residues[i] = (char) i;
 268     }
 269     float[] counts = new float[64];
 270     counts[43] = 16;
 271     counts[59] = 7;
 272     counts[62] = -2;
 273
 274     /*
 275      * sort ascending
 276      */
 277     QuickSort.charSortByFloat(counts, residues, true);
 278     assertEquals(62, residues[0]);
 279     assertEquals(59, residues[62]);
 280     assertEquals(43, residues[63]);
 281
 282     /*
 283      * resort descending
 284      */
 285     QuickSort.charSortByFloat(counts, residues, false);
 286     assertEquals(62, residues[63]);
 287     assertEquals(59, residues[1]);
 288     assertEquals(43, residues[0]);
 289   }
 290
 291   /**
 292    * Test of method that sorts chars by an int array
 293    */
 294   @Test(groups = { "Functional" })
 295   public void testSort_charSortByInt_mostlyZeroValues()
 296   {
 297     char[] residues = new char[64];
 298     for (int i = 0; i < 64; i++)
 299     {
 300       residues[i] = (char) i;
 301     }
 302     int[] counts = new int[64];
 303     counts[43] = 16;
 304     counts[59] = 7;
 305     counts[62] = -2;
 306     QuickSort.sort(counts, residues);
 307     assertEquals(62, residues[0]); // negative sorts to front
 308     assertEquals(59, residues[62]); // 7 sorts to next-to-end
 309     assertEquals(43, residues[63]); // 16 sorts to end
 310   }
 311
 312   /**
 313    * Test that exercises sorting without any attempt at fancy optimisation.
 314    */
 315   @Test(groups = { "Functional" })
 316   public void testCharSortByInt()
 317   {
 318     char[] residues = new char[64];
 319     for (int i = 0; i < 64; i++)
 320     {
 321       residues[i] = (char) i;
 322     }
 323     int[] counts = new int[64];
 324     counts[43] = 16;
 325     counts[59] = 7;
 326     counts[62] = -2;
 327
 328     /*
 329      * sort ascending
 330      */
 331     QuickSort.charSortByInt(counts, residues, true);
 332     assertEquals(62, residues[0]);
 333     assertEquals(59, residues[62]);
 334     assertEquals(43, residues[63]);
 335
 336     /*
 337      * resort descending
 338      */
 339     QuickSort.charSortByInt(counts, residues, false);
 340     assertEquals(62, residues[63]);
 341     assertEquals(59, residues[1]);
 342     assertEquals(43, residues[0]);
 343   }
 344
 345   /**
 346    * Tests the alternative method to sort bby String in descending order,
 347    * case-sensitive
 348    */
 349   @Test(groups = { "Functional" })
 350   public void testSortByString()
 351   {
 352     Object[] things = new Object[] { c1, c2, c3, c4, c5 };
 353     String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
 354         "ALISON" };
 355
 356     /*
 357      * sort descending
 358      */
 359     QuickSort.sortByString(values, things, false);
 360     assertTrue(Arrays.equals(new String[] { "lucy", "henry", "henry",
 361         "JOHN", "ALISON" }, values));
 362     assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
 363
 364     /*
 365      * resort ascending
 366      */
 367     QuickSort.sortByString(values, things, true);
 368     assertTrue(Arrays.equals(new String[] { "ALISON", "JOHN", "henry",
 369         "henry", "lucy" }, values));
 370     // sort is stable: c2/c4 do not swap order
 371     assertTrue(Arrays.equals(new Object[] { c5, c1, c2, c4, c3 }, things));
 372   }
 373 }