/*

 * Copyright (c) 2005, 2006, 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 javax.swing;

import java.text.Collator;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.Comparator;

import java.util.List;

import javax.swing.SortOrder;

/**

 * An implementation of <code>RowSorter</code> that provides sorting and

 * filtering around a grid-based data model.

 * Beyond creating and installing a <code>RowSorter</code>, you very rarely

 * need to interact with one directly.  Refer to

 * {@link javax.swing.table.TableRowSorter TableRowSorter} for a concrete

 * implementation of <code>RowSorter</code> for <code>JTable</code>.

 * <p>

 * Sorting is done based on the current <code>SortKey</code>s, in order.

 * If two objects are equal (the <code>Comparator</code> for the

 * column returns 0) the next <code>SortKey</code> is used.  If no

 * <code>SortKey</code>s remain or the order is <code>UNSORTED</code>, then

 * the order of the rows in the model is used.

 * <p>

 * Sorting of each column is done by way of a <code>Comparator</code>

 * that you can specify using the <code>setComparator</code> method.

 * If a <code>Comparator</code> has not been specified, the

 * <code>Comparator</code> returned by

 * <code>Collator.getInstance()</code> is used on the results of

 * calling <code>toString</code> on the underlying objects.  The

 * <code>Comparator</code> is never passed <code>null</code>.  A

 * <code>null</code> value is treated as occuring before a

 * non-<code>null</code> value, and two <code>null</code> values are

 * considered equal.

 * <p>

 * If you specify a <code>Comparator</code> that casts its argument to

 * a type other than that provided by the model, a

 * <code>ClassCastException</code> will be thrown when the data is sorted.

 * <p>

 * In addition to sorting, <code>DefaultRowSorter</code> provides the

 * ability to filter rows.  Filtering is done by way of a

 * <code>RowFilter</code> that is specified using the

 * <code>setRowFilter</code> method.  If no filter has been specified all

 * rows are included.

 * <p>

 * By default, rows are in unsorted order (the same as the model) and

 * every column is sortable. The default <code>Comparator</code>s are

 * documented in the subclasses (for example, {@link

 * javax.swing.table.TableRowSorter TableRowSorter}).

 * <p>

 * If the underlying model structure changes (the

 * <code>modelStructureChanged</code> method is invoked) the following

 * are reset to their default values: <code>Comparator</code>s by

 * column, current sort order, and whether each column is sortable. To

 * find the default <code>Comparator</code>s, see the concrete

 * implementation (for example, {@link

 * javax.swing.table.TableRowSorter TableRowSorter}).  The default

 * sort order is unsorted (the same as the model), and columns are

 * sortable by default.

 * <p>

 * If the underlying model structure changes (the

 * <code>modelStructureChanged</code> method is invoked) the following

 * are reset to their default values: <code>Comparator</code>s by column,

 * current sort order and whether a column is sortable.

 * <p>

 * <code>DefaultRowSorter</code> is an abstract class.  Concrete

 * subclasses must provide access to the underlying data by invoking

 * {@code setModelWrapper}. The {@code setModelWrapper} method

 * <b>must</b> be invoked soon after the constructor is

 * called, ideally from within the subclass's constructor.

 * Undefined behavior will result if you use a {@code

 * DefaultRowSorter} without specifying a {@code ModelWrapper}.

 * <p>

 * <code>DefaultRowSorter</code> has two formal type parameters.  The

 * first type parameter corresponds to the class of the model, for example

 * <code>DefaultTableModel</code>.  The second type parameter

 * corresponds to the class of the identifier passed to the

 * <code>RowFilter</code>.  Refer to <code>TableRowSorter</code> and

 * <code>RowFilter</code> for more details on the type parameters.

 *

 * @param <M> the type of the model

 * @param <I> the type of the identifier passed to the <code>RowFilter</code>

 * @see javax.swing.table.TableRowSorter

 * @see javax.swing.table.DefaultTableModel

 * @see java.text.Collator

 * @since 1.6

 */

public abstract class DefaultRowSorter<M, I> extends RowSorter<M> {

    /**

     * Whether or not we resort on TableModelEvent.UPDATEs.

     */

    private boolean sortsOnUpdates;

    /**

     * View (JTable) -> model.

     */

    private Row[] viewToModel;

    /**

     * model -> view (JTable)

     */

    private int[] modelToView;

    /**

     * Comparators specified by column.

     */

    private Comparator[] comparators;

    /**

     * Whether or not the specified column is sortable, by column.

     */

    private boolean[] isSortable;

    /**

     * Cached SortKeys for the current sort.

     */

    private SortKey[] cachedSortKeys;

    /**

     * Cached comparators for the current sort

     */

    private Comparator[] sortComparators;

    /**

     * Developer supplied Filter.

     */

    private RowFilter<? super M,? super I> filter;

    /**

     * Value passed to the filter.  The same instance is passed to the

     * filter for different rows.

     */

    private FilterEntry filterEntry;

    /**

     * The sort keys.

     */

    private List<SortKey> sortKeys;

    /**

     * Whether or not to use getStringValueAt.  This is indexed by column.

     */

    private boolean[] useToString;

    /**

     * Indicates the contents are sorted.  This is used if

     * getSortsOnUpdates is false and an update event is received.

     */

    private boolean sorted;

    /**

     * Maximum number of sort keys.

     */

    private int maxSortKeys;

    /**

     * Provides access to the data we're sorting/filtering.

     */

    private ModelWrapper<M,I> modelWrapper;

    /**

     * Size of the model. This is used to enforce error checking within

     * the table changed notification methods (such as rowsInserted).

     */

    private int modelRowCount;

    /**

     * Creates an empty <code>DefaultRowSorter</code>.

     */

    public DefaultRowSorter() {

        sortKeys = Collections.emptyList();

        maxSortKeys = 3;

    }

    /**

     * Sets the model wrapper providing the data that is being sorted and

     * filtered.

     *

     * @param modelWrapper the model wrapper responsible for providing the

     *         data that gets sorted and filtered

     * @throws IllegalArgumentException if {@code modelWrapper} is

     *         {@code null}

     */

    protected final void setModelWrapper(ModelWrapper<M,I> modelWrapper) {

        if (modelWrapper == null) {

            throw new IllegalArgumentException(

                "modelWrapper most be non-null");

        }

        ModelWrapper<M,I> last = this.modelWrapper;

        this.modelWrapper = modelWrapper;

        if (last != null) {

            modelStructureChanged();

        } else {

            // If last is null, we're in the constructor. If we're in

            // the constructor we don't want to call to overridable methods.

            modelRowCount = getModelWrapper().getRowCount();

        }

    }

    /**

     * Returns the model wrapper providing the data that is being sorted and

     * filtered.

     *

     * @return the model wrapper responsible for providing the data that

     *         gets sorted and filtered

     */

    protected final ModelWrapper<M,I> getModelWrapper() {

        return modelWrapper;

    }

    /**

     * Returns the underlying model.

     *

     * @return the underlying model

     */

    public final M getModel() {

        return getModelWrapper().getModel();

    }

    /**

     * Sets whether or not the specified column is sortable.  The specified

     * value is only checked when <code>toggleSortOrder</code> is invoked.

     * It is still possible to sort on a column that has been marked as

     * unsortable by directly setting the sort keys.  The default is

     * true.

     *

     * @param column the column to enable or disable sorting on, in terms

     *        of the underlying model

     * @param sortable whether or not the specified column is sortable

     * @throws IndexOutOfBoundsException if <code>column</code> is outside

     *         the range of the model

     * @see #toggleSortOrder

     * @see #setSortKeys

     */

    public void setSortable(int column, boolean sortable) {

        checkColumn(column);

        if (isSortable == null) {

            isSortable = new boolean[getModelWrapper().getColumnCount()];

            for (int i = isSortable.length - 1; i >= 0; i--) {

                isSortable[i] = true;

            }

        }

        isSortable[column] = sortable;

    }

    /**

     * Returns true if the specified column is sortable; otherwise, false.

     *

     * @param column the column to check sorting for, in terms of the

     *        underlying model

     * @return true if the column is sortable

     * @throws IndexOutOfBoundsException if column is outside

     *         the range of the underlying model

     */

    public boolean isSortable(int column) {

        checkColumn(column);

        return (isSortable == null) ? true : isSortable[column];

    }

    /**

     * Sets the sort keys. This creates a copy of the supplied

     * {@code List}; subsequent changes to the supplied

     * {@code List} do not effect this {@code DefaultRowSorter}.

     * If the sort keys have changed this triggers a sort.

     *

     * @param sortKeys the new <code>SortKeys</code>; <code>null</code>

     *        is a shorthand for specifying an empty list,

     *        indicating that the view should be unsorted

     * @throws IllegalArgumentException if any of the values in

     *         <code>sortKeys</code> are null or have a column index outside

     *         the range of the model

     */

    public void setSortKeys(List<? extends SortKey> sortKeys) {

        List<SortKey> old = this.sortKeys;

        if (sortKeys != null && sortKeys.size() > 0) {

            int max = getModelWrapper().getColumnCount();

            for (SortKey key : sortKeys) {

                if (key == null || key.getColumn() < 0 ||

                        key.getColumn() >= max) {

                    throw new IllegalArgumentException("Invalid SortKey");

                }

            }

            this.sortKeys = Collections.unmodifiableList(

                    new ArrayList<SortKey>(sortKeys));

        }

        else {

            this.sortKeys = Collections.emptyList();

        }

        if (!this.sortKeys.equals(old)) {

            fireSortOrderChanged();

            if (viewToModel == null) {

                // Currently unsorted, use sort so that internal fields

                // are correctly set.

                sort();

            } else {

                sortExistingData();

            }

        }

    }

    /**

     * Returns the current sort keys.  This returns an unmodifiable

     * {@code non-null List}. If you need to change the sort keys,

     * make a copy of the returned {@code List}, mutate the copy

     * and invoke {@code setSortKeys} with the new list.

     *

     * @return the current sort order

     */

    public List<? extends SortKey> getSortKeys() {

        return sortKeys;

    }

    /**

     * Sets the maximum number of sort keys.  The number of sort keys

     * determines how equal values are resolved when sorting.  For

     * example, assume a table row sorter is created and

     * <code>setMaxSortKeys(2)</code> is invoked on it. The user

     * clicks the header for column 1, causing the table rows to be

     * sorted based on the items in column 1.  Next, the user clicks

     * the header for column 2, causing the table to be sorted based

     * on the items in column 2; if any items in column 2 are equal,

     * then those particular rows are ordered based on the items in

     * column 1. In this case, we say that the rows are primarily

     * sorted on column 2, and secondarily on column 1.  If the user

     * then clicks the header for column 3, then the items are

     * primarily sorted on column 3 and secondarily sorted on column

     * 2.  Because the maximum number of sort keys has been set to 2

     * with <code>setMaxSortKeys</code>, column 1 no longer has an

     * effect on the order.

     * <p>

     * The maximum number of sort keys is enforced by

     * <code>toggleSortOrder</code>.  You can specify more sort

     * keys by invoking <code>setSortKeys</code> directly and they will

     * all be honored.  However if <code>toggleSortOrder</code> is subsequently

     * invoked the maximum number of sort keys will be enforced.

     * The default value is 3.

     *

     * @param max the maximum number of sort keys

     * @throws IllegalArgumentException if <code>max</code> &lt; 1

     */

    public void setMaxSortKeys(int max) {

        if (max < 1) {

            throw new IllegalArgumentException("Invalid max");

        }

        maxSortKeys = max;

    }

    /**

     * Returns the maximum number of sort keys.

     *

     * @return the maximum number of sort keys

     */

    public int getMaxSortKeys() {

        return maxSortKeys;

    }

    /**

     * If true, specifies that a sort should happen when the underlying

     * model is updated (<code>rowsUpdated</code> is invoked).  For

     * example, if this is true and the user edits an entry the

     * location of that item in the view may change.  The default is

     * false.

     *

     * @param sortsOnUpdates whether or not to sort on update events

     */

    public void setSortsOnUpdates(boolean sortsOnUpdates) {

        this.sortsOnUpdates = sortsOnUpdates;

    }

    /**

     * Returns true if  a sort should happen when the underlying

     * model is updated; otherwise, returns false.

     *

     * @return whether or not to sort when the model is updated

     */

    public boolean getSortsOnUpdates() {

        return sortsOnUpdates;

    }

    /**

     * Sets the filter that determines which rows, if any, should be

     * hidden from the view.  The filter is applied before sorting.  A value

     * of <code>null</code> indicates all values from the model should be

     * included.

     * <p>

     * <code>RowFilter</code>'s <code>include</code> method is passed an

     * <code>Entry</code> that wraps the underlying model.  The number

     * of columns in the <code>Entry</code> corresponds to the

     * number of columns in the <code>ModelWrapper</code>.  The identifier

     * comes from the <code>ModelWrapper</code> as well.

     * <p>

     * This method triggers a sort.

     *

     * @param filter the filter used to determine what entries should be

     *        included

     */

    public void setRowFilter(RowFilter<? super M,? super I> filter) {

        this.filter = filter;

        sort();

    }

    /**

     * Returns the filter that determines which rows, if any, should

     * be hidden from view.

     *

     * @return the filter

     */

    public RowFilter<? super M,? super I> getRowFilter() {

        return filter;

    }

    /**

     * Reverses the sort order from ascending to descending (or

     * descending to ascending) if the specified column is already the

     * primary sorted column; otherwise, makes the specified column

     * the primary sorted column, with an ascending sort order.  If

     * the specified column is not sortable, this method has no

     * effect.

     *

     * @param column index of the column to make the primary sorted column,

     *        in terms of the underlying model

     * @throws IndexOutOfBoundsException {@inheritDoc}

     * @see #setSortable(int,boolean)

     * @see #setMaxSortKeys(int)

     */

    public void toggleSortOrder(int column) {

        checkColumn(column);

        if (isSortable(column)) {

            List<SortKey> keys = new ArrayList<SortKey>(getSortKeys());

            SortKey sortKey;

            int sortIndex;

            for (sortIndex = keys.size() - 1; sortIndex >= 0; sortIndex--) {

                if (keys.get(sortIndex).getColumn() == column) {

                    break;

                }

            }

            if (sortIndex == -1) {

                // Key doesn't exist

                sortKey = new SortKey(column, SortOrder.ASCENDING);

                keys.add(0, sortKey);

            }

            else if (sortIndex == 0) {

                // It's the primary sorting key, toggle it

                keys.set(0, toggle(keys.get(0)));

            }

            else {

                // It's not the first, but was sorted on, remove old

                // entry, insert as first with ascending.

                keys.remove(sortIndex);

                keys.add(0, new SortKey(column, SortOrder.ASCENDING));

            }

            if (keys.size() > getMaxSortKeys()) {

                keys = keys.subList(0, getMaxSortKeys());

            }

            setSortKeys(keys);

        }

    }

    private SortKey toggle(SortKey key) {

        if (key.getSortOrder() == SortOrder.ASCENDING) {

            return new SortKey(key.getColumn(), SortOrder.DESCENDING);

        }

        return new SortKey(key.getColumn(), SortOrder.ASCENDING);

    }

    /**

     * {@inheritDoc}

     *

     * @throws IndexOutOfBoundsException {@inheritDoc}

     */

    public int convertRowIndexToView(int index) {

        if (modelToView == null) {

            if (index < 0 || index >= getModelWrapper().getRowCount()) {

                throw new IndexOutOfBoundsException("Invalid index");

            }

            return index;

        }

        return modelToView[index];

    }

    /**

     * {@inheritDoc}

     *

     * @throws IndexOutOfBoundsException {@inheritDoc}

     */

    public int convertRowIndexToModel(int index) {

        if (viewToModel == null) {

            if (index < 0 || index >= getModelWrapper().getRowCount()) {

                throw new IndexOutOfBoundsException("Invalid index");

            }

            return index;

        }

        return viewToModel[index].modelIndex;

    }

    private boolean isUnsorted() {

        List<? extends SortKey> keys = getSortKeys();

        int keySize = keys.size();

        return (keySize == 0 || keys.get(0).getSortOrder() ==

                SortOrder.UNSORTED);

    }

    /**