       1 /*
       2  * Copyright (c) 2005, 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 package javax.swing;
      26
      27 import java.text.Collator;
      28 import java.util.ArrayList;
      29 import java.util.Arrays;
      30 import java.util.Collections;
      31 import java.util.Comparator;
      32 import java.util.List;
      33
      34 /**
      35  * An implementation of <code>RowSorter</code> that provides sorting and
      36  * filtering around a grid-based data model.
      37  * Beyond creating and installing a <code>RowSorter</code>, you very rarely
      38  * need to interact with one directly.  Refer to
      39  * {@link javax.swing.table.TableRowSorter TableRowSorter} for a concrete
      40  * implementation of <code>RowSorter</code> for <code>JTable</code>.
      41  * <p>
      42  * Sorting is done based on the current <code>SortKey</code>s, in order.
      43  * If two objects are equal (the <code>Comparator</code> for the
      44  * column returns 0) the next <code>SortKey</code> is used.  If no
      45  * <code>SortKey</code>s remain or the order is <code>UNSORTED</code>, then
      46  * the order of the rows in the model is used.
      47  * <p>
      48  * Sorting of each column is done by way of a <code>Comparator</code>
      49  * that you can specify using the <code>setComparator</code> method.
      50  * If a <code>Comparator</code> has not been specified, the
      51  * <code>Comparator</code> returned by
      52  * <code>Collator.getInstance()</code> is used on the results of
      53  * calling <code>toString</code> on the underlying objects.  The
      54  * <code>Comparator</code> is never passed <code>null</code>.  A
      55  * <code>null</code> value is treated as occurring before a
      56  * non-<code>null</code> value, and two <code>null</code> values are
      57  * considered equal.
      58  * <p>
      59  * If you specify a <code>Comparator</code> that casts its argument to
      60  * a type other than that provided by the model, a
      61  * <code>ClassCastException</code> will be thrown when the data is sorted.
      62  * <p>
      63  * In addition to sorting, <code>DefaultRowSorter</code> provides the
      64  * ability to filter rows.  Filtering is done by way of a
      65  * <code>RowFilter</code> that is specified using the
      66  * <code>setRowFilter</code> method.  If no filter has been specified all
      67  * rows are included.
      68  * <p>
      69  * By default, rows are in unsorted order (the same as the model) and
      70  * every column is sortable. The default <code>Comparator</code>s are
      71  * documented in the subclasses (for example, {@link
      72  * javax.swing.table.TableRowSorter TableRowSorter}).
      73  * <p>
      74  * If the underlying model structure changes (the
      75  * <code>modelStructureChanged</code> method is invoked) the following
      76  * are reset to their default values: <code>Comparator</code>s by
      77  * column, current sort order, and whether each column is sortable. To
      78  * find the default <code>Comparator</code>s, see the concrete
      79  * implementation (for example, {@link
      80  * javax.swing.table.TableRowSorter TableRowSorter}).  The default
      81  * sort order is unsorted (the same as the model), and columns are
      82  * sortable by default.
      83  * <p>
      84  * <code>DefaultRowSorter</code> is an abstract class.  Concrete
      85  * subclasses must provide access to the underlying data by invoking
      86  * {@code setModelWrapper}. The {@code setModelWrapper} method
      87  * <b>must</b> be invoked soon after the constructor is
      88  * called, ideally from within the subclass's constructor.
      89  * Undefined behavior will result if you use a {@code
      90  * DefaultRowSorter} without specifying a {@code ModelWrapper}.
      91  * <p>
      92  * <code>DefaultRowSorter</code> has two formal type parameters.  The
      93  * first type parameter corresponds to the class of the model, for example
      94  * <code>DefaultTableModel</code>.  The second type parameter
      95  * corresponds to the class of the identifier passed to the
      96  * <code>RowFilter</code>.  Refer to <code>TableRowSorter</code> and
      97  * <code>RowFilter</code> for more details on the type parameters.
      98  *
      99  * @param <M> the type of the model
     100  * @param <I> the type of the identifier passed to the <code>RowFilter</code>
     101  * @see javax.swing.table.TableRowSorter
     102  * @see javax.swing.table.DefaultTableModel
     103  * @see java.text.Collator
     104  * @since 1.6
     105  */
     106 public abstract class DefaultRowSorter<M, I> extends RowSorter<M> {
     107     /**
     108      * Whether or not we resort on TableModelEvent.UPDATEs.
     109      */
     110     private boolean sortsOnUpdates;
     111
     112     /**
     113      * View (JTable) -> model.
     114      */
     115     private Row[] viewToModel;
     116
     117     /**
     118      * model -> view (JTable)
     119      */
     120     private int[] modelToView;
     121
     122     /**
     123      * Comparators specified by column.
     124      */
     125     private Comparator<?>[] comparators;
     126
     127     /**
     128      * Whether or not the specified column is sortable, by column.
     129      */
     130     private boolean[] isSortable;
     131
     132     /**
     133      * Cached SortKeys for the current sort.
     134      */
     135     private SortKey[] cachedSortKeys;
     136
     137     /**
     138      * Cached comparators for the current sort
     139      */
     140     private Comparator<?>[] sortComparators;
     141
     142     /**
     143      * Developer supplied Filter.
     144      */
     145     private RowFilter<? super M,? super I> filter;
     146
     147     /**
     148      * Value passed to the filter.  The same instance is passed to the
     149      * filter for different rows.
     150      */
     151     private FilterEntry filterEntry;
     152
     153     /**
     154      * The sort keys.
     155      */
     156     private List<SortKey> sortKeys;
     157
     158     /**
     159      * Whether or not to use getStringValueAt.  This is indexed by column.
     160      */
     161     private boolean[] useToString;
     162
     163     /**
     164      * Indicates the contents are sorted.  This is used if
     165      * getSortsOnUpdates is false and an update event is received.
     166      */
     167     private boolean sorted;
     168
     169     /**
     170      * Maximum number of sort keys.
     171      */
     172     private int maxSortKeys;
     173
     174     /**
     175      * Provides access to the data we're sorting/filtering.
     176      */
     177     private ModelWrapper<M,I> modelWrapper;
     178
     179     /**
     180      * Size of the model. This is used to enforce error checking within
     181      * the table changed notification methods (such as rowsInserted).
     182      */
     183     private int modelRowCount;
     184
     185     // Whether to print warning about JDK-8160087
     186     private static boolean warning8160087 = true;
     187
     188     /**
     189      * Creates an empty <code>DefaultRowSorter</code>.
     190      */
     191     public DefaultRowSorter() {
     192         sortKeys = Collections.emptyList();
     193         maxSortKeys = 3;
     194     }
     195
     196     /**
     197      * Sets the model wrapper providing the data that is being sorted and
     198      * filtered.
     199      *
     200      * @param modelWrapper the model wrapper responsible for providing the
     201      *         data that gets sorted and filtered
     202      * @throws IllegalArgumentException if {@code modelWrapper} is
     203      *         {@code null}
     204      */
     205     protected final void setModelWrapper(ModelWrapper<M,I> modelWrapper) {
     206         if (modelWrapper == null) {
     207             throw new IllegalArgumentException(
     208                 "modelWrapper most be non-null");
     209         }
     210         ModelWrapper<M,I> last = this.modelWrapper;
     211         this.modelWrapper = modelWrapper;
     212         if (last != null) {
     213             modelStructureChanged();
     214         } else {
     215             // If last is null, we're in the constructor. If we're in
     216             // the constructor we don't want to call to overridable methods.
     217             modelRowCount = getModelWrapper().getRowCount();
     218         }
     219     }
     220
     221     /**
     222      * Returns the model wrapper providing the data that is being sorted and
     223      * filtered.
     224      *
     225      * @return the model wrapper responsible for providing the data that
     226      *         gets sorted and filtered
     227      */
     228     protected final ModelWrapper<M,I> getModelWrapper() {
     229         return modelWrapper;
     230     }
     231
     232     /**
     233      * Returns the underlying model.
     234      *
     235      * @return the underlying model
     236      */
     237     public final M getModel() {
     238         return getModelWrapper().getModel();
     239     }
     240
     241     /**
     242      * Sets whether or not the specified column is sortable.  The specified
     243      * value is only checked when <code>toggleSortOrder</code> is invoked.
     244      * It is still possible to sort on a column that has been marked as
     245      * unsortable by directly setting the sort keys.  The default is
     246      * true.
     247      *
     248      * @param column the column to enable or disable sorting on, in terms
     249      *        of the underlying model
     250      * @param sortable whether or not the specified column is sortable
     251      * @throws IndexOutOfBoundsException if <code>column</code> is outside
     252      *         the range of the model
     253      * @see #toggleSortOrder
     254      * @see #setSortKeys
     255      */
     256     public void setSortable(int column, boolean sortable) {
     257         checkColumn(column);
     258         if (isSortable == null) {
     259             isSortable = new boolean[getModelWrapper().getColumnCount()];
     260             for (int i = isSortable.length - 1; i >= 0; i--) {
     261                 isSortable[i] = true;
     262             }
     263         }
     264         isSortable[column] = sortable;
     265     }
     266
     267     /**
     268      * Returns true if the specified column is sortable; otherwise, false.
     269      *
     270      * @param column the column to check sorting for, in terms of the
     271      *        underlying model
     272      * @return true if the column is sortable
     273      * @throws IndexOutOfBoundsException if column is outside
     274      *         the range of the underlying model
     275      */
     276     public boolean isSortable(int column) {
     277         checkColumn(column);
     278         return (isSortable == null) ? true : isSortable[column];
     279     }
     280
     281     /**
     282      * Sets the sort keys. This creates a copy of the supplied
     283      * {@code List}; subsequent changes to the supplied
     284      * {@code List} do not effect this {@code DefaultRowSorter}.
     285      * If the sort keys have changed this triggers a sort.
     286      *
     287      * @param sortKeys the new <code>SortKeys</code>; <code>null</code>
     288      *        is a shorthand for specifying an empty list,
     289      *        indicating that the view should be unsorted
     290      * @throws IllegalArgumentException if any of the values in
     291      *         <code>sortKeys</code> are null or have a column index outside
     292      *         the range of the model
     293      */
     294     public void setSortKeys(List<? extends SortKey> sortKeys) {
     295         List<SortKey> old = this.sortKeys;
     296         if (sortKeys != null && sortKeys.size() > 0) {
     297             int max = getModelWrapper().getColumnCount();
     298             for (SortKey key : sortKeys) {
     299                 if (key == null || key.getColumn() < 0 ||
     300                         key.getColumn() >= max) {
     301                     throw new IllegalArgumentException("Invalid SortKey");
     302                 }
     303             }
     304             this.sortKeys = Collections.unmodifiableList(
     305                     new ArrayList<SortKey>(sortKeys));
     306         }
     307         else {
     308             this.sortKeys = Collections.emptyList();
     309         }
     310         if (!this.sortKeys.equals(old)) {
     311             fireSortOrderChanged();
     312             if (viewToModel == null) {
     313                 // Currently unsorted, use sort so that internal fields
     314                 // are correctly set.
     315                 sort();
     316             } else {
     317                 sortExistingData();
     318             }
     319         }
     320     }
     321
     322     /**
     323      * Returns the current sort keys.  This returns an unmodifiable
     324      * {@code non-null List}. If you need to change the sort keys,
     325      * make a copy of the returned {@code List}, mutate the copy
     326      * and invoke {@code setSortKeys} with the new list.
     327      *
     328      * @return the current sort order
     329      */
     330     public List<? extends SortKey> getSortKeys() {
     331         return sortKeys;
     332     }
     333
     334     /**
     335      * Sets the maximum number of sort keys.  The number of sort keys
     336      * determines how equal values are resolved when sorting.  For
     337      * example, assume a table row sorter is created and
     338      * <code>setMaxSortKeys(2)</code> is invoked on it. The user
     339      * clicks the header for column 1, causing the table rows to be
     340      * sorted based on the items in column 1.  Next, the user clicks
     341      * the header for column 2, causing the table to be sorted based
     342      * on the items in column 2; if any items in column 2 are equal,
     343      * then those particular rows are ordered based on the items in
     344      * column 1. In this case, we say that the rows are primarily
     345      * sorted on column 2, and secondarily on column 1.  If the user
     346      * then clicks the header for column 3, then the items are
     347      * primarily sorted on column 3 and secondarily sorted on column
     348      * 2.  Because the maximum number of sort keys has been set to 2
     349      * with <code>setMaxSortKeys</code>, column 1 no longer has an
     350      * effect on the order.
     351      * <p>
     352      * The maximum number of sort keys is enforced by
     353      * <code>toggleSortOrder</code>.  You can specify more sort
     354      * keys by invoking <code>setSortKeys</code> directly and they will
     355      * all be honored.  However if <code>toggleSortOrder</code> is subsequently
     356      * invoked the maximum number of sort keys will be enforced.
     357      * The default value is 3.
     358      *
     359      * @param max the maximum number of sort keys
     360      * @throws IllegalArgumentException if <code>max</code> &lt; 1
     361      */
     362     public void setMaxSortKeys(int max) {
     363         if (max < 1) {
     364             throw new IllegalArgumentException("Invalid max");
     365         }
     366         maxSortKeys = max;
     367     }
     368
     369     /**
     370      * Returns the maximum number of sort keys.
     371      *
     372      * @return the maximum number of sort keys
     373      */
     374     public int getMaxSortKeys() {
     375         return maxSortKeys;
     376     }
     377
     378     /**
     379      * If true, specifies that a sort should happen when the underlying
     380      * model is updated (<code>rowsUpdated</code> is invoked).  For
     381      * example, if this is true and the user edits an entry the
     382      * location of that item in the view may change.  The default is
     383      * false.
     384      *
     385      * @param sortsOnUpdates whether or not to sort on update events
     386      */
     387     public void setSortsOnUpdates(boolean sortsOnUpdates) {
     388         this.sortsOnUpdates = sortsOnUpdates;
     389     }
     390
     391     /**
     392      * Returns true if  a sort should happen when the underlying
     393      * model is updated; otherwise, returns false.
     394      *
     395      * @return whether or not to sort when the model is updated
     396      */
     397     public boolean getSortsOnUpdates() {
     398         return sortsOnUpdates;
     399     }
     400
     401     /**
     402      * Sets the filter that determines which rows, if any, should be
     403      * hidden from the view.  The filter is applied before sorting.  A value
     404      * of <code>null</code> indicates all values from the model should be
     405      * included.
     406      * <p>
     407      * <code>RowFilter</code>'s <code>include</code> method is passed an
     408      * <code>Entry</code> that wraps the underlying model.  The number
     409      * of columns in the <code>Entry</code> corresponds to the
     410      * number of columns in the <code>ModelWrapper</code>.  The identifier
     411      * comes from the <code>ModelWrapper</code> as well.
     412      * <p>
     413      * This method triggers a sort.
     414      *
     415      * @param filter the filter used to determine what entries should be
     416      *        included
     417      */
     418     public void setRowFilter(RowFilter<? super M,? super I> filter) {
     419         this.filter = filter;
     420         sort();
     421     }
     422
     423     /**
     424      * Returns the filter that determines which rows, if any, should
     425      * be hidden from view.
     426      *
     427      * @return the filter
     428      */
     429     public RowFilter<? super M,? super I> getRowFilter() {
     430         return filter;
     431     }
     432
     433     /**
     434      * Reverses the sort order from ascending to descending (or
     435      * descending to ascending) if the specified column is already the
     436      * primary sorted column; otherwise, makes the specified column
     437      * the primary sorted column, with an ascending sort order.  If
     438      * the specified column is not sortable, this method has no
     439      * effect.
     440      *
     441      * @param column index of the column to make the primary sorted column,
     442      *        in terms of the underlying model
     443      * @throws IndexOutOfBoundsException {@inheritDoc}
     444      * @see #setSortable(int,boolean)
     445      * @see #setMaxSortKeys(int)
     446      */
     447     public void toggleSortOrder(int column) {
     448         checkColumn(column);
     449         if (isSortable(column)) {
     450             List<SortKey> keys = new ArrayList<SortKey>(getSortKeys());
     451             SortKey sortKey;
     452             int sortIndex;
     453             for (sortIndex = keys.size() - 1; sortIndex >= 0; sortIndex--) {
     454                 if (keys.get(sortIndex).getColumn() == column) {
     455                     break;
     456                 }
     457             }
     458             if (sortIndex == -1) {
     459                 // Key doesn't exist
     460                 sortKey = new SortKey(column, SortOrder.ASCENDING);
     461                 keys.add(0, sortKey);
     462             }
     463             else if (sortIndex == 0) {
     464                 // It's the primary sorting key, toggle it
     465                 keys.set(0, toggle(keys.get(0)));
     466             }
     467             else {
     468                 // It's not the first, but was sorted on, remove old
     469                 // entry, insert as first with ascending.
     470                 keys.remove(sortIndex);
     471                 keys.add(0, new SortKey(column, SortOrder.ASCENDING));
     472             }
     473             if (keys.size() > getMaxSortKeys()) {
     474                 keys = keys.subList(0, getMaxSortKeys());
     475             }
     476             setSortKeys(keys);
     477         }
     478     }
     479
     480     private SortKey toggle(SortKey key) {
     481         if (key.getSortOrder() == SortOrder.ASCENDING) {
     482             return new SortKey(key.getColumn(), SortOrder.DESCENDING);
     483         }
     484         return new SortKey(key.getColumn(), SortOrder.ASCENDING);
     485     }
     486
     487     /**
     488      * {@inheritDoc}
     489      *
     490      * @throws IndexOutOfBoundsException {@inheritDoc}
     491      */
     492     public int convertRowIndexToView(int index) {
     493         if (modelToView == null) {
     494             return convertUnsortedUnfiltered(index);
     495         }
     496         return modelToView[index];
     497     }
     498
     499     /**
     500      * {@inheritDoc}
     501      *
     502      * @throws IndexOutOfBoundsException {@inheritDoc}
     503      */
     504     public int convertRowIndexToModel(int index) {
     505         if (viewToModel == null) {
     506             return convertUnsortedUnfiltered(index);
     507         }
     508         return viewToModel[index].modelIndex;
     509     }
     510
     511     private int convertUnsortedUnfiltered(int index) {
     512         if (index < 0 || index >= modelRowCount) {
     513             if(index >= modelRowCount &&
     514                                       index < getModelWrapper().getRowCount()) {
     515                 // 8160087
     516                 if(warning8160087) {
     517                     warning8160087 = false;
     518                     System.err.println("WARNING: row index is bigger than " +
     519                             "sorter's row count. Most likely this is a wrong " +
     520                             "sorter usage.");
     521                 }
     522             } else {
     523                 throw new IndexOutOfBoundsException("Invalid index");
     524             }
     525         }
     526         return index;
     527     }
     528
     529
     530     private boolean isUnsorted() {
     531         List<? extends SortKey> keys = getSortKeys();
     532         int keySize = keys.size();
     533         return (keySize == 0 || keys.get(0).getSortOrder() ==
     534                 SortOrder.UNSORTED);
     535     }
     536
     537     /**
     538      * Sorts the existing filtered data.  This should only be used if
     539      * the filter hasn't changed.
     540      */
     541     private void sortExistingData() {
     542         int[] lastViewToModel = getViewToModelAsInts(viewToModel);
     543
     544         updateUseToString();
     545         cacheSortKeys(getSortKeys());
     546
     547         if (isUnsorted()) {
     548             if (getRowFilter() == null) {
     549                 viewToModel = null;
     550                 modelToView = null;
     551             } else {
     552                 int included = 0;
     553                 for (int i = 0; i < modelToView.length; i++) {
     554                     if (modelToView[i] != -1) {
     555                         viewToModel[included].modelIndex = i;
     556                         modelToView[i] = included++;
     557                     }
     558                 }
     559             }
     560         } else {
     561             // sort the data
     562             Arrays.sort(viewToModel);
     563
     564             // Update the modelToView array
     565             setModelToViewFromViewToModel(false);
     566         }
     567         fireRowSorterChanged(lastViewToModel);
     568     }
     569
     570     /**
     571      * Sorts and filters the rows in the view based on the sort keys
     572      * of the columns currently being sorted and the filter, if any,
     573      * associated with this sorter.  An empty <code>sortKeys</code> list
     574      * indicates that the view should unsorted, the same as the model.
     575      *
     576      * @see #setRowFilter
     577      * @see #setSortKeys
     578      */
     579     public void sort() {
     580         sorted = true;
     581         int[] lastViewToModel = getViewToModelAsInts(viewToModel);
     582         updateUseToString();
     583         if (isUnsorted()) {
     584             // Unsorted
     585             cachedSortKeys = new SortKey[0];
     586             if (getRowFilter() == null) {
     587                 // No filter & unsorted
     588                 if (viewToModel != null) {
     589                     // sorted -> unsorted
     590                     viewToModel = null;
     591                     modelToView = null;
     592                 }
     593                 else {
     594                     // unsorted -> unsorted
     595                     // No need to do anything.
     596                     return;
     597                 }
     598             }
     599             else {
     600                 // There is filter, reset mappings
     601                 initializeFilteredMapping();
     602             }
     603         }
     604         else {
     605             cacheSortKeys(getSortKeys());
     606
     607             if (getRowFilter() != null) {
     608                 initializeFilteredMapping();
     609             }
     610             else {
     611                 createModelToView(getModelWrapper().getRowCount());
     612                 createViewToModel(getModelWrapper().getRowCount());
     613             }
     614
     615             // sort them
     616             Arrays.sort(viewToModel);
     617
     618             // Update the modelToView array
     619             setModelToViewFromViewToModel(false);
     620         }
     621         fireRowSorterChanged(lastViewToModel);
     622     }
     623
     624     /**
     625      * Updates the useToString mapping before a sort.
     626      */
     627     private void updateUseToString() {
     628         int i = getModelWrapper().getColumnCount();
     629         if (useToString == null || useToString.length != i) {
     630             useToString = new boolean[i];
     631         }
     632         for (--i; i >= 0; i--) {
     633             useToString[i] = useToString(i);
     634         }
     635     }
     636
     637     /**
     638      * Resets the viewToModel and modelToView mappings based on
     639      * the current Filter.
     640      */
     641     private void initializeFilteredMapping() {
     642         int rowCount = getModelWrapper().getRowCount();
     643         int i, j;
     644         int excludedCount = 0;
     645
     646         // Update model -> view
     647         createModelToView(rowCount);
     648         for (i = 0; i < rowCount; i++) {
     649             if (include(i)) {
     650                 modelToView[i] = i - excludedCount;
     651             }
     652             else {
     653                 modelToView[i] = -1;
     654                 excludedCount++;
     655             }
     656         }
     657
     658         // Update view -> model
     659         createViewToModel(rowCount - excludedCount);
     660         for (i = 0, j = 0; i < rowCount; i++) {
     661             if (modelToView[i] != -1) {
     662                 viewToModel[j++].modelIndex = i;
     663             }
     664         }
     665     }
     666
     667     /**
     668      * Makes sure the modelToView array is of size rowCount.
     669      */
     670     private void createModelToView(int rowCount) {
     671         if (modelToView == null || modelToView.length != rowCount) {
     672             modelToView = new int[rowCount];
     673         }
     674     }
     675
     676     /**
     677      * Resets the viewToModel array to be of size rowCount.
     678      */
     679     private void createViewToModel(int rowCount) {
     680         int recreateFrom = 0;
     681         if (viewToModel != null) {
     682             recreateFrom = Math.min(rowCount, viewToModel.length);
     683             if (viewToModel.length != rowCount) {
     684                 Row[] oldViewToModel = viewToModel;
     685                 viewToModel = new Row[rowCount];
     686                 System.arraycopy(oldViewToModel, 0, viewToModel,
     687                                  0, recreateFrom);
     688             }
     689         }
     690         else {
     691             viewToModel = new Row[rowCount];
     692         }
     693         int i;
     694         for (i = 0; i < recreateFrom; i++) {
     695             viewToModel[i].modelIndex = i;
     696         }
     697         for (i = recreateFrom; i < rowCount; i++) {
     698             viewToModel[i] = new Row(this, i);
     699         }
     700     }
     701
     702     /**
     703      * Caches the sort keys before a sort.
     704      */
     705     private void cacheSortKeys(List<? extends SortKey> keys) {
     706         int keySize = keys.size();
     707         sortComparators = new Comparator<?>[keySize];
     708         for (int i = 0; i < keySize; i++) {
     709             sortComparators[i] = getComparator0(keys.get(i).getColumn());
     710         }
     711         cachedSortKeys = keys.toArray(new SortKey[keySize]);
     712     }
     713
     714     /**
     715      * Returns whether or not to convert the value to a string before
     716      * doing comparisons when sorting.  If true
     717      * <code>ModelWrapper.getStringValueAt</code> will be used, otherwise
     718      * <code>ModelWrapper.getValueAt</code> will be used.  It is up to
     719      * subclasses, such as <code>TableRowSorter</code>, to honor this value
     720      * in their <code>ModelWrapper</code> implementation.
     721      *
     722      * @param column the index of the column to test, in terms of the
     723      *        underlying model
     724      * @return true if values are to be converted to strings before doing
     725      *              comparisons when sorting
     726      * @throws IndexOutOfBoundsException if <code>column</code> is not valid
     727      */
     728     protected boolean useToString(int column) {
     729         return (getComparator(column) == null);
     730     }
     731
     732     /**
     733      * Refreshes the modelToView mapping from that of viewToModel.
     734      * If <code>unsetFirst</code> is true, all indices in modelToView are
     735      * first set to -1.
     736      */
     737     private void setModelToViewFromViewToModel(boolean unsetFirst) {
     738         int i;
     739         if (unsetFirst) {
     740             for (i = modelToView.length - 1; i >= 0; i--) {
     741                 modelToView[i] = -1;
     742             }
     743         }
     744         for (i = viewToModel.length - 1; i >= 0; i--) {
     745             modelToView[viewToModel[i].modelIndex] = i;
     746         }
     747     }
     748
     749     private int[] getViewToModelAsInts(Row[] viewToModel) {
     750         if (viewToModel != null) {
     751             int[] viewToModelI = new int[viewToModel.length];
     752             for (int i = viewToModel.length - 1; i >= 0; i--) {
     753                 viewToModelI[i] = viewToModel[i].modelIndex;
     754             }
     755             return viewToModelI;
     756         }
     757         return new int[0];
     758     }
     759
     760     /**
     761      * Sets the <code>Comparator</code> to use when sorting the specified
     762      * column.  This does not trigger a sort.  If you want to sort after
     763      * setting the comparator you need to explicitly invoke <code>sort</code>.
     764      *
     765      * @param column the index of the column the <code>Comparator</code> is
     766      *        to be used for, in terms of the underlying model
     767      * @param comparator the <code>Comparator</code> to use
     768      * @throws IndexOutOfBoundsException if <code>column</code> is outside
     769      *         the range of the underlying model
     770      */
     771     public void setComparator(int column, Comparator<?> comparator) {
     772         checkColumn(column);
     773         if (comparators == null) {
     774             comparators = new Comparator<?>[getModelWrapper().getColumnCount()];
     775         }
     776         comparators[column] = comparator;
     777     }
     778
     779     /**
     780      * Returns the <code>Comparator</code> for the specified
     781      * column.  This will return <code>null</code> if a <code>Comparator</code>
     782      * has not been specified for the column.
     783      *
     784      * @param column the column to fetch the <code>Comparator</code> for, in
     785      *        terms of the underlying model
     786      * @return the <code>Comparator</code> for the specified column
     787      * @throws IndexOutOfBoundsException if column is outside
     788      *         the range of the underlying model
     789      */
     790     public Comparator<?> getComparator(int column) {
     791         checkColumn(column);
     792         if (comparators != null) {
     793             return comparators[column];
     794         }
     795         return null;
     796     }
     797
     798     // Returns the Comparator to use during sorting.  Where as
     799     // getComparator() may return null, this will never return null.
     800     private Comparator<?> getComparator0(int column) {
     801         Comparator<?> comparator = getComparator(column);
     802         if (comparator != null) {
     803             return comparator;
     804         }
     805         // This should be ok as useToString(column) should have returned
     806         // true in this case.
     807         return Collator.getInstance();
     808     }
     809
     810     private RowFilter.Entry<M,I> getFilterEntry(int modelIndex) {
     811         if (filterEntry == null) {
     812             filterEntry = new FilterEntry();
     813         }
     814         filterEntry.modelIndex = modelIndex;
     815         return filterEntry;
     816     }
     817
     818     /**
     819      * {@inheritDoc}
     820      */
     821     public int getViewRowCount() {
     822         if (viewToModel != null) {
     823             // When filtering this may differ from getModelWrapper().getRowCount()
     824             return viewToModel.length;
     825         }
     826         return Math.max(getModelWrapper().getRowCount(), modelRowCount);
     827     }
     828
     829     /**
     830      * {@inheritDoc}
     831      */
     832     public int getModelRowCount() {
     833         return getModelWrapper().getRowCount();
     834     }
     835
     836     private void allChanged() {
     837         modelToView = null;
     838         viewToModel = null;
     839         comparators = null;
     840         isSortable = null;
     841         if (isUnsorted()) {
     842             // Keys are already empty, to force a resort we have to
     843             // call sort
     844             sort();
     845         } else {
     846             setSortKeys(null);
     847         }
     848     }
     849
     850     /**
     851      * {@inheritDoc}
     852      */
     853     public void modelStructureChanged() {
     854         allChanged();
     855         modelRowCount = getModelWrapper().getRowCount();
     856     }
     857
     858     /**
     859      * {@inheritDoc}
     860      */
     861     public void allRowsChanged() {
     862         modelRowCount = getModelWrapper().getRowCount();
     863         sort();
     864     }
     865
     866     /**
     867      * {@inheritDoc}
     868      *
     869      * @throws IndexOutOfBoundsException {@inheritDoc}
     870      */
     871     public void rowsInserted(int firstRow, int endRow) {
     872         checkAgainstModel(firstRow, endRow);
     873         int newModelRowCount = getModelWrapper().getRowCount();
     874         if (endRow >= newModelRowCount) {
     875             throw new IndexOutOfBoundsException("Invalid range");
     876         }
     877         modelRowCount = newModelRowCount;
     878         if (shouldOptimizeChange(firstRow, endRow)) {
     879             rowsInserted0(firstRow, endRow);
     880         }
     881     }
     882
     883     /**
     884      * {@inheritDoc}
     885      *
     886      * @throws IndexOutOfBoundsException {@inheritDoc}
     887      */
     888     public void rowsDeleted(int firstRow, int endRow) {
     889         checkAgainstModel(firstRow, endRow);
     890         if (firstRow >= modelRowCount || endRow >= modelRowCount) {
     891             throw new IndexOutOfBoundsException("Invalid range");
     892         }
     893         modelRowCount = getModelWrapper().getRowCount();
     894         if (shouldOptimizeChange(firstRow, endRow)) {
     895             rowsDeleted0(firstRow, endRow);
     896         }
     897     }
     898
     899     /**
     900      * {@inheritDoc}
     901      *
     902      * @throws IndexOutOfBoundsException {@inheritDoc}
     903      */
     904     public void rowsUpdated(int firstRow, int endRow) {
     905         checkAgainstModel(firstRow, endRow);
     906         if (firstRow >= modelRowCount || endRow >= modelRowCount) {
     907             throw new IndexOutOfBoundsException("Invalid range");
     908         }
     909         if (getSortsOnUpdates()) {
     910             if (shouldOptimizeChange(firstRow, endRow)) {
     911                 rowsUpdated0(firstRow, endRow);
     912             }
     913         }
     914         else {
     915             sorted = false;
     916         }
     917     }
     918
     919     /**
     920      * {@inheritDoc}
     921      *
     922      * @throws IndexOutOfBoundsException {@inheritDoc}
     923      */
     924     public void rowsUpdated(int firstRow, int endRow, int column) {
     925         checkColumn(column);
     926         rowsUpdated(firstRow, endRow);
     927     }
     928
     929     private void checkAgainstModel(int firstRow, int endRow) {
     930         if (firstRow > endRow || firstRow < 0 || endRow < 0 ||
     931                 firstRow > modelRowCount) {
     932             throw new IndexOutOfBoundsException("Invalid range");
     933         }
     934     }
     935
     936     /**
     937      * Returns true if the specified row should be included.
     938      */
     939     private boolean include(int row) {
     940         RowFilter<? super M, ? super I> filter = getRowFilter();
     941         if (filter != null) {
     942             return filter.include(getFilterEntry(row));
     943         }
     944         // null filter, always include the row.
     945         return true;
     946     }
     947
     948     @SuppressWarnings("unchecked")
     949     private int compare(int model1, int model2) {
     950         int column;
     951         SortOrder sortOrder;
     952         Object v1, v2;
     953         int result;
     954
     955         for (int counter = 0; counter < cachedSortKeys.length; counter++) {
     956             column = cachedSortKeys[counter].getColumn();
     957             sortOrder = cachedSortKeys[counter].getSortOrder();
     958             if (sortOrder == SortOrder.UNSORTED) {
     959                 result = model1 - model2;
     960             } else {
     961                 // v1 != null && v2 != null
     962                 if (useToString[column]) {
     963                     v1 = getModelWrapper().getStringValueAt(model1, column);
     964                     v2 = getModelWrapper().getStringValueAt(model2, column);
     965                 } else {
     966                     v1 = getModelWrapper().getValueAt(model1, column);
     967                     v2 = getModelWrapper().getValueAt(model2, column);
     968                 }
     969                 // Treat nulls as < then non-null
     970                 if (v1 == null) {
     971                     if (v2 == null) {
     972                         result = 0;
     973                     } else {
     974                         result = -1;
     975                     }
     976                 } else if (v2 == null) {
     977                     result = 1;
     978                 } else {
     979                     Comparator<Object> c =
     980                         (Comparator<Object>)sortComparators[counter];
     981                     result = c.compare(v1, v2);
     982                 }
     983                 if (sortOrder == SortOrder.DESCENDING) {
     984                     result *= -1;
     985                 }
     986             }
     987             if (result != 0) {
     988                 return result;
     989             }
     990         }
     991         // If we get here, they're equal. Fallback to model order.
     992         return model1 - model2;
     993     }
     994
     995     /**
     996      * Whether not we are filtering/sorting.
     997      */
     998     private boolean isTransformed() {
     999         return (viewToModel != null);
    1000     }
    1001
    1002     /**
    1003      * Insets new set of entries.
    1004      *
    1005      * @param toAdd the Rows to add, sorted
    1006      * @param current the array to insert the items into
    1007      */
    1008     private void insertInOrder(List<Row> toAdd, Row[] current) {
    1009         int last = 0;
    1010         int index;
    1011         int max = toAdd.size();
    1012         for (int i = 0; i < max; i++) {
    1013             index = Arrays.binarySearch(current, toAdd.get(i));
    1014             if (index < 0) {
    1015                 index = -1 - index;
    1016             }
    1017             System.arraycopy(current, last,
    1018                              viewToModel, last + i, index - last);
    1019             viewToModel[index + i] = toAdd.get(i);
    1020             last = index;
    1021         }
    1022         System.arraycopy(current, last, viewToModel, last + max,
    1023                          current.length - last);
    1024     }
    1025
    1026     /**
    1027      * Returns true if we should try and optimize the processing of the
    1028      * <code>TableModelEvent</code>.  If this returns false, assume the
    1029      * event was dealt with and no further processing needs to happen.
    1030      */
    1031     private boolean shouldOptimizeChange(int firstRow, int lastRow) {
    1032         if (!isTransformed()) {
    1033             // Not transformed, nothing to do.
    1034             return false;
    1035         }
    1036         if (!sorted || (lastRow - firstRow) > viewToModel.length / 10) {
    1037             // We either weren't sorted, or to much changed, sort it all
    1038             sort();
    1039             return false;
    1040         }
    1041         return true;
    1042     }
    1043
    1044     private void rowsInserted0(int firstRow, int lastRow) {
    1045         int[] oldViewToModel = getViewToModelAsInts(viewToModel);
    1046         int i;
    1047         int delta = (lastRow - firstRow) + 1;
    1048         List<Row> added = new ArrayList<Row>(delta);
    1049
    1050         // Build the list of Rows to add into added
    1051         for (i = firstRow; i <= lastRow; i++) {
    1052             if (include(i)) {
    1053                 added.add(new Row(this, i));
    1054             }
    1055         }
    1056
    1057         // Adjust the model index of rows after the effected region
    1058         int viewIndex;
    1059         for (i = modelToView.length - 1; i >= firstRow; i--) {
    1060             viewIndex = modelToView[i];
    1061             if (viewIndex != -1) {
    1062                 viewToModel[viewIndex].modelIndex += delta;
    1063             }
    1064         }
    1065
    1066         // Insert newly added rows into viewToModel
    1067         if (added.size() > 0) {
    1068             Collections.sort(added);
    1069             Row[] lastViewToModel = viewToModel;
    1070             viewToModel = new Row[viewToModel.length + added.size()];
    1071             insertInOrder(added, lastViewToModel);
    1072         }
    1073
    1074         // Update modelToView
    1075         createModelToView(getModelWrapper().getRowCount());
    1076         setModelToViewFromViewToModel(true);
    1077
    1078         // Notify of change
    1079         fireRowSorterChanged(oldViewToModel);
    1080     }
    1081
    1082     private void rowsDeleted0(int firstRow, int lastRow) {
    1083         int[] oldViewToModel = getViewToModelAsInts(viewToModel);
    1084         int removedFromView = 0;
    1085         int i;
    1086         int viewIndex;
    1087
    1088         // Figure out how many visible rows are going to be effected.
    1089         for (i = firstRow; i <= lastRow; i++) {
    1090             viewIndex = modelToView[i];
    1091             if (viewIndex != -1) {
    1092                 removedFromView++;
    1093                 viewToModel[viewIndex] = null;
    1094             }
    1095         }
    1096
    1097         // Update the model index of rows after the effected region
    1098         int delta = lastRow - firstRow + 1;
    1099         for (i = modelToView.length - 1; i > lastRow; i--) {
    1100             viewIndex = modelToView[i];
    1101             if (viewIndex != -1) {
    1102                 viewToModel[viewIndex].modelIndex -= delta;
    1103             }
    1104         }
    1105
    1106         // Then patch up the viewToModel array
    1107         if (removedFromView > 0) {
    1108             Row[] newViewToModel = new Row[viewToModel.length -
    1109                                            removedFromView];
    1110             int newIndex = 0;
    1111             int last = 0;
    1112             for (i = 0; i < viewToModel.length; i++) {
    1113                 if (viewToModel[i] == null) {
    1114                     System.arraycopy(viewToModel, last,
    1115                                      newViewToModel, newIndex, i - last);
    1116                     newIndex += (i - last);
    1117                     last = i + 1;
    1118                 }
    1119             }
    1120             System.arraycopy(viewToModel, last,
    1121                     newViewToModel, newIndex, viewToModel.length - last);
    1122             viewToModel = newViewToModel;
    1123         }
    1124
    1125         // Update the modelToView mapping
    1126         createModelToView(getModelWrapper().getRowCount());
    1127         setModelToViewFromViewToModel(true);
    1128
    1129         // And notify of change
    1130         fireRowSorterChanged(oldViewToModel);
    1131     }
    1132
    1133     private void rowsUpdated0(int firstRow, int lastRow) {
    1134         int[] oldViewToModel = getViewToModelAsInts(viewToModel);
    1135         int i, j;
    1136         int delta = lastRow - firstRow + 1;
    1137         int modelIndex;
    1138         int last;
    1139         int index;
    1140
    1141         if (getRowFilter() == null) {
    1142             // Sorting only:
    1143
    1144             // Remove the effected rows
    1145             Row[] updated = new Row[delta];
    1146             for (j = 0, i = firstRow; i <= lastRow; i++, j++) {
    1147                 updated[j] = viewToModel[modelToView[i]];
    1148             }
    1149
    1150             // Sort the update rows
    1151             Arrays.sort(updated);
    1152
    1153             // Build the intermediary array: the array of
    1154             // viewToModel without the effected rows.
    1155             Row[] intermediary = new Row[viewToModel.length - delta];
    1156             for (i = 0, j = 0; i < viewToModel.length; i++) {
    1157                 modelIndex = viewToModel[i].modelIndex;
    1158                 if (modelIndex < firstRow || modelIndex > lastRow) {
    1159                     intermediary[j++] = viewToModel[i];
    1160                 }
    1161             }
    1162
    1163             // Build the new viewToModel
    1164             insertInOrder(Arrays.asList(updated), intermediary);
    1165
    1166             // Update modelToView
    1167             setModelToViewFromViewToModel(false);
    1168         }
    1169         else {
    1170             // Sorting & filtering.
    1171
    1172             // Remove the effected rows, adding them to updated and setting
    1173             // modelToView to -2 for any rows that were not filtered out
    1174             List<Row> updated = new ArrayList<Row>(delta);
    1175             int newlyVisible = 0;
    1176             int newlyHidden = 0;
    1177             int effected = 0;
    1178             for (i = firstRow; i <= lastRow; i++) {
    1179                 if (modelToView[i] == -1) {
    1180                     // This row was filtered out
    1181                     if (include(i)) {
    1182                         // No longer filtered
    1183                         updated.add(new Row(this, i));
    1184                         newlyVisible++;
    1185                     }
    1186                 }
    1187                 else {
    1188                     // This row was visible, make sure it should still be
    1189                     // visible.
    1190                     if (!include(i)) {
    1191                         newlyHidden++;
    1192                     }
    1193                     else {
    1194                         updated.add(viewToModel[modelToView[i]]);
    1195                     }
    1196                     modelToView[i] = -2;
    1197                     effected++;
    1198                 }
    1199             }
    1200
    1201             // Sort the updated rows
    1202             Collections.sort(updated);
    1203
    1204             // Build the intermediary array: the array of
    1205             // viewToModel without the updated rows.
    1206             Row[] intermediary = new Row[viewToModel.length - effected];
    1207             for (i = 0, j = 0; i < viewToModel.length; i++) {
    1208                 modelIndex = viewToModel[i].modelIndex;
    1209                 if (modelToView[modelIndex] != -2) {
    1210                     intermediary[j++] = viewToModel[i];
    1211                 }
    1212             }
    1213
    1214             // Recreate viewToModel, if necessary
    1215             if (newlyVisible != newlyHidden) {
    1216                 viewToModel = new Row[viewToModel.length + newlyVisible -
    1217                                       newlyHidden];
    1218             }
    1219
    1220             // Rebuild the new viewToModel array
    1221             insertInOrder(updated, intermediary);
    1222
    1223             // Update modelToView
    1224             setModelToViewFromViewToModel(true);
    1225         }
    1226         // And finally fire a sort event.
    1227         fireRowSorterChanged(oldViewToModel);
    1228     }
    1229
    1230     private void checkColumn(int column) {
    1231         if (column < 0 || column >= getModelWrapper().getColumnCount()) {
    1232             throw new IndexOutOfBoundsException(
    1233                     "column beyond range of TableModel");
    1234         }
    1235     }
    1236
    1237
    1238     /**
    1239      * <code>DefaultRowSorter.ModelWrapper</code> is responsible for providing
    1240      * the data that gets sorted by <code>DefaultRowSorter</code>.  You
    1241      * normally do not interact directly with <code>ModelWrapper</code>.
    1242      * Subclasses of <code>DefaultRowSorter</code> provide an
    1243      * implementation of <code>ModelWrapper</code> wrapping another model.
    1244      * For example,
    1245      * <code>TableRowSorter</code> provides a <code>ModelWrapper</code> that
    1246      * wraps a <code>TableModel</code>.
    1247      * <p>
    1248      * <code>ModelWrapper</code> makes a distinction between values as
    1249      * <code>Object</code>s and <code>String</code>s.  This allows
    1250      * implementations to provide a custom string
    1251      * converter to be used instead of invoking <code>toString</code> on the
    1252      * object.
    1253      *
    1254      * @param <M> the type of the underlying model
    1255      * @param <I> the identifier supplied to the filter
    1256      * @since 1.6
    1257      * @see RowFilter
    1258      * @see RowFilter.Entry
    1259      */
    1260     protected abstract static class ModelWrapper<M,I> {
    1261         /**
    1262          * Creates a new <code>ModelWrapper</code>.
    1263          */
    1264         protected ModelWrapper() {
    1265         }
    1266
    1267         /**
    1268          * Returns the underlying model that this <code>Model</code> is
    1269          * wrapping.
    1270          *
    1271          * @return the underlying model
    1272          */
    1273         public abstract M getModel();
    1274
    1275         /**
    1276          * Returns the number of columns in the model.
    1277          *
    1278          * @return the number of columns in the model
    1279          */
    1280         public abstract int getColumnCount();
    1281
    1282         /**
    1283          * Returns the number of rows in the model.
    1284          *
    1285          * @return the number of rows in the model
    1286          */
    1287         public abstract int getRowCount();
    1288
    1289         /**
    1290          * Returns the value at the specified index.
    1291          *
    1292          * @param row the row index
    1293          * @param column the column index
    1294          * @return the value at the specified index
    1295          * @throws IndexOutOfBoundsException if the indices are outside
    1296          *         the range of the model
    1297          */
    1298         public abstract Object getValueAt(int row, int column);
    1299
    1300         /**
    1301          * Returns the value as a <code>String</code> at the specified
    1302          * index.  This implementation uses <code>toString</code> on
    1303          * the result from <code>getValueAt</code> (making sure
    1304          * to return an empty string for null values).  Subclasses that
    1305          * override this method should never return null.
    1306          *
    1307          * @param row the row index
    1308          * @param column the column index
    1309          * @return the value at the specified index as a <code>String</code>
    1310          * @throws IndexOutOfBoundsException if the indices are outside
    1311          *         the range of the model
    1312          */
    1313         public String getStringValueAt(int row, int column) {
    1314             Object o = getValueAt(row, column);
    1315             if (o == null) {
    1316                 return "";
    1317             }
    1318             String string = o.toString();
    1319             if (string == null) {
    1320                 return "";
    1321             }
    1322             return string;
    1323         }
    1324
    1325         /**
    1326          * Returns the identifier for the specified row.  The return value
    1327          * of this is used as the identifier for the
    1328          * <code>RowFilter.Entry</code> that is passed to the
    1329          * <code>RowFilter</code>.
    1330          *
    1331          * @param row the row to return the identifier for, in terms of
    1332          *            the underlying model
    1333          * @return the identifier
    1334          * @see RowFilter.Entry#getIdentifier
    1335          */
    1336         public abstract I getIdentifier(int row);
    1337     }
    1338
    1339
    1340     /**
    1341      * RowFilter.Entry implementation that delegates to the ModelWrapper.
    1342      * getFilterEntry(int) creates the single instance of this that is
    1343      * passed to the Filter.  Only call getFilterEntry(int) to get
    1344      * the instance.
    1345      */
    1346     private class FilterEntry extends RowFilter.Entry<M,I> {
    1347         /**
    1348          * The index into the model, set in getFilterEntry
    1349          */
    1350         int modelIndex;
    1351
    1352         public M getModel() {
    1353             return getModelWrapper().getModel();
    1354         }
    1355
    1356         public int getValueCount() {
    1357             return getModelWrapper().getColumnCount();
    1358         }
    1359
    1360         public Object getValue(int index) {
    1361             return getModelWrapper().getValueAt(modelIndex, index);
    1362         }
    1363
    1364         public String getStringValue(int index) {
    1365             return getModelWrapper().getStringValueAt(modelIndex, index);
    1366         }
    1367
    1368         public I getIdentifier() {
    1369             return getModelWrapper().getIdentifier(modelIndex);
    1370         }
    1371     }
    1372
    1373
    1374     /**
    1375      * Row is used to handle the actual sorting by way of Comparable.  It
    1376      * will use the sortKeys to do the actual comparison.
    1377      */
    1378     // NOTE: this class is static so that it can be placed in an array
    1379     private static class Row implements Comparable<Row> {
    1380         private DefaultRowSorter<?, ?> sorter;
    1381         int modelIndex;
    1382
    1383         public Row(DefaultRowSorter<?, ?> sorter, int index) {
    1384             this.sorter = sorter;
    1385             modelIndex = index;
    1386         }
    1387
    1388         public int compareTo(Row o) {
    1389             return sorter.compare(modelIndex, o.modelIndex);
    1390         }
    1391     }
    1392 }