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 | */ |
6 | package org.h2.mvstore.rtree; |
7 | |
8 | import java.util.ArrayList; |
9 | import java.util.Iterator; |
10 | |
11 | import org.h2.mvstore.CursorPos; |
12 | import org.h2.mvstore.DataUtils; |
13 | import org.h2.mvstore.MVMap; |
14 | import org.h2.mvstore.Page; |
15 | import org.h2.mvstore.type.DataType; |
16 | import org.h2.mvstore.type.ObjectDataType; |
17 | import 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 | */ |
24 | public 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 | } |