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: * The Original Software is NetBeans. The Initial Developer of the Original
026: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
027: * Microsystems, Inc. All Rights Reserved.
028: *
029: * If you wish your version of this file to be governed by only the CDDL
030: * or only the GPL Version 2, indicate your decision by adding
031: * "[Contributor] elects to include this software in this distribution
032: * under the [CDDL or GPL Version 2] license." If you do not indicate a
033: * single choice of license, a recipient has the option to distribute
034: * your version of this file under either the CDDL, the GPL Version 2 or
035: * to extend the choice of license to its licensees as provided above.
036: * However, if you add GPL Version 2 code and therefore, elected the GPL
037: * Version 2 license, then the option applies only if the new code is
038: * made subject to such option by the copyright holder.
039: */
040:
041: package org.netbeans.lib.profiler.utils;
042:
043: /**
044: * An implementation of quick sort for Strings numbers.
045: * The advantage of this class is that it provides a protected swap(idx1, idx2) method, that can be overridden by a
046: * subclass. This allows one to easily create a subclass of IntSorter, that would sort, for example, a data structure
047: * consisting of several arrays, whose elements at the same index are viewed as a single logical record, and the order
048: * of these records is determined by the order of elements in one int[] array. A subclass to sort such records should
049: * override swap(). The new implementation of swap() should call super.swap() and then take care of swapping the rest
050: * of the "fields" of the two given logical records.
051: *
052: * @author Misha Dmitriev
053: */
054: public class StringSorter {
055: //~ Instance fields ----------------------------------------------------------------------------------------------------------
056:
057: private String[] x;
058: private int len;
059: private int off;
060:
061: //~ Constructors -------------------------------------------------------------------------------------------------------------
062:
063: public StringSorter(String[] x, int off, int len) {
064: this .x = x;
065: this .off = off;
066: this .len = len;
067: }
068:
069: //~ Methods ------------------------------------------------------------------------------------------------------------------
070:
071: /**
072: * Performs sorting in ascending or descending order
073: * @param asc Defines the order of sorting: <CODE>true</CODE> means ascending order, <CODE>false</CODE> means descending order.
074: */
075: public void sort(boolean asc) {
076: if (asc) {
077: sort1Asc(off, len);
078: } else {
079: sort1Desc(off, len);
080: }
081: }
082:
083: /** Swaps x[a] with x[b]. An subclass may override this method to e.g. swap other data associated with elements of the sorted array */
084: protected void swap(int a, int b) {
085: String t = x[a];
086: x[a] = x[b];
087: x[b] = t;
088: }
089:
090: /** Returns the index of the median of the three indexed integers. */
091: private int med3(int a, int b, int c) {
092: return ((x[a].compareTo(x[b]) > 0) ? ((x[b].compareTo(x[c]) > 0) ? b
093: : ((x[a].compareTo(x[c]) > 0) ? c : a))
094: : ((x[b].compareTo(x[c]) < 0) ? b : ((x[a]
095: .compareTo(x[c]) < 0) ? c : a)));
096: }
097:
098: private void sort1Asc(int off, int len) {
099: // Insertion sort on smallest arrays
100: if (len < 7) {
101: for (int i = off; i < (len + off); i++) {
102: for (int j = i; (j > off)
103: && (x[j - 1].compareTo(x[j]) > 0); j--) {
104: swap(j, j - 1);
105: }
106: }
107:
108: return;
109: }
110:
111: // Choose a partition element, v
112: int m = off + (len >> 1); // Small arrays, middle element
113:
114: if (len > 7) {
115: int l = off;
116: int n = (off + len) - 1;
117:
118: if (len > 40) { // Big arrays, pseudomedian of 9
119:
120: int s = len / 8;
121: l = med3(l, l + s, l + (2 * s));
122: m = med3(m - s, m, m + s);
123: n = med3(n - (2 * s), n - s, n);
124: }
125:
126: m = med3(l, m, n); // Mid-size, med of 3
127: }
128:
129: String v = x[m];
130:
131: // Establish Invariant: v* (<v)* (>v)* v*
132: int a = off;
133:
134: // Establish Invariant: v* (<v)* (>v)* v*
135: int b = a;
136:
137: // Establish Invariant: v* (<v)* (>v)* v*
138: int c = (off + len) - 1;
139:
140: // Establish Invariant: v* (<v)* (>v)* v*
141: int d = c;
142:
143: while (true) {
144: while ((b <= c) && (x[b].compareTo(v) <= 0)) {
145: if (x[b].equals(v)) {
146: swap(a++, b);
147: }
148:
149: b++;
150: }
151:
152: while ((c >= b) && (x[c].compareTo(v) >= 0)) {
153: if (x[c].equals(v)) {
154: swap(c, d--);
155: }
156:
157: c--;
158: }
159:
160: if (b > c) {
161: break;
162: }
163:
164: swap(b++, c--);
165: }
166:
167: // Swap partition elements back to middle
168: int s;
169:
170: // Swap partition elements back to middle
171: int n = off + len;
172: s = Math.min(a - off, b - a);
173: vecswap(off, b - s, s);
174: s = Math.min(d - c, n - d - 1);
175: vecswap(b, n - s, s);
176:
177: // Recursively sort non-partition-elements
178: if ((s = b - a) > 1) {
179: sort1Asc(off, s);
180: }
181:
182: if ((s = d - c) > 1) {
183: sort1Asc(n - s, s);
184: }
185: }
186:
187: private void sort1Desc(int off, int len) {
188: // Insertion sort on smallest arrays
189: if (len < 7) {
190: for (int i = off; i < (len + off); i++) {
191: for (int j = i; (j > off)
192: && (x[j - 1].compareTo(x[j]) < 0); j--) {
193: swap(j, j - 1);
194: }
195: }
196:
197: return;
198: }
199:
200: // Choose a partition element, v
201: int m = off + (len >> 1); // Small arrays, middle element
202:
203: if (len > 7) {
204: int l = off;
205: int n = (off + len) - 1;
206:
207: if (len > 40) { // Big arrays, pseudomedian of 9
208:
209: int s = len / 8;
210: l = med3(l, l + s, l + (2 * s));
211: m = med3(m - s, m, m + s);
212: n = med3(n - (2 * s), n - s, n);
213: }
214:
215: m = med3(l, m, n); // Mid-size, med of 3
216: }
217:
218: String v = x[m];
219:
220: // Establish Invariant: v* (<v)* (>v)* v*
221: int a = off;
222:
223: // Establish Invariant: v* (<v)* (>v)* v*
224: int b = a;
225:
226: // Establish Invariant: v* (<v)* (>v)* v*
227: int c = (off + len) - 1;
228:
229: // Establish Invariant: v* (<v)* (>v)* v*
230: int d = c;
231:
232: while (true) {
233: while ((b <= c) && (x[b].compareTo(v) >= 0)) {
234: if (x[b].equals(v)) {
235: swap(a++, b);
236: }
237:
238: b++;
239: }
240:
241: while ((c >= b) && (x[c].compareTo(v) <= 0)) {
242: if (x[c].equals(v)) {
243: swap(c, d--);
244: }
245:
246: c--;
247: }
248:
249: if (b > c) {
250: break;
251: }
252:
253: swap(b++, c--);
254: }
255:
256: // Swap partition elements back to middle
257: int s;
258:
259: // Swap partition elements back to middle
260: int n = off + len;
261: s = Math.min(a - off, b - a);
262: vecswap(off, b - s, s);
263: s = Math.min(d - c, n - d - 1);
264: vecswap(b, n - s, s);
265:
266: // Recursively sort non-partition-elements
267: if ((s = b - a) > 1) {
268: sort1Desc(off, s);
269: }
270:
271: if ((s = d - c) > 1) {
272: sort1Desc(n - s, s);
273: }
274: }
275:
276: /** Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */
277: private void vecswap(int a, int b, int n) {
278: for (int i = 0; i < n; i++, a++, b++) {
279: swap(a, b);
280: }
281: }
282: }
|