1 | /* |
2 | * Copyright 2004-2014 H2 Group. Multiple-Licensed under the MPL 2.0, |
3 | * and the EPL 1.0 (http://h2database.com/html/license.html). |
4 | * Initial Developer: H2 Group |
5 | */ |
6 | package org.h2.result; |
7 | |
8 | import java.util.ArrayList; |
9 | import java.util.Collections; |
10 | import java.util.Comparator; |
11 | |
12 | import org.h2.command.dml.SelectOrderBy; |
13 | import org.h2.engine.Database; |
14 | import org.h2.engine.SysProperties; |
15 | import org.h2.expression.Expression; |
16 | import org.h2.expression.ExpressionColumn; |
17 | import org.h2.table.Column; |
18 | import org.h2.table.TableFilter; |
19 | import org.h2.util.StatementBuilder; |
20 | import org.h2.util.StringUtils; |
21 | import org.h2.util.Utils; |
22 | import org.h2.value.Value; |
23 | import org.h2.value.ValueNull; |
24 | |
25 | /** |
26 | * A sort order represents an ORDER BY clause in a query. |
27 | */ |
28 | public class SortOrder implements Comparator<Value[]> { |
29 | |
30 | /** |
31 | * This bit mask means the values should be sorted in ascending order. |
32 | */ |
33 | public static final int ASCENDING = 0; |
34 | |
35 | /** |
36 | * This bit mask means the values should be sorted in descending order. |
37 | */ |
38 | public static final int DESCENDING = 1; |
39 | |
40 | /** |
41 | * This bit mask means NULLs should be sorted before other data, no matter |
42 | * if ascending or descending order is used. |
43 | */ |
44 | public static final int NULLS_FIRST = 2; |
45 | |
46 | /** |
47 | * This bit mask means NULLs should be sorted after other data, no matter |
48 | * if ascending or descending order is used. |
49 | */ |
50 | public static final int NULLS_LAST = 4; |
51 | |
52 | /** |
53 | * The default sort order for NULL. |
54 | */ |
55 | private static final int DEFAULT_NULL_SORT = |
56 | SysProperties.SORT_NULLS_HIGH ? 1 : -1; |
57 | |
58 | private final Database database; |
59 | |
60 | /** |
61 | * The column indexes of the order by expressions within the query. |
62 | */ |
63 | private final int[] queryColumnIndexes; |
64 | |
65 | /** |
66 | * The sort type bit mask (DESCENDING, NULLS_FIRST, NULLS_LAST). |
67 | */ |
68 | private final int[] sortTypes; |
69 | |
70 | /** |
71 | * The order list. |
72 | */ |
73 | private final ArrayList<SelectOrderBy> orderList; |
74 | |
75 | /** |
76 | * Construct a new sort order object. |
77 | * |
78 | * @param database the database |
79 | * @param queryColumnIndexes the column index list |
80 | * @param sortType the sort order bit masks |
81 | * @param orderList the original query order list (if this is a query) |
82 | */ |
83 | public SortOrder(Database database, int[] queryColumnIndexes, |
84 | int[] sortType, ArrayList<SelectOrderBy> orderList) { |
85 | this.database = database; |
86 | this.queryColumnIndexes = queryColumnIndexes; |
87 | this.sortTypes = sortType; |
88 | this.orderList = orderList; |
89 | } |
90 | |
91 | /** |
92 | * Create the SQL snippet that describes this sort order. |
93 | * This is the SQL snippet that usually appears after the ORDER BY clause. |
94 | * |
95 | * @param list the expression list |
96 | * @param visible the number of columns in the select list |
97 | * @return the SQL snippet |
98 | */ |
99 | public String getSQL(Expression[] list, int visible) { |
100 | StatementBuilder buff = new StatementBuilder(); |
101 | int i = 0; |
102 | for (int idx : queryColumnIndexes) { |
103 | buff.appendExceptFirst(", "); |
104 | if (idx < visible) { |
105 | buff.append(idx + 1); |
106 | } else { |
107 | buff.append('=').append(StringUtils.unEnclose(list[idx].getSQL())); |
108 | } |
109 | int type = sortTypes[i++]; |
110 | if ((type & DESCENDING) != 0) { |
111 | buff.append(" DESC"); |
112 | } |
113 | if ((type & NULLS_FIRST) != 0) { |
114 | buff.append(" NULLS FIRST"); |
115 | } else if ((type & NULLS_LAST) != 0) { |
116 | buff.append(" NULLS LAST"); |
117 | } |
118 | } |
119 | return buff.toString(); |
120 | } |
121 | |
122 | /** |
123 | * Compare two expressions where one of them is NULL. |
124 | * |
125 | * @param aNull whether the first expression is null |
126 | * @param sortType the sort bit mask to use |
127 | * @return the result of the comparison (-1 meaning the first expression |
128 | * should appear before the second, 0 if they are equal) |
129 | */ |
130 | public static int compareNull(boolean aNull, int sortType) { |
131 | if ((sortType & NULLS_FIRST) != 0) { |
132 | return aNull ? -1 : 1; |
133 | } else if ((sortType & NULLS_LAST) != 0) { |
134 | return aNull ? 1 : -1; |
135 | } else { |
136 | // see also JdbcDatabaseMetaData.nullsAreSorted* |
137 | int comp = aNull ? DEFAULT_NULL_SORT : -DEFAULT_NULL_SORT; |
138 | return (sortType & DESCENDING) == 0 ? comp : -comp; |
139 | } |
140 | } |
141 | |
142 | /** |
143 | * Compare two expression lists. |
144 | * |
145 | * @param a the first expression list |
146 | * @param b the second expression list |
147 | * @return the result of the comparison |
148 | */ |
149 | @Override |
150 | public int compare(Value[] a, Value[] b) { |
151 | for (int i = 0, len = queryColumnIndexes.length; i < len; i++) { |
152 | int idx = queryColumnIndexes[i]; |
153 | int type = sortTypes[i]; |
154 | Value ao = a[idx]; |
155 | Value bo = b[idx]; |
156 | boolean aNull = ao == ValueNull.INSTANCE, bNull = bo == ValueNull.INSTANCE; |
157 | if (aNull || bNull) { |
158 | if (aNull == bNull) { |
159 | continue; |
160 | } |
161 | return compareNull(aNull, type); |
162 | } |
163 | int comp = database.compare(ao, bo); |
164 | if (comp != 0) { |
165 | return (type & DESCENDING) == 0 ? comp : -comp; |
166 | } |
167 | } |
168 | return 0; |
169 | } |
170 | |
171 | /** |
172 | * Sort a list of rows. |
173 | * |
174 | * @param rows the list of rows |
175 | */ |
176 | public void sort(ArrayList<Value[]> rows) { |
177 | Collections.sort(rows, this); |
178 | } |
179 | |
180 | /** |
181 | * Sort a list of rows using offset and limit. |
182 | * |
183 | * @param rows the list of rows |
184 | * @param offset the offset |
185 | * @param limit the limit |
186 | */ |
187 | public void sort(ArrayList<Value[]> rows, int offset, int limit) { |
188 | int rowsSize = rows.size(); |
189 | if (rows.isEmpty() || offset >= rowsSize || limit == 0) { |
190 | return; |
191 | } |
192 | if (offset < 0) { |
193 | offset = 0; |
194 | } |
195 | if (offset + limit > rowsSize) { |
196 | limit = rowsSize - offset; |
197 | } |
198 | if (limit == 1 && offset == 0) { |
199 | rows.set(0, Collections.min(rows, this)); |
200 | return; |
201 | } |
202 | Value[][] arr = rows.toArray(new Value[rowsSize][]); |
203 | Utils.sortTopN(arr, offset, limit, this); |
204 | for (int i = 0, end = Math.min(offset + limit, rowsSize); i < end; i++) { |
205 | rows.set(i, arr[i]); |
206 | } |
207 | } |
208 | |
209 | /** |
210 | * Get the column index list. This is the column indexes of the order by |
211 | * expressions within the query. |
212 | * <p> |
213 | * For the query "select name, id from test order by id, name" this is {1, |
214 | * 0} as the first order by expression (the column "id") is the second |
215 | * column of the query, and the second order by expression ("name") is the |
216 | * first column of the query. |
217 | * |
218 | * @return the list |
219 | */ |
220 | public int[] getQueryColumnIndexes() { |
221 | return queryColumnIndexes; |
222 | } |
223 | |
224 | /** |
225 | * Get the column for the given table filter, if the sort column is for this |
226 | * filter. |
227 | * |
228 | * @param index the column index (0, 1,..) |
229 | * @param filter the table filter |
230 | * @return the column, or null |
231 | */ |
232 | public Column getColumn(int index, TableFilter filter) { |
233 | if (orderList == null) { |
234 | return null; |
235 | } |
236 | SelectOrderBy order = orderList.get(index); |
237 | Expression expr = order.expression; |
238 | if (expr == null) { |
239 | return null; |
240 | } |
241 | expr = expr.getNonAliasExpression(); |
242 | if (expr.isConstant()) { |
243 | return null; |
244 | } |
245 | if (!(expr instanceof ExpressionColumn)) { |
246 | return null; |
247 | } |
248 | ExpressionColumn exprCol = (ExpressionColumn) expr; |
249 | if (exprCol.getTableFilter() != filter) { |
250 | return null; |
251 | } |
252 | return exprCol.getColumn(); |
253 | } |
254 | |
255 | /** |
256 | * Get the sort order bit masks. |
257 | * |
258 | * @return the list |
259 | */ |
260 | public int[] getSortTypes() { |
261 | return sortTypes; |
262 | } |
263 | |
264 | } |