Class |
Line # |
Actions |
|||
---|---|---|---|---|---|
QuickSortTest | 34 | 135 | 23 |
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 | @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 | @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 | @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 | @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 | @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 | @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( |
124 | Arrays.equals(new String[] | |
125 | { "lucy", "henry", "henry", "JOHN", "ALISON" }, values)); | |
126 | 1 | 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 | @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 | 1 | @Test(groups = { "Functional" }) |
149 | public void testSort_charSortByFloat_mostlyZeroValues() | |
150 | { | |
151 | 1 | char[] residues = new char[64]; |
152 | 65 | for (int i = 0; i < 64; i++) |
153 | { | |
154 | 64 | residues[i] = (char) i; |
155 | } | |
156 | 1 | float[] counts = new float[64]; |
157 | 1 | counts[43] = 16; |
158 | 1 | counts[59] = 7; |
159 | 1 | counts[62] = -2; |
160 | 1 | QuickSort.sort(counts, residues); |
161 | 1 | assertEquals(62, residues[0]); // negative sorts to front |
162 | 1 | assertEquals(59, residues[62]); // 7 sorts to next-to-end |
163 | 1 | 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 | @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 | 1 | @Test(groups = { "Functional" }) |
260 | public void testCharSortByFloat() | |
261 | { | |
262 | 1 | char[] residues = new char[64]; |
263 | 65 | for (int i = 0; i < 64; i++) |
264 | { | |
265 | 64 | residues[i] = (char) i; |
266 | } | |
267 | 1 | float[] counts = new float[64]; |
268 | 1 | counts[43] = 16; |
269 | 1 | counts[59] = 7; |
270 | 1 | counts[62] = -2; |
271 | ||
272 | /* | |
273 | * sort ascending | |
274 | */ | |
275 | 1 | QuickSort.charSortByFloat(counts, residues, true); |
276 | 1 | assertEquals(62, residues[0]); |
277 | 1 | assertEquals(59, residues[62]); |
278 | 1 | assertEquals(43, residues[63]); |
279 | ||
280 | /* | |
281 | * resort descending | |
282 | */ | |
283 | 1 | QuickSort.charSortByFloat(counts, residues, false); |
284 | 1 | assertEquals(62, residues[63]); |
285 | 1 | assertEquals(59, residues[1]); |
286 | 1 | assertEquals(43, residues[0]); |
287 | } | |
288 | ||
289 | /** | |
290 | * Test of method that sorts chars by an int array | |
291 | */ | |
292 | 1 | @Test(groups = { "Functional" }) |
293 | public void testSort_charSortByInt_mostlyZeroValues() | |
294 | { | |
295 | 1 | char[] residues = new char[64]; |
296 | 65 | for (int i = 0; i < 64; i++) |
297 | { | |
298 | 64 | residues[i] = (char) i; |
299 | } | |
300 | 1 | int[] counts = new int[64]; |
301 | 1 | counts[43] = 16; |
302 | 1 | counts[59] = 7; |
303 | 1 | counts[62] = -2; |
304 | 1 | QuickSort.sort(counts, residues); |
305 | 1 | assertEquals(62, residues[0]); // negative sorts to front |
306 | 1 | assertEquals(59, residues[62]); // 7 sorts to next-to-end |
307 | 1 | assertEquals(43, residues[63]); // 16 sorts to end |
308 | } | |
309 | ||
310 | /** | |
311 | * Test that exercises sorting without any attempt at fancy optimisation. | |
312 | */ | |
313 | 1 | @Test(groups = { "Functional" }) |
314 | public void testCharSortByInt() | |
315 | { | |
316 | 1 | char[] residues = new char[64]; |
317 | 65 | for (int i = 0; i < 64; i++) |
318 | { | |
319 | 64 | residues[i] = (char) i; |
320 | } | |
321 | 1 | int[] counts = new int[64]; |
322 | 1 | counts[43] = 16; |
323 | 1 | counts[59] = 7; |
324 | 1 | counts[62] = -2; |
325 | ||
326 | /* | |
327 | * sort ascending | |
328 | */ | |
329 | 1 | QuickSort.charSortByInt(counts, residues, true); |
330 | 1 | assertEquals(62, residues[0]); |
331 | 1 | assertEquals(59, residues[62]); |
332 | 1 | assertEquals(43, residues[63]); |
333 | ||
334 | /* | |
335 | * resort descending | |
336 | */ | |
337 | 1 | QuickSort.charSortByInt(counts, residues, false); |
338 | 1 | assertEquals(62, residues[63]); |
339 | 1 | assertEquals(59, residues[1]); |
340 | 1 | assertEquals(43, residues[0]); |
341 | } | |
342 | ||
343 | /** | |
344 | * Tests the alternative method to sort bby String in descending order, | |
345 | * case-sensitive | |
346 | */ | |
347 | 1 | @Test(groups = { "Functional" }) |
348 | public void testSortByString() | |
349 | { | |
350 | 1 | Object[] things = new Object[] { c1, c2, c3, c4, c5 }; |
351 | 1 | String[] values = new String[] { "JOHN", "henry", "lucy", "henry", |
352 | "ALISON" }; | |
353 | ||
354 | /* | |
355 | * sort descending | |
356 | */ | |
357 | 1 | QuickSort.sortByString(values, things, false); |
358 | 1 | assertTrue( |
359 | Arrays.equals(new String[] | |
360 | { "lucy", "henry", "henry", "JOHN", "ALISON" }, values)); | |
361 | 1 | assertTrue(Arrays.equals(new Object[] { c3, c2, c4, c1, c5 }, things)); |
362 | ||
363 | /* | |
364 | * resort ascending | |
365 | */ | |
366 | 1 | QuickSort.sortByString(values, things, true); |
367 | 1 | assertTrue( |
368 | Arrays.equals(new String[] | |
369 | { "ALISON", "JOHN", "henry", "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 | } |