001: /*
002: * Copyright 2004-2008 H2 Group. Licensed under the H2 License, Version 1.0
003: * (http://h2database.com/html/license.html).
004: * Initial Developer: H2 Group
005: */
006: package org.h2.result;
007:
008: import java.sql.SQLException;
009:
010: import org.h2.engine.Database;
011: import org.h2.expression.Expression;
012: import org.h2.util.ObjectArray;
013: import org.h2.util.RandomUtils;
014: import org.h2.util.StringUtils;
015: import org.h2.value.Value;
016: import org.h2.value.ValueNull;
017:
018: /**
019: * A sort order represents an ORDER BY clause in a query.
020: */
021: public class SortOrder {
022: public static final int ASCENDING = 0, DESCENDING = 1;
023: public static final int NULLS_FIRST = 2, NULLS_LAST = 4;
024:
025: private Database database;
026: private int len;
027: private int[] indexes;
028: private int[] sortTypes;
029:
030: public SortOrder(Database database, int[] index, int[] sortType) {
031: this .database = database;
032: this .indexes = index;
033: this .sortTypes = sortType;
034: len = index.length;
035: }
036:
037: public String getSQL(Expression[] list, int visible) {
038: StringBuffer buff = new StringBuffer();
039: for (int i = 0; i < len; i++) {
040: if (i > 0) {
041: buff.append(", ");
042: }
043: int idx = indexes[i];
044: if (idx < visible) {
045: buff.append(idx + 1);
046: } else {
047: buff.append("=");
048: buff.append(StringUtils.unEnclose(list[idx].getSQL()));
049: }
050: int type = sortTypes[i];
051: if ((type & DESCENDING) != 0) {
052: buff.append(" DESC");
053: }
054: if ((type & NULLS_FIRST) != 0) {
055: buff.append(" NULLS FIRST");
056: } else if ((type & NULLS_LAST) != 0) {
057: buff.append(" NULLS LAST");
058: }
059: }
060: return buff.toString();
061: }
062:
063: public static int compareNull(boolean aNull, boolean bNull, int type) {
064: if ((type & NULLS_FIRST) != 0) {
065: return aNull ? -1 : 1;
066: } else if ((type & NULLS_LAST) != 0) {
067: return aNull ? 1 : -1;
068: } else {
069: // see also JdbcDatabaseMetaData.nullsAreSorted*
070: int comp = aNull ? -1 : 1;
071: return (type & DESCENDING) == 0 ? comp : -comp;
072: }
073: }
074:
075: public int compare(Value[] a, Value[] b) throws SQLException {
076: for (int i = 0; i < len; i++) {
077: int idx = indexes[i];
078: int type = sortTypes[i];
079: Value ao = a[idx];
080: Value bo = b[idx];
081: boolean aNull = ao == ValueNull.INSTANCE, bNull = bo == ValueNull.INSTANCE;
082: if (aNull || bNull) {
083: if (aNull == bNull) {
084: continue;
085: }
086: return compareNull(aNull, bNull, type);
087: }
088: int comp = database.compare(ao, bo);
089: if (comp != 0) {
090: return (type & DESCENDING) == 0 ? comp : -comp;
091: }
092: }
093: return 0;
094: }
095:
096: public void sort(ObjectArray rows) throws SQLException {
097: sort(rows, 0, rows.size() - 1);
098: }
099:
100: private void swap(ObjectArray rows, int a, int b) {
101: Object t = rows.get(a);
102: rows.set(a, rows.get(b));
103: rows.set(b, t);
104: }
105:
106: private void sort(ObjectArray rows, int l, int r)
107: throws SQLException {
108: // quicksort
109: int i, j;
110: while (r - l > 10) {
111: // randomized pivot to avoid worst case
112: i = RandomUtils.nextInt(r - l - 4) + l + 2;
113: if (compare((Value[]) rows.get(l), (Value[]) rows.get(r)) > 0) {
114: swap(rows, l, r);
115: }
116: if (compare((Value[]) rows.get(i), (Value[]) rows.get(l)) < 0) {
117: swap(rows, l, i);
118: } else if (compare((Value[]) rows.get(i), (Value[]) rows
119: .get(r)) > 0) {
120: swap(rows, i, r);
121: }
122: j = r - 1;
123: swap(rows, i, j);
124: Value[] p = (Value[]) rows.get(j);
125: i = l;
126: while (true) {
127: do {
128: ++i;
129: } while (compare((Value[]) rows.get(i), p) < 0);
130: do {
131: --j;
132: } while (compare((Value[]) rows.get(j), p) > 0);
133: if (i >= j) {
134: break;
135: }
136: swap(rows, i, j);
137: }
138: swap(rows, i, r - 1);
139: sort(rows, l, i - 1);
140: l = i + 1;
141: }
142: for (i = l + 1; i <= r; i++) {
143: Value[] t = (Value[]) rows.get(i);
144: for (j = i - 1; j >= l
145: && (compare((Value[]) rows.get(j), t) > 0); j--) {
146: rows.set(j + 1, rows.get(j));
147: }
148: rows.set(j + 1, t);
149: }
150: }
151:
152: public int[] getIndexes() {
153: return indexes;
154: }
155:
156: public int[] getSortTypes() {
157: return sortTypes;
158: }
159:
160: }
|