1 /*
   2  * Copyright (c) 2010, 2014, 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.transformation;
  27 
  28 import com.sun.javafx.collections.NonIterableChange.SimplePermutationChange;
  29 import com.sun.javafx.collections.SortHelper;
  30 import com.sun.javafx.collections.SourceAdapterChange;
  31 
  32 import java.util.ArrayList;
  33 import java.util.Arrays;
  34 import java.util.Comparator;
  35 import java.util.List;
  36 
  37 import javafx.beans.NamedArg;
  38 import javafx.beans.property.ObjectProperty;
  39 import javafx.beans.property.ObjectPropertyBase;
  40 import javafx.collections.ListChangeListener.Change;
  41 import javafx.collections.ObservableList;
  42 
  43 /**
  44  * Wraps an ObservableList and sorts it's content.
  45  * All changes in the ObservableList are propagated immediately
  46  * to the SortedList.
  47  *
  48  * Note: invalid SortedList (as a result of broken comparison) doesn't send any notification to listeners on becoming
  49  * valid again.
  50  *
  51  * @see TransformationList
  52  * @since JavaFX 8.0
  53  */
  54 public final class SortedList<E> extends TransformationList<E, E>{
  55 
  56     private Comparator<Element<E>> elementComparator;
  57     private Element<E>[] sorted;
  58     private int[] perm;
  59     private int size;
  60 
  61     private final SortHelper helper = new SortHelper();
  62 
  63     private final Element<E> tempElement = new Element<>(null, -1);
  64 
  65 
  66     /**
  67      * Creates a new SortedList wrapped around the source list.
  68      * The source list will be sorted using the comparator provided. If null is provided, the list
  69      * stays unordered and is equal to the source list.
  70      * @param source a list to wrap
  71      * @param comparator a comparator to use or null for unordered List
  72      */
  73     @SuppressWarnings("unchecked")
  74     public SortedList(@NamedArg("source") ObservableList<? extends E> source, @NamedArg("comparator") Comparator<? super E> comparator) {
  75         super(source);
  76         sorted = (Element<E>[]) new Element[source.size() *3/2 + 1];
  77         perm = new int[sorted.length];
  78         size = source.size();
  79         for (int i = 0; i < size; ++i) {
  80             sorted[i] = new Element<E>(source.get(i), i);
  81             perm[i] = i;
  82         }
  83         if (comparator != null) {
  84             setComparator(comparator);
  85         }
  86 
  87     }
  88 
  89     /**
  90      * Constructs a new unordered SortedList wrapper around the source list.
  91      * @param source the source list
  92      * @see #SortedList(javafx.collections.ObservableList, java.util.Comparator)
  93      */
  94     public SortedList(@NamedArg("source") ObservableList<? extends E> source) {
  95         this(source, (Comparator)null);
  96     }
  97 
  98     @Override
  99     protected void sourceChanged(Change<? extends E> c) {
 100         if (elementComparator != null) {
 101             beginChange();
 102             while (c.next()) {
 103                 if (c.wasPermutated()) {
 104                     updatePermutationIndexes(c);
 105                 } else if (c.wasUpdated()) {
 106                     update(c);
 107                 } else {
 108                     addRemove(c);
 109                 }
 110             }
 111             endChange();
 112         } else {
 113             updateUnsorted(c);
 114             fireChange(new SourceAdapterChange<>(this, c));
 115         }
 116     };
 117 
 118     /**
 119      * The comparator that denotes the order of this SortedList.
 120      * Null for unordered SortedList.
 121      */
 122     private ObjectProperty<Comparator<? super E>> comparator;
 123 
 124     public final ObjectProperty<Comparator<? super E>> comparatorProperty() {
 125         if (comparator == null) {
 126             comparator = new ObjectPropertyBase<Comparator<? super E>>() {
 127 
 128                 @Override
 129                 protected void invalidated() {
 130                     Comparator<? super E> current = get();
 131                     elementComparator = current != null ? new ElementComparator<>(current) : null;
 132                     doSortWithPermutationChange();
 133                 }
 134 
 135                 @Override
 136                 public Object getBean() {
 137                     return SortedList.this;
 138                 }
 139 
 140                 @Override
 141                 public String getName() {
 142                     return "comparator";
 143                 }
 144 
 145             };
 146         }
 147         return comparator;
 148     }
 149 
 150     public final Comparator<? super E> getComparator() {
 151         return comparator == null ? null : comparator.get();
 152     }
 153 
 154     public final void setComparator(Comparator<? super E> comparator) {
 155         comparatorProperty().set(comparator);
 156     }
 157 
 158     /**
 159      * Returns the element at the specified position in this list.
 160      *
 161      * @param  index index of the element to return
 162      * @return the element at the specified position in this list
 163      * @throws IndexOutOfBoundsException {@inheritDoc}
 164      */
 165     @Override
 166     public E get(int index) {
 167         if (index >= size) {
 168             throw new IndexOutOfBoundsException();
 169         }
 170         return sorted[index].e;
 171     }
 172 
 173     /**
 174      * Returns the number of elements in this list.
 175      *
 176      * @return the number of elements in this list
 177      */
 178     @Override
 179     public int size() {
 180         return size;
 181     }
 182 
 183     private void doSortWithPermutationChange() {
 184         if (elementComparator != null) {
 185             int[] perm = helper.sort(sorted, 0, size, elementComparator);
 186             for (int i = 0; i < size; i++) {
 187                 this.perm[sorted[i].index] = i;
 188             }
 189             fireChange(new SimplePermutationChange<>(0, size, perm, this));
 190         } else {
 191             int[] perm = new int[size];
 192             int[] rperm = new int[size];
 193             for (int i = 0; i < size; ++i) {
 194                 perm[i] = rperm[i] = i;
 195             }
 196             boolean changed = false;
 197             int idx = 0;
 198             while (idx < size) {
 199                 final int otherIdx = sorted[idx].index;
 200                 if (otherIdx == idx) {
 201                     ++idx;
 202                     continue;
 203                 }
 204                 Element<E> other = sorted[otherIdx];
 205                 sorted[otherIdx] = sorted[idx];
 206                 sorted[idx] = other;
 207                 this.perm[otherIdx] = otherIdx;
 208                 this.perm[idx] = idx;
 209                 perm[rperm[idx]] = otherIdx;
 210                 perm[rperm[otherIdx]] = idx;
 211                 int tp = rperm[idx];
 212                 rperm[idx] = rperm[otherIdx];
 213                 rperm[otherIdx] = tp;
 214                 changed = true;
 215             }
 216             if (changed) {
 217                 fireChange(new SimplePermutationChange<>(0, size, perm, this));
 218             }
 219         }
 220     }
 221 
 222     @Override
 223     public int getSourceIndex(int index) {
 224         return sorted[index].index;
 225     }
 226 
 227     @Override
 228     public int getViewIndex(int index) {
 229         return perm[index];
 230     }
 231 
 232     private void updatePermutationIndexes(Change<? extends E> change) {
 233         for (int i = 0; i < size; ++i) {
 234             int p = change.getPermutation(sorted[i].index);
 235             sorted[i].index = p;
 236             perm[p] = i;
 237         }
 238     }
 239 
 240     private void updateUnsorted(Change<? extends E> c) {
 241         while (c.next()) {
 242             if (c.wasPermutated()) {
 243                 Element[] sortedTmp = new Element[sorted.length];
 244                 for (int i = 0; i < size; ++i) {
 245                     if (i >= c.getFrom() && i < c.getTo()) {
 246                         int p = c.getPermutation(i);
 247                         sortedTmp[p] = sorted[i];
 248                         sortedTmp[p].index = p;
 249                         perm[i] = i;
 250                     } else {
 251                         sortedTmp[i] = sorted[i];
 252                     }
 253                 }
 254                 sorted = sortedTmp;
 255             }
 256             if (c.wasRemoved()) {
 257                 final int removedTo = c.getFrom() + c.getRemovedSize();
 258                 System.arraycopy(sorted, removedTo, sorted, c.getFrom(), size - removedTo);
 259                 System.arraycopy(perm, removedTo, perm, c.getFrom(), size - removedTo);
 260                 size -= c.getRemovedSize();
 261                 updateIndices(removedTo, removedTo, -c.getRemovedSize());
 262             }
 263             if (c.wasAdded()) {
 264                 ensureSize(size + c.getAddedSize());
 265                 updateIndices(c.getFrom(), c.getFrom(), c.getAddedSize());
 266                 System.arraycopy(sorted, c.getFrom(), sorted, c.getTo(), size - c.getFrom());
 267                 System.arraycopy(perm, c.getFrom(), perm, c.getTo(), size - c.getFrom());
 268                 size += c.getAddedSize();
 269                 for (int i = c.getFrom(); i < c.getTo(); ++i) {
 270                     sorted[i] = new Element<E>(c.getList().get(i), i);
 271                     perm[i] = i;
 272                 }
 273             }
 274         }
 275     }
 276 
 277     private static class Element<E> {
 278 
 279         public Element(E e, int index) {
 280             this.e = e;
 281             this.index = index;
 282         }
 283 
 284         private E e;
 285         private int index;
 286     }
 287 
 288     private static class ElementComparator<E> implements Comparator<Element<E>> {
 289 
 290         private final Comparator<? super E> comparator;
 291 
 292         public ElementComparator(Comparator<? super E> comparator) {
 293             this.comparator = comparator;
 294         }
 295 
 296         @Override
 297         @SuppressWarnings("unchecked")
 298         public int compare(Element<E> o1, Element<E> o2) {
 299             return comparator.compare(o1.e, o2.e);
 300         }
 301 
 302     }
 303 
 304     private void ensureSize(int size) {
 305         if (sorted.length < size) {
 306             Element<E>[] replacement = new Element[size * 3/2 + 1];
 307             System.arraycopy(sorted, 0, replacement, 0, this.size);
 308             sorted = replacement;
 309             int[] replacementPerm = new int[size * 3/2 + 1];
 310             System.arraycopy(perm, 0, replacementPerm, 0, this.size);
 311             perm = replacementPerm;
 312         }
 313     }
 314 
 315     private void updateIndices(int from, int viewFrom, int difference) {
 316         for (int i = 0 ; i < size; ++i) {
 317             if (sorted[i].index >= from) {
 318                 sorted[i].index += difference;
 319             }
 320             if (perm[i] >= viewFrom) {
 321                 perm[i] += difference;
 322             }
 323         }
 324     }
 325 
 326     private int findPosition(E e) {
 327         if (sorted.length == 0) {
 328             return 0;
 329         }
 330         tempElement.e = e;
 331         int pos = Arrays.binarySearch(sorted, 0, size, tempElement, elementComparator);
 332         return pos;
 333     }
 334 
 335     private void insertToMapping(E e, int idx) {
 336         int pos = findPosition(e);
 337         if (pos < 0) {
 338             pos = ~pos;
 339         }
 340         ensureSize(size + 1);
 341         updateIndices(idx, pos, 1);
 342         System.arraycopy(sorted, pos, sorted, pos + 1, size - pos);
 343         sorted[pos] = new Element<>(e, idx);
 344         System.arraycopy(perm, idx, perm, idx + 1, size - idx);
 345         perm[idx] = pos;
 346         ++size;
 347         nextAdd(pos, pos + 1);
 348 
 349     }
 350 
 351     private void setAllToMapping(List<? extends E> list, int to) {
 352         ensureSize(to);
 353         size = to;
 354         for (int i = 0; i < to; ++i) {
 355             sorted[i] = new Element<E>(list.get(i), i);
 356         }
 357         int[] perm = helper.sort(sorted, 0, size, elementComparator);
 358         System.arraycopy(perm, 0, this.perm, 0, size);
 359         nextAdd(0, size);
 360     }
 361 
 362     private void removeFromMapping(int idx, E e) {
 363         int pos = perm[idx];
 364         System.arraycopy(sorted, pos + 1, sorted, pos, size - pos - 1);
 365         System.arraycopy(perm, idx + 1, perm, idx, size - idx - 1);
 366         --size;
 367         sorted[size] = null;
 368         updateIndices(idx + 1, pos, - 1);
 369 
 370         nextRemove(pos, e);
 371     }
 372 
 373     private void removeAllFromMapping() {
 374         List<E> removed = new ArrayList(this);
 375         for (int i = 0; i < size; ++i) {
 376             sorted[i] = null;
 377         }
 378         size = 0;
 379         nextRemove(0, removed);
 380     }
 381 
 382     private void update(Change<? extends E> c) {
 383         int[] perm = helper.sort(sorted, 0, size, elementComparator);
 384         for (int i = 0; i < size; i++) {
 385             this.perm[sorted[i].index] = i;
 386         }
 387         nextPermutation(0, size, perm);
 388         for (int i = c.getFrom(), to = c.getTo(); i < to; ++i) {
 389             nextUpdate(this.perm[i]);
 390         }
 391     }
 392 
 393     private void addRemove(Change<? extends E> c) {
 394         if (c.getFrom() == 0 && c.getRemovedSize() == size) {
 395             removeAllFromMapping();
 396         } else {
 397             for (int i = 0, sz = c.getRemovedSize(); i < sz; ++i) {
 398                 removeFromMapping(c.getFrom(), c.getRemoved().get(i));
 399             }
 400         }
 401         if (size == 0) {
 402             setAllToMapping(c.getList(), c.getTo()); // This is basically equivalent to getAddedSubList
 403                                                      // as size is 0, only valid "from" is also 0
 404         } else {
 405             for (int i = c.getFrom(), to = c.getTo(); i < to; ++i) {
 406                 insertToMapping(c.getList().get(i), i);
 407             }
 408         }
 409     }
 410 
 411 
 412 }