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 }