1 /*
2 * Copyright (c) 2010, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package test.javafx.collections;
27
28 import com.sun.javafx.collections.NonIterableChange.SimplePermutationChange;
29 import com.sun.javafx.collections.ObservableListWrapper;
30 import java.util.ArrayList;
31 import java.util.HashMap;
32 import java.util.List;
33 import java.util.Collections;
34 import java.util.Arrays;
35 import java.util.Comparator;
36 import java.util.Map;
37
38 import javafx.beans.Observable;
39 import javafx.beans.property.SimpleObjectProperty;
40 import javafx.collections.FXCollections;
41 import javafx.collections.ListChangeListener;
42 import javafx.collections.ObservableList;
43 import javafx.collections.ObservableListWrapperShim;
44 import javafx.collections.transformation.FilteredList;
45 import javafx.collections.transformation.SortedList;
46 import org.junit.Before;
47 import org.junit.Test;
48 import static org.junit.Assert.* ;
49 import static org.junit.Assert.assertEquals;
50
51 public class SortedListTest {
52
53 private ObservableList<String> list;
54 private MockListObserver<String> mockListObserver;
55 private SortedList<String> sortedList;
56
57 @Before
58 public void setUp() {
59 list = FXCollections.observableArrayList();
60 list.addAll("a", "c", "d", "c");
61 sortedList = list.sorted();
62 mockListObserver = new MockListObserver<String>();
63 sortedList.addListener(mockListObserver);
64 }
65
66 @Test
67 public void testNoChange() {
68 assertEquals(Arrays.asList("a", "c", "c", "d"), sortedList);
69 mockListObserver.check0();
70
71 compareIndices();
72 }
73
74 @Test
75 public void testAdd() {
76 list.clear();
77 mockListObserver.clear();
78 assertEquals(Collections.emptyList(), sortedList);
79 list.addAll("a", "c", "d", "c");
80 assertEquals(Arrays.asList("a", "c", "c", "d"), sortedList);
81 mockListObserver.check1AddRemove(sortedList, Collections.<String>emptyList(), 0, 4);
82 assertEquals(0, sortedList.getSourceIndex(0));
83 assertEquals(2, sortedList.getSourceIndex(3));
84
85 compareIndices();
86 }
87
88 //TODO: replace with sorted.getViewIndex when JDK-8139848 is fixed
89 private <E> int getViewIndex(SortedList<E> sorted, int sourceIndex) {
90 for (int i = 0; i < sorted.size(); i++) {
91 if (sourceIndex == sorted.getSourceIndex(i)) {
92 return i;
93 }
94 }
95 return -1;
96 }
97
98 private <E> void compareIndices(SortedList<E> sorted) {
99 ObservableList<? extends E> source = sorted.getSource();
100 for (int i = 0; i < sorted.size(); i++) {
101 // i as a view index
102 int sourceIndex = sorted.getSourceIndex(i);
103 assertEquals(i, getViewIndex(sorted, sourceIndex));
104 assertSame(sorted.get(i), source.get(sourceIndex));
105
106 // i as a source index
107 int viewIndex = getViewIndex(sorted, i);
108 assertEquals(i, sorted.getSourceIndex(viewIndex));
109 assertSame(source.get(i), sorted.get(viewIndex));
110 }
111 }
112
113 private void compareIndices() {
114 compareIndices(sortedList);
115 }
116
117 @Test
118 public void testAddSingle() {
119 list.add("b");
120 assertEquals(Arrays.asList("a", "b", "c", "c", "d"), sortedList);
121 mockListObserver.check1AddRemove(sortedList, Collections.<String>emptyList(), 1, 2);
122 assertEquals(0, sortedList.getSourceIndex(0));
123 assertEquals(4, sortedList.getSourceIndex(1));
124 assertEquals(1, sortedList.getSourceIndex(2));
125 assertEquals(3, sortedList.getSourceIndex(3));
126 assertEquals(2, sortedList.getSourceIndex(4));
127
128 compareIndices();
129 }
130
131 @Test
132 public void testRemove() {
133 list.removeAll(Arrays.asList("c")); // removes "c", "d", "c", adds "d"
134 assertEquals(Arrays.asList("a", "d"), sortedList);
135 mockListObserver.check1AddRemove(sortedList, Arrays.asList("c", "c"), 1, 1);
136 assertEquals(0, sortedList.getSourceIndex(0));
137 assertEquals(1, sortedList.getSourceIndex(1));
138 mockListObserver.clear();
139 list.removeAll(Arrays.asList("a", "d"));
140 mockListObserver.check1AddRemove(sortedList, Arrays.asList("a", "d"), 0, 0);
141
142 compareIndices();
143 }
144
145 @Test
146 public void testRemoveSingle() {
147 list.remove("a");
148 assertEquals(Arrays.asList("c", "c", "d"), sortedList);
149 mockListObserver.check1AddRemove(sortedList, Arrays.asList("a"), 0, 0);
150 assertEquals(0, sortedList.getSourceIndex(0));
151 assertEquals(2, sortedList.getSourceIndex(1));
152 assertEquals(1, sortedList.getSourceIndex(2));
153
154 compareIndices();
155 }
156
157 @Test
158 public void testMultipleOperations() {
159 list.remove(2);
160 assertEquals(Arrays.asList("a", "c", "c"), sortedList);
161 mockListObserver.check1AddRemove(sortedList, Arrays.asList("d"), 3, 3);
162 mockListObserver.clear();
163 list.add("b");
164 assertEquals(Arrays.asList("a", "b", "c", "c"), sortedList);
165 mockListObserver.check1AddRemove(sortedList, Collections.<String>emptyList(), 1, 2);
166
167 compareIndices();
168 }
169
170 @Test
171 public void testPureRemove() {
172 list.removeAll(Arrays.asList("c", "d"));
173 mockListObserver.check1AddRemove(sortedList, Arrays.asList("c", "c", "d"), 1, 1);
174 assertEquals(0, sortedList.getSourceIndex(0));
175
176 compareIndices();
177 }
178
179 @Test
180 public void testChangeComparator() {
181 SimpleObjectProperty<Comparator<String>> op =
182 new SimpleObjectProperty<>(Comparator.naturalOrder());
183
184 sortedList = new SortedList<>(list);
185 assertEquals(Arrays.asList("a", "c", "d", "c"), sortedList);
186 compareIndices();
187
188 sortedList.comparatorProperty().bind(op);
189 assertEquals(Arrays.asList("a", "c", "c", "d"), sortedList);
190 compareIndices();
191
192 sortedList.addListener(mockListObserver);
193
194 op.set((Comparator<String>) (String o1, String o2) -> -o1.compareTo(o2));
195 assertEquals(Arrays.asList("d", "c", "c", "a"), sortedList);
196 mockListObserver.check1Permutation(sortedList, new int[] {3, 1, 2, 0}); // could be also 3, 2, 1, 0, but the algorithm goes this way
197 compareIndices();
198
199 mockListObserver.clear();
200 op.set(null);
201 assertEquals(Arrays.asList("a", "c", "d", "c"), sortedList);
202 mockListObserver.check1Permutation(sortedList, new int[] {2, 1, 3, 0});
203 compareIndices();
204 }
205
206
207 /**
208 * A slightly updated test provided by "Kleopatra" (http://javafx-jira.kenai.com/browse/RT-14400)
209 */
210 @Test
211 public void testSourceIndex() {
212 final ObservableList<Double> sourceList = FXCollections.observableArrayList(
213 1300., 400., 600.
214 );
215 // the list to be removed again, note that its highest value is greater
216 // then the highest in the base list before adding
217 List<Double> other = Arrays.asList(
218 50., -300., 4000.
219 );
220 sourceList.addAll(other);
221 // wrap into a sorted list and add a listener to the sorted
222 final SortedList<Double> sorted = sourceList.sorted();
223 ListChangeListener<Double> listener = c -> {
224 assertEquals(Arrays.<Double>asList(400.0, 600.0, 1300.0), c.getList());
225
226 c.next();
227 assertEquals(Arrays.<Double>asList(-300.0, 50.0), c.getRemoved());
228 assertEquals(0, c.getFrom());
229 assertEquals(0, c.getTo());
230 assertTrue(c.next());
231 assertEquals(Arrays.<Double>asList(4000.), c.getRemoved());
232 assertEquals(3, c.getFrom());
233 assertEquals(3, c.getTo());
234 assertFalse(c.next());
235
236
237 // grab sourceIndex of last (aka: highest) value in sorted list
238 int sourceIndex = sorted.getSourceIndex(sorted.size() - 1);
239 assertEquals(0, sourceIndex);
240 };
241 sorted.addListener(listener);
242 sourceList.removeAll(other);
243
244 compareIndices(sorted);
245 }
246
247 @Test
248 public void testMutableElement() {
249 ObservableList<Person> list = createPersonsList();
250
251 SortedList<Person> sorted = list.sorted();
252 assertEquals(Arrays.asList(
253 new Person("five"), new Person("four"), new Person("one"),
254 new Person("three"), new Person("two")),
255 sorted);
256 MockListObserver<Person> listener = new MockListObserver<>();
257 sorted.addListener(listener);
258 list.get(3).name.set("zero"); // four -> zero
259 ObservableList<Person> expected = FXCollections.observableArrayList(
260 new Person("five"), new Person("one"), new Person("three"),
261 new Person("two"), new Person("zero"));
262 listener.checkPermutation(0, expected, 0, list.size(), new int[]{0, 4, 1, 2, 3});
263 listener.checkUpdate(1, expected, 4, 5);
264 assertEquals(expected, sorted);
265
266 compareIndices(sorted);
267 }
268
269 @Test
270 public void testMutableElementUnsorted_rt39541() {
271 ObservableList<Person> list = createPersonsList();
272 SortedList<Person> unsorted = new SortedList<>(list);
273 MockListObserver<Person> listener = new MockListObserver<>();
274 unsorted.addListener(listener);
275 list.get(3).name.set("zero"); // four -> zero
276 ObservableList<Person> expected = FXCollections.observableArrayList(
277 new Person("one"), new Person("two"), new Person("three"),
278 new Person("zero"), new Person("five"));
279 listener.check1Update(expected, 3, 4);
280
281 compareIndices(unsorted);
282 }
283
284 @Test
285 public void testMutableElementUnsortedChain_rt39541() {
286 ObservableList<Person> items = createPersonsList();
287
288 SortedList<Person> sorted = items.sorted();
289 SortedList<Person> unsorted = new SortedList<>(sorted);
290
291 assertEquals(sorted, unsorted);
292
293 MockListObserver<Person> listener = new MockListObserver<>();
294 unsorted.addListener(listener);
295 items.get(3).name.set("zero"); // "four" -> "zero"
296 ObservableList<Person> expected = FXCollections.observableArrayList(
297 new Person("five"), new Person("one"), new Person("three"),
298 new Person("two"), new Person("zero"));
299 listener.checkPermutation(0, expected, 0, expected.size(), new int[] {0, 4, 1, 2, 3});
300 listener.checkUpdate(1, expected, 4, 5);
301 assertEquals(expected, sorted);
302 assertEquals(expected, unsorted);
303
304 compareIndices(sorted);
305 compareIndices(unsorted);
306 }
307
308 @Test
309 public void testMutableElementSortedFilteredChain() {
310 ObservableList<Person> items = FXCollections.observableArrayList(
311 (Person p) -> new Observable[]{p.name});
312 items.addAll(
313 new Person("b"), new Person("c"), new Person("a"),
314 new Person("f"), new Person("e"), new Person("d"));
315
316 FilteredList<Person> filtered = items.filtered(e -> !e.name.get().startsWith("z"));
317 MockListObserver<Person> filterListener = new MockListObserver<>();
318 filtered.addListener(filterListener);
319
320 SortedList<Person> sorted = filtered.sorted((x, y) -> x.name.get().compareTo(y.name.get()));
321 MockListObserver<Person> sortListener = new MockListObserver<>();
322 sorted.addListener(sortListener);
323 items.get(2).name.set("z"); // "a" -> "z"
324 filterListener.check1AddRemove(filtered, Arrays.asList(new Person("z")), 2, 2);
325 sortListener.check1AddRemove(sorted, Arrays.asList(new Person("z")), 0, 0);
326 ObservableList<Person> expected = FXCollections.observableArrayList(
327 new Person("b"), new Person("c"), new Person("d"),
328 new Person("e"), new Person("f"));
329 assertEquals(expected, sorted);
330
331 compareIndices(sorted);
332 }
333
334 private ObservableList<Person> createPersonsList() {
335 ObservableList<Person> list = FXCollections.observableArrayList(
336 (Person p) -> new Observable[]{p.name});
337 list.addAll(
338 new Person("one"), new Person("two"), new Person("three"),
339 new Person("four"), new Person("five"));
340 return list;
341 }
342
343 @Test
344 public void testNotComparable() {
345 final Object o1 = new Object() {
346
347 @Override
348 public String toString() {
349 return "c";
350 }
351 };
352 final Object o2 = new Object() {
353
354 @Override
355 public String toString() {
356 return "a";
357 }
358 };
359 final Object o3 = new Object() {
360
361 @Override
362 public String toString() {
363 return "d";
364 }
365 };
366 ObservableList<Object> list = FXCollections.observableArrayList(o1, o2, o3);
367
368 SortedList<Object> sorted = list.sorted();
369 assertEquals(Arrays.asList(o2, o1, o3), sorted);
370
371 compareIndices(sorted);
372 }
373
374 @Test
375 public void testCompareNulls() {
376 ObservableList<String> list = FXCollections.observableArrayList( "g", "a", null, "z");
377
378 SortedList<String> sorted = list.sorted();
379 assertEquals(Arrays.asList(null, "a", "g", "z"), sorted);
380
381 compareIndices(sorted);
382 }
383
384
385 private static class Permutator<E> extends ObservableListWrapper<E> {
386 private List<E> backingList;
387 public Permutator(List<E> list) {
388 super(list);
389 this.backingList = list;
390 }
391
392 public void swap() {
393 E first = get(0);
394 backingList.set(0, get(size() - 1));
395 backingList.set(size() -1, first);
396 ObservableListWrapperShim.fireChange(this,
397 new SimplePermutationChange(0, size(), new int[] {2, 1, 0}, this));
398 }
399
400 }
401 /**
402 * SortedList cant cope with permutations.
403 */
404 @Test
405 public void testPermutate() {
406 List<Integer> list = new ArrayList<Integer>();
407 for (int i = 0; i < 3; i++) {
408 list.add(i);
409 }
410 Permutator<Integer> permutator = new Permutator<Integer>(list);
411 SortedList<Integer> sorted = new SortedList<Integer>(permutator);
412 permutator.swap();
413
414 compareIndices(sorted);
415 }
416
417 @Test
418 public void testUnsorted() {
419 SortedList<String> sorted = new SortedList<>(list);
420 assertEquals(sorted, list);
421 assertEquals(list, sorted);
422
423 list.removeAll("a", "d");
424
425 assertEquals(sorted, list);
426
427 list.addAll(0, Arrays.asList("a", "b", "c"));
428
429 assertEquals(sorted, list);
430
431 FXCollections.sort(list);
432
433 assertEquals(sorted, list);
434
435 compareIndices(sorted);
436 }
437
438 @Test
439 public void testUnsorted2() {
440 list.setAll("a", "b", "c", "d", "e", "f");
441 SortedList<String> sorted = new SortedList<>(list);
442 assertEquals(sorted, list);
443
444 list.removeAll("b", "c", "d");
445
446 assertEquals(sorted, list);
447
448 compareIndices(sorted);
449 }
450
451 @Test
452 public void testSortedNaturalOrder() {
453 assertEquals(Arrays.asList("a", "c", "c", "d"), list.sorted());
454 }
455
456 @Test
457 public void testRemoveFromDuplicates() {
458 String toRemove = new String("A");
459 String other = new String("A");
460 list = FXCollections.observableArrayList(other, toRemove);
461 Comparator<String> c = Comparator.naturalOrder();
462 SortedList<String> sorted = list.sorted(c);
463
464 list.remove(1);
465
466 assertEquals(1, sorted.size());
467 assertTrue(sorted.get(0) == other);
468
469 compareIndices(sorted);
470 }
471
472 @Test
473 public void testAddAllOnEmpty() {
474 list = FXCollections.observableArrayList();
475 SortedList<String> sl = list.sorted(String.CASE_INSENSITIVE_ORDER);
476 list.addAll("B", "A");
477
478 assertEquals(Arrays.asList("A", "B"), sl);
479
480 compareIndices(sl);
481 }
482
483 @Test
484 public void test_rt36353_sortedList() {
485 ObservableList<String> data = FXCollections.observableArrayList("2", "1", "3");
486 SortedList<String> sortedList = new SortedList<String>(data);
487
488 HashMap<Integer, Integer> pMap = new HashMap<>();
489 sortedList.addListener((ListChangeListener<String>) c -> {
490 while (c.next()) {
491 if (c.wasPermutated()) {
492 for (int i = c.getFrom(); i < c.getTo(); i++) {
493 pMap.put(i, c.getPermutation(i));
494 }
495 }
496 }
497 });
498
499 Map<Integer, Integer> expected = new HashMap<>();
500
501 // comparator that will create list of [1,2,3]. Sort indices based on
502 // previous order [2,1,3].
503 sortedList.setComparator((s1,s2) -> s1.compareTo(s2));
504 assertEquals(FXCollections.observableArrayList("1","2","3"), sortedList);
505 expected.put(0, 1); // item "2" has moved from index 0 to index 1
506 expected.put(1, 0); // item "1" has moved from index 1 to index 0
507 expected.put(2, 2); // item "3" has remained in index 2
508 assertEquals(expected, pMap);
509 compareIndices(sortedList);
510
511 // comparator that will create list of [3,2,1]. Sort indices based on
512 // previous order [1,2,3].
513 sortedList.setComparator((s1,s2) -> s2.compareTo(s1));
514 assertEquals(FXCollections.observableArrayList("3","2","1"), sortedList);
515 expected.clear();
516 expected.put(0, 2); // item "1" has moved from index 0 to index 2
517 expected.put(1, 1); // item "2" has remained in index 1
518 expected.put(2, 0); // item "3" has moved from index 2 to index 0
519 assertEquals(expected, pMap);
520 compareIndices(sortedList);
521
522 // null comparator so sort order should return to [2,1,3]. Sort indices based on
523 // previous order [3,2,1].
524 sortedList.setComparator(null);
525 assertEquals(FXCollections.observableArrayList("2","1","3"), sortedList);
526 expected.clear();
527 expected.put(0, 2); // item "3" has moved from index 0 to index 2
528 expected.put(1, 0); // item "2" has moved from index 1 to index 0
529 expected.put(2, 1); // item "1" has moved from index 2 to index 1
530 assertEquals(expected, pMap);
531 compareIndices(sortedList);
532 }
533
534 @Test
535 public void testAddWhenUnsorted() {
536 sortedList.setComparator(null);
537 mockListObserver.clear();
538 list.add(2, "b");
539 assertEquals(5, sortedList.size());
540 assertEquals(Arrays.asList("a", "c", "b", "d", "c"), sortedList);
541 mockListObserver.check1AddRemove(sortedList, Collections.emptyList(), 2, 3);
542 compareIndices();
543
544 mockListObserver.clear();
545 sortedList.setComparator(Comparator.<String>naturalOrder());
546 mockListObserver.check1Permutation(sortedList, new int[] {0, 2, 1, 4, 3});
547 assertEquals(5, sortedList.size());
548 assertEquals(Arrays.asList("a", "b", "c", "c", "d"), sortedList);
549 compareIndices();
550
551 mockListObserver.clear();
552 sortedList.setComparator(null);
553 assertEquals(5, sortedList.size());
554 assertEquals(Arrays.asList("a", "c", "b", "d", "c"), sortedList);
555 mockListObserver.check1Permutation(sortedList, new int[] {0, 2, 1, 4, 3});
556 compareIndices();
557 }
558
559 @Test
560 public void testRemoveWhenUnsorted() {
561 sortedList.setComparator(null);
562 mockListObserver.clear();
563 list.remove(1);
564 assertEquals(3, sortedList.size());
565 assertEquals(Arrays.asList("a", "d", "c"), sortedList);
566 mockListObserver.check1AddRemove(sortedList, Arrays.asList("c"), 1, 1);
567 compareIndices();
568
569 mockListObserver.clear();
570 sortedList.setComparator(Comparator.<String>naturalOrder());
571 mockListObserver.check1Permutation(sortedList, new int[] {0, 2, 1});
572 assertEquals(3, sortedList.size());
573 assertEquals(Arrays.asList("a", "c", "d"), sortedList);
574 compareIndices();
575
576 mockListObserver.clear();
577 sortedList.setComparator(null);
578 assertEquals(3, sortedList.size());
579 assertEquals(Arrays.asList("a", "d", "c"), sortedList);
580 mockListObserver.check1Permutation(sortedList, new int[] {0, 2, 1});
581 compareIndices();
582 }
583
584 @Test
585 public void testSetWhenUnsorted() {
586 sortedList.setComparator(null);
587 mockListObserver.clear();
588 list.set(1, "e");
589 assertEquals(4, sortedList.size());
590 assertEquals(Arrays.asList("a", "e", "d", "c"), sortedList);
591 mockListObserver.check1AddRemove(sortedList, Arrays.asList("c"), 1, 2);
592 compareIndices();
593
594 mockListObserver.clear();
595 sortedList.setComparator(Comparator.<String>naturalOrder());
596 mockListObserver.check1Permutation(sortedList, new int[] {0, 3, 2, 1});
597 assertEquals(4, sortedList.size());
598 assertEquals(Arrays.asList("a", "c", "d", "e"), sortedList);
599 compareIndices();
600
601 mockListObserver.clear();
602 sortedList.setComparator(null);
603 assertEquals(4, sortedList.size());
604 assertEquals(Arrays.asList("a", "e", "d", "c"), sortedList);
605 mockListObserver.check1Permutation(sortedList, new int[] {0, 3, 2, 1});
606 compareIndices();
607 }
608 }