File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\tools\MultiDimension.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 */
7 package org.h2.tools;
8
9 import java.sql.PreparedStatement;
10 import java.sql.ResultSet;
11 import java.sql.SQLException;
12 import java.util.ArrayList;
13 import java.util.Collections;
14 import java.util.Comparator;
15 import org.h2.util.New;
16 import org.h2.util.StringUtils;
17
18 /**
19 * A tool to help an application execute multi-dimensional range queries.
20 * The algorithm used is database independent, the only requirement
21 * is that the engine supports a range index (for example b-tree).
22 */
23 public class MultiDimension implements Comparator<long[]> {
24
25 private static final MultiDimension INSTANCE = new MultiDimension();
26
27 protected MultiDimension() {
28 // don't allow construction by normal code
29 }
30
31 /**
32 * Get the singleton.
33 *
34 * @return the singleton
35 */
36 public static MultiDimension getInstance() {
37 return INSTANCE;
38 }
39
40 /**
41 * Normalize a value so that it is between the minimum and maximum for the
42 * given number of dimensions.
43 *
44 * @param dimensions the number of dimensions
45 * @param value the value (must be in the range min..max)
46 * @param min the minimum value
47 * @param max the maximum value (must be larger than min)
48 * @return the normalized value in the range 0..getMaxValue(dimensions)
49 */
50 public int normalize(int dimensions, double value, double min, double max) {
51 if (value < min || value > max) {
52 throw new IllegalArgumentException(min + "<" + value + "<" + max);
53 }
54 double x = (value - min) / (max - min);
55 return (int) (x * getMaxValue(dimensions));
56 }
57
58 /**
59 * Get the maximum value for the given dimension count. For two dimensions,
60 * each value must contain at most 32 bit, for 3: 21 bit, 4: 16 bit, 5: 12
61 * bit, 6: 10 bit, 7: 9 bit, 8: 8 bit.
62 *
63 * @param dimensions the number of dimensions
64 * @return the maximum value
65 */
66 public int getMaxValue(int dimensions) {
67 if (dimensions < 2 || dimensions > 32) {
68 throw new IllegalArgumentException("" + dimensions);
69 }
70 int bitsPerValue = getBitsPerValue(dimensions);
71 return (int) ((1L << bitsPerValue) - 1);
72 }
73
74 private static int getBitsPerValue(int dimensions) {
75 return Math.min(31, 64 / dimensions);
76 }
77
78 /**
79 * Convert the multi-dimensional value into a one-dimensional (scalar) value.
80 * This is done by interleaving the bits of the values.
81 * Each values must be between 0 (including) and the maximum value
82 * for the given number of dimensions (getMaxValue, excluding).
83 * To normalize values to this range, use the normalize function.
84 *
85 * @param values the multi-dimensional value
86 * @return the scalar value
87 */
88 public long interleave(int... values) {
89 int dimensions = values.length;
90 long max = getMaxValue(dimensions);
91 int bitsPerValue = getBitsPerValue(dimensions);
92 long x = 0;
93 for (int i = 0; i < dimensions; i++) {
94 long k = values[i];
95 if (k < 0 || k > max) {
96 throw new IllegalArgumentException(0 + "<" + k + "<" + max);
97 }
98 for (int b = 0; b < bitsPerValue; b++) {
99 x |= (k & (1L << b)) << (i + (dimensions - 1) * b);
100 }
101 }
102 return x;
103 }
104
105 /**
106 * Convert the two-dimensional value into a one-dimensional (scalar) value.
107 * This is done by interleaving the bits of the values.
108 * Each values must be between 0 (including) and the maximum value
109 * for the given number of dimensions (getMaxValue, excluding).
110 * To normalize values to this range, use the normalize function.
111 *
112 * @param x the value of the first dimension, normalized
113 * @param y the value of the second dimension, normalized
114 * @return the scalar value
115 */
116 public long interleave(int x, int y) {
117 if (x < 0) {
118 throw new IllegalArgumentException(0 + "<" + x);
119 }
120 if (y < 0) {
121 throw new IllegalArgumentException(0 + "<" + y);
122 }
123 long z = 0;
124 for (int i = 0; i < 32; i++) {
125 z |= (x & (1L << i)) << i;
126 z |= (y & (1L << i)) << (i + 1);
127 }
128 return z;
129 }
130
131 /**
132 * Gets one of the original multi-dimensional values from a scalar value.
133 *
134 * @param dimensions the number of dimensions
135 * @param scalar the scalar value
136 * @param dim the dimension of the returned value (starting from 0)
137 * @return the value
138 */
139 public int deinterleave(int dimensions, long scalar, int dim) {
140 int bitsPerValue = getBitsPerValue(dimensions);
141 int value = 0;
142 for (int i = 0; i < bitsPerValue; i++) {
143 value |= (scalar >> (dim + (dimensions - 1) * i)) & (1L << i);
144 }
145 return value;
146 }
147
148 /**
149 * Generates an optimized multi-dimensional range query.
150 * The query contains parameters. It can only be used with the H2 database.
151 *
152 * @param table the table name
153 * @param columns the list of columns
154 * @param scalarColumn the column name of the computed scalar column
155 * @return the query
156 */
157 public String generatePreparedQuery(String table, String scalarColumn, String[] columns) {
158 StringBuilder buff = new StringBuilder("SELECT D.* FROM ");
159 buff.append(StringUtils.quoteIdentifier(table)).
160 append(" D, TABLE(_FROM_ BIGINT=?, _TO_ BIGINT=?) WHERE ").
161 append(StringUtils.quoteIdentifier(scalarColumn)).
162 append(" BETWEEN _FROM_ AND _TO_");
163 for (String col : columns) {
164 buff.append(" AND ").append(StringUtils.quoteIdentifier(col)).append("+1 BETWEEN ?+1 AND ?+1");
165 }
166 return buff.toString();
167 }
168
169 /**
170 * Executes a prepared query that was generated using generatePreparedQuery.
171 *
172 * @param prep the prepared statement
173 * @param min the lower values
174 * @param max the upper values
175 * @return the result set
176 */
177 public ResultSet getResult(PreparedStatement prep, int[] min, int[] max) throws SQLException {
178 long[][] ranges = getMortonRanges(min, max);
179 int len = ranges.length;
180 Long[] from = new Long[len];
181 Long[] to = new Long[len];
182 for (int i = 0; i < len; i++) {
183 from[i] = Long.valueOf(ranges[i][0]);
184 to[i] = Long.valueOf(ranges[i][1]);
185 }
186 prep.setObject(1, from);
187 prep.setObject(2, to);
188 len = min.length;
189 for (int i = 0, idx = 3; i < len; i++) {
190 prep.setInt(idx++, min[i]);
191 prep.setInt(idx++, max[i]);
192 }
193 return prep.executeQuery();
194 }
195
196 /**
197 * Gets a list of ranges to be searched for a multi-dimensional range query
198 * where min &lt;= value &lt;= max. In most cases, the ranges will be larger
199 * than required in order to combine smaller ranges into one. Usually, about
200 * double as many points will be included in the resulting range.
201 *
202 * @param min the minimum value
203 * @param max the maximum value
204 * @return the list of ranges
205 */
206 private long[][] getMortonRanges(int[] min, int[] max) {
207 int len = min.length;
208 if (max.length != len) {
209 throw new IllegalArgumentException(len + "=" + max.length);
210 }
211 for (int i = 0; i < len; i++) {
212 if (min[i] > max[i]) {
213 int temp = min[i];
214 min[i] = max[i];
215 max[i] = temp;
216 }
217 }
218 int total = getSize(min, max, len);
219 ArrayList<long[]> list = New.arrayList();
220 addMortonRanges(list, min, max, len, 0);
221 combineEntries(list, total);
222 long[][] ranges = new long[list.size()][2];
223 list.toArray(ranges);
224 return ranges;
225 }
226
227 private static int getSize(int[] min, int[] max, int len) {
228 int size = 1;
229 for (int i = 0; i < len; i++) {
230 int diff = max[i] - min[i];
231 size *= diff + 1;
232 }
233 return size;
234 }
235
236 /**
237 * Combine entries if the size of the list is too large.
238 *
239 * @param list the size of the list
240 * @param total
241 */
242 private void combineEntries(ArrayList<long[]> list, int total) {
243 Collections.sort(list, this);
244 for (int minGap = 10; minGap < total; minGap += minGap / 2) {
245 for (int i = 0; i < list.size() - 1; i++) {
246 long[] current = list.get(i);
247 long[] next = list.get(i + 1);
248 if (current[1] + minGap >= next[0]) {
249 current[1] = next[1];
250 list.remove(i + 1);
251 i--;
252 }
253 }
254 int searched = 0;
255 for (long[] range : list) {
256 searched += range[1] - range[0] + 1;
257 }
258 if (searched > 2 * total || list.size() < 100) {
259 break;
260 }
261 }
262 }
263
264 public int compare(long[] a, long[] b) {
265 return a[0] > b[0] ? 1 : -1;
266 }
267
268 private void addMortonRanges(ArrayList<long[]> list, int[] min, int[] max, int len, int level) {
269 if (level > 100) {
270 throw new IllegalArgumentException("" + level);
271 }
272 int largest = 0, largestDiff = 0;
273 long size = 1;
274 for (int i = 0; i < len; i++) {
275 int diff = max[i] - min[i];
276 if (diff < 0) {
277 throw new IllegalArgumentException(""+ diff);
278 }
279 size *= diff + 1;
280 if (size < 0) {
281 throw new IllegalArgumentException("" + size);
282 }
283 if (diff > largestDiff) {
284 largestDiff = diff;
285 largest = i;
286 }
287 }
288 long low = interleave(min), high = interleave(max);
289 if (high < low) {
290 throw new IllegalArgumentException(high + "<" + low);
291 }
292 long range = high - low + 1;
293 if (range == size) {
294 long[] item = { low, high };
295 list.add(item);
296 } else {
297 int middle = findMiddle(min[largest], max[largest]);
298 int temp = max[largest];
299 max[largest] = middle;
300 addMortonRanges(list, min, max, len, level + 1);
301 max[largest] = temp;
302 temp = min[largest];
303 min[largest] = middle + 1;
304 addMortonRanges(list, min, max, len, level + 1);
305 min[largest] = temp;
306 }
307 }
308
309 private static int roundUp(int x, int blockSizePowerOf2) {
310 return (x + blockSizePowerOf2 - 1) & (-blockSizePowerOf2);
311 }
312
313 private static int findMiddle(int a, int b) {
314 int diff = b - a - 1;
315 if (diff == 0) {
316 return a;
317 }
318 if (diff == 1) {
319 return a + 1;
320 }
321 int scale = 0;
322 while ((1 << scale) < diff) {
323 scale++;
324 }
325 scale--;
326 int m = roundUp(a + 2, 1 << scale) - 1;
327 if (m <= a || m >= b) {
328 throw new IllegalArgumentException(a + "<" + m + "<" + b);
329 }
330 return m;
331 }
332
333 }
334