test/jalview/util/QuickSortTest.java

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