1 /*
   2  * Copyright (c) 2011, 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.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 }