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(
 124             Arrays.equals(new String[]
 125             { "lucy", "henry", "henry", "JOHN", "ALISON" }, values));
 126     assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
 127   }
 128
 129   /**
 130    * Test whether sort is stable i.e. equal values retain their mutual ordering.
 131    */
 132   @Test(groups = { "Functional" }, enabled = false)
 133   public void testSort_withDuplicates()
 134   {
 135     int[] values = new int[] { 3, 4, 2, 4, 1 };
 136     Object[] letters = new Object[] { "A", "X", "Y", "B", "Z" };
 137     QuickSort.sort(values, letters);
 138     assertTrue(Arrays.equals(new int[] { 1, 2, 3, 4, 4 }, values));
 139     // this fails - do we care?
 140     assertTrue(
 141             Arrays.equals(new Object[]
 142             { "Z", "Y", "A", "X", "B" }, letters));
 143   }
 144
 145   /**
 146    * Test of method that sorts chars by a float array
 147    */
 148   @Test(groups = { "Functional" })
 149   public void testSort_charSortByFloat_mostlyZeroValues()
 150   {
 151     char[] residues = new char[64];
 152     for (int i = 0; i < 64; i++)
 153     {
 154       residues[i] = (char) i;
 155     }
 156     float[] counts = new float[64];
 157     counts[43] = 16;
 158     counts[59] = 7;
 159     counts[62] = -2;
 160     QuickSort.sort(counts, residues);
 161     assertEquals(62, residues[0]); // negative sorts to front
 162     assertEquals(59, residues[62]); // 7 sorts to next-to-end
 163     assertEquals(43, residues[63]); // 16 sorts to end
 164   }
 165
 166   /**
 167    * Timing test - to be run manually as needed, not part of the automated
 168    * suite. <br>
 169    * It shows that the optimised sort is 3-4 times faster than the simple
 170    * external sort if the data to be sorted is mostly zero, but slightly slower
 171    * if the data is fully populated with non-zero values. Worst case for an
 172    * array of size 256 is about 100 sorts per millisecond.
 173    */
 174   @Test(groups = { "Timing" }, enabled = false)
 175   public void testSort_timingTest()
 176   {
 177     char[] residues = new char[256];
 178     for (int i = 0; i < residues.length; i++)
 179     {
 180       residues[i] = (char) i;
 181     }
 182     float[] counts = new float[residues.length];
 183
 184     int iterations = 1000000;
 185
 186     /*
 187      * time it using optimised sort (of a mostly zero-filled array)
 188      */
 189     long start = System.currentTimeMillis();
 190     for (int i = 0; i < iterations; i++)
 191     {
 192       Arrays.fill(counts, 0f);
 193       counts[43] = 16;
 194       counts[59] = 7;
 195       counts[62] = -2;
 196       QuickSort.sort(counts, residues);
 197     }
 198     long elapsed = System.currentTimeMillis() - start;
 199     System.out.println(String.format(
 200             "Time for %d optimised sorts of mostly zeros array length %d was %dms",
 201             iterations, counts.length, elapsed));
 202
 203     /*
 204      * time it using unoptimised external sort
 205      */
 206     start = System.currentTimeMillis();
 207     for (int i = 0; i < iterations; i++)
 208     {
 209       Arrays.fill(counts, 0f);
 210       counts[43] = 16;
 211       counts[59] = 7;
 212       counts[62] = -2;
 213       QuickSort.charSortByFloat(counts, residues, true);
 214     }
 215     elapsed = System.currentTimeMillis() - start;
 216     System.out.println(String.format(
 217             "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.println(String.format(
 238             "Time for %d optimised sorts of non-zeros array length %d was %dms",
 239             iterations, counts.length, elapsed));
 240
 241     /*
 242      * time unoptimised external sort, filled array
 243      */
 244     start = System.currentTimeMillis();
 245     for (int i = 0; i < iterations; i++)
 246     {
 247       System.arraycopy(randoms, 0, counts, 0, randoms.length);
 248       QuickSort.charSortByFloat(counts, residues, true);
 249     }
 250     elapsed = System.currentTimeMillis() - start;
 251     System.out.println(String.format(
 252             "Time for %d external sorts of non-zeros array length %d was %dms",
 253             iterations, counts.length, elapsed));
 254   }
 255
 256   /**
 257    * Test that exercises sort without any attempt at fancy optimisation
 258    */
 259   @Test(groups = { "Functional" })
 260   public void testCharSortByFloat()
 261   {
 262     char[] residues = new char[64];
 263     for (int i = 0; i < 64; i++)
 264     {
 265       residues[i] = (char) i;
 266     }
 267     float[] counts = new float[64];
 268     counts[43] = 16;
 269     counts[59] = 7;
 270     counts[62] = -2;
 271
 272     /*
 273      * sort ascending
 274      */
 275     QuickSort.charSortByFloat(counts, residues, true);
 276     assertEquals(62, residues[0]);
 277     assertEquals(59, residues[62]);
 278     assertEquals(43, residues[63]);
 279
 280     /*
 281      * resort descending
 282      */
 283     QuickSort.charSortByFloat(counts, residues, false);
 284     assertEquals(62, residues[63]);
 285     assertEquals(59, residues[1]);
 286     assertEquals(43, residues[0]);
 287   }
 288
 289   /**
 290    * Test of method that sorts chars by an int array
 291    */
 292   @Test(groups = { "Functional" })
 293   public void testSort_charSortByInt_mostlyZeroValues()
 294   {
 295     char[] residues = new char[64];
 296     for (int i = 0; i < 64; i++)
 297     {
 298       residues[i] = (char) i;
 299     }
 300     int[] counts = new int[64];
 301     counts[43] = 16;
 302     counts[59] = 7;
 303     counts[62] = -2;
 304     QuickSort.sort(counts, residues);
 305     assertEquals(62, residues[0]); // negative sorts to front
 306     assertEquals(59, residues[62]); // 7 sorts to next-to-end
 307     assertEquals(43, residues[63]); // 16 sorts to end
 308   }
 309
 310   /**
 311    * Test that exercises sorting without any attempt at fancy optimisation.
 312    */
 313   @Test(groups = { "Functional" })
 314   public void testCharSortByInt()
 315   {
 316     char[] residues = new char[64];
 317     for (int i = 0; i < 64; i++)
 318     {
 319       residues[i] = (char) i;
 320     }
 321     int[] counts = new int[64];
 322     counts[43] = 16;
 323     counts[59] = 7;
 324     counts[62] = -2;
 325
 326     /*
 327      * sort ascending
 328      */
 329     QuickSort.charSortByInt(counts, residues, true);
 330     assertEquals(62, residues[0]);
 331     assertEquals(59, residues[62]);
 332     assertEquals(43, residues[63]);
 333
 334     /*
 335      * resort descending
 336      */
 337     QuickSort.charSortByInt(counts, residues, false);
 338     assertEquals(62, residues[63]);
 339     assertEquals(59, residues[1]);
 340     assertEquals(43, residues[0]);
 341   }
 342
 343   /**
 344    * Tests the alternative method to sort bby String in descending order,
 345    * case-sensitive
 346    */
 347   @Test(groups = { "Functional" })
 348   public void testSortByString()
 349   {
 350     Object[] things = new Object[] { c1, c2, c3, c4, c5 };
 351     String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
 352         "ALISON" };
 353
 354     /*
 355      * sort descending
 356      */
 357     QuickSort.sortByString(values, things, false);
 358     assertTrue(
 359             Arrays.equals(new String[]
 360             { "lucy", "henry", "henry", "JOHN", "ALISON" }, values));
 361     assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
 362
 363     /*
 364      * resort ascending
 365      */
 366     QuickSort.sortByString(values, things, true);
 367     assertTrue(
 368             Arrays.equals(new String[]
 369             { "ALISON", "JOHN", "henry", "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 }