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 }