EMMA Coverage Report (generated Sun Mar 01 22:06:14 CET 2015)
[all classes][org.h2.tools]

COVERAGE SUMMARY FOR SOURCE FILE [MultiDimension.java]

nameclass, %method, %block, %line, %
MultiDimension.java100% (1/1)100% (18/18)88%  (744/848)93%  (130.5/140)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class MultiDimension100% (1/1)100% (18/18)88%  (744/848)93%  (130.5/140)
getMortonRanges (int [], int []): long [][] 100% (1/1)63%  (50/79)73%  (11/15)
findMiddle (int, int): int 100% (1/1)71%  (45/63)92%  (12/13)
addMortonRanges (ArrayList, int [], int [], int, int): void 100% (1/1)73%  (135/185)88%  (28/32)
combineEntries (ArrayList, int): void 100% (1/1)93%  (92/99)97%  (15.5/16)
<static initializer> 100% (1/1)100% (5/5)100% (1/1)
MultiDimension (): void 100% (1/1)100% (3/3)100% (2/2)
compare (long [], long []): int 100% (1/1)100% (12/12)100% (1/1)
deinterleave (int, long, int): int 100% (1/1)100% (32/32)100% (5/5)
generatePreparedQuery (String, String, String []): String 100% (1/1)100% (45/45)100% (5/5)
getBitsPerValue (int): int 100% (1/1)100% (6/6)100% (1/1)
getInstance (): MultiDimension 100% (1/1)100% (2/2)100% (1/1)
getMaxValue (int): int 100% (1/1)100% (28/28)100% (4/4)
getResult (PreparedStatement, int [], int []): ResultSet 100% (1/1)100% (76/76)100% (14/14)
getSize (int [], int [], int): int 100% (1/1)100% (25/25)100% (5/5)
interleave (int []): long 100% (1/1)100% (74/74)100% (11/11)
interleave (int, int): long 100% (1/1)100% (63/63)100% (9/9)
normalize (int, double, double, double): int 100% (1/1)100% (42/42)100% (4/4)
roundUp (int, int): int 100% (1/1)100% (9/9)100% (1/1)

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 */
6package org.h2.tools;
7 
8import java.sql.PreparedStatement;
9import java.sql.ResultSet;
10import java.sql.SQLException;
11import java.util.ArrayList;
12import java.util.Collections;
13import java.util.Comparator;
14import org.h2.util.New;
15import org.h2.util.StringUtils;
16 
17/**
18 * A tool to help an application execute multi-dimensional range queries.
19 * The algorithm used is database independent, the only requirement
20 * is that the engine supports a range index (for example b-tree).
21 */
22public class MultiDimension implements Comparator<long[]> {
23 
24    private static final MultiDimension INSTANCE = new MultiDimension();
25 
26    protected MultiDimension() {
27        // don't allow construction by normal code
28        // but allow tests
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)
80     * value. This is done by interleaving the bits of the values. Each values
81     * must be between 0 (including) and the maximum value for the given number
82     * of dimensions (getMaxValue, excluding). To normalize values to this
83     * 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. The query contains
150     * 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,
158            String[] columns) {
159        StringBuilder buff = new StringBuilder("SELECT D.* FROM ");
160        buff.append(StringUtils.quoteIdentifier(table)).
161            append(" D, TABLE(_FROM_ BIGINT=?, _TO_ BIGINT=?) WHERE ").
162            append(StringUtils.quoteIdentifier(scalarColumn)).
163            append(" BETWEEN _FROM_ AND _TO_");
164        for (String col : columns) {
165            buff.append(" AND ").append(StringUtils.quoteIdentifier(col)).
166                append("+1 BETWEEN ?+1 AND ?+1");
167        }
168        return buff.toString();
169    }
170 
171    /**
172     * Executes a prepared query that was generated using generatePreparedQuery.
173     *
174     * @param prep the prepared statement
175     * @param min the lower values
176     * @param max the upper values
177     * @return the result set
178     */
179    public ResultSet getResult(PreparedStatement prep, int[] min, int[] max)
180            throws SQLException {
181        long[][] ranges = getMortonRanges(min, max);
182        int len = ranges.length;
183        Long[] from = new Long[len];
184        Long[] to = new Long[len];
185        for (int i = 0; i < len; i++) {
186            from[i] = Long.valueOf(ranges[i][0]);
187            to[i] = Long.valueOf(ranges[i][1]);
188        }
189        prep.setObject(1, from);
190        prep.setObject(2, to);
191        len = min.length;
192        for (int i = 0, idx = 3; i < len; i++) {
193            prep.setInt(idx++, min[i]);
194            prep.setInt(idx++, max[i]);
195        }
196        return prep.executeQuery();
197    }
198 
199    /**
200     * Gets a list of ranges to be searched for a multi-dimensional range query
201     * where min &lt;= value &lt;= max. In most cases, the ranges will be larger
202     * than required in order to combine smaller ranges into one. Usually, about
203     * double as many points will be included in the resulting range.
204     *
205     * @param min the minimum value
206     * @param max the maximum value
207     * @return the list of ranges (low, high pairs)
208     */
209    private long[][] getMortonRanges(int[] min, int[] max) {
210        int len = min.length;
211        if (max.length != len) {
212            throw new IllegalArgumentException(len + "=" + max.length);
213        }
214        for (int i = 0; i < len; i++) {
215            if (min[i] > max[i]) {
216                int temp = min[i];
217                min[i] = max[i];
218                max[i] = temp;
219            }
220        }
221        int total = getSize(min, max, len);
222        ArrayList<long[]> list = New.arrayList();
223        addMortonRanges(list, min, max, len, 0);
224        combineEntries(list, total);
225        long[][] ranges = new long[list.size()][2];
226        list.toArray(ranges);
227        return ranges;
228    }
229 
230    private static int getSize(int[] min, int[] max, int len) {
231        int size = 1;
232        for (int i = 0; i < len; i++) {
233            int diff = max[i] - min[i];
234            size *= diff + 1;
235        }
236        return size;
237    }
238 
239    /**
240     * Combine entries if the size of the list is too large.
241     *
242     * @param list list of pairs(low, high)
243     * @param total product of the gap lengths
244     */
245    private void combineEntries(ArrayList<long[]> list, int total) {
246        Collections.sort(list, this);
247        for (int minGap = 10; minGap < total; minGap += minGap / 2) {
248            for (int i = 0; i < list.size() - 1; i++) {
249                long[] current = list.get(i);
250                long[] next = list.get(i + 1);
251                if (current[1] + minGap >= next[0]) {
252                    current[1] = next[1];
253                    list.remove(i + 1);
254                    i--;
255                }
256            }
257            int searched = 0;
258            for (long[] range : list) {
259                searched += range[1] - range[0] + 1;
260            }
261            if (searched > 2 * total || list.size() < 100) {
262                break;
263            }
264        }
265    }
266 
267    @Override
268    public int compare(long[] a, long[] b) {
269        return a[0] > b[0] ? 1 : -1;
270    }
271 
272    private void addMortonRanges(ArrayList<long[]> list, int[] min, int[] max,
273            int len, int level) {
274        if (level > 100) {
275            throw new IllegalArgumentException("" + level);
276        }
277        int largest = 0, largestDiff = 0;
278        long size = 1;
279        for (int i = 0; i < len; i++) {
280            int diff = max[i] - min[i];
281            if (diff < 0) {
282                throw new IllegalArgumentException(""+ diff);
283            }
284            size *= diff + 1;
285            if (size < 0) {
286                throw new IllegalArgumentException("" + size);
287            }
288            if (diff > largestDiff) {
289                largestDiff = diff;
290                largest = i;
291            }
292        }
293        long low = interleave(min), high = interleave(max);
294        if (high < low) {
295            throw new IllegalArgumentException(high + "<" + low);
296        }
297        long range = high - low + 1;
298        if (range == size) {
299            long[] item = { low, high };
300            list.add(item);
301        } else {
302            int middle = findMiddle(min[largest], max[largest]);
303            int temp = max[largest];
304            max[largest] = middle;
305            addMortonRanges(list, min, max, len, level + 1);
306            max[largest] = temp;
307            temp = min[largest];
308            min[largest] = middle + 1;
309            addMortonRanges(list, min, max, len, level + 1);
310            min[largest] = temp;
311        }
312    }
313 
314    private static int roundUp(int x, int blockSizePowerOf2) {
315        return (x + blockSizePowerOf2 - 1) & (-blockSizePowerOf2);
316    }
317 
318    private static int findMiddle(int a, int b) {
319        int diff = b - a - 1;
320        if (diff == 0) {
321            return a;
322        }
323        if (diff == 1) {
324            return a + 1;
325        }
326        int scale = 0;
327        while ((1 << scale) < diff) {
328            scale++;
329        }
330        scale--;
331        int m = roundUp(a + 2, 1 << scale) - 1;
332        if (m <= a || m >= b) {
333            throw new IllegalArgumentException(a + "<" + m + "<" + b);
334        }
335        return m;
336    }
337 
338}

[all classes][org.h2.tools]
EMMA 2.0.5312 (C) Vladimir Roubtsov