1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
|
6 |
|
|
7 |
|
|
8 |
|
|
9 |
|
|
10 |
|
|
11 |
|
|
12 |
|
|
13 |
|
|
14 |
|
|
15 |
|
|
16 |
|
|
17 |
|
|
18 |
|
|
19 |
|
|
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 |
|
|
|
|
| 65.5% |
Uncovered Elements: 58 (168) |
Complexity: 23 |
Complexity Density: 0.17 |
|
34 |
|
public class QuickSortTest |
35 |
|
{ |
36 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (2) |
Complexity: 1 |
Complexity Density: 0.5 |
|
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 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (6) |
Complexity: 1 |
Complexity Density: 0.17 |
1PASS
|
|
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 |
|
|
63 |
1 |
Object[] expect = new Object[] { c5, c2, c4, c1, c3 }; |
64 |
1 |
assertTrue(Arrays.equals(expect, things)); |
65 |
|
} |
66 |
|
|
67 |
|
|
68 |
|
|
69 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (8) |
Complexity: 1 |
Complexity Density: 0.12 |
1PASS
|
|
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 |
|
|
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 |
|
|
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 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (5) |
Complexity: 1 |
Complexity Density: 0.2 |
1PASS
|
|
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 |
|
|
99 |
1 |
assertTrue(Arrays.equals(new Object[] { c5, c2, c4, c1, c3 }, things)); |
100 |
|
} |
101 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (5) |
Complexity: 1 |
Complexity Density: 0.2 |
1PASS
|
|
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 |
|
|
110 |
1 |
assertTrue(Arrays.equals(new Object[] { c5, c2, c4, c1, c3 }, things)); |
111 |
|
} |
112 |
|
|
113 |
|
|
114 |
|
|
115 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (5) |
Complexity: 1 |
Complexity Density: 0.2 |
1PASS
|
|
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(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 |
|
|
130 |
|
|
|
|
| 0% |
Uncovered Elements: 5 (5) |
Complexity: 1 |
Complexity Density: 0.2 |
1PASS
|
|
131 |
0 |
@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 |
|
|
139 |
0 |
assertTrue(Arrays.equals(new Object[] { "Z", "Y", "A", "X", "B" }, |
140 |
|
letters)); |
141 |
|
} |
142 |
|
|
143 |
|
|
144 |
|
|
145 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (13) |
Complexity: 2 |
Complexity Density: 0.18 |
1PASS
|
|
146 |
1 |
@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]); |
160 |
1 |
assertEquals(59, residues[62]); |
161 |
1 |
assertEquals(43, residues[63]); |
162 |
|
} |
163 |
|
|
164 |
|
|
165 |
|
|
166 |
|
|
167 |
|
|
168 |
|
|
169 |
|
|
170 |
|
|
171 |
|
|
|
|
| 0% |
Uncovered Elements: 51 (51) |
Complexity: 7 |
Complexity Density: 0.18 |
1PASS
|
|
172 |
0 |
@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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
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 |
|
|
260 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (17) |
Complexity: 2 |
Complexity Density: 0.13 |
1PASS
|
|
261 |
1 |
@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 |
|
|
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 |
|
|
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 |
|
|
293 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (13) |
Complexity: 2 |
Complexity Density: 0.18 |
1PASS
|
|
294 |
1 |
@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]); |
308 |
1 |
assertEquals(59, residues[62]); |
309 |
1 |
assertEquals(43, residues[63]); |
310 |
|
} |
311 |
|
|
312 |
|
|
313 |
|
|
314 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (17) |
Complexity: 2 |
Complexity Density: 0.13 |
1PASS
|
|
315 |
1 |
@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 |
|
|
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 |
|
|
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 |
|
|
347 |
|
|
348 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (8) |
Complexity: 1 |
Complexity Density: 0.12 |
1PASS
|
|
349 |
1 |
@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 |
|
|
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 |
|
|
366 |
|
|
367 |
1 |
QuickSort.sortByString(values, things, true); |
368 |
1 |
assertTrue(Arrays.equals(new String[] { "ALISON", "JOHN", "henry", |
369 |
|
"henry", "lucy" }, values)); |
370 |
|
|
371 |
1 |
assertTrue(Arrays.equals(new Object[] { c5, c1, c2, c4, c3 }, things)); |
372 |
|
} |
373 |
|
} |