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 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.transformation.SortedList;
  41 import javafx.collections.transformation.TransformationList;
  42 import org.junit.Before;
  43 import org.junit.Test;
  44 import static org.junit.Assert.* ;
  45 import static org.junit.Assert.assertEquals;
  46 
  47 /**
  48  *
  49  */
  50 public class SortedListTest {
  51 
  52     private ObservableList<String> list;
  53     private MockListObserver<String> mockListObserver;
  54     private SortedList<String> sortedList;
  55 
  56     @Before
  57     public void setUp() {
  58         list = FXCollections.observableArrayList();
  59         list.addAll("a", "c", "d", "c");
  60         sortedList = list.sorted();
  61         mockListObserver = new MockListObserver<String>();
  62         sortedList.addListener(mockListObserver);
  63     }
  64     @Test
  65     public void testNoChange() {
  66         assertEquals(Arrays.asList("a", "c", "c", "d"), sortedList);
  67         mockListObserver.check0();
  68     }
  69 
  70     @Test
  71     public void testAdd() {
  72         list.clear();
  73         mockListObserver.clear();
  74         assertEquals(Collections.emptyList(), sortedList);
  75         list.addAll("a", "c", "d", "c");
  76         assertEquals(Arrays.asList("a", "c", "c", "d"), sortedList);
  77         mockListObserver.check1AddRemove(sortedList, Collections.<String>emptyList(), 0, 4);
  78         assertEquals(0, sortedList.getSourceIndex(0));
  79         assertEquals(2, sortedList.getSourceIndex(3));
  80     }
  81 
  82     @Test
  83     public void testAddSingle() {
  84         list.add("b");
  85         assertEquals(Arrays.asList("a", "b", "c", "c", "d"), sortedList);
  86         mockListObserver.check1AddRemove(sortedList, Collections.<String>emptyList(), 1, 2);
  87         assertEquals(0, sortedList.getSourceIndex(0));
  88         assertEquals(4, sortedList.getSourceIndex(1));
  89         assertEquals(1, sortedList.getSourceIndex(2));
  90         assertEquals(3, sortedList.getSourceIndex(3));
  91         assertEquals(2, sortedList.getSourceIndex(4));
  92     }
  93 
  94     @Test
  95     public void testRemove() {
  96         list.removeAll(Arrays.asList("c")); // removes "c", "d", "c", adds "d"
  97         assertEquals(Arrays.asList("a", "d"), sortedList);
  98         mockListObserver.check1AddRemove(sortedList, Arrays.asList("c", "c"), 1, 1);
  99         assertEquals(0, sortedList.getSourceIndex(0));
 100         assertEquals(1, sortedList.getSourceIndex(1));
 101         mockListObserver.clear();
 102         list.removeAll(Arrays.asList("a", "d"));
 103         mockListObserver.check1AddRemove(sortedList, Arrays.asList("a", "d"), 0, 0);
 104     }
 105 
 106     @Test
 107     public void testRemoveSingle() {
 108         list.remove("a");
 109         assertEquals(Arrays.asList("c", "c", "d"), sortedList);
 110         mockListObserver.check1AddRemove(sortedList, Arrays.asList("a"), 0, 0);
 111         assertEquals(0, sortedList.getSourceIndex(0));
 112         assertEquals(2, sortedList.getSourceIndex(1));
 113         assertEquals(1, sortedList.getSourceIndex(2));
 114     }
 115 
 116     @Test
 117     public void testMultipleOperations() {
 118         list.remove(2);
 119         assertEquals(Arrays.asList("a", "c", "c"), sortedList);
 120         mockListObserver.check1AddRemove(sortedList, Arrays.asList("d"), 3, 3);
 121         mockListObserver.clear();
 122         list.add("b");
 123         assertEquals(Arrays.asList("a", "b", "c", "c"), sortedList);
 124         mockListObserver.check1AddRemove(sortedList, Collections.<String>emptyList(), 1, 2);
 125     }
 126 
 127     @Test
 128     public void testPureRemove() {
 129         list.removeAll(Arrays.asList("c", "d"));
 130         mockListObserver.check1AddRemove(sortedList, Arrays.asList("c", "c", "d"), 1, 1);
 131         assertEquals(0, sortedList.getSourceIndex(0));
 132     }
 133 
 134     @Test
 135     public void testChangeComparator() {
 136         SimpleObjectProperty<Comparator<String>> op =
 137                 new SimpleObjectProperty<>(Comparator.naturalOrder());
 138 
 139         sortedList = new SortedList<>(list);
 140         assertEquals(Arrays.asList("a", "c", "d", "c"), sortedList);
 141         sortedList.comparatorProperty().bind(op);
 142         assertEquals(Arrays.asList("a", "c", "c", "d"), sortedList);
 143         sortedList.addListener(mockListObserver);
 144 
 145         op.set((Comparator<String>) (String o1, String o2) -> -o1.compareTo(o2));
 146         assertEquals(Arrays.asList("d", "c", "c", "a"), sortedList);
 147         mockListObserver.check1Permutation(sortedList, new int[] {3, 1, 2, 0}); // could be also 3, 2, 1, 0, but the algorithm goes this way
 148     }
 149 
 150 
 151    /**
 152      * A slightly updated test provided by "Kleopatra" (http://javafx-jira.kenai.com/browse/RT-14400)
 153      */
 154     @Test
 155     public void testSourceIndex() {
 156         final ObservableList<Double> sourceList = FXCollections.observableArrayList(
 157                 1300., 400., 600.
 158               );
 159         // the list to be removed again, note that its highest value is greater
 160         // then the highest in the base list before adding
 161       List<Double> other = Arrays.asList(
 162               50., -300., 4000.
 163       );
 164       sourceList.addAll(other);
 165       // wrap into a sorted list and add a listener to the sorted
 166       final SortedList<Double> sorted = sourceList.sorted();
 167       ListChangeListener<Double> listener = c -> {
 168           assertEquals(Arrays.<Double>asList(400.0, 600.0, 1300.0), c.getList());
 169 
 170           c.next();
 171           assertEquals(Arrays.<Double>asList(-300.0, 50.0), c.getRemoved());
 172           assertEquals(0, c.getFrom());
 173           assertEquals(0, c.getTo());
 174           assertTrue(c.next());
 175           assertEquals(Arrays.<Double>asList(4000.), c.getRemoved());
 176           assertEquals(3, c.getFrom());
 177           assertEquals(3, c.getTo());
 178           assertFalse(c.next());
 179 
 180 
 181           // grab sourceIndex of last (aka: highest) value in sorted list
 182           int sourceIndex = sorted.getSourceIndex(sorted.size() - 1);
 183           assertEquals(0, sourceIndex);
 184       };
 185       sorted.addListener(listener);
 186       sourceList.removeAll(other);
 187     }
 188 
 189     @Test
 190     public void testMutableElement() {
 191         ObservableList<Person> list = createPersonsList();
 192 
 193         SortedList<Person> sorted = list.sorted();
 194         assertEquals(Arrays.asList(
 195                 new Person("five"), new Person("four"), new Person("one"),
 196                 new Person("three"), new Person("two")),
 197                 sorted);
 198         MockListObserver<Person> listener = new MockListObserver<>();
 199         sorted.addListener(listener);
 200         list.get(3).name.set("zero"); // four -> zero
 201         ObservableList<Person> expected = FXCollections.observableArrayList(
 202                 new Person("five"), new Person("one"), new Person("three"),
 203                 new Person("two"), new Person("zero"));
 204         listener.checkPermutation(0, expected, 0, list.size(), new int[]{0, 4, 1, 2, 3});
 205         listener.checkUpdate(1, expected, 4, 5);
 206         assertEquals(expected, sorted);
 207     }
 208 
 209     @Test
 210     public void testMutableElementUnsorted_rt39541() {
 211         ObservableList<Person> list = createPersonsList();
 212         SortedList<Person> unsorted = new SortedList<>(list);
 213         MockListObserver<Person> listener = new MockListObserver<>();
 214         unsorted.addListener(listener);
 215         list.get(3).name.set("zero"); // four -> zero
 216         ObservableList<Person> expected = FXCollections.observableArrayList(
 217                 new Person("one"), new Person("two"), new Person("three"),
 218                 new Person("zero"), new Person("five"));
 219         listener.check1Update(expected, 3, 4);
 220     }
 221 
 222     @Test
 223     public void testMutableElementUnsortedChain_rt39541() {
 224         ObservableList<Person> items = createPersonsList();
 225 
 226         SortedList<Person> sorted = items.sorted();
 227         SortedList<Person> unsorted = new SortedList<>(sorted);
 228 
 229         assertEquals(sorted, unsorted);
 230 
 231         MockListObserver<Person> listener = new MockListObserver<>();
 232         unsorted.addListener(listener);
 233         items.get(3).name.set("zero"); // "four" -> "zero"
 234         ObservableList<Person> expected = FXCollections.observableArrayList(
 235                 new Person("five"), new Person("one"), new Person("three"),
 236                 new Person("two"), new Person("zero"));
 237         listener.checkPermutation(0, expected, 0, expected.size(), new int[] {0, 4, 1, 2, 3});
 238         listener.checkUpdate(1, expected, 4, 5);
 239         assertEquals(expected, sorted);
 240         assertEquals(expected, unsorted);
 241     }
 242 
 243     private ObservableList<Person> createPersonsList() {
 244         ObservableList<Person> list = FXCollections.observableArrayList(
 245                 (Person p) -> new Observable[]{p.name});
 246         list.addAll(
 247                 new Person("one"), new Person("two"), new Person("three"),
 248                 new Person("four"), new Person("five"));
 249         return list;
 250     }
 251 
 252     @Test
 253     public void testNotComparable() {
 254         final Object o1 = new Object() {
 255 
 256             @Override
 257             public String toString() {
 258                 return "c";
 259             }
 260         };
 261         final Object o2 = new Object() {
 262 
 263             @Override
 264             public String toString() {
 265                 return "a";
 266             }
 267         };
 268         final Object o3 = new Object() {
 269 
 270             @Override
 271             public String toString() {
 272                 return "d";
 273             }
 274         };
 275         ObservableList<Object> list = FXCollections.observableArrayList(o1, o2, o3);
 276 
 277         SortedList<Object> sorted = list.sorted();
 278         assertEquals(Arrays.asList(o2, o1, o3), sorted);
 279     }
 280 
 281     @Test
 282     public void testCompareNulls() {
 283         ObservableList<String> list = FXCollections.observableArrayList( "g", "a", null, "z");
 284 
 285         TransformationList<String, String> sorted = list.sorted();
 286         assertEquals(Arrays.asList(null, "a", "g", "z"), sorted);
 287     }
 288 
 289 
 290     private static class Permutator<E> extends ObservableListWrapper<E> {
 291         private List<E> backingList;
 292         public Permutator(List<E> list) {
 293             super(list);
 294             this.backingList = list;
 295         }
 296 
 297         public void swap() {
 298             E first = get(0);
 299             backingList.set(0, get(size() - 1));
 300             backingList.set(size() -1, first);
 301             fireChange(new SimplePermutationChange(0, size(), new int[] {2, 1, 0}, this));
 302         }
 303 
 304     }
 305     /**
 306      * SortedList cant cope with permutations.
 307      */
 308     @Test
 309     public void testPermutate() {
 310         List<Integer> list = new ArrayList<Integer>();
 311         for (int i = 0; i < 3; i++) {
 312             list.add(i);
 313         }
 314         Permutator<Integer> permutator = new Permutator<Integer>(list);
 315         SortedList<Integer> sorted = new SortedList<Integer>(permutator);
 316         permutator.swap();
 317         assertEquals(0, sorted.getSourceIndex(sorted.size() - 1));
 318     }
 319 
 320     @Test
 321     public void testUnsorted() {
 322         SortedList<String> sorted = new SortedList<>(list);
 323         assertEquals(sorted, list);
 324         assertEquals(list, sorted);
 325 
 326         list.removeAll("a", "d");
 327 
 328         assertEquals(sorted, list);
 329 
 330         list.addAll(0, Arrays.asList("a", "b", "c"));
 331 
 332         assertEquals(sorted, list);
 333 
 334         FXCollections.sort(list);
 335 
 336         assertEquals(sorted, list);
 337 
 338     }
 339 
 340     @Test
 341     public void testSortedNaturalOrder() {
 342         assertEquals(Arrays.asList("a", "c", "c", "d"), list.sorted());
 343     }
 344 
 345     @Test
 346     public void testRemoveFromDuplicates() {
 347         String toRemove = new String("A");
 348         String other = new String("A");
 349         list = FXCollections.observableArrayList(other, toRemove);
 350         Comparator<String> c = Comparator.naturalOrder();
 351         SortedList<String> sorted = list.sorted(c);
 352 
 353         list.remove(1);
 354 
 355         assertEquals(1, sorted.size());
 356         assertTrue(sorted.get(0) == other);
 357     }
 358     
 359     @Test
 360     public void testAddAllOnEmpty() {
 361         list = FXCollections.observableArrayList();
 362         SortedList<String> sl = list.sorted(String.CASE_INSENSITIVE_ORDER);
 363         list.addAll("B", "A");
 364         
 365         assertEquals(Arrays.asList("A", "B"), sl);
 366     }
 367 
 368     @Test
 369     public void test_rt36353_sortedList() {
 370         ObservableList<String> data = FXCollections.observableArrayList("2", "1", "3");
 371         SortedList<String> sortedList = new SortedList<String>(data);
 372 
 373         HashMap<Integer, Integer> pMap = new HashMap<>();
 374         sortedList.addListener((ListChangeListener<String>) c -> {
 375             while (c.next()) {
 376                 if (c.wasPermutated()) {
 377                     for (int i = c.getFrom(); i < c.getTo(); i++) {
 378                         pMap.put(i, c.getPermutation(i));
 379                     }
 380                 }
 381             }
 382         });
 383 
 384         Map<Integer, Integer> expected = new HashMap<>();
 385 
 386         // comparator that will create list of [1,2,3]. Sort indices based on
 387         // previous order [2,1,3].
 388         sortedList.setComparator((s1,s2) -> s1.compareTo(s2));
 389         assertEquals(FXCollections.observableArrayList("1","2","3"), sortedList);
 390         expected.put(0, 1);     // item "2" has moved from index 0 to index 1
 391         expected.put(1, 0);     // item "1" has moved from index 1 to index 0
 392         expected.put(2, 2);     // item "3" has remained in index 2
 393         assertEquals(expected, pMap);
 394 
 395         // comparator that will create list of [3,2,1]. Sort indices based on
 396         // previous order [1,2,3].
 397         sortedList.setComparator((s1,s2) -> s2.compareTo(s1));
 398         assertEquals(FXCollections.observableArrayList("3","2","1"), sortedList);
 399         expected.clear();
 400         expected.put(0, 2);     // item "1" has moved from index 0 to index 2
 401         expected.put(1, 1);     // item "2" has remained in index 1
 402         expected.put(2, 0);     // item "3" has moved from index 2 to index 0
 403         assertEquals(expected, pMap);
 404 
 405         // null comparator so sort order should return to [2,1,3]. Sort indices based on
 406         // previous order [3,2,1].
 407         sortedList.setComparator(null);
 408         assertEquals(FXCollections.observableArrayList("2","1","3"), sortedList);
 409         expected.clear();
 410         expected.put(0, 2);     // item "3" has moved from index 0 to index 2
 411         expected.put(1, 0);     // item "2" has moved from index 1 to index 0
 412         expected.put(2, 1);     // item "1" has moved from index 2 to index 1
 413         assertEquals(expected, pMap);
 414     }
 415 
 416 
 417     @Test
 418     public void testAddWhenUnsorted() {
 419         sortedList.setComparator(null);
 420         mockListObserver.clear();
 421         list.add(2, "b");
 422         assertEquals(5, sortedList.size());
 423         assertEquals(Arrays.asList("a", "c", "b", "d", "c"), sortedList);
 424         mockListObserver.check1AddRemove(sortedList, Collections.emptyList(), 2, 3);
 425 
 426         mockListObserver.clear();
 427         sortedList.setComparator(Comparator.<String>naturalOrder());
 428         mockListObserver.check1Permutation(sortedList, new int[] {0, 2, 1, 4, 3});
 429         assertEquals(5, sortedList.size());
 430         assertEquals(Arrays.asList("a", "b", "c", "c", "d"), sortedList);
 431 
 432         mockListObserver.clear();
 433         sortedList.setComparator(null);
 434         assertEquals(5, sortedList.size());
 435         assertEquals(Arrays.asList("a", "c", "b", "d", "c"), sortedList);
 436         mockListObserver.check1Permutation(sortedList, new int[] {0, 2, 1, 4, 3});
 437 
 438     }
 439 
 440     @Test
 441     public void testRemoveWhenUnsorted() {
 442         sortedList.setComparator(null);
 443         mockListObserver.clear();
 444         list.remove(1);
 445         assertEquals(3, sortedList.size());
 446         assertEquals(Arrays.asList("a", "d", "c"), sortedList);
 447         mockListObserver.check1AddRemove(sortedList, Arrays.asList("c"), 1, 1);
 448 
 449         mockListObserver.clear();
 450         sortedList.setComparator(Comparator.<String>naturalOrder());
 451         mockListObserver.check1Permutation(sortedList, new int[] {0, 2, 1});
 452         assertEquals(3, sortedList.size());
 453         assertEquals(Arrays.asList("a", "c", "d"), sortedList);
 454 
 455         mockListObserver.clear();
 456         sortedList.setComparator(null);
 457         assertEquals(3, sortedList.size());
 458         assertEquals(Arrays.asList("a", "d", "c"), sortedList);
 459         mockListObserver.check1Permutation(sortedList, new int[] {0, 2, 1});
 460     }
 461 
 462     @Test
 463     public void testSetWhenUnsorted() {
 464         sortedList.setComparator(null);
 465         mockListObserver.clear();
 466         list.set(1, "e");
 467         assertEquals(4, sortedList.size());
 468         assertEquals(Arrays.asList("a", "e", "d", "c"), sortedList);
 469         mockListObserver.check1AddRemove(sortedList, Arrays.asList("c"), 1, 2);
 470 
 471         mockListObserver.clear();
 472         sortedList.setComparator(Comparator.<String>naturalOrder());
 473         mockListObserver.check1Permutation(sortedList, new int[] {0, 3, 2, 1});
 474         assertEquals(4, sortedList.size());
 475         assertEquals(Arrays.asList("a", "c", "d", "e"), sortedList);
 476 
 477         mockListObserver.clear();
 478         sortedList.setComparator(null);
 479         assertEquals(4, sortedList.size());
 480         assertEquals(Arrays.asList("a", "e", "d", "c"), sortedList);
 481         mockListObserver.check1Permutation(sortedList, new int[] {0, 3, 2, 1});
 482     }
 483 }