001    /* $Id: TableSorter.java 12 2007-07-27 09:48:53Z ringler $
002     * This class is part of the de.mospace.swing library.
003     * Copyright (C) 2005-2006 Moritz Ringler
004     *
005     * This program is free software; you can redistribute it and/or
006     * modify it under the terms of the GNU General Public License
007     * as published by the Free Software Foundation; either version 2
008     * of the License, or (at your option) any later version.
009     *
010     * This program is distributed in the hope that it will be useful,
011     * but WITHOUT ANY WARRANTY; without even the implied warranty of
012     * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
013     * GNU General Public License for more details.
014     *
015     * You should have received a copy of the GNU General Public License
016     * along with this program; if not, write to the Free Software
017     * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
018     */
019    package de.mospace.swing.table;
020    
021    import java.util.Date;
022    import java.util.Random;
023    
024    /**
025     * A Table sorter along the lines of the TableSorter from Sun's Swing Tutorial.
026     * For a given {@link SortableTableModel} its {@link #sort sort} and
027     * {@link #randomize randomize} methods produce a one-to-one mapping
028     * between entries and row numbers.
029     *
030     * @version $Revision: 12 $ ($Date: 2007-07-27 11:48:53 +0200 (Fr, 27 Jul 2007) $)
031     * @author Moritz Ringler
032     **/
033    public class TableSorter {
034        /** index of the row-for-entry mapping in the arrays returned by the
035        * {@link #sort sort} and {@link #randomize randomize} methods. */
036        public final static int FWD=0;
037        /** index of the entry-for-row mapping in the arrays returned by the
038        * {@link #sort sort} and {@link #randomize randomize} methods. */
039        public final static int INV=1;
040        private int indexes[];
041        private int compares;
042        private SortableTableModel model;
043        private int[][] sortingColumns;
044    
045        /** Constructs a new TableSorter. The same table sorter can be used to sort
046        * multiple table models.
047        */
048        public TableSorter(){
049            //sole constructor
050        }
051    
052        private int compareRowsByColumn(int row1, int row2, int column){
053            Class type = model.getColumnClass(column);
054            SortableTableModel data = model;
055    
056            /* SortableTableModel expects a (sorted row)-index as its
057             * getValueAt-methods first argument, so we have to make
058             * (sorted row)-indexes from the (unsorted row)-indexes
059             */
060            int row1s = model.getRows(row1);
061            int row2s = model.getRows(row2);
062    
063            /* Get the values */
064            Object o1 = data.getValueAt(row1s, column);
065            Object o2 = data.getValueAt(row2s, column);
066    
067            double result = 0;
068            /* If both values are identical, return 0. */
069            if (o1 == o2) { //objects may be null at this stage ->don't use equals()
070                result = 0;
071    
072            /* Define null less than everything. */
073            } else if (o1 == null) {
074                result = -1;
075            } else if (o2 == null) {
076                result = 1;
077            } else if (o1.equals(o2)){
078                return 0;
079    
080            /* Compare numbers numerically */
081            } else if (Number.class.isAssignableFrom(type)) {
082                Number n1 = (Number) o1;
083                Number n2 = (Number) o2;
084                result = n1.doubleValue() - n2.doubleValue();
085    
086            /* Compare dates numerically */
087            } else if (type == java.util.Date.class) {
088                Date d1 = (Date) o1;
089                Date d2 = (Date) o2;
090                result = d1.getTime() - d2.getTime();
091            } else if (type == String.class) {
092            /* mr numeric comparison for numeric strings */
093                String s1 = (String) o1;
094                String s2 = (String) o2;
095                try{
096                    result = Double.parseDouble(s1) - Double.parseDouble(s2);
097                } catch (NumberFormatException ex){
098                    /* mr: changed to non-case-sensitive comparison */
099                    result = (s1.toLowerCase()).compareTo(s2.toLowerCase());
100                }
101            } else if (type == Boolean.class) {
102                Boolean bool1 = (Boolean) o1;
103                Boolean bool2 = (Boolean) o2;
104                if (bool1.equals(bool2)) {
105                    result = 0;
106                } else if (bool1.booleanValue()) { // Define false < true
107                    result = 1;
108                } else {
109                    result = -1;
110                }
111            } else {
112                String s1 = o1.toString();
113                String s2 = o2.toString();
114                /* mr: changed to non-case-sensitive comparison */
115                result = (s1.toLowerCase()).compareTo(s2.toLowerCase());
116            }
117            return (result == 0)
118                    ? 0
119                    : ( (result > 0)? 1 : -1 );
120        }
121    
122        /** Returns {-1|0|1} if row1 is {less than|equal|greater than} row2
123        * in the current sorting.
124        * @param row1 the index of the first row in the comparison
125        * @param row2 the index of the other row in the comparison
126        **/
127        private int compare(int row1, int row2) {
128            compares++;
129            for (int level = 0; level < sortingColumns.length; level++) {
130                int result = compareRowsByColumn(row1, row2, colAtLevel(level));
131                if (result != 0) {
132                    return isAscendingAtLevel(level)? result : -result;
133                }
134            }
135            return 0;
136        }
137    
138        private boolean isAscendingAtLevel(int i){
139            return (sortingColumns[i][1] == SortableTableModel.ASCENDING);
140        }
141    
142        private int colAtLevel(int i){
143            return (sortingColumns[i][0]);
144        }
145    
146        /** (Re-)initializes this sorter with the identity mapping. **/
147        private void reallocateIndices() {
148            int rowCount = model.getRowCount();
149    
150            // Set up a new array of indexes with the right number of elements
151            // for the new data model.
152            indexes = new int[rowCount];
153    
154            // Initialise with the identity mapping.
155            for (int row = 0; row < rowCount; row++) {
156                indexes[row] = row;
157            }
158        }
159    
160        /** Performs sorting of the table. **/
161        private void n2sort() {
162            int n = model.getRowCount();
163            for (int i = 0; i < n; i++) {
164                for (int j = i+1; j < n; j++) {
165                    if (compare(indexes[i], indexes[j]) == -1) {
166                        swap(i, j);
167                    }
168                }
169            }
170        }
171    
172        // This is a home-grown implementation which we have not had time
173        // to research - it may perform poorly in some circumstances. It
174        // requires twice the space of an in-place algorithm and makes
175        // NlogN assigments shuttling the values between the two
176        // arrays. The number of compares appears to vary between N-1 and
177        // NlogN depending on the initial order but the main reason for
178        // using it here is that, unlike qsort, it is stable.
179        private void shuttlesort(int from[], int to[], int low, int high) {
180            if (high - low < 2) {
181                return;
182            }
183            int middle = (low + high)/2;
184            shuttlesort(to, from, low, middle);
185            shuttlesort(to, from, middle, high);
186    
187            int p = low;
188            int q = middle;
189    
190            /* This is an optional short-cut; at each recursive call,
191            check to see if the elements in this subset are already
192            ordered.  If so, no further comparisons are needed; the
193            sub-array can just be copied.  The array must be copied rather
194            than assigned otherwise sister calls in the recursion might
195            get out of sinc.  When the number of elements is three they
196            are partitioned so that the first set, [low, mid), has one
197            element and and the second, [mid, high), has two. We skip the
198            optimisation when the number of elements is three or less as
199            the first compare in the normal merge will produce the same
200            sequence of steps. This optimisation seems to be worthwhile
201            for partially ordered lists but some analysis is needed to
202            find out how the performance drops to Nlog(N) as the initial
203            order diminishes - it may drop very quickly.  */
204    
205            if (high - low >= 4 && compare(from[middle-1], from[middle]) <= 0) {
206                for (int i = low; i < high; i++) {
207                    to[i] = from[i];
208                }
209                return;
210            }
211    
212            // A normal merge.
213    
214            for (int i = low; i < high; i++) {
215                if (q >= high || (p < middle && compare(from[p], from[q]) <= 0)) {
216                    to[i] = from[p++];
217                }
218                else {
219                    to[i] = from[q++];
220                }
221            }
222        }
223    
224        /** Exchanges rows i and j in the current mapping.
225        * @param i the index of the first row
226        * @param j the index of the row to swap the first row with
227        */
228        private void swap(int i, int j) {
229            int tmp = indexes[i];
230            indexes[i] = indexes[j];
231            indexes[j] = tmp;
232        }
233    
234        /** Sorts the specified table model.
235        * @param m the data to sort
236        * @return a 2D array holding the new row-for-entry mapping at
237        *         index FWD and the inverse mapping at index INV.
238        **/
239         public synchronized int[][] sort(SortableTableModel m){
240            model = m;
241            reallocateIndices();
242            sortingColumns = m.getSortOrder();
243            compares = 0;
244            shuttlesort((int[])indexes.clone(), indexes, 0, indexes.length);
245            int n = indexes.length;
246            int[][] mapping = new int[2][n];
247            mapping[INV]=(int[]) indexes.clone();
248            for (int i=0;i<n;i++){
249                mapping[FWD][indexes[i]]=i;
250            }
251            return mapping;
252        }
253    
254        /** Returns a random row-entry mapping for the specified SortableTableModel.
255        * @param m the data to randomize
256        * @return a 2D array holding the new row-for-entry mapping at
257        *         index FWD and the inverse mapping at index INV.
258        */
259        public synchronized int[][] randomize(SortableTableModel m){
260            model = m;
261            /* initialize indexes with the identity mapping */
262            reallocateIndices();
263            int i = indexes.length;
264            if(i==1){
265                return new int[][]{{0},{0}};
266            }
267            int[][] mapping = new int[2][i];
268            /* randomize using the Fisher-Yates algorithm */
269            Random rnd = new Random();
270            while(--i>0){
271                /* Swap element i with a random element with lower index. */
272                swap(i, rnd.nextInt(i));
273                /* Invert the new mapping. */
274                mapping[FWD][indexes[i]]=i;
275            }
276            mapping[INV]=(int[]) indexes.clone();
277            return mapping;
278        }
279    }