KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jdesktop > swing > decorator > ShuttleSorter


1 /*
2  * $Id: ShuttleSorter.java,v 1.1.1.1 2004/06/16 01:43:39 davidson1 Exp $
3  *
4  * Copyright 2004 Sun Microsystems, Inc., 4150 Network Circle,
5  * Santa Clara, California 95054, U.S.A. All rights reserved.
6  */
7
8 package org.jdesktop.swing.decorator;
9
10 /**
11  * Pluggable sorting filter.
12  *
13  * @author Ramesh Gupta
14  */
15 public class ShuttleSorter extends Sorter {
16     private int[] toPrevious, fromPrevious;
17
18     public ShuttleSorter() {
19         this(0, true);
20     }
21
22     public ShuttleSorter(int col, boolean ascending) {
23         super(col, ascending);
24     }
25
26     protected void init() {
27         toPrevious = new int[0];
28         fromPrevious = new int[0];
29     }
30
31     /**
32      * Adopts the row mappings of the specified sorter by cloning the mappings.
33      *
34      * @param oldSorter <code>Sorter</code> whose mappings are to be cloned
35      */
36     protected void adopt(Sorter oldSorter) {
37         if (oldSorter != null) {
38             toPrevious = (int[]) ((ShuttleSorter) oldSorter).toPrevious.clone();
39             /** @todo shouldn't cast */
40             fromPrevious = (int[]) ((ShuttleSorter) oldSorter).fromPrevious.clone();
41             /** @todo shouldn't cast */
42         }
43     }
44
45     /**
46      * Resets the internal row mappings from this filter to the previous filter.
47      */
48     protected void reset() {
49         int inputSize = getInputSize();
50         toPrevious = new int[inputSize];
51         fromPrevious = new int[inputSize];
52         for (int i = 0; i < inputSize; i++) {
53             toPrevious[i] = i; // reset before sorting
54 }
55     }
56
57     /**
58      * Generates the row mappings from the previous filter to this filter.
59      */
60     protected void generateMappingFromPrevious() {
61         for (int i = 0; i < toPrevious.length; i++) {
62             fromPrevious[toPrevious[i]] = i;
63         }
64     }
65
66     /**
67      * Performs the sort.
68      */
69     protected void filter() {
70         sort((int[]) toPrevious.clone(), toPrevious, 0, toPrevious.length);
71     }
72
73     public int getSize() {
74         return toPrevious.length;
75     }
76
77     /**
78      * Returns the row in this filter that maps to the specified row in the
79      * previous filter. If there is no previous filter in the pipeline, this returns
80      * the row in this filter that maps to the specified row in the data model.
81      * This method is called from
82      * {@link org.jdesktop.swing.decorator.Filter#convertRowIndexToView(int) convertRowIndexToView}
83      *
84      * @param row a row index in the previous filter's "view" of the data model
85      * @return the row in this filter that maps to the specified row in
86      * the previous filter
87      */
88     protected int translateFromPreviousFilter(int row) {
89         return fromPrevious[row];
90     }
91
92     /**
93      * Returns the row in the previous filter that maps to the specified row in
94      * this filter. If there is no previous filter in the pipeline, this returns
95      * the row in the data model that maps to the specified row in this filter.
96      * This method is called from
97      * {@link org.jdesktop.swing.decorator.Filter#convertRowIndexToModel(int) convertRowIndexToModel}
98      *
99      * @param row a row index in this filter's "view" of the data model
100      * @return the row in the previous filter that maps to the specified row in
101      * this filter
102      */
103     protected int translateToPreviousFilter(int row) {
104         return toPrevious[row];
105     }
106
107 // Adapted from Phil Milne's TableSorter implementation.
108 // This implementation, however, is not coupled to TableModel in any way,
109 // and may be used with list models and other types of models easily.
110
111 // This is a home-grown implementation which we have not had time
112 // to research - it may perform poorly in some circumstances. It
113 // requires twice the space of an in-place algorithm and makes
114 // NlogN assigments shuttling the values between the two
115 // arrays. The number of compares appears to vary between N-1 and
116 // NlogN depending on the initial order but the main reason for
117 // using it here is that, unlike qsort, it is stable.
118 protected void sort(int from[], int to[], int low, int high) {
119         if (high - low < 2) {
120         // System.out.println("low:"+low+"; high:"+high);
121 return;
122         }
123         int middle = (low + high) >> 1;
124
125         sort(to, from, low, middle);
126         sort(to, from, middle, high);
127
128         int p = low;
129         int q = middle;
130
131         /* This is an optional short-cut; at each recursive call,
132          check to see if the elements in this subset are already
133          ordered. If so, no further comparisons are needed; the
134          sub-array can just be copied. The array must be copied rather
135          than assigned otherwise sister calls in the recursion might
136          get out of sinc. When the number of elements is three they
137          are partitioned so that the first set, [low, mid), has one
138          element and and the second, [mid, high), has two. We skip the
139          optimisation when the number of elements is three or less as
140          the first compare in the normal merge will produce the same
141          sequence of steps. This optimisation seems to be worthwhile
142          for partially ordered lists but some analysis is needed to
143          find out how the performance drops to Nlog(N) as the initial
144          order diminishes - it may drop very quickly. */
145
146         if (high - low >= 4 && compare(from[middle - 1], from[middle]) <= 0) {
147             for (int i = low; i < high; i++) {
148                 to[i] = from[i];
149             }
150             return;
151         }
152
153         // A normal merge.
154
155         for (int i = low; i < high; i++) {
156             if (q >= high || (p < middle && compare(from[p], from[q]) <= 0)) {
157                 to[i] = from[p++];
158             }
159             else {
160                 to[i] = from[q++];
161             }
162         }
163     }
164 }
Popular Tags