|
1
5 package org.h2.tools;
6
7 import java.util.ArrayList  ;
8 import java.util.Collections ;
9 import java.util.Comparator ;
10
11
16 public class MultiDimension {
17
18 private static MultiDimension instance = new MultiDimension();
19
20 private MultiDimension() {
21 }
22
23
28 public static MultiDimension getInstance() {
29 return instance;
30 }
31
32
42 public long interleave(int[] values) {
43 int dimensions = values.length;
44 int bitsPerValue = 64 / dimensions;
45 long max = 1L << bitsPerValue;
47 long x = 0;
48 for (int i = 0; i < dimensions; i++) {
49 long k = values[i];
50 if (k < 0 || k > max) {
51 throw new Error ("value out of range; value=" + values[i] + " min=0 max=" + max);
52 }
53 for (int b = 0; b < bitsPerValue; b++) {
54 x |= (k & (1L << b)) << (i + (dimensions-1) * b);
55 }
56 }
57 if (dimensions == 2) {
58 long xx = getMorton2(values[0], values[1]);
59 if(xx != x) {
60 throw new Error ("test");
61 }
62 }
63 return x;
64 }
65
66
74 public int deinterleave(long scalar, int dimensions, int dim) {
75 int bitsPerValue = 64 / dimensions;
76 int value = 0;
77 for(int i=0; i<bitsPerValue; i++) {
78 value |= (scalar >> (dim + (dimensions-1) * i)) & (1L << i);
79 }
80 return value;
81 }
82
83
84
92
93
94
104 public String getMultiDimensionalQuery(String table, String scalarColumn, String [] columns, int[] min, int[] max) {
105 long[][] ranges = getMortonRanges(min, max);
106 StringBuffer buff = new StringBuffer ("SELECT * FROM (");
107 for(int i=0; i<ranges.length; i++) {
108 if(i>0) {
109 buff.append(" UNION ALL ");
110 }
111 long minScalar = ranges[i][0];
112 long maxScalar = ranges[i][1];
113 buff.append("SELECT * FROM ").append(table).append(" WHERE ");
114 buff.append(scalarColumn).append(" BETWEEN ");
115 buff.append(minScalar).append(" AND ").append(maxScalar);
116 }
117 buff.append(") WHERE ");
118 for(int j=0; j<columns.length; j++) {
119 if(j>0) {
120 buff.append(" AND ");
121 }
122 buff.append(columns[j]).append(" BETWEEN ");
123 buff.append(min[j]).append(" AND ").append(max[j]);
124 }
125 return buff.toString();
126 }
127
128
138 public long[][] getMortonRanges(int[] min, int[] max) {
139 int len = min.length;
140 if(max.length != len) {
141 throw new Error ("dimensions mismatch");
142 }
143 for(int i=0; i<len; i++) {
144 if(min[i] > max[i]) {
145 int temp = min[i];
146 min[i] = max[i];
147 max[i] = temp;
148 }
149 }
150 int total = getSize(min, max, len);
151 ArrayList list = new ArrayList ();
152 addMortonRanges(list, min, max, len, 0);
153 optimize(list, total);
154 long[][] ranges = new long[list.size()][2];
155 list.toArray(ranges);
156 return ranges;
157 }
158
159 private long getMorton2(int x, int y) {
160 long z = 0;
161 for (int i = 0; i < 32; i++) {
162 z |= (x & (1L << i)) << (i);
163 z |= (y & (1L << i)) << (i + 1);
164 }
165 return z;
166 }
167
168 private int getSize(int[] min, int[] max, int len) {
169 int size = 1;
170 for(int i=0; i<len; i++) {
171 int diff = max[i] - min[i];
172 size *= (diff + 1);
173 }
174 return size;
175 }
176
177 private void optimize(ArrayList list, int total) {
178 Collections.sort(list, new Comparator () {
179 public int compare(Object a, Object b) {
180 long[] la = (long[]) a;
181 long[] lb = (long[]) b;
182 return la[0] > lb[0] ? 1 : -1;
183 }
184 });
185 int minGap = 10;
186 for(;; minGap+=(minGap/2) ) {
187 for(int i=0; i<list.size() - 1; i++) {
188 long[] current = (long[]) list.get(i);
189 long[] next = (long[]) list.get(i+1);
190 if(current[1]+minGap >= next[0]) {
191 current[1] = next[1];
192 list.remove(i+1);
193 i--;
194 }
195 }
196 int searched = 0;
197 for(int j=0; j<list.size(); j++) {
198 long[] range = (long[]) list.get(j);
199 searched += range[1]-range[0]+1;
200 }
201 if(searched > 2*total || list.size()<3 ) {
202 break;
203 }
204 }
205 }
206
207 private void addMortonRanges(ArrayList list, int[] min, int[] max, int len, int level) {
208 if(level > 100) {
209 throw new Error ("Stop");
210 }
211 int largest = 0, largestDiff = 0;
212 long size = 1;
213 for(int i=0; i<len; i++) {
214 int diff = max[i] - min[i];
215 if(diff < 0) {
216 throw new Error ("Stop");
217 }
218 size *= (diff + 1);
219 if(size < 0) {
220 throw new Error ("Stop");
221 }
222 if(diff > largestDiff) {
223 largestDiff = diff;
224 largest = i;
225 }
226 }
227 long low = interleave(min), high = interleave(max);
228 if(high < low) {
229 throw new Error ("Stop");
230 }
231 long range = high - low + 1;
232 if(range == size) {
233 long[] item = new long[] { low, high };
234 list.add(item);
235 } else {
236 int middle = findMiddle(min[largest], max[largest]);
237 int temp = max[largest];
238 max[largest] = middle;
239 addMortonRanges(list, min, max, len, level+1);
240 max[largest] = temp;
241 temp = min[largest];
242 min[largest] = middle+1;
243 addMortonRanges(list, min, max, len, level+1);
244 min[largest] = temp;
245 }
246 }
247
248 private int roundUp(int x, int blockSizePowerOf2) {
249 return (x + blockSizePowerOf2 - 1) & (-blockSizePowerOf2);
250 }
251
252 private int findMiddle(int a, int b) {
253 int diff = b - a - 1;
254 if(diff == 0) {
255 return a;
256 }
257 if(diff == 1) {
258 return a + 1;
259 }
260 int scale = 0;
261 while ((1 << scale) < diff) {
262 scale++;
263 }
264 scale--;
265 int m = roundUp(a + 2, 1 << scale) - 1;
266 if(m<=a || m>=b) {
267 throw new Error ("stop");
268 }
269 return m;
270 }
271
272 }
273 |
Popular Tags |
Java API By Example, From Geeks To Geeks.