Clover icon

Coverage Report

  1. Project Clover database Thu Nov 7 2024 17:01:39 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
0.00%
 

Contributing tests

No tests hitting this source file were found.

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