1 /*
2 * Copyright (c) 2011, 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.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 it's 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 private SortHelper getSortHelper() {
184 if (helper == null) {
185 helper = new SortHelper();
186 }
187 return helper;
188 }
189
190 private int findPosition(int p) {
191 if (filtered.length == 0) {
192 return 0;
193 }
194 if (p == 0) {
195 return 0;
196 }
197 int pos = Arrays.binarySearch(filtered, 0, size, p);
198 if (pos < 0 ) {
199 pos = ~pos;
200 }
201 return pos;
202 }
203
204
205 @SuppressWarnings("unchecked")
206 private void ensureSize(int size) {
207 if (filtered.length < size) {
208 int[] replacement = new int[size * 3/2 + 1];
209 System.arraycopy(filtered, 0, replacement, 0, this.size);
210 filtered = replacement;
211 }
212 }
213
214 private void updateIndexes(int from, int delta) {
215 for (int i = from; i < size; ++i) {
216 filtered[i] += delta;
217 }
218 }
219
220 private void permutate(Change<? extends E> c) {
221 int from = findPosition(c.getFrom());
222 int to = findPosition(c.getTo());
223
224 if (to > from) {
225 for (int i = from; i < to; ++i) {
226 filtered[i] = c.getPermutation(filtered[i]);
227 }
228
229 int[] perm = getSortHelper().sort(filtered, from, to);
230 nextPermutation(from, to, perm);
231 }
232 }
233
234 private void addRemove(Change<? extends E> c) {
235 Predicate<? super E> pred = getPredicateImpl();
236 ensureSize(getSource().size());
237 final int from = findPosition(c.getFrom());
238 final int to = findPosition(c.getFrom() + c.getRemovedSize());
239
240 // Mark the nodes that are going to be removed
241 for (int i = from; i < to; ++i) {
242 nextRemove(from, c.getRemoved().get(filtered[i] - c.getFrom()));
243 }
244
245 // Update indexes of the sublist following the last element that was removed
246 updateIndexes(to, c.getAddedSize() - c.getRemovedSize());
247
248 // Replace as many removed elements as possible
249 int fpos = from;
250 int pos = c.getFrom();
251
252 ListIterator<? extends E> it = getSource().listIterator(pos);
253 for (; fpos < to && it.nextIndex() < c.getTo();) {
254 if (pred.test(it.next())) {
255 filtered[fpos] = it.previousIndex();
256 nextAdd(fpos, fpos + 1);
257 ++fpos;
258 }
259 }
260
261 if (fpos < to) {
262 // If there were more removed elements than added
263 System.arraycopy(filtered, to, filtered, fpos, size - to);
264 size -= to - fpos;
265 } else {
266 // Add the remaining elements
267 while (it.nextIndex() < c.getTo()) {
268 if (pred.test(it.next())) {
269 System.arraycopy(filtered, fpos, filtered, fpos + 1, size - fpos);
270 filtered[fpos] = it.previousIndex();
271 nextAdd(fpos, fpos + 1);
272 ++fpos;
273 ++size;
274 }
275 ++pos;
276 }
277 }
278 }
279
280 private void update(Change<? extends E> c) {
281 Predicate<? super E> pred = getPredicateImpl();
282 ensureSize(getSource().size());
283 int sourceFrom = c.getFrom();
284 int sourceTo = c.getTo();
285 int filterFrom = findPosition(sourceFrom);
286 int filterTo = findPosition(sourceTo);
287 ListIterator<? extends E> it = getSource().listIterator(sourceFrom);
288 int pos = filterFrom;
289 while (pos < filterTo || sourceFrom < sourceTo) {
290 E el = it.next();
291 if (pos < size && filtered[pos] == sourceFrom) {
292 if (!pred.test(el)) {
293 nextRemove(pos, el);
294 System.arraycopy(filtered, pos + 1, filtered, pos, size - pos - 1);
295 --size;
296 --filterTo;
297 } else {
298 nextUpdate(pos);
299 ++pos;
300 }
301 } else {
302 if (pred.test(el)) {
303 nextAdd(pos, pos + 1);
304 System.arraycopy(filtered, pos, filtered, pos + 1, size - pos);
305 filtered[pos] = sourceFrom;
306 ++size;
307 ++pos;
308 ++filterTo;
309 }
310 }
311 sourceFrom++;
312 }
313 }
314
315 @SuppressWarnings("unchecked")
316 private void refilter() {
317 ensureSize(getSource().size());
318 List<E> removed = null;
319 if (hasListeners()) {
320 removed = new ArrayList<>(this);
321 }
322 size = 0;
323 int i = 0;
324 Predicate<? super E> pred = getPredicateImpl();
325 for (Iterator<? extends E> it = getSource().iterator();it.hasNext(); ) {
326 final E next = it.next();
327 if (pred.test(next)) {
328 filtered[size++] = i;
329 }
330 ++i;
331 }
332 if (hasListeners()) {
333 fireChange(new GenericAddRemoveChange<>(0, size, removed, this));
334 }
335 }
336
337 }