Added
Link Here
|
1 |
/******************************************************************************* |
2 |
* Copyright (c) 2004 IBM Corporation and others. |
3 |
* All rights reserved. This program and the accompanying materials |
4 |
* are made available under the terms of the Common Public License v1.0 |
5 |
* which accompanies this distribution, and is available at |
6 |
* http://www.eclipse.org/legal/cpl-v10.html |
7 |
* |
8 |
* Contributors: |
9 |
* IBM Corporation - initial API and implementation |
10 |
*******************************************************************************/ |
11 |
package org.eclipse.jface.tests.viewers; |
12 |
|
13 |
import java.util.Arrays; |
14 |
import java.util.Iterator; |
15 |
import java.util.TreeSet; |
16 |
|
17 |
import junit.framework.Assert; |
18 |
import junit.framework.Test; |
19 |
import junit.framework.TestCase; |
20 |
import junit.framework.TestSuite; |
21 |
|
22 |
import org.eclipse.jface.viewers.deferred.LazySortedCollection; |
23 |
|
24 |
/** |
25 |
* @since 3.1 |
26 |
*/ |
27 |
public class LazySortedCollectionTest extends TestCase { |
28 |
|
29 |
public static void main(String[] args) { |
30 |
junit.textui.TestRunner.run(LazySortedCollectionTest.class); |
31 |
} |
32 |
|
33 |
public static Test suite() { |
34 |
return new TestSuite(LazySortedCollectionTest.class); |
35 |
} |
36 |
|
37 |
private TestComparator comparator; |
38 |
private TestComparator comparisonComparator; |
39 |
|
40 |
// All operations will be done on both collections -- after each operation, the result |
41 |
// will be compared |
42 |
private LazySortedCollection collection; |
43 |
private TreeSet comparisonCollection; |
44 |
|
45 |
/** |
46 |
* Please don't add or remove from this set -- we rely on the exact insertion order |
47 |
* to get full coverage from the removal tests. |
48 |
*/ |
49 |
private String[] se = new String[] { |
50 |
"v00 aaaaaa", |
51 |
"v01 apple", |
52 |
"v02 booger", |
53 |
"v03 car", |
54 |
"v04 dog", |
55 |
"v05 elephant", |
56 |
"v06 fox", |
57 |
"v07 goose", |
58 |
"v08 hippie", |
59 |
"v09 iguana", |
60 |
"v10 junk", |
61 |
"v11 karma", |
62 |
"v12 lemon", |
63 |
"v13 mongoose", |
64 |
"v14 noodle", |
65 |
"v15 opal", |
66 |
"v16 pumpkin", |
67 |
"v17 quirks", |
68 |
"v18 resteraunt", |
69 |
"v19 soap", |
70 |
"v20 timmy", |
71 |
"v21 ugly", |
72 |
"v22 virus", |
73 |
"v23 wigwam", |
74 |
"v24 xerxes", |
75 |
"v25 yellow", |
76 |
"v26 zero" |
77 |
}; |
78 |
|
79 |
/** |
80 |
* Please don't mess with the insertion order here or add or remove from this set -- |
81 |
* we rely on the exact order in order to get full coverage for the removal tests. |
82 |
*/ |
83 |
private String[] elements = new String[] { |
84 |
se[19], |
85 |
se[7], |
86 |
se[6], |
87 |
se[1], |
88 |
se[20], |
89 |
se[8], |
90 |
se[0], |
91 |
se[23], |
92 |
se[17], |
93 |
se[18], |
94 |
se[24], |
95 |
se[25], |
96 |
se[10], |
97 |
se[5], |
98 |
se[15], |
99 |
se[16], |
100 |
se[21], |
101 |
se[26], |
102 |
se[22], |
103 |
se[3], |
104 |
se[9], |
105 |
se[4], |
106 |
se[11], |
107 |
se[12], |
108 |
se[13], |
109 |
se[14], |
110 |
se[2] |
111 |
}; |
112 |
|
113 |
|
114 |
public static void printArray(Object[] array) { |
115 |
for (int i = 0; i < array.length; i++) { |
116 |
Object object = array[i]; |
117 |
|
118 |
System.out.println("[" + i + "] = " + array[i]); |
119 |
} |
120 |
} |
121 |
|
122 |
/* (non-Javadoc) |
123 |
* @see junit.framework.TestCase#setUp() |
124 |
*/ |
125 |
protected void setUp() throws Exception { |
126 |
System.out.println("--- " + getName()); |
127 |
|
128 |
comparator = new TestComparator(); |
129 |
collection = new LazySortedCollection(comparator); |
130 |
// Ensure a predictable tree structure |
131 |
collection.enableRandomization = false; |
132 |
|
133 |
comparisonComparator = new TestComparator(); |
134 |
comparisonCollection = new TreeSet(comparisonComparator); |
135 |
|
136 |
addAll(elements); |
137 |
|
138 |
super.setUp(); |
139 |
} |
140 |
|
141 |
/* (non-Javadoc) |
142 |
* @see junit.framework.TestCase#tearDown() |
143 |
*/ |
144 |
protected void tearDown() throws Exception { |
145 |
System.out.println("Comparisons required by lazy collection: " + comparator.comparisons); |
146 |
System.out.println("Comparisons required by reference implementation: " + comparisonComparator.comparisons); |
147 |
System.out.println(""); |
148 |
|
149 |
super.tearDown(); |
150 |
} |
151 |
|
152 |
/** |
153 |
* Computes the entries that are expected to lie in the given range. The result |
154 |
* is sorted. |
155 |
* |
156 |
* @param start |
157 |
* @param length |
158 |
* @return |
159 |
* @since 3.1 |
160 |
*/ |
161 |
private Object[] computeExpectedElementsInRange(int start, int length) { |
162 |
int counter = 0; |
163 |
|
164 |
Iterator iter = comparisonCollection.iterator(); |
165 |
while(iter.hasNext() && counter < start) { |
166 |
iter.next(); |
167 |
counter++; |
168 |
} |
169 |
|
170 |
Object[] result = new Object[length]; |
171 |
for (int i = 0; i < result.length; i++) { |
172 |
result[i] = iter.next(); |
173 |
} |
174 |
|
175 |
return result; |
176 |
} |
177 |
|
178 |
private void addAll(Object[] elements) { |
179 |
collection.addAll(elements); |
180 |
comparisonCollection.addAll(Arrays.asList(elements)); |
181 |
} |
182 |
|
183 |
private void add(Object toAdd) { |
184 |
collection.add(toAdd); |
185 |
comparisonCollection.add(toAdd); |
186 |
} |
187 |
|
188 |
private void remove(Object toRemove) { |
189 |
collection.remove(toRemove); |
190 |
comparisonCollection.remove(toRemove); |
191 |
} |
192 |
|
193 |
private void removeRange(int start, int length) { |
194 |
collection.removeRange(start, length); |
195 |
|
196 |
Object[] expected = computeExpectedElementsInRange(start, length); |
197 |
|
198 |
// Alternative remove implementation that removes one-at-a-time |
199 |
for (int i = 0; i < expected.length; i++) { |
200 |
Object object = expected[i]; |
201 |
|
202 |
comparisonCollection.remove(expected[i]); |
203 |
} |
204 |
} |
205 |
|
206 |
private void clear() { |
207 |
collection.clear(); |
208 |
comparisonCollection.clear(); |
209 |
} |
210 |
|
211 |
/** |
212 |
* Force the collection to sort all elements immediately. |
213 |
* |
214 |
* @since 3.1 |
215 |
*/ |
216 |
private void forceFullSort() { |
217 |
queryRange(0, elements.length, true); |
218 |
} |
219 |
|
220 |
private void assertContentsValid() { |
221 |
queryRange(0, comparisonCollection.size(), false); |
222 |
Assert.assertEquals(comparisonCollection.size(), collection.size()); |
223 |
Assert.assertEquals(comparisonCollection.isEmpty(), collection.isEmpty()); |
224 |
} |
225 |
|
226 |
private void assertIsPermutation(Object[] array1, Object[] array2) { |
227 |
Object[] sorted1 = new Object[array1.length]; |
228 |
System.arraycopy(array1, 0, sorted1, 0, array1.length); |
229 |
Arrays.sort(sorted1, new TestComparator()); |
230 |
|
231 |
Object[] sorted2 = new Object[array2.length]; |
232 |
System.arraycopy(array2, 0, sorted2, 0, array2.length); |
233 |
Arrays.sort(sorted2, new TestComparator()); |
234 |
|
235 |
assertArrayEquals(sorted1, sorted2); |
236 |
} |
237 |
|
238 |
/** |
239 |
* Queries the collection for the given range, and throws an assertation failure if the |
240 |
* result was unexpected. Assumes that the "elements" array was initially added and that nothing |
241 |
* has been added or removed since. |
242 |
* |
243 |
* @param start |
244 |
* @param length |
245 |
* @param sorted |
246 |
* @since 3.1 |
247 |
*/ |
248 |
private Object[] queryRange(int start, int length, boolean sorted) { |
249 |
Object[] result = new Object[length]; |
250 |
|
251 |
int returnValue = collection.getRange(result, start, sorted); |
252 |
|
253 |
Assert.assertEquals(returnValue, length); |
254 |
|
255 |
Object[] expectedResult = computeExpectedElementsInRange(start, length); |
256 |
|
257 |
if (sorted) { |
258 |
// If the result is supposed to be sorted, it will match the expected |
259 |
// result exactly |
260 |
assertArrayEquals(expectedResult, result); |
261 |
} else { |
262 |
// Otherwise, the result merely needs to be a permutation of the |
263 |
// expected result. |
264 |
assertIsPermutation(result, expectedResult); |
265 |
} |
266 |
|
267 |
collection.testInvariants(); |
268 |
|
269 |
return result; |
270 |
} |
271 |
|
272 |
private void assertArrayEquals(Object[] array1, Object[] array2) { |
273 |
for (int i = 0; i < array1.length; i++) { |
274 |
|
275 |
Assert.assertEquals(array1[i], array2[i]); |
276 |
} |
277 |
} |
278 |
|
279 |
public void testComparisonCount() { |
280 |
Assert.assertTrue("additions should not require any comparisons", comparator.comparisons == 0); |
281 |
|
282 |
queryRange(0, elements.length, false); |
283 |
|
284 |
Assert.assertTrue("requesting the complete set of unsorted elements should not require any comparisons", comparator.comparisons == 0); |
285 |
} |
286 |
|
287 |
/** |
288 |
* Ensure that no comparisons are required for range queries once the collection is fully sorted |
289 |
* |
290 |
* @since 3.1 |
291 |
*/ |
292 |
public void testSortAll() { |
293 |
// Test that sorting the entire array works |
294 |
queryRange(0, elements.length, true); |
295 |
|
296 |
int comparisons = comparator.comparisons; |
297 |
|
298 |
// Ensure that subsequent operations require no comparisons |
299 |
queryRange(elements.length - 10, 10, true); |
300 |
queryRange(0, 10, false); |
301 |
|
302 |
Assert.assertEquals("Once the lazy collection is fully sorted, it should not require further comparisons", |
303 |
comparisons, comparator.comparisons); |
304 |
} |
305 |
|
306 |
/** |
307 |
* Tests LazySortedCollection.removeNode(int) when removing a leaf node |
308 |
*/ |
309 |
public void testRemoveLeafNode() { |
310 |
forceFullSort(); |
311 |
remove(se[9]); |
312 |
assertContentsValid(); |
313 |
} |
314 |
|
315 |
/** |
316 |
* Tests LazySortedCollection.removeNode(int) when removing a node with no left child |
317 |
*/ |
318 |
public void testRemoveNodeWithNoLeftChild() { |
319 |
forceFullSort(); |
320 |
remove(se[23]); |
321 |
assertContentsValid(); |
322 |
} |
323 |
|
324 |
/** |
325 |
* Tests LazySortedCollection.removeNode(int) when removing a node with no right child |
326 |
* |
327 |
* @since 3.1 |
328 |
*/ |
329 |
public void testRemoveNodeWithNoRightChild() { |
330 |
forceFullSort(); |
331 |
remove(se[13]); |
332 |
assertContentsValid(); |
333 |
} |
334 |
|
335 |
/** |
336 |
* Tests LazySortedCollection.remove when removing the root node |
337 |
* |
338 |
* @since 3.1 |
339 |
*/ |
340 |
public void testRemoveRootNode() { |
341 |
forceFullSort(); |
342 |
remove(se[19]); |
343 |
assertContentsValid(); |
344 |
} |
345 |
|
346 |
/** |
347 |
* Tests LazySortedCollection.remove when the removal |
348 |
* will require swapping with a non-leaf node. (The descendent with the closest value |
349 |
* in the largest subtree has at least 1 child). |
350 |
* |
351 |
* @since 3.1 |
352 |
*/ |
353 |
public void testRemoveWhereSwappedNodeIsntLeaf() { |
354 |
forceFullSort(); |
355 |
remove(se[14]); |
356 |
assertContentsValid(); |
357 |
} |
358 |
|
359 |
/** |
360 |
* Tests LazySortedCollection.remove when the removal |
361 |
* will require swapping with a non-leaf node, and both the removed node and the swapped |
362 |
* node contain unsorted children. |
363 |
* |
364 |
* @since 3.1 |
365 |
*/ |
366 |
public void testRemoveWithUnsortedSwap() { |
367 |
// Ensure that we've sorted nodes 13 and 14 |
368 |
queryRange(14, 1, true); |
369 |
queryRange(13, 1, true); |
370 |
|
371 |
// Add some unsorted nodes that will become children of the node with value "v13 mongoose" |
372 |
addAll(new String[] {"v13 n", "v13 l"}); |
373 |
// Ensure that the new nodes are pushed down to node 14 by querying its parent (currently at position 8) |
374 |
queryRange(8, 1, true); |
375 |
|
376 |
// Add some unsorted nodes that will become children of the node with value "v14 noodle" |
377 |
addAll(new String[] {"v14 m", "v14 o"}); |
378 |
// Push down the unsorted nodes by querying for the parent of "v14 noodle" |
379 |
// (the parent is currently at position 7) |
380 |
queryRange(7, 1, true); |
381 |
|
382 |
// Now remove node with value "v14 noodle" -- this should swap it with the node "v13 mongoose", requiring |
383 |
// both sets of unsorted children to be dealt with |
384 |
|
385 |
remove(se[14]); |
386 |
assertContentsValid(); |
387 |
} |
388 |
|
389 |
/** |
390 |
* Remove an element from an initially unsorted collection |
391 |
* |
392 |
* @since 3.1 |
393 |
*/ |
394 |
public void testRemoveFromUnsorted() { |
395 |
remove(se[10]); |
396 |
assertContentsValid(); |
397 |
} |
398 |
|
399 |
/** |
400 |
* Remove the root from an initially-unsorted collection |
401 |
* |
402 |
* @since 3.1 |
403 |
*/ |
404 |
public void testRemoveRootFromUnsorted() { |
405 |
remove(se[19]); |
406 |
assertContentsValid(); |
407 |
} |
408 |
|
409 |
/** |
410 |
* Ensure that removing an element that isn't in the collection is a no-op |
411 |
* |
412 |
* @since 3.1 |
413 |
*/ |
414 |
public void testRemoveUnknown() { |
415 |
remove("some unknown element"); |
416 |
assertContentsValid(); |
417 |
} |
418 |
|
419 |
/** |
420 |
* Tests that the swaps during removal don't mess up the internal hashmap. |
421 |
* Perform a removal that will require a swap, add a new item, then |
422 |
* remove the item that was previously swapped. If the hashmap was not updated, |
423 |
* then the removed item may still be pointing to its old index and the |
424 |
* new item will be removed instead. |
425 |
* |
426 |
* @since 3.1 |
427 |
*/ |
428 |
public void testRemovePreviouslySwappedNode() { |
429 |
queryRange(0, elements.length, true); |
430 |
remove(se[14]); |
431 |
// Add a new item -- should reuse the same index used by the previous item |
432 |
add("something new"); |
433 |
assertContentsValid(); |
434 |
remove(se[13]); |
435 |
assertContentsValid(); |
436 |
} |
437 |
|
438 |
/** |
439 |
* Remove all nodes using removeRange |
440 |
* |
441 |
* @since 3.1 |
442 |
*/ |
443 |
public void testRemoveFullRange() { |
444 |
removeRange(0, se.length); |
445 |
assertContentsValid(); |
446 |
} |
447 |
|
448 |
/** |
449 |
* Remove a range that includes the start |
450 |
* |
451 |
* @since 3.1 |
452 |
*/ |
453 |
public void testRemoveFromStart() { |
454 |
removeRange(0, se.length / 2); |
455 |
assertContentsValid(); |
456 |
} |
457 |
|
458 |
/** |
459 |
* Remove a range that includes the last node |
460 |
* |
461 |
* @since 3.1 |
462 |
*/ |
463 |
public void testRemoveFromEnd() { |
464 |
int start = se.length / 2; |
465 |
removeRange(start, se.length - start); |
466 |
assertContentsValid(); |
467 |
} |
468 |
|
469 |
/** |
470 |
* Remove a range that includes the root, but leaves nodes in both subtrees intact. |
471 |
* |
472 |
* @since 3.1 |
473 |
*/ |
474 |
public void testRemoveIncludingRoot() { |
475 |
removeRange(14, 6); |
476 |
assertContentsValid(); |
477 |
} |
478 |
|
479 |
/** |
480 |
* Test boundary conditions: |
481 |
* |
482 |
* Tests moving an entire right subtree, and a left subtree including the tree itself |
483 |
*/ |
484 |
public void testRemoveRightSubtree() { |
485 |
int start = 20; |
486 |
removeRange(9, 5); |
487 |
assertContentsValid(); |
488 |
} |
489 |
|
490 |
/** |
491 |
* Test boundary conditions: Tests moving an entire left subtree |
492 |
*/ |
493 |
public void testRemoveLeftSubtree() { |
494 |
removeRange(3, 4); |
495 |
assertContentsValid(); |
496 |
} |
497 |
|
498 |
/** |
499 |
* Test boundary conditions: Tests moving an entire left subtree including the tree itself |
500 |
*/ |
501 |
public void testRemoveRightIncludingRoot() { |
502 |
removeRange(3, 5); |
503 |
assertContentsValid(); |
504 |
} |
505 |
|
506 |
public void testClear() { |
507 |
clear(); |
508 |
assertContentsValid(); |
509 |
} |
510 |
|
511 |
public void testClearSorted() { |
512 |
forceFullSort(); |
513 |
clear(); |
514 |
assertContentsValid(); |
515 |
} |
516 |
|
517 |
// |
518 |
// |
519 |
// public static void testAdditions() { |
520 |
// TestComparator comparator = new TestComparator(); |
521 |
// LazySortedCollection collection = new LazySortedCollection(comparator); |
522 |
// |
523 |
// addSomeElements(collection); |
524 |
// |
525 |
// System.out.println("comparisons after add = " + comparator.comparisons); |
526 |
// comparator.comparisons = 0; |
527 |
// |
528 |
// // Getfirst10Elements |
529 |
// Object[] first10Elements = new Object[10]; |
530 |
// collection.getFirst(first10Elements, false); |
531 |
// System.out.println("first 10 elements:"); |
532 |
// printArray(first10Elements); |
533 |
// System.out.println("comparisons after getFirst = " + comparator.comparisons); |
534 |
// comparator.comparisons = 0; |
535 |
// |
536 |
// collection.print(); |
537 |
// |
538 |
// // remove the 10th element |
539 |
// collection.remove(first10Elements[9]); |
540 |
// |
541 |
// collection.print(); |
542 |
// |
543 |
//// |
544 |
//// collection.getFirst(first10Elements, true); |
545 |
//// System.out.println("first 10 elements (sorted):"); |
546 |
//// printArray(first10Elements); |
547 |
//// System.out.println("comparisons after getFirst = " + comparator.comparisons); |
548 |
//// comparator.comparisons = 0; |
549 |
//// |
550 |
//// |
551 |
//// |
552 |
//// // get elements 8-13 |
553 |
//// Object[] eightThrough14 = new Object[7]; |
554 |
//// collection.getRange(eightThrough14, 8, false); |
555 |
//// System.out.println("elements 8-14:"); |
556 |
//// printArray(eightThrough14); |
557 |
//// System.out.println("comparisons after 8-14 query = " + comparator.comparisons); |
558 |
//// comparator.comparisons = 0; |
559 |
// |
560 |
// collection.print(); |
561 |
// } |
562 |
} |