1 /* 2 * Copyright (c) 2011, 2016, 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.GenericAddRemoveChange; 29 import com.sun.javafx.collections.SortHelper; 30 import java.util.ArrayList; 31 import java.util.Arrays; 32 import java.util.Iterator; 33 import java.util.List; 34 import java.util.ListIterator; 35 import java.util.function.Predicate; 36 import javafx.beans.NamedArg; 37 import javafx.beans.property.ObjectProperty; 38 import javafx.beans.property.ObjectPropertyBase; 39 import javafx.collections.ListChangeListener.Change; 40 import javafx.collections.ObservableList; 41 42 /** 43 * Wraps an ObservableList and filters its content using the provided Predicate. 44 * All changes in the ObservableList are propagated immediately 45 * to the FilteredList. 46 * 47 * @see TransformationList 48 * @since JavaFX 8.0 49 */ 50 public final class FilteredList<E> extends TransformationList<E, E>{ 51 52 private int[] filtered; 53 private int size; 54 55 private SortHelper helper; 56 private static final Predicate ALWAYS_TRUE = t -> true; 57 58 /** 59 * Constructs a new FilteredList wrapper around the source list. 60 * The provided predicate will match the elements in the source list that will be visible. 61 * If the predicate is null, all elements will be matched and the list is equal to the source list. 62 * @param source the source list 63 * @param predicate the predicate to match the elements or null to match all elements. 64 */ 65 public FilteredList(@NamedArg("source") ObservableList<E> source, @NamedArg("predicate") Predicate<? super E> predicate) { 66 super(source); 67 filtered = new int[source.size() * 3 / 2 + 1]; 68 if (predicate != null) { 69 setPredicate(predicate); 70 } else { 71 for (size = 0; size < source.size(); size++) { 72 filtered[size] = size; 73 } 74 } 75 } 76 77 /** 78 * Constructs a new FilteredList wrapper around the source list. 79 * This list has an "always true" predicate, containing all the elements 80 * of the source list. 81 * <p> 82 * This constructor might be useful if you want to bind {@link #predicateProperty()} 83 * of this list. 84 * @param source the source list 85 */ 86 public FilteredList(@NamedArg("source") ObservableList<E> source) { 87 this(source, null); 88 } 89 90 /** 91 * The predicate that will match the elements that will be in this FilteredList. 92 * Elements not matching the predicate will be filtered-out. 93 * Null predicate means "always true" predicate, all elements will be matched. 94 */ 95 private ObjectProperty<Predicate<? super E>> predicate; 96 97 public final ObjectProperty<Predicate<? super E>> predicateProperty() { 98 if (predicate == null) { 99 predicate = new ObjectPropertyBase<Predicate<? super E>>() { 100 @Override 101 protected void invalidated() { 102 refilter(); 103 } 104 105 @Override 106 public Object getBean() { 107 return FilteredList.this; 108 } 109 110 @Override 111 public String getName() { 112 return "predicate"; 113 } 114 115 }; 116 } 117 return predicate; 118 } 119 120 public final Predicate<? super E> getPredicate() { 121 return predicate == null ? null : predicate.get(); 122 } 123 124 public final void setPredicate(Predicate<? super E> predicate) { 125 predicateProperty().set(predicate); 126 } 127 128 private Predicate<? super E> getPredicateImpl() { 129 if (getPredicate() != null) { 130 return getPredicate(); 131 } 132 return ALWAYS_TRUE; 133 } 134 135 @Override 136 protected void sourceChanged(Change<? extends E> c) { 137 beginChange(); 138 while (c.next()) { 139 if (c.wasPermutated()) { 140 permutate(c); 141 } else if (c.wasUpdated()) { 142 update(c); 143 } else { 144 addRemove(c); 145 } 146 } 147 endChange(); 148 } 149 150 /** 151 * Returns the number of elements in this list. 152 * 153 * @return the number of elements in this list 154 */ 155 @Override 156 public int size() { 157 return size; 158 } 159 160 /** 161 * Returns the element at the specified position in this list. 162 * 163 * @param index index of the element to return 164 * @return the element at the specified position in this list 165 * @throws IndexOutOfBoundsException {@inheritDoc} 166 */ 167 @Override 168 public E get(int index) { 169 if (index >= size) { 170 throw new IndexOutOfBoundsException(); 171 } 172 return getSource().get(filtered[index]); 173 } 174 175 @Override 176 public int getSourceIndex(int index) { 177 if (index >= size) { 178 throw new IndexOutOfBoundsException(); 179 } 180 return filtered[index]; 181 } 182 183 @Override 184 public int getViewIndex(int index) { 185 return Arrays.binarySearch(filtered, 0, size, index); 186 } 187 188 private SortHelper getSortHelper() { 189 if (helper == null) { 190 helper = new SortHelper(); 191 } 192 return helper; 193 } 194 195 private int findPosition(int p) { 196 if (filtered.length == 0) { 197 return 0; 198 } 199 if (p == 0) { 200 return 0; 201 } 202 int pos = Arrays.binarySearch(filtered, 0, size, p); 203 if (pos < 0 ) { 204 pos = ~pos; 205 } 206 return pos; 207 } 208 209 210 @SuppressWarnings("unchecked") 211 private void ensureSize(int size) { 212 if (filtered.length < size) { 213 int[] replacement = new int[size * 3/2 + 1]; 214 System.arraycopy(filtered, 0, replacement, 0, this.size); 215 filtered = replacement; 216 } 217 } 218 219 private void updateIndexes(int from, int delta) { 220 for (int i = from; i < size; ++i) { 221 filtered[i] += delta; 222 } 223 } 224 225 private void permutate(Change<? extends E> c) { 226 int from = findPosition(c.getFrom()); 227 int to = findPosition(c.getTo()); 228 229 if (to > from) { 230 for (int i = from; i < to; ++i) { 231 filtered[i] = c.getPermutation(filtered[i]); 232 } 233 234 int[] perm = getSortHelper().sort(filtered, from, to); 235 nextPermutation(from, to, perm); 236 } 237 } 238 239 private void addRemove(Change<? extends E> c) { 240 Predicate<? super E> pred = getPredicateImpl(); 241 ensureSize(getSource().size()); 242 final int from = findPosition(c.getFrom()); 243 final int to = findPosition(c.getFrom() + c.getRemovedSize()); 244 245 // Mark the nodes that are going to be removed 246 for (int i = from; i < to; ++i) { 247 nextRemove(from, c.getRemoved().get(filtered[i] - c.getFrom())); 248 } 249 250 // Update indexes of the sublist following the last element that was removed 251 updateIndexes(to, c.getAddedSize() - c.getRemovedSize()); 252 253 // Replace as many removed elements as possible 254 int fpos = from; 255 int pos = c.getFrom(); 256 257 ListIterator<? extends E> it = getSource().listIterator(pos); 258 for (; fpos < to && it.nextIndex() < c.getTo();) { 259 if (pred.test(it.next())) { 260 filtered[fpos] = it.previousIndex(); 261 nextAdd(fpos, fpos + 1); 262 ++fpos; 263 } 264 } 265 266 if (fpos < to) { 267 // If there were more removed elements than added 268 System.arraycopy(filtered, to, filtered, fpos, size - to); 269 size -= to - fpos; 270 } else { 271 // Add the remaining elements 272 while (it.nextIndex() < c.getTo()) { 273 if (pred.test(it.next())) { 274 System.arraycopy(filtered, fpos, filtered, fpos + 1, size - fpos); 275 filtered[fpos] = it.previousIndex(); 276 nextAdd(fpos, fpos + 1); 277 ++fpos; 278 ++size; 279 } 280 ++pos; 281 } 282 } 283 } 284 285 private void update(Change<? extends E> c) { 286 Predicate<? super E> pred = getPredicateImpl(); 287 ensureSize(getSource().size()); 288 int sourceFrom = c.getFrom(); 289 int sourceTo = c.getTo(); 290 int filterFrom = findPosition(sourceFrom); 291 int filterTo = findPosition(sourceTo); 292 ListIterator<? extends E> it = getSource().listIterator(sourceFrom); 293 int pos = filterFrom; 294 while (pos < filterTo || sourceFrom < sourceTo) { 295 E el = it.next(); 296 if (pos < size && filtered[pos] == sourceFrom) { 297 if (!pred.test(el)) { 298 nextRemove(pos, el); 299 System.arraycopy(filtered, pos + 1, filtered, pos, size - pos - 1); 300 --size; 301 --filterTo; 302 } else { 303 nextUpdate(pos); 304 ++pos; 305 } 306 } else { 307 if (pred.test(el)) { 308 nextAdd(pos, pos + 1); 309 System.arraycopy(filtered, pos, filtered, pos + 1, size - pos); 310 filtered[pos] = sourceFrom; 311 ++size; 312 ++pos; 313 ++filterTo; 314 } 315 } 316 sourceFrom++; 317 } 318 } 319 320 @SuppressWarnings("unchecked") 321 private void refilter() { 322 ensureSize(getSource().size()); 323 List<E> removed = null; 324 if (hasListeners()) { 325 removed = new ArrayList<>(this); 326 } 327 size = 0; 328 int i = 0; 329 Predicate<? super E> pred = getPredicateImpl(); 330 for (Iterator<? extends E> it = getSource().iterator();it.hasNext(); ) { 331 final E next = it.next(); 332 if (pred.test(next)) { 333 filtered[size++] = i; 334 } 335 ++i; 336 } 337 if (hasListeners()) { 338 fireChange(new GenericAddRemoveChange<>(0, size, removed, this)); 339 } 340 } 341 342 }