http://openjdk.java.net/projects/openjfx/javafx-base/: OpenJFX JavaFX
  • OpenJFX Mailing List 
/*
 * Copyright (c) 2010, 2017, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package javafx.collections.transformation;

import com.sun.javafx.collections.NonIterableChange.SimplePermutationChange;
import com.sun.javafx.collections.SortHelper;
import com.sun.javafx.collections.SourceAdapterChange;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

import javafx.beans.NamedArg;
import javafx.beans.property.ObjectProperty;
import javafx.beans.property.ObjectPropertyBase;
import javafx.collections.ListChangeListener.Change;
import javafx.collections.ObservableList;


Wraps an ObservableList and sorts its content.
All changes in the ObservableList are propagated immediately
to the SortedList.
Note: invalid SortedList (as a result of broken comparison) doesn't send any notification to listeners on becoming
valid again.

See Also:
  • TransformationList
Since:JavaFX 8.0
/**
 * Wraps an ObservableList and sorts its content.
 * All changes in the ObservableList are propagated immediately
 * to the SortedList.
 *
 * Note: invalid SortedList (as a result of broken comparison) doesn't send any notification to listeners on becoming
 * valid again.
 *
 * @see TransformationList
 * @since JavaFX 8.0
 */
public final class SortedList<E> extends TransformationList<E, E>{

    private Comparator<Element<E>> elementComparator;
    private Element<E>[] sorted;
    private int[] perm;
    private int size;

    private final SortHelper helper = new SortHelper();

    private final Element<E> tempElement = new Element<>(null, -1);


    
Creates a new SortedList wrapped around the source list.
The source list will be sorted using the comparator provided. If null is provided, the list
stays unordered and is equal to the source list.

Params:
  • source – a list to wrap
  • comparator – a comparator to use or null for unordered List
/**
     * Creates a new SortedList wrapped around the source list.
     * The source list will be sorted using the comparator provided. If null is provided, the list
     * stays unordered and is equal to the source list.
     * @param source a list to wrap
     * @param comparator a comparator to use or null for unordered List
     */
    @SuppressWarnings("unchecked")
    public SortedList(@NamedArg("source") ObservableList<? extends E> source, @NamedArg("comparator") Comparator<? super E> comparator) {
        super(source);
        sorted = (Element<E>[]) new Element[source.size() *3/2 + 1];
        perm = new int[sorted.length];
        size = source.size();
        for (int i = 0; i < size; ++i) {
            sorted[i] = new Element<E>(source.get(i), i);
            perm[i] = i;
        }
        if (comparator != null) {
            setComparator(comparator);
        }

    }

    
Constructs a new unordered SortedList wrapper around the source list.

Params:
  • source – the source list
See Also:
/**
     * Constructs a new unordered SortedList wrapper around the source list.
     * @param source the source list
     * @see #SortedList(javafx.collections.ObservableList, java.util.Comparator)
     */
    public SortedList(@NamedArg("source") ObservableList<? extends E> source) {
        this(source, (Comparator)null);
    }

    @Override
    protected void sourceChanged(Change<? extends E> c) {
        if (elementComparator != null) {
            beginChange();
            while (c.next()) {
                if (c.wasPermutated()) {
                    updatePermutationIndexes(c);
                } else if (c.wasUpdated()) {
                    update(c);
                } else {
                    addRemove(c);
                }
            }
            endChange();
        } else {
            updateUnsorted(c);
            fireChange(new SourceAdapterChange<>(this, c));
        }
    };

    
The comparator that denotes the order of this SortedList.
Null for unordered SortedList.

/**
     * The comparator that denotes the order of this SortedList.
     * Null for unordered SortedList.
     */
    private ObjectProperty<Comparator<? super E>> comparator;

    public final ObjectProperty<Comparator<? super E>> comparatorProperty() {
        if (comparator == null) {
            comparator = new ObjectPropertyBase<Comparator<? super E>>() {

                @Override
                protected void invalidated() {
                    Comparator<? super E> current = get();
                    elementComparator = current != null ? new ElementComparator<>(current) : null;
                    doSortWithPermutationChange();
                }

                @Override
                public Object getBean() {
                    return SortedList.this;
                }

                @Override
                public String getName() {
                    return "comparator";
                }

            };
        }
        return comparator;
    }

    public final Comparator<? super E> getComparator() {
        return comparator == null ? null : comparator.get();
    }

    public final void setComparator(Comparator<? super E> comparator) {
        comparatorProperty().set(comparator);
    }

    
Returns the element at the specified position in this list.

Params:
  • index – index of the element to return
Throws:
Returns:the element at the specified position in this list
/**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    @Override
    public E get(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return sorted[index].e;
    }

    
Returns the number of elements in this list.

Returns:the number of elements in this list
/**
     * Returns the number of elements in this list.
     *
     * @return the number of elements in this list
     */
    @Override
    public int size() {
        return size;
    }

    private void doSortWithPermutationChange() {
        if (elementComparator != null) {
            int[] perm = helper.sort(sorted, 0, size, elementComparator);
            for (int i = 0; i < size; i++) {
                this.perm[sorted[i].index] = i;
            }
            fireChange(new SimplePermutationChange<>(0, size, perm, this));
        } else {
            int[] perm = new int[size];
            int[] rperm = new int[size];
            for (int i = 0; i < size; ++i) {
                perm[i] = rperm[i] = i;
            }
            boolean changed = false;
            int idx = 0;
            while (idx < size) {
                final int otherIdx = sorted[idx].index;
                if (otherIdx == idx) {
                    ++idx;
                    continue;
                }
                Element<E> other = sorted[otherIdx];
                sorted[otherIdx] = sorted[idx];
                sorted[idx] = other;
                this.perm[idx] = idx;
                this.perm[otherIdx] = otherIdx;
                perm[rperm[idx]] = otherIdx;
                perm[rperm[otherIdx]] = idx;
                int tp = rperm[idx];
                rperm[idx] = rperm[otherIdx];
                rperm[otherIdx] = tp;
                changed = true;
            }
            if (changed) {
                fireChange(new SimplePermutationChange<>(0, size, perm, this));
            }
        }
    }

    @Override
    public int getSourceIndex(int index) {
        return sorted[index].index;
    }

    @Override
    public int getViewIndex(int index) {
        return perm[index];
    }

    private void updatePermutationIndexes(Change<? extends E> change) {
        for (int i = 0; i < size; ++i) {
            int p = change.getPermutation(sorted[i].index);
            sorted[i].index = p;
            perm[p] = i;
        }
    }

    private void updateUnsorted(Change<? extends E> c) {
        while (c.next()) {
            if (c.wasPermutated()) {
                Element[] sortedTmp = new Element[sorted.length];
                for (int i = 0; i < size; ++i) {
                    if (i >= c.getFrom() && i < c.getTo()) {
                        int p = c.getPermutation(i);
                        sortedTmp[p] = sorted[i];
                        sortedTmp[p].index = p;
                        perm[i] = i;
                    } else {
                        sortedTmp[i] = sorted[i];
                    }
                }
                sorted = sortedTmp;
            }
            if (c.wasRemoved()) {
                final int removedTo = c.getFrom() + c.getRemovedSize();
                System.arraycopy(sorted, removedTo, sorted, c.getFrom(), size - removedTo);
                System.arraycopy(perm, removedTo, perm, c.getFrom(), size - removedTo);
                size -= c.getRemovedSize();
                updateIndices(removedTo, removedTo, -c.getRemovedSize());
            }
            if (c.wasAdded()) {
                ensureSize(size + c.getAddedSize());
                updateIndices(c.getFrom(), c.getFrom(), c.getAddedSize());
                System.arraycopy(sorted, c.getFrom(), sorted, c.getTo(), size - c.getFrom());
                System.arraycopy(perm, c.getFrom(), perm, c.getTo(), size - c.getFrom());
                size += c.getAddedSize();
                for (int i = c.getFrom(); i < c.getTo(); ++i) {
                    sorted[i] = new Element<E>(c.getList().get(i), i);
                    perm[i] = i;
                }
            }
        }
    }

    private static class Element<E> {

        public Element(E e, int index) {
            this.e = e;
            this.index = index;
        }

        private E e;
        private int index;
    }

    private static class ElementComparator<E> implements Comparator<Element<E>> {

        private final Comparator<? super E> comparator;

        public ElementComparator(Comparator<? super E> comparator) {
            this.comparator = comparator;
        }

        @Override
        @SuppressWarnings("unchecked")
        public int compare(Element<E> o1, Element<E> o2) {
            return comparator.compare(o1.e, o2.e);
        }

    }

    private void ensureSize(int size) {
        if (sorted.length < size) {
            Element<E>[] replacement = new Element[size * 3/2 + 1];
            System.arraycopy(sorted, 0, replacement, 0, this.size);
            sorted = replacement;
            int[] replacementPerm = new int[size * 3/2 + 1];
            System.arraycopy(perm, 0, replacementPerm, 0, this.size);
            perm = replacementPerm;
        }
    }

    private void updateIndices(int from, int viewFrom, int difference) {
        for (int i = 0 ; i < size; ++i) {
            if (sorted[i].index >= from) {
                sorted[i].index += difference;
            }
            if (perm[i] >= viewFrom) {
                perm[i] += difference;
            }
        }
    }

    private int findPosition(E e) {
        if (sorted.length == 0) {
            return 0;
        }
        tempElement.e = e;
        int pos = Arrays.binarySearch(sorted, 0, size, tempElement, elementComparator);
        return pos;
    }

    private void insertToMapping(E e, int idx) {
        int pos = findPosition(e);
        if (pos < 0) {
            pos = ~pos;
        }
        ensureSize(size + 1);
        updateIndices(idx, pos, 1);
        System.arraycopy(sorted, pos, sorted, pos + 1, size - pos);
        sorted[pos] = new Element<>(e, idx);
        System.arraycopy(perm, idx, perm, idx + 1, size - idx);
        perm[idx] = pos;
        ++size;
        nextAdd(pos, pos + 1);

    }

    private void setAllToMapping(List<? extends E> list, int to) {
        ensureSize(to);
        size = to;
        for (int i = 0; i < to; ++i) {
            sorted[i] = new Element<E>(list.get(i), i);
        }
        int[] perm = helper.sort(sorted, 0, size, elementComparator);
        System.arraycopy(perm, 0, this.perm, 0, size);
        nextAdd(0, size);
    }

    private void removeFromMapping(int idx, E e) {
        int pos = perm[idx];
        System.arraycopy(sorted, pos + 1, sorted, pos, size - pos - 1);
        System.arraycopy(perm, idx + 1, perm, idx, size - idx - 1);
        --size;
        sorted[size] = null;
        updateIndices(idx + 1, pos, - 1);

        nextRemove(pos, e);
    }

    private void removeAllFromMapping() {
        List<E> removed = new ArrayList(this);
        for (int i = 0; i < size; ++i) {
            sorted[i] = null;
        }
        size = 0;
        nextRemove(0, removed);
    }

    private void update(Change<? extends E> c) {
        int[] perm = helper.sort(sorted, 0, size, elementComparator);
        for (int i = 0; i < size; i++) {
            this.perm[sorted[i].index] = i;
        }
        nextPermutation(0, size, perm);
        for (int i = c.getFrom(), to = c.getTo(); i < to; ++i) {
            nextUpdate(this.perm[i]);
        }
    }

    private void addRemove(Change<? extends E> c) {
        if (c.getFrom() == 0 && c.getRemovedSize() == size) {
            removeAllFromMapping();
        } else {
            for (int i = 0, sz = c.getRemovedSize(); i < sz; ++i) {
                removeFromMapping(c.getFrom(), c.getRemoved().get(i));
            }
        }
        if (size == 0) {
            setAllToMapping(c.getList(), c.getTo()); // This is basically equivalent to getAddedSubList
                                                     // as size is 0, only valid "from" is also 0
        } else {
            for (int i = c.getFrom(), to = c.getTo(); i < to; ++i) {
                insertToMapping(c.getList().get(i), i);
            }
        }
    }


}