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 }