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 integer 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 IntSorter {
055: //~ Instance fields ----------------------------------------------------------------------------------------------------------
056:
057: private int[] x;
058: private int len;
059: private int off;
060:
061: //~ Constructors -------------------------------------------------------------------------------------------------------------
062:
063: public IntSorter(int[] 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: int 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] < x[b]) ? ((x[b] < x[c]) ? b : ((x[a] < x[c]) ? c
093: : a)) : ((x[b] > x[c]) ? b : ((x[a] > x[c]) ? c : a)));
094: }
095:
096: private void sort1Asc(int off, int len) {
097: // Insertion sort on smallest arrays
098: if (len < 7) {
099: for (int i = off; i < (len + off); i++) {
100: for (int j = i; (j > off) && (x[j - 1] > x[j]); j--) {
101: swap(j, j - 1);
102: }
103: }
104:
105: return;
106: }
107:
108: // Choose a partition element, v
109: int m = off + (len >> 1); // Small arrays, middle element
110:
111: if (len > 7) {
112: int l = off;
113: int n = (off + len) - 1;
114:
115: if (len > 40) { // Big arrays, pseudomedian of 9
116:
117: int s = len / 8;
118: l = med3(l, l + s, l + (2 * s));
119: m = med3(m - s, m, m + s);
120: n = med3(n - (2 * s), n - s, n);
121: }
122:
123: m = med3(l, m, n); // Mid-size, med of 3
124: }
125:
126: int v = x[m];
127:
128: // Establish Invariant: v* (<v)* (>v)* v*
129: int a = off;
130:
131: // Establish Invariant: v* (<v)* (>v)* v*
132: int b = a;
133:
134: // Establish Invariant: v* (<v)* (>v)* v*
135: int c = (off + len) - 1;
136:
137: // Establish Invariant: v* (<v)* (>v)* v*
138: int d = c;
139:
140: while (true) {
141: while ((b <= c) && (x[b] <= v)) {
142: if (x[b] == v) {
143: swap(a++, b);
144: }
145:
146: b++;
147: }
148:
149: while ((c >= b) && (x[c] >= v)) {
150: if (x[c] == v) {
151: swap(c, d--);
152: }
153:
154: c--;
155: }
156:
157: if (b > c) {
158: break;
159: }
160:
161: swap(b++, c--);
162: }
163:
164: // Swap partition elements back to middle
165: int s;
166:
167: // Swap partition elements back to middle
168: int n = off + len;
169: s = Math.min(a - off, b - a);
170: vecswap(off, b - s, s);
171: s = Math.min(d - c, n - d - 1);
172: vecswap(b, n - s, s);
173:
174: // Recursively sort non-partition-elements
175: if ((s = b - a) > 1) {
176: sort1Asc(off, s);
177: }
178:
179: if ((s = d - c) > 1) {
180: sort1Asc(n - s, s);
181: }
182: }
183:
184: private void sort1Desc(int off, int len) {
185: // Insertion sort on smallest arrays
186: if (len < 7) {
187: for (int i = off; i < (len + off); i++) {
188: for (int j = i; (j > off) && (x[j - 1] < x[j]); j--) {
189: swap(j, j - 1);
190: }
191: }
192:
193: return;
194: }
195:
196: // Choose a partition element, v
197: int m = off + (len >> 1); // Small arrays, middle element
198:
199: if (len > 7) {
200: int l = off;
201: int n = (off + len) - 1;
202:
203: if (len > 40) { // Big arrays, pseudomedian of 9
204:
205: int s = len / 8;
206: l = med3(l, l + s, l + (2 * s));
207: m = med3(m - s, m, m + s);
208: n = med3(n - (2 * s), n - s, n);
209: }
210:
211: m = med3(l, m, n); // Mid-size, med of 3
212: }
213:
214: int v = x[m];
215:
216: // Establish Invariant: v* (<v)* (>v)* v*
217: int a = off;
218:
219: // Establish Invariant: v* (<v)* (>v)* v*
220: int b = a;
221:
222: // Establish Invariant: v* (<v)* (>v)* v*
223: int c = (off + len) - 1;
224:
225: // Establish Invariant: v* (<v)* (>v)* v*
226: int d = c;
227:
228: while (true) {
229: while ((b <= c) && (x[b] >= v)) {
230: if (x[b] == v) {
231: swap(a++, b);
232: }
233:
234: b++;
235: }
236:
237: while ((c >= b) && (x[c] <= v)) {
238: if (x[c] == v) {
239: swap(c, d--);
240: }
241:
242: c--;
243: }
244:
245: if (b > c) {
246: break;
247: }
248:
249: swap(b++, c--);
250: }
251:
252: // Swap partition elements back to middle
253: int s;
254:
255: // Swap partition elements back to middle
256: int n = off + len;
257: s = Math.min(a - off, b - a);
258: vecswap(off, b - s, s);
259: s = Math.min(d - c, n - d - 1);
260: vecswap(b, n - s, s);
261:
262: // Recursively sort non-partition-elements
263: if ((s = b - a) > 1) {
264: sort1Desc(off, s);
265: }
266:
267: if ((s = d - c) > 1) {
268: sort1Desc(n - s, s);
269: }
270: }
271:
272: /** Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */
273: private void vecswap(int a, int b, int n) {
274: for (int i = 0; i < n; i++, a++, b++) {
275: swap(a, b);
276: }
277: }
278: }
|