001: /*
002: * Copyright (c) 1998-2008 Caucho Technology -- all rights reserved
003: *
004: * This file is part of Resin(R) Open Source
005: *
006: * Each copy or derived work must preserve the copyright notice and this
007: * notice unmodified.
008: *
009: * Resin Open Source is free software; you can redistribute it and/or modify
010: * it under the terms of the GNU General Public License as published by
011: * the Free Software Foundation; either version 2 of the License, or
012: * (at your option) any later version.
013: *
014: * Resin Open Source is distributed in the hope that it will be useful,
015: * but WITHOUT ANY WARRANTY; without even the implied warranty of
016: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE, or any warranty
017: * of NON-INFRINGEMENT. See the GNU General Public License for more
018: * details.
019: *
020: * You should have received a copy of the GNU General Public License
021: * along with Resin Open Source; if not, write to the
022: * Free SoftwareFoundation, Inc.
023: * 59 Temple Place, Suite 330
024: * Boston, MA 02111-1307 USA
025: *
026: * @author Scott Ferguson
027: */
028:
029: package com.caucho.db.sql;
030:
031: import com.caucho.log.Log;
032: import com.caucho.util.IntArray;
033:
034: import java.sql.SQLException;
035: import java.util.logging.Logger;
036:
037: abstract class Order {
038: private static final Logger log = Log.open(Order.class);
039:
040: private boolean _isAscending = true;
041:
042: protected Order _next;
043:
044: /**
045: * Set true for ascending.
046: */
047: public boolean isAscending() {
048: return _isAscending;
049: }
050:
051: /**
052: * Set true for ascending.
053: */
054: public void setAscending(boolean isAscending) {
055: _isAscending = isAscending;
056: }
057:
058: /**
059: * Append the next value.
060: */
061: static Order append(Order order, Order next) {
062: if (order == null)
063: return next;
064: else {
065: order._next = next;
066: return order;
067: }
068: }
069:
070: abstract public int compare(SelectResult result, int indexA,
071: int indexB) throws SQLException;
072:
073: /**
074: * Sorts the database result.
075: */
076: public void sort(SelectResult result, IntArray rowArray)
077: throws SQLException {
078: int[] rows = rowArray.getArray();
079: int size = rowArray.size();
080:
081: sort(result, rows, 0, size);
082: }
083:
084: /**
085: * Sorts a subset of the database result.
086: */
087: private void sort(SelectResult result, int[] rows, int offset,
088: int length) throws SQLException {
089: if (length > 3) {
090: int head = offset;
091: int right = offset + length - 1;
092: int tail = right;
093: int pivot = offset + length / 2;
094: int pivotIndex = rows[pivot];
095:
096: // swap(pivot, right)
097: int temp = rows[right];
098: rows[right] = pivotIndex;
099: rows[pivot] = temp;
100:
101: --tail;
102:
103: for (;;) {
104:
105: while (head <= tail
106: && compare(result, rows[head], pivotIndex) < 0) {
107: ++head;
108: }
109:
110: while (head <= tail
111: && compare(result, rows[tail], pivotIndex) > 0) {
112: --tail;
113: }
114:
115: if (head > tail) {
116: break;
117: }
118:
119: // swap(head++, tail--)
120: temp = rows[head];
121: rows[head++] = rows[tail];
122: rows[tail--] = temp;
123: }
124:
125: if (compare(result, rows[head], pivotIndex) > 0) {
126: // swap(head, right)
127: temp = rows[head];
128: rows[head] = rows[right];
129: rows[right] = temp;
130: }
131:
132: if (offset < head) {
133: sort(result, rows, offset, head - offset);
134: }
135:
136: if (right > head) {
137: sort(result, rows, head + 1, right - head);
138: }
139: } else if (length == 3) {
140: int indexA = rows[offset + 0];
141: int indexB = rows[offset + 1];
142: int indexC = rows[offset + 2];
143:
144: if (compare(result, indexB, indexA) < 0) {
145: int temp = indexA;
146: indexA = indexB;
147: indexB = temp;
148: }
149:
150: // A <= B <= C
151: if (compare(result, indexB, indexC) <= 0) {
152: }
153: // C < A <= B
154: else if (compare(result, indexC, indexA) < 0) {
155: int temp = indexC;
156: indexC = indexB;
157: indexB = indexA;
158: indexA = temp;
159: }
160: // A <= C < B
161: else {
162: int temp = indexC;
163: indexC = indexB;
164: indexB = temp;
165: }
166:
167: rows[offset + 0] = indexA;
168: rows[offset + 1] = indexB;
169: rows[offset + 2] = indexC;
170: } else if (length == 2) {
171: int indexA = rows[offset];
172: int indexB = rows[offset + 1];
173:
174: if (compare(result, indexB, indexA) < 0) {
175: int temp = indexB;
176: indexB = indexA;
177: indexA = temp;
178: }
179:
180: rows[offset + 0] = indexA;
181: rows[offset + 1] = indexB;
182: } else {
183: // nothing to do
184: }
185: }
186: }
|