001: /* Copyright (c) 1995-2000, The Hypersonic SQL Group.
002: * All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * Redistributions of source code must retain the above copyright notice, this
008: * list of conditions and the following disclaimer.
009: *
010: * Redistributions in binary form must reproduce the above copyright notice,
011: * this list of conditions and the following disclaimer in the documentation
012: * and/or other materials provided with the distribution.
013: *
014: * Neither the name of the Hypersonic SQL Group nor the names of its
015: * contributors may be used to endorse or promote products derived from this
016: * software without specific prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL THE HYPERSONIC SQL GROUP,
022: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
023: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
024: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
026: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029: *
030: * This software consists of voluntary contributions made by many individuals
031: * on behalf of the Hypersonic SQL Group.
032: *
033: *
034: * For work added by the HSQL Development Group:
035: *
036: * Copyright (c) 2001-2005, The HSQL Development Group
037: * All rights reserved.
038: *
039: * Redistribution and use in source and binary forms, with or without
040: * modification, are permitted provided that the following conditions are met:
041: *
042: * Redistributions of source code must retain the above copyright notice, this
043: * list of conditions and the following disclaimer.
044: *
045: * Redistributions in binary form must reproduce the above copyright notice,
046: * this list of conditions and the following disclaimer in the documentation
047: * and/or other materials provided with the distribution.
048: *
049: * Neither the name of the HSQL Development Group nor the names of its
050: * contributors may be used to endorse or promote products derived from this
051: * software without specific prior written permission.
052: *
053: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
054: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
055: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
056: * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
057: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
058: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
059: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
060: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
061: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
062: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
063: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
064: */
065:
066: package org.hsqldb.lib;
067:
068: public class Sort {
069:
070: /**
071: * FastQSorts the [l,r] partition (inclusive) of the specfied array of
072: * Rows, using the comparator.
073: *
074: * Modified from the original method in Hypersonic with the addition of
075: * the comparator. (fredt@users)
076: *
077: * @author Thomas Mueller (Hypersonic SQL Group)
078: * @version 1.7.2
079: * @since 1.7.2
080: */
081: public static final void sort(Object[] w,
082: ObjectComparator comparator, int l, int r) {
083:
084: int i;
085: int j;
086: Object p;
087:
088: if (l > r) {
089: return;
090: }
091:
092: while (r - l > 10) {
093: i = (r + l) >> 1;
094:
095: if (comparator.compare(w[l], w[r]) > 0) {
096: swap(w, l, r);
097: }
098:
099: if (comparator.compare(w[i], w[l]) < 0) {
100: swap(w, l, i);
101: } else if (comparator.compare(w[i], w[r]) > 0) {
102: swap(w, i, r);
103: }
104:
105: j = r - 1;
106:
107: swap(w, i, j);
108:
109: p = w[j];
110: i = l;
111:
112: while (true) {
113: while (comparator.compare(w[++i], p) < 0) {
114: ;
115: }
116:
117: while (comparator.compare(w[--j], p) > 0) {
118: ;
119: }
120:
121: if (i >= j) {
122: break;
123: }
124:
125: swap(w, i, j);
126: }
127:
128: swap(w, i, r - 1);
129: sort(w, comparator, l, i - 1);
130:
131: l = i + 1;
132: }
133:
134: for (i = l + 1; i <= r; i++) {
135: Object t = w[i];
136:
137: for (j = i - 1; j >= l && comparator.compare(w[j], t) > 0; j--) {
138: w[j + 1] = w[j];
139: }
140:
141: w[j + 1] = t;
142: }
143: }
144:
145: /**
146: * Swaps the a'th and b'th elements of the specified Row array.
147: */
148: private static void swap(Object[] w, int a, int b) {
149:
150: Object t = w[a];
151:
152: w[a] = w[b];
153: w[b] = t;
154: }
155:
156: public static class StringComparator implements ObjectComparator {
157:
158: public int compare(Object a, Object b) {
159:
160: // handle nulls
161: if (a == b) {
162: return 0;
163: }
164:
165: if (a == null) {
166: return -1;
167: }
168:
169: if (b == null) {
170: return 1;
171: }
172:
173: return ((String) a).compareTo((String) b);
174: }
175: }
176: }
|