test/jalview/util/QuickSortTest.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 static org.testng.AssertJUnit.assertEquals;
  24 import static org.testng.AssertJUnit.assertTrue;
  25
  26 import java.util.Arrays;
  27
  28 import org.testng.annotations.BeforeMethod;
  29 import org.testng.annotations.Test;
  30
  31 public class QuickSortTest
  32 {
  33   private static final String c1 = "Blue";
  34
  35   private static final String c2 = "Yellow";
  36
  37   private static final String c3 = "Orange";
  38
  39   private static final String c4 = "Green";
  40
  41   private Object[] things;
  42
  43   private final Object[] sortedThings = new Object[] { c4, c2, c1, c3 };
  44
  45   @BeforeMethod(alwaysRun = true)
  46   public void setUp()
  47   {
  48     things = new Object[] { c1, c2, c3, c4 };
  49   }
  50
  51   @Test(groups = { "Functional" })
  52   public void testSort_byIntValues()
  53   {
  54     int[] values = new int[] { 3, 2, 4, 1 };
  55     QuickSort.sort(values, things);
  56     assertTrue(Arrays.equals(new int[] { 1, 2, 3, 4 }, values));
  57     assertTrue(Arrays.equals(sortedThings, things));
  58   }
  59
  60   @Test(groups = { "Functional" })
  61   public void testSort_byFloatValues()
  62   {
  63     float[] values = new float[] { 3f, 2f, 4f, 1f };
  64     QuickSort.sort(values, things);
  65     assertTrue(Arrays.equals(new float[] { 1f, 2f, 3f, 4f }, values));
  66     assertTrue(Arrays.equals(sortedThings, things));
  67   }
  68
  69   @Test(groups = { "Functional" })
  70   public void testSort_byDoubleValues()
  71   {
  72     double[] values = new double[] { 3d, 2d, 4d, 1d };
  73     QuickSort.sort(values, things);
  74     assertTrue(Arrays.equals(new double[] { 1d, 2d, 3d, 4d }, values));
  75     assertTrue(Arrays.equals(sortedThings, things));
  76   }
  77
  78   /**
  79    * Sort by String is descending order, case-sensitive
  80    */
  81   @Test(groups = { "Functional" })
  82   public void testSort_byStringValues()
  83   {
  84     String[] values = new String[] { "JOHN", "henry", "lucy", "ALISON" };
  85     QuickSort.sort(values, things);
  86     assertTrue(Arrays.equals(new String[] { "lucy", "henry", "JOHN",
  87         "ALISON" }, values));
  88     assertTrue(Arrays.equals(new Object[] { c3, c2, c1, c4 }, things));
  89   }
  90
  91   /**
  92    * Test whether sort is stable i.e. equal values retain their mutual ordering.
  93    */
  94   @Test(groups = { "Functional" }, enabled = false)
  95   public void testSort_withDuplicates()
  96   {
  97     int[] values = new int[] { 3, 4, 2, 4, 1 };
  98     Object[] things = new Object[] { "A", "X", "Y", "B", "Z" };
  99     QuickSort.sort(values, things);
 100     assertTrue(Arrays.equals(new int[] { 1, 2, 3, 4, 4 }, values));
 101     // this fails - do we care?
 102     assertTrue(Arrays.equals(new Object[] { "Z", "Y", "A", "X", "B" },
 103             things));
 104   }
 105
 106   /**
 107    * Test that exercises sort with a mostly zero-valued sortby array. May be of
 108    * interest to check the sort algorithm is efficient.
 109    */
 110   @Test(groups = { "Functional" })
 111   public void testSort_MostlyZeroValues()
 112   {
 113     char[] residues = new char[64];
 114     for (int i = 0; i < 64; i++)
 115     {
 116       residues[i] = (char) i;
 117     }
 118     float[] counts = new float[64];
 119     counts[43] = 16;
 120     counts[59] = 7;
 121     counts[62] = 2;
 122     QuickSort.sort(counts, residues);
 123     assertEquals(43, residues[63]);
 124     assertEquals(59, residues[62]);
 125     assertEquals(62, residues[61]);
 126   }
 127 }