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

COVERAGE SUMMARY FOR SOURCE FILE [MVRTreeMap.java]

nameclass, %method, %block, %line, %
MVRTreeMap.java100% (5/5)85%  (33/39)94%  (1161/1230)95%  (249.9/264)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class MVRTreeMap$RTreeCursor100% (1/1)57%  (4/7)87%  (150/172)86%  (38/44)
check (boolean, SpatialKey, SpatialKey): boolean 0%   (0/1)0%   (0/2)0%   (0/1)
remove (): void 0%   (0/1)0%   (0/3)0%   (0/1)
skip (long): void 0%   (0/1)0%   (0/15)0%   (0/3)
next (): SpatialKey 100% (1/1)83%  (10/12)80%  (4/5)
MVRTreeMap$RTreeCursor (Page, SpatialKey): void 100% (1/1)100% (9/9)100% (4/4)
fetchNext (): void 100% (1/1)100% (107/107)100% (25/25)
hasNext (): boolean 100% (1/1)100% (24/24)100% (5/5)
     
class MVRTreeMap100% (1/1)88%  (21/24)95%  (940/987)96%  (197.9/206)
addNodeKeys (ArrayList, Page): void 0%   (0/1)0%   (0/27)0%   (0/5)
create (int, DataType): MVRTreeMap 0%   (0/1)0%   (0/6)0%   (0/1)
isQuadraticSplit (): boolean 0%   (0/1)0%   (0/3)0%   (0/1)
set (Page, long, Object, Object): Object 100% (1/1)85%  (64/75)91%  (11.9/13)
MVRTreeMap (int, DataType): void 100% (1/1)100% (13/13)100% (3/3)
add (Page, long, Object, Object): void 100% (1/1)100% (128/128)100% (30/30)
add (SpatialKey, Object): void 100% (1/1)100% (7/7)100% (2/2)
contains (Page, int, Object): boolean 100% (1/1)100% (8/8)100% (1/1)
findContainedKeys (SpatialKey): MVRTreeMap$RTreeCursor 100% (1/1)100% (8/8)100% (1/1)
findIntersectingKeys (SpatialKey): MVRTreeMap$RTreeCursor 100% (1/1)100% (8/8)100% (1/1)
get (Object): Object 100% (1/1)100% (6/6)100% (1/1)
get (Page, Object): Object 100% (1/1)100% (51/51)100% (10/10)
getBounds (Page): Object 100% (1/1)100% (24/24)100% (4/4)
getChildPageCount (Page): int 100% (1/1)100% (5/5)100% (1/1)
getType (): String 100% (1/1)100% (2/2)100% (1/1)
move (Page, Page, int): void 100% (1/1)100% (30/30)100% (9/9)
newPage (boolean, long): Page 100% (1/1)100% (30/30)100% (6/6)
put (SpatialKey, Object): Object 100% (1/1)100% (6/6)100% (1/1)
putOrAdd (SpatialKey, Object, boolean): Object 100% (1/1)100% (117/117)100% (17/17)
remove (Page, long, Object): Object 100% (1/1)100% (105/105)100% (25/25)
setQuadraticSplit (boolean): void 100% (1/1)100% (4/4)100% (2/2)
split (Page, long): Page 100% (1/1)100% (13/13)100% (1/1)
splitLinear (Page, long): Page 100% (1/1)100% (133/133)100% (27/27)
splitQuadratic (Page, long): Page 100% (1/1)100% (178/178)100% (43/43)
     
class MVRTreeMap$1100% (1/1)100% (2/2)100% (15/15)100% (2/2)
MVRTreeMap$1 (MVRTreeMap, Page, SpatialKey): void 100% (1/1)100% (8/8)100% (1/1)
check (boolean, SpatialKey, SpatialKey): boolean 100% (1/1)100% (7/7)100% (1/1)
     
class MVRTreeMap$2100% (1/1)100% (2/2)100% (24/24)100% (4/4)
MVRTreeMap$2 (MVRTreeMap, Page, SpatialKey): void 100% (1/1)100% (8/8)100% (1/1)
check (boolean, SpatialKey, SpatialKey): boolean 100% (1/1)100% (16/16)100% (3/3)
     
class MVRTreeMap$Builder100% (1/1)100% (4/4)100% (32/32)100% (10/10)
MVRTreeMap$Builder (): void 100% (1/1)100% (6/6)100% (3/3)
create (): MVRTreeMap 100% (1/1)100% (16/16)100% (3/3)
dimensions (int): MVRTreeMap$Builder 100% (1/1)100% (5/5)100% (2/2)
valueType (DataType): MVRTreeMap$Builder 100% (1/1)100% (5/5)100% (2/2)

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.util.ArrayList;
9import java.util.Iterator;
10 
11import org.h2.mvstore.CursorPos;
12import org.h2.mvstore.DataUtils;
13import org.h2.mvstore.MVMap;
14import org.h2.mvstore.Page;
15import org.h2.mvstore.type.DataType;
16import org.h2.mvstore.type.ObjectDataType;
17import org.h2.util.New;
18 
19/**
20 * An r-tree implementation. It uses the quadratic split algorithm.
21 *
22 * @param <V> the value class
23 */
24public class MVRTreeMap<V> extends MVMap<SpatialKey, V> {
25 
26    /**
27     * The spatial key type.
28     */
29    final SpatialDataType keyType;
30 
31    private boolean quadraticSplit;
32 
33    public MVRTreeMap(int dimensions, DataType valueType) {
34        super(new SpatialDataType(dimensions), valueType);
35        this.keyType = (SpatialDataType) getKeyType();
36    }
37 
38    /**
39     * Create a new map with the given dimensions and value type.
40     *
41     * @param <V> the value type
42     * @param dimensions the number of dimensions
43     * @param valueType the value type
44     * @return the map
45     */
46    public static <V> MVRTreeMap<V> create(int dimensions, DataType valueType) {
47        return new MVRTreeMap<V>(dimensions, valueType);
48    }
49 
50    @Override
51    @SuppressWarnings("unchecked")
52    public V get(Object key) {
53        return (V) get(root, key);
54    }
55 
56    /**
57     * Iterate over all keys that have an intersection with the given rectangle.
58     *
59     * @param x the rectangle
60     * @return the iterator
61     */
62    public RTreeCursor findIntersectingKeys(SpatialKey x) {
63        return new RTreeCursor(root, x) {
64            @Override
65            protected boolean check(boolean leaf, SpatialKey key,
66                    SpatialKey test) {
67                return keyType.isOverlap(key, test);
68            }
69        };
70    }
71 
72    /**
73     * Iterate over all keys that are fully contained within the given
74     * rectangle.
75     *
76     * @param x the rectangle
77     * @return the iterator
78     */
79    public RTreeCursor findContainedKeys(SpatialKey x) {
80        return new RTreeCursor(root, x) {
81            @Override
82            protected boolean check(boolean leaf, SpatialKey key,
83                    SpatialKey test) {
84                if (leaf) {
85                    return keyType.isInside(key, test);
86                }
87                return keyType.isOverlap(key, test);
88            }
89        };
90    }
91 
92    private boolean contains(Page p, int index, Object key) {
93        return keyType.contains(p.getKey(index), key);
94    }
95 
96    /**
97     * Get the object for the given key. An exact match is required.
98     *
99     * @param p the page
100     * @param key the key
101     * @return the value, or null if not found
102     */
103    protected Object get(Page p, Object key) {
104        if (!p.isLeaf()) {
105            for (int i = 0; i < p.getKeyCount(); i++) {
106                if (contains(p, i, key)) {
107                    Object o = get(p.getChildPage(i), key);
108                    if (o != null) {
109                        return o;
110                    }
111                }
112            }
113        } else {
114            for (int i = 0; i < p.getKeyCount(); i++) {
115                if (keyType.equals(p.getKey(i), key)) {
116                    return p.getValue(i);
117                }
118            }
119        }
120        return null;
121    }
122 
123    @Override
124    protected synchronized Object remove(Page p, long writeVersion, Object key) {
125        Object result = null;
126        if (p.isLeaf()) {
127            for (int i = 0; i < p.getKeyCount(); i++) {
128                if (keyType.equals(p.getKey(i), key)) {
129                    result = p.getValue(i);
130                    p.remove(i);
131                    break;
132                }
133            }
134            return result;
135        }
136        for (int i = 0; i < p.getKeyCount(); i++) {
137            if (contains(p, i, key)) {
138                Page cOld = p.getChildPage(i);
139                // this will mark the old page as deleted
140                // so we need to update the parent in any case
141                // (otherwise the old page might be deleted again)
142                Page c = cOld.copy(writeVersion);
143                long oldSize = c.getTotalCount();
144                result = remove(c, writeVersion, key);
145                p.setChild(i, c);
146                if (oldSize == c.getTotalCount()) {
147                    continue;
148                }
149                if (c.getTotalCount() == 0) {
150                    // this child was deleted
151                    p.remove(i);
152                    if (p.getKeyCount() == 0) {
153                        c.removePage();
154                    }
155                    break;
156                }
157                Object oldBounds = p.getKey(i);
158                if (!keyType.isInside(key, oldBounds)) {
159                    p.setKey(i, getBounds(c));
160                }
161                break;
162            }
163        }
164        return result;
165    }
166 
167    private Object getBounds(Page x) {
168        Object bounds = keyType.createBoundingBox(x.getKey(0));
169        for (int i = 1; i < x.getKeyCount(); i++) {
170            keyType.increaseBounds(bounds, x.getKey(i));
171        }
172        return bounds;
173    }
174 
175    @Override
176    @SuppressWarnings("unchecked")
177    public V put(SpatialKey key, V value) {
178        return (V) putOrAdd(key, value, false);
179    }
180 
181    /**
182     * Add a given key-value pair. The key should not exist (if it exists, the
183     * result is undefined).
184     *
185     * @param key the key
186     * @param value the value
187     */
188    public void add(SpatialKey key, V value) {
189        putOrAdd(key, value, true);
190    }
191 
192    private synchronized Object putOrAdd(SpatialKey key, V value, boolean alwaysAdd) {
193        beforeWrite();
194        long v = writeVersion;
195        Page p = root.copy(v);
196        Object result;
197        if (alwaysAdd || get(key) == null) {
198            if (p.getMemory() > store.getPageSplitSize() &&
199                    p.getKeyCount() > 3) {
200                // only possible if this is the root, else we would have
201                // split earlier (this requires pageSplitSize is fixed)
202                long totalCount = p.getTotalCount();
203                Page split = split(p, v);
204                Object k1 = getBounds(p);
205                Object k2 = getBounds(split);
206                Object[] keys = { k1, k2 };
207                Page.PageReference[] children = {
208                        new Page.PageReference(p, p.getPos(), p.getTotalCount()),
209                        new Page.PageReference(split, split.getPos(), split.getTotalCount()),
210                        new Page.PageReference(null, 0, 0)
211                };
212                p = Page.create(this, v,
213                        keys, null,
214                        children,
215                        totalCount, 0);
216                // now p is a node; continues
217            }
218            add(p, v, key, value);
219            result = null;
220        } else {
221            result = set(p, v, key, value);
222        }
223        newRoot(p);
224        return result;
225    }
226 
227    /**
228     * Update the value for the given key. The key must exist.
229     *
230     * @param p the page
231     * @param writeVersion the write version
232     * @param key the key
233     * @param value the new value
234     * @return the old value (never null)
235     */
236    private Object set(Page p, long writeVersion, Object key, Object value) {
237        if (p.isLeaf()) {
238            for (int i = 0; i < p.getKeyCount(); i++) {
239                if (keyType.equals(p.getKey(i), key)) {
240                    return p.setValue(i, value);
241                }
242            }
243        } else {
244            for (int i = 0; i < p.getKeyCount(); i++) {
245                if (contains(p, i, key)) {
246                    Page c = p.getChildPage(i);
247                    if (get(c, key) != null) {
248                        c = c.copy(writeVersion);
249                        Object result = set(c, writeVersion, key, value);
250                        p.setChild(i, c);
251                        return result;
252                    }
253                }
254            }
255        }
256        throw DataUtils.newIllegalStateException(DataUtils.ERROR_INTERNAL,
257                "Not found: {0}", key);
258    }
259 
260    private void add(Page p, long writeVersion, Object key, Object value) {
261        if (p.isLeaf()) {
262            p.insertLeaf(p.getKeyCount(), key, value);
263            return;
264        }
265        // p is a node
266        int index = -1;
267        for (int i = 0; i < p.getKeyCount(); i++) {
268            if (contains(p, i, key)) {
269                index = i;
270                break;
271            }
272        }
273        if (index < 0) {
274            // a new entry, we don't know where to add yet
275            float min = Float.MAX_VALUE;
276            for (int i = 0; i < p.getKeyCount(); i++) {
277                Object k = p.getKey(i);
278                float areaIncrease = keyType.getAreaIncrease(k, key);
279                if (areaIncrease < min) {
280                    index = i;
281                    min = areaIncrease;
282                }
283            }
284        }
285        Page c = p.getChildPage(index).copy(writeVersion);
286        if (c.getMemory() > store.getPageSplitSize() && c.getKeyCount() > 4) {
287            // split on the way down
288            Page split = split(c, writeVersion);
289            p.setKey(index, getBounds(c));
290            p.setChild(index, c);
291            p.insertNode(index, getBounds(split), split);
292            // now we are not sure where to add
293            add(p, writeVersion, key, value);
294            return;
295        }
296        add(c, writeVersion, key, value);
297        Object bounds = p.getKey(index);
298        keyType.increaseBounds(bounds, key);
299        p.setKey(index, bounds);
300        p.setChild(index, c);
301    }
302 
303    private Page split(Page p, long writeVersion) {
304        return quadraticSplit ?
305                splitQuadratic(p, writeVersion) :
306                splitLinear(p, writeVersion);
307    }
308 
309    private Page splitLinear(Page p, long writeVersion) {
310        ArrayList<Object> keys = New.arrayList();
311        for (int i = 0; i < p.getKeyCount(); i++) {
312            keys.add(p.getKey(i));
313        }
314        int[] extremes = keyType.getExtremes(keys);
315        if (extremes == null) {
316            return splitQuadratic(p, writeVersion);
317        }
318        Page splitA = newPage(p.isLeaf(), writeVersion);
319        Page splitB = newPage(p.isLeaf(), writeVersion);
320        move(p, splitA, extremes[0]);
321        if (extremes[1] > extremes[0]) {
322            extremes[1]--;
323        }
324        move(p, splitB, extremes[1]);
325        Object boundsA = keyType.createBoundingBox(splitA.getKey(0));
326        Object boundsB = keyType.createBoundingBox(splitB.getKey(0));
327        while (p.getKeyCount() > 0) {
328            Object o = p.getKey(0);
329            float a = keyType.getAreaIncrease(boundsA, o);
330            float b = keyType.getAreaIncrease(boundsB, o);
331            if (a < b) {
332                keyType.increaseBounds(boundsA, o);
333                move(p, splitA, 0);
334            } else {
335                keyType.increaseBounds(boundsB, o);
336                move(p, splitB, 0);
337            }
338        }
339        while (splitB.getKeyCount() > 0) {
340            move(splitB, p, 0);
341        }
342        return splitA;
343    }
344 
345    private Page splitQuadratic(Page p, long writeVersion) {
346        Page splitA = newPage(p.isLeaf(), writeVersion);
347        Page splitB = newPage(p.isLeaf(), writeVersion);
348        float largest = Float.MIN_VALUE;
349        int ia = 0, ib = 0;
350        for (int a = 0; a < p.getKeyCount(); a++) {
351            Object objA = p.getKey(a);
352            for (int b = 0; b < p.getKeyCount(); b++) {
353                if (a == b) {
354                    continue;
355                }
356                Object objB = p.getKey(b);
357                float area = keyType.getCombinedArea(objA, objB);
358                if (area > largest) {
359                    largest = area;
360                    ia = a;
361                    ib = b;
362                }
363            }
364        }
365        move(p, splitA, ia);
366        if (ia < ib) {
367            ib--;
368        }
369        move(p, splitB, ib);
370        Object boundsA = keyType.createBoundingBox(splitA.getKey(0));
371        Object boundsB = keyType.createBoundingBox(splitB.getKey(0));
372        while (p.getKeyCount() > 0) {
373            float diff = 0, bestA = 0, bestB = 0;
374            int best = 0;
375            for (int i = 0; i < p.getKeyCount(); i++) {
376                Object o = p.getKey(i);
377                float incA = keyType.getAreaIncrease(boundsA, o);
378                float incB = keyType.getAreaIncrease(boundsB, o);
379                float d = Math.abs(incA - incB);
380                if (d > diff) {
381                    diff = d;
382                    bestA = incA;
383                    bestB = incB;
384                    best = i;
385                }
386            }
387            if (bestA < bestB) {
388                keyType.increaseBounds(boundsA, p.getKey(best));
389                move(p, splitA, best);
390            } else {
391                keyType.increaseBounds(boundsB, p.getKey(best));
392                move(p, splitB, best);
393            }
394        }
395        while (splitB.getKeyCount() > 0) {
396            move(splitB, p, 0);
397        }
398        return splitA;
399    }
400 
401    private Page newPage(boolean leaf, long writeVersion) {
402        Object[] values;
403        Page.PageReference[] refs;
404        if (leaf) {
405            values = Page.EMPTY_OBJECT_ARRAY;
406            refs = null;
407        } else {
408            values = null;
409            refs = new Page.PageReference[] {
410                    new Page.PageReference(null, 0, 0)};
411        }
412        return Page.create(this, writeVersion,
413                Page.EMPTY_OBJECT_ARRAY, values,
414                refs, 0, 0);
415    }
416 
417    private static void move(Page source, Page target, int sourceIndex) {
418        Object k = source.getKey(sourceIndex);
419        if (source.isLeaf()) {
420            Object v = source.getValue(sourceIndex);
421            target.insertLeaf(0, k, v);
422        } else {
423            Page c = source.getChildPage(sourceIndex);
424            target.insertNode(0, k, c);
425        }
426        source.remove(sourceIndex);
427    }
428 
429    /**
430     * Add all node keys (including internal bounds) to the given list.
431     * This is mainly used to visualize the internal splits.
432     *
433     * @param list the list
434     * @param p the root page
435     */
436    public void addNodeKeys(ArrayList<SpatialKey> list, Page p) {
437        if (p != null && !p.isLeaf()) {
438            for (int i = 0; i < p.getKeyCount(); i++) {
439                list.add((SpatialKey) p.getKey(i));
440                addNodeKeys(list, p.getChildPage(i));
441            }
442        }
443    }
444 
445    public boolean isQuadraticSplit() {
446        return quadraticSplit;
447    }
448 
449    public void setQuadraticSplit(boolean quadraticSplit) {
450        this.quadraticSplit = quadraticSplit;
451    }
452 
453    @Override
454    protected int getChildPageCount(Page p) {
455        return p.getRawChildPageCount() - 1;
456    }
457 
458    /**
459     * A cursor to iterate over a subset of the keys.
460     */
461    public static class RTreeCursor implements Iterator<SpatialKey> {
462 
463        private final SpatialKey filter;
464        private CursorPos pos;
465        private SpatialKey current;
466        private final Page root;
467        private boolean initialized;
468 
469        protected RTreeCursor(Page root, SpatialKey filter) {
470            this.root = root;
471            this.filter = filter;
472        }
473 
474        @Override
475        public boolean hasNext() {
476            if (!initialized) {
477                // init
478                pos = new CursorPos(root, 0, null);
479                fetchNext();
480                initialized = true;
481            }
482            return current != null;
483        }
484 
485        /**
486         * Skip over that many entries. This method is relatively fast (for this
487         * map implementation) even if many entries need to be skipped.
488         *
489         * @param n the number of entries to skip
490         */
491        public void skip(long n) {
492            while (hasNext() && n-- > 0) {
493                fetchNext();
494            }
495        }
496 
497        @Override
498        public SpatialKey next() {
499            if (!hasNext()) {
500                return null;
501            }
502            SpatialKey c = current;
503            fetchNext();
504            return c;
505        }
506 
507        @Override
508        public void remove() {
509            throw DataUtils.newUnsupportedOperationException(
510                    "Removing is not supported");
511        }
512 
513        /**
514         * Fetch the next entry if there is one.
515         */
516        protected void fetchNext() {
517            while (pos != null) {
518                Page p = pos.page;
519                if (p.isLeaf()) {
520                    while (pos.index < p.getKeyCount()) {
521                        SpatialKey c = (SpatialKey) p.getKey(pos.index++);
522                        if (filter == null || check(true, c, filter)) {
523                            current = c;
524                            return;
525                        }
526                    }
527                } else {
528                    boolean found = false;
529                    while (pos.index < p.getKeyCount()) {
530                        int index = pos.index++;
531                        SpatialKey c = (SpatialKey) p.getKey(index);
532                        if (filter == null || check(false, c, filter)) {
533                            Page child = pos.page.getChildPage(index);
534                            pos = new CursorPos(child, 0, pos);
535                            found = true;
536                            break;
537                        }
538                    }
539                    if (found) {
540                        continue;
541                    }
542                }
543                // parent
544                pos = pos.parent;
545            }
546            current = null;
547        }
548 
549        /**
550         * Check a given key.
551         *
552         * @param leaf if the key is from a leaf page
553         * @param key the stored key
554         * @param test the user-supplied test key
555         * @return true if there is a match
556         */
557        protected boolean check(boolean leaf, SpatialKey key, SpatialKey test) {
558            return true;
559        }
560 
561    }
562 
563    @Override
564    public String getType() {
565        return "rtree";
566    }
567 
568    /**
569     * A builder for this class.
570     *
571     * @param <V> the value type
572     */
573    public static class Builder<V> implements
574            MVMap.MapBuilder<MVRTreeMap<V>, SpatialKey, V> {
575 
576        private int dimensions = 2;
577        private DataType valueType;
578 
579        /**
580         * Create a new builder for maps with 2 dimensions.
581         */
582        public Builder() {
583            // default
584        }
585 
586        /**
587         * Set the dimensions.
588         *
589         * @param dimensions the dimensions to use
590         * @return this
591         */
592        public Builder<V> dimensions(int dimensions) {
593            this.dimensions = dimensions;
594            return this;
595        }
596 
597        /**
598         * Set the key data type.
599         *
600         * @param valueType the key type
601         * @return this
602         */
603        public Builder<V> valueType(DataType valueType) {
604            this.valueType = valueType;
605            return this;
606        }
607 
608        @Override
609        public MVRTreeMap<V> create() {
610            if (valueType == null) {
611                valueType = new ObjectDataType();
612            }
613            return new MVRTreeMap<V>(dimensions, valueType);
614        }
615 
616    }
617 
618}

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