Clover icon

jalviewX

  1. Project Clover database Wed Oct 31 2018 15:13:58 GMT
  2. Package jalview.util

File QuickSortTest.java

 

Code metrics

20
135
13
1
373
241
23
0.17
10.38
13
1.77

Classes

Class Line # Actions
QuickSortTest 34 135 23 58
0.654761965.5%
 

Contributing tests

This file is covered by 10 tests. .

Source view

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  1 toggle @BeforeClass(alwaysRun = true)
38    public void setUpJvOptionPane()
39    {
40  1 JvOptionPane.setInteractiveMode(false);
41  1 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  1 toggle @Test(groups = { "Functional" })
55    public void testSort_byIntValues()
56    {
57  1 int[] values = new int[] { 3, 0, 4, 3, -1 };
58  1 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
59   
60  1 QuickSort.sort(values, things);
61  1 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  1 Object[] expect = new Object[] { c5, c2, c4, c1, c3 };
64  1 assertTrue(Arrays.equals(expect, things));
65    }
66   
67    /**
68    * Test the alternative sort objects by integer method
69    */
 
70  1 toggle @Test(groups = { "Functional" })
71    public void testSortByInt()
72    {
73  1 int[] values = new int[] { 3, 0, 4, 3, -1 };
74  1 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
75   
76    /*
77    * sort ascending
78    */
79  1 QuickSort.sortByInt(values, things, true);
80  1 assertTrue(Arrays.equals(new int[] { -1, 0, 3, 3, 4 }, values));
81  1 assertTrue(Arrays.equals(new Object[] { c5, c2, c1, c4, c3 }, things));
82   
83    /*
84    * resort descending; c1/c4 should not change order
85    */
86  1 QuickSort.sortByInt(values, things, false);
87  1 assertTrue(Arrays.equals(new int[] { 4, 3, 3, 0, -1 }, values));
88  1 assertTrue(Arrays.equals(new Object[] { c3, c1, c4, c2, c5 }, things));
89    }
90   
 
91  1 toggle @Test(groups = { "Functional" })
92    public void testSort_byFloatValues()
93    {
94  1 float[] values = new float[] { 3f, 0f, 4f, 3f, -1f };
95  1 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
96  1 QuickSort.sort(values, things);
97  1 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  1 assertTrue(Arrays.equals(new Object[] { c5, c2, c4, c1, c3 }, things));
100    }
101   
 
102  1 toggle @Test(groups = { "Functional" })
103    public void testSort_byDoubleValues()
104    {
105  1 double[] values = new double[] { 3d, 0d, 4d, 3d, -1d };
106  1 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
107  1 QuickSort.sort(values, things);
108  1 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  1 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  1 toggle @Test(groups = { "Functional" })
117    public void testSort_byStringValues()
118    {
119  1 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
120  1 String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
121    "ALISON" };
122  1 QuickSort.sort(values, things);
123  1 assertTrue(Arrays.equals(new String[] { "lucy", "henry", "henry",
124    "JOHN", "ALISON" }, values));
125  1 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  0 toggle @Test(groups = { "Functional" }, enabled = false)
132    public void testSort_withDuplicates()
133    {
134  0 int[] values = new int[] { 3, 4, 2, 4, 1 };
135  0 Object[] letters = new Object[] { "A", "X", "Y", "B", "Z" };
136  0 QuickSort.sort(values, letters);
137  0 assertTrue(Arrays.equals(new int[] { 1, 2, 3, 4, 4 }, values));
138    // this fails - do we care?
139  0 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  1 toggle @Test(groups = { "Functional" })
147    public void testSort_charSortByFloat_mostlyZeroValues()
148    {
149  1 char[] residues = new char[64];
150  65 for (int i = 0; i < 64; i++)
151    {
152  64 residues[i] = (char) i;
153    }
154  1 float[] counts = new float[64];
155  1 counts[43] = 16;
156  1 counts[59] = 7;
157  1 counts[62] = -2;
158  1 QuickSort.sort(counts, residues);
159  1 assertEquals(62, residues[0]); // negative sorts to front
160  1 assertEquals(59, residues[62]); // 7 sorts to next-to-end
161  1 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  0 toggle @Test(groups = { "Timing" }, enabled = false)
173    public void testSort_timingTest()
174    {
175  0 char[] residues = new char[256];
176  0 for (int i = 0; i < residues.length; i++)
177    {
178  0 residues[i] = (char) i;
179    }
180  0 float[] counts = new float[residues.length];
181   
182  0 int iterations = 1000000;
183   
184    /*
185    * time it using optimised sort (of a mostly zero-filled array)
186    */
187  0 long start = System.currentTimeMillis();
188  0 for (int i = 0; i < iterations; i++)
189    {
190  0 Arrays.fill(counts, 0f);
191  0 counts[43] = 16;
192  0 counts[59] = 7;
193  0 counts[62] = -2;
194  0 QuickSort.sort(counts, residues);
195    }
196  0 long elapsed = System.currentTimeMillis() - start;
197  0 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  0 start = System.currentTimeMillis();
206  0 for (int i = 0; i < iterations; i++)
207    {
208  0 Arrays.fill(counts, 0f);
209  0 counts[43] = 16;
210  0 counts[59] = 7;
211  0 counts[62] = -2;
212  0 QuickSort.charSortByFloat(counts, residues, true);
213    }
214  0 elapsed = System.currentTimeMillis() - start;
215  0 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  0 Random random = new Random();
224  0 float[] randoms = new float[counts.length];
225  0 for (int i = 0; i < randoms.length; i++)
226    {
227  0 randoms[i] = random.nextFloat();
228    }
229   
230  0 start = System.currentTimeMillis();
231  0 for (int i = 0; i < iterations; i++)
232    {
233  0 System.arraycopy(randoms, 0, counts, 0, randoms.length);
234  0 QuickSort.sort(counts, residues);
235    }
236  0 elapsed = System.currentTimeMillis() - start;
237  0 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  0 start = System.currentTimeMillis();
246  0 for (int i = 0; i < iterations; i++)
247    {
248  0 System.arraycopy(randoms, 0, counts, 0, randoms.length);
249  0 QuickSort.charSortByFloat(counts, residues, true);
250    }
251  0 elapsed = System.currentTimeMillis() - start;
252  0 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  1 toggle @Test(groups = { "Functional" })
262    public void testCharSortByFloat()
263    {
264  1 char[] residues = new char[64];
265  65 for (int i = 0; i < 64; i++)
266    {
267  64 residues[i] = (char) i;
268    }
269  1 float[] counts = new float[64];
270  1 counts[43] = 16;
271  1 counts[59] = 7;
272  1 counts[62] = -2;
273   
274    /*
275    * sort ascending
276    */
277  1 QuickSort.charSortByFloat(counts, residues, true);
278  1 assertEquals(62, residues[0]);
279  1 assertEquals(59, residues[62]);
280  1 assertEquals(43, residues[63]);
281   
282    /*
283    * resort descending
284    */
285  1 QuickSort.charSortByFloat(counts, residues, false);
286  1 assertEquals(62, residues[63]);
287  1 assertEquals(59, residues[1]);
288  1 assertEquals(43, residues[0]);
289    }
290   
291    /**
292    * Test of method that sorts chars by an int array
293    */
 
294  1 toggle @Test(groups = { "Functional" })
295    public void testSort_charSortByInt_mostlyZeroValues()
296    {
297  1 char[] residues = new char[64];
298  65 for (int i = 0; i < 64; i++)
299    {
300  64 residues[i] = (char) i;
301    }
302  1 int[] counts = new int[64];
303  1 counts[43] = 16;
304  1 counts[59] = 7;
305  1 counts[62] = -2;
306  1 QuickSort.sort(counts, residues);
307  1 assertEquals(62, residues[0]); // negative sorts to front
308  1 assertEquals(59, residues[62]); // 7 sorts to next-to-end
309  1 assertEquals(43, residues[63]); // 16 sorts to end
310    }
311   
312    /**
313    * Test that exercises sorting without any attempt at fancy optimisation.
314    */
 
315  1 toggle @Test(groups = { "Functional" })
316    public void testCharSortByInt()
317    {
318  1 char[] residues = new char[64];
319  65 for (int i = 0; i < 64; i++)
320    {
321  64 residues[i] = (char) i;
322    }
323  1 int[] counts = new int[64];
324  1 counts[43] = 16;
325  1 counts[59] = 7;
326  1 counts[62] = -2;
327   
328    /*
329    * sort ascending
330    */
331  1 QuickSort.charSortByInt(counts, residues, true);
332  1 assertEquals(62, residues[0]);
333  1 assertEquals(59, residues[62]);
334  1 assertEquals(43, residues[63]);
335   
336    /*
337    * resort descending
338    */
339  1 QuickSort.charSortByInt(counts, residues, false);
340  1 assertEquals(62, residues[63]);
341  1 assertEquals(59, residues[1]);
342  1 assertEquals(43, residues[0]);
343    }
344   
345    /**
346    * Tests the alternative method to sort bby String in descending order,
347    * case-sensitive
348    */
 
349  1 toggle @Test(groups = { "Functional" })
350    public void testSortByString()
351    {
352  1 Object[] things = new Object[] { c1, c2, c3, c4, c5 };
353  1 String[] values = new String[] { "JOHN", "henry", "lucy", "henry",
354    "ALISON" };
355   
356    /*
357    * sort descending
358    */
359  1 QuickSort.sortByString(values, things, false);
360  1 assertTrue(Arrays.equals(new String[] { "lucy", "henry", "henry",
361    "JOHN", "ALISON" }, values));
362  1 assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things));
363   
364    /*
365    * resort ascending
366    */
367  1 QuickSort.sortByString(values, things, true);
368  1 assertTrue(Arrays.equals(new String[] { "ALISON", "JOHN", "henry",
369    "henry", "lucy" }, values));
370    // sort is stable: c2/c4 do not swap order
371  1 assertTrue(Arrays.equals(new Object[] { c5, c1, c2, c4, c3 }, things));
372    }
373    }
  • Report generated by OpenClover v 4.2.1 on Wed Oct 31 2018 15:15:54 GMT using coverage data from Wed Oct 31 2018 15:15:47 GMT.
  • Clover free edition.