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

COVERAGE SUMMARY FOR SOURCE FILE [SpatialDataType.java]

nameclass, %method, %block, %line, %
SpatialDataType.java100% (1/1)94%  (16/17)97%  (691/714)98%  (131/134)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class SpatialDataType100% (1/1)94%  (16/17)97%  (691/714)98%  (131/134)
compare (Object, Object): int 0%   (0/1)0%   (0/22)0%   (0/3)
SpatialDataType (int): void 100% (1/1)96%  (23/24)99%  (4/4)
contains (Object, Object): boolean 100% (1/1)100% (34/34)100% (6/6)
createBoundingBox (Object): Object 100% (1/1)100% (41/41)100% (6/6)
equals (Object, Object): boolean 100% (1/1)100% (16/16)100% (3/3)
getAreaIncrease (Object, Object): float 100% (1/1)100% (78/78)100% (16/16)
getCombinedArea (Object, Object): float 100% (1/1)100% (40/40)100% (8/8)
getExtremes (ArrayList): int [] 100% (1/1)100% (168/168)100% (34/34)
getMemory (Object): int 100% (1/1)100% (7/7)100% (1/1)
increaseBounds (Object, Object): void 100% (1/1)100% (35/35)100% (6/6)
increaseMaxInnerBounds (Object, Object): void 100% (1/1)100% (35/35)100% (6/6)
isInside (Object, Object): boolean 100% (1/1)100% (34/34)100% (6/6)
isOverlap (Object, Object): boolean 100% (1/1)100% (34/34)100% (6/6)
read (ByteBuffer): Object 100% (1/1)100% (55/55)100% (11/11)
read (ByteBuffer, Object [], int, boolean): void 100% (1/1)100% (14/14)100% (3/3)
write (WriteBuffer, Object [], int, boolean): void 100% (1/1)100% (14/14)100% (3/3)
write (WriteBuffer, Object): void 100% (1/1)100% (63/63)100% (12/12)

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.mvstore.rtree;
7 
8import java.nio.ByteBuffer;
9import java.util.ArrayList;
10import org.h2.mvstore.DataUtils;
11import org.h2.mvstore.WriteBuffer;
12import org.h2.mvstore.type.DataType;
13 
14/**
15 * A spatial data type. This class supports up to 31 dimensions. Each dimension
16 * can have a minimum and a maximum value of type float. For each dimension, the
17 * maximum value is only stored when it is not the same as the minimum.
18 */
19public class SpatialDataType implements DataType {
20 
21    private final int dimensions;
22 
23    public SpatialDataType(int dimensions) {
24        // Because of how we are storing the
25        // min-max-flag in the read/write method
26        // the number of dimensions must be < 32.
27        DataUtils.checkArgument(
28                dimensions >= 1 && dimensions < 32,
29                "Dimensions must be between 1 and 31, is {0}", dimensions);
30        this.dimensions = dimensions;
31    }
32 
33    @Override
34    public int compare(Object a, Object b) {
35        long la = ((SpatialKey) a).getId();
36        long lb = ((SpatialKey) b).getId();
37        return la < lb ? -1 : la > lb ? 1 : 0;
38    }
39 
40    /**
41     * Check whether two spatial values are equal.
42     *
43     * @param a the first value
44     * @param b the second value
45     * @return true if they are equal
46     */
47    public boolean equals(Object a, Object b) {
48        long la = ((SpatialKey) a).getId();
49        long lb = ((SpatialKey) b).getId();
50        return la == lb;
51    }
52 
53    @Override
54    public int getMemory(Object obj) {
55        return 40 + dimensions * 4;
56    }
57 
58    @Override
59    public void read(ByteBuffer buff, Object[] obj, int len, boolean key) {
60        for (int i = 0; i < len; i++) {
61            obj[i] = read(buff);
62        }
63    }
64 
65    @Override
66    public void write(WriteBuffer buff, Object[] obj, int len, boolean key) {
67        for (int i = 0; i < len; i++) {
68            write(buff, obj[i]);
69        }
70    }
71 
72    @Override
73    public void write(WriteBuffer buff, Object obj) {
74        SpatialKey k = (SpatialKey) obj;
75        int flags = 0;
76        for (int i = 0; i < dimensions; i++) {
77            if (k.min(i) == k.max(i)) {
78                flags |= 1 << i;
79            }
80        }
81        buff.putVarInt(flags);
82        for (int i = 0; i < dimensions; i++) {
83            buff.putFloat(k.min(i));
84            if ((flags & (1 << i)) == 0) {
85                buff.putFloat(k.max(i));
86            }
87        }
88        buff.putVarLong(k.getId());
89    }
90 
91    @Override
92    public Object read(ByteBuffer buff) {
93        int flags = DataUtils.readVarInt(buff);
94        float[] minMax = new float[dimensions * 2];
95        for (int i = 0; i < dimensions; i++) {
96            float min = buff.getFloat();
97            float max;
98            if ((flags & (1 << i)) != 0) {
99                max = min;
100            } else {
101                max = buff.getFloat();
102            }
103            minMax[i + i] = min;
104            minMax[i + i + 1] = max;
105        }
106        long id = DataUtils.readVarLong(buff);
107        return new SpatialKey(id, minMax);
108    }
109 
110    /**
111     * Check whether the two objects overlap.
112     *
113     * @param objA the first object
114     * @param objB the second object
115     * @return true if they overlap
116     */
117    public boolean isOverlap(Object objA, Object objB) {
118        SpatialKey a = (SpatialKey) objA;
119        SpatialKey b = (SpatialKey) objB;
120        for (int i = 0; i < dimensions; i++) {
121            if (a.max(i) < b.min(i) || a.min(i) > b.max(i)) {
122                return false;
123            }
124        }
125        return true;
126    }
127 
128    /**
129     * Increase the bounds in the given spatial object.
130     *
131     * @param bounds the bounds (may be modified)
132     * @param add the value
133     */
134    public void increaseBounds(Object bounds, Object add) {
135        SpatialKey b = (SpatialKey) bounds;
136        SpatialKey a = (SpatialKey) add;
137        for (int i = 0; i < dimensions; i++) {
138            b.setMin(i, Math.min(b.min(i), a.min(i)));
139            b.setMax(i, Math.max(b.max(i), a.max(i)));
140        }
141    }
142 
143    /**
144     * Get the area increase by extending a to contain b.
145     *
146     * @param objA the bounding box
147     * @param objB the object
148     * @return the area
149     */
150    public float getAreaIncrease(Object objA, Object objB) {
151        SpatialKey a = (SpatialKey) objA;
152        SpatialKey b = (SpatialKey) objB;
153        float min = a.min(0);
154        float max = a.max(0);
155        float areaOld = max - min;
156        min = Math.min(min,  b.min(0));
157        max = Math.max(max,  b.max(0));
158        float areaNew = max - min;
159        for (int i = 1; i < dimensions; i++) {
160            min = a.min(i);
161            max = a.max(i);
162            areaOld *= max - min;
163            min = Math.min(min,  b.min(i));
164            max = Math.max(max,  b.max(i));
165            areaNew *= max - min;
166        }
167        return areaNew - areaOld;
168    }
169 
170    /**
171     * Get the combined area of both objects.
172     *
173     * @param objA the first object
174     * @param objB the second object
175     * @return the area
176     */
177    float getCombinedArea(Object objA, Object objB) {
178        SpatialKey a = (SpatialKey) objA;
179        SpatialKey b = (SpatialKey) objB;
180        float area = 1;
181        for (int i = 0; i < dimensions; i++) {
182            float min = Math.min(a.min(i),  b.min(i));
183            float max = Math.max(a.max(i),  b.max(i));
184            area *= max - min;
185        }
186        return area;
187    }
188 
189    /**
190     * Check whether a contains b.
191     *
192     * @param objA the bounding box
193     * @param objB the object
194     * @return the area
195     */
196    public boolean contains(Object objA, Object objB) {
197        SpatialKey a = (SpatialKey) objA;
198        SpatialKey b = (SpatialKey) objB;
199        for (int i = 0; i < dimensions; i++) {
200            if (a.min(i) > b.min(i) || a.max(i) < b.max(i)) {
201                return false;
202            }
203        }
204        return true;
205    }
206 
207    /**
208     * Check whether a is completely inside b and does not touch the
209     * given bound.
210     *
211     * @param objA the object to check
212     * @param objB the bounds
213     * @return true if a is completely inside b
214     */
215    public boolean isInside(Object objA, Object objB) {
216        SpatialKey a = (SpatialKey) objA;
217        SpatialKey b = (SpatialKey) objB;
218        for (int i = 0; i < dimensions; i++) {
219            if (a.min(i) <= b.min(i) || a.max(i) >= b.max(i)) {
220                return false;
221            }
222        }
223        return true;
224    }
225 
226    /**
227     * Create a bounding box starting with the given object.
228     *
229     * @param objA the object
230     * @return the bounding box
231     */
232    Object createBoundingBox(Object objA) {
233        float[] minMax = new float[dimensions * 2];
234        SpatialKey a = (SpatialKey) objA;
235        for (int i = 0; i < dimensions; i++) {
236            minMax[i + i] = a.min(i);
237            minMax[i + i + 1] = a.max(i);
238        }
239        return new SpatialKey(0, minMax);
240    }
241 
242    /**
243     * Get the most extreme pair (elements that are as far apart as possible).
244     * This method is used to split a page (linear split). If no extreme objects
245     * could be found, this method returns null.
246     *
247     * @param list the objects
248     * @return the indexes of the extremes
249     */
250    public int[] getExtremes(ArrayList<Object> list) {
251        SpatialKey bounds = (SpatialKey) createBoundingBox(list.get(0));
252        SpatialKey boundsInner = (SpatialKey) createBoundingBox(bounds);
253        for (int i = 0; i < dimensions; i++) {
254            float t = boundsInner.min(i);
255            boundsInner.setMin(i, boundsInner.max(i));
256            boundsInner.setMax(i, t);
257        }
258        for (int i = 0; i < list.size(); i++) {
259            Object o = list.get(i);
260            increaseBounds(bounds, o);
261            increaseMaxInnerBounds(boundsInner, o);
262        }
263        double best = 0;
264        int bestDim = 0;
265        for (int i = 0; i < dimensions; i++) {
266            float inner = boundsInner.max(i) - boundsInner.min(i);
267            if (inner < 0) {
268                continue;
269            }
270            float outer = bounds.max(i) - bounds.min(i);
271            float d = inner / outer;
272            if (d > best) {
273                best = d;
274                bestDim = i;
275            }
276        }
277        if (best <= 0) {
278            return null;
279        }
280        float min = boundsInner.min(bestDim);
281        float max = boundsInner.max(bestDim);
282        int firstIndex = -1, lastIndex = -1;
283        for (int i = 0; i < list.size() &&
284                (firstIndex < 0 || lastIndex < 0); i++) {
285            SpatialKey o = (SpatialKey) list.get(i);
286            if (firstIndex < 0 && o.max(bestDim) == min) {
287                firstIndex = i;
288            } else if (lastIndex < 0 && o.min(bestDim) == max) {
289                lastIndex = i;
290            }
291        }
292        return new int[] { firstIndex, lastIndex };
293    }
294 
295    private void increaseMaxInnerBounds(Object bounds, Object add) {
296        SpatialKey b = (SpatialKey) bounds;
297        SpatialKey a = (SpatialKey) add;
298        for (int i = 0; i < dimensions; i++) {
299            b.setMin(i, Math.min(b.min(i), a.max(i)));
300            b.setMax(i, Math.max(b.max(i), a.min(i)));
301        }
302    }
303 
304}

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