001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2007 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041:
042: package com.sun.data.provider.impl;
043:
044: import java.text.Collator;
045: import java.util.Comparator;
046: import java.util.Date;
047: import java.util.Locale;
048: import com.sun.data.provider.DataProviderException;
049: import com.sun.data.provider.RowKey;
050: import com.sun.data.provider.SortCriteria;
051: import com.sun.data.provider.TableDataProvider;
052: import com.sun.data.provider.TableDataSorter;
053:
054: /**
055: * The BasicTableDataSorter utilizes the {@link Comparable} interface on
056: * data objects in the specified {@link TableDataProvider} to provide a
057: * sorted version of the data based on the specified sort criteria.
058: *
059: * @author Joe Nuxoll, Dan Labracque
060: */
061: public class BasicTableDataSorter implements TableDataSorter {
062:
063: /**
064: * Constructs a BasicTableDataSorter with no sort criteria or locale
065: * setting.
066: */
067: public BasicTableDataSorter() {
068: }
069:
070: /**
071: * Constructs a BasicTableDataSorter with the specified initial sort
072: * criteria and no locale setting.
073: *
074: * @param sortCriteria The desired initial sort criteria
075: */
076: public BasicTableDataSorter(SortCriteria[] sortCriteria) {
077: this .sortCriteria = sortCriteria;
078: }
079:
080: /**
081: * Constructs a BasicTableDataSorter with the specified locale with no
082: * initial sort criteria.
083: *
084: * @param sortLocale The desired sort locale
085: */
086: public BasicTableDataSorter(Locale sortLocale) {
087: this .sortLocale = sortLocale;
088: }
089:
090: /**
091: * Constructs a BasicTableDataSorter with the specified initial sort
092: * criteria and sort locale.
093: *
094: * @param sortCriteria The desired initial sort criteria
095: * @param sortLocale The desired sort locale
096: */
097: public BasicTableDataSorter(SortCriteria[] sortCriteria,
098: Locale sortLocale) {
099: this .sortCriteria = sortCriteria;
100: this .sortLocale = sortLocale;
101: }
102:
103: /**
104: * Storage for the sort criteria
105: */
106: protected SortCriteria[] sortCriteria;
107:
108: /**
109: * Storage for the sort locale
110: */
111: protected Locale sortLocale;
112:
113: /** {@inheritDoc} */
114: public void setSortCriteria(SortCriteria[] sortCriteria) {
115: this .sortCriteria = sortCriteria;
116: }
117:
118: /** {@inheritDoc} */
119: public SortCriteria[] getSortCriteria() {
120: return sortCriteria;
121: }
122:
123: /** {@inheritDoc} */
124: public void setSortLocale(Locale sortLocale) {
125: this .sortLocale = sortLocale;
126: }
127:
128: /** {@inheritDoc} */
129: public Locale getSortLocale() {
130: return sortLocale;
131: }
132:
133: /**
134: * <p>Get an array containing an row of sorted rows. This method does not
135: * modify the model, but creates an rowed array of sorted rows. The
136: * returned array is typically used to row through model rows to obtain
137: * the next sorted object.</p>
138: *
139: * <p>The sorting algorithms selected for this method are based on the
140: * merge sort and radix sort. The radix sort, always sorts on the least
141: * significant object. For example, we could sort information three times
142: * with a stable sort: first on day, next on month, and finally on year.
143: * The analysis of the running time depends on the stable sort used as the
144: * intermediate sorting algorithm. If there are m passes, and m is
145: * constant, the radix sort runs in linear time. The total time for the
146: * merge sort algorithm is O(n log n) in the worst case.</p>
147: *
148: * {@inheritDoc}
149: */
150: public RowKey[] sort(TableDataProvider provider, RowKey[] rows)
151: throws DataProviderException {
152:
153: if (rows == null || rows.length == 0) {
154: return RowKey.EMPTY_ARRAY;
155: }
156:
157: // Initialize an array to contain the row of sorted rows.
158: int[] sortIndex = new int[rows.length];
159: for (int i = 0; i < rows.length; i++) {
160: sortIndex[i] = i;
161: }
162:
163: if (sortCriteria != null) {
164: for (int i = sortCriteria.length - 1; i >= 0; i--) {
165: mergeSort(sortIndex, 0, sortIndex.length - 1,
166: sortCriteria[i], provider, rows);
167: }
168: }
169:
170: RowKey[] sortedRows = new RowKey[sortIndex.length];
171: for (int i = 0; i < sortedRows.length; i++) {
172: sortedRows[i] = rows[sortIndex[i]];
173: }
174:
175: return sortedRows;
176: }
177:
178: // ---------------------------------------------------- Private Sort Methods
179:
180: /*
181: * The mergesort algorithm execution is illustrated as:
182: *
183: * 1. Partition the input sequence into two halves.
184: * 2. Sort the two subsequences using the same algorithm.
185: * 3. Merge the two sorted subsequences.
186: *
187: * The merge operation employed in step (3) combines two sorted
188: * subsequences to produce a single sorted array.
189: */
190: private void mergeSort(int a[], int first, int last,
191: SortCriteria sc, TableDataProvider tdp, RowKey[] rows)
192: throws DataProviderException {
193:
194: if (first < last) {
195: int mid = (first + last) / 2; // Index of midpoint
196: mergeSort(a, first, mid, sc, tdp, rows); // Sort left half
197: mergeSort(a, mid + 1, last, sc, tdp, rows); // Sort right half
198: merge(a, first, mid, last, sc, tdp, rows); // Merge both halves
199: }
200: }
201:
202: /*
203: * Merge 2 sorted array segments a[first...mid] and
204: * a[mid+1...last] into one sorted array.
205: */
206: private void merge(int a[], int first, int mid, int last,
207: SortCriteria sc, TableDataProvider tdp, RowKey[] rows)
208: throws DataProviderException {
209:
210: int length = last - first + 1; // Length of auxilary array.
211: int tmp[] = new int[length]; // Auxilary array.
212: int row1 = 0; // Index of first subarray.
213: int row2 = mid - first + 1; // Index of second subarray.
214:
215: // Initialize auxilary array.
216: for (int i = 0; i < length; i++) {
217: tmp[i] = a[first + i];
218: }
219:
220: // Combine subarrays.
221: for (int i = 0; i < length; i++) {
222: if (row2 <= last - first) {
223: if (row1 <= mid - first) {
224: if (sc.isAscending() ? compare(sc, tdp,
225: rows[tmp[row1]], rows[tmp[row2]]) > 0
226: : compare(sc, tdp, rows[tmp[row1]],
227: rows[tmp[row2]]) < 0)
228: a[first + i] = tmp[row2++];
229: else {
230: a[first + i] = tmp[row1++];
231: }
232: } else {
233: a[first + i] = tmp[row2++];
234: }
235: } else {
236: a[first + i] = tmp[row1++];
237: }
238: }
239: }
240:
241: /*
242: * Helper method to compare two objects. This method compares the following
243: * types:
244: *
245: * Boolean
246: * Character
247: * Comparator
248: * Date
249: * Number
250: * String
251: *
252: * If the object type is not identified, the object value is compared as a
253: * string.
254: */
255: private int compare(SortCriteria sc, TableDataProvider tdp,
256: RowKey row1, RowKey row2) throws DataProviderException {
257: // Get objects for the current row index
258: Object o1 = sc.getSortValue(tdp, row1);
259: Object o2 = sc.getSortValue(tdp, row2);
260:
261: // Ensure objects are not null
262: if (o1 == null && o2 == null) {
263: return 0;
264: } else if (o1 == o2) {
265: return 0;
266: } else if (o1 == null) {
267: return 1;
268: } else if (o2 == null) {
269: return -1; // Null values should appear first for descending sorts.
270: }
271:
272: // Test object values
273: if (o1 instanceof Comparator && o2 instanceof Comparator) {
274: return ((Comparator) o1).compare(o1, o2);
275: } else if (o1 instanceof Character && o2 instanceof Character) {
276: return ((Character) o1).compareTo(o2);
277: } else if (o1 instanceof Date && o2 instanceof Date) {
278: return ((Date) o1).compareTo(o2);
279: } else if (o1 instanceof Number && o2 instanceof Number) {
280: Double d1 = new Double(((Number) o1).doubleValue());
281: Double d2 = new Double(((Number) o2).doubleValue());
282: return d1.compareTo(d2);
283: } else if (o1 instanceof Boolean && o2 instanceof Boolean) {
284: boolean b1 = ((Boolean) o1).booleanValue();
285: boolean b2 = ((Boolean) o2).booleanValue();
286:
287: if (b1 == b2)
288: return 0;
289: else if (b1)
290: return -1;
291: else
292: return 1;
293: } else if (o1 instanceof String && o2 instanceof String) {
294: String s1 = (String) o1;
295: String s2 = (String) o2;
296:
297: // The String.compareTo method performs a binary comparison of the
298: // Unicode characters within the two strings. For most languages;
299: // however, this binary comparison cannot be relied on to sort
300: // strings because the Unicode values do not correspond to the
301: // relative order of the characters.
302: Collator collator = Collator
303: .getInstance(sortLocale != null ? sortLocale
304: : Locale.getDefault());
305: collator.setStrength(Collator.IDENTICAL);
306:
307: return collator.compare(s1, s2);
308: } else {
309: String s1 = o1.toString();
310: String s2 = o2.toString();
311: return s1.compareTo(s2);
312: }
313: }
314: }
|